对 AlphaZero 算法为何有效的原则性理解?

机器算法验证 神经网络 深度学习 强化学习 游戏
2022-03-24 01:14:12

大致来说,AlphaGo / AlphaGo Zero的算法如下:

  1. 使用策略网络,生成移动概率的分布(直观地,根据第一近似值捕捉这些移动的好坏程度)。

  2. 根据这些概率选择走法,并想象走棋产生的棋盘位置。然后使用价值网络来评估结果位置。

  3. 通过使用 MCTS(蒙特卡罗树搜索)重复此操作n次,这导致“增强”移动概率。(这些概率代表获胜的比率nMCTS 样本。

我的问题是:

  • 为什么 AlphaZero同时使用策略网络和价值网络它也可以仅使用具有 MCTS 的策略网络,或仅使用具有 MCTS 的价值网络。是否有原则性的理解为什么这很有效?(除了“它在实验中效果很好”)。

  • 为什么 AlphaZero 同时使用价值函数和“置信上限”来指导其搜索?

2个回答

首先要注意一点:AlphaGo Zero 实际上只使用一个网络,它不再像最初的 AlphaGo 那样具有单独的价值和策略网络。不过,那个单一的网络确实仍然有单独的价值策略 (两个单独的输出)......所以我想你仍然可以直观地认为它有两个网络(它们恰好在它们之间共享大量参数)。


撇开这种技术性问题,首先重要的是要很好地理解通过学习(无论是政策还是价值网络)和搜索(MCTS)实现的不同角色是什么另一方面:

  • 通过学习获得的网络(价值和政策)可以非正式地被视为为程序提供了强烈的直觉这些组件查看当前状态,并立即为要执行的操作做出“快速决策”(在策略网络的情况下)或“快速评估”以估计状态的价值(在价值网络的情况下) . 他们已经可以被训练以自己令人钦佩的水平表现,但在某种意义上总是会受到限制。当不与搜索元素(如 MCTS)结合时,它们不会执行任何额外的“推理”或“思考”。
  • 搜索组件(MCTS)为程序提供“推理”/“思考”/“审议”。它不会做出任何即时的“快速”决定,但会愉快地使用尽可能多的思考时间来继续推理并逐渐改进它在“思考”的特定回合中做出的决定。它真正专注于一个特定的回合,而不是同时学习专注于整个游戏的组件。给定无限的思考时间,它会发挥最佳效果。

为什么 AlphaZero 同时使用策略网络和价值网络?它也可以仅使用具有 MCTS 的策略网络,或仅使用具有 MCTS 的价值网络。是否有原则性的理解为什么这很有效?(除了“它在实验中效果很好”)。

注意:

  • 给定一个状态s,价值网络给出了价值的估计V(s)那个状态的s.
  • 给定一个状态s, 策略网络给出一个动作的推荐a=π(s)采取(或概率分布π(s,a)在不同的可能行动a)。

这些是完全不同类型的输出,这意味着 MCTS 算法中有不同的部分可以使用它们:

  • 输出V(s)对价值网络的评价是“事后诸葛亮”的评价。你首先必须真正达到一个状态s,然后可以使用价值网络对其进行评估。这很有用,例如,如果您想提前终止 MCTS 的播放/推出(在它一直推出到真正的终端状态之前),并为该推出返回合理的评估。但是,它不能(有效地)用于例如在推出期间的动作选择;如果你想使用V(s)估计以确定在推出中选择哪个操作,您必须首先生成所有可能的后续状态s对于所有可能的操作,评估所有这些操作,然后您最终可以相应地选择最佳操作。这在计算上是昂贵的。
  • 输出π(s,a)策略网络的一个“主动行动选择”。例如,您可以在播放/推出期间使用它来立即为当前状态选择一个动作s,无需先生成和评估所有可能的后继者s. 但是,当您希望终止推出、评估结果状态并反向传播该评估时……策略网络不提供执行此操作所需的信息,它不会为您提供状态值估计。

在实践中,确实希望能够同时完成上面描述的对一个网络来说容易做而对另一个网络来说很难做到的事情。在 MCTS 中使用强大的“直觉”(通过学习获得)进行动作选择是很重要的,因为这会导致更现实的部署,因此通常也会带来更好的评估。这不能使用价值网络来完成(好吧,它可以在 MCTS 的选择阶段/树遍历中,但一旦到达尚未完全展开的节点就不行)。还希望尽早终止推出并反向传播高质量的评估,而不是一直推出它们(这会花费更多时间并引入更多差异,因为沿着轨迹选择不切实际动作的可能性更大)。


为什么 AlphaZero 同时使用价值函数和“置信上限”来指导其搜索?

当搜索过程开始时,当我们还没有运行大量的 MCTS 模拟时,纯粹基于 MCTS 本身的评估(通常用于 UCB 方程)是不可靠的。因此,最初,对价值估计有强烈的“直觉”是有用的,正如价值网络所提供的那样。

随着执行的 MCTS 模拟数量的增加(特别是它趋于无穷大,但当然也早于实践),我们预计基于 MCTS 的评估将逐渐变得更加可靠,最终甚至可能变得比学习的更准确价值网络。请注意,价值网络经过训练可以立即为任何游戏状态提供合理的价值估计。MCTS 搜索过程将所有时间都用于计算当前游戏状态的可靠价值估计,允许“专门化”当前游戏状态。因此,随着时间的推移,我们将开始更多地依赖基于 MCTS 的评估,而更少地依赖来自价值网络的初始“直觉”。

使用策略网络和价值网络似乎与决斗 DQN 使用的技巧有关。最简单的决斗 DQN 是在最后一层附近“分支”以计算优势值的单个网络A(s,a)对于每个动作,以及价值V(s)对于当前状态。明确地将每个动作的优势与当前状态的值分开,在 Atari 基准测试中具有更好的训练稳定性、更快的收敛性和更好的性能(Dueling Network Architectures for Deep Reinforcement Learning,Wang et al. 2015)。这是因为它明确了Q价值观:

Q(s,a)=V(s)+A(s,a)

AlphaZero 和决斗 DQN 之间的区别似乎在于,它不是使用具有不同分支的相同网络来近似V(s)A(s,a),而是使用不同的价值和策略网络。

这只是一个类比,但我认为它说明了为什么区分问题的不同组成部分可以使学习复杂问题变得更容易。