一个求解零和博弈的通用框架：让人工智能自己发现算法
相关论文：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自主发现零和博弈求解算法的算法框架。
虽然目前基于博弈论的策略池扩展方法（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 算法的算法框图。
最终实验结果表明，在不同 Best response 情况下，训练出的自动课程选择策略在 Exploitability 优化上基本与基于博弈论的课程选择算法（PSRO）持平甚至更好，验证了提出算法的有效性。
该论文在 2D-RPS 环境中进行课程与策略可视化，探究模型学习的课程选择策略与基于博弈论的课程选择策略的差别。在 approximate best response 条件下，该结果解释了模型课程比Nash均衡课程更低的 Exploitability的原因。经过学习的课程选择策略将充分考虑best-response本身的强弱从而给出对应的合适课程，极大增强策略的多样性。而基于Nash均衡的课程在第7个iteration后就无法提供新的有效策略。
消融实验
该论文对梯度回传的 Window size 以及模型种类以及模型大小进行了消融实验，并探讨了不同组件对于算法的影响。结果表明，window size大小与模型训练效果成正比关系，同时GRU模型+大网络可以取得比较优异的效果。
综合评价
该算法创新的通过元学习实现了针对于自动课程选择策略的学习，让 AI 仅从数据中就自己学会了在求解双人零和博弈的算法。实现了无显式博弈论知识的课程选择策略，并通过数十类真实游戏及扑克验证了AI所发现求解算法的泛化能力。
线上直播
分享嘉宾：杨耀东，UCL汪军教授团队
分享摘要：策略空间中的不可传递性问题（A赢B，B赢C，但A不能赢C）给设计有效学习算法求解两人零和博弈游戏带来了诸多挑战。该问题存在于众多游戏中，如星际争霸、中国象棋和扑克。
在本次分享中，嘉宾将介绍其团队在设计有效联盟训练（league training）方法方面的工作，该方法可以在两人零和博弈游戏中生成近似纳什均衡的智能体。
嘉宾简介：杨耀东博士主要研究方向为强化学习和多智能体系统。他曾在顶级会议、期刊发表30多篇研究论文，并在CoRL 2020，AAMAS 2021中获得最佳论文奖。他本科就读于中国科技大学，并在帝国理工学院获得硕士学位、伦敦大学学院获得博士学位。
分享PPT：已上传至直播间评论区，欢迎大家下载阅读。