mlsanityData to 7 Oct 2026

Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning

arXiv 2605.05262 ↗First posted 6 May 2026stat.ML cs.AI cs.LGcited by 2

On the map: LLM reasoning → Reinforcement learning for reasoning

also in 1 more
Abstract (arXiv)

We formalize Rollout Informativeness under a Fixed Budget (RIFB) as the expected non-vanishing policy-gradient mass that a tool-use rollout set injects into Group Relative Policy Optimization (GRPO). We prove that any budget-agnostic independent sampler suffers a collapse rate bounded away from zero for hard prompts regardless of the budget. Motivated by this, we recast intermediate state selection as a monotone submodular maximization problem, where a greedy one-step selector enjoys a 1 minus 1/e approximation guarantee. Our Uncertainty-aware Upper Confidence Bound (UUCB) terms arise as closed-form marginal gains of this objective. This turns the token-level entropy bonus from an empirical trick into an analytic consequence of the formulation. We present InfoTree, a training-time tree-search framework coupling UUCB with a learned Adaptive Budget Allocator (ABA) and an asynchronous Speculative Expansion scheme. ABA rescues prompts whose initial tree is wasted on uniform outcomes, lifting the mixed-outcome ratio from 58.1 percent to 76.3 percent with less than 5 percent budget overhead. Speculative Expansion reduces wall-clock overhead from 14.3 percent to 4.8 percent by tolerating bounded staleness in UUCB scores. Across nine benchmarks spanning math reasoning (AIME 2024 and 2025, MATH-500, OlympiadBench, USAMO), web-search agents (GAIA, HLE-100, BrowseComp-lite), and tool-rich coding and OS agents (APPS-verified, AgentBench-OS), InfoTree outperforms flat GRPO, DeepSearch, Tree-GRPO, AT2PO, CW-GRPO, and RC-GRPO. Head-to-head compositions with Tree-GRPO prefix sharing and CW-GRPO contribution weights deliver further gains, confirming that our selector operates orthogonally to rollout reuse and trajectory re-weighting. A 5 by 5 by 5 robustness grid reveals that over three quarters of the hyperparameter space lies on a performance plateau, confirming UUCB robustness.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning. Builds on 21 of its 30 references that are in the map. First posted on arXiv 6 May 2026.

Builds on

21 of 30 references.

Closest ancestors · 10

Same direction, newest first

  1. 2026Enhancing LLM-based Search Agents via Contribution Weighted Group Relative Policy Optimization15 Apr
  2. 2026Dynamics-Predictive Sampling for Active RL Finetuning of Large Reasoning Models11 Mar
  3. 2026Train Less, Learn More: Adaptive Efficient Rollout Optimization for Group-Based Reinforcement Learning15 Feb
  4. 2026Self-Hinting Language Models Enhance Reinforcement Learning3 Feb
  5. 2026RC-GRPO: Reward-Conditioned Group Relative Policy Optimization for Multi-Turn Tool Calling Agents3 Feb
  6. 2025XRPO: Pushing the limits of GRPO with Targeted Exploration and Exploitation8 Oct
  7. 2025DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search29 Sep
  8. 2024ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search6 Jun
  9. 2023Let's Verify Step by Step31 May
  10. 2022Solving math word problems with process- and outcome-based feedback25 Nov

Other references · 11

  1. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  2. 2024HybridFlow: A Flexible and Efficient RLHF Frameworkcited by 1,980
  3. 2023Reasoning with Language Model is Planning with World Modelcited by 846
  4. 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Trainingcited by 291
  5. 2023Planning with Large Language Models for Code Generationcited by 179
  6. 2024Tree Search for Language Model Agentscited by 148
  7. 2025Tree Search for LLM Agent Reinforcement Learningcited by 73
  8. 2025Demystifying Reinforcement Learning in Agentic Reasoningcited by 32
  9. 2024MBA-RAG: a Bandit Approach for Adaptive Retrieval-Augmented Generation through Question Complexitycited by 28
  10. 2026TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAGcited by 5
  11. 2026ECHO: Entropy-Confidence Hybrid Optimization for Test-Time Reinforcement Learningcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026SIPO: Selective-Inference Policy Optimization for Tree-Structured Agentic RLcited by 0
  2. 2026Where the Model Changes Its Mind: Hindsight-Divergence Localization for Efficient Reinforcement Learning with Verifiable Rewardscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Information Gain-based Rollout Policy Optimization: An Adaptive Tree-Structured Rollout Approach for Multi-Turn LLM Agents
  2. 2026SAPO: Single-Rollout Autoregressive Policy Optimization for Agentic Reinforcement Learning
  3. 2026TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning
  4. 2026RTMC: Step-Level Credit Assignment via Rollout Trees
  5. 2026EPIG-Tree: Compute-Optimal Branching for Gradient-Efficient Reinforcement Learning
  6. 2026Process Reward Informed Tree Rollout for Effective Multi-Turn RL
  7. 2026Branching Policy Optimization: Sandbox-Native Language Agent Reinforcement Learning
  8. 2026Tool-Aware Optimization with Entropy Guidance for Efficient Agentic Reinforcement Learning