通过子模优化提升工具使用智能体的搜索效率，显著减少资源浪费。
Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning
- 将状态选择建模为子模最大化问题，用贪心策略保证近似最优。
- 在多个基准上性能超越现有方法，混合结果比例提升至76.3%。
- 适合需要高效推理与资源受限场景的智能体系统设计者。
我们将固定预算下的滚动信息量（RIFB）定义为工具使用滚动集对组相对策略优化（GRPO）注入的非消失梯度质量期望。证明了任何无预算感知的独立采样器在困难提示下均存在远离零的崩溃率。为此，我们将中间状态选择重构为单调子模最大化问题，贪心一步选择器具备1−1/e的近似保证。不确定性感知的上置信界（UUCB）项由此目标的闭式边际增益自然导出，使词级熵奖励从经验技巧变为理论推论。我们提出InfoTree框架，结合UUCB与学习到的自适应预算分配器（ABA）及异步推测扩展机制。ABA使混合结果比例从58.1%提升至76.3%，预算开销不足5%；推测扩展将墙钟开销从14.3%降至4.8%。在涵盖数学推理（AIME 2024/2025、MATH-500、OlympiadBench、USAMO）、网页搜索代理（GAIA、HLE-100、BrowseComp-lite）和工具丰富的编码与操作系统代理（APPS-verified、AgentBench-OS）的九个基准上，InfoTree优于平铺式GRPO、DeepSearch、Tree-GRPO、AT2PO、CW-GRPO与RC-GRPO。与共享前缀的Tree-GRPO及基于贡献权重的CW-GRPO对比显示进一步增益，证实所提选择器与轨迹复用、重加权正交。5×5×5鲁棒性网格表明，超参数空间中超过四分之三区域位于性能平台，验证了UUCB的鲁棒性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。