arXiv 2607.15610v1 · 发布 2026-07-17

面向高效多轮强化学习的过程奖励引导树状推演

Process Reward Informed Tree Rollout for Effective Multi-Turn RL

AUTHORS Xintong Li, Sha Li, Yuwei Zhang, Changlong Yu, Rongmei Lin, Hongye Jin, Shuyi Guan, Xin Liu, Linwei Li, Qingyu Yin, Jingbo Shang

EVIDENCE 设计新的强化学习rollout算法并以过程奖励引导探索

SCORE 0.9

PDF ↗ 2607.15610v1.pdf

GENERATED 2026-07-25 21:37:44 UTC

📝 TLDR

面向LLM智能体的多轮强化学习，传统GRPO/RLOO在长视野任务中对完整轨迹独立均匀采样，预算浪费于无效死胡同且有潜力的中间状态缺乏探索。本文提出PATR框架，以过程评分器引导的自适应树形rollout，从高潜力中间状态选择性分支并复用共享前缀，保守终止退化路径。在SWE-Bench上取得+5.0分提升，在FrozenLake上提升+9.3分，证明过程引导的树形rollout是多轮RL可扩展训练的有效策略。

🧭 速览

动机

长视野智能体任务中，GRPO/RLOO对完整轨迹独立均匀采样，浪费预算于无信息量的死胡同，中间有潜力状态探索不足。

方法

PATR用任务适配的过程反馈对部分轨迹打分，从高潜力状态选择性分支，复用共享前缀，保守停止退化路径。

结果

在SWE-Bench上提升+5.0分，FrozenLake上提升+9.3分，相同训练预算下实现更高效的探索。

结论

过程引导的树形rollout是多轮智能体强化学习实现可扩展训练的有效探索策略。

📊 论文图表(共 3 张)

展开查看 3 张图

TL;DR

多轮强化学习训练大语言模型智能体时，传统方法对完整轨迹独立均匀采样，在长视野任务中浪费大量预算于死胡同，而有潜力的中间状态反而探索不足。PATR 框架将 rollout 组组织为树结构，用过程评分器对部分轨迹打分，动态决定在何处分支、保留或剪枝，从而将探索资源集中于最有前景的方向。在 SWE-Bench 上提升 +5.0 分、FrozenLake 上提升 +9.3 分，证明了过程引导的树状 rollout 是可扩展多轮强化学习的有效策略。

研究背景与动机

大语言模型智能体在复杂任务中需要多轮交互——执行工具、接收反馈、再做决策。这种[[多轮智能体]]的特性使得训练时的轨迹往往很长，从初始状态到任务完成可能需要数十步操作。在这样的长视野设定下，如何高效地进行[[强化学习]]训练就成了关键问题。

当前主流的方法如 GRPO（Group Relative Policy Optimization）和 RLOO 依赖对多条独立采样的完整轨迹进行组内相对[[优势估计]]。具体来说，智能体从同一 prompt 出发，独立生成若干完整轨迹，根据最终奖励的组内排名计算优势，再更新策略。这种范式在轨迹较短、奖励密集的任务中表现良好，但面对软件工程修复、复杂推理等长视野任务时，均匀采样的策略暴露出明显缺陷：大量轨迹会在中途进入死胡同（如重复调用同一工具、执行错误操作序列），这些无效尝试消耗了宝贵的采样预算，却对策略更新贡献甚微；而少数处于"正确轨道"上的中间状态本应获得更多探索机会，却因为预算被浪费而得不到充分采样。

造成这一困境的根源在于，传统 rollout 策略将探索预算均匀分配给所有分支，无法感知哪些中间状态更有前景。这促使研究者思考一个根本性问题：既然轨迹天然具有"动作-观察"交替的多轮结构，是否可以将一组轨迹组织成树形，从有潜力的节点选择性分支，而不是盲目采样完整轨迹？

方法

PATR（Process-scorer guided Adaptive Tree Rollout）的核心洞察是：有效探索的本质是决定在何处分支。树结构天然适合表示多轮决策过程——根节点是初始状态，每个分支点对应一个中间状态，子节点代表在该状态下采取的不同动作。关键在于，PATR 的设计原则是过程分数仅用于 rollout 分配，不参与奖励或优势计算，从而保持与标准 GRPO 目标的完全兼容性。

框架的运行流程如下：给定任务 prompt $x$ ，首先初始化 $B_{0}$ 条活跃分支，每个分支最多推进 $K$ 步。每隔 $K$ 步，所有活跃分支的状态-轨迹对 $τ_{i}^{t}$ 都会经过一个任务适配的过程评分器 $S_{ϕ}$ ，输出归一化的潜力分数 $s_{i}^{t} \in [0, 1]$ 。根据这个分数，系统将分支路由至三条路径——扩展、保留或剪枝。

扩展路径对应高分分支：从同一中间状态用当前策略采样 $M$ 个子分支，形成树形展开。这样做的好处是能够复用共享前缀，避免重复计算已经验证过的正确路径部分。保留路径对应中等分数的分支，它们继续推进 $K$ 步后再次接受评估。剪枝路径则处理低分分支或检测到重复动作的退化路径，满足条件 $s_{i}^{t} < median_{j \in A} s_{j}^{t} - α$ 或连续 $Θ$ 步重复同一动作时即终止。值得注意的是，早停的分支不会被丢弃，而是作为负样本保留在 rollout 组中参与策略优化——这一设计显著提升了 rollout 组的多样性，使得优势估计更加稳定。

过程评分器是框架中唯一需要针对任务设计的组件。论文提供了三种实现方式：启发式评分器利用可观测的中间信号，适用于结构化环境如 FrozenLake；预训练 PRM 评分器将部分轨迹序列化后输入通用过程奖励模型，聚合得到整体分数；LLM-as-judge 评分器使用专门的评判模型，针对软件工程任务设计了诊断/编辑/验证三阶段的提示模板，输出归一化分数。这三种评分器共享统一接口 $S_{ϕ} (x, τ_{i}^{t})$ ，可以根据任务特性灵活选择或组合使用。

最终生成的树形 rollout 组 $G (x)$ 仍然使用标准 GRPO 目标进行训练，组内优势计算保持不变，过程分数的作用仅限于引导采样分配，不对优化目标产生任何污染。这种设计确保了方法的可扩展性——任何支持 GRPO 训练的基础设施都可以直接适配 PATR，只需在采样阶段加入树构建逻辑。

实验与结果

论文在两个差异显著的任务上验证了 PATR 的有效性。FrozenLake 是结构化的网格世界导航任务，控制变量可观测、奖励信号清晰，适合验证框架在相对简单场景下的表现；SWE-Bench Verified 则选取了 500 个真实 GitHub issue 修复任务，是极具挑战性的长视野软件工程基准，此前鲜有树状 rollout 智能体强化学习方法在此任务上报告结果。

在 FrozenLake 上，PATR 相比标准 GRPO 提升 +9.3 分，有趣的是小模型（Qwen2.5-0.5B）的收益比大模型更显著——这说明过程引导的 rollout 能够有效补偿弱基策略在探索方向的不足。训练曲线显示 PATR 更早达到更高性能，且在整个训练过程中保持更高的环境完成率，说明树形采样不仅提升了最终效果，还加快了收敛速度。

SWE-Bench 上的结果更为关键：PATR 相比 GRPO 提升 +5.0 分，相比此前基于不确定性分支的 ARPO 方法提升 +1.8 分。更值得关注的是性能提升并非来自更长的探索——PATR 的平均响应长度和交互轮次通常更短，这直接证明了其效率优势来自于更精准的探索定向，而非简单地消耗更多算力。

消融实验进一步揭示了几个重要发现。通过对比 PATR-PRM 和 PATR-Judge 两个变体，论文发现 PRM 评分器在 SWE-Bench 上略占优势，但 Judge 提供了无需任务专用训练的灵活替代方案。"保留全部剪枝"与"仅保留最优"的对比则验证了将早停分支作为负样本的设计价值——丢弃这些分支会导致 rollout 组多样性下降，优势估计的方差增大。此外，Tree-Random 基线（保留树结构但随机选择分支）的表现介于 GRPO 和 PATR 之间，清晰分离了"树结构"与"过程引导"各自对性能的贡献。

讨论与可借鉴点

PATR 的成功揭示了一个更普适的原则：在长视野多轮任务中，探索效率的关键不在于采样多少轨迹，而在于将采样预算分配到哪些状态。树形结构提供了表示和操作这种分配的语言，过程评分器则提供了判断"哪个状态值得探索"的信号。两者的结合使得 PATR 能够在保持与标准策略优化兼容的同时，实现质量感知的自适应探索。

这一设计思路对当前 [[强化学习]] 研究有几点可借鉴之处。首先，过程信号与策略优化的解耦值得注意——论文刻意将过程分数排除在奖励和优势计算之外，这不仅是理论上的优雅，更避免了过程奖励模型可能引入的偏置污染策略更新的风险。其次，剪枝分支的保留作为负样本是一个看似反直觉但实际有效的设计：在长视野任务中，知道"什么路径行不通"本身就是有价值的信息，丢弃这些样本等于浪费了本可以提升优势估计质量的对比案例。最后，评分器的可插拔架构为不同任务场景提供了灵活性——从简单的启发式规则到复杂的 LLM 评判，评分器的选择可以在计算成本和准确性之间权衡。

当然，方法也存在局限。过程评分器的质量直接决定了分支决策的准确性——如果评分器对特定任务产生系统性偏置（如现有 PRM 倾向于给更长响应更高分），可能导致次优分支被过度扩展。更重要的是，PATR 目前只在软件工程和网格导航两个任务上验证，对于网页导航、具身交互等更具开放性的多轮智能体场景，其评分器的设计范式能否迁移仍有待探索。此外，论文未披露完整的算力消耗数据，这使得方法的实际部署成本难以准确评估。未来的工作可以从理论层面分析非均匀采样引入的偏差界，或者将 PATR 的思想与基于模型的方法（如 MCTS）进行更深层的融合。

摘要

强化学习（RL）已成为训练大语言模型智能体的关键方法，然而 GRPO/RLOO 等主流方法依赖多条独立采样的完整轨迹来进行优势估计。在长视野智能体任务中，这种均匀的推演策略会浪费预算在无信息量的死胡同尝试上，而有潜力的中间状态却得不到充分的探索。智能体轨迹的多轮结构——动作与观察交替出现——天然支持将一组轨迹组织成一棵树，其中每一轮都充当探索的决策点。这一视角将有效探索重新定义为决定在何处进行分支的问题。我们提出了过程评分器引导的自适应树状推演（PATR），一种面向多轮智能体强化学习的质量感知推演框架。PATR 利用任务适配的过程反馈对部分轨迹进行打分，选择性地从有潜力的状态进行分支，复用共享前缀，并保守地停止退化路径以减少无效采样。生成的推演组仍可与标准策略优化方法配合使用，在相同训练预算下提供更高效的探索。我们在 FrozenLake 以及颇具挑战性的 SWE-Bench 上对 PATR 进行了评估，后者此前鲜有先前的树状推演智能体强化学习方法涉足。实验表明，PATR 在 SWE-Bench 上最高提升 +5.0 分，在 FrozenLake 上最高提升 +9.3 分，凸显了过程引导的树状推演作为可扩展多轮强化学习的有效策略。

Abstract

Reinforcement learning (RL) has become a key approach for training LLM agents, yet popular methods such as GRPO/RLOO rely on multiple independently sampled complete trajectories for advantage estimation. In long-horizon agentic tasks, such a uniform rollout strategy can waste budget on uninformative dead-end attempts, while promising intermediate states do not receive sufficient exploration. The multi-turn structure of agentic trajectories, with interleaved actions and observations, naturally supports organizing a trajectory group as a tree, where each turn serves as a decision point for exploration. This perspective reframes effective exploration as the problem of deciding where to branch. We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL. PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops degenerate paths to reduce wasted sampling. The resulting rollout groups remain compatible with standard policy optimization while providing more efficient exploration under the same training budget. We evaluate PATR on FrozenLake and the challenging SWE-Bench, which is largely unexplored by prior tree-rollout agent RL methods. Experiments show that PATR improves performance by up to +5.0 points on SWE-Bench and +9.3 points on FrozenLake, highlighting process-guided tree rollouts as an effective strategy for scalable multi-turn RL.

论文详细总结（自动生成）

论文总结：面向高效多轮强化学习的过程奖励引导树状推演（PATR）

1. 核心问题与研究动机

问题背景：当前面向 LLM 智能体的多轮强化学习（如 GRPO、RLOO）普遍采用对完整轨迹独立采样的方式构造 rollout 组，以此进行组内相对优势估计。
关键缺陷：
在长视野、稀疏奖励的智能体任务（如软件工程）中，均匀采样浪费大量预算于无信息量的死胡同（重复工具调用、错误回环等）。
有潜力的中间状态反而得不到充分探索，导致 rollout 组冗余、低质量、优势估计噪声大。
核心洞察：智能体轨迹天然具有"动作-观察"交替的多轮结构，可将一组轨迹组织成树，每个决策轮次作为分支选择点；有效探索 = 决定在何处分支。
现有不足：先前的树状 rollout 方法要么基于熵/不确定性信号（未直接衡量任务进展），要么每步搜索最优动作（偏离当前策略分布），均未能兼顾过程质量与策略学习的兼容性。

2. 方法论

2.1 核心思想

PATR（Process-scorer guided Adaptive Tree Rollout）将 rollout 组构造为部分轨迹树，由任务适配的过程评分器 $S_{ϕ}$ 指导分支扩展、保留与剪枝。关键设计原则：过程分数仅用于 rollout 分配，不参与奖励或优势计算，从而保持与标准 GRPO 目标的兼容性。

2.2 自适应树构建（算法流程）

对每个任务 prompt $x$ ：

1. 初始化 $B_{0}$ 条活跃分支 $A$ ，完成分支集合 $C \leftarrow \emptyset$ 。

2. 每个分支最多推进 $K$ 步；中途终止的分支转入 $C$ 。

3. 对剩余活跃分支 $τ_{i}^{t}$ ，由过程评分器打分：

s_{i}^{t} = S_{ϕ} (x, τ_{i}^{t}) \in [0, 1]

4. 根据分数路由至三条路径：

扩展（Expansion）：高分分支 $E \subseteq A$ ，从同一中间状态采样 $M$ 个子分支：

τ_{i}^{t, m} \sim π_{θ} (\cdot ∣ x, τ_{i}^{t}), m = 1, \dots, M

保留（Survival）：中等分分支继续推进 $K$ 步后重新评估。
剪枝（Pruning）：满足以下条件之一即终止：

s_{i}^{t} < median_{j \in A} s_{j}^{t} - α 或 连续 Θ 步重复同一动作

5. 早停分支保留而非丢弃，作为负样本参与策略优化。

6. 最终 rollout 组 $G (x) = C$ 。

2.3 任务适配过程评分器（三种实现）

启发式评分器：利用可观测的中间信号（如累积奖励、BFS 最短路径距离等），适用于 FrozenLake 等结构化环境。
预训练 PRM 评分器：将部分轨迹序列化为问题-响应格式，喂入 Skywork-o1-Open-PRM-Qwen-2.5-7B，取步级分数 $c_{1}, \dots, c_{L_{i}}$ 聚合：

s_{i}^{t} = f_{a g g} (c_{1}, \dots, c_{L_{i}})

聚合方式可为最后一步分数、均值、最大值或加权组合。

LLM-as-judge 评分器：使用 Qwen2.5-Coder-7B-Instruct 作为评判器，针对 SWE 任务设计阶段感知提示（诊断/编辑/验证三阶段），输出归一化分数，并与启发式信号混合：

s_{i}^{t} = λ s_{j u d g e} (τ_{i}^{t}) + (1 - λ) s_{h e u r} (τ_{i}^{t})

2.4 GRPO 训练目标

沿用标准 GRPO 目标，但 rollout 组换为树构造的 $G (x)$ ，组内优势为：

A_{i}^{t r ee} = \frac{r _{i}^{o u t} - μ _{G} ( x )}{σ _{G} ( x ) + ϵ}

策略更新仍使用裁剪的 importance-weighted 目标：

L (θ) = E_{x} \frac{1}{G} i = 1 \sum G \frac{1}{∣ τ _{i} ∣} t = 1 \sum ∣ τ_{i} ∣ min (ρ_{i, t} (θ) A_{i}^{o u t}, clip (ρ_{i, t} (θ), 1 - ϵ, 1 + ϵ) A_{i}^{o u t})

其中 $ρ_{i, t} (θ) = π_{θ} (a_{i, t} ∣ h_{i, t - 1}) / π_{θ_{o l d}} (a_{i, t} ∣ h_{i, t - 1})$ 。过程分数不参与该项，仅在 rollout 阶段使用。

3. 实验设计

3.1 任务与数据集

FrozenLake（rLLM 框架）：结构化网格世界导航，控制变量可观测，过程质量可用启发式估计。
SWE-Bench Verified：500 个人工筛选的实例，面向真实 GitHub issue 修复的长视野软件工程任务。

3.2 模型

FrozenLake：Qwen2.5-0.5B-Instruct、Qwen2.5-3B-Instruct
SWE-Bench：Qwen3-4B-Instruct-2507

3.3 对比基线

GRPO：标准独立完整轨迹采样。
DAPO：token 级策略梯度精炼 + 拒绝采样 + 非对称裁剪。
ARPO：基于不确定性（高熵）信号的自适应分支。
Tree-Random：同树结构但分支选择随机，孤立"过程引导"与"树结构"的贡献。

3.4 评估方式

FrozenLake：成功率（Succ. Rate）与 Pass@4。
SWE-Bench：解决率（Resolved Rate）、环境完成率（Env Done）、平均交互轮次。

4. 资源与算力

FrozenLake：1 个 A100 节点，batch size 64，训练 400 步。
SWE-Agent 训练：1 个 H200 节点，batch size 8，训练 300 步。
PATR 超参：初始分支数 $B_{0} = 4$ ，每分支扩展 $M = 2$ 个子分支，分支间隔 $K = 5$ （FrozenLake）/ $K = 13$ （SWE），最大交互 10 轮 / 50 轮，最大响应 10K / 32K tokens，分数边界 $α = 0.5$ ，重复动作终止阈值 $Θ = 6$ 。
通用超参：学习率 $1 \times 1 0^{- 6}$ ，裁剪比 0.28，KL 系数 0.001，温度 1.0。
推理服务：PRM 与 Judge 模型部署在独立的 vLLM 推理服务器上，避免训练时 GPU 争抢。
算力报告完整性：训练总时长（wall-clock time）未在文中明确披露，仅给出硬件节点数。

5. 实验数量与充分性

主结果实验：2 个任务 × 2 个模型规模（FrozenLake）+ 1 个模型（SWE-Bench） = 至少 3 组实验。
消融实验：
超参消融：分支因子 $M$ （2 vs 3）、分支间隔 $K$ （13 vs 15 vs 20）、top- $k$ （1 vs 2 vs 4）共 7 组。
Rollout 组构造：保留全部剪枝（Keep All） vs 仅保留最优（Best_n），2 个变体 × 2 个评分器。
评分器实例化对比：PATR-PRM vs PATR-Judge。
训练动力学分析：训练奖励、平均轮次、策略熵三组曲线对比。
公平性：所有方法使用相同 rollout 预算与训练步数；GRPO/DAPO 使用组大小 8，ARPO/Tree-Random/PATR 使用相同的初始分支数。
充分性评估：整体覆盖较全面，跨不同模型规模和任务难度，并隔离了"树结构"与"过程引导"的独立贡献。但 SWE-Bench 仅报告单一模型（Qwen3-4B）的结果，跨模型泛化未充分验证。

6. 主要结论与发现

性能提升：PATR 在 SWE-Bench 上最优变体（PATR-PRM）相比 GRPO 提升 +5.0 分，相比最强基线 ARPO 提升 +1.8 分；在 FrozenLake 上最多提升 +9.3 分（小模型上从 66.5% → 75.8%）。
效率优势：平均响应长度与交互轮次通常更短，性能提升并非来自更长的探索。
小模型收益更大：在 Qwen2.5-0.5B 上 PATR 收益最显著，提示过程引导的 rollout 可补偿弱基策略的不足。
Graph 质量更高：PATR 生成的 rollout 组包含共享前缀、覆盖成功/失败/早停等多样结果，使 GRPO 优势估计更稳定。
评分器选择：PRM 评分器在 SWE-Bench 上略优于 Judge，但 Judge 提供了无需任务专用 PRM 的灵活替代方案。
收敛更快：训练曲线显示 PATR 更早达到更高性能，全程保持更高环境完成率。

7. 优点与亮点

方法论层面：
将"过程奖励"与"树状 rollout"有机结合，且严格保持与 GRPO 的兼容性——过程分数不污染奖励或优势。
三路径路由（扩展/保留/剪枝）清晰、可解释，且剪枝分支保留为负样本，提升了 rollout 组的多样性。
评分器抽象为统一接口 $S_{ϕ} (x, τ_{i}^{t})$ ，支持启发式 / PRM / LLM-as-judge 即插即用，适配不同任务。
Judge 评分器采用阶段感知提示（诊断/编辑/验证），对长视野软件工程任务特别有效。
实验层面：
首次将树状 rollout 智能体 RL 拓展到 SWE-Bench 这一高度挑战性长视野任务。
通过 Tree-Random 基线清晰隔离了"树结构"与"过程引导"的贡献。
训练动力学分析（奖励、轮次、熵）增强了结论的可信度。
消融实验（Keep All vs Best_n）验证了保留剪枝分支作为负样本的必要性。

8. 不足与局限

过程评分器敏感性：方法效果高度依赖过程评分器质量，不准确的评分可能导致次优分支被扩展或有用分支被错误剪枝。
PRM 偏置风险：文中明确指出 Skywork-o1-Open-PRM-Qwen-2.5-7B 倾向于给出更长的响应，可能影响分支排序与 rollout 分配。
任务覆盖有限：仅在 FrozenLake 与 SWE-Bench 两个基准上验证，尚未覆盖网页导航、具身交互、开放工具调用等多轮智能体场景。
SWE-Bench 单一模型：仅使用 Qwen3-4B-Instruct-2507 训练与评估，跨模型规模、跨基座家族的泛化能力未充分验证。
算力报告不完整：未披露训练总时长、token 总消耗等成本指标，复现成本难以估算。
诱导偏差讨论：方法虽然保持了理论上的策略目标不变，但非均匀采样引入了对 rollout 分布的局部偏差，文中仅做定性讨论，未给出理论偏差界或收敛性证明。
评分器开销：SWE-Bench 实验需额外调用 PRM 或 Judge 模型（独立 vLLM 服务），虽未影响训练 GPU，但增加了系统复杂度与延迟。

（完）

✨ 编译论文

点「✨ 编译」开始,LLM 会按 Polaris 风格翻译并把图片/表格嵌到对应位置。结果存到浏览器 localStorage,下次访问自动加载。