📊 statistics

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

本文介绍了 InfoTree，这是一种面向工具使用智能体强化学习的训练期树搜索框架，它将 rollout 的信息量形式化为子模最大化问题，从而推导出一种不确定性感知的选择策略（UUCB）和自适应预算分配器，进而在保持鲁棒性和效率的同时，在多种推理与工具使用基准测试中显著优于现有方法。

原作者： Yuelin Hu, Zhenbo Yu, Zhengxue Cheng, Wei Liu, Li Song

发布于 2026-05-08

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Yuelin Hu, Zhenbo Yu, Zhengxue Cheng, Wei Liu, Li Song

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试通过让机器人反复练习，教它如何解决复杂谜题（如数学问题或编程任务）。在人工智能领域，这种练习被称为“ rollout（ rollout）”。机器人尝试解决问题，如果正确则获得奖励，如果错误则受到惩罚。目标是从这些尝试中学习。

然而，存在一个大问题：“回声室”效应。

如果你让机器人对同一道难题尝试 16 次，它可能会连续 16 次给出完全相同的错误答案。或者，如果是一道简单谜题，它可能会连续 16 次给出完全相同的正确答案。在这两种情况下，机器人都学不到任何新东西，因为缺乏多样性。这就像让学生参加同一份选择题测试 16 次；如果每次都答错，他们并不会明白为什么错了，只会感到沮丧。

本文介绍了一种名为INFOTREE的新方法来解决这一问题。以下是其工作原理，辅以简单的类比：

1. 问题：“无聊的课堂”

作者将这种现象称为“坍缩”。如果机器人的所有尝试都完全相同，训练信号（即课程）就会消失。他们从数学上证明，无论让机器人尝试多少次（即使给予巨大的尝试预算），如果是难题，它最终都会陷入重复且无益的答案循环中。这就像一位老师只允许已经知道答案的学生举手，而那些不知道答案的学生永远没有机会学习。

2. 解决方案：“好奇的探索者”（次模最大化）

INFOTREE 不再让机器人随机选择答案，而是采用一种智能策略来选择下一步探索哪条路径。作者将这一过程视为一场**“最大化多样性”**的游戏。

他们使用了一个名为次模性的数学概念。可以将其想象为打包行李箱：

如果你装进一件衬衫，它会增加价值。
如果你装进第二件颜色完全相同的衬衫，它带来的新价值微乎其微。
但如果你装进一件不同的物品（比如帽子或鞋子），它就能带来巨大的新价值。

INFOTREE 就像一个聪明的打包者。它会审视机器人当前的尝试，并问道：“哪一步能给我们提供最多的新信息？”它不仅仅寻找“最好”的答案，而是寻找与其他答案不同的答案。

3. “智能选择器”的三种成分

为了决定探索哪条路径，该系统使用了一个公式（称为UUCB），混合了三种成分，就像炖一锅好汤的食谱：

“自信”成分（覆盖率）：“我们之前尝试过这条路径吗？”如果机器人很有信心且经常看到这条路径，它就不需要再次前往。
“好奇”成分（新颖性）：“我们曾经到过地图的这个部分吗？”如果一条路径是新的且未被探索，机器人会被鼓励前往那里。
“混乱”成分（对比/熵）：“这里的答案是否杂乱且各不相同？”系统主动寻找机器人感到困惑的地方，或者不同尝试导致不同结果的地方。这种“混乱”实际上是好消息，因为它意味着有很多东西可以学习。

通过平衡这三者，机器人避免了“无聊的课堂”，并确保每一次练习都能教会它一些新东西。

4. 安全网：“救援队”（自适应预算分配器）

有时，即使是智能选择器也会陷入困境。也许机器人如此困惑，以至于它尝试的每一条路径都通向死胡同。

解决方法：INFOTREE 拥有一个小小的“救援队”（自适应预算分配器）。它会监视机器人的练习情况。如果它发现机器人即将把所有时间浪费在死胡同上，救援队就会说：“停下！让我们做一个疯狂的大胆猜测，看看能否打破这种模式。”
结果：这挽救了原本会被浪费的训练过程，将一轮“无用”的练习转化为有用的练习。

5. 速度提升：“推测性扩展”

通常，这种智能选择过程非常缓慢，因为计算机必须等待一个计算完成才能开始下一个。

解决方法：INFOTREE 使用了一种“推测性”技巧。它让计算机在之前的计算完全结束之前就猜测下一步。如果猜测正确，那就太好了！如果错误，它只需回滚并重试。
结果：这使得整个过程快得多（减少了超过 10% 的浪费时间），因此机器人可以在更短的时间内学到更多。

总结

本文在九种不同类型的挑战上测试了这种新方法（INFOTREE），从解决高难度数学竞赛（如 AIME）到帮助机器人浏览网页和编写代码。

结果：

更好的学习：机器人学习速度显著加快，解决问题的数量超过了以往的方法。
不再浪费时间：它阻止了机器人陷入重复答案的循环。
鲁棒性：即使设置发生轻微变化，该系统也能良好运行，这意味着它不是一个仅在完美条件下才有效的“脆弱”技巧。

简而言之，INFOTREE是一种通过确保 AI 智能体从不会重复练习同一个错误来教导它们的方法。它迫使它们探索问题空间中“混乱”和“不同”的部分，将徒劳的努力转化为宝贵的教训。

技术摘要：在固定预算下最大化 rollout 的信息量

1. 问题定义

本文针对工具增强型大语言模型（LLMs）在稀疏终端奖励（例如 $R \in \{-1, +1\}$ ）下的强化学习（RL）中存在的一个结构性瓶颈。核心问题是固定预算下的 rollout 信息量（RIFB）。

在标准的组相对策略优化（GRPO）中，优势信号通过对一组 $B$ 个 rollout 的奖励标准差进行归一化来生成。如果给定提示的 $B$ 个独立 rollout 均产生相同的结果（全部成功或全部失败），则标准差变为零，导致优势信号坍缩为零。因此，没有梯度质量被注入到策略中，使得在这些 rollout 上花费的计算资源变得无用。

作者将这一现象形式化为独立采样的不可能性结果：

定理 1： 对于任何与预算无关的独立采样器，发生坍缩（零方差）的概率为 $p^B + (1-p)^B$ ，其中 $p$ 是单个提示的成功概率。
推论： 当 $p \to 0$ 或 $p \to 1$ （困难提示）时，不坍缩的概率最多随预算 $B$ 线性增长（ $B \cdot \min(p, 1-p)$ ）。因此，单纯增加 rollout 预算 $B$ 无法使困难提示摆脱零梯度状态；无论预算大小如何，坍缩率始终被限制在远离零的水平。

2. 方法论：INFOTREE

为了克服独立采样的局限性，作者提出了INFOTREE，这是一种训练时的树搜索框架，旨在优化扩展哪些状态，而非采样多少个。

2.1 次模性形式化

核心见解在于，选择要扩展的中间状态以最大化树信息量的问题，可以被表述为一个单调次模最大化问题。目标函数 $F$ 由三项组成：

覆盖度（Coverage）： 追踪叶子节点的备份值 $\bar{Q}(s)$ 。
新颖性（Novelty）： 基于访问次数的探索项（经典的 UCB 项）。
对比度（Contrast）： 追踪兄弟节点之间结果的多样性，源自 token 级别的熵。

作者证明了 $F$ 是单调且次模的。这使得可以使用贪心选择器，并为最优扩展计划提供理论上的 $(1 - 1/e)$ 近似保证。

2.2 UUCB 选择器

次模问题的贪心解产生了**不确定性感知上置信界（UUCB）**分数，这并非经验启发式方法，而是目标函数的闭式边际增益：
$\text{UUCB}(v) = \bar{Q}(v) + c\sqrt{\frac{\ln N(p_a(v))}{N(v)+1}} + \lambda_H \tilde{H}(v) - \lambda_C \tilde{C}(v) - \lambda_D \tilde{d}(v)$

$\bar{Q}(v)$ ： 覆盖度增益。
第二项： 新颖性增益（标准 UCB 探索）。
$\lambda_H \tilde{H}(v)$ ： 对比度增益，代表深度分层的 token 级熵（归一化以便在不同深度间具有可比性）。
惩罚项： $\lambda_C$ 和 $\lambda_D$ 分别惩罚工具调用成本和扩展深度，以遵守预算约束。

2.3 系统组件

INFOTREE 将 UUCB 选择器与另外两种机制集成，以解决实际弱点：

自适应预算分配器（ABA）： 一个轻量级 MLP，离线训练以预测具有均匀结果树（可能坍缩）的提示是否可以通过单次高温 rollout“挽救”。如果预测的挽救概率超过阈值，则触发额外 rollout。这将混合结果比率从约 58% 提升至约 76%，且预算开销小于 5%。
推测性扩展： 为了降低实际运行时间延迟，工作节点使用可能过时的 Q 值（有界过时性）来评估 UUCB 分数。一个协调步骤根据版本标签接受或回滚扩展。这将开销从 14.3% 降低至 4.8%。
分层优势： 一种从根到叶路径上基于兄弟节点对比度导出的梯度信号，提供了一种替代的信用分配机制，补充了组归一化的 GRPO 优势。

3. 主要贡献

理论形式化： 本文定义了 RIFB，并证明了无论预算大小如何，独立采样在困难提示上都会遭受持续的坍缩。
次模归约： 确立了固定预算下的树构建是一个次模最大化问题，为贪心 UUCB 选择器提供了理论上的 $(1-1/e)$ 保证。
解析推导： 证明了 UUCB 中的熵奖励是次模目标（对比度项）的解析结果，而非经验技巧。
系统设计： 引入 ABA 和推测性扩展，构建了一个在信息量与计算效率之间取得平衡的实用框架。
正交性： 作者表明，他们的选择机制在轨迹重加权（如 CW-GRPO）和 rollout 复用（如 Tree-GRPO 前缀共享）的轴向上是正交的，从而允许组合增益。

4. 实验结果

该方法在数学推理、网络搜索以及富含工具的编码/操作系统代理等九个基准测试上进行了评估。

性能： INFOTREE 始终优于 Flat GRPO、DeepSearch、Tree-GRPO、AT2PO、CW-GRPO 和 RC-GRPO。
- 在 AIME 2025 上，INFOTREE 的 Mean@32 达到 30.2（Flat GRPO 为 27.7，Tree-GRPO 为 29.1）。
- 在 GAIA 上，其准确率达到 56.0%（Flat GRPO 为 44.8%）。
组合性： 将 INFOTREE 与 Tree-GRPO 前缀共享或 CW-GRPO 贡献权重结合可带来进一步增益，证实了这些方法的正交性。
鲁棒性： 对 UUCB 系数（ $\lambda_H, \lambda_C, \lambda_D$ ）进行 $5 \times 5 \times 5$ 超参数网格搜索显示，超过 75% 的空间位于最优值 2.1 分以内，表明该方法对超参数调整不敏感。
效率： 尽管进行了树搜索，但通过推测性扩展，实际运行时间开销降至 4.8%。“达到目标步数”（达到 Mean@32 为 28 所需的步数）从 248（Flat GRPO）降至 138（INFOTREE），实际运行时间提升了 1.57 倍。
梯度信息量： 对梯度范数平方的直接测量显示，INFOTREE 产生的 RIFB 比 Flat GRPO 高 3.9 倍。

5. 意义与主张

本文主张将 rollout 策略的设计从工程偏好重新定位为具有形式化基础的优化问题。

从启发式到理论： 该工作将熵奖励从经验技巧转变为次模目标的必要组成部分，为其包含提供了理论依据。
解决坍缩问题： 通过次模选择和自适应预算明确针对“零梯度”状态，INFOTREE 解决了当前基于 GRPO 的代理在困难提示上的根本局限性。
互补性： 结果表明，通过树构建最大化 rollout 信息量是一个独特且互补的维度，区别于现有专注于重加权或多样化独立样本的方法。

作者指出了局限性，包括在树构建过程中假设策略固定，以及在无验证奖励的开放任务上结果的初步性质。然而，该框架被呈现为在稀疏奖励下训练工具增强型代理的稳健解决方案。