🤖 AI

Epistemic Monte Carlo Tree Search

本文介绍了认知蒙特卡洛树搜索（EMCTS），该方法将认知不确定性融入蒙特卡洛树搜索，与标准的 AlphaZero/MuZero 方法相比，显著提升了稀疏奖励环境中的样本效率和探索能力。

原作者： Yaniv Oren, Viliam Vadocz, Matthijs T. J. Spaan, Wendelin Böhmer

发布于 2026-05-18

📖 1 分钟阅读☕ 轻松阅读

原作者： Yaniv Oren, Viliam Vadocz, Matthijs T. J. Spaan, Wendelin Böhmer

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

以下是用简单语言和创意类比对论文《认知蒙特卡洛树搜索》的解释。

宏观图景：“自信探索者”问题

想象你正在教一个机器人玩一个非常困难的游戏，比如从零开始编写计算机程序，或者穿越一个巨大而黑暗的迷宫。这个游戏之所以棘手，是因为奖励极其稀缺。你可能需要走几千步，才能找到一个能通向胜利的“好”动作。

目前这些游戏最先进的 AI 被称为AlphaZero/MuZero。可以将这些 AI 想象成杰出的棋手，它们能够前瞻许多步来规划策略。它们使用一种称为**蒙特卡洛树搜索（MCTS）**的技术，这就像在脑海中构建一本巨大的“选择你自己的冒险”书，以模拟不同的未来。

问题所在：
这些 AI 通过玩游戏并构建一个关于世界如何运作的“心理模型”来学习。但由于它们尚未见识过“一切”，其心理模型存在空白。

认知不确定性（Epistemic Uncertainty）： 这是一种 fancy 的说法，意思是“我不知道这个，因为我以前没见过”。
缺陷： 标准的 AlphaZero 算法非常擅长规划，但它将自己的心理模型视为 100% 完美的真理。它没有意识到：“嘿，我这是在猜测，因为我从未去过迷宫的这个部分。”因为它不知道自己是在猜测，所以它觉得没有必要去探索那些未知区域。它陷入了重复已知行为的循环，错过了隐藏在黑暗中的稀有奖励。

解决方案：认知蒙特卡洛树搜索（EMCTS）

作者提出了一种名为**认知蒙特卡洛树搜索（Epistemic Monte Carlo Tree Search, EMCTS）**的新方法。

类比：拿着红笔的地图绘制者
想象 AI 是一位正在绘制新岛屿地图的地图绘制者。

标准 AlphaZero： 根据所见绘制地图。如果它看到一片森林，它就画一片森林。如果它没看到岛屿的另一边，它就留白，或者猜测那里看起来像森林。它假设自己的绘图是完美的。
EMCTS： 也绘制地图，但它携带一支不确定性红笔。
- 当它绘制多次访问过的岛屿部分时，线条是黑色且实心的。
- 当它绘制从未见过的部分时，它用模糊、颤抖的红色线条绘制，并用大字写上“我不确定这个”。
- 关键在于，当 AI 规划下一步时，它不仅仅看黑色线条。它会查看颤抖的红色线条，并思考：“这个区域是不确定的。也许这里有宝箱！我应该去检查一下。”

通过明确追踪自己对预测的不确定程度，AI 被激励去探索地图中“颤抖”的部分，从而更快地发现稀有奖励。

工作原理（机制）

该论文引入了三个主要技巧来实现这一目标：

“乐观”评分： AI 不再仅仅问“这里的平均奖励是多少？”，而是问“考虑到我可能会出错，这里最好的可能奖励是多少？”它为通向不确定区域的动作加分。这就像一位寻宝者说：“我还没在这里找到黄金，但既然我不知道那里有什么，在证明之前，我就假设那里满是黄金。”
传播怀疑： 当 AI 模拟一条未来路径（树中的一个分支）时，它不仅仅计算奖励。它还会计算该路径每一步存在的“怀疑”（不确定性）程度。如果 AI 对第一步不确定，这种怀疑会沿路径向下传递，使整条路径看起来“不确定”，因此“值得探索”。
并行思考： 作者构建了一个快速的并行版本系统（使用名为 JAX 的工具），以便 AI 可以同时运行许多“如果”场景，快速确定哪些路径值得探索。

结果：它奏效了吗？

作者在两个奖励极其稀缺的极难环境中测试了这种新方法：

1. “代码编写者”（Subleq）

任务： AI 必须用一种非常原始的单指令汇编语言"Subleq"编写程序来解决数学问题。
结果： 标准 AlphaZero 表现挣扎，需要大量尝试才能找到可行的程序。而新的EMCTS版本则快得多地找到了正确的代码。这就像标准 AI 在随机输入字母，而 EMCTS AI 则系统地检查最可能有效的“不确定”组合。

2. “深海”（Deep Sea Benchmark）

任务： 想象一个网格，你从左上角开始，需要到达右下角。终点有一个奖励，但你走的每一步都会给你一个微小的“惩罚”（负分）。通往奖励的路径是一条单一、特定的线。如果你偏离了，就一无所获。
结果： 这是一个经典的“大海捞针”问题。标准 AlphaZero 及类似方法未能在合理时间内解决它，因为它们无法理解需要深入探索。然而，EMCTS代理成功穿越了网格，即使奖励是随机且嘈杂的。它们证明，通过利用搜索树来估计不确定性，它们比不使用此目的进行搜索的方法能更高效地找到隐藏路径。

核心结论

该论文声称，通过教导 AI 识别它不知道什么（认知不确定性），并利用这种“不知道”的感觉来指导其规划（搜索），我们可以创造出在探索困难、奖励稀疏的环境中表现更好的代理。

它将 AI 从一个自信但盲目的规划者，转变为一个好奇的探索者，因为它确切地知道地图哪里不完整，从而知道下一步该看哪里。这使得它在算法设计或探索未知世界等复杂任务中，寻找解决方案的效率显著提高。

技术摘要：认知蒙特卡洛树搜索

问题陈述

AlphaZero/MuZero（A/MZ）算法家族通过将蒙特卡洛树搜索（MCTS）与学习到的价值模型及环境动力学模型相结合，取得了显著成功。然而，存在一个关键局限：虽然学习到的模型引入了认知不确定性（源于训练数据覆盖范围有限的不确定性），但标准 MCTS 并未在搜索过程中考虑这种不确定性的传播。因此，A/MZ 无法有效利用 MCTS 在稀疏奖励环境中进行深度探索。深度探索要求智能体将自身导向新颖的转移，无论这些转移距离当前状态有多远；这种能力对于算法设计或编程等任务至关重要，因为这些任务奖励稀疏且状态空间巨大。若不考虑认知不确定性，搜索可能会基于不准确模型预测收敛到次优策略，从而未能探索状态空间中必要的区域。

方法论：认知 MCTS（EMCTS）

作者提出了认知 MCTS（EMCTS），这是一个理论驱动框架，将认知不确定性整合到 MCTS 过程中以促进深度探索。该方法包含三个主要组成部分：

1. 构建带不确定性的搜索

作者将学习到的环境模型 $\hat{M}$ 建模为随机变量。他们基于学习模型内价值预测的方差，推导出了最优价值函数 $Q^*$ 的上置信界（UCB）。

理论基础：定理 1 确立，对于学习到的模型 $\hat{M}$ ，真实最优值 $Q^*(s, a)$ 被模型中的最大期望值加上一个与该值标准差成正比的项所界定，该项由置信参数 $\delta$ 缩放。
搜索策略：标准的 PUCT（预测器上置信界）选择策略被修改为认知 P/UCT（EP/UCT）。选择准则变为：
$a = \arg\max_{a} \left( q_{\hat{M}}(s, a) + \beta \sqrt{V[q_{\hat{M}}(s, a)]} + \text{探索项} \right)$
其中， $q_{\hat{M}}$ 表示估计值， $\sqrt{V[q_{\hat{M}}]}$ 表示认知不确定性。超参数 $\beta$ 控制利用与探索之间的权衡。

2. 传播认知不确定性

核心贡献在于一种机制，能够在搜索树中传播不确定性，而不仅仅是传播价值。

备份中的不确定性：备份步骤 $\nu$ 的不确定性是通过将即时奖励的方差与折扣后未来价值的不确定性方差相加来计算的。
节点价值不确定性：由于 A/MZ 在整个规划过程中使用相同的模型，备份回报是相关的。为了避免假设独立性，作者提出使用个体备份回报标准差之和的上界来界定节点价值 $V[q_{\hat{M}}(s, a)]$ 的方差：
$V[q_{\hat{M}}(s, a)] \leq \left( \frac{1}{N(s, a)} \sum_{i=1}^{N(s, a)} \sqrt{V[\nu_i(s, a)]} \right)^2$
估计器：该方法利用现有的奖励不确定性估计器（例如随机网络蒸馏 RND 或基于哈希的计数）和价值不确定性估计器（例如不确定性贝尔曼方程 UBE）。对于未观察到的转移，方差被设定为有界随机变量的最大可能方差。

3. 处理学习到的转移模型

虽然理论推导假设已知转移模型，但作者解决了学习到的转移动力学（如 MuZero 中）带来的挑战。他们提出了一种“最大乐观”近似：当在轨迹中遇到第一个不确定转移时，假设该轨迹中的所有后续预测都具有最大不确定性。这确保了 UCB 在探索目的上仍然是有效的上界。

主要贡献

认知 MCTS（EMCTS）：一种新颖算法，扩展了 MCTS 以估计并传播来自学习到的价值和/或奖励模型的认知不确定性，使搜索过程能够主动寻找不确定区域。
理论框架：推导了基于 UCB 的搜索策略（EP/UCT），其理论基础在于学习模型的方差，为深度探索提供了形式化机制。
实现：一种并行化的 JAX 实现的 EMCTS，与 AlphaZero 智能体配对，应用于汇编语言 subleq 环境和 Deep Sea 基准测试。

实验结果

作者在两个具有挑战性的稀疏奖励领域评估了 EMCTS：

1. Subleq 编程任务

任务：编写 subleq 汇编语言代码以解决特定函数（取反正数和恒等函数）。这涉及搜索一个约为 $16^{10}$ 个状态的状态空间。
结果：与 AlphaZero 配对的 EMCTS（E-AZ）显著优于基线 AlphaZero。E-AZ 以远少于基线的样本量解决了更难的“恒等函数”任务。该方法表明，使用适当的不确定性估计器（例如 IO 哈希与完整状态哈希）进一步提高了样本效率。

2. Deep Sea 基准测试

任务：一个网格世界环境，智能体必须找到具有稀疏奖励的唯一最优轨迹。通过随机探索找到解的概率随网格大小呈指数级衰减。
结果：
- 深度探索：基线 A/MZ 智能体在合理的训练预算内未能解决 Deep Sea 变体（包括确定性奖励和随机性奖励）。相比之下，EMCTS 智能体（E-AZ 和 E-MZ）解决了这些任务，展示了样本复杂度随环境规模呈亚指数级扩展。
- 搜索收益：EMCTS 显著优于一种消融实验（A/MZ+UBE），后者仅利用不确定性进行动作选择，但未利用搜索来估计该不确定性。这证实了搜索本身提高了不确定性估计的质量，从而实现了更高效的探索。
- 鲁棒性：即使在使用 MuZero 的学习到的转移动力学（价值等价抽象）以及存在随机奖励的情况下，该方法依然有效。

意义与主张

本文主张 EMCTS 解决了基于模型的强化学习中的一个根本性差距：标准 MCTS 无法利用认知不确定性进行探索。通过将不确定性传播整合到搜索树中，该方法使 A/MZ 智能体能够：

在稀疏奖励环境中实现显著更高的样本效率。
解决基线 A/MZ 实际上无法解决的硬探索基准（如 Deep Sea）。
通过为价值预测提供更好的不确定性估计，潜在地提高离线强化学习和离线策略目标生成的可靠性。

作者将 EMCTS 定位为对 A/MZ 家族的一种实用且理论驱动的增强，使这些算法能够更好地应对涉及算法设计和稀疏奖励的现实世界应用，在这些应用中深度探索至关重要。