Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents

We would like to thank the reviewers for the kind words and constructive feedback.

”Concerns Regarding Multi-turn DPO Loss…”*

It is indeed true that the standard DPO multi-turn loss depends on deterministic dynamics. In our own experiments, the OpenTable environment is non-deterministic (it’s a live website), while WebSHop is. We hypothesize that this is one of the reasons why outcome-level only DPO training performs relatively worse on OpenTable, while tree-based search data seems to offer larger improvement as it improves credit assignment. We should also note that under a slight change in perspective on preference modelling, the DPO loss is still valid in stochastic environments as well [1]. To what degree we can assume this holds in agentic settings is an open question.

Scalability and Computational Cost:

We believe that computational costs can be manageable, while the biggest bottleneck for agents is the environment interaction. When the environment is “live” (such as a real website with real bookings) this can be quite costly and hard. While some approaches can be used to improve efficiency (such as our step-level critic) it is likely this is a necessary part for training advanced reasoning agents. We believe that effective approaches for this could mimic efforts in robotics, such as a mix of “sim” and real - i.e. containerized simulated environments and real data used together. The advantage of our approach is that the DPO training can be carried on off-policy (and even fully offline) data.

Limited Real-World Validation

We agree that our application is somewhat limited, however training general-purpose web agents is still very much an open problem. Our work aims to be an initial step in that direction. In the meantime we have been working on extending our results to a wider set of simulated web applications and evaluating the potential sim-to-real results. This remains work in progress due to the complexities of accurate environment design.

Sparse Reward Challenges

The reviewer is indeed correct. This was the main motivation behind our use of the step-level critic model, which does improve performance in credit assignment. Ideally we would use a Process Reward Model (PRM) for this ranking as a prior over actions to explore first, however we believe training one would require a significant amount of either human data or Monte-Carlo rollouts, hence we opted for a zero-shot LLM-as-a-judge approach.

[1] Contrastive Preference Learning: Learning from Human Feedback without RL, Joey Hejna, Rafael Rafailov, Harshit Sikchi, Chelsea Finn, Scott Niekum, W. Bradley Knox, Dorsa Sadigh, 2024

We would like to thank the reviewer for the kind words and suggestions! We have made many changes to incorporate the feedback in our manuscript.

We agree that some definitions were unclear and have changed them. We have added more explicit definitions of AgentQ and AgentQ+MCTS so that there is no longer any ambiguity. We have also addressed many other writing improvements.

In general, each paper should have a separate experiment section (like Section 4 in the STaR paper) to present the baselines…

We structured our presentation to present initial results and the motivation for the development of our method first. In particular, in standard RLHF, well-executed RL training matches performance of inference-optimization approaches [1]. This is the direction reflected in our “Preliminary Approach With Outcome Supervision” section. However, in our experiments, it emerged this is not the case in multi-turn agentic domains, where search proved to be critical, both for learning credit assignment as well as performance at deployment time. This observation leads to our next two sections.

We have made some additional changes to the layout of the paper following your review. We have rewritten the discussion of the full WebShop results so that both the WebShop and OpenTable results are discussed in one experimental section. In addition, we have made the analysis more clear. This does improve the readability of the paper as now section 5 is focused on methods and section 6 contains results.

Why is there no RFT + MTCS demonstrated in Figure 1? Note that this baseline is listed in Figure 3

In the WebShop domain, the performance between the base xLaM model and the RFT fine-tune is relatively close and they perform comparably with the addition of inference-time search. We use the RFT fine-tune on OpenTable since the base model is quite poor in comparison so it is not worthwhile to perform MCTS with it.

What are the current state-of-the-art numbers on these two benchmarks?

As far as we are aware the current best results (success rates) on WebShop in a zero-shot approach are comparable to AgentQ zero-shot performance, and significantly lacking the performance with additional inference-time search.

The OpenTable environment is not an existing benchmark, but a real-world website, which we used to demonstrate training and deployment in a real scenario. In our own evaluations the human-performance is comparable to AgentQ+MCTS with errors coming from task ambiguity and similar restaurant names with different locations.

Lack of ablation studies…

We carry out large number of ablations on our OpenTable real environment training such as:

Full-trajectory level outcome versus search-based training (DPO vs AgentQ). The effect of the step-level self-evaluation (AgentQNoAIFeedback) Zero-shot performance + Inference-time search (AgentQ vs AGentQ+MCTS)

We did not include all of these in the WebShop experiment, since the environment is significantly simpler and does not require as extensive credit assignment as the more challenging OpenTable domain, hence the effect of these design choices is not as clear.

What if we directly run the Q function as the final deployed policy without DPO training a policy?

We should note that we do not train a separate value function, but only construct MC estimates to guide our search. We believe that training an accurate value network would require a significant amount of rollouts and interactions, hence why we choose to use an LLM for zero-shot process guidance. This is essentially the “RFT + MCTS” baseline, which uses the base RFT policy and critic models without any additional training. If we allocate an infinite amount of time, what's the limit of this approach? Any concrete case study?

We ran the deployment-search until the model reached success (as judged by the critic) or hit an interaction limit. In this case, by design we found steady improvement with additional search ranging from the AgentQ zero-shot performance to AGentQ+MCTS level performance.

The experimental section is incomplete….

The goal of our work is to develop pipelines for training and improved reasoning of LLM agents. As such, we do not aim to ablate the design choices of the core agent such as memory, action formulation, planning, prompting etc…

We carry out large number of ablations on our OpenTable real environment training such as:

1. Full-trajectory level outcome versus search-based training (DPO vs AgentQ).
2. The effect of the step-level self-evaluation (AgentQNoAIFeedback)
3. Zero-shot performance + Inference-time search (AgentQ vs AGentQ+MCTS)

We did not include all of these in the WebShop experiment, since the environment is significantly simpler and does not require as extensive credit assignment as the more challenging OpenTable domain, hence the effect of these design choices is not as clear.

Many critical descriptions of the methods…

We would like to thank the reviewer for the detailed feedback on the presentation of our work and are working on incorporating their feedback.

The authors state that the agent trained by DPO behaves greedily (Line 288). Does the step-level DPO address this issue?

No, we observe consistent model collapse in the agent behaviour with different RL techniques. While we can improve zero-shot performance, it still lags behind expert-level actions. This is largely resolved with additional inference-time search (AgentQ+MCTS). Since the release of our work similar effects have been observed in simpler domains such as math. We believe that using inference-time search techniques for agents is going to be a significant research and development direction over the next several years.

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

We did not observe such an effect, however, we did not ablate the core agent design choices to a significant degree.

How is the ranking of responses transferred to Q^ ?

We assign a normalized score to each action based on its ranking. We observed this to be more efficient than exploring actions based on individual pointwise scoring and evaluations.

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

These were obtained from the original work [1]. We should note that the challenge of the environment seems to originate from the ambiguity of product descriptions. In our own attempts, success rates varied between 40%-55% depending on the evaluator.

Which correspond to the explanation action in Figure 4?

Figure 4 shows the input and output formats of the prompt for the base agent used across all experiments.

[1] WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents Shunyu Yao, Howard Chen, John Yang, Karthik Narasimhan, 2023

We would like to thank the reviewer for the detailed feedback.

“The idea is not novel enough since Agent Q uses a combination of DPO, MCTS, and process supervision for web navigation task.”

The general research direction of combining LLMs with search capabilities is relatively new with most works focusing on model-training in the math domain developed within the last 6-9 months. We believe that our work is the first one to scale these ideas to realistic agentic applications beyond simple tasks such as the Game of 24 or high-school math. Moreover, we believe that advanced reasoning capabilities for agentic models will be the main research and development direction in artificial intelligence over the next two years and our work is an early attempt in that direction.

As for DPO, MCTS, and process supervision, the relevant works have been referenced and contextualized in the paper.

Lack of experimental details, such as hyperparameters, and the significance of the results. Also, the code is not provided.

Due to the large-scale interaction requirements with real websites as well as training costs, we cannot provide significance over multiple runs, but this has been standard in LLM training literature since the rise of “large” foundational models.

Unfortunately we cannot open-source our code, but we still believe that our research and results will be informative and useful to the community.

Lack of ablation studies to analyze the effects of number of iterations in Agent Q. All reported results are over 3 iterations. While the RFT model continues improving, the DPO-based models largely saturate in performance by iteration 3. This is consistent with observations on efficiency in simpler domains, such as math [1]

On the presentation, we have incorporated all your suggestions into the updated draft. Thank you for the effort and detail you provided in your feedback. It has helped us to improve the quality of the paper.

"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 apologize for this typo, Figure 1 has the correct performance numbers and we have fixed the references to it.

How does the computational complexity of Agent Q compare to the baseline methods?

While our agentic pipeline uses multiple components the core costs are still based on model processing of inputs and generating outputs. Thus the computational requirements for training are somewhat comparable (not accounting for additional search at agent deployment time).

[1] RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold, Amrith Setlur, Saurabh Garg, Xinyang Geng, Naman Garg, Virginia Smith, Aviral Kumar, 2024

We would like to thank the reviewer for the detailed feedback!

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.

The plan is generated as part of the first agent step and thus in MCTS we can backtrack (and occasionally do) to the initial stage and re-generate a new plan.

Despite the expressions such as "real-world booking scenarios" (Abstract) and "Scaling To Real World Websites" (Section 6)...

We do agree that our proposed tasks are somewhat narrow in their formulation, however training general-purpose agents in real domains is still a major unsolved problem. We believe the major challenge in this domain is the dynamic, non-stationary and real-time environment of a live website as availability and dining options change minute-to-minute.

This is in stark contrast to prior reasoning works which combine tree search with LLMs and RL, as they operate in static MDPs, such as solving high-school math. As far as we are aware our work is the first one to show such capabilities in non-deterministic non-static domains.

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).

This is indeed correct, but the result is based on the more simplistic nature of the WebShop environment. The core idea of our tree-search based training is to help the agent learn credit assignment in complex multi-step (and potentially dynamic) environments.

In this case we use WebShop as a development proof-of-concept environment. This domain is deterministic and relatively simple as it only requires about six steps to solve. Hence here credit assignment is not as much of an issue.

In contrast, the real OpenTable environment requires about 13 steps to solve and is non-deterministic, thus credit assignment issues become more prominent and the gap between purely outcome-driven training versus the tree-structured exploration we use becomes more apparent.

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).

The main contribution of our work is to extend approaches based on search and LLMs from relatively simpler static domains such as math to realistic and more complex agentic dynamic scenarios, which presents unique challenges not previously explored as far as we’re aware.