Paper 2509.21240
Tree Search for LLM Agent Reinforcement Learning
- Published
- Sep 2025
- Research lab
- Independent
- Citations
- 52
- GitHub
- 392 stars
01 In brief
Summary
The paper introduces Tree-GRPO, a reinforcement learning method for LLM agents that uses tree search for rollouts, with each node representing a complete agent interaction step (Thought-Action-Observation).
This approach shares common prefixes across rollouts, increasing the number of samples under a fixed token/tool-call budget.
Tree-GRPO estimates group relative advantages at both intra-tree and inter-tree levels, deriving step-level process supervision signals from outcome rewards alone.
Theoretical analysis shows that intra-tree GRPO is structurally equivalent to step-level DPO.
Experiments on 11 datasets across single-hop, multi-hop, and web-agent QA tasks demonstrate that Tree-GRPO outperforms chain-based RL methods, achieving higher performance with less rollout budget.
Notably, it enables a base model to learn multi-turn agent interactions without SFT, and with only a quarter of the rollout budget compared to chain-based methods.
02 From the paper
Abstract
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.