Tree-OPO: Off-policy Monte Carlo Tree-Guided Advantage Optimization for Multistep Reasoning

📄 arXiv: 2509.09284v3 📥 PDF

作者: Bingning Huang, Tu Nguyen, Matthieu Zimmer

分类: cs.AI, cs.CL, cs.LG

发布日期: 2025-09-11 (更新: 2025-12-21)

💡 一句话要点

提出Tree-OPO，利用MCTS指导优势函数优化，提升LLM多步推理能力

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 蒙特卡洛树搜索 强化学习 策略优化 多步推理 优势函数估计 分阶段学习 数学推理 大语言模型

📋 核心要点

  1. 现有方法难以有效利用MCTS生成的轨迹来提升策略优化，尤其是在多步推理任务中。
  2. 论文提出Tree-OPO框架，核心思想是利用MCTS生成轨迹，构建树状课程，并设计分阶段优势估计（SAE）方法。
  3. 实验结果表明，SAE在数学推理任务上显著提升了最终准确率，验证了其有效性和样本效率。

📝 摘要（中文）

本文探索了如何将蒙特卡洛树搜索（MCTS）生成的高质量中间轨迹，用于改进验证器引导的强化学习（RL）中的策略优化，特别是在数学和符号领域。受到MCTS在生成高质量中间轨迹方面的启发，本文将Group Relative Policy Optimization (GRPO) 重新构建为一个分阶段的训练范式，利用教师模型的MCTS rollout构建树状结构的课程前缀。由此引入了为来自不同前缀的训练样本计算优势函数的挑战，因为每个前缀都有不同的预期回报。为此，本文提出了分阶段优势估计（SAE），通过将奖励投影到尊重树层次结构的约束集上，来计算低方差、前缀感知的优势函数。在数学推理任务上的实验结果表明，SAE提高了最终准确率，优于标准GRPO。理论分析证实SAE降低了梯度方差，从而提高了样本效率。通过SAE的实际实现，比较了高效的启发式方法和形式化的二次规划。

🔬 方法详解

问题定义：论文旨在解决大型语言模型（LLMs）在多步推理任务中，如何更有效地利用蒙特卡洛树搜索（MCTS）生成的中间轨迹来提升策略优化的问题。现有方法通常将MCTS轨迹用于训练价值或奖励模型，而忽略了其在策略优化中的潜力。此外，直接应用现有策略优化算法（如GRPO）时，难以处理来自不同MCTS前缀的样本，因为每个前缀的预期回报不同，导致优势函数估计偏差。

核心思路：论文的核心思路是将MCTS生成的轨迹视为一种课程，构建一个树状结构，其中每个节点代表一个推理步骤的前缀。然后，通过分阶段优势估计（SAE）方法，为每个前缀的样本计算低方差、前缀感知的优势函数。这样可以更准确地评估策略在每个推理步骤的优劣，从而引导策略优化。

技术框架：Tree-OPO框架包含以下主要阶段：1) 使用MCTS生成高质量的中间轨迹；2) 将MCTS轨迹构建成树状结构的课程前缀；3) 使用分阶段优势估计（SAE）方法计算每个前缀的优势函数；4) 使用GRPO算法进行策略优化，其中优势函数由SAE提供。

关键创新：论文的关键创新在于提出了分阶段优势估计（SAE）方法。SAE通过将奖励投影到尊重树层次结构的约束集上，来计算低方差、前缀感知的优势函数。这与传统的优势函数估计方法不同，后者通常忽略了样本来自不同前缀的事实，导致估计偏差。SAE能够更准确地评估策略在每个推理步骤的优劣，从而提高策略优化的效果。

关键设计：SAE的核心在于如何构建约束集和进行奖励投影。论文提出了两种SAE的实现方式：一种是基于启发式的近似方法，另一种是基于二次规划的精确方法。启发式方法通过简单的规则来构建约束集，计算效率高，但可能存在一定的近似误差。二次规划方法通过求解一个二次规划问题来构建最优的约束集，精度高，但计算复杂度也较高。论文还对两种方法的性能进行了比较。

🖼️ 关键图片

img_0

📊 实验亮点

实验结果表明，在数学推理任务上，Tree-OPO框架结合SAE方法，显著提高了最终准确率，优于标准的GRPO算法。具体而言，SAE能够降低梯度方差，从而提高样本效率。论文还比较了启发式SAE和基于二次规划的SAE，结果表明两种方法都能有效提升性能，但二次规划SAE的精度更高。

🎯 应用场景

该研究成果可应用于各种需要多步推理的场景，例如数学问题求解、符号推理、游戏AI等。通过利用MCTS生成的高质量轨迹，可以显著提升LLM在这些任务上的性能。此外，SAE方法也可以推广到其他强化学习算法中，提高样本效率和策略优化效果。

📄 摘要（原文）

Recent advances in reasoning with large language models (LLMs) have shown the effectiveness of Monte Carlo Tree Search (MCTS) for generating high quality intermediate trajectories, particularly in math and symbolic domains. Inspired by this, we explore how MCTS derived trajectories, traditionally used for training value or reward models, can be repurposed to improve policy optimization in verifier guided reinforcement learning (RL). Specifically, we focus on Group Relative Policy Optimization (GRPO), a recent algorithm that enables consistent policy learning from group relative judgments. We reframe GRPO into a staged training paradigm, leveraging a teacher's MCTS rollouts to construct a tree structured curriculum of prefixes. This introduces the novel challenge of computing advantages for training samples that originate from different prefixes, each with a distinct expected return. To address this, we propose Staged Advantage Estimation (SAE), a framework for computing low variance, prefix aware advantages by projecting rewards onto a constraint set that respects the tree's hierarchy. Our empirical results on mathematical reasoning tasks show that SAE improves final accuracy over standard GRPO. This outcome is grounded in our theoretical analysis, which confirms that SAE reduces gradient variance, a principled path to improved sample efficiency. We demonstrate this through practical SAE implementations, comparing efficient heuristics against a formal quadratic program.