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

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

## Key facts

- Cited by 2 papers in the map (data through 14 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.

## Placed in

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

## Builds on (most cited first, 21 of 21)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Tree Search for Language Model Agents](https://mlsanity.com/paper/2407.01476/) (2024)
- [Tree Search for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21240/) (2025)
- [Demystifying Reinforcement Learning in Agentic Reasoning](https://mlsanity.com/paper/2510.11701/) (2025)
- [MBA-RAG: a Bandit Approach for Adaptive Retrieval-Augmented Generation through Question Complexity](https://mlsanity.com/paper/2412.01572/) (2024)
- [Self-Hinting Language Models Enhance Reinforcement Learning](https://mlsanity.com/paper/2602.03143/) (2026)
- [XRPO: Pushing the limits of GRPO with Targeted Exploration and Exploitation](https://mlsanity.com/paper/2510.06672/) (2025)
- [Train Less, Learn More: Adaptive Efficient Rollout Optimization for Group-Based Reinforcement Learning](https://mlsanity.com/paper/2602.14338/) (2026)
- [DeepSearch: Overcome the Bottleneck of Reinforcement Learning with Verifiable Rewards via Monte Carlo Tree Search](https://mlsanity.com/paper/2509.25454/) (2025)
- [RC-GRPO: Reward-Conditioned Group Relative Policy Optimization for Multi-Turn Tool Calling Agents](https://mlsanity.com/paper/2602.03025/) (2026)
- [Dynamics-Predictive Sampling for Active RL Finetuning of Large Reasoning Models](https://mlsanity.com/paper/2603.10887/) (2026)
- [Enhancing LLM-based Search Agents via Contribution Weighted Group Relative Policy Optimization](https://mlsanity.com/paper/2604.14267/) (2026)
- [TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG](https://mlsanity.com/paper/2601.06922/) (2026)
- [ECHO: Entropy-Confidence Hybrid Optimization for Test-Time Reinforcement Learning](https://mlsanity.com/paper/2602.02150/) (2026)

## Built on by (most cited first, 2 of 2)

- [SIPO: Selective-Inference Policy Optimization for Tree-Structured Agentic RL](https://mlsanity.com/paper/2609.34805/) (2026)
- [Where the Model Changes Its Mind: Hindsight-Divergence Localization for Efficient Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2609.36864/) (2026)

## 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.