mlsanityData to 7 Oct 2026

Tree Search for LLM Agent Reinforcement Learning

arXiv 2509.21240 ↗First posted 25 Sep 2025cs.LG cs.AIcited by 73

On the map: LLM agents and tool use → Reinforcement learning for LLM agents

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.

Key facts. Cited by 73 papers in the map (data through 7 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.

Builds on

72 of 86 references.

Closest ancestors · 12

Same direction, newest first

  1. 2025Scaling up Multi-Turn Off-Policy RL and Multi-Agent Tree Search for LLM Step-Provers8 Sep
  2. 2025The Landscape of Agentic Reinforcement Learning for LLMs: A Survey2 Sep
  3. 2025SimpleTIR: End-to-End Reinforcement Learning for Multi-Turn Tool-Integrated Reasoning2 Sep
  4. 2025Agentic Reinforced Policy Optimization26 Jul
  5. 2025Group-in-Group Policy Optimization for LLM Agent Training16 May
  6. 2025Iterative Tool Usage Exploration for Multimodal Agents via Step-wise Preference Tuning30 Apr
  7. 2025Agentic Reasoning and Tool Integration for LLMs via Reinforcement Learning28 Apr
  8. 2025RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning24 Apr
  9. 2025ToolRL: Reward is All Tool Learning Needs16 Apr
  10. 2025ReTool: Reinforcement Learning for Strategic Tool Use in LLMs15 Apr
  11. 2025ToRL: Scaling Tool-Integrated RL30 Mar
  12. 2025Process Reward Models for LLM Agents: Practical Framework and Directions14 Feb

Other references · 60

  1. 2024The Llama 3 Herd of Modelscited by 14,192
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  3. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,355
  4. 2025Qwen3 Technical Reportcited by 8,195
  5. 2024Qwen2.5 Technical Reportcited by 4,713
  6. 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,779
  7. 2018HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answeringcited by 3,686
  8. 2023Let's Verify Step by Stepcited by 3,598
  9. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  10. 2017TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehensioncited by 2,895
  11. 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scalecited by 2,678
  12. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
38 more
  1. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 1,916
  2. 2025Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learningcited by 1,371
  3. 2020Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Stepscited by 1,259
  4. 2022Text Embeddings by Weakly-Supervised Contrastive Pre-trainingcited by 1,216
  5. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,193
  6. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,173
  7. 2022When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memoriescited by 1,103
  8. 2023GAIA: a benchmark for General AI Assistantscited by 1,084
  9. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,054
  10. 2024Tulu 3: Pushing Frontiers in Open Language Model Post-Trainingcited by 988
  11. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 895
  12. 2021MuSiQue: Multihop Questions via Single-hop Question Compositioncited by 893
  13. 2025Group Sequence Policy Optimizationcited by 788
  14. 2025SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-trainingcited by 655
  15. 2025BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agentscited by 616
  16. 2023Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Modelscited by 551
  17. 2025Process Reinforcement through Implicit Rewardscited by 478
  18. 2025Search-o1: Agentic Search-Enhanced Large Reasoning Modelscited by 423
  19. 2024ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Searchcited by 338
  20. 2025WebThinker: Empowering Large Reasoning Models with Deep Research Capabilitycited by 320
  21. 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Trainingcited by 291
  22. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoningcited by 267
  23. 2024Step-DPO: Step-wise Preference Optimization for Long-chain Reasoning of LLMscited by 265
  24. 2023A Survey of Reinforcement Learning from Human Feedbackcited by 259
  25. 2024Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learningcited by 238
  26. 2023Large Language Model Guided Tree-of-Thoughtcited by 218
  27. 2025ZeroSearch: Incentivize the Search Capability of LLMs without Searchingcited by 203
  28. 2024DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Searchcited by 189
  29. 2025WebDancer: Towards Autonomous Information Seeking Agencycited by 180
  30. 2025WebWalker: Benchmarking LLMs in Web Traversalcited by 171
  31. 2024VinePPO: Refining Credit Assignment in RL Training of LLMscited by 168
  32. 2018RUDDER: Return Decomposition for Delayed Rewardscited by 162
  33. 2024Tree Search for Language Model Agentscited by 148
  34. 2025GPG: A Simple and Strong Reinforcement Learning Baseline for Model Reasoningcited by 147
  35. 2025Beyond Ten Turns: Unlocking Long-Horizon Agentic Search with Large-Scale Asynchronous RLcited by 144
  36. 2025BFS-Prover: Scalable Best-First Tree Search for LLM-based Automatic Theorem Provingcited by 82
  37. 2025StepSearch: Igniting LLMs Search Ability via Step-Wise Proximal Policy Optimizationcited by 82
  38. 2025Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Modelscited by 75

50 most cited of 60 All 60 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 67.

73 papers.

Sort:

By area:

  1. 2026A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agentscited by 47
  2. 2025Agentic Entropy-Balanced Policy Optimizationcited by 39
  3. 2025Agent-R1: A Unified and Modular Framework for Agentic Reinforcement Learningcited by 28
  4. 2026Code2World: A GUI World Model via Renderable Code Generationcited by 26
  5. 2025Video-STAR: Reinforcing Open-Vocabulary Action Recognition with Toolscited by 23
  6. 2026Harder Is Better: Boosting Mathematical Reasoning via Difficulty-Aware GRPO and Multi-Aspect Question Reformulationcited by 18
  7. 2025On Group Relative Policy Optimization Collapse in Agent Search: The Lazy Likelihood-Displacementcited by 15
  8. 2026Mem-T: Densifying Rewards for Long-Horizon Memory Agentscited by 14
  9. 2026PivotRL: High Accuracy Agentic Post-Training at Low Compute Costcited by 12
  10. 2026Crab: A Semantics-Aware Checkpoint/Restore Runtime for Agent Sandboxescited by 11
  11. 2026Visually-Guided Policy Optimization for Multimodal Reasoningcited by 10
  12. 2026Exact Is Easier: Credit Assignment for Cooperative LLM Agentscited by 9
38 more
  1. 2026TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learningcited by 9
  2. 2026LongHorizon-Harness: Advancing Long-Horizon Agents for Real-World Taskscited by 9
  3. 2026Reinforced Efficient Reasoning via Semantically Diverse Explorationcited by 8
  4. 2026Thinking with Map: Reinforced Parallel Map-Augmented Agent for Geolocalizationcited by 8
  5. 2026CAPO: Critic-Guided Action-Aligned Policy Optimization for Advancing LLM Agent Capabilitiescited by 8
  6. 2026Generate, Filter, Control, Replay: A Comprehensive Survey of Rollout Strategies for LLM Reinforcement Learningcited by 8
  7. 2026Shepherd: Enabling Programmable Meta-Agents via Reversible Agentic Execution Tracescited by 8
  8. 2026Learning Decentralized LLM Collaboration with Multi-Agent Actor Criticcited by 7
  9. 2026FlowSteer: Towards Agents Designing Agentic Workflows via Reinforced Progressive Canvas Editingcited by 7
  10. 2026On Protecting Agentic Systems' Intellectual Property via Watermarkingcited by 7
  11. 2026Thinking with Deltas: Incentivizing Reinforcement Learning via Differential Visual Reasoning Policycited by 6
  12. 2026TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agentscited by 6
  13. 2026Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipecited by 6
  14. 2026SkillFlow: Flow-Driven Recursive Skill Evolution for Agentic Orchestrationcited by 6
  15. 2026PBSD: Privileged Bayesian Self-Distillation for Long-Horizon Credit Assignmentcited by 6
  16. 2026Learning from the Irrecoverable: Error-Localized Policy Optimization for Tool-Integrated LLM Reasoningcited by 5
  17. 2026PAIR: Prefix-Aware Internal Reward Model for Multi-Turn Agent Optimizationcited by 5
  18. 2025Tree Training: Accelerating Agentic LLMs Training via Shared Prefix Reusecited by 4
  19. 2026ECHO: Entropy-Confidence Hybrid Optimization for Test-Time Reinforcement Learningcited by 4
  20. 2026Optimizing CUDA like a Human: Micro-Profiling Tools as Expert Surrogates for LLM-Based GPU Kernel Optimizationcited by 4
  21. 2026TopoCurate:Modeling Interaction Topology for Tool-Use Agent Trainingcited by 3
  22. 2026Self-Induced Outcome Potential: Turn-Level Credit Assignment for Agents without Verifierscited by 3
  23. 2026Learning Agentic Policy from Action Guidancecited by 3
  24. 2026APPO: Agentic Procedural Policy Optimizationcited by 3
  25. 2026GraphPO: Graph-based Policy Optimization for Reasoning Modelscited by 3
  26. 2025Iterative GRPO: Batch-Online Multi-Turn RL via Single-Turn RLHFcited by 2
  27. 2026Believe Your Model: Distribution-Guided Confidence Calibrationcited by 2
  28. 2026GeoSolver: Scaling Test-Time Reasoning in Remote Sensing with Fine-Grained Process Supervisioncited by 2
  29. 2026Uno-Orchestra: Parsimonious Agent Routing via Selective Delegationcited by 2
  30. 2026Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learningcited by 2
  31. 2026StraTA: Incentivizing Agentic Reinforcement Learning with Strategic Trajectory Abstractioncited by 2
  32. 2026Ace-Skill: Bootstrapping Multimodal Agents with Prioritized and Clustered Evolutioncited by 2
  33. 2026Self-Improving Language Models with Bidirectional Evolutionary Searchcited by 2
  34. 2026Agent Reinforcement Learning via Pivotal-Aware Self-Feedback Retrycited by 2
  35. 2026Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agentscited by 2
  36. 2026Optimizing What Policies Learn From: Recoverability-aware Rollout Intervention Learningcited by 2
  37. 2026TL-GRPO: Turn-Level RL for Reasoning-Guided Iterative Optimizationcited by 1
  38. 2026Can David Beat Goliath? On Multi-Hop Reasoning with Resource-Constrained Agentscited by 1

50 most cited of 73 All 73 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2026TreeAdv: Tree-Structured Advantage Redistribution for Group-Based RL
  2. 2026AT2PO: Agentic Turn-based Policy Optimization via Tree Search
  3. 2026Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning
  4. 2026Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization
  5. 2026Enhancing LLM-based Search Agents via Contribution Weighted Group Relative Policy Optimization
  6. 2026Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning
  7. 2026PlanPO: Group Planning-Aware Policy Optimization for Multi-Turn Agentic LLMs
  8. 2025Tree-OPO: Off-policy Monte Carlo Tree-Guided Advantage Optimization for Multistep Reasoning