# Tree Search for LLM Agent Reinforcement Learning

arXiv: https://arxiv.org/abs/2509.21240 · HTML: https://mlsanity.com/paper/2509.21240/

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 72 of its 86 references that are in the map.
- First posted on arXiv 25 Sep 2025.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 30 of 72)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Group Sequence Policy Optimization](https://mlsanity.com/paper/2507.18071/) (2025)
- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agents](https://mlsanity.com/paper/2504.12516/) (2025)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)

## Built on by (most cited first, 30 of 79)

- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [Agentic Entropy-Balanced Policy Optimization](https://mlsanity.com/paper/2510.14545/) (2025)
- [Agent-R1: A Unified and Modular Framework for Agentic Reinforcement Learning](https://mlsanity.com/paper/2511.14460/) (2025)
- [Code2World: A GUI World Model via Renderable Code Generation](https://mlsanity.com/paper/2602.09856/) (2026)
- [Video-STAR: Reinforcing Open-Vocabulary Action Recognition with Tools](https://mlsanity.com/paper/2510.08480/) (2025)
- [Harder Is Better: Boosting Mathematical Reasoning via Difficulty-Aware GRPO and Multi-Aspect Question Reformulation](https://mlsanity.com/paper/2601.20614/) (2026)
- [Mem-T: Densifying Rewards for Long-Horizon Memory Agents](https://mlsanity.com/paper/2601.23014/) (2026)
- [On Group Relative Policy Optimization Collapse in Agent Search: The Lazy Likelihood-Displacement](https://mlsanity.com/paper/2512.04220/) (2025)
- [PivotRL: High Accuracy Agentic Post-Training at Low Compute Cost](https://mlsanity.com/paper/2603.21383/) (2026)
- [Crab: A Semantics-Aware Checkpoint/Restore Runtime for Agent Sandboxes](https://mlsanity.com/paper/2604.28138/) (2026)
- [LongHorizon-Harness: Advancing Long-Horizon Agents for Real-World Tasks](https://mlsanity.com/paper/2608.01964/) (2026)
- [Shepherd: Enabling Programmable Meta-Agents via Reversible Agentic Execution Traces](https://mlsanity.com/paper/2605.10913/) (2026)
- [Visually-Guided Policy Optimization for Multimodal Reasoning](https://mlsanity.com/paper/2604.09349/) (2026)
- [TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning](https://mlsanity.com/paper/2606.11119/) (2026)
- [Thinking with Map: Reinforced Parallel Map-Augmented Agent for Geolocalization](https://mlsanity.com/paper/2601.05432/) (2026)
- [FlowSteer: Towards Agents Designing Agentic Workflows via Reinforced Progressive Canvas Editing](https://mlsanity.com/paper/2602.01664/) (2026)
- [Exact Is Easier: Credit Assignment for Cooperative LLM Agents](https://mlsanity.com/paper/2603.06859/) (2026)
- [Generate, Filter, Control, Replay: A Comprehensive Survey of Rollout Strategies for LLM Reinforcement Learning](https://mlsanity.com/paper/2605.02913/) (2026)
- [Reinforced Efficient Reasoning via Semantically Diverse Exploration](https://mlsanity.com/paper/2601.05053/) (2026)
- [Learning Decentralized LLM Collaboration with Multi-Agent Actor Critic](https://mlsanity.com/paper/2601.21972/) (2026)
- [On Protecting Agentic Systems' Intellectual Property via Watermarking](https://mlsanity.com/paper/2602.08401/) (2026)
- [Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe](https://mlsanity.com/paper/2603.21972/) (2026)
- [CAPO: Critic-Guided Action-Aligned Policy Optimization for Advancing LLM Agent Capabilities](https://mlsanity.com/paper/2604.18401/) (2026)
- [TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents](https://mlsanity.com/paper/2602.11767/) (2026)
- [Thinking with Deltas: Incentivizing Reinforcement Learning via Differential Visual Reasoning Policy](https://mlsanity.com/paper/2601.06801/) (2026)
- [Learning from the Irrecoverable: Error-Localized Policy Optimization for Tool-Integrated LLM Reasoning](https://mlsanity.com/paper/2602.09598/) (2026)
- [Uno-Orchestra: Parsimonious Agent Routing via Selective Delegation](https://mlsanity.com/paper/2605.05007/) (2026)
- [SkillFlow: Flow-Driven Recursive Skill Evolution for Agentic Orchestration](https://mlsanity.com/paper/2605.14089/) (2026)
- [PBSD: Privileged Bayesian Self-Distillation for Long-Horizon Credit Assignment](https://mlsanity.com/paper/2606.09348/) (2026)
- [Tree Training: Accelerating Agentic LLMs Training via Shared Prefix Reuse](https://mlsanity.com/paper/2511.00413/) (2025)

## Abstract (arXiv)

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.