Tree Search for LLM Agent Reinforcement Learning
Recent advances in reinforcement learning (RL) have significantly enhanced
the agentic capabilities of large language models (LLMs). In long-term and
multi-turn agent tasks, existing approaches driven solely by outcome rewards
often suffer from the problem of sparse supervision. To address the challenge,
we propose Tree-based Group Relative Policy Optimization (Tree-GRPO), a grouped
agent RL method based on tree search, where each tree node represents the
complete agent interaction step. By sharing common prefixes, the tree search
sampling increases the number of rollouts achievable within a fixed budget of
tokens or tool calls. Moreover, we find that the tree-structured trajectory
naturally allows the construction of step-wise process supervised signals even
using only the outcome reward. Based on this, Tree-GRPO estimates the grouped
relative advantages both on intra-tree and inter-tree levels. Through
theoretical analysis, we demonstrate that the objective of intra-tree level
group relative policy optimization is equivalent to that of step-level direct
preference learning. Experiments across 11 datasets and 3 types of QA tasks
demonstrate the superiority of the proposed tree-based RL over the chain-based
RL method.
68d6011f8ccd91bdd39ffdfc
Yuxiang Ji
claimed_verified
2025-09-26T12:16:47.611Z
666a83e9b2d8397c1e545785
https://cdn-avatars.huggingface.co/v1/production/uploads/666a83e9b2d8397c1e545785/7PxrVl38zWUbjAsZThHHb.jpeg
Yuxiang Ji
user
Yux1ang
68d6011f8ccd91bdd39ffdfd
Ziyu Ma
68d6011f8ccd91bdd39ffdfe
Yong Wang
68d6011f8ccd91bdd39ffdff
Guanhua Chen
68d6011f8ccd91bdd39ffe00
Xiangxiang Chu
68d6011f8ccd91bdd39ffe01
Liaoni Wu
Tree Search for LLM Agent Reinforcement Learning
Recent advances in reinforcement learning (RL) have significantly enhanced
the agentic capabilities of large language models (LLMs). In long-term and
multi-turn agent tasks, existing approaches driven solely by outcome rewards
often suffer from the problem of sparse supervision. To address the challenge,
we propose Tree-based Group Relative Policy Optimization (Tree-GRPO), a grouped
agent RL method based on tree search, where each tree node represents the
complete agent interaction step. By sharing common prefixes, the tree search
sampling increases the number of rollouts achievable within a fixed budget of
tokens or tool calls. Moreover, we find that the tree-structured trajectory
naturally allows the construction of step-wise process supervised signals even
using only the outcome reward. Based on this, Tree-GRPO estimates the grouped
relative advantages both on intra-tree and inter-tree levels. Through
theoretical analysis, we demonstrate that the objective of intra-tree level
group relative policy optimization is equivalent to that of step-level direct
preference learning. Experiments across 11 datasets and 3 types of QA tasks
demonstrate the superiority of the proposed tree-based RL over the chain-based
RL method.
Tree-based Group Relative Policy Optimization (Tree-GRPO) enhances reinforcement learning for large language models by using tree search to improve rollouts and estimate grouped relative advantages, outperforming chain-based methods.
reinforcement learning large language models sparse supervision Tree-based Group Relative Policy Optimization tree search rollouts step-wise process supervised signals intra-tree level inter-tree level step-level direct preference learning