Source-linked AI summary
Tree Search for LLM Agent Reinforcement Learning
Yuxiang Ji, Ziyu Ma, Yong Wang, Guanhua Chen, Xiangxiang Chu, Liaoni Wu
TL;DR
Long-horizon, multi-turn agent RL is limited by costly redundant rollouts and sparse outcome-only supervision. Tree-GRPO uses step-level tree search with shared prefixes and tree-based relative advantages to address these constraints. Across 11 datasets, it outperforms chain-based RL, including with substantially lower rollout budgets.
Problem
Long-horizon multi-turn agent RL faces costly, redundant rollouts and sparse supervision when a single outcome reward covers the trajectory.
Method
Tree-GRPO performs tree-search rollouts with complete agent steps as nodes, sharing prefixes and estimating relative advantages within and across trees.
Results
Across 11 datasets, Tree-GRPO consistently improves over chain-based methods across model series and scales, including under limited rollout budgets.
Takeaways & Limitations
Tree-structured rollouts provide more rollout samples and step-level process supervision while using outcome rewards for multi-turn agent RL.
Takeaways & Limitations
Larger expansion within fewer trees narrows exploration because more trajectories share the same prefix, and tree configurations have varying effects.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Long-horizon agentic RL faces costly, redundant rollouts and sparse supervision. Tree-GRPO addresses both through step-level tree search, tree-derived process signals, and grouped advantage estimation, with improvements across 11 datasets.
- Motivation: Agent trajectories can require thousands of tokens and multiple tool calls, making rollout sampling costly and redundant under independent chain-based strategies.Tool calls may also incur substantial external costs, such as high-priced search APIs.
- Method: Tree-GRPO replaces independent chain-based rollouts with a tree whose nodes represent complete Thought-Action-Observation agent steps.Shared prefixes create interleaved trajectories while preserving semantically clear agent-step boundaries.
- Efficiency: 1.5× samples can be obtained under the same token or tool-call budget, depending on tree structure, compared with chain-based rollout.The shared-prefix design explicitly constrains rollout budgets in both tokens and tool calls.
- Process supervision: Tree-GRPO back-propagates leaf outcome rewards at branching points, using sibling-branch differences as process-level preference signals.Random expansion produces process signals with varying granularity for learning intermediate decisions.
- Evaluation: Experiments cover 11 datasets spanning single-hop, multi-hop knowledge-intensive, and hard web-agent tasks, with consistent gains across model series and scales.The method also enables a base model to adopt a predefined multi-turn interaction paradigm without supervised fine-tuning.
- Evaluation: On Qwen2.5-3b, Tree-GRPO outperforms the chain-based method while using only one quarter of the rollout budget.The result is reported under an extremely limited token/tool-call rollout budget.
2 PRELIMINARY
The paper models multi-turn ReAct interaction as an MDP whose states contain accumulated context and whose compound actions contain thought-action pairs. RL then optimizes the full trajectory, typically using outcome rewards and group-based advantage estimation.
- Multi-turn agent framework: A ReAct episode consists of repeated Thought-Action-Observation cycles in which the LLM generates a thought and parsable action from the current context.Actions typically invoke tools that return new observations from the environment.
- Multi-turn agent framework: H = {(τ0, α0, o0), (τ1, α1, o1), ..., (τT −1, αT −1, oT −1)} represents the complete T-step interleaved agent episode.The trajectory grows linearly with the number of interaction steps.
- Multi-turn agent framework: For complex tasks requiring many interactions, the full trajectory can reach tens of thousands of tokens.This reflects the linear growth of trajectories with the number of steps.
- MDP formulation: The process is formulated as an MDP M = {S, A, P}, with accumulated interaction context as state, thought-action pairs as compound actions, and environment-plus-context transitions.The transition dynamics include both external environment changes and concatenation of full context over time.
- RL objective: RL optimizes the policy over complete state-action trajectories by maximizing expected return.Optimization uses an advantage estimator to stabilize gradient updates.
- Reward structure: Existing agentic RL commonly assigns one scalar outcome reward to the entire trajectory, creating trajectory-level supervision.The reward may come from predefined rules or model-based scoring functions.
- Group-based RL: Group-based RL estimates advantages from multiple candidate rollouts and an in-group baseline rather than an additional value function.The baseline guides the optimization direction while reducing reliance on PPO-style value estimation.
3 TREE-BASED GROUP RELATIVE POLICY OPTIMIZATION (TREE-GRPO)
Tree-GRPO replaces independent chain rollouts with tree-search sampling whose agent-step nodes share prefixes, enabling more rollouts under the same budget. The tree also supplies process-level credit from outcome rewards through intra-tree and inter-tree relative advantages, with intra-tree optimization theoretically matching step-level preference learning.
- 3.1 TREE SEARCH FOR AGENT ROLLOUT: Tree-GRPO shares partial prefixes between agent-step rollouts to obtain more rollouts under the same token or tool-call budget.Each tree node represents a complete thought-action-observation step, rather than a token- or sentence-level unit.
- 3.1 TREE SEARCH FOR AGENT ROLLOUT: The initialize-then-expand procedure starts multiple chains, samples non-leaf nodes, and iteratively expands selected nodes into new branches.The resulting rollout count is M × (L × N + 1) for one prompt, with expected tree-search budget E[Btree] = M · B + L · N · B/2.
- 3.1 TREE SEARCH FOR AGENT ROLLOUT: Fixed-budget configurations trade rollout count against exploration scope: fewer trees and more expansions increase rollouts but make trajectories share more prefixes.Different tree configurations therefore have varying effects in experiments.
- 3.2 TREE-BASED GROUP RELATIVE ADVANTAGES: Tree-structured rollouts convert differences between subtree outcome rewards at branching points into process-level preference signals with granularity determined by subtree depth.This addresses trajectory-level credit assignment, where every step otherwise receives the same outcome-derived advantage.
- 3.2 TREE-BASED GROUP RELATIVE ADVANTAGES: Tree-GRPO combines intra-tree and inter-tree grouped relative advantages because few rollouts within one tree can make the intra-tree baseline unreliable.The inter-tree grouping is used to stabilize training alongside the explicit intra-tree preference objective.
- 3.3 IMPLICIT STEP-LEVEL PREFERENCE LEARNING: Under a binary preference assumption, intra-tree GRPO and step-level DPO share the same gradient structure, differing only in the weight term.Thus intra-tree GRPO implicitly performs step-level preference optimization during online rollout.
4 EXPERIMENT
The experiments evaluate Tree-GRPO across 11 QA datasets and show consistent advantages over chain-based RL, including under constrained rollout budgets. Results also examine task difficulty, interaction length, hyperparameter stability, and tree-based advantage estimation.
- Experimental Setup: Experiments cover 11 benchmarks spanning multi-hop QA, single-hop QA, and web-agent QA, using EM or F1 metrics as appropriate.The study compares Tree-GRPO with direct prompting, ReAct, Search-o1, GRPO, and GSPO across Qwen and Llama models.
- Multi-Hop QA: 16% to 69% relative improvement is achieved by Tree-GRPO over chain-based GRPO on models below 3b in multi-hop QA.Tree-GRPO remains effective on Qwen2.5-1.5b, while chain-based methods struggle to induce multi-turn tool use; the 14b model sees an average relative improvement of 8.4%.
- Single-Hop QA: Tree-GRPO shows stable improvements over chain-based RL in single-hop QA, especially for Qwen2.5-1.5b and Qwen2.5-3b.Because most single-hop questions require only one retrieval and answering round, their limited tree depth restricts additional gains from process-level supervision.
- Web-Agent QA: 28% average improvement is achieved by Tree-GRPO over chain-based GRPO on GAIA, while BrowseComp shows only marginal RL gains constrained primarily by training data.Tree-GRPO consistently outperforms chain-based GRPO across four web-agent QA test datasets.
- Different Training Budget: 112% relative improvement is achieved under a highly constrained rollout budget with only two complete rollouts per prompt.Tree-GRPO remains superior while using only a quarter of the chain-based rollout budget; its advantage from finer process supervision persists in multi-hop settings.
- Quantitative Analysis: Tree-GRPO encourages longer multi-hop interactions, increasing average tool calls from 2.4 to 3.0, and remains stable across learning-rate warmup and KL-coefficient settings.Combining intra-tree and inter-tree advantages improves stability when intra-tree branching is insufficient, while retaining step-level preference-learning properties.
5 RELATED WORK
Related work situates Tree-GRPO among sparse-reward reinforcement learning, LLM-agent RL, and tree-search research. Existing approaches address exploration, credit assignment, process supervision, or reasoning-path search through different mechanisms.
- Reinforcement Learning for Sparse Rewards: Sparse-reward RL methods include exploration-oriented techniques and approaches that improve credit assignment through heuristic or sampling-based structures.The paper notes that exploration is not currently the primary bottleneck for LLM agents because of strong base-model priors and structured action spaces.
- Tree-based Advantage: Table 4 studies alternative tree-based advantage estimators, including intra-tree, inter-tree, and their combination.The supplied passage identifies combined advantage estimation as more stable and improved across varied settings.
- Reinforcement Learning for LLM and Agent: Process reward models can improve complex reasoning, but most existing LLM RL work still relies solely on outcome rewards.This distinction motivates constructing finer-grained process signals from tree-structured agent trajectories.
- Tree Search for LLM Reasoning: LLM tree-search research includes test-time scaling and Monte Carlo tree search for generating multiple reasoning or proof paths.These lines of work primarily address reasoning-time search rather than the online agent RL setting targeted by Tree-GRPO.
6 CONCLUSION
Tree-GRPO replaces independent chain rollouts with tree-search sampling over agent step-level nodes. Across 11 datasets, the approach reduces rollout costs, supplies implicit step-level preference learning, and outperforms chain-based agent RL.
- Conclusion: Tree-GRPO uses agent step-level nodes and shared prefixes to reduce token and tool-call rollout budgets during training.Its tree structure also supports tree-based grouping for advantage estimation and an implicit step-level preference-learning objective.
- Conclusion: Empirical evaluations on 11 datasets demonstrate the superiority of Tree-GRPO for agentic reinforcement learning.The conclusion summarizes the paper's reported comparison with independent chain-based rollouts.
A DATASETS
The paper evaluates Tree-GRPO across single-hop and multi-hop question-answering settings, using distinct training and test datasets. Single-hop questions require one supporting passage, whereas multi-hop questions require compositional reasoning across multiple documents or entities.
- Single-Hop QA: Single-hop QA is solvable with a single supporting passage.Its training split comes from NQ and contains 79,168 QA pairs.
- Single-Hop QA: Single-hop QA tests use NQ, TriviaQA, and PopQA.Their test sets contain 3,610, 11,313, and 14,267 QA pairs, respectively.
- Multi-Hop QA: Multi-hop QA requires compositional reasoning and evidence aggregation across multiple documents or entities.Its training split comes from HotpotQA and contains 90,447 QA pairs.
- Multi-Hop QA: Multi-hop QA tests include HotpotQA, 2WikiMultiHopQA, Musique, and Bamboogle.Musique additionally requires information retrieval, semantic understanding, and logical reasoning.
A.3 WEB-AGENT QUESTION ANSWERING
The web-agent QA setting evaluates interactive search and information integration on web environments. Its training data combines verified ASearcher-35K samples with WebDancer samples, while testing uses four web-oriented benchmarks.
- Task Definition: Web-agent QA requires agents to search, navigate, and perform single- or multi-turn information integration in interactive web environments.The setting covers both single-turn and multi-turn exploration.
- Training Data: Web-agent QA training uses 2,000 verified ASearcher-35K samples and 200 released WebDancer samples.The ASearcher-35K questions and answers are filtered and verified.
- Training Data: The web-agent QA experimental setup is relatively small because real search APIs are costly and high-quality training samples are difficult to obtain.This limits the scale of the training setup to the stated data sources.
- Test Data: Web-agent QA testing uses SimpleQA, GAIA, WebWalkerQA, and BrowseComp.GAIA contributes 103 text-only questions, while BrowseComp contains 1,266 complex information-seeking questions.
B.1 IMPLEMENTATION DETAILS
The implementation builds on Search-R1 and evaluates Tree-GRPO alongside direct prompting, retrieval, ReAct, GRPO, and GSPO baselines. Experiments use fixed optimization settings and search-based agent interactions.
- Implementation: The implementation is built on Search-R1 and uses learning rate 1e-6 with a 0.001 K3 KL coefficient.The default group size is 4 for chain-based RL, while Tree-GRPO uses M = 2, N = 2, L = 1.
- Implementation: Single-hop and multi-hop experiments use 180 training steps, batch size 512, PPO mini-batch size 64, and maximum responses of 4096 tokens.The agent receives the top 3 passages from the local retrieval server.
- Implementation: Web-agent experiments use 34 training steps, batch size 128, PPO mini-batch size 64, and maximum responses of 8000 tokens.The supplied passage states that the web-agent setup uses a larger retrieval context than the QA settings.
- Baselines: Baselines include direct inference, ReAct, Search-o1, GRPO, and GSPO.Search-o1 integrates agentic retrieval-augmented generation and reason-in-document modules.
- Baselines: ReAct interleaves reasoning traces with tool-call actions, and the RL-based methods use ReAct as their agent framework.The model uses observations to refine subsequent reasoning.
- Baselines: GRPO computes relative advantages across multiple trajectories without a value or critic model, while GSPO applies trajectory-level reweighting.Tree-GRPO is built on GRPO and uses GRPO as the primary chain-based RL baseline.
B.3 TREE SEARCH AT DIFFERENT LEVELS
The paper compares token/sentence-level and agent-step-level tree search for agent RL. Agent-step-level search performs better because it preserves meaningful interaction units, while tree parameters trade off sampling diversity and process-signal granularity.
- Token/Sentence-Level Search: Token/sentence-level tree search uses tokens as tree nodes and is separately implemented for agent RL.The comparison keeps the other experimental settings consistent with Tree-GRPO.
- Comparison: Agent-step-level tree search outperforms token/sentence-level search in both single-hop and multi-hop QA.The token/sentence-level variant also falls below chain-based GRPO.
- Comparison: Token/sentence-level branching can waste rollout budget because branching in the middle of an agent step lacks a clear purpose.Its credit assignment also undermines agent-step integrity and hinders learning performance.
- Tree-Search Structures: When N = 0 and L = 0, Tree-GRPO degenerates into vanilla GRPO.The authors generally set L = 1 because expansion iterations are executed serially and directly affect rollout efficiency.
- Tree-Search Structures: M controls sampling diversity, whereas N and L control process-signal granularity.The required granularity correlates with interaction length because tree depth is determined by the number of agent steps.
C THEORETICAL ANALYSIS
The theoretical analysis characterizes intra-tree GRPO under a binary preference setting and relates it to step-level DPO. It also outlines the Tree-GRPO optimization procedure and reports supporting case studies.
- Binary Preference Setting: Under a binary preference setting, each intermediate tree node’s subsequent trajectories fall into winning and losing categories with rewards {1,0}.
- Intra-tree Group Policy Optimization: Intra-tree GRPO estimates advantages by comparing winning or losing rewards with a probability-weighted baseline.
- Structural Equivalence: Intra-tree GRPO and step-level DPO admit the same gradient-estimator structure, differing only in the weight term.
- Case Studies: The reported case studies include successful multi-turn tool use and failed paths that were not reconsidered or verified.
- Optimization Procedure: Tree-GRPO computes intra-tree and inter-tree group-relative advantages before updating the policy with the Tree-GRPO objective.