引用本文

王龙, 黄锋. 多智能体博弈、学习与控制. 自动化学报, 2023, 49(3): 580−613 doi: 10.16383/j.aas.c220680

Wang Long, Huang Feng. An interdisciplinary survey of multi-agent games, learning, and control. Acta Automatica Sinica, 2023, 49(3): 580−613 doi: 10.16383/j.aas.c220680

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c220680

关键词

博弈论，多智能体学习，控制论，强化学习，人工智能 

摘要

近年来, 人工智能(Artificial intelligence, AI)技术在棋牌游戏、计算机视觉、自然语言处理和蛋白质结构解析与预测等研究领域取得了众多突破性进展, 传统学科之间的固有壁垒正在被逐步打破, 多学科深度交叉融合的态势变得越发明显. 作为现代智能科学的三个重要组成部分, 博弈论、多智能体学习与控制论自诞生之初就逐渐展现出一种“你中有我, 我中有你” 的关联关系. 特别地, 近年来在AI技术的促进作用下, 这三者间的交叉研究成果正呈现出一种井喷式增长的态势. 为及时反映这一学术动态和趋势, 本文对这三者的异同、联系以及最新的研究进展进行了系统梳理. 首先, 介绍了作为纽带连接这三者的四种基本博弈形式, 进而论述了对应于这四种基本博弈形式的多智能体学习方法; 然后, 按照不同的专题, 梳理了这三者交叉研究的最新进展; 最后, 对这一新兴交叉研究领域进行了总结与展望.

文章导读

近年来, 随着人工智能(Artificial intelligence, AI)技术的飞速发展, 博弈论在社会智能[1-2]、机器智能[3]、合作智能[4]、AI安全[5-6]和AI伦理[7-8]等新兴交叉研究领域中扮演着越来越重要的角色. 特别地, 通过结合多智能体学习与控制论等理论方法, 博弈论已成为AI和自动控制领域中的一个热点研究方向.

从本质上讲, 所谓博弈论就是一类研究理性智能体(Agent)①之间策略交互的数学理论与方法[9]. 它是现代数学的一个分支, 也是运筹学的一个重要组成部分. 虽然博弈论的早期思想可以追溯到公元前, 但其作为一个独立的研究领域正式诞生的标志是von Neumann和Morgenstern于1944年合著的《博弈论与经济行为》 (Theory of Games and Economic Behavior)一书[10]. 作为多智能体系统或者分布式AI (Distributed AI)的一个研究主题[11-13], 多智能体学习主要研究多个智能体交互的策略学习问题. 从其发展历程上讲, 多智能体学习与博弈论几乎具有一样长的历史. 例如, 早在1951年, 文献[14]就提出了一类称为虚拟对弈(Fictitious play)的学习方法用于求解博弈的Nash均衡问题. 尔后, 在上世纪80年代后期, 伴随着学术界对演化计算、社会学习、交互学习和多智能体场景下的强化学习产生的广泛兴趣, 多智能体学习的研究开始在AI领域中兴起[12, 15]. 特别地, 近年来借助多智能体学习在棋牌[16-18]和视频游戏[19-21]等特定任务上取得的突破性进展, 这一方向在AI领域中再次掀起了热潮, 成为AI研究的核心内容之一. 与博弈论的发展历程相类似, 虽然人类进行自动控制的生产实践最早可以追溯到公元前[22], 但控制论作为一个独立的研究领域正式诞生的标志是Wiener于1948年撰写的《控制论》 (Cybernetics)一书[23]. 通过对比讨论 “动物智能” 与 “机器智能” 中的若干重要问题, Wiener指出“智能的首要问题是‘学习’”[24]. 综上可见, 虽然博弈论、多智能体学习与控制论分属不同的研究领域, 但究其发展根源和轨迹, 它们从来都不是相互割裂的, 而是紧密关联、相互融合的, 展现出一种 “你中有我, 我中有你” 的景象.

反映到具体的研究中, 博弈论、多智能体学习与控制论的融合通常包含在三种不同的场景设置中. 第一种设置为智能体之间完全合作. 在该设置下, 连接博弈论、多智能体学习与控制论的一种典型博弈形式是团队博弈(Team game)[25-26], 即所有博弈者具有一个相同收益函数的博弈形式. 在博弈论中, 团队博弈最初用于研究组织问题[25]. 而在多智能体学习中, 这类博弈主要用于处理多智能体的合作序贯决策问题, 也为发展合作型多智能体强化学习算法提供模型框架[27-28]. 考虑到分布式控制与团队博弈的信息结构问题[29]具有诸多相似之处, 在控制论中, 团队博弈主要用于分析团队决策问题[26]. 如果博弈的所有博弈者具有相同的(全局)信息结构, 团队博弈中的决策问题则可以转化成一个传统的集中式控制问题; 而如果每个博弈者具有不同的(局部)信息结构, 团队博弈的决策问题则可以转化成一个多智能体合作控制问题或者分布式控制问题[30-31]. 虽然团队博弈最早提出于上世纪50年代[25], 但时至今日, 它在控制领域中仍然是一个重要的研究主题[32-34]. 第二种设置为智能体之间完全竞争. 在该设置下, 连接博弈论、多智能体学习与控制论的一种典型博弈形式是零和博弈(Zero-sum game), 即两个博弈者具有零和收益关系(一个博弈者的收益是另一个博弈者的损失)的博弈形式. 在博弈论中, 零和博弈主要用于研究具有完全对立目标的博弈者间的决策问题. 而在多智能体学习中, 这类博弈主要用于处理多智能体的竞争序贯决策问题, 也为发展基于极大极小原理的多智能体强化学习算法提供模型框架[35]. 相比而言, 在控制论中, 零和博弈常用于处理含不确定因素的系统控制(鲁棒控制)问题[36-37]. 在该类问题中, 控制器(Controller)通常被视为一个最大化某一特定性能指标的博弈者; 而系统的不确定性(如干扰、噪声)则被视为另一个博弈者, 其目标是使控制器所最大化的性能指标最小化. 第三种设置为智能体之间既不完全合作又不完全竞争, 即混合设置. 在该设置下, 多智能体系统所形成的博弈是一个一般和博弈(General-sum game). 对于这类博弈, Nash均衡一般是标准的解[38]. 在多智能体学习中, 这类博弈通常用于处理一般化的多智能体序贯决策问题, 也为发展混合型的多智能体强化学习算法提供模型框架[39-40]. 相比而言, 在控制论中, 这种设置下的博弈者通常被视为是控制器, 而博弈者的策略被视为是控制律(Control law). 为了实现一个特定的任务目标, 比如收敛到一个Nash均衡, 博弈者的策略更新规则或学习算法通常需要进行额外设计[30, 41].

由于学科发展等种种原因, 博弈论和自动控制的研究对象曾经一度存在一些差异. 但借助AI和多智能体学习等技术, 它们之间的差异如今正在慢慢变小. 博弈论的研究对象一般是理性的“智能体”, 或者是具有智能的“生命体”, 比如人和动物等[9-10]; 而自动控制的研究对象一般是“机器”, 或者是无生命的“物理对象”, 比如机器人和航空航天器等[22, 42]. 然而, 近年来在AI技术和信息技术的推动作用下, 传统无生命的物理对象通过机器学习等方法正在逐渐被赋予如生命体一样的智能性. 与此同时, 自动控制的研究对象也在从单纯的物理系统逐步地转向机器、人与社会等更为复杂的融合交互系统[43]. 在这一全新的交互系统中, 机器不再被视为是一种无生命的物理对象, 而是作为一种智能的载体广泛地参与到人类社会的各种交互之中, 并呈现出一种人与人、人与机器、机器与机器的混合交互景象[1-4]. 然而, 这一全新的交互系统在促进人类社会发展的同时, 也将给人类带来一些新的挑战, 比如伦理问题和安全问题等. 考虑到这些新的挑战本身大部分是由多种研究对象所引发的, 比如人这类对象可能涉及到博弈论和社会学等, 机器这类对象可能涉及到控制论和机器学习等, 所以单一的学科或研究领域都会或多或少地存在着一些不足. 为此, 博弈论、多智能体学习与控制论的交叉融合有望在这方面发挥重要作用. 一方面, 它们交叉融合的本身可以促进各单一研究领域的发展; 另一方面, 它们涵盖的广泛理论体系可以为这一全新交互系统提供恰当的分析方法和研究工具.

当前无论是在博弈论领域、AI领域还是在自动控制领域, 博弈与多智能体学习的交叉[13, 44-50]、博弈与控制的交叉[30, 37, 51-53]、以及多智能体学习与控制的交叉[54-56]都是前沿的热点研究方向, 并且在这些主题下的相关工作和进展正呈现出一种井喷式增长的态势[57]. 然而, 据作者所知, 目前国内外已有的综述性文献主要集中讨论了这三者中的某两个特定领域[24, 30, 44, 47-52, 54-55, 58], 还没有文献宏观地从这三者的角度对它们的联系、区别以及最新的交叉研究成果进行全面的审视与梳理. 本文的主要目的是试图填补这一空白, 核心内容主要分为3节: 第1节主要介绍并讨论作为纽带连接博弈论、多智能体学习与控制论的四种基本博弈形式, 即标准式博弈(Normal-form game)、演化博弈(Evolutionary game)、随机博弈(Stochastic game)和不完全信息博弈(Incomplete-information game); 第2节主要论述对应于这四种基本博弈形式的多智能体学习方法, 即策略学习(Strategic learning)、学习动力学(Learning dynamics)、强化学习(Reinforcement learning)和鲁棒学习(Robust learning); 第3节按照不同研究专题梳理并介绍当前博弈、学习与控制的几类典型交叉研究成果. 最后, 针对这一重要前沿交叉研究领域给出总结与展望.

图 1  Markov决策过程和Markov博弈的示意图

图 2  基本博弈形式的一个统一理论框架图

作为现代数学的一个重要分支和运筹学的一个重要组成部分, 博弈论近年来在学术界受到越来越多的关注. 特别地, 随着多智能体系统和AI等研究领域的兴起, 博弈论、多智能体学习与控制论的交叉融合目前已发展成为一个前沿热点研究方向. 为了及时反映这一学术动态和趋势, 本文从连接这三者的四类基本博弈形式出发, 系统地讨论了它们之间的联系与区别, 论述了它们对应的各类多智能体学习方法, 还回顾了当前几个博弈、学习与控制的交叉研究专题. 作为全文内容的一个总结, 图3左边子图描述了多智能体博弈、学习与控制在宏观层面上的相互联系, 右边子图展示了本文介绍的各类博弈形式、多智能体学习方法和控制论方法之间的内在关联关系(图中的数字表示本文的章节编号).

图 3  本文介绍的各类博弈形式、学习方法和控制论方法之间的内在关联关系图

目前, 虽然多智能体博弈、学习与控制这一新兴交叉研究领域已经取得了一些初步成果, 但总体而言, 它仍然处于发展初期, 还有巨大的发展空间. 从大的方向上看, 以下几方面未来还有待于进一步探索.

1)无模型的(Model-free)博弈论或数据驱动的(Data-driven)博弈论. 在博弈论的传统研究中, 大部分工作都是基于特定的博弈模型或者发展新的博弈模型来开展的. 换句话讲, 在这些研究中, 博弈模型是事先设定的并且(或部分)为博弈者所已知的. 因此, 从方法论上讲, 它们属于基于模型的(Model-based)博弈论, 即“白盒” (White-box)的方法. 然而, 在大量与博弈论相关的实际应用, 比如视频游戏、多机器人系统、自动驾驶和无人机集群中, 获取准确的模型信息通常是比较困难的. 例如, 为了实现某些实际应用中的特定任务目标, 博弈者的收益函数通常可能需要进行额外设计[41, 231, 320]. 针对这些无模型的博弈应用问题, 如果传统基于模型的博弈论方法继续被使用去求解诸如Nash均衡等博弈问题, 那么它将自然会面临一些理论困境. 为此, 这就十分有必要去发展一类无模型的或数据驱动的博弈论方法, 即利用博弈实时产生的数据或者博弈交互后的离线数据来实现对一个博弈问题的求解(也就是“黑盒” (Black-box)或者“灰盒” (Gray-box)的方法). 目前, 虽然这方面已有一些相关工作, 比如著名的虚拟对弈方法[14, 184]和多智能体强化学习方法, 但总体而言, 这一领域仍处于发展初期, 还有许多不完善之处.

2)博弈论、多智能体学习与控制论的进一步深度融合. 目前, 在自动控制领域中, 博弈、学习与控制的大部分交叉研究工作都是基于最优控制和微分博弈来开展的. 除此之外, 博弈论和控制论本质上还有许多相通之处. 例如, 如果从博弈论的角度来看控制论, 控制系统中的控制器一般可视为博弈中的决策者, 它可以改变受控系统的演化轨迹以期达到某种理想效果; 反过来, 如果从控制论的角度来看博弈论, 博弈中的博弈者一般可视为控制系统中的控制器, 它的决策目标或偏好(Preference)通常可认为是一种控制目标. 因此, 从控制论的角度上讲, 博弈论也被视为是一类研究交互控制器之间的合作与竞争的数学理论[30]. 另外, 作为现代控制论的一个重要组成部分, 鲁棒控制[237]与鲁棒优化[179]、鲁棒博弈[180]以及鲁棒学习[233]在基本思想上均有诸多相似之处. 虽然受安全AI和鲁棒AI[5-6, 321]这一研究主题的驱动, 当前鲁棒的机器学习技术在AI领域中已成为一个热点研究方向, 但鲁棒控制、鲁棒优化、鲁棒博弈和鲁棒学习间的交叉研究在自动控制领域中目前仍比较稀少.

3)建立并发展包含其他博弈形式的学习与控制的研究框架. 本文讨论的博弈形式主要涉及标准式博弈、演化博弈、随机博弈、不完全信息博弈、势博弈和微分博弈. 除了这些基本博弈形式之外, 现代博弈论中还有一些其他新颖形式, 比如扩展式博弈(Extensive-form game)[18, 322-323]、信号博弈(Signaling game)[324]、量子博弈(Quantum game)[325-327]和平均场博弈(Mean-field game)[328-329]等. 因此, 如何建立并发展一个包含其他博弈形式的学习与控制的研究框架将是一个十分值得深入探究的课题.

4)博弈论、动力系统与深度学习的结合. 演化博弈动力学是博弈论与动力系统的一种结合形式. 考虑到当前在机器学习领域中, 动力系统与深度学习的结合是一个广受关注的研究课题[330-332]. 因此, 如果演化博弈动力学可以进一步与深度学习相结合, 那么这在理论上将是十分有意义的. 尽管当前这方面已有一些探索性工作, 比如神经复制动力学[119], 但总体而言, 这一研究方向目前才刚刚兴起并且在理论上还有诸多不完善之处.

5)博弈、学习与控制的交叉研究在一些新兴领域中的应用. 博弈论自诞生以来, 已在经济学、社会学、心理学、生物学、物理学、认知科学和计算机科学等研究领域中得到了大量卓有成效的应用. 近年来, 伴随着AI技术的快速发展, 人们也见证着一些新兴交叉研究领域的兴起, 比如社会智能[1-2]、机器智能[3]、合作智能[4]、AI安全[5-6]和AI伦理[7-8]等. 考虑到这些研究主题本身具有广泛的学科交叉性. 因此, 如何将博弈、学习与控制的交叉研究成果应用于这些新兴领域是未来一个十分值得探究的课题.

作者简介

王龙

北京大学教授. 1992年获得北京大学博士学位. 主要研究方向为人工智能, 博弈控制理论, 演化动力学. 本文通信作者. E-mail: longwang@pku.edu.cn

黄锋

北京大学博士研究生. 2016年获得电子科技大学学士学位. 主要研究方向为博弈论、多智能体学习与控制论间的交叉. E-mail: fenghuang@pku.edu.cn