与 AI 博弈：从 AlphaGo 到 MuZero（四）

• AlphaGo 论文地址：https://www.nature.com/articles/nature16961
• AlphaGo Zero 论文地址：https://www.nature.com/articles/nature24270
• AlphaZero 论文地址：https://arxiv.org/abs/1712.01815
• MuZero 论文地址：https://arxiv.org/abs/1911.08265

DeepMind 官网介绍：https://deepmind.com/research/case-studies/alphago-the-story-so-far

5. MuZero

MuZero 在Deepmind 的 2019 年的初步论文中首次介绍，通过学习一个仅关注规划环境中最重要方面的模型来解决这个问题。通过将此模型与 AlphaZero 强大的前向树搜索相结合，MuZero 在 Atari 测试中得到了新的最先进的结果，同时在围棋、国际象棋和将棋等经典规划挑战中的表现与 AlphaZero 相媲美。MuZero 展示了强化学习算法能力的重大飞跃。

5.1 Generalising to unknown models

计划能力是人类智能的重要组成部分，使人类能够解决问题并对未来做出决定。例如，如果我们看到乌云正在形成，我们可能会预测会下雨，并决定在冒险之前带上一把雨伞。人类可以快速学习这种能力，并且可以推广到新的场景，这是作者希望算法具有的特性。

研究人员试图通过使用两种主要方法来应对人工智能中的这一重大挑战：前向搜索或基于模型的规划（model-based planning）。使用前向搜索的系统（例如 AlphaZero）在跳棋、国际象棋和扑克等经典游戏中取得了显着的成功，但依赖于了解其环境动态的知识，例如游戏规则或精确的模拟器。这使得很难将它们应用于混乱的现实世界问题，这些问题通常很复杂，很难提炼成简单的规则。

基于模型的系统旨在通过学习环境动态的准确模型，然后使用它进行规划来解决这个问题。然而，对环境的各个方面进行建模的复杂性意味着这些算法无法在视觉丰富的领域（例如 Atari）中竞争。到目前为止，Atari 上的最佳结果来自无模型系统，例如 DQN、R2D2 和 Agent57。顾名思义，无模型算法（model-free algorithms）不使用学习模型，而是估计下一步要采取的最佳行动。

MuZero 使用不同的方法来克服以前方法的局限性。 MuZero 没有尝试对整个环境进行建模，而是对代理决策过程中重要的方面进行建模。毕竟，知道雨伞避免淋湿比了解空气中雨滴形状更有意义。

具体来说，MuZero 模拟了对规划至关重要的三个环境因素：

• The value: how good is the current position?
• The policy: which action is the best to take?
• The reward: how good was the last action?

这些都是基于深度神经网络学习的， MuZero 了解当它采取某种行动时会发生什么并做出对应的计划。

A. MuZero 如何让模型学会“计划”？

下图说明如何使用蒙特卡洛树搜索与 MuZero 神经网络进行规划。从游戏中的当前位置（顶部的示意图围棋棋盘）开始，MuZero 使用表示函数 ( h h h) 从观察映射到神经网络使用的 Embedding ( s 0 s^0 s0)。使用动态函数 ( g g g) 和预测函数 ( f f f)，MuZero 可以考虑未来可能的动作序列 ( a a a)，并选择最佳动作。

给定前一个状态 s k − 1 s^{k-1} sk−1 和一个候选动作 a k a^k ak ，动态函数 g g g 得到一个即时奖励值 r k r^k rk 和一个新的状态 s k s^k sk，输入 s k s^k sk 到预测函数 f f f 中得到策略 p k p^k pk 和价值函数 v k v^k vk，而最初的状态 s 0 s^0 s0 表示是通过预先训练的表示函数 h h h （例如：围棋和 Atari ）进行 embedding。

B. MuZero 如何对未知环境做出相应动作？

MuZero 使用它在与环境交互时收集的经验来训练其神经网络。这种经验包括来自环境的观察和奖励，以及在决定最佳行动时执行的搜索结果。

在每个时间步 t t t 执行蒙特卡洛树搜索。搜索策略网络 π t \pi_t πt​ 采样一个动作 a t + 1 a_{t+1} at+1​ （与从根节点对每个动作的访问次数成正比），环境接收到动作并生成一个新的观察 o t + 1 o_{t+1} ot+1​ 和奖励 u t + 1 u_{t+1} ut+1​ 。结束时所有轨迹数据均被存储到缓冲区。

C. MuZero 如何训练网络？

在训练期间，模型与收集的经验一起展开，在每一步预测先前保存的信息：价值函数 v v v 预测观察到的奖励的总和 ( u u u)，策略估计 ( p p p) 预测先前的搜索结果 ( π π π)，奖励估计 r r r 预测最后观察到的奖励 ( u u u)。

将轨迹从缓冲区采样。对于初始步骤，表示函数 h h h 接收来自所选轨迹的过去观察值 o 1 , . . . , o t o_1,...,o_t o1​,...,ot​ 作为输入。该模型随后被循环展开 K K K 步。在每一步 k k k，动态函数 g g g 接收来自上一步的状态 s k − 1 s_{k-1} sk−1​ 和实际动作 a t + k a_{t+k} at+k​ 作为输入。表示函数、动态函数和预测函数的参数通过时间反向传播进行端到端联合训练，以预测三个量：策略网络 p k ≈ π t + k p^k ≈ π_{t+k} pk≈πt+k​ 、价值网络 v k ≈ z t + k v^k ≈ z_{t+k} vk≈zt+k​ 和奖励 r t + k ≈ u t + k r_{t+k} ≈ u_{t+k} rt+k​≈ut+k​ ，其中 z t + k z_{t+k} zt+k​ 是 sample return：最终奖励（棋盘游戏）或 n n n 步回报（Atari）。

MuZero 可以重复使用其学习模型来改进其规划，而不是从环境中收集新数据。例如，在 Atari 的测试中，这个变体 - 称为 MuZero Reanalyze - 在 90% 的时间里使用学习模型来重新规划过去几个场景应该做的事情。

5.2 MuZero 算法

在每个时间步 t t t ，对于每个 k = 1... K k = 1...K k=1...K 时间步，以过去的观察 o 1 , . . . , o t o_1,...,o_t o1​,...,ot​ 和未来的动作 a t + 1 , . . . , a t + k a_{t+1},...,a_{t+k} at+1​,...,at+k​ 为条件，由参数为 θ θ θ 的模型 μ θ μ_θ μθ​ 进行预测。该模型预测三个未来量：策略 p t k ≈ π ( a t + k + 1 ∣ o 1 , . . . , o t , a t + 1 , . . . , a t + k ) \mathbf{p}^k_t≈π(a_{t+k+1}|o_1,...,o_t,a_{t+1},...,a_{t+k}) ptk​≈π(at+k+1​∣o1​,...,ot​,at+1​,...,at+k​)，价值函数 v t k ≈ E [ u t + k + 1 + γ u t + k + 2 + . . . ∣ o 1 , . . . , o t , a t + 1 , . . . , a t + k ] v^k_t ≈ \mathbb{E}[u_{t+k +1} + γu_{t+k+2} + ...|o_1,...,o_t,a_{t+1},...,a_{t+k}] vtk​≈E[ut+k+1​+γut+k+2​+...∣o1​,...,ot​,at+1​,...,at+k​]，奖励 r t k ≈ u t + k r^k_t ≈ u_{t+k} rtk​≈ut+k​ ，其中 u u u 是真实观察到的奖励， π π π 是用于选择实际行动的策略， γ γ γ 是环境的折损函数。

在每个时间步 t t t（为简单起见，下标 t t t 被忽略），模型由一个表示函数、一个动态函数和一个预测函数的组合来表示。动态函数 r k , s k = g θ ( s k − 1 , a k ) r_k,s_k = g_θ(s^{k-1},a^k) rk​,sk​=gθ​(sk−1,ak)，是一个循环过程，在每个假设的步骤 k k k，计算一个即时奖励 r k r_k rk​ 和一个内部状态 s k s_k sk​。它反映了一个 MDP 模型的结构，该模型计算给定状态和动作的预期奖励和状态转换。然而，与基于模型的 RL 的传统方法不同，这个内部状态 s k s_k sk​ 没有附加环境状态的语义（它只是整个模型的隐藏状态，其唯一目的是准确预测相关的、未来的值：策略、价值和奖励）。在 MuZero 中，动态函数是以确定的方式表示的；随机转换的扩展是后续进一步工作。策略和价值函数是通过预测函数 p k , v k = f θ ( s k ) \mathbf{p}_k,v_k=f_θ(s_k) pk​,vk​=fθ​(sk​) 从内部状态 s k s_k sk​ 计算出来的，类似于 AlphaZero 的联合策略和价值网络。根 状态 s 0 s_0 s0​ 使用一个对过去观察结果进行 embedding 的表示函数来初始化， s 0 = h θ ( o 1 , . . . , o t ) s_0=h_θ(o_1,...,o_t) s0​=hθ​(o1​,...,ot​)；同样，除了对未来预测的支持外，这没有特殊的语义。

给定这样一个模型，就有可能在给定过去的观察值 o 1 , . . . , o t o_1,...,o_t o1​,...,ot​ 的情况下，对假设的未来轨迹进行搜索 a 1 , . . . , a k a_1,...,a_k a1​,...,ak​ 。例如，一个朴素的搜索可以简单地选择使价值函数最大化的 k k k 步动作序列。更一般地说，可以将任何 MDP 规划算法应用于动态函数所引起的内部奖励和状态空间。具体来说，作者使用一种类似于 AlphaZero 搜索的 MCTS 算法，它的生成允许单一代理域（single agent domains）和中间奖励。在每个内部节点，它利用当前模型参数 θ 产生的策略、价值和奖励估计。MCTS 算法输出一个推荐的策略 π t π_t πt​ 和估计的价值 ν t ν_t νt​。然后选择一个行动 a t + 1 ∼ π t a_{t+1}∼π_t at+1​∼πt​

模型的所有参数都经过联合训练，以准确地将每个假设步骤 k k k 的策略、价值和奖励与经过 k k k 个实际时间步骤后观察到的相应目标值相匹配。与 AlphaZero 类似，改进的策略目标是由 MCTS 搜索生成的；第一个目标是最小化预测策略 p t k \mathbf{p}^k_t ptk​ 和搜索策略 π t + k π_{t+k} πt+k​ 之间的误差。与 AlphaZero 一样，改进的价值目标是通过玩游戏或 MDP 生成的。然而，与 AlphaZero 不同，作者通过从搜索值引导 n n n 步到未来以允许具有折损和中间奖励的长时间跨度， z t = u t + 1 + γ u t + 2 + . . . + γ n − 1 u t + n + γ n ν t + n z_t = u_{t+1} +γu_{t+2} +...+ γ^{n−1}u_{t+n} + γ^nν_{t+n} zt​=ut+1​+γut+2​+...+γn−1ut+n​+γnνt+n​ .棋盘游戏中的最终结果 {败局，平局，赢局} 被视为在剧集最后一步发生的奖励 u t ∈ { − 1 , 0 , + 1 } u_t ∈\{−1,0,+1\} ut​∈{−1,0,+1}。具体来说，第二个目标是最小化预测价值 v t k v^k_t vtk​ 和价值目标 z t + k z_{t+k} zt+k​ 之间的误差。奖励目标只是观察到的奖励；因此，第三个目标是最小化预测奖励 r t k r^k_t rtk​ 和观察到的奖励 u t + k u_{t+k} ut+k​ 之间的误差。最后，还添加了一个 L2 正则化项，复合损失为：

l t ( θ ) = ∑ k = 0 K l r ( u t + k , r t k ) + l v ( z t + k , v t k ) + l p ( π t + k , p t k ) + c ∣ ∣ θ ∣ ∣ 2 l_t(θ) = ∑^K_{k=0} l^r(u_{t+k},r^k_t ) + l^v(z_{t+k},v^k_t ) + l^p(π_{t+k},\mathbf{p}^k_t ) + c||θ||^2 lt​(θ)=k=0∑K​lr(ut+k​,rtk​)+lv(zt+k​,vtk​)+lp(πt+k​,ptk​)+c∣∣θ∣∣2

其中 l r l_r lr​、 l v l_v lv​ 和 l p l_p lp​ 分别是奖励、价值和策略的损失函数。

5.3 MuZero 性能

作者选择了四个不同的域来测试 MuZeros 的功能。围棋、国际象棋和将棋用于评估其在具有挑战性的规划问题上的表现，并且作者使用 Atari 作为更复杂的视觉问题的基准。在所有情况下，MuZero 均为强化学习算法的 SOTA，优于 Atari 上的所有先前算法，并在围棋、国际象棋和将棋上与 AlphaZero 的超人性能相媲美。

每次训练运行使用 200M 或 20B 帧在 Atari 上的性能。 MuZero 在这两种设置中都达到了 SOTA。所有分数都根据测试人员的表现进行了标准化 。

作者还更详细地测试了 MuZero 使用其学习模型进行规划的能力。作者从围棋中经典的精确规划挑战开始，一步棋就意味着输赢。为了确认更多的计划应该带来更好的结果的直觉，作者测量了一个完全训练的 MuZero 版本在有更多的时间来计划每个动作时可以变得更强大（见下图左图）。结果表明，随着作者将每步走的时间从 0.1 秒增加到 50 秒，增加了 1000 多 Elo（衡量玩家相对技能的指标）。这类似于强大的业余选手和最强的职业选手之间的区别。

左图：随着计划每一步棋的时间增加，围棋的实力显着增加。注意 MuZero 的缩放比例与 AlphaZero 的缩放比例几乎完美匹配，AlphaZero 可以访问完美的模拟器。右图：Atari 游戏 Ms Pac-Man 中的得分也随着训练期间每一步的计划数量而增加。每个图都显示了不同的训练运行，其中 MuZero 被允许考虑每次移动的不同数量的模拟。

有趣的是，当 MuZero 每次移动只允许考虑六或七个模拟时——这个数字太小而无法涵盖 Ms Pac-Man 中所有可用的动作——它仍然取得了良好的性能。这表明 MuZero 能够在动作和情况之间进行概括，并且不需要穷举搜索所有可能性来有效学习。

参考资料

• http://tromp.github.io/go.html
• https://towardsdatascience.com/the-upper-confidence-bound-ucb-bandit-algorithm-c05c2bf4c13f
• https://en.wikipedia.org/wiki/AlphaGo
• https://deepmind.com/blog/article/alphago-zero-starting-scratch
• https://towardsdatascience.com/the-evolution-of-alphago-to-muzero-c2c37306bf9