💻 computer science

Twice Sequential Monte Carlo for Tree Search

本文介绍了双重序贯蒙特卡洛树搜索（TSMCTS），这是一种新颖的算法，它通过有效缓解路径退化和方差问题，同时保留其在并行化和 GPU 加速方面的优势，从而增强了基于模型的强化学习中序贯蒙特卡洛方法的可扩展性和稳定性。

原作者： Yaniv Oren, Joery A. de Vries, Pascal R. van der Vaart, Matthijs T. J. Spaan, Wendelin Böhmer

发布于 2026-05-22

📖 1 分钟阅读☕ 轻松阅读

原作者： Yaniv Oren, Joery A. de Vries, Pascal R. van der Vaart, Matthijs T. J. Spaan, Wendelin Böhmer

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

想象一下，你正在尝试解决一个非常复杂的谜题，比如 navigating 一个迷宫或玩一款高难度的电子游戏。你拥有一个“大脑”（一个 AI 智能体），它需要决定下一步该采取什么行动。为了做出最佳决策，这个“大脑”会尝试向未来“展望”，模拟成千上万条可能的路径，以查看哪一条能带来最高的分数。

本文介绍了一种让 AI 进行这种“展望”的更聪明的新方法。作者将其称为双重序贯蒙特卡洛树搜索（Twice Sequential Monte Carlo Tree Search, TSMCTS）。

以下是他们解决的问题及其解决方案的分解，使用了简单的类比。

问题：“拥挤的房间”与“孤独的房间”

要理解这种新方法，我们首先需要审视它试图改进的两种旧方法：

旧方法（MCTS）： 想象一支探险队试图绘制一个洞穴的地图。他们构建了一个巨大的、分叉的路径树。每次遇到死胡同，他们就会返回并尝试另一条分支。
- 优点： 他们非常彻底，不容易感到困惑。
- 缺点： 速度慢。他们必须在内存中构建整个树结构。很难让庞大的计算机团队协同工作，因为它们在尝试更新同一张地图时会不断互相碰撞。
替代方法（SMC）： 想象 1000 名跑步者（粒子）同时出发，沿着不同的路径同时奔跑。他们不构建树；他们只是奔跑。
- 优点： 速度极快，很容易让 1000 台计算机并行运行这 1000 名跑步者。
- 缺点： 随着跑步者深入洞穴，一些奇怪的事情发生了。
  - “方差”问题： 他们跑得越远，结果就越混乱。这就像试图预测 10 年后的天气；你看得越远，你的预测就越不准确。
  - “路径退化”问题： 最终，几乎所有跑步者都意识到某条特定路径看起来比其他路径稍好一些。他们全部放弃了自己独特的路径，涌向那条单一的“最佳”路径。突然间，1000 名跑步者都在做完全相同的事情。AI 停止“思考”，只是随大流，从而错过了潜在更好、更隐蔽的路径。

解决方案：TSMCTS（“双重”方法）

作者创建了TSMCTS，旨在获得跑步者（SMC）的速度，同时避免混乱或“拥挤”问题。他们通过两个主要步骤实现了这一点：

步骤 1：停止计算跑步者，开始计算分数（SMCTS）

在旧的跑步者方法中，AI 只关心跑步者走了哪条路径。如果所有跑步者都走了同一条路径，AI 就会认为那是唯一的选择。

作者改变了规则：AI 不再只是观察跑步者，而是为每一个可能的起始动作保留一个记分牌。

即使所有 1000 名跑步者最终都走上了同一条路径，AI 也会记住：“嘿，我们尝试过那条路径，这是我们要得到的平均分数。”
如果一名跑步者掉下悬崖，AI 不会忘记那条路径；它会用糟糕的分数更新记分牌。
结果： AI 保留了每个起始动作好坏的“运行平均值”，即使跑步者停止探索那条特定路径。这阻止了“拥挤”问题，因为 AI 仍然拥有跑步者放弃的路径的数据。

步骤 2：“锦标赛”策略（双重）

解决方案的第二部分涉及如何分配计算机的时间。

想象你有一笔预算来测试 100 种不同的起始动作。
旧方法： 你可能会对 100 种动作都进行少量测试，或者对少数几种动作进行大量测试。
TSMCTS 方法： 他们使用一种称为**序贯减半（Sequential Halving）**的策略（就像锦标赛淘汰赛制）。
1. 第一轮： 你挑选 16 个有希望的移动。你派遣一个小团队跑步者去测试所有 16 个。
2. 第二轮： 你查看分数。表现最差的 8 个被淘汰。你让剩下的 8 个接受更多跑步者的测试，进行更深入的探索。
3. 第三轮： 你淘汰表现最差的 4 个。你派遣更多的跑步者去测试前 4 名。
4. 决赛： 你将所有资源集中在单一的最佳移动上。

为什么这是“双重”？
该算法在循环中运行两次这种“跑步者模拟”（SMCTS）：

首先，它运行一次快速模拟，以查看哪些动作看起来有希望。
然后，它只在第一轮获胜者上运行第二次、更深入的模拟，使用更多的跑步者来获得超准确的分数。

为什么这很重要（结果）

该论文在各种类似电子游戏的环境中测试了这种新方法（有些涉及像国际象棋这样的离散选择，有些涉及像控制机器人这样的连续运动）。

扩展性更好： 随着给予 AI 更多时间进行“思考”（更深的搜索），旧的跑步者方法表现变差（因为混乱和拥挤）。而 TSMCTS 表现更好。
更稳定： 它预测的分数“抖动”要小得多（方差更低）。
不会陷入停滞： 它成功避免了“路径退化”，即 AI 停止思考并随大流的情况。
依然快速： 它保持了跑步者方法的超快速并行特性，使其易于在现代图形处理器（GPU）上运行。

总结

将TSMCTS想象成一位聪明的教练管理着一支侦察兵团队。

旧的跑步者方法就像派出侦察兵，但如果他们都喜欢同一条路径，教练就会完全忘记其他路径。
新方法为每一条路径保留记分卡，甚至是侦察兵放弃的那些路径。
它还像一场锦标赛，迅速淘汰坏路径，并将所有资源投入到最佳路径中，确保最终决定基于尽可能准确的数据。

结果是一个能够思考得更深、做出更好决策，并且比以前的方法更快的 AI。

技术摘要：用于树搜索的两次序贯蒙特卡洛

1. 问题陈述

利用搜索（规划）的基于模型的强化学习（RL）算法推动了从游戏到机器人领域的一系列重大突破。该领域的主导算法是蒙特卡洛树搜索（MCTS），它驱动了 AlphaGo 和 MuZero 等系统。然而，MCTS 面临两个主要瓶颈：

计算低效性：其顺序性质使其难以利用现代深度强化学习中不可或缺的工具——GPU 进行并行化和加速。
内存限制：MCTS 需要在内存中维护整个搜索树，导致空间复杂度随树的大小增长，阻碍了 GPU 的可扩展性。

序贯蒙特卡洛（SMC）作为一种可并行化的 MCTS 替代方案应运而生。通过在 $N$ 个粒子上并行近似轨迹分布，SMC 提供了线性的内存扩展性，并且更适合 GPU 加速。然而，将标准 SMC 应用于 RL 搜索时存在两个关键缺陷，使其无法随搜索深度（顺序计算）的增加而扩展：

指数方差：由于可能轨迹的指数级增长，估计量的方差随搜索深度急剧增加。
路径退化：一种现象，即在达到一定深度后，所有粒子都关联到同一个根动作。这导致策略估计坍缩为狄拉克分布（delta distribution），使得进一步搜索变得多余，并在训练信号中引发“目标退化”。

2. 方法论

作者提出了两次序贯蒙特卡洛树搜索（TSMCTS），这是一种新颖的算法，旨在保留 SMC 的并行化优势，同时缓解其方差和退化问题。该方法建立在三个关键的概念转变和算法组件之上：

2.1. 面向 RL 的 SMC 重构（RL-SMC）

作者首先通过摒弃先前工作（如 Piché 等人，2019）中使用的“控制即推理”（CAI）框架，重新构建了用于策略改进的 SMC。相反，他们直接定义了由通用贪婪化算子 $I$ 导出的改进策略 $\pi'$ 所生成的轨迹上的目标分布。

视角转变：搜索不再侧重于估计轨迹分布，而是聚焦于估计改进策略在根节点处的动作值（ $Q$ 值）。
优势：这使得能够集成类似于 MCTS 的反向传播机制，其中价值估计在粒子间进行聚合，从而在粒子退化为单一路径时减轻信息丢失。

2.2. 序贯蒙特卡洛树搜索（SMCTS）

基于 RL-SMC 公式，作者引入了 SMCTS，该算法包含一个基于价值的反向传播步骤：

扩展：粒子转移到新状态。
搜索：计算重要性采样权重，使粒子与改进策略对齐。
反向传播：评估回报，并对关联到同一根动作的粒子进行平均，以更新动作值的运行均值（ $\bar{Q}_t$ ）。

结果：这种聚合防止了策略目标坍缩为狄拉克分布（缓解了路径退化），并通过跨时间平均回报降低了估计量方差。

2.3. 两次序贯蒙特卡洛树搜索（TSMCTS）

为了进一步解决方差问题并优化根节点的搜索预算，TSMCTS 将根动作选择视为一个具有已知预算的简单遗憾（simple-regret）最佳动作识别问题。它采用序贯减半（Sequential Halving, SH） 老虎机算法作为 SMCTS 的包装器：

迭代减半：算法运行 $\log_2 m_1$ 次迭代（其中 $m_1$ 是初始搜索的动作数量）。
资源分配：在每次迭代中，候选动作集减半，而分配给每个剩余动作的粒子数量加倍。
方差降低：该策略减少了每次迭代的搜索范围（因为总计算量固定），从而内在降低了方差（因为 SMC 方差随深度增长）。此外，它使用逆方差加权在迭代间聚合价值估计，优先选择最可能是最优的动作。
并行性：关键在于，给定迭代中每个动作的搜索是独立且并行执行的，保留了 SMC 对 GPU 友好的特性。

3. 主要贡献

TSMCTS 算法：一种新的搜索算法，结合了 SMC、MCTS 风格的反向传播和序贯减半，以实现策略改进。
理论重构：推导出不依赖于“控制即推理”框架的 RL 用 SMC，支持通用贪婪化算子并直接聚焦于价值估计。
缓解 SMC 局限性：论文证明 TSMCTS 有效解决了标准 SMC 的两种主要失效模式：
- 它随顺序计算（搜索深度）的增加而呈现有利的扩展性，而标准 SMC 的性能则随之恶化。
- 它显著降低了估计量方差，并防止根节点处的路径退化。
保留并行性：该算法保留了 SMC 的线性空间复杂度和天然并行性，使其适用于 GPU 加速。

4. 实验结果

作者在一系列离散（Jumanji: Snake, Rubik's Cube）和连续（Brax: Ant, HalfCheetah, Humanoid）环境中评估了 TSMCTS，并与以下方法进行了比较：

SMC 基线：SPO（Macfarlane 等人，2024）中使用的标准 SMC 方法。
SMCTS：基于价值的中间 SMC 算法。
GumbelAZ：使用 GumbelMCTS（Danihelka 等人，2022）的现代基于 MCTS 的智能体。
TRT SMC：一种带有信任域优化的最新 SMC 变体。

主要发现：

随深度的扩展：与因方差和退化而在搜索深度增加时性能下降的 SMC 基线不同，TSMCTS 的性能随深度增加而提升或保持稳定。
方差与退化：与 SMC 基线和 TRT SMC 相比，TSMCTS 在根估计量中表现出显著更低的方差，并在策略目标中维持更高数量的活跃动作（避免坍缩为单一动作）。
性能：TSMCTS 在所有环境中均显著优于 SMC 基线和 SMCTS。它同时也优于或达到了基于 MCTS 的 GumbelAZ 的性能，同时保持了 SMC 的计算效率优势。
效率：TSMCTS 展现出比 GumbelMCTS 更好的运行时效率，并与 SMC 基线相当，仅增加了适度的计算开销。

5. 意义与主张

论文声称，TSMCTS 代表了基于搜索的 RL 策略改进的重大进步。通过成功弥合 SMC 的并行化优势与 MCTS 的鲁棒性之间的差距，TSMCTS 为基于模型的 RL 提供了一种可扩展的替代方案。

作者强调，他们的方法：

解决了可扩展性悖论：它允许 SMC 从增加的顺序计算（更深搜索）中受益，而无需承受通常限制其发展的方差爆炸或路径退化。
泛化了策略改进：底层公式支持任何贪婪化算子，使该方法能够适应未来策略优化算子的改进。
保持了硬件兼容性：它保留了使 SMC 成为现代深度 RL 硬件（GPU）理想选择的特性，即并行化和线性内存扩展，而 MCTS 在这些约束下则难以应对。

这项工作将 TSMCTS 定位为不仅仅是 SMC 的一个变体，而是一个稳健的通用搜索算子，可在并行化和内存效率至关重要的场景中替代 MCTS，同时避免标准 SMC 的陷阱。