TGPO: Tree-Guided Preference Optimization for Robust Web Agent Reinforcement Learning

Ziyuan Chen, Zhenghui Zhao, Zhangye Han, Miancan Liu, Xianhang Ye, Yiqing Li, Hongbo Min, Jinkui Ren, Xiantao Zhang, Guitao CaoarXiv 2025 · DOI · arXiv

Introduction

Autonomous web agents, designed to navigate complex digital environments to fulfill user requests, represent a significant frontier in artificial intelligence. However, training these agents using Reinforcement Learning (RL) is fraught with challenges, primarily due to credit assignment misallocation, high annotation costs, and reward sparsity. Standard offline RL often penalizes entire trajectories for a single terminal failure, creating "label conflicts" where correct intermediate actions are incorrectly labeled as negative.

Methodology: Tree-Guided Preference Optimization

To address these issues, we present Tree-Guided Preference Optimization (TGPO), an offline RL framework that enhances the efficiency and accuracy of web agent training.

Overview of the TGPO framework, illustrating the transition from linear trajectory rollouts to a tree-structured representation, followed by automated reward modeling and optimization.

The TGPO framework introduces three core innovations:

  1. Tree-Structured Trajectory Representation: By merging semantically identical states across different interaction sequences, TGPO transforms linear trajectories into a unified tree. This structure explicitly identifies decision points where paths diverge, allowing the model to distinguish between successful and unsuccessful branches from the same state, thereby resolving label conflicts.
  2. Automated Process Reward Model (PRM): To eliminate the need for expensive manual labeling, TGPO utilizes an automated PRM. This model evaluates intermediate steps based on subgoal progress, action accuracy (verified via Vision-Language Models), format validity, and redundancy penalties.
  3. Dynamic Weighting Mechanism: The framework prioritizes learning at critical decision points—states where action choices lead to significantly different reward outcomes—ensuring the model focuses on the most impactful transitions.

Experimental Evaluation

The efficacy of TGPO was evaluated on two distinct benchmarks: Online-Mind2Web, featuring 300 tasks across 136 real-world websites, and C-WebShop, a dataset of 50 complex Chinese e-commerce tasks from Taobao designed to test multi-step shopping robustness.

Results and Discussion

TGPO demonstrates substantial performance gains over existing baselines and state-of-the-art closed-source models.

Success rates and execution efficiency metrics for TGPO compared to SFT, KTO, and DPO baselines across the Online-Mind2Web and C-WebShop datasets.

As shown in the results, TGPO achieved a 38.4% success rate on the Online-Mind2Web benchmark, significantly outperforming GPT-4o (30.0%) and standard Direct Preference Optimization (34.0%). Furthermore, on the C-WebShop dataset, TGPO reached a 78.6% success rate while drastically improving execution efficiency. The average number of steps required to complete a task was reduced from 14.28 in the base model to just 8.66, highlighting the framework's ability to minimize redundant actions and avoid the circular logic often seen in weaker agents. Ablation studies further confirmed that the tree structure itself is a powerful tool, with the "Tree" version of KTO (KTO-Tree) outperforming standard KTO by over 7%.

Conclusion

TGPO offers a robust solution for training web agents by leveraging tree-structured data to mitigate the noise inherent in offline RL. While the current implementation relies on Vision-Language Models for reward verification—introducing some computational overhead—the results confirm that state merging and fine-grained process rewards are essential for developing concise and effective autonomous agents. Future work will explore the generalization of this tree-guided approach to broader GUI and gaming environments.

Summary updated

BibTeX
@misc{chen2025tgpo,
  author = {Ziyuan Chen and Zhenghui Zhao and Zhangye Han and Miancan Liu and Xianhang Ye and Yiqing Li and Hongbo Min and Jinkui Ren and Xiantao Zhang and Guitao Cao},
  title = {{TGPO: Tree-Guided Preference Optimization for Robust Web Agent Reinforcement Learning}},
  year = {2025},
  eprint = {2509.14172},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.14172},
}
Figure