ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning

In Table 2, you show the results for several search methods with a different amount of tokens? Would it be possible to have a comparison with a fixed computational budget?

We clarify that we did not intentionally increase the budget allocated to R-MCTS. All agents (ToT, Search Agent, MCTS, and R-MCTS) are run under the same search budget and hyperparameters such as width and breadth factor (please also see our general response GR-1). However, the greedy best-first nature of algorithms such as ToT BFS/DFS and Search Agent makes them often terminate early as they keep expanding states with high estimated value.

Under equal token usage, we show that:

• Best-of-N ReACT using MAD underperforms R-MCTS under all token usages as shown in the table in GR-2.
• R-MCTS achieves 35.0% on Classifieds with 4.0x ReACT token usage (from Figure 1 left), whereas Search Agent achieves only 33.8% with 4.2x ReACT token usage (from Table 2).

I wasn't able to understand what the values in the Training column from Table 3 means, can you clarify?

Sorry for the confusion. The “Training” column indicates whether the VLM used has undergone training mentioned in Section 3.2, and if so, how many trajectories are used. For example, the first two rows in Table 3 directly prompt OpenAI’s GPT-4o-mini and o1-mini, respectively, to complete tasks on VWA. In contrast, the last two rows prompt GPT-4o that has undergone BiT SFT and TrT SFT training with 65 and 35 trajectories, respectively.

We will clarify this in the caption in Table 3.

References

[1] Xie, Tianbao et al. “OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments.” ArXiv abs/2404.07972 (2024): n. pag.

[2] Rawles, Christopher et al. “Android in the Wild: A Large-Scale Dataset for Android Device Control.” ArXiv abs/2307.10088 (2023): n. Pag.

[3] Zhou, Shuyan et al. “WebArena: A Realistic Web Environment for Building Autonomous Agents.” ArXiv abs/2307.13854 (2023): n. pag.

Thank you for providing these questions and suggestions!

The presentation of the paper makes it hard to follow. For example, in the second paragraph of Section 3.1 the authors say that the mult-agent-debate state estimation was introduced in Section 2.3 but in that section they say that the methodology will be described in the next section.

Sorry for the confusion. We believe there is a typo on L175, where it stated “multi-agent-debate (Section 2.3)” instead of “multi-agent-debate”. We overlooked this mistake as we have re-organized this paper several times trying to improve readability. We will fix this in our final manuscript.

We clarify that our work focuses on how to effectively scale test-time compute to improve VLM agents, and efficiently transfer knowledge acquired from search back to the model to enhance its reasoning and planning abilities. We achieve this by introducing a new search algorithm R-MCTS (Section 3.1), and new training methods such as Tree-Traversal SFT (Section 3.2). We then experimented on VisualWebArena, and presented our R-MCTS results in Section 4.1, training results in Section 4.2, and an additional scaling experiment in Section 4.3. Finally, we provided numerous analyses in Section 5, such as an ablation study (Section 5.2) and a qualitative analysis of R-MCTS (Section 5.3).

The methodology seems to be specifically tailored for the web navigation task, and it is potentially unlikely to generalize to different tasks.

VisualWebArena (and WebArena) are challenging yet realistic benchmarks to evaluate autonomous multimodal agents' performance on executing tasks on a computer. Practically, R-MCTS agent only requires a visual or textual representation of the environment state (e.g., a screenshot) and outputs actions such as clicking, typing, scrolling, etc. All methods do not have access to any unrealistic web resources, such as the backend web implementation. This makes it easy to transfer between many tasks and domains. To demonstrate this, we additionally present results from evaluating on the GitLab domain from [3]:

We believe this is a generic and extensible setup and can be extended to other benchmarks such as Operating System tasks [1] and Android tasks [2].

We are sorry if we misunderstood your original question. If the above does not resolve your concern, could you please elaborate more why it is potentially hard to generalize to different tasks?

Why is the methodology only evaluated on the web? Is it because it requires access to the model of the environment to run the MCTS?

We evaluated VisualWebArena as it offers a suite of diverse, realistic, and reproducible environments including shopping (Shopping), social forums (Reddit), and content management (CMS). Practically, our agent only requires access to a visual or textual representation of the environment state (e.g., a screenshot), and is independent of the backend web implementation. We will clarify this in our section 2.3.

Can you please better explain how the simulation step was carried out in the algorithm? In vanilla MCTS, it is carried out with random rollout. Is it different in the proposed methodology?

Sorry for the confusion. Our rollout policy is based on the current agent, and simulation is based on executing the action in an actual browser. We will clarify this in our Appendix A.1.

Thank you again for these questions and feedback! Please let us know at your earliest convenience if you have any further questions or concerns, or would like to us conduct any additional experiments.

Thank you for the clarifications. I now understand the methodology better and I increase the score to 6.

Thank you for providing these questions and comments!

Why is it valid to self-generate data from an imperfect LLM, self-reflect with an imperfect LLM, and fine-tune an imperfect LLM from data generated by itself? Is this based on some sound principle?

Thank you for the question. Self-improvement methods using model generated data are highly common [1,2,3,4,5]. This is because 1) evaluating a solution/trajectory is typically easier than generating it; and 2) training an LLM/VLM with data of higher performance (albeit noisy) than itself is alike RLHF [6,7] which uses data generated by the model itself judged by an imperfect reward model. Hence, many work in self-improvement explores methods to obtain high-quality data using LLM/VLMs, despite their imperfections.

We will add this in our background section.

Given that no LLMs are perfect, so that the data generated and the evaluations conducted by LLMs are likely not fully reliable, although the algorithm may improve the performance.

Self-improvement methods [1,2,3,4,5] using data generated by LLMs have shown improved performance in areas such as math, coding, creative writing, and more. Similar to these prior work, we trained GPT-4o in agentic tasks using higher-performance data (i.e., from R-MCTS) than the model itself (i.e., ReACT), and showed that it can match over 85% of R-MCTS’s performance while reducing token usage by upto 4x (see Section 4.2).

What are the drawbacks and limitations of a learning system trained with data not fully reliable?

As data collected from self-improvement methods contains noises, the data collection and training loop will typically plateau after a few iterations. However, since our method uses on-policy data generated by the model itself, we believe it is also unlikely for the model to “unlearn” skills that it already possesses and significantly worsen performance.

We will add this consideration in our limitation section.

References:

[1] Jiaxin Huang, Shixiang Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2023. Large Language Models Can Self-Improve. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 1051–1068, Singapore. Association for Computational Linguistics.

[2] Gulcehre, Caglar et al. “Reinforced Self-Training (ReST) for Language Modeling.” ArXiv abs/2308.08998 (2023): n. pag.

[3] Aksitov, Renat et al. “ReST meets ReAct: Self-Improvement for Multi-Step Reasoning LLM Agent.” ArXiv abs/2312.10003 (2023): n. Pag.

[4] Yu, Xiao et al. “Teaching Language Models to Self-Improve through Interactive Demonstrations.” North American Chapter of the Association for Computational Linguistics (2023).

[5] Hu, Chi et al. “Teaching Language Models to Self-Improve by Learning from Language Feedback.” Annual Meeting of the Association for Computational Linguistics (2024).

[6] Ouyang, Long et al. “Training language models to follow instructions with human feedback.” ArXiv abs/2203.02155 (2022): n. pag.

[7] Sun, Zhiqing et al. “SALMON: Self-Alignment with Instructable Reward Models.” International Conference on Learning Representations (2023).

Thank you again for these questions and feedback! Please let us know at your earliest convenience if you have any further questions or concerns, or would like to us conduct any additional experiments.

Thank you for your reply.

Having many reference does not make it convincing... Self-improvement based on a fixed, imperfect LLM is not a valid approach.

Sorry if we misunderstood your statement, but are you claiming that all these prior work in model self-improvement [1,2,3,4,5] as well as their respective prior/follow up work are not valid?

We note that [1,2,3,4,5] are only very few examples we cited from the area of self-improvement research, which studies how to use a LLM/VLM to improve its own generation without additional human resources/signals. For more prior work in this area, we refer to papers that cites or follows up [1], [8] or [9], which we believe are one of the first papers that present convincing results in LLM self-improvement.

The fundamental issue is: Where is the reliable information? LLMs are not perfect, so that they can not guarantee reliable information

On a high level, we note that this loop of "generating improved data with an LLM" and "training the LLM with these data" is also common in alignment research. For example, RLHF [6] and its numerous follow up work trains an LLM using its own generation judged by a learned reward model, which is often also an LLM.

More References

[8] Madaan, Aman et al. “Self-Refine: Iterative Refinement with Self-Feedback.” ArXiv abs/2303.17651 (2023): n. pag.

[9] Bai, Yuntao, et al. "Constitutional ai: Harmlessness from ai feedback." arXiv preprint arXiv:2212.08073 (2022).

Thanks for acknowledging our responses on providing the CI. We hope we have at least addressed your concern on trustiness of our method!

I am surprised with the following comment: being accepted by a top AI conference and the # citations are so important, and the disdain with error bars, compared to top venue publication / citation.

Thank you for referencing our previous responses. To provide additional context, consider the following statement we made:

As to your question “without error bars or confidence intervals, why trust papers like ReAct”, we refrain from commenting on it. It is worth noting, however, that ReAct has been accepted by ICLR 2024 and cited for 1700+ times, and the absence of error bars in such papers (including GPT-4/Claude/LLama report) does not preclude their significant impact.

We respectfully disagree with your perception of our stance. We trust in the discretion of ICLR 2024 and the broader research community, as well as in the validity of the results presented in the ReAct paper. More importantly, we have already acknowledged and agreed with your emphasis on the importance of including error bars and CI. We completely concur that their inclusion strengthens the reliability of experiment results. This is why we provided error bars and CI in our work to address this very point.

We are unsure how you derived the impression that we "disdain error bars" from any of our prior responses. If there is a specific statement or tone that led to this misunderstanding, we would like to make corrections.

the problem is treating an imperfect LLM as an oracle.

Regarding your main concern of “reliable signal” and the raised problem “treating an imperfect LLM as an oracle": we never stated or conveyed in our paper that we treat the value function (an imperfect LLM) as an oracle one. We appreciate it if you can provide line numbers where we have made such claims and we will be happy to make corrections.

Additionally, [14] from OpenAI has shown critiques from a language model, though imperfect, is helpful to improve a base language model. Furthermore, [15] from Anthropic has shown that training a harmless AI assistant through self-improvement leveraging AI feedback is feasible. Similar from other works we have cited, these are only a few examples where feedback from imperfect LLM has shown to be useful to improve the base model. Our approach aligns with this broader body of work of model self-improvement, emphasizing that while imperfections exist, useful signals can still emerge.

More broadly, even the entire training pipeline of modern LLMs does not consistently guarantee a “reliable signal.” The pre-training corpus often contains imperfections, and the accuracy of instruction-following is not assured to be 100%. Similarly, preference data collected from annotators may have inherent biases or inconsistencies. Ongoing research efforts are focused on improving data quality across various stages, including enhancing the reliability and diversity of pre-training and post-training datasets.

Additional References:

[14] Saunders, William, et al. "Self-critiquing models for assisting human evaluators." arXiv preprint arXiv:2206.05802 (2022).

[15] Bai, Yuntao, et al. "Constitutional ai: Harmlessness from ai feedback." arXiv preprint arXiv:2212.08073 (2022).

In AlphaZero / MuZero, MCTS is part of policy iteration, with many iterations. AlphaZero and MuZero are for very specific problems, namely games with perfect rules / models. LLMs are for very general problems... LLMs + MCTS papers are mimicking AlphaZero / MuZero, but they are very different.

We note that our R-MCTS (Section 3.1) followed by our self-learning (Section 3.2) forms one policy iteration. We agree that works in AI agents is different from works in games with perfect rules, but we believe this does not imply LLMs+MCTS is infeasible for AI agents. In fact, our work (and the recent work you cited) shows that MCTS can be applied to LLMs/VLMs to significantly improve their performance (see our Table 1). Augmenting LLMs with MCTS (and our R-MCTS) within an agentic setting is nontrivial, as there are no perfect evaluators/rewards and the environment (i.e., real websites) is highly complex. We believe it is one of our core contributions and novelty to scale GPT-4o agent’s performance using our R-MCTS algorithm, and then to train and improve GPT-4o’s performance using data obtained during the search process.

We clarify that we did not claim to achieve near-human/super-human performance with our method: we are trying to leverage the generator-discriminator gap to improve our policy model (i.e., GPT-4o) as mentioned in our first response in this discussion. To achieve superhuman performance alike AlphaGo-Zero, we agree and believe iteratively optimizing in an perfect environment with perfect rules/reward is necessary.

The fact that LLMs people choose success rate as the metric may reflect the limitation of LLMs... Usually AI agents look for optimal solutions, not feasible ones. There are previous works, even many of them, does not justify its validity.

We agree that LLMs have limitations. As mentioned in our previous response, we followed the official benchmark implementation to use success rate, and compare against other works with the same metric. We suggest that future agent benchmark papers to explore other alternatives.

However, we believe the work you cited “AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training” utilizes final answer accuracy as the metric for GSM8k, which we believe is essentially the same as success rate, since neither ensures “optimality of solutions”.

Thank you for providing these detailed comments and acknowledging the clarity and quality of our paper’s presentation!

Missing relevant multi-step exploration baselines including Reflexion [1] and Intelligent Go-Explore [2]

Thank you for the suggestion! We note that Search Agent [1] already outperforms Reflexion (see Table 2 in [1]), and our proposed R-MCTS outperforms Search Agent (see our Table 2). Intelligent Go-Explore (IGE) is based on the Go-Explore algorithm [3], and offers a different heuristic function which prioritizes expanding states that are the most “interesting”, instead of states with the highest value (used in ToT and Search Agent) or highest UCT (used in MCTS and R-MCTS). We believe experimenting with different heuristics is a perpendicular direction to our work, which focuses on scaling test-time compute (Section 3.1) and transferring knowledge acquired from search back to the model (Section 3.2).

We will add [1] and [2] in our related work section. We leave the exploration of using different heuristic functions to future work.

The baselines in the main evaluation are not fairly evaluated with equal compute, e.g. does R-MCTS beat ReAct’s 7-shot performance in Table 2?

We clarify that we did not intentionally increase the budget allocated to R-MCTS. All agents (ToT, Search Agent, MCTS, and R-MCTS) are run under the same search budget and hyperparameters such as width and breadth factor (please also see our general response GR-1). However, the greedy best-first nature of algorithms such as ToT BFS/DFS and Search Agent makes them often terminate early as they keep expanding states with high estimated value.

Under equal token usage, we show that:

• Best-of-N ReACT using MAD underperforms R-MCTS under all token usages as shown in the table in GR-2.
• R-MCTS achieves 35.0% on Classifieds with 4.0x ReACT token usage (from Figure 1 left), whereas Search Agent achieves only 33.8% with 4.2x ReACT token usage (from Table 2).

Equally for the self-learning results, would fine-tuning on the best-of-n ReAct trajectories deliver similar improvements in base performance?

Thank you for the question! We believe you are comparing to the “Best-in-Tree” method, which trains the agent using the best action found during R-MCTS. Since Best-of-7 ReACT underperforms R-MCTS (see table in GR-2), we believe this would result in inferior performance in training.

Evaluation is limited to the VisualWebArena (VWA) benchmark, focusing solely on web navigation tasks. Other VLM domains could include video games, etc.

Thank you for the comment. Many recent work in generalist agents focuses on web benchmarks [1,4,5,6,7] as it offers highly diverse and reproducible environments such as shopping, social forums, collaborative software development, and content management. In addition to the VWA environments we evaluated in this work, we also evaluated GitLab tasks from WebArena, to emphasize on the generality of these browser-based tasks. We present the results below.

Clarify what kind of autonomous agents on L11, and MCTS should be attributed to Coulom et al. 2006

Thank you for the suggestion! We will clarify on L11 that autonomous agents in this work refers to VLM systems capable of executing computer tasks. We will also cite [8] when mentioning MCTS in this paper.

Why not also fine-tune GPT-4o instead of the in-context contrastive reflection approach?

Sorry if we misunderstood this question. We note that VWA does not provide ground-truth, optimal trajectories for training. We finetuned GPT-4o in Section 4.2 using 1) Best-In-Tree SFT which trains GPT-4o on the actions returned by a search algorithm (e.g., R-MCTS), and Tree-Traversal SFT which trains GPT-4o on all tree traversals that happened during search. Table 3 shows that both training methods recovered over 85% of R-MCTS performance while reducing token usage by up to 4x; and that Tree-Traversal SFT achieves a significantly higher success rate on unseen tasks.

Does the proposed algorithm beat the baselines with equal compute?

Empirically, R-MCTS with the same token budget as Search Agent already out-performs Search Agent. Figure 1 left shows that R-MCTS achieves 35.0% on classifieds with 4.0x ReACT token usage, whereas Search Agent achieves only 33.8% with 4.2x ReACT token usage (from Table 2). Additionally, we also followed your suggestions and compared R-MCTS with Best-of-N ReACT using MAD in the table in GR-2. We find that Best-of-N is much less efficient at scaling test-time compute in agentic tasks compared to R-MCTS with equal compute.

What is the impact of the size of the reflection database on value accuracy?

Thank you for the question. We did not set an upper limit of the reflection database size, but simply controlled the maximum number of reflections to be generated per episode (i.e., 3 per task). In our preliminary experiments, we find varying this number from 1-3 did not significantly impact performance. In general, we believe the size of the database would most strongly influence the performance of the retrieval model, which is a perpendicular research direction. We leave this to future work.

References:

[1] Koh, Jing Yu et al. “Tree Search for Language Model Agents.” ArXiv abs/2407.01476 (2024): n. Pag.

[2] Lu, Cong et al. “Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Models.” ArXiv abs/2405.15143 (2024): n. pag.

[3] Ecoffet, Adrien, et al. "Go-explore: a new approach for hard-exploration problems." arXiv preprint arXiv:1901.10995 (2019).

[4] Wang, Xingyao et al. “OpenHands: An Open Platform for AI Software Developers as Generalist Agents.” (2024).

[5] Zhang, Yao et al. “WebPilot: A Versatile and Autonomous Multi-Agent System for Web Task Execution with Strategic Exploration.” ArXiv abs/2408.15978 (2024): n. Pag.

[6] Xie, Tianbao et al. “OpenAgents: An Open Platform for Language Agents in the Wild.” ArXiv abs/2310.10634 (2023): n. Pag.

[7] Abuelsaad, Tamer et al. “Agent-E: From Autonomous Web Navigation to Foundational Design Principles in Agentic Systems.” ArXiv abs/2407.13032 (2024): n. Pag.

[8] Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. 5th International Conference on Computer and Games, May 2006, Turin, Italy. ffinria-00116992f

Thank you again for these questions and feedback! Please let us know at your earliest convenience if you have any further questions or concerns, or would like to us conduct any additional experiments.

Thank you for reading through our responses and raising the score! We will incorporate a detailed discussion clarifying our experimental setup and the distinctions between search algorithms in the final manuscript. For completeness, we also address the additional question below.

Please also match compute for the new domain as well for a fair comparison.

Since it is difficult to precisely control different search algorithms token usage (as they can produce trees of different shapes, see our GR-1 for more details), we followed your other suggestions and matched our R-MCTS_{MAD} with Best-of-N ReACT. We present the updated table below (changes shown in italic). Similar to our conclusion in GR-2, we find Best-of-N underperforms R-MCTS.

Thank you for providing these detailed feedbacks and acknowledging our “interesting study of search methods”!

One of the most important limitations of the work: the use of agent-environment interactions to generate and expand new nodes in the search tree… It should be very clear for each of the methods in the experimental section whether the method uses the simulator and if so, to what extent.

We clarify that we followed prior work [1] where all search methods (including ToT BFS, ToT DFS, Search Agent, MCTS, and R-MCTS) have full access to a web browser instance but no access to the ground-truth evaluator/reward function. We believe this is a practical setup since it does not require any human intervention/related resources, other than accessing a web browser.

We are sorry for the confusion, and will clarify this setup more in our Section 4.

[Figure 1 right] discusses actions allowed and “unseen” success rate … Do you want to convey the fact that SFT on search trajectories (i.e., Tree-Traversal SFT) allows the model to learn the shortest path?

Sorry for the confusion. We did not intend to convey that Tree-Traversal SFT (TrT SFT) trains the model to learn the shortest path. TrT SFT trains the agent to learn to explore and backtrack, a feature of the MCTS-based algorithms. Our result in Figure 1 right shows that agents after TrT SFT improves performance when more action steps are allocated, similar to scaling token usages with R-MCTS in Figure 1 left. This indicates that TrT SFT is not teaching the agent the shortest path (otherwise performance would change with an increased action budget), but rather how to conduct test-time search. Figure 4 provides a concrete example of TrT SFT trained GPT-4o exploring, evaluating, and backtracking without augmenting with search algorithms.

Concerns about the improvement step… Once again, this seems to be essential to your method, but there is no reason why this improvement step cannot be applied to the other search methods.

Thank you for pointing this out! We did not state that our training methods (e.g., Tree-Traversal SFT) are specific to our R-MCTS algorithm. In fact, our methods can be applied to any search algorithm that iteratively constructs a tree. In this work, we chose R-MCTS as an example (see L240) simply because it has the best performance, which is essential for an effective self-learning setup (Section 3.2).

We will add this discussion in our Section 3.2.

As it stands, the message is mostly centered around R-MCTS_{MAD} improving SoTA on VWA, but focus should be given to agents that can utilize the simulator. Obvious candidates for these agents include algorithms like BFS, DFS, and MCTS.

We are sorry if we misunderstood this question. We clarify that in our experiments (Section 4.1) all search methods (ToT BFS, ToT DFS, Search Agent, MCTS, and R-MCTS) have full access to a browser instance to perform simulation. No methods have access to ground-truth reward function or any human-related signals. In addition, we also use the same hyperparameters (e.g., breadth and width factor, see L306-310) different search algorithms to ensure a fair comparison.

Please see our GR-1 and GR-2 for more details.

Additionally, empirical results should be much more explicit on the number of simulations that were used in each case. Even for results on SFT where the number of simulations is perhaps irrelevant at test time, it should be clear how many simulations were necessary to build the datasets used for SFT.

We are sorry if we misunderstood this question. We reiterate that all search methods only have access to a web browser and have no access to the ground-truth reward function or any human-related signals. The number of simulations (e.g., nodes) is proportional to the tokens reported in our experiment. The SFT training data has 10.34 nodes per task, and they directly come from the R-MCTS search trees from Table 2. In general, we believe it is difficult to estimate a priori the minimum number of simulation/nodes to build an effective SFT dataset. We leave this for future work.

I wonder if the authors considered Best-on-N (i.e. generate many candidate trajectories without any search) as a baseline… To my point on scaling results such as those presented in Figure 1a, it is important to acknowledge that, as we increase the number of available tokens, there are things simpler than MCTS

Thank you for pointing this out! Please refer to our GR-2, where we showed that Best-of-N ReACT is much less efficient at scaling test time compute than search methods such as R-MCTS. We will add this result in our final manuscript.

If the number of tokens for ReAct is not something that can be controlled, then the plot in Figure 1 (a) needs another baseline

Yes, controlling token usage of different search algorithms is difficult. We implemented your suggestion above, and compared Best-of-N to R-MCTS across different token costs. Since ground-truth evaluator cannot be accessed during search time, Best-of-N becomes an inefficient version of search algorithms such as R-MCTS, as it rollouts the trajectory regardless of the quality of the states. Please refer to our Table in GR-2 for this result.

We will follow your suggestion and update Figure 1 (a) with this Best-of-N ReACT results.

The result [in Figure 1 left] is stating that the more an agent has access to a simulator to learn about possible trajectories, the better the performance - but I imagine the authors want a stronger message.

The first part of the work focuses on exploring how to scale test-time compute to improve VLM agents performance (Figure 1 left). Naive methods to scale up compute (e.g., Best-of-N ReACT) cannot efficiently improve performance compared to search algorithms such as R-MCTS, which we show in the table in GR-2. Similarly, in Table 2 in this paper we also show that other search algorithms from prior work (ToT BFS, ToT DFS, and Search Agent) also underperforms R-MCTS.

Why can’t we increase the size of the search tree for ToT, Search-Agents, MCTS, to match the token consumption of R-MCTS?

We clarify that all search methods (ToT BFS, ToT DFS, Search Agent, MCTS, and RMCTS) are ran under the same search budget, and the token variations are caused by the agent themselves terminate quickly with incorrect states, as they focus solely on rolling out states perceived to have high value (see L445-448). Please refer to GR-1 for more details.

Empirically, R-MCTS with the same token budget as Search Agent already out-performs Search Agent. Figure 1 left shows that R-MCTS achieves 35.0% on classifieds with 4.0x ReACT token usage, whereas Search Agent achieves only 33.8% with 4.2x ReACT token usage (from Table 2). Additionally, naively scaling up compute with Best-of-N ReACT also underperforms R-MCTS under the same token consumption, which we show in GR-2.

References:

[1] Koh, Jing Yu et al. “Tree Search for Language Model Agents.” ArXiv abs/2407.01476 (2024): n. Pag.

Thank you again for these questions and feedback! Please let us know at your earliest convenience if you have any further questions or concerns, or would like to us conduct any additional experiments.

[1] Koh, Jing Yu et al. “Tree Search for Language Model Agents.” ArXiv abs/2407.01476 (2024): n. Pag.

[2] Zhou, Andy et al. “Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models.” ArXiv abs/2310.04406 (2023): n. Pag.

[3] Zhang, Yao et al. “WebPilot: A Versatile and Autonomous Multi-Agent System for Web Task Execution with Strategic Exploration.” ArXiv abs/2408.15978 (2024): n. pag.

[4] Gulcehre, Caglar et al. “Reinforced Self-Training (ReST) for Language Modeling.” ArXiv abs/2308.08998 (2023): n. pag.

[5] Jiaxin Huang, Shixiang Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2023. Large Language Models Can Self-Improve. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 1051–1068, Singapore. Association for Computational Linguistics.

[6] Aksitov, Renat et al. “ReST meets ReAct: Self-Improvement for Multi-Step Reasoning LLM Agent.” ArXiv abs/2312.10003 (2023): n. Pag.

[7] Sun, Zhiqing et al. “SALMON: Self-Alignment with Instructable Reward Models.” International Conference on Learning Representations (2023).

[8] Hu, Chi et al. “Teaching Language Models to Self-Improve by Learning from Language Feedback.” Annual Meeting of the Association for Computational Linguistics (2024).