固定预算下最大化轨迹信息量：工具使用智能体强化学习的次模树搜索视角
Maximizing Rollout Informativeness under a Fixed Budget: A Submodular View of Tree Search for Tool-Use Agentic Reinforcement Learning
摘要
我们将固定预算（RIFB）下的采样轨迹信息量正式化为工具使用采样轨迹集注入到组相对策略优化（GRPO）中的预期不消失的政策梯度质量。我们证明，无论预算如何，任何与预算无关的独立采样器都会因硬提示而遭受远离零的崩溃率。受此启发，我们将中间状态选择重新定义为单调子模最大化问题，其中贪婪的单步选择器享有 1 - 1/e 近似保证。我们的不确定性感知上限（UUCB）项作为该目标的封闭式边际收益而出现。这将 词元级 熵奖励从经验技巧转变为公式的分析结果。我们提出了 InfoTree，一种将 UUCB 与学习自适应预算分配器 (ABA) 和异步推测扩展方案相结合的训练时树搜索框架。 ABA 拯救了那些最初的树被浪费在统一结果上的提示，将混合结果比率从 58.1% 提高到 76.3%，而预算开销不到 5%。推测扩展通过容忍 UUCB 分数中有限的陈旧性，将挂钟开销从 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 x 5 x 5 的稳健性网格显示，超过四分之三的超参数空间处于性能稳定状态，证实了 UUCB 的稳健性。