「机器之心走近全球顶尖实验室：UCL多智能体强化学习研究团队」系列直播今晚第四期，来自UCL汪军教授团队的杨耀东博士将带来分享：Dealing with Non-transitivity in Two-player Zero-sum Games。
- 相关论文：Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games
- 论文链接：https://arxiv.org/abs/2106.02745
- 直播链接：https://jmq.h5.xeknow.com/s/3TEGZb（点击阅读原文直达）
研究动机
如何高效的求解纳什均衡，尤其是大规模博弈的纳什均衡，一直是多智能体领域中的研究热点。它在游戏 AI 上（例如德州扑克，星际争霸，王者荣耀等）有着广泛的应用。
然而解决两人零和博弈通常需要许多以博弈论知识为基础的人为设计的算法。目前，基于种群的策略池扩展方法，如Double Oracle /PSRO，是其中一类主要算法。该系列方法基于博弈理论构建了全自动的课程设计（Auto-curricula）机制，即在每个回合，通过训练对当前对手策略池内纳什均衡的最优反馈策略（best response），从而完成对自己策略池的扩展，进而最小化被剥削值（Exploitability），最终收敛到纳什均衡。
在该团队的最新工作中，他们发现 AI 完全有能力从零开始仅从数据中去发现这些基于博弈论的算法 (也就是 learning to learn )，并达到超过最先进博弈求解器的效果。具体来讲，该论文首次发现了，在求解双人零和博弈的过程中，AI 可以仅从数据中就自己发现多智能体学习算法， 例如学会了什么是纳什均衡，而不需要先验的博弈论知识去构建学习算法。在数十个真实游戏中，该论文发现AI自己学会的求解算法有着比最强基线PSRO算法更好的效果。更令人着迷的是，AI 自己发现的学习算法拥有很强的泛化能力，例如，在 Kuhn Poker 上发现的求解算法可以用来求解 Leduc Poker。此项工作可能会开启一个有希望的未来方向，即仅从数据中发现通用的多智能体学习算法，并且最少程度的使用人类的先验知识。
主要解决哪些问题
该论文首次提出并实现了在不需要先验博弈论知识的前提下，仅通过智能体与对手的交互数据，让AI自主发现零和博弈求解算法的算法框架。
虽然目前基于博弈论的策略池扩展方法（PSRO等）已被证明在最优策略可获得的假设下，可以收敛到纳什均衡，但在实际的大规模游戏中，主流策略优化算法（如强化学习）仅能保证近似最优策略条件被满足。因此基于博弈论的自动课程设计(auto-curricula)并不总能产生合理的课程设计，使得策略池扩展的过程受到限制。该论文的算法通过元学习(learning to learn)的方式，自适应的产生更为合适的自动课程，从而在近似最优策略可得的情况下，实现更好的策略池扩展，获得更低的被剥削值（Exploitability）。
方法
首先，考虑到自动课程选择策略需要对不同博弈（Game）具有一定泛化性，该论文使用神经网络作为自动课程选择策略。同时，为了保证该神经网络对不同的Game都具有泛化性，该论文假设存在一个 Game 服从一个分布 P(G)，通过在分布中采样Game完成元学习过程。该策略网络通过输入Meta-game的回报矩阵，产生策略池中策略的概率分布，作为对应的自动课程。通过对该自动课程的最优对抗（Best response），实现策略池拓展。 该策略网络具有的特点是输入维度为 N*N, 输出维度为 N*1，且 N 会随着策略拓展过程逐渐增大。且由于其为课程选择策略，神经网络需要满足对应的行交换不变性（row permutation invariance）和列交换置换性（column permutation equivariance）。根据相应需求，我们设计了三种策略网络，分别基于MLP，一维卷积Conv1d 和循环神经网络 GRU。
该论文将课程选择策略优化问题建模成 Exploitability 最小化问题。由于整个策略池拓展的过程中的课程选择，策略拓展本身是可微的，该论文主要探讨Best response过程对模型优化的影响。针对Best response 可微和不可微的条件，该论文提出了对应的两种元学习算法：LMAC 和 ES-LMAC，实现自动课程选择策略的学习。对于可导的 Best response 过程，LMAC将策略池扩展方法的过程微分化，实现对于 Exploitability 对于自动课程选择策略模型参数的反向传播。其中如何完成 Best response 过程的反向传播是算法中的重点
LMAC 主要讨论基于梯度下降和基于 RL的Best response 过程。针对基于梯度下降的Bestresponse 过程，算法可以通过自动微分工具完成 Meta-gradient 的反向传播过程。同时，针对于梯度步较多的情况，LMAC 使用 Implicit gradient ，通过二阶梯度的逆矩阵完成了轨迹无关的Meta gradient 计算过程，节省了运算时间与空间。针对使用 RL 算法的情况，LMAC 通过无偏的 DICE 算符，完成 RL 过程中一阶与二阶策略梯度的无偏估计，最终实现Meta-gradient 的反传。ES-LMAC主要针对于不可导的 Best response 过程进行元学习。对于基于复杂的 RL 算法如PPO，或搜索类的 Best response 算法，LMAC无法将这些过程可微化。ES-LMAC 通过零阶的进化策略（Evolutionalstrategy）完成课程选择策略的优化。通过模型参数扰动给exploitability带来的变化量实现模型更新梯度的估计。以下为 LMAC 与 ES-LMAC 算法的算法框图。
关键结果和结论
该论文分别在五种双人零和博弈游戏：Game of Skill, Differentiable Lotto,2D-RPS,Iterated Matching pennies 和 Kuhn Poker 上进行了实验。
有效性验证
最终实验结果表明，在不同 Best response 情况下，训练出的自动课程选择策略在 Exploitability 优化上基本与基于博弈论的课程选择算法（PSRO）持平甚至更好，验证了提出算法的有效性。
可视化
该论文在 2D-RPS 环境中进行课程与策略可视化，探究模型学习的课程选择策略与基于博弈论的课程选择策略的差别。在 approximate best response 条件下，该结果解释了模型课程比Nash均衡课程更低的 Exploitability的原因。经过学习的课程选择策略将充分考虑best-response本身的强弱从而给出对应的合适课程，极大增强策略的多样性。而基于Nash均衡的课程在第7个iteration后就无法提供新的有效策略。
消融实验
该论文对梯度回传的 Window size 以及模型种类以及模型大小进行了消融实验，并探讨了不同组件对于算法的影响。结果表明，window size大小与模型训练效果成正比关系，同时GRU模型 大网络可以取得比较优异的效果。
泛化能力
为了衡量算法的泛化能力，该论文在Out of distribution 的游戏上测试了模型效果。例如，在固定维度Gos Game上训练的模型可以泛化到其他维度甚至其他种类NFG Game上并取得比基线更好的效果。同时，仅仅在相对简单的Kuhn Poker上训练得到的课程选择策略可以在更为困难的 Leduc Poker 上进行泛化并获得比基线更好的效果。这充分展现了算法学习的课程选择策略的泛化能力。
创新点
首次提出了基于元学习（learning to learn）的课程策略发现算法，在不需要先验博弈论知识的情况下，让AI自动发现并完成了对于零和博弈的求解，并且AI自主发现的算法具有高泛化性，可以求解类似游戏。
综合评价
该算法创新的通过元学习实现了针对于自动课程选择策略的学习，让 AI 仅从数据中就自己学会了在求解双人零和博弈的算法。实现了无显式博弈论知识的课程选择策略，并通过数十类真实游戏及扑克验证了AI所发现求解算法的泛化能力。
