Contrastive Branch Policy Optimization

# 对比分支策略优化

来源：https://arxiv.org/html/2608.24300

CCS：计算方法  
强化学习

CCS：计算方法  
智能体

王颖  
单位：阿里巴巴集团，中国杭州  
单位：哈尔滨工业大学，中国哈尔滨  
邮箱：[[email protected]](mailto:[email protected])

邱常林  
注：通讯作者：邱常林  
邮箱：[[email protected]](mailto:[email protected])  
单位：阿里巴巴集团，中国杭州  
邮箱：[[email protected]](mailto:[email protected])

林邦  
单位：阿里巴巴集团，中国杭州  
邮箱：[[email protected]](mailto:[email protected])

金林波  
单位：阿里巴巴集团，中国杭州  
邮箱：[[email protected]](mailto:[email protected])

姜文  
单位：阿里巴巴集团，中国杭州  
邮箱：[[email protected]](mailto:[email protected])

孙哲  
单位：阿里巴巴集团，中国杭州  
邮箱：[[email protected]](mailto:[email protected])

杨景丽  
单位：哈尔滨工业大学，中国哈尔滨  
邮箱：[[email protected]](mailto:[email protected])

###### 摘要

带有可验证奖励的强化学习使语言模型能够学习与外部工具进行多轮交互，但其稀疏的结果奖励无法为识别哪些中间决策对成功负责提供信号。分支采样在替代续写之间引入局部比较，但现有方法往往混淆了两个不同的问题：分配固定的采样预算以及将分支结果转化为词元级别的信用分配。我们引入**对比分支策略优化**，将这两个问题解耦并为每个问题分配专门的机制。生成熵在整个响应中筛选候选分支位置，而路径级和节点级衰减在轨迹和位置上分配固定预算，以防止探索坍缩到少数路径或相邻词元上。一条父轨迹及其共享相同词元前缀的分支构成一个**精确前缀组**，该受控组内的奖励变化定义了**对比分支价值**，这是一种基于结果的局部决策敏感性估计，它在不改变续写优势符号的前提下重新调整其大小。当沿同一轨迹选择多个节点时，CBPO将其划分为非重叠的信用段，从而避免对共享词元产生重复梯度。CBPO仅需要结果奖励而不需要过程级标注，为工具集成智能体训练中的细粒度信用分配提供了实用解决方案。在十个基准上的广泛实验——五个用于数学推理，五个用于知识密集型搜索——表明，CBPO始终优于最先进的策略优化和基于分支的方法，在两个领域和两种模型规模上都达到了最高的宏观平均准确率。

###### 关键词：强化学习，大语言模型，工具集成推理，信用分配

## 1. 引言

链式思维提示和带有可验证奖励的强化学习已经显著提升了大语言模型的推理能力。然而，许多任务需要当前信息、精确计算或来自外部环境的反馈。解决此类任务需要与搜索引擎、代码解释器或两者进行多轮交互。最近的系统将强化学习应用于这些交互，包括需要协调使用多种工具的场景。然而，产生的训练信号仍然是粗糙的。大多数RLVR和智能体强化学习方法为轨迹中的每个生成词元分配单一的终端奖励。这种统一的信用无法区分决定性的工具请求或纠正与仅仅先于成功答案的文本。过程监督和逐步偏好优化提供了更细粒度的信号，但需要中间标签或偏好。基于树的采样则仅使用结果奖励比较来自共享历史的续写。然而，这种方法仍然需要一个有原则的策略，以便在有限预算下定位分支并将它们的结果映射到局部策略更新。现有方法仅部分解决了这些需求。GIGPO和Tree-GRPO从共享或树结构历史构建局部优势，而ARPO使用生成熵在工具反馈后选择分支点。熵提供了词元级别不确定性的廉价代理，但并不衡量结果敏感性。仅基于熵的分配可能将分支集中在相邻位置，忽略工具边界外的重要决策，或者强调不影响最终答案的变化。对比分支策略优化将候选发现与信用分配分离。CBPO在响应中扫描局部熵，并应用路径级和节点级衰减来分配固定的分支预算。一条父轨迹和共享相同词元前缀的分支构成一个精确前缀组。该受控组内的奖励变化定义了对比分支价值，这是一种基于结果的局部决策敏感性估计。有界形式的CBV改变了续写优势的大小，但不改变其符号。复制的前缀不接收分支梯度，多个分支节点将父轨迹划分为非重叠的信用段。因此，这两个信号服务于不同的功能：熵识别替代续写，而观察到的结果变化估计它们的任务相关性。评估涵盖两个模型规模，包括五个工具增强的数学基准和五个知识密集型搜索基准。CBPO始终优于最先进的策略优化和基于分支的方法，在两个领域都达到了最高的宏观平均。主要贡献如下：

- • 将分支选择表述为在整个响应上的预算化探索。固定间隔的熵窗口暴露了超出工具边界的候选者，而路径级和节点级衰减防止分配坍缩到少数轨迹或相邻位置。
- • CBV从精确前缀组内的奖励变化估计局部决策敏感性。标准化和有界的CBV调节续写优势而不改变其符号。前缀掩码和非重叠分割防止对共享词元重复分配信用。
- • 跨越十个基准和两种模型规模的实验表明，CBPO始终优于强大的策略优化和基于分支的基线。跨规模的消融研究进一步将这些增益归因于平衡的分支分配和基于结果对比的信用分配。

## 2. 相关工作

### 2.1 细粒度信用分配

PPO从轨迹级回报优化策略。基于GRPO的推理系统同样从每个完成的响应中得出一个优势。后续变体改进了优化稳定性或可扩展性，而GSPO将优化单元从词元移到了序列。这些方法直接从结果奖励进行训练，但没有区分关键的中间选择与弱相关的过渡文本。问题分解、计算纠正、工具选择和答案验证可能对多步解决方案做出不同的贡献。因此，分配单一的优势可能会同时强化有效决策和偶然行为。过程奖励和逐步偏好优化更直接地监督中间推理。偏好目标（如DPO）和词元熵方法提供了替代的局部信号。过程标签和学习到的价值估计可以提供密集反馈，但需要标注成本或估计误差。熵既不需要标注也不需要学习价值估计，但它衡量的是预测不确定性，而不是某个位置与最终奖励的经验关联性。基于树的方法重用前缀并从中间状态采样多个续写，从而以受控成本进行局部比较。在线变体从当前策略的后代、树内对比或循环历史中得出优势。熵可以以低计算成本识别不确定的候选者。此外，一小部分高熵词元可能主导有效更新。EAPO结合了奖励极性和词元熵。AEPO在采样和优化期间平衡熵，同时限制连续高熵位置的重复分支。这些方法使用不确定性来指导优化，但发散的词元分布不一定产生发散的结果。CBPO则将熵限制用于候选筛选，并通过共享相同前缀的续写之间的结果对比来估计局部信用。

### 2.2 工具集成推理

外部工具允许语言模型访问当前信息、执行精确计算并作用于环境。工具集成推理超越了是否调用工具的二元决策。模型必须选择工具、构建请求、确定何时调用、验证响应、整合结果并适当终止。搜索提供开放世界的证据，而代码解释器支持计算和程序化验证。协调两者需要在内部推理和外部操作之间进行重复转换，并处理新观察结果。该领域的工作已从提示推理和行动，发展到用于搜索、代码解释器以及多工具协调的强化学习。最近的WSDM研究训练自主的程序化智能体，并使用强化学习优化工具选择。与提示或监督模仿不同，强化学习可以通过环境反馈和终端结果优化完整的交互。然而，在长轨迹中，成功可能取决于调用前推理、请求构建、反馈解释或调用后综合。因此，工具返回边界只能捕获潜在关键位置的一个子集。知识密集型任务也依赖于检索质量和时机。当第一阶段候选池召回不足时，自适应检索可以超越初始排序。在基于LLM的事实核查中，自适应证据检索允许模型确定内部知识何时不足或与外部证据冲突。这些WSDM研究关注的是检索和验证，而不是词元级别的信用分配，但揭示了相同的结构性挑战。智能体必须确定何处的额外计算或证据可以改变最终结果。长期工具学习通常通过奖励塑形、过程监督或步骤级优化来改进规划或归因。中间监督成本高昂，而预定义状态和步骤边界限制了信用分配的粒度。GIGPO从共享历史中得出步骤级优势。ARPO在工具反馈后分支，并将产生的优势分配给后缀。前者依赖于重复的历史状态，后者将工具返回视为固定的分支边界。CBPO在完整响应中搜索分支候选，然后通过比较相同前缀下的结果来分配局部信用。

## 3. 预备知识

### 工具集成采样

给定来自数据集D的问题x和工具集T，策略πθ生成交互轨迹τ，其中交错出现模型词元、工具请求和环境观察。令z = (z₁, ..., z_{|z|})收集τ的模型生成词元，o₀, o₁, ..., o_{L-1}表示工具观察序列。模型在位置t生成的词元z_t的概率取决于先前的词元和观察：p(z_t | z_{<t}, o_{<t})。类似地，工具请求和观察的分布取决于当前上下文。采样在τ完成或达到最大长度L时终止。

### 带有分支的策略优化

我们考虑一个在带有工具的环境中训练的策略πθ，其目标是最大化轨迹τ的期望累积奖励：E[R(τ)]，其中R(τ)是结果奖励。标准策略梯度更新为∇θ E[R(τ)] = E[∑_t ∇θ log πθ(a_t | s_t) · A_t]，其中a_t是动作（词元），s_t是状态（历史），A_t是优势。对于结果奖励，通常使用单步优势A_t = R(τ) - b，其中b是基线。为了引入分支，我们在每个轨迹τ上维护一组候选分支点。对于每个候选位置i，我们采样K_i个替代续写，每个续写从位置i继续生成直到结束，从而产生一组扩展轨迹。对于每个扩展轨迹，我们计算结果奖励。通过比较共享前缀但具有不同续写的轨迹的奖励，我们为候选位置i估计局部优势。最后，我们将这些局部优势与原始的全轨迹优势结合，以更新策略。

### 对比分支价值

关键问题是如何从一组扩展轨迹的奖励中估计一个位置i的重要性。我们定义精确前缀组G_i为共享相同词元前缀直到位置i的所有轨迹的集合。该组包括父轨迹（我们将其视为“基准”或“锚点”续写）和K_i个采样的分支续写。设r_p为父轨迹的奖励，{r_1, ..., r_{K_i}}为分支的奖励。该组奖励的均值为μ_i = (r_p + ∑_k r_k) / (K_i + 1)。我们定义**对比分支价值**为该组奖励的方差：CBV_i = Var(G_i) = [ (r_p - μ_i)² + ∑_k (r_k - μ_i)² ] / (K_i + 1)。CBV_i衡量了在固定前缀i之后，改变续写对最终结果的影响程度。高CBV表示该位置是一个关键决策点。为了稳定训练，我们对CBV应用有界变换，例如使用分位数归一化或裁剪。具体地，我们计算批内所有位置的CBV统计量，并定义缩放后的CBV：Z_i^{CBV} = (CBV_i - median(CBV)) / σ_{CBV}，其中σ_{CBV}是标准差。然后，我们应用一个有界函数，如双曲正切或符号函数加幅度缩放，确保缩放后的值Z_i^{CBV}在[-C, C]之间。如果Z_i^{CBV} > 0，表示该位置的决策变化导致了奖励变化高于平均水平；如果Z_i^{CBV} < 0，表示变化低于平均水平。最后，我们将此信号整合到优势估计中。对于分支k在位置i的续写，其优势调整为A_{i,k}^{CBPO} = A_{i,k}^{base} · (1 + λ · Z_i^{CBV})，其中A_{i,k}^{base}是仅基于结果奖励的基线优势（例如，分支k的奖励减去基线），λ是缩放超参数。注意，如果Z_i^{CBV} > 0，我们放大该分支的优势（无论正负），如果Z_i^{CBV} < 0，则缩小优势。这样，CBPO强化了在关键决策点处导致更好结果的续写，同时弱化了在不敏感点处的更新。

### 信用分配

CBV在组级别识别了相对结果敏感性，但优化器仍然需要词元级别的优势。问题级GRPO归一化首先为每条轨迹生成基础优势A_{i,k}。节点i处的共同前缀接收组均值优势：
A_i^{shared} = 1/(K_i + 1) ∑_{k=0}^{K_i} A_{i,k}
对于分支k从位置i开始的后缀（词元序列），我们分配对应于每个词元的调整后优势。具体地，对于位置j > i的后缀中的词元z_j，其优势为A_j^{branch} = A_{i,k}^{CBPO}。然而，如果多个分支节点共享相同的词元前缀，我们需要确保这些共享词元不会收到重复的梯度。我们通过将轨迹划分为非重叠的信用段来实现这一点。给定沿轨迹选择的分支节点索引集合{i_1, i_2, ..., i_m}（按顺序排列），我们为每个节点定义一个信用区间。第一个信用区间是[0, i_1]，对应于所有词元z_0到z_{i_1}。这些词元的优势是所有分支（包括父轨迹）在位置i_1处优势的平均值：A_j^{shared} = A_{i_1}^{shared}，对于j ≤ i_1。下一个信用区间是(i_1, i_2]，对应于词元z_{i_1+1}到z_{i_2}。对于这个区间内的词元，我们考虑从节点i_1分支出来的特定分支续写。设k^*为从节点i_1导出并延续到节点i_2的分支索引（在多个分支中，我们需要选择一条路径，通常选择奖励最高的或随机采样的路径）。然后，该区间内词元的优势设置为A_j^{branch} = A_{i_1, k^*}^{CBPO}，对于i_1 < j ≤ i_2。以此类推，最后一个信用区间从最后一个分支节点i_m到轨迹结束。这种方法确保了每个词元只从一个信用段接收优势，避免了重复信用。前缀掩码（在共享前缀部分使用共享优势）进一步确保了在多个分支重叠的区域，更新是一致的。

### 优化目标

我们使用策略梯度更新（如PPO或GRPO）来优化策略πθ。在每次迭代中，我们为一批问题采样轨迹，运行分支采样，计算所有轨迹和分支的奖励，然后计算基础优势和CBV缩放后的优势。最终的词元级优势按照上述信用分配方案计算。然后，我们执行标准的策略梯度更新，最大化以下目标：J(θ) = E_{(τ, A)} [ ∑_t log πθ(a_t | s_t) · A_t ]，其中A_t是计算出的词元级优势。我们使用裁剪或熵正则化来稳定训练。重要的是，CBPO的开销主要在于分支采样和奖励计算，这在许多工具集成任务中是必要的，并且可以并行化。

### 详细算法

算法1描述了CBPO的训练循环。

**算法1：对比分支策略优化（CBPO）**
输入：策略模型πθ，工具集T，数据集D，批大小B，最大分支数K，衰减因子λ。
输出：训练后的策略πθ。

1: for iteration = 1 to N do
2:   从D采样一批问题{x_1, ..., x_B}
3:   for each x_i in the batch do
4:     使用πθ生成轨迹τ_i，与工具交互，直到完成或达到最大长度。
5:     记录所有词元、工具请求和观察。
6:     计算结果奖励R(τ_i)。
7:     选择候选分支位置。使用生成熵：对于每个词元位置t，计算条件熵H_t = -∑_v p(v) log p(v)，其中p(v)是下一个词元v的概率。选择熵最高的B个位置（或熵超过阈值的），最多K个。
8:     for each candidate position i in τ_i do
9:       从位置i开始采样K_i个替代续写（例如，K_i = K），使用πθ生成直到结束。对于每个续写，与工具交互并计算奖励。得到一组扩展轨迹。
10:      计算该精确前缀组G_i的奖励和：CBV_i = Var(G_i)。
11:    end for
12:    批量归一化所有轨迹的CBV值，计算Z_i^{CBV}。
13:    对于每个轨迹τ_i，将分支节点排序：i_1 < i_2 < ... < i_m。
14:    计算基础优势A_{i,k}^{base} = R(扩展轨迹) - b，其中b是基线（例如，批内平均奖励）。
15:    对于每个节点i_k，计算缩放后的优势A_{i_k, j}^{CBPO} = A_{i_k, j}^{base} * (1 + λ * Z_{i_k}^{CBV})。
16:    为轨迹τ_i中的每个词元分配信用：
       - 对于t ≤ i_1：A_t = 1/(K_{i_1}+1) ∑_{j=0}^{K_{i_1}} A_{i_1, j}^{CBPO}
       - 对于i_k < t ≤ i_{k+1}：选择从i_k延续到i_{k+1}的分支续写j^*（例如，奖励最高的），A_t = A_{i_k, j^*}^{CBPO}
       - 对于t > i_m：选择从i_m延续到最后的分支续写j^*，A_t = A_{i_m, j^*}^{CBPO}
17:   end for
18:  使用计算出的词元级优势{A_t}更新策略πθ（例如，使用PPO或GRPO目标）。
19: end for

### 工具集成推理的实现考虑

在CBPO的上下文中，工具集成推理带来了特定挑战。工具调用和响应引入了“黑盒”步骤，其内部状态可能不可见。CBPO通过将分支点放置在这些边界处或内部来处理这个问题。生成熵有助于识别模型不确定的地方，可能是在工具调用之前或之后。此外，工具反馈可能会显著改变上下文。CBPO的路径级衰减有助于防止在工具调用后立即分支过多，因为那里可能只是对工具输出的简单反应。节点级衰减鼓励在长工具交互链中更均匀地探索不同的决策点。精确前缀组自然地处理了工具调用，因为工具请求和响应是词元序列的一部分，因此包含在前缀中。

### 与现有分支方法的比较

与GIGPO相比，CBPO不依赖于重复的历史状态来推导优势，而是通过精确前缀组进行显式对比。这提供了更直接的决策敏感性度量。与Tree-GRPO相比，CBPO的分支预算分配更灵活，由熵和衰减驱动，而不是固定的树结构。与ARPO相比，CBPO不限于在工具反馈后分支，而是可以探索整个响应。此外，CBPO的CBV提供了比仅依赖熵或固定步骤边界更丰富的信用信号。

### 计算复杂度分析

CBPO引入了额外的开销，主要来自分支采样和奖励计算。在最佳情况下，如果我们每个轨迹采样B个分支点，每个分支点采样K个续写，则开销为O(B*K)倍的基础采样成本。然而，在实践中，许多分支点可能被衰减因子过滤掉，或者熵窗口限制了候选者数量。此外，分支可以并行生成和评估。由于工具集成推理已经需要多次环境交互，额外的分支采样可能只增加适度的成本，特别是如果续写较短（例如，在工具调用后分支）。CBPO的收益（更有效的信用分配）通常证明了这种额外成本是合理的。