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

Authors: Xiao Yu, Baolin Peng, Vineeth Vajipey, Hao Cheng, Michel Galley, Jianfeng Gao, Zhou Yu
Primary area: foundation or frontier models, including LLMs
Keywords: AI agent, tree search, self-improvement

Abstract:
Autonomous agents have demonstrated significant potential in automating complex multistep decision-making tasks. However, even state-of-the-art vision-language models (VLMs), such as GPT-4o, still fall short of human-level performance, particularly in intricate web environments and long-horizon planning tasks. To address these limitations, we introduce Reflective Monte Carlo Tree Search (R-MCTS), a novel test-time algorithm designed to enhance the ability of AI agents, e.g., powered by GPT-4o, to explore decision space on the fly.
R-MCTS extends traditional MCTS by 1) incorporating contrastive reflection, allowing agents to learn from past interactions and dynamically improve their search efficiency; and 2) using multi-agent debate to provide reliable state evaluation. Moreover, we improve the agent's performance by fine-tuning GPT-4o through self-learning, using R-MCTS generated tree traversals without any human-provided labels. On the challenging VisualWebArena benchmark, our GPT-4o-based R-MCTS agent achieves a 6% to 30% relative improvement across various tasks compared to the previous state-of-the-art. Additionally, we show that the knowledge gained from test-time search can be effectively transferred back to GPT-4o via fine-tuning. The fine-tuned GPT-4o matches 97\% of R-MCTS's performance while reducing compute usage by a factor of four at test time. Furthermore, qualitative results reveal that the fine-tuned GPT-4o model demonstrates the ability to explore the environment, evaluate a state, and backtrack to viable ones when it detects that the current state cannot lead to success. Moreover, our work demonstrates the compute scaling properties in both training - data collection with R-MCTS - and testing time. These results suggest a promising research direction to enhance VLMs' reasoning and planning capabilities for agentic applications via test-time search and self-learning.

Decision: accept (poster)
Reviewer scores: 6, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1729785912601

thread_type:
official_review

<thread_object>
creator: reviewer_ssy4

<content>
summary:
The paper presents a variation of MCTS that exploit the reasoning capabilities of VLMs and that can also be fine tuned.

strengths:
1. Incorporating VLMs reasoning capabilities into MCTS is a novel idea with great potential.
2. The proposed methodology has been extensively evaluated on a challenging benchmark and significantly outperforms the baselines.
3. Improvements of the benchmark with optimizations that will useful for future works.

weaknesses:
1. 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.
2. The methodology seems to be specifically tailored for the web navigation task, and it is potentially unlikely to generalize to different tasks. A clearer explanation and a better contextualization would improve the clarity of the paper.

questions:
1. Why is the methodology only evaluated in web? Is it because it requires access to the model of the environment to run the MCTS?
2. Can you please better explain how the simulation step carried out in the algorithm? In vanilla MCTS, it is carried out with random rollout. Is it different in the proposed methodology?
2. In Table 2, you show the results for several search methodology with a different amount of tokens? Would it be possible to have a comparison with a fixed computational budget? I think it would be a more fair comparison with the baselines.
3. I wasn't able to understand what the values in Training column from Table 3 means, can you clarify?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729996822129

thread_type:
official_review

<thread_object>
creator: reviewer_xtze

<content>
summary:
The authors propose to improve autonomous AI agents with reflective tree search and self-learning. The authors introduce Reflective Monte Carlo Tree Search (R-MCTS), a test-time algorithm to explore decision space on the fly, with contrastive reflection and multi-agent debate. The authors fine-tune GPT-4o through self-learning, using tree traversals generated by R-MCTS, without any human-provided labels. The authors conduct experiments with VisualWebArena benchmark.

strengths:
Reflective Monte Carlo Tree Search (R-MCTS) for test-time exploration of decision space
fine-tuning GPT-4o through self-learning

weaknesses:
A fundamental issue is: 
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.
It is desirable or a must to collect reliable training data and feedback for a healthy learning system.

questions:
Why it is 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?
Although the algorithm may improve the performance, what is the drawbacks and limitations of a learning system trained with data not fully reliable?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730702709639

thread_type:
official_review

<thread_object>
creator: reviewer_ddld

<content>
summary:
The paper presents a novel algorithm improving the capabilities of VLM agents in long-horizon exploration tasks via a combination of MCTS, and value function estimation by reflection and multi-agent debate. The authors show strong results in the VisualWebArena benchmark as well as showing these behaviors can be distilled back into GPT-4o to improve its base performance.

strengths:
- Well-written and clearly presented paper
- Strong motivation in improving VLM agents in long-horizon tasks
- Novel contrastive reflection proposal that enables a VLM to in-context learn from errors in value estimation
- Thorough ablations over two different value function constructions and individual components of the algorithm 
- Informative analysis of the types of errors the agent makes in Section 5.3.

weaknesses:
- Missing relevant multi-step exploration baselines including Reflexion [1] and Intelligent Go-Explore [2]
- 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? What about ToT’s 2-shot performance? This makes it impossible to evaluate the paper’s contribution. Equally for the self-learning results, would fine-tuning on the best-of-n ReAct trajectories deliver similar improvements in base performance? I would raise my score if the authors could show positive results for this.
- Evaluation is limited to the VisualWebArena benchmark, focusing solely on web navigation tasks. Other VLM domains could include video games, etc.

Minor: 
- Line 11: clarify what kind of autonomous agents, the authors clearly mean foundation model based rather than traditional RL
- MCTS should be attributed to Coulom et al. 2006

[1] Reflexion: Language Agents with Verbal Reinforcement Learning Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, Shunyu Yao.

[2] Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Models Cong Lu, Shengran Hu, Jeff Clune.

questions:
- Why not also fine-tune GPT-4o instead of the in-context contrastive reflection approach?
- Does the proposed algorithm beat the baselines with equal compute? 
- What is the impact of the size of the reflection database on value accuracy?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731315087554

thread_type:
official_review

<thread_object>
creator: reviewer_gidu

<content>
summary:
This paper provides an overview of MCTS based methods for improved test-time (i.e. inference-time) algorithms for Visual Language Models and tested on the VisualWebArena benchmark for complex web environments. This benchmark is particularly important as it poses a substantial challenge, as VLMs have been shown to often fall short of human-level performance in such tasks, hence any progress in this space is important. The most performant variation of the search algorithm studied in this paper is R-MCTS, which leverages the well known benefits of the traditional Monte Carlo Tree Search (MCTS) algorithm, popular method for improving decision-making in long-horizon tasks with a large action space. Although MCTS has been used in other contacts with a learned world model, this paper is using the WebArena simulator to expand tree nodes. None of the results use the VLM or some other learned model for transitions. VLM is only used for policy and value functions.

R-MCTS extends traditional MCTS by incorporating contrastive reflection and utilizing multi-agent debate. Contrastive reflection allows agents to learn from past interactions and dynamically improve their search efficiency. Perhaps the most impactful design choice is the Memorization of reflection. Reflection embeddings are stored in a vector database and, during inference, relevant reflections are retrieved from the database and appended to the agent's current context, enabling it to learn from past mistakes and improve future task executions. On the other hand, Multi-Agent Debate prompts multiple VLMs to generate individual value estimates, which are then aggregated to produce a final estimate. This approach aims to provide a more holistic view of the current state and encourage stronger reasoning through collaborative/adversarial incentives.

Experiments performed on the VisualWebArena (VWA) benchmark, which evaluates multimodal agents' performance across various web navigation tasks, demonstrated the effectiveness of R-MCTS, with significant performance boosts over alternative search methods.
Moreover, the authors demonstrate that the search trajectories can be effectively transferred back to base models via fine-tuning, resulting in improved performance without requiring search augmentation at test time.

strengths:
Building agents that are capable of solving complex web navigation using methodologies that are as general as possible will prove to be among the most impactful contributions in the field of AI. The authors are doing a good job to emphasize this and they provide an important contribution in this area, properly aligned with many findings that emphasize the strong VLM capabilities in inference time reasoning and planning.Additionally, the authors demonstrated how easily integrated concepts drawn from human dialogue can be used to improve generic methods. They did this by pinpointing two intuitive modifications to MCTS: contrastive reflection and debating.The boost in performance with the proposed methods is also quite significant, raising the bar on the type of capabilities that can be achieved with the use of LLMs, while also demonstrating the strong potential of scaling up these methods (e.g. longer search horizons, more inference time computations). Lastly, I will point out that the paper is overall well contextualized with respect to the current literature on agentic LLM frameworks, search-based methods for LLMs/VLMs and other inference time algorithms. I would also like to applaud the contributions to SFT-based experiments and emphasizing the importance of generating quality synthetic data, given the cost and logistical challenges associated with human data collection

weaknesses:
I will perhaps start with what I believe is 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. Unless there is something that I am missing, the search algorithm is based on Alpha-Zero and not Mu-Zero, which essentially means that the results rely heavily on access to a simulator at test time. This should be stated explicitly and the experimental work should be adjusted to account for this rather important detail. In particular, neither ReAct,  nor TreeOfThought (albeit it could be adapted to use the simulator) are presented as a way to enhance agent performance by using an exact simulator. 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 (e.g. how many transitions). Note that I am a strong proponent of using a simulator when available and I also think this should be clarified as a distinct paradigm from a method similar to MuZero, which is fully devoted to a simulator, and hence much more generalizable. At the same time, having access to ground truth transitions can indeed make a huge difference in terms of access to important information, hence empirical results should be presented in a way that makes this use much more transparent. Note that many results in Reinforcement Learning, where agents similarly have access to a simulator, will always report results as functions of “episodes” or “epochs”, both of which are essentially reporting the amount of simulated interactions that an agent has access to. As such, comparing an agent such as ReAct that (AFAICT) doesn’t have access to these simulated transitions, or even another search agent for which readers have no clear understanding of how it works, can be quite misleading.

Figure 1 (left) should be explained much more clearly and that should be done in the captions of the Figure, given that the figure is placed in on the first page. It is great that the reader is given the impact of the work as early as possible. I personally struggled to understand the result both when I first saw it on the first page and after I reached the experimental section and the Figure was explained. First, if the number of tokens for ReAct is not something that can be controlled, then the plot in Figure 1 (a) needs another baseline, e.g. MCTS, Search-Agent. As it stands, the result 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. Similarly, for the Figure on the right side, the plot now discusses actions allowed and “unseen” success rate, which once again seems quite selective and there is no clear message takeaway message. Do you want to convey the fact that SFT on search trajectories allows the model to learn the shortest path?

I would also like to raise concerns about the improvement step, which is essentially doubling down on the advantage of using a simulator by storing embeddings of reflections. This is akin to Replay buffers in Reinforcement Learning. Once again, this seems to be essential to your method, but there is no reason why this improvement step cannot be applied for the other search methods.

Given my take on the main results (i.e. Figure 1) and my comments on the simulator, I would encourage the authors to be more explicit about the significance of the work. 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, and the additional components the authors propose should then be clearly justified and ablated, especially when they can be applied independent of the search method. Note that the same I argument can be made for the multi-agent value function. 

For experiments, perhaps testing more than two underlying models is necessary to better understand the phenomenon of search for VWA, albeit it is understandable if this incurs costs that are too high for their corresponding institution/s. 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.

I noticed that there is a very clear emphasis on the number of tokens used by either of the methods. I wonder if the authors considered Best-on-N (i.e. generate many candidate trajectories without any search) as a baseline, and if so, why was it not included in the studies? 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 that could be done and search should only be justified when the performance gap is significant. Additionally, why can’t we increase the size of the search tree for ToT, Search-Agents, MCTS, to match the token consumption of R-MCTS? 

Lastly, as far as novelty is concerned, I stand by my take that the paper is a very interesting study of search methods when a simulator for VWA is provided to the agent and the R-MCTS algorithm is a simple twist to the very popular MCTS. The modifications themselves, whether contrastive reflections, multi-agent debates, or self learning, are, as the authors already made clear, existing concepts with straightforward incorporation with MCTS on VLMs.

questions:
Since my stance on the paper is strongly grounded on my understanding that the trees for the search algorithms are built with full access to the VMA simulators, I would love if the authors are more descriptive on how experiments were conducted. For context, my assumption is based on the description of the MCTS algorithm in the Appendix, where $\mathcal{T}$ is used to expand new nodes.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731873067948

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank all reviewers for their helpful feedback and suggestions!

---

> GR-1: Concerns about experimental setup: the use of agent-environment interactions/more tokens/etc by RMCTS agents

We clarify that in our Table 2, all search methods (ToT BFS, ToT DFS, Search Agent, MCTS, and RMCTS) are ran under the same search budget, have full access to a browser instance to perform simulation, and uses a self-evaluated value function. **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. We believe this corresponds to the traditional model self-improvement setup where the agent has **no access** to any human-related signals but only data created by itself.

The variation in token usage arises from agents terminating the search either when they **believe they have achieved the task** (with an estimated value of 1.0) or when the **search budget is exhausted**, whichever comes first. In practice, we find best-first methods such as ToT and Search Agent often terminate quickly with incorrect states, as they focus solely on rolling out states *perceived* to have high value (see L445-448).

We will add these clarifications in our experimental setup section (4) and our analysis section (5.3).


> GR-2: Have the authors best-on-N (e.g., with ReACT) as a much simpler method to scale token consumption for performance?

Best-of-N with ReACT rolls out N trajectories, and returns the best trajectory scored by a reward model/evaluator. However, since no methods can access the ground-truth reward (see response above), best-of-N ReACT with an estimated reward function (e.g., MAD) becomes an inefficient version of the tree search used in this work. This is because best-of-N rolls out the trajectory *regardless of state quality*, whereas MCTS (and R-MCTS) prioritizes visiting states using an exploration-exploitation trade-off (the UCT bound, see L121-124).

Empirically, we show this by running best-of-N ReACT with various N on Classifieds, and compare it against R-MCTS:


| Method            | Value | Token | Success |
|--------------------|-------|-------|---------|
| ReACT             | -     | 1x    | 28.6%   |
| Best-of-4 ReACT   | MAD   | 4x    | 32.5%   |
| R-MCTS            | MAD   | 4x    | **35.0%** |
| Best-of-7 ReACT   | MAD   | 7x    | 35.0%   |
| R-MCTS            | MAD   | 7x    | **37.6%** |
| Best-of-10 ReACT  | MAD   | 10x   | 37.6%   |
| R-MCTS            | MAD   | 10x   | **43.6%** |
| Best-of-12 ReACT  | MAD   | 12x   | 38.9%   |
| R-MCTS            | MAD   | 12x   | **47.5%** |

Results above show that R-MCTS is much more efficient at scaling test-time compute at agentic tasks, especially when more tokens are allocated.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733203993842

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
**We thank all reviewers for their valuable comments and their engagement throughout the discussion period.** We are glad that reviewers found the paper to be well presented and contextualized (Gidu, ddLD, XTzE), the approach to be novel (ddLD, SSY4) and impactful (Gidu), and experiments to be thorough (ddLD) and extensively evaluated (SSY4).

Throughout the discussion period, we believe that our responses addressed the concerns brought up in each review, and we have updated our manuscript to reflect these changes (shown in red). Please let us know if there is anything else we can further clarify before the end of the discussion phase.

---

We summarize the main concerns and how we addressed them below.

\
> Search budget and token usage variation of different search algorithms

We clarified that all search methods (ToT BFS, ToT DFS, Search Agent, MCTS, and RMCTS) are run under the same search budget and hyperparameters, have full access to a browser instance to perform simulation, and a self-evaluated value function. We emphasize that precisely controlling the token usage apriori is infeasible for all search algorithms, as it is hard to estimate beforehand which action the algorithm will generate/explore and whether the agents will terminate early once they believe they have achieved the task. To this end, we followed reviewer Gidu and ddLD’s suggestions and additionally ran Best-of-N ReACT, and showed that under equal token R-MCTS substantially outperforms Best-of-N ReACT (response GR-2).

We believe we have addressed the concern throughout the discussion, and we have updated Figure 1 and Section 4-4.3 in our manuscript correspondingly.

\
> Access to a simulator or the ground truth evaluator code

We clarified that all search methods 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 agree with reviewer Gidu that implementing a MuZero-like algorithm (using an additional VLM to model website transitions) is highly exciting. In this work, we followed many recent agent-related work [1,2,3] and allowed search methods to use an actual browser. We believe that developing simulator-based search methods like AlphaGo Zero is a *crucial first step* toward building MuZero-like approaches. We emphasize that it is also our research goal to build more general and performant agents like Mu-Zero. We will study this closely in our future work.

We believe we have addressed the concern, and we have added these clarifications in Section 4 of our manuscript. We also added a discussion on the idea of developing MuZero-like approaches in our limitations section.

\
> Whether our work required access to the model of the environment/can generalize to other domains

We clarified that all agents only access a visual or textual representation of the environment state (e.g., a screenshot) as input, and *is independent of the backend web implementation*. All methods do **not** have access to any unrealistic web resources. This makes it easy to transfer between many tasks and domains, which we demonstrated by additionally experimenting on the GitLab domain (see response to reviewer ddLD and SSY4).

We believe we have addressed the concern, and we have added clarifications in Section 2.3. We have also updated our Table 1 with these GitLab results.

\
> Model self-improvement using self-evaluations/reward from an VLM is not a valid approach, although the algorithm may improve the performance.

We agree that, ideally, search and training should be conducted with perfect evaluator/reward models. However, this is hard to obtain in many domains, and many current research [4,5,6,7,8] relies on imperfect evaluation/reward models to further advance state-of-the-art. Reviewer Gidu shared a similar stance: “Using unreliable models to guide a search process is not a novelty nor is it problematic. In fact, it is arguably the only way to solve large complex problems.”

We understand reviewer XTzE’s concern towards the whole community: “I'm concerned with how the LLM community is approaching AI agents”. In general, we agree and believe that developing a reliable and near-perfect reward model for AI agents (as well as for many other domains such as preference learning) is challenging yet of strong interest to the research community. We leave this for future work.

\
> Other individual concerns/questions

We believe we have also addressed other individual questions, such as whether our Tree-Traversal SFT is designed specifically for R-MCTS, and adding standard deviations to our Table 1. We have updated our manuscript to reflect these questions and discussions.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes an MCTS approach that can update a base foundation model on long horizon tasks. This is clearly highly relevant right now and the authors did a good job of improving the evaluations during the rebuttal phase. I think the work will be interesting for many communities given the current emphasis on agents, and recommend acceptance.