Skip to content

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

🕒 Published (v1): 2025-01-01 · Source: ICLR · Venue: ICLR 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ExACT combines test-time Monte Carlo Tree Search with a novel self-learning strategy to build "o1-like" VLM agents for long-horizon web navigation. Reflective MCTS (R-MCTS) extends classic MCTS with contrastive reflection and multi-agent debate, while Exploratory Learning distills full search-tree traversals back into GPT-4o via fine-tuning. The result is a fine-tuned agent that can autonomously explore, evaluate states, and backtrack without any external search algorithm at inference.

Problem

State-of-the-art VLMs (e.g., GPT-4o) achieve under 20% success on complex web tasks despite human performance of 89% on VisualWebArena. Existing search-augmented agents (Tree of Thought, SearchAgent) lack balanced exploration-exploitation and cannot learn from past interactions within a search session; more critically, no prior work transfers MCTS-acquired knowledge back into the model to reduce inference cost.

Method

R-MCTS extends MCTS with two additions:

  1. Contrastive Reflection: After each trajectory, the agent identifies the most erroneous actions by computing |V(o_{t+1}) − Q(o_t, a_t)| (analogous to TD error). For each erroneous action, a VLM simulates the expected next state, then generates a reflection contrasting expected vs. actual outcome. Reflections are embedded and stored in a vector DB. On future tasks, relevant reflections are retrieved via cosine similarity and prepended to the agent's context, updating both policy and value functions in-context.

  2. Multi-Agent Debate (MAD) value function: Two VLM instances generate opposing arguments (promising/unpromising) about the current state; a third VLM judge aggregates them into a scalar value estimate v_MA.

Exploratory Learning (EL) fine-tunes GPT-4o on full MCTS tree traversals rather than only the final best-action trajectory (Imitation Learning/IL). Tree traversals are replayed and flattened into a single sequence of (value_estimate, action) tuples including backtrack steps, teaching the model to intrinsically explore and self-evaluate at inference without search.

Key Contributions

  • R-MCTS: MCTS augmented with contrastive in-context reflection and multi-agent debate state evaluation, achieving new SOTA on VisualWebArena.
  • Exploratory Learning: fine-tuning strategy using MCTS tree traversals (not just optimal paths), enabling autonomous exploration/backtracking at inference without search.
  • Demonstration of compute scaling laws in both test-time search (more nodes → higher success) and training-time (EL-trained model scales with allowed actions at inference).
  • First work to fine-tune GPT-4o on MCTS-generated trajectories for agentic web tasks.

Results

  • R-MCTS vs. SearchAgent (prior SOTA) on VWA (GPT-4o backbone, 7.3–10.1× ReACT tokens):
  • Classifieds: 41.0% vs. 33.8% (+21% relative)
  • Reddit: 28.7% vs. 21.9% (+31% relative)
  • Shopping: 32.3% vs. 30.3% (+7% relative)
  • GitLab (WebArena): 23.5% vs. 13.8% (+70% relative)
  • Ablation (VWA overall): R-MCTS_MAD 33.7%; removing policy reflection drops to 30.2%; removing search entirely drops to 21.9%.
  • Exploratory Learning vs. R-MCTS_MAD on unseen Classifieds tasks: EL achieves 18.6% vs. IL's 12.4%; both recover >85% of R-MCTS_MAD's performance at 2.5–3.6× ReACT tokens (vs. 9.6× for R-MCTS).
  • Scaling: R-MCTS with 15 nodes achieves 47.5% on Classifieds vs. 28.6% for ReACT (+66% relative); EL-trained model shows favorable scaling with allowed action budget compared to IL.

Limitations

  • R-MCTS consumes ~10× more tokens than ReACT, making real-time deployment expensive.
  • Fine-tuning experiments restricted to text-only modality (GPT-4o vision fine-tuning unsupported at time of study), limiting applicability to the full multimodal setting.
  • Long MCTS tree traversals are costly to train on and may be difficult for the model to learn from in very long-horizon tasks.
  • Core error analysis reveals persistent failures from GPT-4o's fine-grained visual and web understanding (e.g., misidentifying grid-position items, incorrect global-minimum reasoning), which search and reflection do not fully address.

Relevance to Vision-Language Models

ExACT directly addresses the gap between VLM capability and agent-level performance in multimodal environments, demonstrating that structured test-time search combined with reflective self-improvement can substantially close that gap. The Exploratory Learning paradigm is significant for the VLM community because it shows that search-derived data—capturing exploration and failure recovery—is a higher-quality training signal than optimal-trajectory imitation, enabling internalization of search-like behaviors without inference-time overhead. The multi-agent debate value function connects to ongoing work on using VLMs as verifiers and critics. This positions ExACT in the emerging line of "o1-like" scaling for VLM agents, suggesting compute scaling laws apply to multimodal agentic tasks analogously to text-based reasoning.