「人机对抗中的博弈学习方法」最新2022综述

2022 年 9 月 11 日 专知

近年来，人机对抗智能技术作为人工智能领域的前沿方向取得了一系列突破性的进展，如 AlphaGo 和 DeepStack 分别在围棋和二人无限注德州扑克中击败了人类专业选手. 这些突破离不开博弈论和机器学习的深度结合. 本文通过梳理当前人机对抗智能技术领域的重要工作，深入分析博弈论和机器学习在其中发挥的作用，总结了面向人机对抗任务的博弈学习研究框架，指出博弈论为人机对抗任务提供博弈模型和定义求解目标，机器学习帮助形成稳定高效可扩展的求解算法. 具体地，本文首先介绍了人机对抗中的博弈学习方法的内涵，详细阐述了面向人机对抗任务的博弈学习研究框架，包括博弈模型构建、解概念定义、博弈解计算三个基本步骤，之后利用该框架分析了当前人机对抗智能技术领域的典型进展，最后指出了人机对抗中的博弈学习未来发展可能面临的挑战. 本文梳理总结的人机对抗中的博弈学习研究框架为人机对抗智能技术领域的发展提供了方法保障和技术途径，同时也为通用人工智能的发展提供了新思路.

周雷，尹奇跃，黄凯奇. “人机对抗中的博弈学习方法”, 计算机学报，2022.

(https://cjc.ict.ac.cn/online/bfpub/zl-2022323165812.pdf)

1 引言

人机对抗智能技术研究计算机博弈中机器战胜人类的方法，是当前人工智能研究领域的前沿方向，它以人机（人类与机器）和机机（机器与机器）对抗为主要形式研究不同博弈场景下，机器智能战胜人类智能的基础理论与方法技术[1] . 人机对抗智能技术通过人、机、环境之间的博弈对抗和交互学习，探索巨复杂、高动态、不确定的对抗环境下机器智能快速增长的机理和途径，以期最终达到或者超越人类智能.

人机对抗智能技术的突破离不开机器学习的发展，机器学习主要研究如何让机器通过与数据的交互实现能力的提升[2][3] . 然而，与传统的机器学习关注单智能体（single-agent）与环境的交互不同，人机对抗智能技术研究的场景往往包含两个或两个以上智能体，也就是多智能体（multi-agent）的情形，这些智能体都拥有自己的优化目标，比如最大化自身收益. 此时，如果直接应用单智能体机器学习方法，得到的智能体（称为中心智能体）一般表现欠佳[4][5] . 这是因为传统机器学习方法假设数据的产生机制是平稳的（stationary）[6]（即数据均来自于同一个分布，简称为环境的平稳性），这一假设忽略了研究场景中的其他智能体，而这些智能体也同时在进行学习，因此其行为模式会随着时间发生变化，从而破坏中心智能体所处环境的平稳性，进而导致传统机器学习方法失去理论保证[2][3] . 更为严峻的是，随着人机对抗场景中智能体数量的增加，环境非平稳的问题将会愈发凸显，多个趋利的智能体在学习的过程中相互影响的情况将不可避免.

为了处理环境非平稳的问题，有学者考虑将博弈论引入机器学习方法中[7] . 这主要是因为博弈论本身就是为了研究多个利己个体之间的策略性交互（strategic interactions）而发展的数学理论. 博弈论诞生于 1944 年 von Neumann 和 Morgenstern 合著的 Theory of Games and Economic Behavior[8] . 在完全理性的假设下，博弈论给出了一系列解概念来预测博弈最终可能的结果. 博弈论早期的大部分工作关注不同博弈场景下解概念（solution concepts）的定义、精炼（refinement）、存在性及其拥有的性质 [9] . 随着博弈论的发展，部分研究者开始研究在非完全理性的情形下，个体是否可以通过迭代学习的方式来达到这些解概念，其中著名的工作包括 Brown 提出的虚拟对局（fictitious play）[10]，Hannan 和 Blackwell 研究的无悔学习（no-regret learning， regret minimization，or Hannan consistency）[11][12][13] 等.

近年来，得益于机器算力的提升和深度学习的兴起，人机对抗智能技术领域取得了一系列突破，如 DeepMind 团队开发的 AlphaGo[14]首次击败了人类围棋顶尖选手李世石，阿尔伯塔大学团队开发的 DeepStack[15]在二人无限注德州扑克中击败了专家级人类选手等. 在 AlphaGo 中，围棋被建模为二人零和完美信息扩展形式博弈，并利用自我对局、蒙特卡洛树搜索以及深度神经网络近似来对博弈进行求解；在 DeepStack 中，二人德州扑克被建模为二人零和非完美信息扩展形式博弈，求解方法结合了自我对局、反事实遗憾最小化算法以及深度神经网络近似. 从这些例子可以看出，人机对抗智能技术领域的突破离不开博弈论和机器学习的深度结合.

然而，虽然人机对抗智能技术领域目前取得了一系列突破，博弈论与机器学习交叉方向的研究却缺乏清晰的研究框架. 基于此，本文通过梳理人机对抗智能技术领域的重要工作，介绍了人机对抗中的博弈学习方法的内涵，总结了面向人机对抗任务的博弈学习研究框架，包括其组成要素和基本步骤，并利用该框架对人机对抗智能技术领域的典型进展进行了分析. 本文作者认为，随着人机对抗智能技术领域试验场景和测试环境逐渐接近真实场景，场景的复杂性和对抗性急剧增加，结合现代机器学习方法和博弈论的博弈学习方法将会在未来人机对抗领域的发展中发挥越来越重要的作用。

2 发展历史

自图灵测试这一人机对抗模式在 1950 年被提出[16]以来，博弈论和机器学习就在人工智能的发展中发挥着越来越重要的作用，并呈现出交叉融合的趋势. 本文梳理了人机对抗智能技术和博弈论领域开创性的工作和里程碑事件，并将其发展历史分为两条路线，一条是博弈论结合专家系统（见图 1 中绿色实线），另一条是博弈论结合学习方法（见图 1 中橙色虚线）.

1.1 路线一：博弈论结合专家系统

在发展路线一中，为了取得较好的人机对抗表现，研究者们主要是针对基于博弈论的 min-max 树搜索算法进行优化，并结合专家经验来改进评估函数. 路线一的简要发展历程如下: 1950年Shannon发表了第一篇利用编程来实现国际象棋走子程序的论文[17]，论文中 Shannon 参考 von Neumann 证明的 minimax 定理[8][18]设计了 min-max 搜索算法和局面评估函数. 对于局面评估函数的设计，参考的是如下定理：在国际象棋中，最终的结局只可能是以下三种当中的一种：(1) 不论白方如何走子，黑方有一种策略总能保证赢；(2) 不论黑方如何走子，白方有一种策略总能保证赢； (3)黑白双方都有一种策略保证至少平局. 1956 年 Samuel 利用第一台商用计算机 IBM 701 编写了跳棋（checkers）走子程序，并在 1959 年发表论文总结了该程序的设计思想和原理[19] . 该跳棋走子程序使用了 min-max 搜索. 1957 年，Bernstein 带领的团队在 IBM 701 上完成了第一个能下完整局的国际象棋走子程序，该程序使用了 min-max 搜索，但每次最多向后搜索 4 步，每步只能考虑 7 个备选走法. 1958 年，Newell，Shaw 和 Simon 第一次在国际象棋程序中使用 alpha-beta 剪枝搜索算法[20] . Alpha-beta 剪枝算法是 min-max 搜索算法的改进，通过剪掉明显次优的子树分支，该算法极大地降低了搜索空间. 该算法最初由 McCarthy 在 1956 年提出. 此后，跳棋和国际象棋程序的优化大多围绕评估函数和搜索算法进行改进. 随着计算能力的增强，IBM 公司开发的国际象棋程序 Deep Blue 在 1997 年利用总结了大量人类经验的评估函数和强大的搜索能力击败国际象棋大师 Kasparov，一时轰动. 该事件从此成为人机对抗智能技术发展历史上的标志性事件.

1.2 路线二：博弈论结合学习方法

路线一中采用的方法很难称得上实现了机器的―学习‖能力，在路线二中，研究者们试图克服机器对专家数据的过度依赖，希望能够打造自主学习的智能机器. 路线二的简要发展历程如下：最早在人机对抗研究中引入学习的是 Samuel，他 1957 年完成的跳棋走子程序不仅使用了 min-max 搜索，同时也引入了两种―学习‖机制[19]：死记硬背式学习（rote learning）和泛化式学习（learning by generalization）. 前者通过存储之前下棋过程中计算得到的局面得分来减少不必要的搜索，后者则根据下棋的不同结果来更新评估函数中不同参数的系数来得到一个更好的评估函数. 此外，该论文也第一次提到了自我对局（self-play）. 此后，这种通过学习来提升机器能力的思想就一直没能引起重视. 直到 1990 年前后，才陆续出现了能够学习的棋类程序. 这其中比较知名的是 1994 年 Tesauro 结合神经网络和强化学习训练出的双陆棋程序 TD-Gammon[21] . TD-Gammon 的成功引起了许多学者对学习算法的兴趣，并促成了博弈论与机器学习的初步结合，其中著名的工作是 Littman 在 1994 年正式建立了 Markov 博弈（或随机博弈）与多智能体强化学习之间的联系. 之后，Markov 博弈便作为多智能体强化学习的理论框架，启发了众多学者的研究. 同时，在该论文中 Littman 也提出了第一个多智能体强化学习算法 minimax-Q [22]. Minimax-Q 是针对二人零和博弈的学习算法，当博弈的双方都使用该算法时，最终博弈双方的策略都会收敛到二人零和博弈的最优解极大极小策略上. 值得指出的是，除了人工智能领域，博弈论领域的研究者们很早也开始了对学习方法的研究.与人工智能领域学者的出发点不同，他们关注的是在博弈模型给定的情形下，如何设计迭代学习的规则能使个体的策略收敛到均衡.此类方法之后被称为博弈学习（game-theoretic learning）方法.博弈学习方法的思想最早可以追溯到 1951 年 Brown 提出的虚拟对局（fictitious play）[10]，即采用迭代学习的方式来计算二人零和博弈的极大极小策略，之后著名的博弈学习方法包括无悔学习（ no-regret learning ） [11][12][13] 和复制动力学（ replicator dynamics）[23] . 在 1998 年，几乎与 Littman 等人同一时期，Fundenberg 和 Levine 出版了著作 The Theory of Learning in Games[24]，对之前博弈学习方法的研究进行了汇总、总结和扩展.博弈学习方法的研究为博弈论中的解概念（主要是纳什均衡）提供了非理性假设下的解释，换言之，非理性的个体在一定学习规则的指导下也能达到均衡. 此后，博弈论和机器学习领域的研究兴趣和研究内容开始交叉，逐步形成了博弈论与机器学习结合的博弈学习方法[25][26][27][28][29][30] .相关工作包括： (1) 利用强化学习方法计算博弈的解，比如 Nash-Q [31]等；(2)利用博弈论中的学习方法进行游戏 AI 的算法设计，比如针对不完美信息博弈的反事实遗憾最小化算法[28]（属于无悔学习算法的一种）； (3)利用机器学习加强博弈论中学习方法的可扩展性，比如虚拟自我对局（fictitious self-play，FSP） [29] . 相比于传统解决单智能体与环境交互问题的机器学习方法，与博弈论结合的学习方法有两个优势：一是充分考虑了多个智能体同时最大化收益时环境的非平稳问题，学习的目标是任务的均衡解而不是让某个智能体的收益最大化；二是在满足模型的假设时，这些算法一般具有收敛的理论保证.特别地，面向人机对抗任务，人机对抗中的博弈学习方法在此基础上添加了人机对抗任务建模，为的是能更好地利用和拓展现有的博弈学习方法来处理复杂的人机对抗任务.

近年来，随着深度学习的兴起，深度神经网络被广泛应用于人机对抗任务,形成了一系列优秀的模型和博弈学习算法[5][32][33][34][35][36][37][38][39][40] . 这也促进了人机对抗智能技术近期一系列的突破，包括2016 年AlphaGo击败围棋9段选手李世石，2017 年 Libratus[30]和 DeepStack[15]分别在二人无限注德州扑克中击败人类专业选手以及 2019 年 AlphaStar[41]在星际争霸 2 中击败人类顶级选手.

3 人机对抗中的博弈学习方法内涵

人机对抗中的博弈学习方法是一种面向人机对抗任务，以博弈论为理论基础、以机器学习为主要技术手段，通过智能体与环境、智能体与其他智能体的交互来获得具有良好性质（比如适应性、鲁棒性等等）博弈策略的学习方法，是实现人机对抗智能技术的核心. 具体地，人机对抗中的博弈学习方法基于博弈论建模人机对抗任务和定义学习目标，并利用机器学习方法来帮助设计高效、稳健、可扩展的学习算法以完成人机对抗任务. 为了阐述博弈学习方法与当前机器学习方法的区别与联系，本文按照系统中信息的流向以及信息产生的机制将已有的学习框架划分为一元、二元以及三元（或多元）学习. 在一元学习中，智能体从数据中获取知识，并且这个过程只涉及数据到智能体的单向信息流动，监督学习、无监督学习以及深度学习都属于一元学习（见图 2 (A)）. 在二元学习中，智能体通过与环境互动得到数据，进而获取知识，与一元学习不同的是此时数据的产生不仅取决于环境也取决于智能体，即智能体决策的好坏影响它自身学习的效果，必要时智能体还需要对环境动力学进行建模，单智能体强化学习属于二元学习（见图 2 (B)）. 在三元学习中，智能体通过与环境和其他智能体的交互获得数据，此时智能体学习的效果受到环境和其他智能体的共同影响，必要时智能体需要对环境动力学和其他智能体进行建模（见图 2 (C)），博弈学习属于三元学习.

4 人机对抗中的博弈学习研究框架

通过对博弈论和人机对抗智能技术发展历程的梳理，并结合人机对抗中的博弈学习方法的内涵，本文总结出了如图 3 所示的人机对抗中的博弈学习研究框架：人机对抗中的博弈学习研究框架以人机对抗任务为输入，首先通过博弈模型构建获得博弈模型，然后通过解概念定义得到博弈的可行解，最后通过博弈解计算输出满足需求的博弈策略组合，也就是学习任务的解. 直观来讲，人机对抗中的博弈学习研究框架将一类人机对抗任务的解决近似或等价转换为对某一类博弈问题的求解，该框架包含两个组成要素（博弈模型和博弈解）和三个基本步骤（博弈模型构建、解概念定义和博弈解计算）.

5 典型应用

上一节阐述了人机对抗中的博弈学习研究框架，本节将利用该框架对当前人机对抗智能技术领域的重要工作进行分析（如表 2 所示），这些工作基本涵盖了本文介绍的几种博弈模型，包括完美信息扩展形式博弈（围棋）、不完美信息扩展形式博弈（德州扑克）以及部分可观测 Markov 博弈（星际争霸 2）. 各工作的具体分析如下：

6 总结与展望

人机对抗智能技术是人工智能发展的前沿方向，它通过人、机、环境之间的博弈对抗和交互学习研究机器智能快速提升的基础理论与方法技术. 为了更好地促进人机对抗智能技术的发展，本文通过梳理人机对抗智能技术领域的重要工作，总结了面向人机对抗任务的博弈学习研究框架，指出了博弈论和机器学习在其中发挥的作用，阐述了人机对抗中的博弈学习方法的两个组成要素和三个基本步骤，并利用该框架分析了领域内的重要进展. 与此同时，本文就当前人机对抗中的博弈学习方法面临的理论和应用难点问题进行了介绍，包括非零和博弈求解目标定义、博弈学习方法的可解释性、多样化博弈学习测试环境构建以及大规模复杂博弈快速求解. 人机对抗中的博弈学习方法是人机对抗智能技术的核心，它为人机对抗智能技术领域的发展提供了方法保障和技术途径，同时也为通用人工智能的发展提供了新思路.

专知便捷查看