Thank you for your time and valuable feedback! We have tried to address your concerns below:

Weakness:

The evaluation is somewhat lacking, only evaluated on blocksworld and GSM8K, and ablations were missing (only statistics of # of actions were given), no intuition on how to tune the hyperparameters B,K,C

• The primary rationale behind selecting Blocksworld and GSM8K is rooted in their suitability for evaluating distinct facets: Blocksworld provides an ideal dataset for assessing the planning capability of LLM and its respective technique, while GSM8K offers a suitable dataset for evaluating problem-solving abilities. We consider these two categories of datasets, focusing on Planning and Problem Solving, as strong benchmarks for our evaluation.
• B, K, C values we set based on the grid search technique. We set a reasonable range for all the parameters - $1 \leq C \leq 10000$ , $1 \leq B \leq 1000$, $1 \leq K \leq 1000$ and ran a grid search to approximate the values.

Questions:

How come RAP scores are missing for every evaluated environment? It is mentioned RAP is not compatible with OAI APIs, maybe supply more results with open-source models?
We added RAP to demonstrate its slower performance compared to REX in problem-solving. Reflexion and CoT were used as other advanced techniques for performance comparison.

how was each action generated? If im not mistaken they are each reasoning steps. And if temperature is 0, how come there are variations to the steps generated when prompted twice? is it caused by using previous history of steps in the UCB prompt (State-Action-Feedback in figure 4)?

• The LLM receives input comprising details about the problem requiring a solution, a set of few-shot examples, and potential actions derived from previous interactions, each categorized as HIGH or LOW (as outlined in Algorithm 1 in the paper). The LLM is then prompted to select an action with a higher likelihood of success at each stage. Further elaboration on the specific prompt structure and action generation is provided in Section B of the Appendix, while Section C contains illustrative examples.
• Based on the trajectory and the final answer generated by the LLM, rewards are computed following the procedure outlined in Algorithm 1 in the paper. These rewards are utilized to calculate UCB scores (equation 1), which are further categorized as HIGH or LOW. Subsequently, these categorized scores are incorporated into the prompt for the succeeding iteration. In essence, the Agent suggests a solution, receives feedback, and then proposes a different solution in the subsequent iteration based on this received feedback. In our context, the Agent is represented by the LLM, and each prompt iteration contains updated information on the effectiveness of the (state, action) pair. Therefore, setting the temperature (t) to 0 should not inhibit the Agent from suggesting alternative solutions. More details on this is available in Section B & C of the Appendix.

Do you have some intuition on when is REX-UCL better than REX-UCB and vice-versa? (Paper only included REX-UCL is better at exploration than REX-R)

• Accuracy:
  • REX-UCL demonstrates strong performance in mathematical reasoning scenarios, particularly in cases with a significantly expansive action space. For instance, in GSM8K where the number of operands can be extensive, REX-UCL effectively narrows down the action space by effectively suppressing the respective logits.
  • REX-UCB tends to perform well in planning scenarios, where the action space is bounded.
• Speed:
  • REX-UCB is faster than REX-UCL, below is the number of API calls made by these two techniques for Blocksworld and GSM8K datasets: | Method | Blocksworld | GSM8K | |-----------|-------------|-----------| |REX-UCB| 10 |10| |REX-UCL| 60 |80| (For Blocksworld, depth(d)=6, number of passes(n)=10, number of potential actions(m)=4; For GSM8K, depth(d)=8, number of passes(n)=10, number of potential actions(m)=4)

How come when more steps (6) is required, method is worse than Reflexion? Shouldn't it be the opposite, since REX employs search trees. Do you have any intuition?
Reflexion utilizes natural language feedback, whereas REX employs a simpler form of feedback, either HIGH/LOW or a scalar value. We posit that in specific scenarios, natural language feedback may convey more valuable information compared to our proposed feedback system. Consequently, Reflexion outperforms REX in the 6-step subset. Our approach is particularly advantageous in real-world situations where the true nature of an action remains ambiguous, such as when selecting an API. In such cases, we believe our strategy holds an advantage. Results in Table 1 are averaged over 10 runs/iterations. While 10 iterations suffice for a 2-step problem to find a solution, arriving at the correct solution quickly may be more challenging for a 6-step problem.

Thank you for your time and valuable feedback! We have tried to address your concerns below:

Questions:

- Consider adjusting the visuals here to make the differences clearer. Perhaps by showing where LLM evaluations occur along the search tree to make it clearer that REX-UCL is evaluating the LLM for each step of the depth of the tree.
- Figure 3 was helpful, but I could not understand what Figure 2 was meant to illustrate by highlighting some lines in the rollout as red.
The primary purpose of Figure 2 is to illustrate the transformation of the classical MCTS technique into various REX variations. Figure 2(b) specifically details the rollout strategy for REX-UCL. The phrase 'Repeat d times,' highlighted in red in Figure 2(b), signifies invoking the LLM 'd' times. As each invocation of LLM triggers the simultaneous execution of the Selection and Expansion steps within the REX-UCL strategy, the loop is situated under these blocks. Additionally, the red arrow marks in Figure 2(b) represent the step-by-step invocation of LLM. Further elaboration on the LLM input, specifically the prompt structures for REX-UCB and REX-UCL, is provided in section B of the Appendix.

Is it possible to provide uncertainty estimates on the scores provided? (For example, using multiple seeds for different runs of the algorithms)
We have set the temperature to 0.0 to ensure that it does not obscure the effectiveness of the proposed approach and to facilitate a stable comparison. The following stats were derived from 5 runs each with gpt-3.5-turbo-0301 LLM. We applied REX-UCB and REX-UCL to the Blocksworld dataset to demonstrate the observable level of uncertainty. For the results reported in the paper, the same experimental setup was used for other techniques (CoT, Reflexion) as well. The mean(μ) and standard deviation(σ) of number of correct answers across 5 runs is presented below:

Note: In the paper, the results reported are average over 10 runs.

What is the intuition for why the REX methods do worse in the largest Blocksworld scenario?
As the complexity of a problem increases (measured in terms of the number of steps required to solve it), the permutations of action sequences, i.e., trajectories, also increase. For instance, in the 6-step Blocksworld problem, which comprises 6 steps involving 4 actions (pick, put, stack, unstack) and several blocks, there are approximately 6 * 4 * 4 (= 96) potential actions to consider simultaneously. This potentially contributes to a decline in the model's performance. Moreover, we conducted all experiments with 10 runs/passes. Increasing the number of runs for more complex problems could potentially enhance performance.

Is there other evidence for the strength of REX on GSM8k-test?
As already stated, the experimental results were obtained by averaging the results across 10 random runs. This supports the robust and consistent superiority of REX over Reflexion and CoT. As you have pointed out, REX has superior speed when d<=3.

What search depth(s) (d) were used for the experiments?
We have set d=6 for Blocksworld and d=8 for GSM8K.

Could the results in table 1 be replicated with a model that exposes logits and compared?
(Currently working on it. Will share the results soon.)

How were C, B, and K selected for the experiments? The above values we set based on the grid search technique. We set a reasonable range for all the parameters - $1 \leq C \leq 10000$, $1 \leq B \leq 1000$, $1 \leq K \leq 1000$ and ran a grid search to approximate the values.

Consider computing the results with (approximately) matching compute budgets for the methods being compared. Ideally this would be a matching number of generated tokens. A more coarse comparison would be matching the number of inference calls made. Regardless, some baseline equivalence should be established for the compute budget to allow fair comparison of the accuracy.
The time complexity presented in Table 1 roughly addresses this concern. Below is the number of inference calls made by each of the techniques for every task/problem in Blocksworld and GSM8K datasets: (For Blocksworld, depth(d)=6, number of passes(n)=10, number of potential actions(m)=4; For GSM8K, depth(d)=8, number of passes(n)=10, number of potential actions(m)=4)

Thank you for your time and valuable feedback! We have tried to address your concerns below:

Questions:

1. The paper presents two algorithms : REX-UCB and REX-R, which differ only in the way the rewards are classified. I wonder whether these could have been unified into one coherent approach. If not, it is important to explicitly mention when one should use which algorithm.

• As noted in the paper, REX-R equals REX-UCB when setting the constant $C$ in equation (1) to zero. We introduced these two distinct approaches to highlight the importance of the UCB score over absolute reward. Merely relying on feedback (as Reward) isn't enough for optimal performance; achieving superior results requires a nuanced balance between exploring and exploiting the action space.
• REX-UCB has showcased better performance compared to REX-R, indicating our preference for REX-UCB across all scenarios. The introduction of REX-R aimed to emphasize that relying solely on Reward for feedback does not lead to optimal performance, as highlighted in the earlier point.

2. Is the approach limited to discrete actions? Could it be adapted for continuous action space problems?
Yes, in most cases, the approach can be extended to a continuous action space.

• A straightforward method involves converting the continuous space into a discrete one. However, this approach would yield discrete actions rather than continuous ones.
• If the continuous action space possesses inherent ordering, such as being all positive real numbers ($\mathbb{R}^+$), the algorithm remains applicable but may introduce some associated error. This reliance largely hinges on the LLM's capacity to discern relative distinctions among various actions. For instance, within the $\mathbb{R}^+$ action space, actions with greater absolute values might yield higher rewards. Consequently, the LLM might learn to predict higher-value actions. Conversely, if cyclic patterns exist between the reward and action space, the LLM might face potential confusion. In summary, REX can definitely be used for continuous action space, but REX's performance in continuous action spaces is contingent upon factors like the environment's nature, the underlying LLM employed, and the complexity of the problem.

3. Is it assumed that a user can map the UCB scores to HIGH/LOW? This may not always be possible.
No, this assumption was never made. In Algorithm 1, line 5, we can see that the action with the highest UCB score gets 'HIGH' and all the remaining actions get 'LOW'. The user is never involved in any of the REX algorithms.

4. Can the method deal with non-binary rewards?
Certainly! The current REX implementation supports non-binary rewards. Essentially, our approach utilizes UCB scores, meaning if the UCB formula can handle diverse rewards, our approach can as well.

5. How would the method fare in tasks that involve a long sequence of steps till the final solution is found? Would the LLM’s prediction accuracy (of intermediate steps -with reference to line 7 in Alg 1) be a limitating factor in such tasks?
Indeed, as outlined in the "Limitations" in Section 5.4 of the paper, our approach relies on In-Context learning, where the input size limitation of the LLM poses a constraint. However, a potential workaround involves segmenting the sequence of actions, summarizing them, and adding them to the prompt. While this solution may partially alleviate the problem, it won't completely resolve it.

6. Can the tasks described be solved with reinforcement learning alone? If so, this would be a natural baseline to add to the experiments.
Not really. We have taken into account benchmark datasets like GSM8K, where questions are presented in natural language. Thus, relying solely on RL techniques is impractical in this scenario.

7. An intuitive example to accompany 1. And 2. In Section 4.1 would have provided a much clearer picture of the approach.
Examples are provided in Section C of the Appendix. Happy to share more examples, if you're interested.

8. The introduction could have included more emphasis about how the contributions (1), (2) and (3) are achieved.
In the Introduction, our emphasis has been on establishing the significance and current trends in Autonomous Agents. We consider it vital to convey the motivation behind our project. The achievement of (1), (2), and (3) is outlined in the final paragraph of the Introduction. We delve deeper into these aspects within the "Proposed Methodology" and "Experiments" sections.

9. In section 4.1 - `form’ should be ‘from’. This mistake is also repeated in later parts of the paper.
Thank you for helping us identify this typo. We have corrected it.

Thank you for your time and valuable feedback! We have tried to address your concerns below:

Weaknesses:

First, I consider that the authors should compare of the performance of their LLM-based approaches with SOTA methods that are not based on LLMs.
Our paper focuses on demonstrating the efficiency of MCTS, particularly the UCB scoring mechanism, within LLMs. Comparing with non-LLM methods might not be feasible for datasets where questions are in natural language, making it challenging to adapt them to non-LLM approaches. Dataset nature impacts comparison feasibility; transforming natural language to discrete states for non-LLM methods may not be viable for all datasets. Hence we have only considered LLM-based approaches for comparison.

Second, the authors state that "RAP is not compatible with OpenAI APIs; therefore, we have exclusively focused on evaluating the time complexity of RAP, without delving into its accuracy", but I do not think that this is a good reason why the authors do not have to empirically evaluate RAP.
We added RAP to demonstrate its slower performance compared to REX in problem-solving. Reflexion and CoT were used as other advanced techniques for performance comparison.

I would recommend the authors to at least the similarities and differences and compare the authors' proposed method with Yao et al. (2023) in same benchmarks.
Although visually similar, REX and ToT differ in several ways:

1. ToT samples possible actions at each state and pursues the most promising action based on voting, while REX directly determines actions from the UCB score, making it more systematic.
2. In ToT, an invalid trajectory leads to backtracking and pursuit of the next best trajectory. Conversely, in REX, upon encountering an invalid trajectory, feedback in the form of the UCB score is utilized. In the subsequent iteration, REX pursues the most promising action sequence.

Algorithm 1, line 3: $\forall (s, a) \in Q$. $Q$ is not a set of state-action pairs. This part should be $\forall (s, a) \in S$x $A$
In Algorithm 1, $Q$ includes all possible combinations of $(s, a)$. Equation (1) shows that to compute the UCB score, every $(s, a)$ pair must have a representation in $Q$. To avoid confusion for the reader, we opted to maintain the expression as "$\forall (s, a) \in Q$".

Algorithm 1, line 14: $\forall (s, a) \in H$. $H$ is a time step.
As already defined in the "Require:" section of Algorithm 1, $H$ represents sequence-of-intermediate-steps. so in line 14, we are conveying the idea that - for every intermediate step taken in the latest solution, we are updating $Q(s, a)$

The overall alogrithmic flow is not clear to me. I guess it is mainly because "AGENT.FUNCTION()" (FUNCTION = {SOLVE, VALIDATEACTION, CALCULATEUCB}) is not explained. In addition to the math problems mentioned earlier, the algorithmic flow in this paper is hard to follow.
We have added more details about these functions in Section D of the Appendix.

Questions:

[Q1] Could you tell me the similarities and differences between the authors' approach and Tree-of-Thoughts (Yao et al., 2023)? Is it possible to compare the performance of the two methods in the same benchmark? Because the authors use Blocksworld and GSM8K and Yao et al. (2023) use Game of 24, Creative Writing, and Mini Crosswords, I guess some of them are used for the comparison.

• We have addressed the similarities and differences between REX and ToT in the above section.
• (Currently running ToT on Blocksworld and GSM8K, We will share the results soon. )

[Q2] Although I can guess what are Agent.Solve and CALCULATEUCB to some extent, there is almost no information on what is Agent.ValidateAction. Could you elaborate more?

• Details available in Appendix - Section D

[Q3] I suspect that the high performance of REX in BlocksWorld is due to the data leak. Did the authors use the ordinary BlocksWorld environments with default settings?\

• We have confirmed that there's no data leakage in our setup. We created our few-shot examples (3 in total) to form the prompt and used these examples consistently across Reflexion, CoT, and all REX variations. It's impossible for REX to experience data leakage while others do not.