PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xiao Yu, Baolin Peng, Vineeth Vajipey, Hao Cheng, Michel Galley, Jianfeng Gao, Zhou Yu

arXiv:2410.02052v5cs.CLcs.CV

TL;DR

Long-horizon web agents struggle to explore large decision spaces, and existing search approaches have difficulty balancing exploration with exploitation and transferring search experience back into models. ExACT combines reflective Monte Carlo Tree Search with Exploratory Learning on search traversals. On VisualWebArena, R-MCTS improves on the previous state of the art, while Exploratory Learning transfers search behavior to GPT-4o with lower inference cost.

  • Problem

    VLM agents struggle to explore large action spaces and balance exploration with exploitation in long-horizon tasks, while existing search methods do not learn from prior interactions or transfer search knowledge into the model.

    Source: §1 · p. 2

  • Method

    ExACT combines R-MCTS, which uses contrastive reflection and multi-agent debate, with Exploratory Learning that trains GPT-4o on search-tree traversals.

    Source: §1 · p. 2, §3.1 · p. 4, §3.2 · p. 6

  • Results

    On VisualWebArena, GPT-4o-based R-MCTS improves relative performance by 6% to 30% over the previous state of the art, while Exploratory Learning recovers 87% of search performance at 2.7x lower inference cost.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Fine-tuned GPT-4o begins to display test-time compute scaling properties similar to search algorithms.

    Source: §7 · p. 11

    MCTS-based agents consume nearly 10x more tokens than REACT, creating a performance-versus-cost/time trade-off that may limit real-world practicality.

    Source: §8 · p. 11

Abstract

from arXiv · show

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 tasks. To address these limitations, we present ExACT, an approach to combine test-time search and self-learning to build o1-like models for agentic applications. We first introduce Reflective Monte Carlo Tree Search (R-MCTS), a novel test time algorithm designed to enhance AI agents' ability 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 for reliable state evaluation. Next, we introduce Exploratory Learning, a novel learning strategy to teach agents to search at inference time without relying on any external search algorithms. 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 and experience gained from test-time search can be effectively transferred back to GPT-4o via fine-tuning. After Exploratory Learning, GPT-4o 1) 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, and 2) matches 87% of R-MCTS's performance while using significantly less compute. Notably, 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' capabilities for agentic applications via test-time search and self-learning.

1 INTRODUCTION

Long-horizon web agents struggle to explore large decision spaces, while existing search methods balance exploration and exploitation poorly and do not transfer search experience back into the model. ExACT combines reflective search with training on search experience to address these challenges.

1 INTRODUCTION

  • Existing search methods struggle to balance exploration and exploitation, learn from past interactions, and transfer search knowledge into the model.The introduction also notes that GPT-4o-based agents achieve success rates below 20%, compared with human performance of 89%.Source: §1 · p. 2
  • ExACT combines test-time search with self-learning through R-MCTS and Exploratory Learning.R-MCTS adds contrastive reflection over past experiences and multi-agent debate for state evaluation; Exploratory Learning trains on search-tree traversals to explore, evaluate, and backtrack.Source: §1 · p. 2
  • On VisualWebArena, GPT-4o-based R-MCTS improves relative performance by 6% to 30% over the previous state of the art across environments.GPT-4o trained with Exploratory Learning also explores, evaluates, and backtracks without search augmentation, recovering 87% of search performance while reducing inference cost by 2.7x.Source: §1 · p. 2

2 BACKGROUND

The background frames web navigation as decision-making under partial observability, introduces Monte Carlo Tree Search, and describes common VLM agent setups.

2.1 NAVIGATING THE WEB

  • Web navigation is modeled as a partially observable decision process, with states covering the webpage and database and actions expressed in natural language.The agent receives observations after actions, and the interaction ends at a step limit or STOP action before a terminal reward is returned.Source: §2.1 · pp. 2–3, §2.3 · p. 3

2.2 MONTE CARLO TREE SEARCH

  • MCTS repeatedly selects and simulates actions, updates tree value estimates, and returns a best action after its search budget is exhausted.Selection uses Upper Confidence Tree Bound to balance exploration and exploitation.Source: §2.2 · p. 3

2.3 SETUP

  • VisualWebArena defines an action space for web navigation.Table 1 presents that action space.Source: Table 1 · p. 3
  • VLM web agents can use a policy to generate actions from the task and interaction history, or add a value function to guide simulation-based search.The section distinguishes a single-agent value estimate from a multi-agent value function.Source: §2.3 · pp. 3–4

3 METHOD

ExACT addresses agents’ difficulty adapting to diverse web environments with reflective MCTS and Exploratory Learning. R-MCTS improves search during inference, while Exploratory Learning trains GPT-4o on search traversals.

3.1 REFLECTIVE MCTS

  • The method targets web environments whose diverse layouts and functionality make it difficult for search-augmented agents to adapt quickly to unseen environments.The paper notes that websites differ substantially and almost every webpage is unique.Source: §3.1 · p. 4
  • R-MCTS extends MCTS with contrastive reflection over past executions and multi-agent-debate state estimates to improve decision-making during inference.The agent iteratively builds a tree through selection, expansion, simulation, and backpropagation, while updating policy and value functions in context.Source: §3.1 · p. 4
  • Contrastive reflection attributes errors, contrasts expected and actual outcomes, and stores lessons from long-horizon trajectories.The method is described as three steps: error attribution, contrastive learning, and memorization of reflection.Source: §3.1 · pp. 4–5
  • Reflection selects errors by the gap between predicted future success V and tree-simulated success Q, focusing policy reflection on actions and value reflection on misestimated states.The method identifies erroneous actions or value estimates using the difference between V and Q.Source: §3.1 · p. 4
  • For new tasks, the agent retrieves relevant reflections using cosine similarity between task-state embeddings and appends them to its context.The stored reflections are embedded using the task and state.Source: §3.1 · p. 5
  • Multi-agent debate prompts two VLMs to argue opposing value assessments, then uses another VLM to aggregate them into a final judgment.The approach is intended to provide more reliable state estimates and mitigate mistakes caused by oversights.Source: §3.1 · p. 5

3.2 EXPLORATORY LEARNING

  • Exploratory Learning trains GPT-4o on search-tree traversals to explore, evaluate states, and backtrack, unlike Imitation Learning on final search-selected actions.Figure 3 contrasts the two training approaches.Source: §3.2 · p. 5, Figure 3 · p. 5
  • Exploratory Learning replays each search tree, pairs explored or backtracked actions with estimated values, and concatenates the records into a training trajectory.The resulting trajectory is used to train GPT-4o.Source: §3.2 · p. 6

4 EXPERIMENTS

The experiments evaluate R-MCTS on VisualWebArena and OSWorld, then test whether GPT-4o can learn exploratory behavior from R-MCTS experience. Results report benchmark gains, learning without search augmentation, and performance scaling with additional compute.

4 EXPERIMENTS

  • VisualWebArena evaluation covers 910 tasks across Classifieds, Reddit, and Shopping, while OSWorld adds 369 open-ended computer tasks and the study also evaluates GitHub tasks from WebArena.VisualWebArena tasks require visual understanding, and 25.2% include images; the benchmark setup uses Set-of-Mark-augmented screenshots.Source: §4 · p. 6
  • R-MCTS is compared with direct prompting and search baselines, including REACT, Tree of Thought, Search Agent, and MCTS.For VisualWebArena, search methods use breadth and depth limits of five and stop execution after at most five actions; OSWorld execution is limited to 15 steps.Source: §4 · pp. 6–7

4.1 R-MCTS RESULTS

  • R-MCTS sets a VisualWebArena state-of-the-art, improving 6% to 30% over the previous best method across environments.With a single-agent value function it improves on MCTS by 2.2 points on average; multi-agent debate adds 1.6 points on average.Source: §4.1 · p. 7, Table 2 · p. 7
  • On OSWorld, R-MCTS shows competitive performance against state-of-the-art methods using either screenshot-plus-accessibility-tree or accessibility-tree-only inputs.The tables cover 369 open-ended computer tasks, while the results passage notes R-MCTS uses a single model with a search algorithm.Source: §4 · p. 6, Table 3 · p. 7, §4.1 · p. 8

4.2 LEARNING RESULTS

  • Learning data comes from R-MCTSMAD trajectories: 65 are sampled by estimated final success, then trajectories longer than 20 actions are removed, leaving 35 for fine-tuning.The trajectories are formatted as multi-turn chats for the OpenAI fine-tuning API.Source: §4.2 · p. 8
  • On 234 Classifieds tasks, GPT-4o trained with Imitation Learning or Exploratory Learning outperforms REACT without search and achieves over 85% of R-MCTSMAD performance with up to 4x fewer tokens.Exploratory Learning also achieves a significantly higher success rate on unseen tasks; fine-tuning is evaluated text-only because GPT-4o fine-tuning did not support images at the time.Source: §4.2 · p. 8, Table 5 · p. 8
  • Exploratory Learning enables GPT-4o to explore, evaluate states, and backtrack on unseen tasks without a search algorithm.In the Classifieds example, the agent abandons an unreliable search result and uses category filters instead.Source: §4.2 · p. 9, Figure 4 · p. 9

4.3 COMPUTE SCALING RESULTS

  • With 15 nodes per tree, R-MCTSMAD improves success rate by 66% relative to REACT on the 234 Classifieds tasks.Performance rises with additional test-time compute; without search, both Imitation Learning and Exploratory Learning also improve as more actions per task are allowed, with Exploratory Learning showing a more favorable scaling trend.Source: §4.3 · p. 9

5 ANALYSIS

The analysis finds that R-MCTS improves success across task difficulties, with multi-agent debate helping on harder tasks but sometimes overthinking easier ones. Ablations highlight policy reflection and search, while trajectory inspection identifies reflection and UCT as sources of action-quality gains and backbone understanding as a major error source.

5.1 SUCCESS RATE BREAKDOWN

  • Multi-agent debate further improves medium and hard tasks but can slightly reduce easier-task performance through overthinking.The authors suggest debate encourages more critical state evaluation in long-horizon tasks, while sometimes avoiding nonexistent issues in easier tasks.Source: §5.1 · p. 10
  • R-MCTS improved performance by an average of 2.5% absolute compared with the prior best across all task difficulties, benefiting long-horizon planning and robustness on easier tasks.Source: §5.1 · p. 9

5.2 ABLATION STUDIES

  • Ablations across 910 VWA tasks find policy-improvement reflections more crucial than value-function reflections, and search essential for competitive performance.Table 7 reports overall performance after removing each component.Source: §5.2 · p. 10, Table 7 · p. 10

5.3 QUALITATIVE ANALYSIS

  • Among the 80 sampled tasks, R-MCTSMAD outperformed SEARCH AGENT in 12.5%, primarily due to policy improvement via the reflection-improvement process (60%) and exploration–exploitation balance using UCT instead of best-first (30%).Source: §5.3 · p. 10
  • Most R-MCTSMAD errors were attributed to the backbone VLM’s difficulty understanding webpage screenshots and product images.The analysis groups errors into answer formatting, agent-environment interaction, model image understanding, and model web understanding.Source: §5.3 · p. 10, Figure 5 · p. 10

6 RELATED WORK

Prior work applies language and vision-language models to agent tasks, and adds reflection, search, or supervised training. The paper positions MCTS in realistic web environments and training from MCTS trajectories as its distinctions.

Language-Guided Agents

  • Language-guided agents use LLMs as policies, components of designed frameworks, heuristic- or prompt-augmented systems, and tool-using systems; visual tasks also use VLMs.The authors note that these methods typically struggle with planning and error recovery in long-horizon tasks.Source: §6 · p. 11

Augmenting Agent with Search/Reflection

  • Prior work explores iterative self-refinement and BFS/DFS, best-first, or MCTS search, often in text-based settings without substantial complex-environment interaction.The paper contrasts that scope with its focus on long-horizon agentic tasks in realistic web environments, multi-agent-debate state evaluation, and contrastive reflection.Source: §6 · p. 11

Training Agents

  • The authors position training GPT-4o on MCTS-produced trajectories, including full tree traversal to teach exploration, evaluation, and backtracking, as novel.They contrast this with prior supervised training using human- or machine-generated trajectories from direct prompting.Source: §6 · p. 11

7 CONCLUSION

The conclusion presents R-MCTS as a search-augmented agent and describes transferring search knowledge to GPT-4o through imitation and exploratory learning. On VisualWebArena, R-MCTS achieves state-of-the-art performance, while fine-tuned GPT-4o displays test-time compute scaling properties similar to search algorithms.

7 CONCLUSION

  • On VisualWebArena, R-MCTS achieves a new state of the art, and fine-tuned GPT-4o displays test-time compute scaling properties similar to search algorithms.The transfer methods train on best actions returned by tree search (Imitation Learning) or the entire MCTS tree traversal (Exploratory Learning).Source: §7 · p. 11

8 LIMITATIONS

The limitations section identifies high test-time cost for MCTS agents and long tree traversals that make training costly and potentially difficult for models to learn from.

High cost of scaling test-time compute

  • MCTS-based agents consume nearly 10x more tokens than REACT, creating a performance-versus-cost/time trade-off that may limit real-world practicality.The authors note that search agents can also curate VLM training data without human labels.Source: §8 · pp. 11–12

Long trajectories from tree traversal

  • Long-horizon tasks require substantial R-MCTS simulation and produce long tree traversals that can be costly to train on and difficult for models to learn from.The authors leave exploration of this issue to future work, while suggesting iterative self-learning and improved policy/value functions as possible mitigations.Source: §8 · p. 12

A ADDITIONAL IMPLEMENTATION DETAILS

The appendix specifies the shared MCTS search loop, R-MCTS reflection and retrieval updates, and browser changes made to support backtracking.

A.1 MONTE CARLO TREE SEARCH

  • MCTS repeatedly selects and expands actions, evaluates trajectories with a VLM value function, back-propagates Q and visit counts, then executes the most-visited action.Selection uses a PUCT variant to balance exploration and exploitation; its exploration-rate hyperparameter is cp = 1.0 in these experiments.Source: §A.1 · p. 16

A.2 R-MCTS PSEUDO CODE

  • R-MCTS alternates tree-search inference with reflection on past actions, then retrieves relevant reflections to update its policy and value function in context.It reflects on the top three erroneous policy actions and one value-function error per trajectory; retrieval uses cosine similarity and a 0.25 threshold.Source: §A.2 · pp. 17–18, Figure 6 · p. 18

B.1 WEB BROWSER

  • The modified browser parallelizes webpage processing, caches Set-of-Mark outputs, and remaps element IDs after backtracking using metadata word overlap.The appendix reports a quantitative study of these browser changes in Table 9.Source: §B.1 · p. 19

B.2 VWA EVALUATION

The evaluation addresses a mismatch between some task wording and VisualWebArena’s URL-based success check by clarifying the requested final action.

B.2 VWA EVALUATION

  • Some agents return the correct item description from search results, but VisualWebArena checks whether the final URL is the desired item’s page.The authors attribute this error to task intents that do not explicitly require navigating to the item page.Source: §B.2 · p. 19
  • Appending an instruction to navigate to the item page and return its URL improved all methods and VLMs, according to the authors.The change affected 93 Classifieds instances, none in Reddit, and 34 Shopping instances; the study uses the updated intents unless otherwise specified.Source: §B.2 · p. 19

C.1 ERROR ANNOTATION SCHEME

The appendix describes the error categories used to inspect R-MCTS failures, the webpage representation, and prompts used for reflection, improvement, and debate.

C.1 ERROR ANNOTATION SCHEME

  • R-MCTS errors are grouped into four primary categories and eight subtypes, with Figure 7 reporting an analysis of 80 randomly sampled Classifieds tasks.The categories cover answer formatting, environmental issues, model text understanding, and model image understanding.Source: §C.1 · pp. 19, 21, Figure 7 · p. 21

D.1 SET-OF-MARK AUGMENTATION

  • Set-of-Mark augmentation places bounding boxes and unique identifiers on interactive webpage elements.Figure 8 provides an example of the augmented webpage input.Source: §D.1 · p. 22, Figure 8 · p. 22

D.2 PROMPTS FOR R-MCTS AGENT

  • The appendix lists prompts for expected-state generation, contrastive reflection, action generation from retrieved reflections, and multi-agent debate for value estimation.Tables 11–15 present these prompt groups, including opposing-argument generation and final judgment from those arguments.Source: §D.2 · p. 22, Table 11 · p. 23, Table 12 · p. 24
Loading 2410.02052v5…