Research map / Multi-agent systems and games / LLM agents
ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes R-MCTS, a test-time MCTS agent with contrastive reflection and multi-agent debate value estimation, plus Exploratory Learning (TreeSFT) to fine-tune GPT-4o on full search-tree traversals so it can explore and backtrack without external search.
Problem
Vision-language model web agents underperform humans on long-horizon web navigation, and search-augmented agents are expensive at inference and their search gains are not transferred back into the model.
Approach
Extends MCTS with in-context contrastive reflections retrieved from a vector database and a multi-agent-debate value function, then distills full MCTS tree traversals (exploration, evaluation, backtracking) into GPT-4o via fine-tuning (TreeSFT) rather than only the best actions (ChainSFT).
Key results
- R-MCTS with multi-agent debate reaches 41.0% success on VWA Classifieds versus 37.6% for MCTS and 33.8% for Search Agent, with 6-30% relative gains across environments.
- On OSWorld with screenshot+accessibility tree, R-MCTS achieves 19.39% overall success versus 11.21% for ReAct with GPT-4o.
- TreeSFT-trained GPT-4o reaches 27.8% overall success on Classifieds with no search, versus 22.2% for ReAct; R-MCTS with debate reaches 32.1% with 9.6x tokens and TreeSFT reaches 3.6x tokens.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add R-MCTS search with a single-agent value function instead of Search Agent | GPT-4o web agent · Classifieds (VWA) | Success: 33.8% -> 40.2% | Helped |
| Add multi-agent debate to R-MCTS with a single-agent value function | R-MCTS · Classifieds (VWA) | Success: 40.2% -> 41.0% | Helped |
| Add multi-agent debate to R-MCTS with a single-agent value function | R-MCTS · Reddit (VWA) | Success: 25.2% -> 28.7% | Helped |
| Add multi-agent debate to R-MCTS with a single-agent value function | R-MCTS · Shopping (VWA) | Success: 31.9% -> 32.3% | Helped |
| Add multi-agent debate to R-MCTS with a single-agent value function | R-MCTS · GitLab (WA) | Success: 20.9% -> 23.5% | Helped |
| Fine-tune GPT-4o on search-selected actions | GPT-4o · Classifieds (VWA, text-only; Unseen) | Success: 12.4% -> 18.6% | Helped |
| Add value reflection (ablation) | R-MCTS debate · VWA (all tasks; Overall) | Success: 32.9% -> 33.7% | Helped |
| Add policy reflection (ablation) | R-MCTS debate · VWA (all tasks; Overall) | Success: 30.2% -> 33.7% | Helped |
| Add search (ablation) | R-MCTS debate · VWA (all tasks; Overall) | Success: 21.9% -> 33.7% | Helped |
| Add multi-agent debate for state evaluation | R-MCTS · VWA easy tasks | Success: 50.7% -> 49.3% | Hurt |
| Add multi-agent debate for state evaluation | R-MCTS · VWA hard tasks | Success: 19.9% -> 23.6% | Helped |
| Update task instructions to require navigating to the item page and returning its URL | GPT-4o ReAct · Classifieds (VWA; 75 sampled tasks) | Success: 14.67% -> 27.27% | Helped |
Surprising findings
- Fine-tuning on best actions only (ChainSFT) reaches 31.2% overall, slightly above TreeSFT's 27.8% overall, though TreeSFT generalizes better to unseen tasks (18.6% vs 12.4%).
- Multi-agent debate slightly hurts easy tasks due to over-thinking, while helping medium and hard tasks.
Limitations
- Search-augmented agents consume roughly 10x more tokens than ReAct, limiting practicality.
- Long tree traversals are costly to train on and may be hard for models to learn from.
- Fine-tuning experiments limited to 234 Classifieds tasks and text-only input because GPT-4o vision fine-tuning was unsupported.
Experimental setup
Datasets: VisualWebArena Classifieds tasks
Benchmarks: VisualWebArena OSWorld WebArena GitLab
Metrics: success rate token consumption relative to ReAct
Baselines: ReAct Tree of Thought BFS Tree of Thought DFS Search Agent MCTS AgentSymbiotic AgentStore Learn-by-Interact ICAL GPT-4o-mini o1-mini
Builds on: Monte Carlo Tree Search ReAct Tree of Thoughts Search Agent Set-of-Mark
Closest papers by meaning
- MARS: Modular Agent with Reflective Search for Automated AI Research (ICML 2026 · similarity 0.88)
- Agentick: A Unified Benchmark for General Sequential Decision-Making Agents (NeurIPS 2026 · similarity 0.88)
- Monte Carlo Planning with Large Language Model for Text-Based Game Agents (ICLR 2025 · similarity 0.87)
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.87)
- SEEA-R1: Tree-Structured Reinforcement Fine-Tuning for Self-Evolving Embodied Agents (NeurIPS 2025 · similarity 0.87)
- FML-bench: A Controlled Study of AI Research Agent Strategies from the Perspective of Search Dynamics (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.