【论文阅读】DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning

1 本文解决了什么问题？

斗地主是一个非常具有挑战性的博弈，有竞争、协作、不完善的信息、庞大的状态空间等难点，特别是有大量可能的行动，而合法行动在不同的回合中差异很大。而现有的强化学习方法仅关注于简单的、较小的动作空间，因此无法在斗地主中表现良好。本文提出了一种概念简单且实际有效的斗地主 AI 系统，称为DouZero。DouZero 使用神经网络、动作编码以及并行化增强了传统蒙特卡洛方法。在具有 4 个 GPU 的单机上，训练几天就优于所有现有的斗地主程序，并且在 Botzone 排行榜上排名第一（共 344 个 AI）。

斗地主中博弈的难点：

斗地主中的玩家具有合作和竞争的博弈关系，并且状态是部分可观测的，信息交流受限。扑克游戏中表现优异的 CFR 算法及其变种在复杂的三人设置中并不健全。由于手牌组合情况较多，因此斗地主具有庞大的动作空间（斗地主具有 10410^4104 个可能的动作）。与德州扑克不同的是，斗地主中的动作很难进行抽象，这导致搜索的计算量十分昂贵，使用强化学习算法效率低。

现有的斗地主解决方法：

常规的强化学习方法：DQN 和 A3C 算法。DQN 由于动作空间变大会使得高估问题变得严重，A3C 由于无法利用斗地主的动作特征，因此无法像 DQN 一样概括部分可观测的状态。因此，A3C 和 DQN 在对战简单的规则智能体时，只有 20% 的胜率。DeltaDou：第一个与顶级人类玩家相比，达到人类水平性能的人工智能程序。它通过使用贝叶斯方法推断隐藏信息，并基于其他参与者的策略网络采样动作的算法。为了抽象动作空间，DeltaDou 基于启发式规则对 kicker 网络进行预训练，但其训练时间非常长。

综上，现有的斗地主 AI 程序计算成本高，并且由于极大程度依赖于人类知识，很可能是次优的。

2 本文的解决方法是什么？

2.1 Deep Monte-Carlo

蒙特卡洛方法（Monte-Carlo）是一种基于平均样本收益的强化学习方法。为了优化策略 π\piπ，可以通过迭代执行下列步骤，使用 every-visit MC 方法来估计 Q 值 Q(s,a)Q(s, a)Q(s,a) 表：

使用策略 π\piπ 生成一个 episode；对于每个在 episode 中的 s,as,as,a，使用所有关于 s,as,as,a 的样本的平均收益计算、更新 Q(s,a)Q(s, a)Q(s,a)；对于 episode 中的每个 sss，更新策略 π(s)←arg⁡max⁡aQ(s,a)\pi(s) \leftarrow \arg \max _a Q(s, a)π(s)←argmaxa​Q(s,a)。

步骤 2 中的平均收益通常使用累计折扣奖励进行计算。与依赖于自举（bootstrapping）的 Q 学习不同，MC 方法直接近似目标 Q 值。步骤1 中使用 epsilon-greedy 方法来平衡探索与利用。上述过程可以自然地与深度神经网络进行结合，即 Deep Monte Carlo (DMC)。具体地，使用神经网络代替 Q 值表，并用均方误差（MSE）进行网络参数更新。

虽然 MC 方法被批评不能处理不完整的事件，并且由于高方差而被认为效率低下，但 DMC 非常适合斗地主。首先，斗地珠是一个情节性的任务，所以不需要处理不完整的情节。其次，DMC 可以很容易地并行化，有效地每秒生成多个样本，以缓解高方差问题。

为什么不能直接使用 DQN？

Deep Q-Learning 是一种自举的方法，它使用下一步的 Q 值来更新当前步的 Q 值。与 DMC 相似的是，它们都是对 Q 值的近似方法，但就斗地主而言，DMC 更为合适。

首先，DQN 由于使用了自举，本身具有高估问题，而在更大的动作空间中，高估问题就更加严重了。虽然现在已经有缓解高估问题的技巧，如 Double DQN 和 经验回放，但在斗地主中实验证明，DQN 不稳定。反观 MC 方法，并不使用自举，直接对真实的 Q 值进行近似。

第二，斗地主是一个长视野、奖励稀疏的博弈场景。这可能会延缓 Q-Learning 的收敛速度。不同于 DQN，蒙特卡罗收敛不受节目长度的影响，因为它直接接近真实的目标 Q 值。

第三，在斗地主问题中，DQN 的实施并不容易，因为动作空间庞大，并且会发生变化。具体来说，DQN 在每次 max 操作时，由于需要迭代所有合法动作，会产生极高的计算成本。此外，不同状态下的合法动作是不同的，因此在批处理操作时也很不方便。

MC 方法可能会受到高方差带来的影响，这意味着需要进行更多采样让其收敛，这很容易通过并行化进行加速采样。

2.2 DouZero System

下图为扑克牌的矩阵表示方法，使用 one-hot 编码进行手牌表示。

下图为 Q 网络的结构。对于状态，作者提取几个手牌矩阵来表示手牌，其他玩家的手牌的联合和最近的移动，以及一些 one-hot 向量来表示的数量，其他玩家的牌和到目前为止玩的炸弹的数量。类似地，本文使用一个手牌矩阵来编码动作。对于神经体系结构，LSTM 用于编码历史移动，并且输出与其他状态/动作特征连接起来。

对于 actor 的并行化。作者将地主表示为 LLL，在地主前行动的农民记为 UUU，在地主后行动的农民记为 DDD。作者用多个 actor 过程和一个 learner 过程并行化 DMC，分别总结在 算法1 和 算法2 中。

learner 为这三个位置维护三个全局 Q 网络，并使用 actor 过程提供的数据，计算 MSE 损失来更新网络参数来近似目标值。每个 actor 维护了三个本地的 Q 网络，它们定期与全局 Q 网络进行同步。actor 将从游戏引擎中反复采样轨迹，并计算每个状态-动作对的累积奖励。learner 与 actor 的信息交流通过三个共享的缓冲区实现。

3 本文有什么关键的实验结果？

本文设计的实验需要解决以下问题：

DouZero 与现有的斗地主程序算法，如基于规则的，基于 RL 的，基于 MCTS 的方法对比，有什么优势？DouZero 如果考虑上抢地主阶段，会如何表现？DouZero 的训练效率如何？DouZero 与 boostrapping 和 actor-critic 方法相比表现如何？DouZero 所学到的策略与人类专家的知识是否一致？DouZero 与现有方法相比，推理时的计算效率高吗？DouZero 中，两个农民是否能够学会相互合作？

在扑克中，常见的用于衡量策略的指标是可利用度。然而，在斗地主中，由于具有三个玩家，同时有很大的状态、动作空间，因此计算可利用度是十分棘手的。为了评估算法性能，作者让算法之间进行对战。具体来说，对于两种竞争算法的 A 和 B 和给定的牌型，它们将首先分别作为地主和农民的位置。对局结束后，双方交换位置，并且牌型不变。

对比方法：

DeltaDou：一个强大的人工智能程序，它使用贝叶斯方法来推断隐藏的信息，并使用 MCTS 搜索动作。本文使用了作者提供的代码和预训练过的模型。该模型经过了两个月的训练，显示出与顶级人类玩家表现相当。CQN：组合 Q-Learning 是一个基于手牌分解和 DQN 的程序。本文使用了开源代码和作者提供的预训练模型。SL：监督学习基线。作者在内部收集了来自联盟最高级别的玩家的 226,230 场人类专家比赛。然后我们使用与 DouZero 相同的状态重构符号和神经结构，从这些数据中生成 49,990,075 个样本来训练监督代理。Rule-Based Programs：作者收集了一些基于开放的启发式的程序，包括 RHCP，一个名为 RHCP-v25 的改进版本，以及 RLCard 包 6 中的规则模型（Zha等人，a）。

评估指标：

WP(Winning Percentage)：胜率，以 A 获胜的比赛次数除以总比赛次数。ADP(Average Difference in Points)： A 和 B 每场比赛得分的平均差。基点是1，每枚炸弹都得分加倍。

3.1 与现有方法的表现对比

首先，DouZero 策略在所有基于规则的策略和监督学习中占主导地位，证明了在斗地主中采用强化学习的有效性。

其次，DouZero 的性能明显优于 CQN。回想一下，CQN 同样用动作分解和 DQN 来训练 Q 网络。DouZero 的优势表明DMC 是这确实是在斗地主中训练 Q 网络的有效方法。

第三，DouZero 的性能表现比目前最强的斗地主 AI 要更优秀。我们注意到斗地主有很高的方差，也就是说，赢得一个游戏依赖于初始手牌的强度，这是高度依赖于运气。因此，WP为 0.586，ADP为 0.258，表明比有明显的改善。

下图展示了 DouZero、DeltaDou 和 SL 的 Elo 评分。

3.2 抢地主阶段比较

作者使用人类专家数据训练一个具有监督学习的抢地主网络。将排名前三的算法，即 DouZero、DeltaDou 和 SL，放入了一个斗地主游戏的三个位置。在每个游戏中，随机选择第一个投标人，并使用预先训练的投标网络模拟抢地主阶段。该网络同时用于三个玩家上。带了抢地主阶段的 DouZero 仍具有很强的优势：

3.3 DouZero 的训练效率

使用 SL 和 DeltaDou 作为对手来绘制 WP 和 ADP w.r.t.的曲线的训练天数。

首先，DouZero 在 WP 和 ADP 方面，在一天和两天的训练中分别优于 SL。注意到 DouZero 和 SL 使用完全相同的神经结构进行训练。因此，我们将 DouZero 的优越性归因于自博弈强化学习。虽 然SL 的性能也很好，但它依赖于大量数据，数据不灵活，可能会限制其性能。

第二，DouZero 训练在 3 天和 10 天的训练时间内，在 WP 和 ADP 方面分别优于 DeltaDou。我们注意到 DeltaDou 是通过启发式上的监督学习初始化的，并且训练时间超过两个月。而 DouZero 从零开始，只需要几天的训练就能打败 DeltaDou。这表明，没有搜索的无模型强化学习在斗地主中确实是有效的。

作者还比较了不同 actor 数量的训练速度情况。使用更多的 actor 能够加速训练。作者还发现，所有这三个设置都显示出了相似的样本效率。在未来，将探索在多个服务器上使用更多的参与者来进一步提高训练效率的可能性。

3.4 与 SARSA 和 actor-critic 方法的表现对比

作者实现了两种 DouZero 的变体。首先，用时间差异（TD）目标代替 DMC 目标。这就导致了 SARSA 的一个深度神经网络版本。其次，实现了一个具有动作特征的 actor-critic 变体。具体来说，我们使用 Q 网络作为具有行动特征的 critic，并使用训练策略作为具有动作掩码的 actor 来消除非法行为。

首先，没有观察到使用 TD 学习的明显好处。观察到，DMC 在训练时间和样本效率方面的学习速度略快于 SARSA。可能的原因是 TD学习在稀疏的奖励设置中并没有多大帮助。

第二，观察到 actor-critic 的性能比较差。这就说明向 critic 添加动作特性可能不足以解决复杂的动作空间问题。

3.5 在专家数据上对 DouZero 分析

作者在整个训练过程中计算了 DouZero 对人类数据的准确性。

首先，在早期阶段，即训练的前五天，准确性不断提高。这表明，智能体通过自博弈，可能已经学会了一些与人类专业知识相一致的策略。

其次，经过五天的训练，准确度急剧下降。注意到，针对 SL 的 ADP 在5天后仍在改善。这表明，这些智能体可能已经发现了一些人类无法轻易发现的新颖的、更强的策略，这再次验证了自我游戏强化学习的有效性。

3.6 推断时间的比较

可以观察到 DouZero 比 DeltaDou、CQN、RHCP 和 RHCP-v2 快几个数量级。这是意料之中的，因为 DeltaDou 需要执行大量的蒙特卡罗模拟，而 CQN、RHCP 和 RHCP-v2 需要昂贵的手牌分解计算。然而，DouZero 在每一步中只执行神经网络的一次正向传递。DouZero 的有效推理使我们每秒生成大量样本用于强化学习。它还可以在实际应用程序中部署模型 .

3.7 案例研究

作者转储来自 Botzone 的竞赛日志，并将最大可能动作动作与其预测的 Q 值可视化。图10显示了两个农民可以合作打败地主的典型案例。

右边的农民只剩下一张牌了。在这里，底部的农民可以打一个小的单牌来帮助其他农民赢。

首先，我们发现 DouZero 输出的所有高概率动作都是极有信心获胜的小的单牌，这表明 DouZero 的两个农民可能已经学会了合作。

其次，动作 4 的预测 Q 值（0.808）远低于动作 3 的预测 Q 值（0.971）。一种可能的解释是，外面还有一个4，所以玩4可能不一定有帮助农民赢了。在实践中，在这种特殊的情况下，其他农民唯一的牌的等级不高于 4。总的来说，在这种情况下，动作 3 确实是最好的一步。

总结

本文的贡献：

将 DQN 的 TD 更新换成了 MC 更新；多 actor 并行化，加速训练，同时帮助 MC 更好地降低方差；不使用先验的人类专家知识，从零训练；当前最优的斗地主算法（但现在好像不是了）