Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents

## Abstract

Abstract Large Language Models (LLMs) have shown remarkable capabilities in natural language tasks requiring complex reasoning, yet their application in agentic, multi-step reasoning within interactive environments remains a difficult challenge. Traditional supervised pre-training on static datasets falls short in enabling autonomous agent capabilities needed to perform complex decision-making in dynamic settings like web navigation. Previous attempts to bridge this gap through supervised fine-tuning on curated expert demonstrations often suffer from compounding errors and limited exploration data, resulting in sub-optimal policy outcomes. To overcome these challenges, we propose a framework that combines guided Monte Carlo Tree Search (MCTS) search with a self-critique mechanism and iterative fine-tuning on agent interactions using an off-policy variant of the Direct Preference Optimization (DPO) algorithm. Our method allows LLM agents to learn effectively from both successful and unsuccessful trajectories, thereby improving their generalization in complex, multi-step reasoning tasks. We validate our approach in the WebShop environment, a simulated e-commerce platform—where it consistently outperforms behavior cloning and reinforced fine-tuning baseline, and beats average human performance when equipped with the capability to do online search. In real-world booking
scenarios, our methodology boosts Llama-3 70B model’s zero-shot performance from 18.6% to 81.7% success rate (a 340% relative increase ) after a single day of data collection and further to 95.4% with online search. We believe this represents a substantial leap forward in the capabilities of autonomous agents, paving the way for more sophisticated and reliable decision-making in real-world settings.

## 1 Introduction

Figure: Figure 1: We use Monte Carlo Tree Search (MCTS) to guide trajectory collection and iteratively improve model performance using direct preference optimization (DPO). We begin on the left by sampling a user query from the list of tasks in the dataset. We iteratively expand the search tree using UCB1 as a heuristic to balance exploration and exploitation of different actions. We store the accumulated reward obtained for each node in the tree, where in this image darker green indicates higher reward and darker red indicates lower reward. To construct the preference dataset, we compute a weighted score of the MCTS average Q-value and score generated by a feedback language model to construct contrastive pairs for DPO. The policy is optimized and can be iteratively improved.
Refer to caption: images/AgentTree2.png

The recent advances in Large Language Models (LLMs) represent a significant leap in artificial intelligence. Frontier models like ChatGPT (John Schulman et al., ), Gemini (Anil et al., ), Opus (Anthropic, ), and LLaMA-3 (Touvron et al., ) demonstrate promising reasoning capabilities that approach average human performance in a number of domains. These breakthroughs have extended the utility of LLMs from traditional chat and text-based applications to more dynamic, agentic roles, in which they do not just generate text but can take actions autonomously in a number of environments including code and software engineering (Holt et al., ; Zhang et al., ; Jimenez et al., ; Yang et al., ), device control (Wang et al., ; Zhang et al., ; Chen and Li, ) and web applications (Hong et al., ; Deng et al., ; Zhou et al., ; Lai et al., ; Gur et al., ) among others. However, despite these advancements, significant challenges persist: LLMs still struggle to generalize effectively in interactive, multi-step environments, since they are not native trained for such applications . This is true, even for some of the strongest models of the current generation, such as GPT-4 (Achiam et al., ).

A growing literature on agentic formulation seeks to address these issues; however these works mostly focus on building frameworks around prompt-based learning on existing models or limited fine-tuning on static datasets, and are thus limited by the base models’ reasoning and decision making capabilities.
Reasoning and planning have indeed been highlighted as core challenges for current LLMs. Since the seminal work on chain-of-thought reasoning (Wei et al., ), significant efforts have been made to improve these capabilities via prompt-based strategies (Kojima et al., ; Wang et al., ; Qiao et al., ; Yao et al., ). While successful, these approaches are still bounded by the base model’s performance. Another direction of research has explored fine-tuning approaches (Zelikman et al., ; Pang et al., ), and more recently combining them with inference-time search prompting (Yao et al., ) to produce fine-grained feedback. Concurrent works (Xie et al., ; Hwang et al., ; Zhang et al., ; Tian et al., ) utilize the traces produced by search algorithms and combine them with optimization approaches (Rafailov et al., ; Zelikman et al., ) to achieve significant boost in capabilities, especially in mathematics problem solving and code generation.

In this work we explore improving planning and reasoning capabilities of a web agent, which interacts with a real world website. Our goal is to design an approach that allows the agent to improve with autonomous experience and limited supervision. Indeed, prior works (Yao et al., ; Zhang et al., ; Masterman et al., ; Sumers et al., ) have shown strong reasoning to be critical for performance of autonomous agents, where challenges are even greater than during text generation, as the model needs to further understand how its actions affect its environment. Towards this goal, we introduce Agent Q—a novel approach that combines several key concepts in reasoning, search, self-critique and reinforcement learning. Our method takes inspiration from Sutton’s The Bitter Lesson on the power of general purpose methods that continue to scale with increased computation, showing the significant benefits of combining search and learning.

Inspired by the success of search-based methods in prior game-playing settings (Silver et al., ; Brown and Sandholm, ; Gray et al., ) and mathematical reasoning (Yao et al., ; Besta et al., ), we deploy a Monte Carlo Tree Search (MCTS) based search routine over web pages to guide agent exploration. Given the complexity of the environment, we use a base LLM for sampling possible rationales and web actions to explore. While this simple search-strategy shows a meaningful improvement in the success rate, it still struggles on long horizon tasks due to sparsity of environment rewards. Indeed even a small mistake across the trajectory can cause the final agent output to be wrong, creating significant credit assignment problems. To overcome this, we use AI feedback (Bai et al., ) and self-criticism (Yuan et al., ) to further prompt the LLM to provide self-evaluation feedback at each node, which serves as intermediate reward and helps guide the search steps. This meaningfully improves the final agent success rate, but requires significant online interactions and moreover the capability to rollback actions, which is not always possible in online realistic settings. Such online autonomous search with little supervision on the web can result in a weak or unsafe agent which can make many errors, resulting in risky behaviors in sensitive online settings like bank transfers and sensitive information sharing.

To correct this, we use the traces generated by the search process to improve capabilities of the model by learning from both the successful and unsuccessful trajectories with offline reinforcement learning, utilizing the Direct Preference Optimization (DPO) algorithm. We create preferences over different branches at the node level, which are scored using a mixture of the AI process feedback rewards and the final success rate of the explored branch.
We evaluate our approach on the simulated WebShop benchmark (Yao et al., )—a simulated e-commerce platform—as well as a real-world reservations booking website. We utilize LLaMa 3-70B as the base model in our experiments. In the WebShop environment, our approach consistently outperforms behavior cloning and reinforcement learning fine-tuned baselines, and beats average human
performance when equipped with the capability to do online search.

In our real-world booking experiments, using our Agent Q framework we improve the model zero-shot absolute success rate from 18.6% to 81.7% (a 340% relative increase), outperforming GPT-4’s performance after a single day of autonomous data collection. When we equip Agent Q with online search capability, our absolute success further improves to 95.4%. We believe that our approach represents a significant step forward in the development of autonomous web agents through it’s search and self-critique capabilities, setting a new benchmark for reliable multi-step decision-making in interactive settings.

## 2 Related Work

Our work touches on a large number of research directions around agent design, self-improvement, reasoning and reinforcement learning. We include a short overview of related works from those various fields below.

### 2.1 Guided Search for Reasoning and Planning

The latest generation of Large Language Models (LLMs) have demonstrated promising emerging properties around reasoning and planning. Moreover such behaviours can be directly elicited from strong models only using simple prompting techniques (Wei et al., ; Kojima et al., ; Qiao et al., ). These have also become an integral part of agentic design (Yao et al., ; Zhang et al., ), which we also utilize for our approach. Another emerging research direction is based around step-by-step verifiers or “Process Reward Models” (Uesato et al., ; Lightman et al., ), specifically for mathematical reasoning. These have shown to improve performance beyond purely outcome-based training, however they require a large amount of human effort to label individual steps. Some recent approaches have proposed self-supervised methods for step-level supervision (Hwang et al., ; Wang et al., ; Setlur et al., ). A number of concurrent works (Xie et al., ; Zhang et al., ; Tian et al., ) have further explored tree-based search approaches (Yao et al., ) in combination with DPO (Rafailov et al., ) training for math-based reasoning. These algorithms optimize actions at the node level, using different branches produced by the search algorithm to create preference pairs. Our approach shares similarities to the self-supervised search proposed in (Yao et al., ) with a combination of AI-based feedback (Bai et al., ; Yuan et al., ) to guide intermediate search steps, but we are the first to scale this a realistic agent setting. Similar approaches were proposed in (Zhou et al., ; Hao et al., ), and other works (Koh et al., ); however these works only use the base model’s zero-shot capability and do not train it further. Moreover they are only evaluated on simulated environments. Beyond the search stage, our work further adopts the training methodology of (Xie et al., ; Zhang et al., ; Tian et al., ), which significantly boosts our agent’s zero-shot capabilities.

### 2.2 Web Agents

The strength and capabilities of recent pretrained Large Language (Vision) Models LL(V)Ms has significantly boosted progress in developing autonomous web-agents. Improved code understanding and long context have allowed agents to represent environment state and action space with document object model (DOM) allowing for deployment in complex and realistic domains. Moreover strong reasoning (Yao et al., ) and planning (Liu et al., ; Zhang et al., ) capabilities have also led to the development of a number of promising agents (Zhang and Zhang, ; Hong et al., ; Zhou et al., ; Deng et al., ; Gur et al., ). Beyond using LL(V)Ms as plug-and-play planners/policies, recent works have sought to improve agentic-specific performance. Examples include online exploration (Zhang et al., ), planning (Zhang et al., ), error-correction (Wang et al., ), and self- (Wu et al., ) or AI-critique (He et al., ; Pan et al., ). However, with small exceptions (Nakano et al., ) (which is still limited in scope) these agents mostly provide a framework around a strong pre-existing model like GPT4-V or deploy limited fine-tuning and adaptation. In this work we show that model training is crucial for continuous improvement. We combine a planning and reasoning agent with MCTS inference-time search and AI self-critique for self-supervised data collection, which we then use for RL type training.

### 2.3 Reinforcement Learning for LLMs and Agents

Reinforcement Learning has become a significant component of training modern generative AI systems (Ouyang et al., ; Bai et al., ; Touvron et al., ). Classical approaches have deployed the PPO algorithm (Schulman et al., )—or similar policy-gradient based methods—and have even been scaled to autonomous web search agents (Nakano et al., ) as well as embodied applications with vision-language models (Zhai et al., ) (in simulation). However, these algorithms are challenging due to their complexity and the need for a high number of online samples from the model. This is especially prominent in potentially risky situations, such as autonomous agentic models that could make a number of impactful mistakes during training. Implicit Language Q-learning (Snell et al., ) and the Q-transformer (Chebotar et al., ) are offline RL algorithms (Levine et al., ) designed for auto-regressive transformer models, and hence can be safely trained on pre-collected datasets; however they have not been successfully scaled to modern LLMs. While these methods represent a token-level MDP, (Zhou et al., ) has shown success formulating the RL problem at a step level and these ideas have recently been scaled to a general device-control agent (Bai et al., ). However, these algorithms still have high complexity and require auxiliary models, such as value functions, so instead in our approach we opt to use the Direct Preference Optimization (DPO) algorithm (Rafailov et al., ) due to it’s simplicity and natural fit for the branching nature of tree-search based data.

## 3 Preliminaries

In this section we will outline the preliminaries of our agent training process.

### 3.1 Agent Formulation

Figure: Figure 2: We provide the following input format to the Agent, consisting of the system prompt, execution history, the current observation as a DOM representation, and the user query containing the goal. We divide our Agent output format into an overall step-by-step plan, thought, a command, and a status code.
Refer to caption: images/AgentFormat.png

We consider a general POMDP setup $(\mathcal{O},\mathcal{S},\mathcal{A},T,R,\mu_{0},\gamma)$ where $\mathcal{O}$ denotes the observation space, $\mathcal{S}$ the unobserved state space, $\mathcal{A}$ the action space, $T(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})$ the transition distribution (in this case the dynamics of a web browser), $R(\mathbf{s},\mathbf{a})$ the reward function (in this work we use sparse rewards of 1/0 representing success/failure), $\mu_{0}(\mathbf{s}_{0})$ the initial state distribution, and $\gamma$ the discount factor, which we set to 1. A POMDP is the most suitable framework to model web interactions for several reasons - first novel environments, which the agent is unfamiliar with require exploration in order to locate the task objective, consistent with the meta-reinforcement learning as task inference view Humplik et al. (). Moreover, the real web is dynamic, which creates partial observability of the current state each time the agent is deployed - i.e. it does not a priori know current booking availability before attempting to do it. We will outline the main parts of our web agent below.

The agent observation $\mathbf{o}_{t}\in\mathcal{O}$ are commands/information given by the user and the web browser. The first observation $\mathbf{o}_{1}$ is a user text instruction, such as

"Book reservation for restaurant Cecconi’s on OpenTable for 4 people on May 22 2024 at 7:00 PM"

for example and a browser home page. Subsequent observations consist of web pages from the browser, represented as a HTML DOM format. Occasionally for some tasks the agent might ask for confirmation/feedback from the user, which then also becomes part of the observation.

The agent actions $\mathbf{a}_{t}\in\mathcal{A}$ are composite, based on agent history $\mathbf{h}_{t}$. Our base approach is a ReAct agent Yao et al. () with a preliminary planning step (PlanReAct) Liu et al. () with few additional components.

- •
Planning For the first action after the initial observation we leverage the base LLM’s planning capabilities Huang et al. () and prompt the agent to generate a plan $\mathbf{a}_{1}^{\text{plan}}\sim\pi(\mathbf{a}_{1}^{\text{plan}}|\mathbf{h}_{1})$ of sequential steps to execute in language.
- •
Reasoning Subsequently all actions consist of a thought action $\mathbf{a}_{t}^{\text{tht}}\sim\pi(\mathbf{a}_{t}^{\text{tht}}|\mathbf{h}_{t})$, which is reasoning step Wei et al. ().
- •
Environment action Next we generate the browser interaction command $\mathbf{a}_{t}^{\text{env}}\sim\pi(\mathbf{a}_{t}^{\text{env}}|\mathbf{h}_{t},\mathbf{a}_{t}^{\text{tht}})$, which consists of a finite set of options like "CLICK [ELEMENT ID]", "SCROLL", "TYPE [CONTENT]" or "ASK USER [CONTENT]" etc.. This is the only part of the action generation, which interacts with the environment.
- •
Explanation action After the environment interaction action has been generated, we additional prompt the model for an explanation action $\mathbf{a}_{t}^{\text{expl}}\sim\pi(\mathbf{a}_{t}^{\text{expl}}|\mathbf{h}_{t},\mathbf{a}_{t}^{\text{tht}},\mathbf{a}_{t}^{\text{env}})$.

We denote the step action $\mathbf{a}_{t}$ as a tuple of plan, thought, environment and explanation actions for the first step and thought, environment and explanation actions for subsequent steps. When optimizing models we consider the joint likelihood

$$ $\displaystyle\log\pi(\mathbf{a}_{1}|\mathbf{h}_{1})=$ $\displaystyle\log\pi(\mathbf{a}_{1}^{\text{expl}}|\mathbf{h}_{1},\mathbf{a}_{1}^{\text{env}},\mathbf{a}_{1}^{\text{tht}},\mathbf{a}_{1}^{\text{plan}})+\log\pi(\mathbf{a}_{1}^{\text{env}}|\mathbf{h}_{1},\mathbf{a}_{1}^{\text{tht}},\mathbf{a}_{1}^{\text{plan}})+$ $\displaystyle\log\pi(\mathbf{a}^{\text{tht}}_{1}|\mathbf{h}_{1},\mathbf{a}^{\text{plan}}_{1})+\log\pi(\mathbf{a}^{\text{plan}}_{1}|\mathbf{h}_{1})$ (1) $$

for the initial action and

$$ $\log\pi(\mathbf{a}_{t}|\mathbf{h}_{t})=\log\pi(\mathbf{a}_{t}^{\text{expl}}|\mathbf{h}_{t},\mathbf{a}_{t}^{\text{env}},\mathbf{a}_{t}^{\text{tht}})+\log\pi(\mathbf{a}_{t}^{\text{env}}|\mathbf{h}_{t},\mathbf{a}_{t}^{\text{tht}})+\log\pi(\mathbf{a}^{\text{tht}}_{t}|\mathbf{h}_{t})$ $$

for subsequent actions, unlike some prior works Zhai et al. (), which down-weight the reasoning likelihood.

The agent state is the current state of the web, which may mot be observable. In this POMDP formulation we also need to build an agent memory component $\mathbf{h}_{t}$. Prior works have used the entire trajectory of observations and actions, however HTML DOMs can be hundred of thousands of tokens long. Moreover realistic web-tasks can require many more interactions than static benchmarks such as WebShop Yao et al. () and WebArena Zhou et al. (), which most prior works use. This makes it impractical to use full web trajectories due to limited context windows, potential out-of-distribution issues and practical inference speed and cost. Instead, we build the history representation of the agent as $\mathbf{h}_{t}=(\mathbf{a}_{1},\ldots,\mathbf{a}_{t-1},\mathbf{o}_{t})$. That is, the agent history consists of the actions generated so far and the current browser state. With some abuse of notation we will also refer to this as the agent state. Even though only the environment action is used for interacting with the browser, we construct the agent thought and explanation actions to act as a form of inner monologue Huang et al. () and adequately represent its state and intentions. This allows us to use a significantly more compact history representation. We should note that, while only the environment action affects the browser state, the planning, reasoning and explanation components affect subsequent decisions due to conditioning. Because of this reason, when we optimize the agent, we compute likelihoods over the composite action.

### 3.2 Fine-Tuning Language Models From Feedback

Classical approaches to RLHF in foundation models Stiennon et al. (); Ouyang et al. () use the model as a policy $\pi_{\theta}$ and optimize an objective of the form:

$$ $\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:standard_rl}}{e}q:standard_{r}l}\mathbb{E}_{\mathbf{a}\sim\pi_{\theta}(\mathbf{a}|\mathbf{h})}[r(\mathbf{a},\mathbf{h})]-\beta\mathbb{D}_{KL}[\pi_{\theta}(\mathbf{a}|\mathbf{h})||\pi_{\text{ref}}(\mathbf{a}|\mathbf{h})]$ (2) $$

where $\pi_{\text{ref}}$ is some reference policy (usually the initial model). The goal of this formulation is to optimize some target objective (expressed by the reward $r(\mathbf{a},\mathbf{h})$) while preventing out-of-distribution drift. This objective can be extended to multi-step agentic problems, where the model interacts with an external environment env such as in Nakano et al. () which focuses on information retrieval using web navigation. In this case we use an objective of the kind

$$ $\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:multi_step_rl}}{e}q:multi_{s}tep_{r}l}\mathbb{E}_{\pi_{\theta},\text{env}}\left[\sum_{t}r(\mathbf{a}_{t},\mathbf{h}_{t})]-\beta\mathbb{D}_{KL}[\pi_{\theta}(\mathbf{a}_{t})|\mathbf{h}_{t})||\pi_{\text{ref}}(\mathbf{a}_{t}|\mathbf{h}_{t})]\right]$ (3) $$

Classical RLHF has used policy gradient type of algorithms, such as PPO Schulman et al. (), however, they are complex and require online data, which can be costly/dangerous to collect autonomously in the agent setting. While PPO has shown some success in prior web agent applications Nakano et al. (). The issues above largely make the approach not practical for general web tasks, beyond information retrieval. In this work we utilize some recent alternatives, outlined below.

#### 3.2.1 Reinforced Fine-Tuning

Reinforced fine-tuning (RFT) algorithms Zelikman et al. (); Gulcehre et al. (); Yuan et al. (); Singh et al. () have grown in popularity due to their simplicity and scalability. These methods aggregate data and filter out the sub-optimal samples based on some reward model or a verifier to construct a growing dataset of high-quality trajectories $\mathcal{D}$. Given this dataset and a parameterized model $\pi_{\theta}$ we can carry out standard supervised fine-tuning (SFT):

$$ $\mathcal{L}(\pi_{\theta},\mathcal{D})=-\mathbb{E}_{\mathcal{D}}\left[\sum_{t=1}^{T}\log\pi_{\theta}(\mathbf{a}_{t}|\mathbf{h}_{t})\right]$ (4) $$

In this objective the divergence penalty is only applied implicitly by limiting the number of training rounds. While simple and relatively successful, empirically these methods tend to under-perform standard RL and alternatives Dubois et al. (); Tajwar et al. (); Setlur et al. () in the text generation domain, particularly in reasoning. We largely observe similar empirical results, and we use these methods mostly as baselines to build intuition.

#### 3.2.2 Direct Preference Optimization

Direct Preference Optimization (DPO) Rafailov et al. () is an offline RL Levine et al. () alternative to the classical RLHF optimization pipeline. It is a suitable algorithm for agent fine-tuning, as it can use fully offline data and does not require online rollouts. The original formulation in the pure text generation setting considers feedback of pairwise comparisons $(\mathbf{h},\mathbf{a}^{w},\mathbf{a}^{l})$, where $\mathbf{s}$ is a single prompt and $\mathbf{a}^{w}$ and $\mathbf{a}^{l}$ are two responses with $\mathbf{a}^{w}\succ\mathbf{a}^{l}$ indicating that $\mathbf{a}^{w}$ is preferred over $\mathbf{a}^{l}$. The DPO objective then minimizes the following loss:

$$ $\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:step_DPO}}{e}q:step_{D}PO}\mathcal{L}_{\text{DPO}}(\pi_{\theta};\mathcal{D})=-\mathbb{E}_{(\mathbf{h},\mathbf{a}^{w},\mathbf{a}^{l})\sim\mathcal{D}}\left[\log\sigma\left(\left(\beta\log\frac{\pi_{\theta}(\mathbf{a}^{w}|\mathbf{h}^{w})}{\pi_{\text{ref}}(\mathbf{a}^{w}|\mathbf{h}^{w})}\right)-\left(\beta\log\frac{\pi_{\theta}(\mathbf{a}^{l}|\mathbf{h}^{l})}{\pi_{\text{ref}}(\mathbf{a}^{l}|\mathbf{h}^{l})}\right)\right)\right]$ (5) $$

While the algorithm was developed in a bandit setting Hejna et al. (); Rafailov et al. () have extended it to multi-turn settings with preferences over over trajectories. In our setting, we can directly utilize this objective as:

$$ $\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:trajectory_DPO}}{e}q:trajectory_{D}PO}\mathcal{L}_{\text{T-DPO}}(\pi_{\theta};\mathcal{D})=-\mathbb{E}_{(\tau_{w},\tau_{l})\sim\mathcal{D}}\left[\log\sigma\left(\left(\sum_{t=0}^{|\tau^{w}|}\beta\log\frac{\pi_{\theta}(\mathbf{a}_{t}^{w}|\mathbf{h}_{t}^{w})}{\pi_{\text{ref}}(\mathbf{a}_{t}^{w}|\mathbf{h}_{t}^{w})}\right)-\left(\sum_{t=0}^{|\tau^{l}|}\beta\log\frac{\pi_{\theta}(\mathbf{a}_{t}^{l}|\mathbf{h}_{t}^{l})}{\pi_{\text{ref}}(\mathbf{a}_{t}^{l}|\mathbf{h}_{t}^{l})}\right)\right)\right]$ (6) $$

One bottleneck for the practical deployment of the algorithm is the need for a reference model $\pi_{\text{ref}}$ during optimization, which requires more computational resources. Instead in our settings, we slightly modify the algorithm using an off-policy replay buffer, which aggregates trajectory data, as well as likelihoods of the generated actions. During the optimization step, we sample tuples of trajectories and the corresponding likelihoods under the data generation (reference) density, which eliminates the need for a separate reference model.

## 4 Preliminary Approach With Outcome Supervision

Figure: Figure 3: Success rate of different approaches on the WebShop Yao et al. () task. All models are based on xLAM-v0.1-r Zhang et al. (). RFT and DPO over xLAM-v0.1-r demonstrate improvements in performance from 28.6% to 31.3% and 37.5% respectively. However, these methods still lag behind average human performance of 50.0%. Our approach, Agent Q + MCTS achieves a significant gain (76.57% relative improvement) over the base model, outperforming average human performance on WebShop with a success rate of 50.5%.
Refer to caption: images/WebShopPreliminaryResultsPassFinalBold.png

In this section we will outline preliminary experimental results, which will build the base understanding for our further experiments. We use the AgentOhana xLAM-v0.1-r model Zhang et al. (), which is a fine-tune of a pre-trained Mixtral-8x7B-Instruct-v0.1 model Jiang et al. () on a mix of agentic applications, including WebShop SFT data. We also incorporate the same agent configuration (^1^11https://github.com/SalesforceAIResearch/xLAM) specified by the AgentLite Liu et al. () work to ensure a fair comparison between our fine-tuned model and the xLAM base model performance. We evaluate all approaches on the WebShop environment Yao et al. (), where the agent needs to find particular products by browsing a simulated web shop. The environment comes with a set of 12,087 pre-defined tasks (corresponding to specific products to find), which we split into a train set of 11,000 tasks, which we use for further agent fine-tuning and a set of 1,087 held-out tasks, which we use for zero-shot evaluation.
We show success rates (exact product match) for different approaches in Fig. 3. The base xLAM-v0.1-r model achieves success rate of 28.6% on the test tasks. All other methods are based on outcome-based supervision only, depending on whether a particular attempt was successful or not. We see that further RFT training, using a STaR-like algorithm Zelikman et al. () on the trajectory level, as outlined in Sec. 3.2.1, achieves success rate of 31.3%, which is a small improvements of 2.7% over the initial model. This is not surprising since the base model is already trained as an agent on the environment with supervised fine-tuning on demonstrations. Our next experiment fine-tunes the base model using the trajectory-level DPO algorithm, as outlined in Eq. 6 in Sec. 3.2.2 using successful trajectories as preferred over failed ones. This approach also uses only outcome-level supervision, but unlike the RFT baseline can utilize failed trajectories as well, which improves the agent performance by 9.3% over RFT agent to 40.6% success rate. We also evaluate this model with beam search for the action generation, which can be considered a form of planning the horizon of a single environment action (which still consists of multiple simple actions) Rafailov et al. (), but it only yields marginal improvement over the base model. These findings match results on reasoning for math problems Pang et al. () and some recent approaches that also apply DPO to agent applications Song et al. (); Xi et al. ().

Despite the additional reinforcement learning training, our agents are still not able to match the average human performance on this environment. We identify that one of the core failure modes of the DPO policy is that it executes a greedy search when looking for matches to the product query. For example, for every search query, the WebShop environment yields a number of pages of results. However, we find that the model nearly always greedily searches for the best matching item in the first page of results rather than using the "[NEXT]" and "[PREV]" buttons to navigate between pages, essentially deploying a weak exploration strategy.

## 5 Agent Search

As we discovered in the previous section, while training based on outcome supervision with DPO yields meaningful improvement, the model is still not able to match human performance due to it’s limited exploration. In this section we will explore endowing the agent with additional search capability via MCTS.

### 5.1 Monte-Carlo Tree Search Over Web-Pages

The Monte Carlo Tree Search (MCTS) algorithm Kocsis and Szepesvári () employed in this work follows closely the one in Hao et al. () and consists of four phases: selection, expansion, simulation, and backpropagation. Each phase plays a critical role in balancing exploration and exploitation while iteratively refining the policy.

We formulate the web agent execution as tree search over web-pages. The state is represented as described in Section 3.1 and consist of the summary of the agent’s history and the DOM tree of the current web-page. Unlike board games, such as Chess or Go Silver et al. () the complex web-agent action space we use is open-format and variable. Instead we will use the base model as an action-proposal distribution and sample a fixed amount of possible actions at each node (web-page). Once we select and execute an action in the browser we traverse the next web-page, which together with the updated history becomes the new node.

#### 5.1.1 Action Selection With AI Process Supervision

Figure: Figure 4: The policy proposes K actions at every step during inference time search. The critic, also initialized as the same base LLM model used by the policy, ranks the actions proposed by the policy. This ranking is used to guide node selection after expansion and used to construct preference pairs during policy training.
Refer to caption: images/process_supervision.png

The selection phase uses the Upper Confidence Bound (UCB1) formulation of MCTS also used by Hao et al. () to select nodes which aims to balance exploration and exploitation. With some abuse of notation we will also denote the agent state with $\mathbf{h}_{t}$. We consider the value function $Q(\mathbf{h}_{t},\mathbf{a})$ which represents the estimated value (chance of success) represents the estimated value of taking action $\mathbf{a}$ in the state $\mathbf{h}_{t}$. At each new node $\mathbf{h}_{t}$ we sample $K$ proposal actions from the base model $\mathbf{a}_{t}^{1},\ldots,\mathbf{a}_{t}^{K}$. We initialize all values $Q(\mathbf{h}_{t},\mathbf{a}_{t}^{i}),i=1,\ldots,K$ to zero. The web-based environment does not provide intermediate rewards to guide the search, so we incorporate AI-based critique to provide process supervision at the step level to guide the exploration process. We use the base model to produce a feedback score for each action by asking it to rank the generated actions by its perceived utility in helping the agent complete the user task.

We query the feedback model for multiple iterations, each time removing the best action selected from the previous iteration from the list, until we have a full ranking of all actions. The full AI feedback process is demonstrated in Figure 4. After the initial selection, we select the actions to explore based on the standard MCTS UCB1 formulation:

$$ $\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:mcts_ucb}}{e}q:mcts_{u}cb}\mathbf{a}_{t}^{*}=\arg\max_{\mathbf{a}_{t}^{1},\ldots,\mathbf{a}_{t}^{K}}\left[Q(\mathbf{h}_{t},\mathbf{a})+c_{\text{exp}}\cdot\sqrt{\frac{\log N(\mathbf{h}_{t})}{1+N(\mathbf{h}_{t+1})}}\right],$ (7) $$

where $N(\mathbf{h}_{t})$ is the visitation frequency of state $\mathbf{h}_{t}$, and $c_{\text{exp}}$ is an exploration constant. For each rollout added to the tree, we start at the root node and follow the child states that maximize the UCB1 score until we reach a leaf node. This process is repeated for each tree/prompt in the batch.

#### 5.1.2 Expansion and Backtracking

Based on the preceding section, we select and execute an action in the browser environment to reach a new node (page). Beginning from the selected state node’s trace, we roll out the trajectory using the current policy $\pi_{\theta}$ until a terminal state is reached. The environment returns a reward at the end of the trajectory, $R$, where $R=1$ if the agent was successful and $R=0$ otherwise. We then backpropagate this reward by updating the values of each node bottom up from the leaf node to the root as follows:

$$ $\displaystyle Q(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$ $\displaystyle\leftarrow\frac{Q(\mathbf{h}_{t},\mathbf{a}_{t}^{i})N(\mathbf{h}_{t},\mathbf{a}_{t}^{i})+R}{N(\mathbf{h}_{t},\mathbf{a}_{t}^{i})+1}$ (8) $\displaystyle N(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$ $\displaystyle\leftarrow N(\mathbf{h}_{t},\mathbf{a}_{t}^{i})+1$ $$

Each state node tracks two values: $Q(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$, the average reward for passing through state $\mathbf{h}_{t}$ and choosing action $\mathbf{a}_{t}^{i}$, and $N(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$, the number of times this state action pair was visited during search (and $N(\mathbf{h}_{t})=\sum_{i=1}^{K}N(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$). The backpropogation updates correctly maintain these values.

### 5.2 Improving Zero-Shot Performance with Reinforcement Learning

Figure: Algorithm 1 MCTS Guided Direct Preference Optimization

Training large foundation models with offline Snell et al. () or off-policy Chebotar et al. () reinforcement learning at scale has still remained challenging. At the same time online (on-policy) reinforcement learning Stiennon et al. (); Ouyang et al. () is not scalable to real interactive environments. Instead, we follow a line of recent works, which apply the DPO algorithm Rafailov et al. (, ) at the step level in multi-step reasoning problems in mathematical domains Xie et al. (); Hwang et al. (); Chen et al. (); Lai et al. (); Lu et al. (); Setlur et al. (); Zhang et al. (). Our approach is most similar to Xie et al. (); Chen et al. (); Zhang et al. () who also use the branching nature of tree search to produce step-level preference pairs. We will also use this approach in our setting due to its simplicity, scalability and prior success in smaller scale (non-interactive) reasoning applications.

We will generate a dataset of preference pairs $\mathcal{P}=\{\mathbf{h}_{t},\mathbf{a}_{t}^{w},\mathbf{a}_{t}^{l}\}$ where we make sure both actions were explored. We then optimize the DPO objective in Eq. 5 on the node level. We will leverage a theoretical result below to guide the construction of these preferences. We can make a number of modifications to Theorem 6.1 from Setlur et al. () to incorporate the interactive nature of the web environment dynamics to obtain the following result:

###### Theorem 1 .

Consider a policy that optimizes the objective in Eq. 3 on trajectories generated by $\pi_{\text{ref}}$ and that at each node $\mathbf{h}_{t}$ we have preferences generated accordingly to $p(\mathbf{a}_{t}^{w}\succ\mathbf{a}_{t}^{l}|\mathbf{h}_{t})\propto\sigma(Q(\mathbf{h}_{t},\mathbf{a}_{t}^{w})-Q(\mathbf{h}_{t},\mathbf{a}_{t}^{l}))$, then the policy which optimizes the DPO objective in Eq. 5 is identical to the optimal RL policy

$$ $\pi^{*}(\mathbf{a}|\mathbf{h}_{t})\propto\pi_{\text{ref}}(\mathbf{a}|\mathbf{h}_{t})\exp\left(Q(\mathbf{h}_{t},\mathbf{a})/\beta\right)$ (9) $$

###### Proof.

The proof follows directly from the proof of Theorem 6.1 in Setlur et al. () and the control as inference arguments in Rafailov et al. (); Levine ().
∎

That is, we can approximate the optimal RL policy if we generate preferences under the optimal value function (or an approximation thereof). Since the outcome success provides limited supervision we also incorporate process supervision through the AI feedback as outlined in Section 5.1.1. We interpret the ranking of possible actions by the model to be driven by an implicit value function. Similar semantics was used in Koh et al. (), where GPT-4 was used as a zero-shot value function, while here we ask the model to instead reason over the given potential actions and provide rankings instead. This self-rewarding approach has shown promise in the RLHF setting Yuan et al. () and we utilize it for our agent setting as well. Under this formulation, we compute the state-action value as an average:

$$ $\addcontentsline{lla}{section}{\numberline{\string\crtrefnumber{eq:mixQ}}{e}q:mixQ}Q(\mathbf{h}_{t},\mathbf{a}_{t}^{i})=\alpha\tilde{Q}(\mathbf{h}_{t},\mathbf{a}_{t}^{i})+(1-\alpha)\hat{Q}(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$ (10) $$

where $\tilde{Q}(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$ is the empirical value estimated through MCTS backpropagation and $\hat{Q}(\mathbf{h}_{t},\mathbf{a}_{t}^{i})$ is a value estimate based on the ranking of the action $\mathbf{a}_{t}^{i}$ by the process supervision AI model. We then create preferences over pairs of actions which are above a certain value threshold $|Q(\mathbf{h}_{t},\mathbf{a}_{t}^{w})-Q(\mathbf{h}_{t},\mathbf{a}_{t}^{l})|\geq\theta_{\text{threshold}}$. The full outline of our RL approach is shown in Algorithm 1.

###### Theorem 1 .

###### Proof.

### 5.3 Full WebShop Results

The full range of results and baselines is shown in Figure 3. We see that equipping the agent with search capabilities at test time significantly boost success rates from 28.6% to 48.4% when using MCTS on top of the base xLAM-v0.1-r model, approaching close to the average human performance of 50.0% and significantly out-performing the zero-shot performance of the DPO model trained with outcome supervision. We further fine-tune the base model using the approach outlined in Algorithm 1, which yields an improvement of 0.9% over the base DPO model. Using MCTS on top of the trained Agent Q model further improves performance to 50.5% slightly out-performing the average human success rates. We find that the ability to search at test time is a significant paradigm shift from zero-shot agents, even with significant RL training. Furthermore, while dense-level supervision improves over purely outcome-based one, the improvement is modest on WebShop. This is because the environment requires relatively short trajectories, and the model is capable to learn credit assignment purely from outcome supervision. We will further explore more complex real world environment, which requires longer-range credit assignment.

## 6 Scaling To Real World Websites

In this section we will investigate scaling the Agent Q framework to real use cases on live websites, in particular bookings on OpenTable. We carried out initial experiments with the xLAM-v0.1-r model, which proved to weak for the task achieving an initial success rate of 0.0%. Instead we shifted to the LLaMa 70B Instruct model, which was able to achive some non-trivial initial success.

### 6.1 The OpenTable Environment

Figure: Figure 5: At the end of a trajectory, a GPT-4-V evaluator is called to provide feedback on the agent’s performance given the final observation and action history to determine the success score. The model is prompted with a condensed execution history of the trajectory and the screenshot of the final state. The success metric is a binary 0/1 value.
Refer to caption: images/outocme_supervision.png

In OpenTable, the agent is tasked with booking a restaurant reservation for a user. The agent must find a restaurant page on the OpenTable site, look for a reservation at a certain date and time, choose seating options that align with a user’s preference and submit the user contact information to complete the task successfully. Since OpenTable is a live environment and is difficult to programatically measure metrics for, we use a language model, GPT-4-V to collect rewards for each trajectory, based on the following metrics: (1) date and time set correctly, (2) party size set correctly, (3) user information entered correctly, and (4) clicked complete reservation. The task is marked as completed if each of the above constraints are satisfied. The outcome supervision setup is shown in Figure 5. We experimented with using LLaMa 70B for outcome supervision as well, but discovered that vision capabilities significantly improve the success classification accuracy (as measured by human validation). At the time of writing no open source vision-language model of sufficient capability was available, hence we opted to use GPT-4-V. We believe that as more open-source multi-modal models become available we can switch to a fully self-supervised pipeline.

To generate queries for the OpenTable benchmark dataset, we programatically generate a diverse set of user queries by combining the restaurant name, desired date and time, and user information.

Navigating on live websites pose a wide variety of challenges. For example, consider that the user specifies a restaurant in a different city than the location the browser is initialized in, the model will have to take extra steps to find the restaurant. Further, if the exact user requested date and time are not available, the model may have to choose the closest available reservation slot. Lastly, if there are preferences, such as indoor or outdoor seating options that the model is presented with, the desired behavior is to interact with the user to determine the best course of action. OpenTable presents a complex set of challenges for web navigation agents; the number of steps required to complete the task is on average 13.9 steps, over double the average number of steps for Webshop, 6.8.

Figure: Figure 6: Success rate of different approaches on OpenTable. All models unless otherwise stated are based on LLaMA-3-70B-Instruct Touvron et al. (). Using DPO and RFT with MCTS further improves performance from 18.6% to 71.8% and 84.3% respectively. We show that Agent Q in itself achieves 81.7% and Agent Q + MCTS significantly outperforms all other techniques, with a performance of 95.4% on OpenTable.
Refer to caption: images/open_table_sr_final_bold.png

For the observation space for this environment, we design an intermediate state representation that crawls the raw HTML content of a website to retrieve relevant visual components, and highlight interactive elements to the model. The agent is allowed the actions, "CLICK [ID]", "GOTO [URL]", "TYPE [ID] [TEXT]", "SUBMIT [ID]", "CLEAR [ID]", "SCROLL [UP/DOWN]", and "ASK USER HELP". For OpenTable experiments, we use the LLaMA-3-70B-Instruct model as the initial policy. We find that the superior reasoning abilities of this class of model is required for effective task completion, which is necessary to produce the diverse success and failure trajectories required to effectively improve the policy.

### 6.2 Results On OpenTable

The base xLAM-v0.1-r model achieves a success rate of 0.0%, largely from failing to follow instructions for the general web navigation instructions used for live websites, contrary to the simplified observation and action space used in WebShop. We instead initialize the base policy with the LLaMa-3 70B Instruct model, which achieves a zero-shot success rate of 18.6%. We do a single round of RFT on 600 successful trajectories which improves the success rate to 67.2% already out-performing the the GPT-4o model zero-shot performance with a success rate of 62.6%. For all other baselines we adopt the RFT model as the reference policy, due to the relatively low success rate of original LLaMa 3 70B Instruct model.

In this environment, training with outcome-supervision only DPO further improves performance by 4.6% to 71.8% but significantly under-performs the full Agent Q pipeline which achieves a zero-shot success rate of 81.7% We hypothesizes that this is due to the fact that OpenTable is a significantly more challenging environment, which requires almost twice as many steps to complete as WebShop, so the agent benefits from fine-grained supervision and credit assignment. We further ablate the role of the intermediate AI feedback process supervision during training as outlined in Eq. 10 and use MCTS with online Q values computed from outcome rewards only. This setting still outperforms training with trajectory-level DPO (75.2% versus 71.8%) likely due to the more fine-grained credit assignment that the branching tree search provides to the agent. However, zero-shot performance is still meaningfully worse than using intermediate process-level supervision and the full Agent Q achieves 6.5% higher success rate at 81.7%.

Similar to the WebShop experiment we see a step level increase in capability from allowing the model to search at inference time, with the base RFT model achieving 84.3% success with MCTS, outperforming the Agent Q zero-shot performance of 81.7% success. However, if we carry out additional MCTS search using the Agent Q model as the base policy we achieve a significant 95.4% success rate.

## 7 Discussion

In this work we developed algorithms for autonomous improvement of web-agents with limited human supervision. While most prior works build frameworks around existing models without additional training, we specifically seek to fine-tune pre-trained models for web navigation tasks based on synthetic reasoning and search data. While we achieve significant improvement in model capabilities on our target domain, many research questions remain.

Design of reasoning algorithms. The core challenge for our web agents is the weak reasoning capabilities, which limit the agent’s exploration and search strategy. In our approach we used process-level supervision from a separate critic model, which we prompt to rank possible agent actions. This is in contrast to works in mathematical reasoning where PRMs are usually trained to classify the correctness of individual steps Lightman et al. (), while other agent works Koh et al. () have prompted models as zero-shot value functions. Furthermore, while we spent significant effort in training the agent policy, we maintain a frozen critic, which would likely also benefit from additional fine-tuning. We defer exploration of these design choices to further work.

Choice of search algorithm. We used MCTS search due to the approach’s prior success in mathematical and code reasoning tasks. However, agent models executing MCTS on live environments might require significant number of risky interactions and a different search strategy might be more suitable. Recent works such as Lehnert et al. (); Gandhi et al. () have even suggested directly learning to optimally search and explore in reasoning tasks using meta-reinforcement learning. We believe this is a promising research direction for autonomous agents, which we will pursue in further work.

Discrepancy between zero-shot vs search results. Similar to some recent works that focus on code and reasoning, we observe significant gap between zero-shot agent performance and performance of the agent equipped with search capabilities Snell et al. (); Brown et al. (). Investigating these trade-offs at scale and the potential effect of different search/optimization approaches.

Online safety and interaction. The design of agent Q allows for largely autonomous exploration, self-evaluation and improvement with limited human intervention. However, the agent might make a significant number of mistakes in it’s search process which might be difficult to fix/reverse, especially for safety-critical online transactions, such as communications/email, payments, filings etc. This limits the scope of websites that Agent Q can be safely deployed and we might require additional safety critics and human-in-the-loop training setups.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 1
questions: Besides the weaknesses above, further questions are as follows:

- "RFT and DPO over xLAM-v0.1-r demonstrate improvements in performance from 28.6% to 31.3% and 37.5% respectively." However, 37.5% is the result of GPT-4 in Figure 1, not DPO. So what are the correct results of GPT-4 and DPO?
- "We use the base model to produce a feedback score for each action by asking it to rank the generated actions by its perceived utility in helping the agent complete the user task." Can the authors provide more details on how the feedback score is generated?
- How does the number of iterations in Agent Q affect the performance? Are there any ablation studies on this?
- How does the computational complexity of Agent Q compare to the baseline methods?
soundness: 2
strengths: - The paper proposes a method for online fine-tuning a web navigation agent and the empirical results show that the proposed method outperforms the baseline methods.
- The paper evaluates Agent Q on both simulated and real-world tasks, demonstrating its effectiveness in various scenarios.
summary: The paper proposes Agent Q, an online fine-tuning framework for enhancing reasoning capabilities in autonomous AI agents for web navigation tasks. Agent Q combines DPO, MCTS, and process supervision to improve the agent's performance. The experimental results show that Agent Q outperforms the baselines on two benchmark tasks, highlighting its potential for real-world applications.
weaknesses: - The idea is not novel enough since Agent Q uses a combination of DPO, MCTS, and process supervision for web navigation task.
- Lack of experimental details, such as hyperparameters, and the significance of the results. Also, the code is not provided.
- Lack of ablation studies to analyze the effects of number of iterations in Agent Q.

Format and writing issues:

- The paper cites papers using wrong LaTeX commands. For example, "(Zhou et al., 2024c) has shown success
formulating the RL problem at a step level" should be changed into "Zhou et al. (2024c) has shown success
formulating the RL problem at a step level" by using the `\citet` command. "Classical RLHF has used policy gradient type of algorithms, such as PPO Schulman et al. (2017), ... " should be changed into "Classical RLHF has used policy gradient type of algorithms, such as PPO (Schulman et al., 2017), ... " by using the `\citep` command. I strongly recommend the authors to use the correct LaTeX commands for citations.
- "will produce actions $\mathbf{a}_t \sim \pi \mathbf{a} | \mathbf{h}_t)$" should be "will produce actions $\mathbf{a}_t \sim \pi(\mathbf{a} | \mathbf{h}_t)$". The same issue in Eq. (2).
- Inconsistent equation referencing: In Algorithm 1, the equation is referenced as (9) and Eq. (4), but in the text, it is referenced as Eq. 2. The same issue for figures. There are "Figure 1" and "Fig. 1" in the text. I recommend the authors to check the consistency of the referencing.
- Replicated references in the paper, such as "Appagent: Multimodal agents as smartphone users", "Chain of preference optimization: Improving chain-of-thought reasoning in llms".
- "In this environment, training with outcome-supervision only DPO further improves performance by 4.6% to 71.8% but significantly under-performs the full Agent Q pipeline which achieves a zero-shot success rate of 81.7%" does not have a period at the end of the sentence. I recommend the authors to check the punctuation of the sentences in the paper.

---

confidence: 4
contribution: 1
initial_rating: 5
presentation: 3
questions: Please check out the weaknesses section.
soundness: 2
strengths: - The proposed approach is mostly sound (except for the open-loop planning component). MCTS can be an effective method for gathering trajectory data for agent training, and preference-based learning could be useful in web agent training scenarios.
- Overall, the manuscript is clear and easy to follow. The figures are made well for fair overviews. The writing is clear in general.
summary: The authors introduce an approach to train web agents, named *Agent Q*. It generates training data with MCTS over web pages and performs preference-based learning (DPO) over probable actions in each web page. As they assume sparse, trajectory-level success-or-failure feedbacks from the environment, the LLM-based critic is employed to generate such step-level feedback. The authors perform evaluation of the proposed approach on one existing benchmark, WebShop, and their own benchmark on OpenTable, and they demonstrate that their approach outperforms the employed baseline methods.
weaknesses: - The proposed approach generates a plan at the beginning of each trajectory, which seems to stay frozen for the rest. This open-loop planning can be a bottleneck for improving agents' capabilities in more general, complex scenarios.
- Despite the expressions such as "real-world booking scenarios" (Abstract) and "Scaling To Real World Websites" (Section 6), the proposed OpenTable experiment doesn't seem ideal for testing the proposed approach's "real-world" capabilities. The set of tasks are generated "by combining the restaurant name, desired date and time, and user information" (L1061), and the evaluation is done based on "(1) date and time set correctly, (2) party size set correctly, (3) user information entered correctly, and (4) clicked complete reservation" (L1053). These imply that the training and test tasks (and thus correct trajectories) all share similar structures with the same set of constraints, and it can make it hard to assess the generalization capabilities of the approach, which is an important part of being "real-world." Besides, the proposed approach uses a frozen plan for each trajectory, which can be a suitable design for OpenTable but not for most of real-world websites and scenarios.
- According to the WebShop results, the advantage of the proposed approach, especially over the trajectory-level DPO baseline doesn't seem very clear to me (40.6% vs 41.5% from Figure 1).
- Combining MCTS, self-evaluation, and step-level preference learning for training has already been explored in prior work (e.g., Xie et al., 2024, as mentioned in this submission).

---

confidence: 5
contribution: 2
initial_rating: 5
presentation: 2
questions: The authors state that the agent trained by DPO behaves greedily (Line 288). Does the step-level DPO address this issue?

Utilizing planning actions could deteriorate performance[1]. Did the authors observe similar outcomes?

How is the ranking of responses transferred to $\hat Q$?

How are the success rates of Human (average) and Human (expert) shown in Figure 1 obtained?

Which correspond to the explanation action in Figure 4?

References:
[1] Liu Z, Yao W, Zhang J, et al. Bolaa: Benchmarking and orchestrating llm-augmented autonomous agents[J]. arXiv preprint arXiv:2308.05960, 2023.
soundness: 4
strengths: The proposed method is successfully applied to the real-world booking scenario and achieve a $95.4\%$ success rate after a single day of data collection.
summary: This paper introduces AgentQ, an approach to enhance the capabilities of LLM agents in executing complex, multi-step planning and reasoning tasks within interactive environments. The integration of Monte Carlo Tree Search (MCTS) and iterative fine-tuning using step-level Direct Preference Optimization (DPO) has been demonstrated to be effective in LLM reasoning tasks. The authors apply the approach to both a simulated e-commerce task and the real-world booking scenario, incorporating several agent-related components. Empirical results demonstrate that AgentQ shows significant improvements over baseline methods and even surpassing average human performance under certain conditions.
weaknesses: The experimental section is incomplete. The ablation study is entirely missing, providing no concrete indications of the strength of each component or design choice, such as the self-critique mechanism, the four types of actions, the effects of training sample sizes, and the weighted coefficient $\alpha$. While I understand the challenges of conducting experiments in real scenarios, ablations in the WebShop context are essential to validate the method's effectiveness. Furthermore, there is no analysis of the generated trajectories, nor are there case studies demonstrating the proposed method's efficacy.

The success rate of AgentQ+MCTS remains significantly lower than that of human experts. The authors attribute this discrepancy to short trajectories. More advanced LLMs should be evaluated to support this conclusion, such as LLaMA-3-70B-Instruct used in the booking scenario.

Many critical descriptions of the methods are lacking; please refer to the questions section.

Several important hyperparameters, such as $\theta_{threshold}$, are not listed.

The definition of $\tau$ in Equation 5 is missing.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 1
questions: See comments above.

In general, I would like to show my support for this project. It is a good one. However, the paper should be rewritten to get accepted.

I'm happy to raise my score after seeing the revised version.
soundness: 2
strengths: 1. The final web agent presented in this paper achieves state-of-the-art performances in particularly challenging environments. The result, I believe, is impressive.

2. The idea of combining search and RL to improve LLM's reasoning capabilities is novel. This project is one of the pioneer works that make this combination work. It would be inspiring for the community. 

So, in principle, I believe this project is worth a presentation opportunity at top-tier ML conferences.
summary: This paper tackles the problem of building autonomous agents for web navigation tasks, including webshop and OpenTable. The proposed approach, AgentQ, leverages MCTS to generate an offline dataset and adopts DPO to fine-tune a base model based on both positive and negative trajectories. Finally, by combining AgentQ and online MTCS, the final performance substantially outperforms existing baselines.
weaknesses: My biggest complaint about this paper is its writing. This paper is particularly poorly written. It is such a great project but presented as an arbitrary technical report. Let's take the STaR (https://arxiv.org/pdf/2405.00451) paper as a good writing reference and I will leave a few detailed comments below. 

1. There is a significant lack of definitions. Throughout the paper, there is no definition of AgentQ. What do you mean by AgentQ? What is the difference between AgentQ and other baselines like DPO/STaR/XLaM? In the experiments, you use both AgentQ and AagentQ+MTCS as method names in the plot. What are the differences? It seems AgentQ itself requires MTCS for data generation. I spent a long time figuring out that the "MTCS" in Figure 1 refers to inference-time MTCS. Let's take the STaR paper as a reference. The STaR paper has a rigorous method section, where the definition of the method (including why it is named STaR) is clearly stated in Section 3. It even shows an overview plot in Figure 1 to make a reader understand the method better. 

2. Many experiment and baseline details are lacking. In general, each paper should have a separate experiment section (like Section 4 in the STaR paper) to present the baselines, environment, and main results. However, in this paper, all the presentations are sequential without even a centralized experiment section, which brings substantial difficulties for readers to follow. It is also unclear to me how these baselines are selected. For example, why is there no RFT + MTCS demonstrated in Figure 1? Note that this baseline is listed in Figure 3. What are the current state-of-the-art numbers on these two benchmarks?

3. Lack of ablation studies. For example, for AgentQ, it is unclear to me how effective each component is. I think a separate ablation studies section should be presented. What if we run RFT with the same data collection pipeline? Does the same conclusion still hold for Webshop if we turn the AI-based action section off? What if we directly run the Q function as the final deployed policy without DPO training a policy? Moreover, since MTCS is involved, it is critical to me to see the performance growth w.r.t. the computation budget used by MTCS, both online and offline. I cannot see any detailed specifications of MTCS in the main paper. If we allocate an infinite amount of time, what's the limit of this approach? Any concrete case study?

4. The AI-based action selection protocol looks unclear to me. This protocol only ranks agents. But MTCS expands the actions using the UCB criteria. The data generation also depends on the Q function only. The ranking does not help learn the Q function. Why do you need an AI to rank the policies? My understanding of it is that it works as a branching mechanism to allow MTCS to only traverse those most promising actions. Is my understanding correct? 

5. The theorem is good as it is but I don't think it makes too much sense for the overall project. You are not sampling data according to the  Q-induced distribution. The theorem and your algorithm aren't strongly connected. I would suggest you put more content on ablation studies and fine-grained controlled experiments.

6. Another minor point is that the citation formats are not consistent across the paper. Please update accordingly.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 4
questions: Please refer to the weaknesses.
soundness: 3
strengths: **Originality:**

The paper introduces a unique approach by combining MCTS with self-critique and DPO to enhance the decision-making abilities of AI agents. This innovative blend of techniques addresses the limitations of traditional LLMs in dynamic environments, making it a fresh contribution to the field.

**Quality:**

The research is thorough and well-executed, with rigorous experiments conducted in both simulated and real-world settings. The significant improvements in success rates, particularly in complex web navigation tasks, demonstrate the robustness and effectiveness of the proposed framework.

**Clarity:**

The paper is clearly written and well-structured, making complex concepts accessible. The methodology and results are presented in a straightforward manner, supported by clear figures and discussions that highlight the framework's advantages.

**Significance:**

Agent Q's ability to outperform existing methods and approach human-level performance in certain tasks is highly significant. It represents a substantial step forward in creating more autonomous and reliable AI systems, with broad implications for various applications, from web navigation to real-world decision-making.
summary: The paper presents Agent Q, a framework that improves the multi-step reasoning abilities of AI agents in interactive environments by combining guided MCTS with self-critique and an off-policy variant of DPO. It achieves superior performance in web navigation tasks, significantly outperforming standard methods and nearing human-level competence.
weaknesses: **Concerns Regarding Multi-turn DPO Loss:**

This paper extends the DPO loss to accommodate multi-turn interactions, as shown in Eq 5. However, recent literature [1], specifically in section 2.2, suggests that the expected multi-turn DPO loss is predicated on deterministic environment transitions. When transitions are stochastic, as is often the case in complex, real-world environments, the efficacy of the multi-turn DPO loss becomes unpredictable. It would be beneficial to see an analysis or empirical evidence that your approach is effective for the stochastic environment.
    
**Scalability and Computational Cost:**

The integration of MCTS, while enhancing performance, comes at a significant computational cost. For real-time applications or large-scale deployments, this could be prohibitive. A deeper analysis of the computational overhead and potential optimizations to mitigate this would be valuable. Could you elaborate on any strategies you've considered or implemented to address this?

**Limited Real-World Validation:**

Your experiments in WebShop and a real-world booking scenario are impressive, but they represent a limited scope of real-world environments. It's unclear how your framework would generalize to other domains or more complex applications. Broadening the range of scenarios tested would provide a more thorough validation of your framework's robustness and versatility.

**Sparse Reward Challenges:**

The sparsity of rewards in long-horizon tasks poses a significant challenge for your framework. While AI feedback and self-critique offer some mitigation, there's still a noticeable struggle with credit assignment. Exploring more sophisticated reward shaping or alternative methods to provide denser feedback could significantly enhance performance in these scenarios.

[1] Xiong, Wei, et al. "Building math agents with multi-turn iterative preference learning." *arXiv preprint arXiv:2409.02392* (2024).

Meta-review: This paper proposes an online framework to improve agents' autonomous reasoning capabilities in web navigation. There are two main concerns. First, the method and experiments (including ablation studies) lack details, which make it hard to follow the manuscript. Second, the novelty of the method. DPO, MCTS and the combination of those have been proposed by prior work. However, web navigation can be a new downstream task, which has its own unique challenges. In this regard, dismissing a paper's contribution purely because of its use of prior work may not be justified. However, a more detailed and careful discussion and validation of why using those methods and the combination of those method can be a good idea to address the challenges in web navigation( and what is the unique aspect of web navigation) is needed for readers to better appreciate this work.

Decision: Reject