Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents

Pranav Putta; Edmund Mills; Naman Garg; Sumeet Motwani; Chelsea Finn; Divyansh Garg; Rafael Rafailov

Source-linked AI summary

Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents

Pranav Putta, Edmund Mills, Naman Garg, Sumeet Motwani, Chelsea Finn, Divyansh Garg, Rafael Rafailov

arXiv:2408.07199v1Aug 13, 2024cs.AIcs.LG

TL;DR

Autonomous web agents need to reason and act over multi-step interactive environments, but static training and limited exploration constrain their improvement. Agent Q combines MCTS, self-critique, and off-policy DPO learning from agent trajectories; it raises booking success from 18.6% to 81.7%, reaching 95.4% with online search. The approach improves web-agent capabilities in simulated and real-world settings, while safety-critical deployment remains constrained by search mistakes and limited reversibility.

Problem
Static training and limited exploration constrain LLM agents’ ability to perform multi-step reasoning and decision-making in interactive web environments.
Method
Agent Q combines MCTS-guided exploration, AI self-critique, and off-policy DPO training on successful and unsuccessful agent trajectories.
Results
18.6% to 81.7% zero-shot absolute success: Agent Q achieves a 340% relative increase in real-world booking after one day of autonomous data collection, reaching 95.4% with online search.
Takeaways & Limitations
The framework improves autonomous web-agent capabilities through model training with synthetic reasoning and search data, across simulated and real-world web tasks.
Takeaways & Limitations
Safety-critical deployment is limited because autonomous search may make mistakes that are difficult to fix or reverse, motivating additional safety critics and human-in-the-loop training.

Abstract

from arXiv · show

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 ga-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

Agent Q targets autonomous web agents that must plan and reason across interactive, multi-step tasks, where static training and limited exploration remain inadequate. It combines search, self-critique, and iterative preference-based learning to improve agent performance.

Motivation and contribution: Agent Q addresses web-agent planning and reasoning by combining search, self-critique, and reinforcement learning for autonomous experience with limited supervision.The framework is designed for agents interacting with real-world websites.
Method: MCTS guides exploration of web actions, while self-critique supplies intermediate feedback to mitigate sparse rewards and credit-assignment problems.The search uses a base LLM to sample rationales and actions, then evaluates nodes with AI feedback.
Method: DPO learns from successful and unsuccessful search trajectories by creating node-level preferences from process-feedback rewards and branch success.This converts search traces into offline reinforcement-learning data for iterative policy improvement.
Results: In WebShop, Agent Q consistently outperforms behavior cloning and reinforcement-learning fine-tuned baselines, and exceeds average human performance with online search.The comparison is reported for the simulated e-commerce environment.
Results: 18.6% to 81.7%: Agent Q raises zero-shot absolute success in real-world booking, a 340% relative increase after one day of autonomous data collection.The result also outperforms GPT-4’s performance in that setting.
Results: 95.4% success follows when the booking agent is equipped with online search.This is the reported absolute success rate after adding online search capability.

2. Related Work

Related work spans prompt-based reasoning, tree search, reinforcement learning, and web-agent frameworks. Agent Q combines node-level search preferences, AI feedback, and further model training for realistic web-agent settings rather than relying only on pretrained capabilities.

Guided Search for Reasoning and Planning: Prompt-based reasoning and planning methods improve LLM behavior but remain bounded by the base model’s performance.Related work includes chain-of-thought, zero-shot prompting, and other prompt-based strategies.
Guided Search for Reasoning and Planning: Prior tree-search methods create preference pairs from different branches, while Agent Q adds AI feedback to guide intermediate search steps.The paper positions this combination as scaled to a realistic agent setting.
Web Agents: Earlier web agents mostly wrap strong pretrained models or apply limited fine-tuning and adaptation.This limitation is described across existing autonomous web-agent approaches.
Web Agents: Agent Q combines planning and reasoning with MCTS inference-time search, AI self-critique, self-supervised data collection, and RL-type training.The approach emphasizes model training for continuous improvement rather than framework design alone.
Reinforcement Learning for LLMs and Agents: PPO-style reinforcement learning is complex and requires costly online data, while offline alternatives can require auxiliary value models or have limited scaling to modern LLMs.These constraints motivate the paper’s preference for DPO.
Reinforcement Learning for LLMs and Agents: DPO is selected for its simplicity and fit with branching tree-search data, where actions can be optimized at the node level.The paper also introduces an off-policy replay-buffer modification that removes the need for a separate reference model.

3. Preliminaries

The paper formulates web interaction as a partially observable decision problem and represents agent actions as structured planning, reasoning, environment, and explanation components. It introduces supervised and preference-based fine-tuning objectives, including an off-policy replay-buffer modification to DPO.

3.1. Agent Formulation: A POMDP models web interactions with partial observability, browser transitions, sparse success/failure rewards, and discount factor γ=1.The formulation supports exploration because novel environments require discovering task objectives, while real websites dynamically change.
3.1. Agent Formulation: Agent actions combine planning, reasoning, browser interaction, and explanation components, while only the environment action changes the browser.Planning is generated initially; subsequent steps include thought, environment, and explanation actions that condition later decisions.
3.1. Agent Formulation: The agent history h_t contains prior actions and the current browser state rather than the full web trajectory.This compact representation addresses long HTML DOMs, limited context windows, inference cost, and potential out-of-distribution issues.
3.2.1. Reinforced Fine-Tuning: Reinforced fine-tuning constructs a dataset of high-quality trajectories by filtering samples with a reward model or verifier before supervised fine-tuning.Its divergence penalty is applied implicitly by limiting training rounds, and the paper uses this approach primarily as a baseline.
3.2.2. Direct Preference Optimization: DPO is an offline reinforcement-learning alternative that learns from pairwise preferences without requiring online rollouts.In this paper’s agent setting, preferences can extend to multi-turn trajectories and branches.
3.2.2. Direct Preference Optimization: An off-policy replay buffer modifies DPO by aggregating trajectories and action likelihoods, eliminating the need for a reference model during optimization.The method samples trajectories and corresponding data-generation likelihoods during optimization.

4. Preliminary Approach With Outcome Supervision

Outcome-supervised fine-tuning improves WebShop performance over the base agent, but the resulting policies remain below average human performance and exhibit weak exploration. DPO benefits from failed trajectories, while beam search provides only marginal additional improvement.

4. Preliminary Approach With Outcome Supervision: 28.6% success rate is achieved by the base xLAM-v0.1-r model on 1,087 held-out WebShop tasks.The benchmark contains 12,087 tasks, split into 11,000 training tasks and 1,087 held-out evaluation tasks.
4. Preliminary Approach With Outcome Supervision: 31.3% success rate is achieved by trajectory-level RFT, a 2.7% improvement over the initial model.The base model was already supervised-fine-tuned on agent demonstrations.
4. Preliminary Approach With Outcome Supervision: 40.6% success rate is achieved by trajectory-level DPO, improving 9.3% over the RFT agent by using failed trajectories alongside successful ones.This experiment uses only outcome-level supervision and prefers successful trajectories over failed ones.
4. Preliminary Approach With Outcome Supervision: Greedy first-page product searches leave the DPO policy below average human performance because it rarely uses WebShop’s [NEXT] and [PREV] navigation controls.The paper identifies this behavior as a weak exploration strategy and a core failure mode.

5. Agent Search

Agent Search adds MCTS-based exploration to web-agent inference, using AI process supervision to rank actions and provide intermediate rewards. Search traces then support node-level DPO preference learning from successful and unsuccessful branches.

Agent Search: MCTS adds test-time search over web-page states using selection, expansion, simulation, and backpropagation to balance exploration and exploitation.The base LLM samples candidate actions, and rollouts continue until terminal states.
Action Selection With AI Process Supervision: The critic’s action rankings guide node selection after expansion and generate preference pairs for policy training.The critic is initialized from the same base LLM as the policy.
Action Selection With AI Process Supervision: AI process supervision ranks sampled actions and supplies intermediate feedback because web environments provide sparse end-of-trajectory rewards.The feedback guides exploration at each node and helps address long-horizon credit assignment.
Improving Zero-Shot Performance with Reinforcement Learning: The framework uses off-policy DPO on node-level preferences formed from process-feedback rewards and final branch success.Preferences compare child actions when their estimated values differ beyond a threshold.
Improving Zero-Shot Performance with Reinforcement Learning: Theorem 1 states that, under preferences generated from the appropriate value function, the DPO-optimal policy is identical to the optimal RL policy.The paper uses this result to motivate value-based preference construction.
Full WebShop Results: 50.5% success on WebShop is achieved by applying MCTS to the trained Agent Q model, slightly exceeding the 50.0% average human performance.MCTS on the base xLAM-v0.1-r model raises success from 28.6% to 48.4%.

6. Scaling To Real World Websites

The real-world evaluation applies Agent Q to OpenTable bookings, where success requires completing multiple reservation constraints in a live website. Agent Q improves performance substantially, and combining it with MCTS reaches 95.4% success.

The OpenTable Environment: OpenTable tasks require finding a restaurant, selecting a reservation matching user constraints, entering contact information, and completing the booking.The evaluator checks date and time, party size, user information, and reservation completion.
The OpenTable Environment: GPT-4-V evaluates the final observation and action history, assigning a binary 0/1 success score to each trajectory.The evaluator also receives a screenshot of the final state.
Results On OpenTable: 18.6% zero-shot success rises to 67.2% after one round of RFT on 600 successful trajectories.The RFT model becomes the reference policy for the remaining baselines.
Results On OpenTable: 81.7% zero-shot success is achieved by the full Agent Q pipeline, exceeding outcome-supervision-only DPO at 71.8%.The paper attributes the difference to OpenTable’s longer trajectories and need for finer-grained credit assignment.
Results On OpenTable: 84.3% success is achieved by adding MCTS to the base RFT model, while Agent Q plus MCTS reaches 95.4%.The latter significantly outperforms the other reported techniques on OpenTable.

7. Discussion

Agent Q enables autonomous web-agent improvement with limited human supervision, while identifying unresolved concerns about critic design, search choice, zero-shot/search gaps, and online safety.

Agent Q fine-tunes pretrained models for web navigation using synthetic reasoning and search data with limited human supervision.
Design of reasoning algorithms: The separate critic provides process-level supervision by ranking possible agent actions, but remains frozen and may benefit from fine-tuning.
Choice of search algorithm: MCTS was selected for prior success in mathematics and code reasoning, though live-environment execution may require many risky interactions.
Discrepancy between zero-shot vs search results: A significant gap remains between zero-shot agent performance and performance with search capabilities.
Online safety and interaction: Autonomous exploration may produce mistakes that are difficult to reverse in safety-critical transactions, limiting safe deployment without additional critics or human oversight.