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
Venue: ICLR 2025 Poster (2025)
Keywords: AI agent
tree search
self-improvement
Primary area: foundation or frontier models, including LLMs

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.

Published as a conference paper at ICLR 2025
EXAcT: TEACHING AI AGENTS TO EXPLORE WITH REFLECTIVE-MCTS AND EXPLORATORY LEARNING
Xiao Yu', Baolin Pengat, Vineeth Vajipey', Hao Cheng", Michel Galley?
Jianfeng G & Zhou Yu!- 'Columbia University, NY Microsoft Research, Redmond (xy2437, zy2461 (e6/66//coolooooooooo www.oombiaa......moem........all edu (baolinpeng, [rgao]@microse
ABSTRACT
Autonomous agents have demonstrated significant potential in automating com- plex multistep decision-making tasks. However, even state-of-the-art vision- language models (VLMs), such GPT-4o, still fall short of human-level per- formance, particularly in intricate web environments and long-horizon tasks. To address these limitations, we present EXACT, approach to combine test-time search and self-learning to build ol-like models for agentic applications. We first introduce Reflective Monte Carlo Tree Search (R-MCTS), a novel test-time al- gorithm designed to enhance AI agents' ability to explore decision space on the fly. R-MCTS extends traditional MCTS by 1) incorporating contrastive reflec- tion, allowing agents to learn from past interactions and dynamically improve their search efficiency; and 2) using multi-agent debate to provide reliable state evaluation. Next, we introduce Exploratory Learning, a novel learning strategy teach agents search inference time without relying on any external search algorithms. On the challenging VisualWebAren benchmark, our GPT-4o-based R-MCTS agent achieves 6% to 30% relative improvement across various tasks compared to the previous state-of-the-an Additionally, we show that the knowl- edge and experience gained from test-time search can be effectively transferred back to GPT-4o via fine-tuning. After Exploratory Learning, GPT-4o 1) demon- strates 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% 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 promis- ing research direction enhance VLMs' reasoning and planning capabilities for agentic applications via test-time search and self-learning
47.5
47
R-MCTSWAD
Exploratory Learning
Best-of-N ReACT
Imitation Leaming No SFT
Success Rate
10.0
37.6
Unseen Success
5.0
35.0
32.5
28
0.0
10
10
Tokens (x ReACT)
Number of Actions Allowed
Figure 1: Our work yields compute scaling of GPT-4o with R-MCTS (left) and fine-tuned GPT-4o (right), for both training and testing, respectively. Left is evaluated on all 234 tasks from Classifieds in AisualWebArena and right is evaluated on 169 unseen tasks from Classifieds.
'Equal Advisory Contribution; Project Lead
Code and data can be found wtthttss://// aak ma RXACT

---

Published as a conference paper at ICLR 2025
INTRODUCTION
Visual-Language Models (VLMs) have seen significant advancements, becoming increasingly pow- erful processing and generating multimodal content. High-capacity models such as GPT-4o (Ope-
nA 2024a), Gemini (Gemmnn 2024), Phi-3 (Abdin et al. 2024), and Opus (Anthropic, 2024) have demonstrated promising understanding and reasoning abilities, paving the way for building VLM-
based agents that can automate computer tasks such software engineering (Yang et al., 2024 Wang et al. 2024), web navigation (Zhou et al., 2024bj Koh et al. 2024a) and mobile device con- trol (Rawles al., 2023; 2024). As many computer tasks require agents to interact with complex environments for long-term objectives, one critical challenge is to reason over extended periods and dynamically explore a large decision space. Current models often struggle accessing wide range of potential actions in these environments, and balancing exploration and exploitation in long- horizon tasks. Even GPTT-4o-based agents significantly underperform humans, achieving success rates less than 20% compared to human performance of 89% (Koh et al. 2024a).
As demonstrated by OpenAl's ol (OpenAl 2024b) and [nell et al. (2024), increasing the number of thinking tokens as chain of thoughts at test time improves accuracy on tasks that require long- horizon planning and reasoning, such as math and coding. This naturally raises the question: Can we scale test-time computation to improve VLMs' decision-making capabilities in multistep planning and reasoning for agentic tasks? An intuitive strategy for agentic tasks, such as web navigation, is search. By exploring different actions and evaluating their consequences, models can gain a better understanding of the environment, reason about correct actions, and plan more effectively for long-term objectives. Recent work in this direction includes Tree of Thought (Yao et al., 2023a) and Search Agent (Koh et al. 2024b), which rely on best-first search in the form of BFS/DFS and A search, respectively. suffer from 1) a lack of balance between exploration and exploitation, which is crucial for handling complex tasks, and 2) an inability to learn from past interactions to improve future searches, which humans naturally do. More importantly, these works focus primarily on prompt-based methods and do not address how to transfer knowledge from search back into the model. This results in agents with high inference costs for complex tasks, as it requires the use of VLMs with search algorithms.
augment the VLM's Mecision-making process. However, these methods
In this work, we explore how effectively scale test-time compute improve VLM agents, and efficiently transfer knowledge and experience acquired from search back to the model to enhance its reasoning and planning abilities. We present ExAcT, an approach combine test-time search and self-learning to build oi-k models for agentic applications. First, we introduce our Reflec- tive Monte Carlo Tree Search (R-MCTS) agent. Our method extends the classic MCTS with two innovations: confrastive reflection to improve search quality in real time using high-quality reflec- tions obtained from past experiences, inspired by conceptual models of human learning (Marton) 2014); and multi-agent debate technique for reliable state evaluation, inspired by collaborative and iterative human evaluation approaches (yan der Lee et al., 2019). Second, we propose Exploratory Learning, method to teach agents to search at inference time without relying on any external search algorithms. In contrast to traditional Imitation Learning which trains the model with the optimal, final actions returned from the search process, Exploratory Learning teaches the models explore the environment, evaluate a state, and backtrack to viable ones using search tree traversals.
Experiments on the challenging WesualWebArena (Koh et al., (024a) show that our GPT-4o-based R- MCTS agent achieves a new state-of-the-art performance, with a 6% to 30% relative improvement across various environments compared to the previous state-of-the-art. Additionally, we find GPT- 4o trained with Exploratory Learning demonstrates the ability to 1) explore, evaluate, and backtrack without any search augmentation; and 2) recover 87% of the search performance while reducing the inference cost by 2.7x. This represents an important step towards improving VLM's 's planning and reasoning capabilities for agentic applications by leveraging test-time search and self-learning.
BACKGROUND
2.1 NAVIGATING THE WEB
Decision making in a complex environment is typically formulated as a Partially Observable Markov Decision Process (POMDP) of (S, A, T), which consists of sets of states, actions, observations, and a transition function. In the context of web navigation, a state s E S represents the entire environment's state including the current webpage and database states; action A is an
2

---

Published as a conference paper at ICLR 2025
tion the agent can express in natural language and execute in the environment (see Table observation is a textual or visual representation of the current webpage; and the transition function a(s,a) + (s',o') executes action in the environment and returns the next state and observation. For more details, we refer the reader to /hhou et al. (2024b); Koh et al. (2024a).
2.2 MONTE CARLO TREE SEARCH
In long-horizon tasks with large action space, Monte Carlo Tree Search (MCTS) (Silver et al. 2017 Swiechowski et al. 2022) is a popular method to improve decision making. MCTS explores mul- tiple actions, evaluates their consequences, and re- turns the best action for execution after conducting large number simulations. We briefly describe the MCTS algorithm here and refer to Appendix A.] for more details. Given a state to search from, MCTS it- eratively constructs a tree by: 1) selecting an action to explore/exploit using Upper Confidence Tree Bound (UCT) (Kocsis & Szepesvári 2006 Rosin 2011;: 2) expanding and evaluating the selected ac- tion by simulating the next state Tx,,
Action Type a
Description
click [elem] hover [elem]
Click on elem.
Hover over elem.
type [elem] [text]
Type text into elem.
press [key.comb]
Press a key combo.
new tab tab focus [index]
Open new tab.
Focus the i-th tab, Close current tab.
tab close goto [url]
Go to url.
back
Click back.
go forward scroll [up ddwn]
Click forward.
Scroll or down. End with an output.
stop [answer]
s, a) - (5',0')
and evaluating current progress; 3) backpropagating the evaluation to update the tree's s value estimates of
Table 1:
Action space for web navigation de- fined in Visual WebArraaa (Koh et al. (024a)
quality of the executed action. This search process repeated until the search budget is exhausted, and the most-visited (Silver et al. 2017 or the highest-value action (Koesis & Szepesvári 2006) is returned.
2.3 SETUP
We now present the setup commonly used by VLMs for agentic tasks, e.g., that of Visual (Koh et al. 2024a). web agent begins by receiving a task g in natural language (and images) and starting webpage op. Then, each time step t: 1) the agent generates on the last state St, which encodes information from past actions and observations; and 2) a, is executed, transiting agent. This agent-environment interaction continues until either the maximum number of steps T reached, the agent issues STOP action to terminate the episode. Finally, a terminal reward rr E {0, 1) is returned based on the final answer or the last environment state ST-
action a, A based
state [(st, 4z) - (S--1, 0t+1), and observation 0++1 is returned to the
In practice, visual agents are often implemented using a large vision-language model (VLM) such as GPT-4o (OpenAl 2024a). Common approaches include directly prompting the VLM as a policy function generate an action T(-) - a given task and previous actions and observations (Yao et al. 2023b; Koh et al. 2024a); to additionally construct value functions
V..) and conduct simulation-bant searches before returning an action (Yao al.] 2023a| Zhou et 2024a Koh
et al. 2024b). We detail these methods below.
VLM a Policy Function Given task g and an trajectory T {og, ap.
ai Oz policy π (g. + returns the next action a, execute. Popular methods such as ReACT (Yao) al. 2023b) use a VLM as policy by directly prompting it for an action, after optionally generating reasoning step. Then, the environment executes action o and returns a new observation 0,+1- This process repeats until a STOP action is issued or the maximum number of steps is reached.
VLM as Value Function To augment an agent's decision-making process, many recent works implement a value function V--) to guide the VLM to predict better actions. Given a trajectory т, value function estimates the expected success rate given the current state s;. However, since state 8; of the environment (e.g., including database information) may not always be accessible to the agent, value functions are often implemented using the current observed trajectory and the task description instead: (g. ) + [0, 1) In this work, we consider two value functions. A single-
agent value function (ao et al. 2023a Koh et al. 2024b) directly prompts a VLM with all inputs

---

Published as a conference paper at ICLR 2025
(task g, trajectory 7) to generate value estimate Usai
Usa VLM (g.T) E [0.
and a value function based on multi-agent debate, which we describe in the next section.
METHOD
We propose EXACT, approach to teach Al agents to explore via test-time search (Section 3.1) and self-learning (Section 3.2).
3.1 REFLECTIVE MCTS
Web tasks are highly diverse different websites have different layouts and functionallties (e.g., Amazon versus Reddit), and almost every webpage is unique. Although sarch-a agents have shown promising results in web navigation tasks, their performance is limited by the complex- ity of web environments and their inability to quickly adapt to unseen environments.
We propose Reflective Monte Carlo Tree Search (R-MCTS), an extension of classic MCTS that improves the agent's decision making process on the fly by incorporating reflection over its past task executions, and state estimations us- ing multi-agent-debate.
INFERENCE
STOP
reefect
We present a high- level overview of an R-MCTS agent in FFg- ure 2] and a pseudo-code description in Ap- pendix A.2] Similarly to classic MCTS, an R- MCTS agent during inference predicts ac- tion a, by iteratively building a search tree that explores the current decision space (i.e., looping over selection, expansion, simulation, and back- propagation steps). Unlike classic MCTS, R- MCTS also iteratively improves the search pro- cess by 1) using contrastive reflection identify- ing past mistakesssucceesses; and 2) updating the agent's 's policy and value functions (in-context) improve its future task executions during infer- ence. This improvement step helps R-MCTS to avoid repeating the same mistakes and explore more promising actions when faced with similar situations in the future. For clarity, we describe this improvement process in the context of policy reflection, since value reflection is highly simila
S
sefictio
Rafiection
Imporie
IMPROVEMENT
Lagend:
Stole
Action
VLM
Fiat Injjetory tree search
Figure 2: omit value function reflection for brevity.
Overview of an R-MCTS Agent. We
Contrastive Reflection Policy (or value) function consists of three steps: 1) error attribution; 2) constrastive learning: and 3) memorization of reflection. Given a (long-horizon) trajectory т. this process intuitively corresponds to first identifying the most "erroneous' action, then analyzing the error by comparing what the agent expects to achieve with what actually happens, and finally storing this knowledge by remembering the task and state where the error occurs. This process is inspired by human cognitive learning (Marton) 2014), where contrasting our mental model of the world with the reality is effective way obtain new knowledge.
Formally, given a task and trajectory т, we first identify n, most erroncous actions (and ny value estimates for value reflection) for reflection, based the difference between the VLM's predicted future success V and the search-tree's simulated future success Q:
error=((a.I))
(o++1) - Q(o,, de)l, errorv((.:7)) = (V 1,, a.-1)) 1)].
Note that this form of comparing value function and action-value function Q is similar Tem- poral Difference Error used in reinforcement learning (Sutton & Barto 2018). For each of the erroneous actions {ā..... an }, we then prompt the VLM identify reasoning mistakes and gain understanding of navigating in the specific environment. We achieve this by contrastive learning
2 Foor value reflection, we reflect on states for erroncous state estimations instead of actions. Then, we prompt the VLM to predict the expected future actions, and generate a reflection contrasting the agent's 's actual actions. For simplicity, we the accessibility representation of in text modality throughout this process.
4

---

Published as a conference paper at ICLR 2025
Imitation Learning
Exploratory Learning
lask
IAMOTO
lask
DAUTTS
12
dala=
data
Figure 3: Given a trajectory from R-MCTS, Imitation Learning removes intermediate search trees and directly trains GPT-4o learn from the final executed actions; Exploratory Learning flattens tree traversals into single trajectory and trains GPT-4o to explore, evaluate, and backtrack.
we first 1) prompt the VLM to predict the expected transition ō141 after executing â. and 2) prompt the VLM to generate a reflection by contrasting the current Or, at, the expected ōr+1 and real o++1:
ot, ō = VLM (g, (oo, ",, Ht),, reflect(ā.lg, 7) = VLM Oz, ãt {oe+1, oc+1) 1-)
Finally, to help the agent memorize this reflection at test-time, we embed the reflection using the current task and state (g. oz) and store it in vector database.
Then, given new task and a new observation (gnew ofew) to perform inference, we improve the policy (and value) function by 1) retrieving the most relevant reflections using cosine similarity of their embedding:" [ and 2) appending them into the agent's s current context. For clarity, also illustrate this reflection and improvement process in Figure 5 Appendix A.2)
Improvement
Multi-Agent Value Function In addition the ditecttioniimroveeeet with using multi-agent value function to provide more reliable state estimates. Intuitively, this method offers 1) more holistic view of the current state mitigate mistakes caused by oversights; and 2) stronger reasoning elicited by collaborative/adversaii incentives (Bowman et al.) 20222) )
loop, also experiment
Formally, multi-agent value function prompts multiple VLMs each generate value estimate vf, and then aggregate all estimates {o², v=,.... to produce a final estimate thai
VLM, (g. r) E [0, 1] and Usa aggregate T, fu', v2 o².....) [0, 1].
In this study, we implement the multi-agent value function using multi- multi-agent-debaee (MAD). Given task g and trajectory MAD prompts two VLMs to generate two opposing arguments for the current value estimate (i.e., why the current state is promising/not promising), and then aggregates the two arguments using another VLM obtain a final judgement:
aggregate(g. r, [u v2 ....)) VLM (g, t, [v ......).
For the prompts used by contrastive reflection, improvement, and MAD, please refer to Appendix E.2
3.2 EXPLORATORY LEARNING
Search-augmenter agents such as R-MCTS improve performance at the expense of increased test- time computation. Using GPT-4o powered R- -CCTS as an example, we explore how to teach agents to search and explore at inference time without relying on any external search algorithms. We propose Exploratory Learning (EL), a learning strategy to teach GPT-4o to explore, evaluate, and backtrackon using all tree traversals that happened during search. This is contrast to the traditional Imitation Learning (IL) approach, which directly fine-tunes GPT-4o on the actions returned by the search algorithm. We illustrate these two methods in Figure 3
*For simplicity, directly concatenate new, pew)) into single string and feed into embedding model (text-ada-003-smalll, OpenAl 2024c)).
5

---

Published as a conference paper at ICLR 2025
Given task g, a trajectory {ov, du..... 0. }. and all search trees Tree(oo), Tree(or) obtained during R-MCTS, Imitation Learning trains GPT-4o to learn an improved policy by directly fine- tuning the actions executed in (i.e., best actions selected by search). This method is simple, but relies on the model itself to learn the implicit reasoning process. Exploratory Learning improves GPT-40's 's decision making ability by using both and tree traversals Tree(oo): Tree(or). Specif- ically, given a tree Tree(o:), we 1) replay the tree search process to obtain observations o, actions explored or backtracked a, and the estimated values v; 2) combine value estimation and action into a single action a t (v, a), and 3) append them to form a single trajectory T/. We then repeat this for all trees, and obtain a single trajectory r' (Tó- .... 7/ } used to train GPT-4o.
EXPERIMENTS
We primarily experiment on VisualWebArena (VWA), a benchmark designed evaluate multimodal agents performance on across a wide range of web navigation tasks and environments. To further measure the generalizability of our method, we also evaluate on other popular benchmarks such as OSWorld and relevant domains from WebArena. We describe the experimental setup, baselines, and other relevant implementation details below.
Benchmarks
(Koh et al.) 2024a) is large-scale benchmark consisting of 910 tasks across three different web environments: Classifieds, Reddit, and Shopping. All tasks in VWA require visual understanding of webpage content solve effectively, and 25.2% of the tasks also include images as input (e.g., help me make a post selling this item + an image of a phone). We host all web environments locally and evaluate on all 910 tasks, unless otherwise specified. We follow (Koh et al. 2024a b) and use Set-of-Mark (Yang et al. 20236) augmented web screenshots as the agent's 's imput. An example is presented in AApendix E.1
Beyond VWA, we also consider OSWorld (Xie et al. 2024), an diverse benchmark consisting of 369 open-ended computer tasks that involves real web and desktop apps in open domains, OS file I/O, and workflows spanning multiple applications; and relevant domains (i.e., GitHub) from WehArena (Zhou et al. 2024b) to further enhance our evaluation.
Baselines We mainly compare R-MCTS against direct prompting methods as well search- augmented agents backed by various algorithms. For direct prompting methods, we consider REACT Yao et al. 2023b), which prompts a VIM generate the reasoning step before generating the action. For search, we consider Tree of Thought (TOT, Yao et al.] (202a)), which uses BFS or DFS to explore the decision space and returns the best action found according to V: SEARCH AGENT (Koh et al.] 2024bb), which is a best-first method inspired by A* search; and MCTS (iilver et al., 2017 Zhou al. 2024a
Yu et al. 2023), which uses MCTS to determine the best action to take.
For evaluations on OSWorld, please refer to palppeddix C for more details.
Policy and Value Implementation Search methods require policy that can generate up to b ac- tions for exploration, and value function that returns a value between 0 and 1. We follow Koh cet al. (2024b) to implement such a policy by 1) sampling up to 20 responses from the VLM with a temperature of 1.0 and top-p of 0.95, using nucleus sampling (Holtzman et al. 2020); 2) aggre- gating the counts of each unique action; and 3) returning the top-b actions with the highest counts. We implement the single-agent value function Vsa by 1) prompting the VLM with multiple-choice based prompt; 2) sampling 20 responses with temperature of 1.0 and top-p of 0.95; 3) converting the selected choices into a numeric value; and 4) returning the average value of all responses. We im- plement the multi-agent value function Vsaa by 1) prompting the VLM twice to generate reasons why the current state is promising/unpromiinng 2) prompt the VLM again to generate a final judgement with a multiple-choice-el based prompt; and 3) converting the selected choice into a numeric value. We use GPT-4o (2024-05-13) 13) (OpenAl (2024a) as the VLM for all methods as has been widely used in the development of of ofte--of-the-are the-art agents (Koh et al. 2024b Wang et al. 2024
Search Parameters On VisualWebArena, we follow Koh et al. 2024b to compare all search methods with breadth 6 and depth d limit of 5 per tree, and to stop task execution after a maximum
Thiis replay stops the first time when the search process reached the best action.

---

Published as a conference paper at ICLR 2025
of 5 actions. Since different algorithms behave differently during search, also set maximum search time of 5 minutes per state. For MUCTS-basee algorithms, we use UCT bound with c, = 1.0 for action selection, and use the most-visited child for selecting the best action (Silver al. 2017). On OSWorld, we follow other official results and stop task execution after a maximum 15 steps. Since this is significantly longer than the evaluation VWA, we max node limit of 60, and set b = 10 to be decaying exponentially per depth when running R-MCTS.
4.1
R-MCTS RESULTS
Classifieds (VWA)
Reddit (VWA)
Shopping (VWA)
GitLah (WA)
Search
Value
Tokens
Success
Tokens
Success
Tokens
Success
Tokens
Success
X (REACT)
1x
28.6%
1x
13.8%
1x
23.2%
1x
11.3%
TOT
SA
3.2x
30.7%
4.7x
19.5%
4.3x
29.2%
4.6x
14.1%
TOTDES
SA
3.1x
30.3%
4.2x
16.7%
4.0x
28.3%
4.3x
14.1%
SEARCH AGENT
SA
4.2x
33.8%
5.4x
21.9%
5.1x
30.3%
3.0x
13.8%
MCTS
3A
7.2x
37.6%
9.5x
23.8%
8.9x
29.4%
5.7x
19.9%
R-MCTS
SA
7.3x
40.2%
7.3x
25.2%
7.6x
31.9%
6.0x
20.9%
R-MCTS
MAD
7.4x
41.0%
9.7x
28.7%
10.1x
32.3%
8.8x
23.5%
Table 2: Comparing different agent's 's token consumption and performance on VisualWebArena (VWA). For more domain diversity, we also evaluate GitLab tasks from WebArena (WA). We show average token used per task using REACT as baseline.
We summarize the performance of R-MCTS and other search-augmented agents evaluated on Vi- sualWebArena (VWA) in Table 2] We observe that all search-based methods deliver significant improvements across the VWA environments, albeit with increased test-time compute measured by the number of tokens. Among these methods, MCTS consistently outperforms its counterparts. This is likely due to MCTS's ability to balance exploration and exploitation through UCT, whereas other methods primarily rely on V guide the search. Additionally, our R-MCTS agent sets new state- state-of-the th- performance benchmark across all VWA environments, with relative improve- ments ranging from 6% to 30% over the previous best-performing method, Search Agent. When using a single-agent value function, R-MCTS improves upon MCTS by an average of 2.2 points. Furthermore, with the integration of multi-agent debate, R-MCTS achieves an additional 1.6-point improvement on average. These findings highlight promising approach to scaling test-time com- pute in agentic applications by integrating search, reflection, and multi-agent debate strategies. The comprehensive leaderboard for WebArrWab can be found in Appendix Table 10]
We also extend our R-MCTS agent on OSWorld. Please refer to Appendix for more details.
4.2 LEARNING RESULTS
Next, we evaluate EXACT: teaching GPT-4o to explore and improve its performance using knowl- edge and experience gained from R-MCTS. Since GPT-4o fine-tuning does not support image @ we evaluate all methods with a text-only modality from VWA. We mainly consider training and evaluating on 234 tasks from the Classifieds environment, GPT-4o finetuming is costly. For sim- plicity, we refer to R-MCTS with a aulti-agent-debate value function VXA as R-MCTS Note that ExACT and REACT similar prompts, with slight modifications in the system prompts to encourage exploration
Training Data We first run R-MCTS on Classifieds, and then sampled 65 trajectories for Imitation Learning according to the estimated values of final success. However, since search tree traversals are typically long, we further remove trajectory that results in more than 20 actions, pro- ducing 35 trajectories. We format these data into multi-turn chats, and use OpenAl finetuning API for training.
Quantitative Results indicate that both EXACT, trained with Imitation Learning and Exploratory Learning, outperform
We present the comparison results with REACT in Table Our findings
At the time of the study, GPT-4o vision-finetuning was not yet supported.

---

Published as a conference paper at ICLR 2025
Success
Method
Model
Search
Max Steps
Training
Tokens
Seen
Unseen
Overall
REACT
-Pi-io-mini
x
20
X
1.0x
20.9%
REACT ol-mini
X
20
X
1.0xt
23.9%
REACT
GPT-4o
X
1.0x
22.2%
REACT GPT-40
X
20
X
2.4x
22.2%
EXACT
GPT-4o
R- R-MCTS
20
X
9.6x
32.1 1%
EXACT
GPT-4o w/ IL
X
20
65
2.5x
80.0%
12.4%
31.2%
EXACT
Go w/ EL
X
20
35
3,6x
80.0%
18.6%
27.8%
Table 3: Comparing different model's performance evaluated in the Classifieds environment, All non-search methods are based on direct prompting. *While total token consumption is similar, ol- mini used 20x more output tokens (reasoning output) than GPT-4o-mini's output tokens (output).
most recent tooffee with a screen'. Then, comment with "great item..
Legend:
Action sequence:
search) touch screen'
State transitio:
Start
Agent output:
XXX
aciinn
V=gg: ; [go_ backback
V=
Ø *P
[stop]
[cice] Applanoes
[clos] Keurig KS.0
[type) Igrea Ier
Figure 4: After Exploratory Learning, GPT-4o demonstrates the ability to explore, evaluate, and backtrack without augmenting with search algorithms.
REACT (based on the untrained GPT-4o) by considerable margin, even without utilizing any search algorithm. Compared to R- R-MCTSWAD. both methods achieved over 85% of the performance while reducing token usage by up to 4x. In addition, ExAcT with EL achieves significantly higher success rate on unseen tasks, demonstrating the effectiveness of exploratory learning. These results suggest that even powerful models like GPT-4o can benefit greatly from training with agentic data.
Qualitative Results With Exploratory Learning, we find that GPT-4o is able to perform better on unseen tasks by performing exploration, state evaluation, and backtracking without relying on any search algorithm. We illustrate an example in Figurre 4 after attempting to directly search for "coffee maker with a touch screen", the Exploratory Learning trained-GPT-4e finds that the search function in Classifieds may be unreliable (top search result is sofa) and backtracked to use category filters instead.
4.3 COMPUTE SCALING RESULTS
We explore whether R-MCTS and the fine-tuned model after the self-learning stage has the property of test- computing scaling, i.e., whether performance can increase when more test-time computes, such search tokens, are allocated. To study this, we follow the same experiment setup in our main results in Secciin 4.1, but vary the search budget to allow R-MCTS for (2, 5, 10, 15) nodes per search tree. We then compare performance (Success Rate) and token consumption per task compared to REACT (Tokens) in Figure la] Since searching with more nodes significantly increases time and cost, we report results by testing on all 234 tasks in the Classifieds environment.
As shown in Figure I our proposed R-MCTS and Exploratory Learning exhibit strong scaling prop- erties for both train-time and test-time compute. Particularly, in Figure I left, we find that R- MCTS significantly improves performance when allocated with more test-time compute: using 15 nodes per tree, R-MCTS achieves a relative improvement 66% compared to REACT. Fur- thermore, Figure rright also illustrates that without search, both Imitation Learning and Exploratory
8

---

Published as a conference paper at ICLR 2025
Learning substantially boost the performance of untrained GPT-4o when allowed more actions per task. Notably. Exploratory Learning demonstrates a more favorable scaling trend in test-time compute compared to Imitation Learning. it is trained to learn to search. These results highlight the potential for self-improvement via reflective search and self-learning in agentic applications.
ANALYSIS
Search
Easy
Medium
Hard
5.1 SUCCESS RATE BREAKDOWN
X (REACT)
42.4%
20.9%
11.6%
ToTBrs
46.4%
28.0%
14.7%
In addition to having tasks in different environ- ments, VWA labels these task for action difficulty. These labeled by estimating the number of steps an average human would take to complete the task: easy (1-3 steps). medium (4-9 steps). and hard (10 steps or more). We evaluate all methods using the same setup as in main results in Sec- tion 4.1
DOT
46.8%
26.5%
12.8%
Search Agent
45.9%
29.6%
18.4%
MCTS
47.8%
32.5%
16.5%
R-MCTS R-MCTS
50.7%
33.6%
19.9%
49.3%
34.1%
23.6%
We present the results in Table 4
Table 4: VWA performance by difficulty.
R-MCTS improves performance across difficulties Compared to prior best, we find R-MCTS agent improved performance by an avearge of 2.5% absolute across all difficulties. This shows that the search and improvement loop in the R-MCTS agent not only benefits planning long-horizon tasks, but also enhances robustness in solving easier tasks.
Multi-Aeent-Debate benefits difficult tasks When using multi-agent value function (R- MCTSyaD), performance is further improved in medium and hard tasks. We believe this is be- cause multi-agent debate encourages more critical view of the current state, and making less error-prone in long horizon tasks. However, in easier tasks, we find such method can suffer from "over-thinking" by trying to avoid non-existent issues, which can slightly reduce performance.
5.2 ABLATION STUDIES
We perform ablation studies for each of component in R-MCTS to understand their contributions to the overall performance. In Table 3] report the over- all performance across all 910 tasks in VWA when removing 1) reflection from value function; reflec- tion from policy; and 3) the search algorithm. We find that reflections for policy improvement cial than reflections for value function, and that search essential for competitive performance.
Overall Success
Method
Token
R-MCTS
9.3x
33.7%
Value refl.
9.0x
32.9%
Policy refl.
8.6x
30.2%
Search
1.0x
21.9%
Table 5: Ablation studies on VWA.
5.3 QUALITATIVE ANALYSIS
To better understand the search process in R-MCTS we manually inspect 80 randomly sampled trajectories and their corresponding search trees. We compare against trajectories generated by SEARCH AGENT and analyze enrors made by our method.
Exploration and Reflection improves action quality Amongst the 80 samples, we find that R- MCTSyan outperforms SEARCH AGENT in 12.5% of the tasks. We find that this is primarily due to R-MCTSuan 's ability to improve policy (60%) using the dnfection-improvemeed tion 3.T and its ability to balance exploration-exploittiie (30%) using UCT instead of best-first.
process (Sec-)
GPT-4o still lacks finegrained image and web understanding In Figure 6 we categorize all er- rors made by R-MCTS during its search process by 1. failing to correctly format the final answer (answer formatting error); 2. errors caused by the agent-environment interaction (environmental er- ror); 3. enrors caused by GPT-4o's 's inability to perform fine-grained image understanding (model image understanding): and 4. errors caused by GPT-4o's limited web understanding/reason abil- ity (model web understanding). For more details, please refer to Apppendixx D..1] Our analysis reveals

---

Published as a conference paper at ICLR 2025
that most of the errors caused by the backbone VLM's inability to understand the provided web- page screenshot/prouuct images. Examples include failing to correctly identify the item on a-th row and b-th column a shopping page; and misunderstanding that the cheapest product shown on the current page (sorted by most recently listed) is the cheapest product available on the entire site. We believe these model issues are fundamental to many current agents that rely on prompting and suggest that model training (alike Section 3.2) is essential to further improve agent's 's performance.
6 RELATED WORK
Sanguagge-uuider Agents Advances in large language models (LLMs) have motivated many
cent works to re-purpose LLMs for automating agentic tasks (Nakano et al. [022]] Kim et al.
2023
Xi et al.] 2023). These methods include prompting LLM directly as policy (Hong et 2023
Yao et al. 2023b Sridhar et al. 2023; Yang et al. 2023a). as a component of manually designed
agentic framework (Park et al., [023] Sumers et al. 22024) , combined with manually crafted heuris- tics/prompt designs to improve performance (Fu et al., 2024, Sodhi et al. (2024), or combined with tool uses for question answering/code generation (Yang et al., 2024; Xia et al. (024).. For tasks that requires visual understanding, many recent work have thus swapped the prompting L.MSs to prompting visual language models (VLMs) such as GPT-4o (Zheng et al. 2024, Koh et al., (2024)). However, these methods typically suffer in long-horizon tasks that requires planning and error covery. Our work thus augments VLMs agents with search algorithms such as MCTS (Silver et al.) 2017 to complete tasks in complex and realistic web environments.
Augmenting Agent with Search/Reflection Using LLMs or VLMs to solve long-horizon tasks such web navigation is a highly challenging task (Liu et al.. 2023 Zhou al. 2024b Koh al.)
2024a). Many recent work thus also explored various strategies to improve agent's ' decision making process, such as: iteratively prompting the model to improve its own output (Madaan 2023 Yu et al., 2024; Shhinn et al. (2023); and augmenting agent's 's decision process using search algorithms such as BFS/DFS (Yao et al. 2023a), best-first search (Koh al., 2024b), and MCTS (Yu et al. 2023 Zhou et al., 2024a). However, many of these methods primarily focus on rext-based environ- ments such as question answering and programming, and do not involve substantial interaction with complex environment. In contrast, our work focuses on 1) conducting MCTS in long-horizon, agentic tasks in a realistic web environment; 2) incorporating multi-agent-debate value function to improve state evaluation; and 3) using contrastive reflection to learn from past successes and failures in long execution trajectories.
Training Agents Besides improving agent's performance test-time, many works also explored methods to train the backbone LLM/VVM. Examples include Mind2Web (Deng et al. 2023). Fire- ACT al. (2023), AgentInstruct (Zeng al. 2023). WebGum (Furuta et al. 2024), AutoWe- bGLM (Lai et al. 2024). and more (Zhang et al. 2024b Liu et al. 2024 Zhang et al. 2024a). These methods rely on collecting human or machine generated trajectories based on direct prompting, and perform supervised training to improve model's ' performance. To our knowledge, we are the first to train GPT-4o using trajectories produced by MCTS, and to teach GPT-4o to explore, evaluate, and backtrack in complex web environments through training on MCTS tree traversal.
7 CONCLUSION
In this work, we first introduced R-MCTS agent, cearch-augmented agent powered by by 1) MCTS to explore, evaluate, and backtrack in complex and realistic web environments: 2) multi-agent-debba value function for reliable state evaluation; and 3) contrastive reflection to learn from past successes and failures in long execution trajectories. Then, we proposed methods to transfer knowledge ac- quired from search back to GPT-4o by 1) training on best actions returned by tree search (Imitation Learning); and 2) training on the entire MCTS tree traversal (Exploratory Learning). Experiments on the challenging Visual WebaalWerrren benchmark show that R-MCTS achieves a new state of the art, and that finetuned GPT-4o agent begins to display test-time compute scaling properties similar to search algorithms. We believe our work presents a promising direction to combine test-time time search and model self-learning to develop the next-generation autonomous agents.
10

---

Published as a conference paper at ICLR 2025
8 LIMITATIONS
High cost of scaling test-time compute Although MCTSS-ased agents achieve strong perfor- mance on benchmarks such VWA, they consume nearly 10x more tokens compared REACT. This presents clear trade-off between performance and cost/time, and may limit the practicality of deploying such agents in real-world applications. However, these search-augmented agents can be used to curate training data for VLMs without human labels, which can in turn help develop stronger VLMs. Our work presents a promising step in this direction using Imitation Learning and Exploratory Learning, and we believe such self-learning loop is crucial to build stronger agents.
Long trajectories from tree traversal In long-horizon tasks, R-MCTS agents require a large amount of simulation to identify optimal actions, resulting in long tree traversals. Training these long traversals can be costly, and may be difficult for models to learn from. Nevertheless, we believe this issue can be iteratively mitigated by using self-learning to improve model capability, and by conducting search using the improved policy/value functions. We leave explorations for future work.
REFERENCES
Marah Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat Behl, et al. Phi-3 technical re- port: A highly capable language model locally on your phone. arXiv preprint arXiv:2404. 14219, 2024.
Saaket Agashe, Jiuzhou Han, Shuyu Gan, Jiachen Yang, Ang Li, and Xin Eric Wang. Agent s: An open agentic framework that uses computers like human, 2024. URL https://arxiv.. org/abs/22 /2100 08164
Anonymous. Learn-by-interact: A data-centric framework for self-adaptive agents in realistic envi- ronments. In Submitted to The Thirteenth International Conference on Learning Representations, 2024.
under review.
Anthropic. The claude model family: Opus, sommet, http://iw.aa.aaaaaaaaaaooooooatt com/ dea htt.a:/00...aacccaaaaaaaabb..a..
Laaoodee___rrr_C_aee Claude_
3. f. 2024.
Samuel R. Bowman, Jeeyoon Hyun, Ethan Perez, Edwin Chen, Craig Pettit, Scott Heiner, Kamilè Lukošiūté, Amanda Askell, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Christopher Olah, Daniela Amodei, Dario Amodei, Dawn Drain, Dustin Li, Eli Tran- Johnson, Jackson Kernion, Jamie Kerr, Jared Mueller, Jeffrey Ladish. Joshua Landau, Kamal Ndousse, Liane Lovitt, Nelson Elhage, Nicholas Schiefer, Nicholas Joseph, Noemí Mercado, Nova DasSarma, Robin Larson, Sam McCandlish, Sandipan Kundu, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Timothy Tellcen-Lawton, Tom Brown, Tom Henighan, Tristan Hume, Yuntao Bai, Zac Hatfield-Dodde Ben Mann, and Jared Kaplan. Mcasuring progress scalable oversight for large language models, 2022. https: abs/ 0.ss/2211.03544
Baian Chen, Chang Shu, Ehsan Shareghi, Nigel Collier, Karthik Narasimhan, and Shunyu Yao. Fireact: Toward language agent fine-tuning, 2023.
05915
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Samuel Stevens. Boshi Wang. Huan Sun, and Yu Su. Mind2weh: Towards a generalist agent for the web, 2023. URL https://arxiv..
org/abs/ abs/2306.06070
Yao Fu, Dong-Ki Ki Kim, Jaekyeom Kim, Sungryull Sohn, Lajanugen Logeswaran, Kyunghoon Bae, and Honglak Lee. Autoguide: Automated generation and selection of sate-award guidelines for large language model agents, 2024. http::/:: hatpss///rriivv org/ abs/ / 2403.44004 08978
Hiroki Furuta, Kuang- Huei Lee, Ofir Nachum, Yutaka Matsuo, Aleksandra Faust, Shixiang Shane Gu, and Izzeddin Gur. Multimodal web navigation with instruction-finetumed finetumed foundation models, 2024. URI.tttps. / /tt../..bb33335.1..1333

---

Published as a conference paper at ICLR 2025
Gemini. Gemini: A family of highly capable multimodal models, 2024. URL https: org/abs/ 2312. 11805
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration, 2020. URL htRLtt:t/////xtt...o.
abs
Sirui Hong. Mingehen Zhuge, Jonathan Chen, Xiawu Zheng. Yuheng Cheng, Ceyao Zhang, Jin- lin Wang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. Metagpt: Meta programming for a multi-agent collaborative framework, 2023. /RR/ihtpss.//axxi..rr/////s 200.////33300030322222 00352
Chengyou Jia, Minnan Luo, Zhuohang Dang, Qiushi Sun, Fangzhi Xu, Junlin Hu, Tianbao Xie, and Zhiyong Wu. Agentstore: Scalable integration of heterogeneous agents as specialized generalist computer assistant, 2024. URL httphhttt/aaiiiiiiee
18603
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks, 2023. URLBttts:://artt //axivv.aaiiivaa/aa www.:org/aaaa....ae /ttp:/bbb/333..444333.3
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In Proceedings of the 17th European Conference on Machine Learning, ECML'06, pp. 282-293, Berlin, Heidelberg, 2006. Springer- ISBN 354045375X. doi: 10.1007/11871842 29. URL http:: //doi.
otg/1001007/1110..
Jing Yu Koh, Robert Lo, Lawrence Jang, Vikram Duvvur, Ming Chong Lim, Po-Yu Huang, Graham Neubig, Shuyan Zhou, Ruslan Salakhutdinov. and Daniel Fried. Visualwebarena: Evaluating multimodal agents on realistic visual web tasks, 2024a. URL
wrw.voorg/aaa /bs//////////
2401. 13649
Jing Yu Koh, Stephen McAleer, Daniel Fried, and Ruslan Salakhutdinov. Tree search for language model agents, 2024b.
wwtp://rrgaaabba/aae.oae 21476
Hanyu Lai, Xiao Liu, lat Long Iong, Shuntian Yao, Yuxuan Chen, Pengbo Shen, Hao Yu, Hanchen Zhang, Xiaohan Zhang, Yuxiao Dong, and Jie Tang. Autowebglm: Bootstrap and reinforce a large language model-based web navigating agent, 2024. URL pettps://arxive org/ a
2404. 03648
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du Chenhui Zhang, Sheng Shen, Tianjun Zhang, Yu Su, Huan Sun, Minlie Huang. Yuxiao Dong, and Jie Tang. Agentbench: Evaluating Ilms as agents, 2023. URL https:://axxt org/ /bs/
2308. 03688
Zuxin Liu, Thai Hoang, Jianguo Zhang, Ming Zhu, Tian Lan, Shirley Kokane, Juntao Tan, Weiran Yao, Zhiwei Liu, Yihao Feng, et al. Apigen: Automated pipeline for generating verifiable and diverse function-calling datasets. arXiv preprint arXiv:2406.188. 18518, 2024.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao. Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang. Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self- refine: Iterative refinement with self-feedback, 2023. URL https: http://axvvvv.o/ ott.ab//r//bb///// 23C3.17651
Ference Marton. Necessary Conditions of Learning. Routledge, 1st edition, 2014. doi: 10.4324/
9781315816876. URL httpss://ctciii... .or./rg/gl 10 0.4424447813333 581 6876
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Eloundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman. Webgpt:
Browser-assisted question-answering with human feedback, 2022. URL
oxc/abs/2112.0933
OpenAl. Hello GPT-4o. htth:://opeaa..ccmmindee///////p
2024a. Ac-
cessed: 2024-09-28.
12

---

Published as a conference paper at ICLR 2025
OpenAl. Introducing OpenAl ol. https://openat.comt 2024b. Accessed: 2024-09-29.
OpenAl. New embedding models and api updates. http:::/oppeaa.ccomm//
eew--mmbdding-eom model-gg--ooeeeeeeeeee--- and--nd-Bas api sspiuupdaess/ 2024c. Accessed: 2024-09-28.
Joon Sung Park, Joseph C. O'Brien, Carrie Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Berstten. Generative agents: Interactive simulacra of human behavior, 2023. URL
Christopher Rawles, Alice Li, Daniel Rodriguez, Oriana Riva, and Timothy Lillicrap. Android in the wild: A lcage-scale dataset for android device control, 2023. wwtphtttss///rxiiie org/
abs 2bb//307.. 10088
Christopher Rawles, Sarah Clinckemaillie, Yifan Chang, Jonathan Waltz, Gabrielle Lau, Marybeth Fair, Alice Li, William Bishop, Wei Li, Folawiyo Aajaaall-Ajala, Daniel Toyama, Robert Berry, Divya Tyamagundlu, Timothy Lillicrap, and Oriana Riva. Androidworld: dynamic benchmark- ing environment for autonomous agents, 2024. URL https: wwwpvvarivvvv. orw.v///4gg//////55555
14573
Christopher D. Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):203-230, March 2011. ISSN 1012-2443. s10472-011 1114772011-9258-0 1-9258-6.
doi: 10.1007/
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023. URL
atttss:/aarxtr org.//////////33311132
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Si- monyan, and Demis Hassabis. Mastering chess and shogi by self-play with general reinforce-
ment learning algorithm, 2017. URL URL http::tps//// /tttpps:/aax....oo////o// hbwpg//ab///1ul 01815
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters, 2024. URL https: pettps://arxizn /ttp/aaaxvvvoogeeeeeeeeee abs / 2408. 03314
Paloma Sodhi, S. R. K. Branavan, Yoav Artzi, and Ryan McDonald. Step: Stacked Ilm policies for web actions, 2024. URL
Abishck Sridhar, Robert Lo, Frank F. Xu. Hao Zhu, and Shuyan Zhou. Hierarchical prompting assists large language model on web navigation, 2023. URL
2365. 14257
Theodore R. Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas L. Griffiths. Cognitive archi- tectures for language agents, 2024. URL Wttphhtps:///xxxx org 2ttab///33..000 02427
Richard Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL
2nd.
html
Chris van der Lee, Albert Gatt, Emiel van Miltenburg, Sander Wubben, and Emiel Krahmer.
Best practices for the human evaluation of automatically generated text. In Kees van Deemter, Chenghua Lin, and Hiroya Takamura (eds.), Proceedings of the 12th International Confer- ence on Natural Language Generation, pp. 355-368, Tokyo, Japan, October-November 2019. Association for Computational Linguistics. doi: 10.18653/v1/W19-888 1643.33... URL https:
Xingyao Wang, Boxuan Li, Yufan Song, Frank F. Xu, Xiangru Tang, Mingchen Zhuge, Jiayi Pan, Yueqi Song, Bowen Li, Jaskirat Singh, Hoang H. Tran, Fuqiang Li, Ren Ma, Mingzhang Zheng, Bill Qian, Yanjun Shao, Niklas Muennighoff, Yizhe Zhang, Binyuan Hui, Junyang Lin, Robert Brennan, Hao Peng, Heng Ji, and Graham Neubig. Opendevin: An open platform for ai software developers generalist agents, 2024. URL https: wttp::/aaxvvvvv. httpp/////aaiooooo/aa/////////// 16741
13

---

Published as a conference paper at ICLR 2025
Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong. Ming Zhang, Jun- zhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang. Limao Xiong. Yuhao Zhou, Weiran Wang. Changhao Jiang, Yicheng Zou, Xiangyang Liu, Zhangyue Yin, Shihan Dou, Rongxiang Weng, Wensen Cheng, Qi Zhang, Wenjuan Qin, Yongyan Zheng, Xipeng Qiu, Xuan- jing Huang, and Tao Gui. The rise and potential of large language model based agents: A survey, 2023. URL https: / www.aawww.i.g...oaaaoooaoaa
2009 07864
Chunqiu Steven Xia, Yinlin Deng, Soren Dunn, and Lingming Zhang. Agentless: Demystifying Ilm- abs/ /200. 0149
based software engineering agents, 2024. URL
Tianbao Xie, Danyang Zhang, Jixuan Chen, Xiaochuan Li, Siheng Zhao, Ruisheng Cao. Toh Jing Hua, Zhoujun Cheng, Dongchan Shin, Fangyu Lei, Yitao Liu, Yiheng Xu, Shuyan Zhou, Sil- vio Savarese, Caiming Xiong, Victor Zhong, and Tao Yu. Osworld: Benchmarking multimodal agents for open-ended tasks in real computer environments, 2024. URL https://arxxx org/abs/ 2404. 07972
Hui Yang, Sifu Yue, and Yunzhong He. Auto-gpt for online decision making: Benchmarks and additional opinions, 2023a. URL httpl/tts//aaxi..orrrr/o//// abs// 2306 02224
Jianwei Yang. Hao Zhang, Feng Li, Xueyan Zou, Chunyuan Li, and Jianfeng Gao. Set-of-mark prompting unleashes extraordinary visual grounding in gpt-4v, 2023b. URL bRtpss////axx org/abs/ 2a00. 11441
John Yang, Carlos E. Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. Swe-agent: Agent-computer interfaces enable automated software engineering, 2024. URL htLLhtts::// arxiv http://///.aa..oooo.//////////5/
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023a.
URL http::tt/a//xiiiii
wttp/br//////eoeeeoeo/eeeeeeee/e 2305 10601
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023b. Uttppstts///axxi
org/aba/2222 attaabaa221.... 03629
Xiao Yu, Maximillian Chen, and Zhou Yu. Prompt-based cante-carlo tree search for goal-oriented dialogue policy planning, 2023. URL htt.thts//aaxxi...o.o wrw.vv.rorga..... http://abbb3335553353333
Xiao Yu, Baolin Peng, Michel Galley, Jianfeng Gao, and Zhou Yu. Teaching language models to self-improve through interactive demonstrations, 2024. URL https://erxiv.orr////
2310.13522
Aohan Zeng, Mingdao Liu, Rui Lu, Bowen Wang, Xiao Liu, Yuxiao Dong, and Jie Tang. Agenttun- ing: Enabling generalized agent abilities for 1lms, 2023. URL htttt:tt////xet org/ abs/ 2310. 12823
Jannuu Zhang, Tian Lan, Rithesh Murthy, Zhiwei Liu, Weiran Yao, Juntao Tan, Thai Hoang, Liang- wei Yang, Yihao Feng, Zuxin Liu, et al. Agentohana: Design unified data and training pipeline for effective agent learning. arXiv preprini arXiv:2402. /5500 2024a.
Jianguo Zhang, Tian Lan, Ming Zhu, Zuxin Liu, Thai Hoang, Shirley Kokane, Weiran Yao, Juntao Tan, Akshara Prabhakar, Haolin Chen, Zhiwei Liu, Yihao Feng, Tulika Awalgaonkar, Rithesh Murthy, Eric Hu, Zeyuan Chen, Ran Xu, Juan Carlos Niebles, Shelby Heinecke, Huan Wang, Silvio Savarese, and Caiming Xiong. xlam: A family of large action models empower agent systems. arXiv, 2024b. URL https: / //aaaiiivvv..////////aa/////aat/ org/ abs 020./22299..3222
Boyuan Zheng, Boyu Gou, Jihyung Kil, Huan Sun, and Yu Su. Gpt-4v(ssion) is generalist web agent, if grounded, 2024. URL
Andy Zhou, Kai Yan, Michal Shlapentokh -oatpennnkkh-RRhhma.....m Haohan Wang, and Yu- Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models, 2024a. URL http:t wwwrx/w.wrr/aabb/22322 04406
14

---

Published as a conference paper at ICLR 2025
Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uni Alon, and Graham Neubig. Webarena: A realistic web environment for building autonomous agents, 2024b. URL
abs/
2307 13854
Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Maúdziuk. Monte carlo tree search: a review of recent modifications and applications. Artificial Intelligence Review, 56(3): 2497-2562, July 2022. ISSN 1573-7462. doi: 10. 14.20077/ 10228-y. URL http:
//dx. ///
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL IMPLEMENTATION DETAILS
A.1 MONTE CARLO TREE SEARCH
We describe the Monte Carlo Tree Search (MCTS) algorithm used in work in Algorithm We use the same MCTS search implementation for all relevant methods (MCTS, R-MCTS, and R- MCTSyaD agent). For clarity, abuse the notation represent observations in this section, in order comply with notations used in other works (Swiechowski et al. 2022).
Algorithm MCTS
Require: VLM policy πT (g, r)
Require: VLM value (g,, T)
Require: environment T
Require: goal g and current observation 8
Require: actual trajectory far (before s)
1: while search budget is not exhausted do
2: Scurr 8
3: Tourr T
4: selection
5:
while Scurr is not leaf node do
6:
6 arg max, o (Seurre a) + U (Scurr: a)
7:
Scurr + (Seurr:: a))
8:
Teurr f Tour {a, Scurr
9:
end while
10:
expansion
11:
{al a ,a?,...,a" ......a]} +- T(9, Teurr)
12:
I/ evaluation
V(g, Teurr)
14:
11 bacckppropaaation
while Scurr # do
16:
Scurr + -parent(seurr Geurr)
update Q, using with Eiuution (2)
18: end while
19: end while
20: // preddcttion
21: a² + arg maxa as)
22: return a"
During selection, we follow Silver al, (207)) and use a variant of PUCT (Rosin 2011) balance exploration and exploitation:
VE, (s,b))
U(s.a)= =p P(als) (((aas)
a(s
where is a hyperparameter controlling the exploration rate, P(a]s) is the VLM's prior probabil- ity of generating action in state s, and N ((s, a) is the state visit count. We use cp 1.0 in our experiments.
During evaluation, we prompt the VLM value function using the process described in Sec- Tion 2.3 During back-propagation, we update the search tree's action-value estimate Q and visita- tion count N using running average:
+ V -- ((s.a)
Q(s,a)+ +
N(s.a)+ +1
(2)
a(s,a)
16

---

Published as a conference paper at ICLR 2025
Algorithm 2 R-MCTS Agent
Require: VLM policy π ((g. r)
Require: VLM value (gg,T)
Require: environment T
Require: list of tasks to complete G
for task g in G do
2: // inference loop
3: T {
4: tree <- -sso}
5:
while task not terminated do
6:
while search budget not exhausted do
7:
selection
8:
sclection(tree)
9:
expansion
10:
reflections, retrieve(db,, 9, 8t)
11:
o,,..., at +- (g, T, reflection))) // simulation
13:
8141 + T(s,,
reflectionsy retrieve(dby, g. St+1)
15:
+ V(g, (su, ao...., $1+1), reflectionsy)
bacc--propagation
17:
tree c- update(tree, 0))1,
end while ac f bestaaction(ree)
19:
20:
St+1 t T(st, 0t)
21:
TU S1+1)
22:
tree +- {s++1}
23:
end while
24:
< task success/failure
improvement loop
26: reflections,, reflectionsy + reffect(VLMM T)
db, + update(reflections.))
28:
dby + update((releetionss))
end for
Algorithm Policy Reflection
Algorithm 4 Value Reflection
Require: VLM used during search
Require: VLM used during search
Require: Terminated task g and trajectory
Require: Terminated task y and trajectory
Require:
Search tree statistics Q,
Require:
Search tree statistics Q, V
Require: Vector database db
Require: Vector database db
1: // error altribution
1: // error altribution
2: ā + -arg max; error(alg.) r)
ō t- arg max, error T)
3: // contrastive reflection
3: // contrastive reflection
4: ōt+1 +- VLM(g, {op, 40, Oz, az.)
4: à, < L-VLM(g, {0o, ao....,; 5t))
5: reflection <- VL.M(g, ot, 0t, (ot-1, )
5: reflection <- VLM a: Ôt, {at, at})
6: // memorization
memorization
7: key + embedding(g,, 0z)
7: key embedding(g, 0z)
8: db f add(key, reflection)
db +- add(key, reflection)
9: return
return
A.2 R-MCTS PSEUDO CODE
Overall Algorithm We describe our R-MCTS agent in Algorithhm 2 For clarity, also abuse the notation s to represent observations in this section, in order to comply with notations used other works (Swiechowski et al. 2022). We omitted details about action selection, expansion, simulation, and back-propagation they described in Appendix A.T We present the main loop in R-MCTS
17

---

Published as a conference paper at ICLR 2025
REFLECT
IMPROVE
error attribution
given test new task
task 2
task
O
*
arg max ((@)
retrieve
0.6
contrastive reflection
in-context update
memorization
}
Reflection
Value
Key
Figure In-context imnprveenn- loop for an R-MCTS agent. For brevity, we only present policy reflection, as value reflection is similar. Left: after complete episode, the agent 1) uses search tree statistics to select the most erroneous action āj from 7 to reflect on; 2) prompts the VLM generate reflection by contrasting what it expects achieve 64+1 and what actually happens oc+1; 3) embeds the reflection agent 1) retrieves most relevant reflections from the database; 2) improves its policy (and value function) using in-context learning.
vector database. Right: to generate an action in a new task, the
which consists of an inference loop where the agent conducts tree search find the best action for given state; and 2) an improvement loop where the agent reflects on its past actions, and updates its policy and value function in-context using retrieval for future tasks. We detail the reflection and update process below.
Contrastive Reflection We present the pseudo code for both policy contrastive reflection and value contrastive reflection in Algorithm 3 and Algorithm 4 respectively, and illustrate the reflection-update process in Figure 5) This reflection process is repeated for times per trajectory for the top-n, erroneous actions during policy reflection, and ny times for value function reflection. We use n = 3 and ny in our experiments. We use cext-ada-003-smal (OpenAl 2024c) as the embedding model. For clarity, we repeat the error attribution equations in Seeciion below:
error=(al17) (o(++)) - Q(or, at)l (o)l7) (V(o.) ((0--1,40-1) (3)
Improvement Given a new task and trajectory 7 {oo, ao ao...., or). we retrieve the m = most relevant reflections from the database, and use them to improve the policy and value function by appending them into the existing context (see Appendix E.2 for the prompt template). The retrieval process is done by computing the cosine similarity between the current task and observation embedding(g, o,) and the keys stored in the vector database. Since many tasks/webe wekksge are unique, also set minimum similarity threshold of 0.25 to only relevant reflections.
18

---

Published as a conference paper at ICLR 2025
Method
Task Affected by Error
Avg.
Time per Task
Success Rate
Koh et al. (024b)
40.00%
33.47 min
45.00%
+Asyncio
40.00%
14.65 min
35.00%
+Caching
35.00%
10.03 min
40.00%
+Action Re-mapping
10.00%
10.10 min
45.00%
Table 6:
Ablation studies of our modified browser implementation. Results are evaluated using SEARCH AGENT over 20 randomly sampled task in the Classifieds environment.
Method
Model
Success Rate Before
Success Rate After
REACT
GPT-4o-mini 10.67%
14.67% 22.67%
SEARCH AGENT
GPT-44-mini
18.67%
REACT
GPT-4o
14.67%
27.27%
SEARCH AGENT
GPT-4o
26.67%
38.57%
Table Performance comparison after updating task intents in VWA. We measure the task success before and after the updates for 75 randomly sampled tasks in the Classifieds environment.
B
ADDITIONAL DETAILS ABOUT VWA
B.
WEB BROWSER
agents require frequent backtracking explore actions. As result, find prior implementations of the web browser is inefficient and error prone: 1) all processing is done in single thread sequentially; every (backtracked) page is re-processed from scratch; and can frequently cause action element id mismatch errors since backtracked page may not always be the same as before (e.g., search history is stored in the website's database and cannot be reset).
We thus modified the existing web browser used in Koh et al. (2024b), and used the same modified browser for all methods in our experiments. Our modifications include:
1. use asyncio parallelize webpage processing (Asyncio):
2. implement a caching mechanism to store and retrieve SoM processing output when the same webpage is encountered (Caching):
3. when SoM element ids changed after backtracking, we implement a simple heuristic (word overlap of some metadata associated with the element) re-map the VLM generated action id back to the correct element id (Action Re-mapping).
We present a quantitative study of these changes in Table
B.2 VWA EVALUATION
One common eгror we find with GPT-4o based agents (e.g., using REACT) is to directly return the (correct) item's 's name and description from (e.g..) the search result page, while VWA evaluates these tasks by checking if the final state's URL is the desired item's URL. However, we believe this is due to ambiguously phrased task intent, such as "Find me the cheapest blue kayak on this site", and "Find the most expensive car from Virginia that neon green", which does not explicitly mention/require navigating to the item's 's page complete.
To this end, we updated these task instructions by appending the sentence: "Finish the task by navigating to that item's page and returning me the url link(s)" to these tasks for clarity. This change affected 93 instances in the Classifieds environment, instance in the Reddit environment, and 34 instances in the Shopping environment. We present quantitative study of this change in Table 7, and find that all methods/VLLMs significantly improved by simply aligning the task intent with the evaluation metric. Unless otherwise specified, use these updated task intents for all methods
19

---

Published as a conference paper at ICLR 2025
6.55g B.315
Error Type
answer formatting error
URL/product detail formatting error environmental
eervioonment/eegreennttioo error [potential] evaluation error model image understanding
45.2%
image details (color, material, etc)
image position (i-th column/row)
45.2%
selected wrong SOM
model web understanding
forgot to sort search results
significant web common-sense
Figure 6: Error analysis for R R-MCTS after manually inspecting the search trees for 80 randomly sampled tasks from the Classfieds environment.
and experiments in this work. The comprehensive leaderboard for VisuelWebArena can be found in Table 10
C OSWORLD RESULTS
Baselines For evaluations OSWorld, directly compare against existing best methods from the official leaderboard. This includes AGENT-S (Agashe et al. 2024), a prompt-based framework that augments agents with online web search and an experience auggeeeted hierarchical planning module; AGENTSTORE (Jia et al. 2024) method that uses multiple (over 20) specialized agents as well as finetuning methods such as self-instruct to improve performance; [nnoyymous] 2024), data-centric framework using synthetic data (manually created based lated documentations and ggent-environmen interaction histories) to improve performance by either in-context learning further training. In general, these methods rely using additional resources such as online web search, task-specific models, or performs model training to improve performance.
LEARN-BY-INTER INTER ACT
Method
Model
Training
OS
Office
Daily
Profess.
Workflow
Overall
Success
Success
Success
Success
Success
Success
REACT
GPT-4o
41.67%
6.16%
12.33%
14.29%
7.46%
11.21%
AGENT-S
GPT-4o Web
45.83%
13.83%
30.46%
36.73%
10.53%
20.58%
AGENTSTORE(ICL)
Hybrid
X
1.71%
32.05%
22.44%
13.55%
ACENTSTORE(FT)
Hybrid
/
15.38%
37.18%
12.20%
17.34%
AGENTSTORE(AT)
Hybrid
V
28.20%
37.18%
23.93%
23.85%
R-MCTS
GPT-4o
x
45.83%
15.56%
25.27%
22.44%
11.52%
19.39%
Table 8: Comparing different agent's performance on OSWorld, using screenshot + accessibility tree as input. For AGENT-Sand AGENTSTORE, we use results reported by the respective authors. "Training" indicates whether the method finetuned the agent model. Results with gray backgrounds uses either additional resources (c.g., web search), models, or performs training.
Results We summarize the results evaluated using "screenshot + accessibility tree" input modality in Table 8 and also using "accessibility tree" only in Table 9 We find that R-MCTS shows com- petitive performance compared other state-of-tee of-the-art methods, despite only using on a single model with search algorithm.
20

---

Published as a conference paper at ICLR 2025
Method
Model
Training
OS
Office
Daily
Profess.
Workflow
Overall
Success
Success 6.99%
Success
Success
Success
Success
REACT
GPT-4o
20.831
16.81%
16.33%
7.56%
11.4%
LEANN-DY-INERRCT
Gemini- p-pro RAG
10.3%
Claudo-3.5 5-snncttt RAG
22.5%
MCTS
37.50%
10.41%
21.82%
24.49%
10.87%
16.6%
Table 9: Comparing different agent's performance OSWorld, using accessibility input. Results with gray backgrounds uses either additional resources (e.g., RAG with manually popu- lated database) or different models.
Model
Inputs
Success Rate (%)
ExAcT (GPT-40 R- R-MCTSSAn MAD)
SoM + Caption + Image
33.74
EXACT (GPT-40 R-MCTSsa)
SoM + Caption Image
32.53
GPT-4o MCTS
SoM + Caption Image
30.22
GPT-4o Search
SoM Caption Image
26.40
GPT-4o ICAL
SoM + Caption Image
23,40
GPT-4o
SoM + Caption Image
19.78
Llama-3-70B + Search
AxTree Caption
16.70
GPT-4V
SoM + Caption Image
16.37
+
AxTree + Caption + Image
15.05
GPT-4
AxTree Caption
12.75
Gemini-Pro-1.5
SoM + Caption Image
11.98
Llama-3-70B- BLIP-2-T5XI.
AxTree Caption
9.78
GPT-4
AXTree
7.25
Ge
SoM + Caption Image
6.59
Gemini-Pro
SoM + Caption Image
6.04
Gemini-Pre
SoM + Caption Image
5.71
Gemini- -rro BLIP-2-T5XL
AxTree Caption
3.85
GPT-3.5 + BLIP-2-T5XL
AxTree + Caption
2.97
GPT-3.5 LLLaV-7B
AxTree Caption
2.75
GPT-3.5
AXTree
2.20
Gemini-Pro
AXTree
2.20
Mixtral-8x -anrall8x77++1 BLIP-2-T5XL
AxTree Caption
1.87
Mixtral-8x7b
AXTree
1.76
Llama-2-70B
AXTree
1.10
SoM + Caption Image
0.99
AXTree + Caption Image
0.77
1lama-2-708 + BLIP-2-TSXL
AxTree + Caption
0.66
CogVLM
SoM + Caption Image
0.33
CLg
AXTree + Caption Image
0.33
Table 10: VisualWebArena Leaderboard
D ADDITIONAL ANALYSIS DETAILS
D. ERROR ANNOTATION SCHEME
We label errors made by our R-MCTS agent into primary categories (answer formatting error, environmental error, model text understanding, and model image understanding). We find these categories covered most of the error cases. We further sub-divided these categories into 8 sub-error types for more detailed analysis, and present the result in Figure 6 We detail the error types below.
Answer Formatting Answer formatting errors include: 1) returning the item's name/description instead of its URL used for evaluation, or failing to format a range of prices into the instructed format /product detail formatting error).
21

---

Published as a conference paper at ICLR 2025
Arte crafts
Image
[20] [ING]
[description: wooden plate
with bullFighter
[21] [A]
[natador painting plate]
[ttaticeext]
[StaticText]]
[Lessure World (MD)]
Original Webpage
SoM Augmented Input
Figure 7: Example Set-of-Mart augmented webpage used as inputs for VLM agents.
Environmental Errors Environmental errors include: 1) incompatibility issues with certain web- site functionality (e.g., dropdown menu) with SoM augmentation (envinmmenttrepreeentta er- ror); and 2) ambiguous task intents leading to more than one potentially correct answer, one of which the model returned (potential evaluation error).
Model Image Understanding Model image understanding errors include: 1) failing to correctly identify certain properties (e.g., color, pattern, material, etc.) from an image (image details); 2) failing to identify product on the i-th row and/or j-th column (image position); and 3) generating an action with element ID not present the current observation (selected wrong SoM id).
Model Web Understanding Model web understanding errors include: 1) forgetting to sort search results and misunderstands the most expensive/cheapest item the current page is also the most expensive/cheapest item on the entire website (forgot to sort search results); and 2) other errors potentially caused by lack web common-sense knowledge, such trying filter for price ranges by typing in the search bar instead of using price filters, and returning related items on other pages when specifically instructed find it the current page (significant web common-sense error)
E ADDITIONAL PROMPTING DETAILS
E. SET-OF-MARK AUGMENTATION
We follow Koh et al. 22024 b) and represent visual webpages using Set-of-Mark (SoM) (Yang al. 2023b) augmentation. SoM augments webpage by 1) creating bounding boxes around each interactive element on the page; and 2) adding a unique identifier to each element. We present an example in Figure
E.2 PROMPTS FOR R-MCTS AGENT
Prompts for Contrastive Reflection We present the prompts to generate expected observation given a previous state an action in Table II] We then generate a reflection using use the prompts in Table 12
Prompts for Improvement We present the prompts used to format the relevant reflections re- trieved from the vector database back into model's current context in Table 13
22

---

Published as a conference paper at ICLR 2025
Role
Prompt
System
You are an autonomous intelligent agent tasked with navigating a web browser.
You will be given web-based tasks. These tasks will be accomplished through the use of specific actions you can issue.
Here's s the information you'll IIl'll have: (... some content omitted)
User
OBSERVATION:
0 [StaticTexx]]] [What are you looking for today?]
[5] [INPUT]
[6] [SELECT] [Select a category]
[7] [BUTTON] [Search]
[ [Static Text] [Latest Listings]
[SexticTexx]] [Atlas Powered Audio System w/ Tripod 150.00 Music instru-
ments Borough of Red Lion (Pennsylvania) 2023/1 1/16]
(... some content omitted)
OBJECTIVE: Find me the cheapest red Toyota. It should be between $3000 to $6000. Finish the task by navigating to that item's page and returning me the url lsn.(s).
IMAGES: (1) current page screenshot
image_uri danarimage/png.base64.,
VBORROKGGOAAAANNSU.
Assistant
Based on the objective. need to find the cheapest red Toyota priced between $3000 to S6000. (... some content omitted) In summary, the next action will perform is "'type [5] [red Toyota] [1]""
User
What do you expect to happen after taking this action? Briefly describe what you think will appear the webpage after performing the action.
Assistant
After taking this action, expect the webpage to display search results display- ing red Toyotas, (... some content omitted)
Table 11: Prompts used generate the expected state transition. image_url is the base64 encoded SoM augmented web screenshot. Multimodal input in highlighted in orange. Generated response is highlighted in blue.
23

---

Published as a conference paper at ICLR 2025
Role
Prompt
System
You are an autonomous intelligent agent tasked with navigating a web browser.
You will be given web-based tasks. These tasks will be accomplished through the use of specific actions you can issue.
Here's 's the information you'l you'll have:
(... some content omitted)
User
OBSERVATION:
[ [StaticcTex] [What are you looking for today?]
[5] [INPUT]
[6] [SELECT] [Select category]
[7] [BUTTON] [Search]
[StaticText] [Latest Listings]
[Static Text] [Atlas Powered Audio System w/ Tripod 150.00 Music instru-
ments Borough of Red Lion (Pennsylvania) 2023/1
(... some content omitted)
OBJECTIVE: Find me the cheapest red Toyota. It should be between $3000 to $6000. Finish the task by navigating to that item's page and returning me the url link(s).
IMAGES: (1) current page screenshot
image_url: dataiimage/png:base66.
Assistant
Based on the objective, need to find the cheapest red Toyota priced between $3000 to $6000. (... some content omitted)
In summary, the next action will perform is ""type [5] [red Toyota] [1]
Expectation: After taking this action, I expect the webpage to display search results displaying red Toyotas, (... some content omitted)
User
NEXT OBSERVATION:
[596] RootWebArea 'red Toyota Classifieds' focused: True
[630] link CCassiifids,, description: blue and black logo...'
[663] img 'Classifieds, description: a blue and black logo...
[638] link 'My account"
[639] link 'Logout'
[640] link 'Publish Ad'
[647] link 'Classifieds'
(... some content omitted)
IMAGES: (1) next page screenshot
Image URL: hitt:inggggggaasoooo/BBBBoKKKO
Is this wehpage what you expected? not, can you conclude anything spe- cial about navigating on this website? If you faced the same situation again, what would you do differently at a high level? Do NOT propose any specific actions/answers.
Keep your response within 100 words.
Assistant
This webpage does not display the expected car listings but rather includes various (... some content ommitted)
Table 12: Prompt used generate contrastive reflections given expected observation highlighted in teal. image.urt is the base64 encoded SoM augmented web screenshot. Multimodal input in highlighted in orange. Generated response is highlighted in blue.
24

---

Published as a conference paper at ICLR 2025
Role
Prompt
System:
You are an autonomous intelligent agent tasked with navigating a web browser.
You will be given web-based tasks. These tasks will be accomplished through the use of specific actions you can issue.
Here's the information you'll have: (... some content omitted)
User
REFL ECTION: here are some relevant reflections from other tasks. Note that these reflections may not be directly related to the new task below, but they may provide some useful insights.
OBJECTIVE (1): I recall seeing this exact item (... some content omitted) ATTEMPTED ACTION (1): Let's think step-by-step. The objective is to find the most recent post of the item shown in the image, which is a personal wa- tercraft. To find this, will search for "watercraft" in the search box. (... some content omitted)
In summary, the next action will perform is "type [5] [watercraft] [1] REFLECTION (1): This webpage (... some content omitted). However, it did not directly show the item from the provided image. The search term might have been too broad. (...some content omitted) #*###
OBJECTIVE (2): Tell me the name of the lister with (... some content omitted)
ATTEMPTED ACTION (2): Let's think step-by-step. The objective is to find the name of the lister with the most expensive green vehicle from West Virginia. (..some content ommitted)
In summary, the next action I will perform is "'click [60]
REFLECTION (2): Yes, the webpage what expected, displaying listings specifically from West Virginia. However, appears that filtering by color (green) is not directly possible. (... some content omitted)
!MMORTANT! Below is the task you need to solve. Please read the user's intent and input images (if any) carefully.
OBSERVATION:
[1] [IM]] [Classifieds, description: a blue and black logo with the words ohm,
url: http://coffee.cc http://fffee.cc.ooomlbbeeee htt.uummbaaccd.578........
[2] [A] [My account]
[3] [A] [Logout]
[4] [A] [Publish Ad]
[StaticText]] [What are you looking for today?]
(... some content omitted)
URL: http://classifedsscom
OBJECTIVE: How many yellow or blue motoreycles in total were posted on 25th October 2023?
PREVIOUS ACTION: None
NOTE: Remember that you should consider user's intent and reflections (if applicable) to better plan the next action.
IMAGES: (1) current page screenshot
Image URL: dltiingggnhhhsess.vooKKKKAAAA
Assistant
Let us think step by step. The objective is to find the total number of yellow or blue motorcycles posted 25th October 2023. From the reflections (... some content omitted)
Table 13: Prompt used generate an action given retrieved reflections, which is highlighted in teal.
image url is the base64 encoded SoM augmented web screenshot. Multimodal input in highlighted orange. Generated response is highlighted blue. For brevity, we present prompts for trajectories with only one action executed so far.
25

---

Published as a conference paper at ICLR 2025
Role
Prompt
System
You autonomous intelligent agent tasked with navigating web browser.
You will be given web-based tasks. These tasks will be accomplished through the of specific actions you can issue.
Here's the information you'll have: (... some content omitted)
User
User Intent: Find me the cheapest red Toyota. It should be between $3000 to $6000. Finish the task by navigating to that item's page and returning me the url link(s).
IMAGES: (1) start page screenshot
Image URL:
Assistant
type [5] [red Toyota] where [5] [INPUT] element with content
User
Last page
http::///offtto...cooommbaaaaa// http:///////dddd...pppaeeg-e phppp.ge..pp.................... IMAGES: (1) last page screenshot.
Image URL: haa.mng//pgggooooo//BBBooooooo
Now, it is your turn to evaluate the success/failure of the agent's execution so far. (... some content omitted)
And your goal to find the most convincing evidence why the agent is NOT on the right track to complete the task. (... some content omitted) Keep your response within 100 words.
Assistant
The agent has not successfully completed the task. The user's 's intent was to find the cheapest red Toyota priced between $3000 and $6000. The search results include vehicles that are outside the price range and have the wrong color (... some content omitted)
Table 14: Prompts used to generate opposing arguments for value estimation. image url is the base64 encoded SoM augmented web screenshot. Multimodal input in highlighted in orange. Gen- erated response is highlighted in blue. For brevity, we present prompts for trajectories with only one action executed so far.
26

---

Published as a conference paper at ICLR 2025
Role
Prompt
System
You are an autonomous intelligent agent tasked with navigating a web browser.
You will be given web-based tasks. These tasks will be accomplished through the use of specific actions you can issue.
Here's the information you'll have: (... some content omitted)
User
User Intent: Find me the cheapest red Toyota. It should be between $3000 to $6000. Finish the task by navigating to that item's page and returning me the url lin.(s).
IMAGES: (1) start page screenshot
Image URL:
Assistant
type [5] [red Toyota] where [5] [INPUT] element with content
User
Last page BURL_htpp/ccoffcecs..olommm / phagpaee..p.............
IMAGES: (1) last page screenshot.
Image URL: waw.iinggpnngaaeee..///ooooooo
Now, it is your turn to evaluate whether the agent's actions so far are success- fully aligned with the user's intent. (... some content omitted)
To better verify if user's intent is fulfilled correctly, you may find the following opinions helpful:
Reasons why the agent is NOT the right track:
The agent has not successfully completed the task. The user's intent was to find the cheapest red Toyota priced between $3000 and $6000. The search results include vehicles that are outside the price range and have the wrong color (... some content omitted)
Reasons why the agent is on the right track:
The agent has successfully navigated to the search results page for "red Toyota". Specifically, the "2007 Toyota Yaris" at $3000 and the "2007 Toyota Corolla" at $6500 are relevant. (...some content omitted)
Note that these opinions may or may NOT be correct. You should make your judgment based on the user's intent, the observations, and the agent's executed actions so far.
To make a final decision, choose one of the following status codes and provide your thought process.
STATUS CODES:
A. The agent's 's last action "'stop" and it contains the correct answer (...some
content omitted)
B. The agent is very close to finishing the task (...some content omitted)
C. The agent still needs few more actions (...some content omitted)
D. (..some content omitted)
E. (..s content omitted)
Assistant
Thoughts: The agent has successfully navigated to the results page for "red Toyota". However, it hasn't identified the cheapest (...some content omitted) STATUS CODE:
Table 15: Prompts used to generate the final judgement for value estimation, given opposing ar- guments highlighted in teal. image.url is the base64 encoded SoM augmented web screenshot. Multimodal input in highlighted in orange. Generated response is highlighted in blue. For brevity, we present prompts for trajectories with only one action executed so far.
27

---

Published as a conference paper at ICLR 2025
Prompts for Multi-Agent-Dbbaee We present the prompts to perform multi-agent-debate in Ta- ble 14 and Table 13] For simplicity, we present prompts to generate opposing arguments for value estimation Table 14] since prompts to generate supporting arguments is highly similar.
28


Reviews:
[{"review_id": "kCwVBVfreo", "reviewer": "Reviewer_Gidu", "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.\n\nR-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.\n\nExperiments 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.\nMoreover, 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.", "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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\nFigure 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?\n\nI 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.\n\nGiven 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. \n\nFor 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.\n\nI 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? \n\nLastly, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BIjcdLFOJE", "reviewer": "Reviewer_ddLD", "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.", "questions": "- Why not also fine-tune GPT-4o instead of the in-context contrastive reflection approach?\n- Does the proposed algorithm beat the baselines with equal compute? \n- What is the impact of the size of the reflection database on value accuracy?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "- Well-written and clearly presented paper\n- Strong motivation in improving VLM agents in long-horizon tasks\n- Novel contrastive reflection proposal that enables a VLM to in-context learn from errors in value estimation\n- Thorough ablations over two different value function constructions and individual components of the algorithm \n- 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]\n- 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.\n- Evaluation is limited to the VisualWebArena benchmark, focusing solely on web navigation tasks. Other VLM domains could include video games, etc.\n\nMinor: \n- Line 11: clarify what kind of autonomous agents, the authors clearly mean foundation model based rather than traditional RL\n- MCTS should be attributed to Coulom et al. 2006\n\n[1] Reflexion: Language Agents with Verbal Reinforcement Learning Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, Shunyu Yao.\n\n[2] Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Models Cong Lu, Shengran Hu, Jeff Clune.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qiBomg2JL4", "reviewer": "Reviewer_XTzE", "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.", "questions": "Why it is valid to\nself-generate data from an imperfect LLM,\nself-reflect with an imperfect LLM, and\nfine-tune an imperfect LLM from data generated by itself?\nIs this based on some sound principle?\nAlthough the algorithm may improve the performance, what is the drawbacks and limitations of a learning system trained with data not fully reliable?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Reflective Monte Carlo Tree Search (R-MCTS) for test-time exploration of decision space\nfine-tuning GPT-4o through self-learning", "weaknesses": "A fundamental issue is: \nGiven 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.\nIt is desirable or a must to collect reliable training data and feedback for a healthy learning system.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BX5xsM1ctG", "reviewer": "Reviewer_SSY4", "summary": "The paper presents a variation of MCTS that exploit the reasoning capabilities of VLMs and that can also be fine tuned.", "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?\n2. 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?\n2. 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.\n3. I wasn't able to understand what the values in Training column from Table 3 means, can you clarify?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Incorporating VLMs reasoning capabilities into MCTS is a novel idea with great potential.\n2. The proposed methodology has been extensively evaluated on a challenging benchmark and significantly outperforms the baselines.\n3. 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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)