该论文首次提出并实现了在不需要先验博弈论知识的前提下,仅通过智能体与对手的交互数据,让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 过程的反向传播是算法中的重点
最终实验结果表明,在不同 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:已上传至直播间评论区,欢迎大家下载阅读。 |
|