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

• URL: http://arxiv.org/abs/2605.05262v1
• Date: Wed, 06 May 2026 06:17:48 GMT
• Title: Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning
• Abstract summary: We prove that any budget-agnostic independent sampler suffers a collapse rate bounded away from zero for hard prompts regardless of the budget.<n>Our Uncertainty-aware Upper Confidence Bound (UUCB) terms arise as closed-form marginal gains of this objective.<n>We present InfoTree, a training-time tree-search framework coupling UUCB with a learned Adaptive Budget Allocator (ABA) and an asynchronous Speculative Expansion scheme.
• Score: 21.974153439592317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Why Sample What You Can Enumerate? Exact Policy Optimization for Genomic Tool Selection [23.92446384027772]
  Reinforcement learning over a frozen reasoner has become a common recipe for teaching a policy which external tools invoke.<n>We show that this recipe becomes structurally mismatched in specialist scientific settings where the complete tool-subset space is enumerable.<n>We introduce FGPO, which scores every tool subset and optimize the exact action expectation, so each update sees the complete action space.
  arXiv  Detail & Related papers  (2026-09-09T14:20:47Z)
• Threshold-Based Selection for Continuous Optimization: A Leaf-Abscission Instantiation [1.827510863075184]
  Leaf Abscission Optimization (LAO) uses rank-based strength, a phenological seasonal signal, diversity modulation, environmental pressure, and a base regrowth kernel.<n>This paper formalizes threshold-based selection as an evaluation-gating architecture in which each incumbent is tested before variation and a replacement is generated and evaluated only when contextual pressure exceeds strength.
  arXiv  Detail & Related papers  (2026-09-06T17:41:35Z)
• Unifying Depth and Width Pruning for LLMs via Binary Knapsack Optimization [22.700846957818687]
  Structured pruning is a promising approach for compressing large language models (LLMs)<n>We present SNIPER, a two-stage structured pruning framework that solves a knapsack optimization over coarse-granularity components.<n>We demonstrate SNIPER's consistent improvements in average performance retention and task-level stability over six state-of-the-art pruners.
  arXiv  Detail & Related papers  (2026-08-13T08:32:18Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Knowledge Index of Noah's Ark [63.143852586221534]
  We introduce KINA, an 899-item benchmark across 261 fine-grained disciplines.<n>We prove a bonus-on-bar tournament weakly FOSD-dominates flat payment in released-review quality.<n>The top model, Gemini-3.1-Pro-Preview, reaches 53.17%, followed by Claude-Opus-4.6 at 49.92% and GPT-5.4 at 48.55%.
  arXiv  Detail & Related papers  (2026-06-03T17:06:49Z)
• Agentic Forecasting using Sequential Bayesian Updating of Linguistic Beliefs [1.7470133607730627]
  BLF (Bayesian Linguistic Forecaster) is an agentic system for binary forecasting.<n>On 400 backtesting questions from the ForecastBench leaderboard, BLF outperforms all the top public methods.
  arXiv  Detail & Related papers  (2026-04-20T17:57:51Z)
• Adaptive Query Routing: A Tier-Based Framework for Hybrid Retrieval Across Financial, Legal, and Medical Documents [0.0]
  Retrieval-Augmented Generation (RAG) has become the standard paradigm for grounding Large Language Model outputs in external knowledge.<n>This paper extends their work by evaluating three retrieval architectures: Vector RAG, Tree Reasoning, and the proposed Adaptive Hybrid Retrieval (AHR) across financial legal legal domains.
  arXiv  Detail & Related papers  (2026-04-14T10:48:13Z)
• FIPO: Eliciting Deep Reasoning with Future-KL Influenced Policy Optimization [84.58281577727566]
  We present Future-KL Influenced Policy Optimization (FIPO), a reinforcement learning algorithm designed to overcome reasoning bottlenecks in large language models.<n>FIPO addresses this by incorporating discounted future-KL divergence into the policy update, creating a dense advantage formulation that re-weights tokens based on their influence on subsequent trajectory behavior.<n> evaluated on Qwen2.5-32B, FIPO extends the average chain-of-thought length from roughly 4,000 to over 10,000 tokens and increases AIME 2024 Pass@1 accuracy from 50.0% to a peak of 58.0%.
  arXiv  Detail & Related papers  (2026-03-20T10:24:50Z)
• Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents [40.18150559561834]
  Budget-Aware Value Tree (BAVT) is a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree.<n>BAVT consistently outperforms parallel sampling baselines.
  arXiv  Detail & Related papers  (2026-03-13T04:10:27Z)
• Budget-Sensitive Discovery Scoring: A Formally Verified Framework for Evaluating AI-Guided Scientific Selection [0.0]
  Budget-Sensitive Discovery Score (BSDS) penalizes false discoveries at each budget level.<n>Discovery Quality Score (DQS) provides a single summary statistic that no proposer can inflate by performing well at a cherry-picked budget.<n> framework applies to any setting where candidates are selected under budget constraints and asymmetric error costs.
  arXiv  Detail & Related papers  (2026-03-12T18:09:53Z)
• Unbiased Dynamic Pruning for Efficient Group-Based Policy Optimization [60.87651283510059]
  Group Relative Policy Optimization (GRPO) effectively scales LLM reasoning but incurs prohibitive computational costs.<n>We propose Dynamic Pruning Policy Optimization (DPPO), a framework that enables dynamic pruning while preserving unbiased gradient estimation.<n>To mitigate the data sparsity induced by pruning, we introduce Dense Prompt Packing, a window-based greedy strategy.
  arXiv  Detail & Related papers  (2026-03-04T14:48:53Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• AT$^2$PO: Agentic Turn-based Policy Optimization via Tree Search [19.443576967819684]
  LLM agents have emerged as powerful systems for tackling multi-turn tasks by interleaving internal reasoning and external tool interactions.<n>We present AT$2$PO, a unified framework for multi-turn agentic RL that addresses three core challenges: limited exploration diversity, sparse credit assignment, and misaligned policy optimization.
  arXiv  Detail & Related papers  (2026-01-08T09:35:49Z)
• Towards a Science of Scaling Agent Systems [79.64446272302287]
  We formalize a definition for agent evaluation and characterize scaling laws as the interplay between agent quantity, coordination structure, modelic, and task properties.<n>We derive a predictive model using coordination metrics, that cross-validated R2=0, enabling prediction on unseen task domains.<n>We identify three effects: (1) a tool-coordination trade-off: under fixed computational budgets, tool-heavy tasks suffer disproportionately from multi-agent overhead, and (2) a capability saturation: coordination yields diminishing or negative returns once single-agent baselines exceed 45%.
  arXiv  Detail & Related papers  (2025-12-09T06:52:21Z)
• BranchGRPO: Stable and Efficient GRPO with Structured Branching in Diffusion Models [57.304411396229035]
  We present BranchGRPO, a method that restructures the rollout process into a branching tree.<n>On HPDv2.1 image alignment, BranchGRPO improves alignment scores by up to textbf16% over DanceGRPO.<n>A hybrid variant, BranchGRPO-Mix, further accelerates training to 4.7x faster than DanceGRPO without degrading alignment.
  arXiv  Detail & Related papers  (2025-09-07T12:53:06Z)
• TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
  TreePO is a self-guided rollout algorithm that views sequence generation as a tree-structured searching process.<n>TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity.
  arXiv  Detail & Related papers  (2025-08-24T16:52:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.