【ZiDongHua 之自动化学院派收录关键词：同济大学 人工智能 】
 
　　同济大学陈杰院士团队 | 对抗博弈的决策方法综述研究团队
 
　　李修贤,孟敏,洪奕光,陈杰：同济大学电子与信息工程学院，上海自主智能无人系统科学中心研究意义
 
　　与人工智能关系密切的博弈论在众多领域具有广泛应用。而在许多实际应用中，如扑克游戏、追逃问题、海岸防卫、网络安全等，玩家之间往往具有敌对立场，即每个玩家明显具有自私行为并对其他玩家造成利益损失。在这些场景中，对抗博弈的高效智能决策方法对于玩家至关重要，其在国计民生、科技发展及国防安全等多方面扮演着重要角色。
 
 
　　本文工作
 
　　基于此，本文就对抗博弈的三种主要模型进行了系统性的综述，包括零和正规式与扩展式博弈、Stackelberg博弈以及零和微分博弈，旨在从博弈模型、研究分类、流行算法及未来展望等多维度对对抗博弈进行概述。值得注意的是，这三种博弈模型并不相互独立，从不同角度来看有可能具有一定的重叠性。例如，Stackelberg博弈和微分博弈也可以是零和博弈。
 
　　(1) 研究分类
 
　　正规式博弈用于描述玩家同时决策的情形，而扩展式博弈应用于玩家序贯决策的情况，特别对于不完美信息博弈尤其重要。而零和博弈意味着所有玩家的效用函数之和始终为零。已有文献中，零和正规式和扩展式博弈的研究大致可分为：双线性博弈、鞍点问题、多玩家零和博弈、团队博弈和不完美信息零和博弈。
 
　　Stackelberg博弈用于处理玩家具有不对称信息的情形，其中领导者具有信息与决策的主导权，并知道跟随者们的效用函数，而跟随者们通常在领导者做出决策后执行最佳响应动作。此类博弈主要包括一般性Stackelberg博弈 (GSGs) 与Stackelberg安全博弈 (SSGs)，其中后者是前者的一类特殊情况。在SSGs中，领导者和跟随者通常被叫做防卫者和攻击者。已有文献研究主要包括一般性的GSGs和SSGs、连续Stackelberg博弈 (玩家具有连续的决策空间)、不完全信息Stackelberg博弈等。
 
　　微分博弈是用于描述连续时间演化的博弈模型，即描述此类博弈的模型为连续时间微分方程。现有文献中大多研究的是二人的零和微分博弈，此类模型在追逃等多种问题中具有广泛应用。现有研究大体分为：线性二次微分博弈、非线性微分博弈、Stackelberg微分博弈、随机微分博弈等，另外，基于不同的终端时间与状态约束，研究也包括有限和无限终端时间、状态无约束和状态有约束情形。
 
　　(2) 主流算法
 
　　对于零和正规式博弈，至今已有大量算法，例如，后悔匹配 (RM)、RM+、fictitious play、 (online) double oracle等。其中，最流行的算法是基于后悔学习的，通常称为no-regret (或次线性) 学习算法，依赖于外部遗憾、内在遗憾、交换遗憾及基于纳什均衡的遗憾等概念。基于此，两个主流算法是optimistic FTRL和optimistic mirror descent。
 
　　针对零和不完美信息扩展式博弈，流行方法均基于反事实遗憾最小化 (CFR)。至今，许多更优性能的CFR变体被相继提出，包括CFR+、DCFR、LCFR、ECFR、AutoCFR等。同时涌现大量AI算法，例如，PSRO、deep CFR、single deep CFR、UDEF、PoG、NAC等。
 
　　针对Stackelberg博弈，普遍的解决办法是把问题转化成双层线性规划或者混合整数线性规划问题，然后流行的解决算法包括multiple LP方法、benders decomposition、cut and branch等。对于连续Stackelberg博弈，常用算法是梯度上升下降法，许多算法都可以看作这个算法的变体。
 
　　对于零和微分博弈，最流行的方法是粘性解方法，其关键是Hamilton-Jacobi-Isaacs方程，值函数是此方程的解。
 
　　(3) 未来展望
 
　　最后，针对对抗博弈中的诸多挑战，提出了潜在的热点研究方向，包括高效算法设计、最后迭代收敛、不完美信息、大型模型、不完全信息、有限理性、动态环境、混合博弈、博弈中的人工智能方法等。
 
　　文章信息