多智能体博弈强化学习研究综述

王 军，曹 雷，陈希亮，赖 俊，章乐贵

陆军工程大学 指挥控制工程学院，南京210007

自20世纪50年代著名的达特茅斯会议首次提出人工智能的概念以来，人工智能就在不断的发展，人工智能的发展大致可分为运算智能、感知智能和认知智能几个阶段。运算智能，即快速计算和记忆存储能力。感知智能，即视觉、听觉、触觉等感知能力，如采用神经元网络方法识别图像和斯坦福大学研制的诊断和治疗感染性疾病的专家系统MYCIN，所依赖的技术主要是监督学习，监督学习解决问题的方法就是靠输入大量的标签数据学到抽象特征并分类。随着感知智能技术的不断提高和完善，人工智能也逐渐从感知智能向决策智能迈进[1]，如AlphaGo、AlphaZero和DQN在Atari游戏中的重大突破，而AlphaGo的核心算法是强化学习，相比监督学习的标签数据，强化学习只需要带有回报的交互数据[2]。然而现实世界复杂多变，物联网时代使得物物相连，单个智能体的智能决策已无法满足需求，群体智能决策逐渐成为主流，很多过去被认为是不可能解决的群体决策问题都能通过多智能体深度强化学习算法得以解决[3]，最具代表性的就是StarCraftⅡ、Dota2和德州扑克。

1 多智能体深度强化学习关键科学问题

强化学习主要解决的是序贯决策问题，需要智能体不断地与环境进行交互和尝试，当智能体通过动作与环境进行交互时，环境会给智能体一个即时回报，智能体会根据回报评估采取的动作，如果是正向的回报则加大采取该动作的概率，如果是负向的回报则减小采取该动作的概率，同时智能体的动作可能会改变环境，不断重复，最终找到最优策略使得累积回报的期望最大。在单智能体任务中，算法只需要考虑一个智能体的动作和状态，相比单智能体深度强化学习，多智能体深度强化学习要考虑的动作和状态空间都更大，每个智能体的回报不仅和环境有关，与其他智能体的动作也紧密联系，这使得多智能体学习任务的求解更加复杂。由单智能体系统向多智能体系统过渡时主要存在以下难点。

（1）维度爆炸。多智能体系统中动作空间、状态空间和参数数量大幅度增加，迫使计算量呈指数递增导致维度爆炸，该问题的主要解决办法有如下几种：一是采用混合型训练机制，即集中式训练分布式执行（CTDE），二是基于伪计数的探索算法，算法通过设计满足一定性质的密度模型来评估频次，计算在连续空间下具有泛化性的伪计数提高探索效率，缓解维数爆炸问题。

（2）环境非平稳性。多智能体强化学习中环境状态转移函数取决于联合动作，导致环境的非平稳性，解决该问题的主要办法有如下几种：一是采用AC框架，通过在训练过程中获得其他智能体的信息和行动，智能体不会经历环境动态的意外变化，二是采用对手建模，通过模拟其他智能体的策略，可以稳定智能体的训练过程，三是利用元学习更快适应非平稳性环境。

（3）信度分配。当智能体的数量增加时，信度分配是无法回避的问题，解决该问题的主要方法有平均分配、差分回报分配、优势函数分配以及Deepmind提出的基于情景记忆检索TVT算法[4]。

随着智能体数量的增加，最大化长期累积回报的期望作为学习目标很难得到收敛结果，某些特殊收敛点所对应的策略也不符合实际情况，所以多智能体强化学习中各智能体的学习目标还应该增加合理性和收敛性，并且可以从具体理论上解释。同时，在很多实际博弈场景下，最优解未必存在，这些问题都阻碍多智能体强化学习进一步发展。随着博弈理论的引入，很好地解决了多智能体直接的相互关系，博弈中的均衡解可以代替最优解以求得相对有效的策略，同时该策略具有合理性。

多智能体系统中智能体之间的关系可以用博弈论中玩家之间的关系来表示，一般分为竞争、合作和混合型。博弈论中按照博弈玩家同时决策还是先后决策分别称为标准型博弈（Normal form Games）和扩展式博弈（Extensive form Games），囚徒困境就是常见的标准型博弈，而围棋就是常见的扩展式博弈。另外，按照博弈中所有玩家收益的和是否为零可分为零和博弈和一般和博弈，根据玩家的目标是否一致分为共同利益博弈和不同利益博弈。扩展式博弈中根据信息是否已知可以划分为完全信息扩展式博弈和不完全信息扩展式博弈[5]。

多智能体中均衡、协同和合作等学习目标都会涉及到智能体之间的决策问题，博弈论的中心思想是为博弈建立一个策略交互模型，博弈论中均衡解是让博弈玩家都满意的策略组合，通过展示玩家最终会采用哪些策略来描述博弈的结果，这与多智能体深度强化学习的学习目标完美契合，利用博弈论中纳什均衡、Stacklberg均衡和元均衡等概念来指导智能体每次迭代，以使结果收敛到纳什均衡点，同时使得每个智能体的收益相对较大，收敛速度比较快。将博弈理论引入多智能体深度强化学习算法中取得了很多成果，具体的算法如图1所示。

图1 主要算法分类图Fig.1 Classification of main algorithms

2 多智能体博弈强化学习基本概念

本章重点叙述多智能体强化学习和博弈论的相关概念，最简单的强化学习数学模型是马尔可夫决策过程，博弈论中最核心的概念是纳什均衡。

2.1 马尔可夫决策过程（MDP）

MDP是一个由五元组S,A,P,R,r构成。其中，S是包含所有状态的有限集合，A是包含智能体所有动作的有限集合，P定义为P:S×A×S→[0,1]的转换函数，R定义为R:S×A×S→R的回报函数，r∈[]0,1是折扣系数，用于平衡智能体的瞬时回报和长期回报对总回报的影响。

MDP的求解目标是找到期望回报值最大的最优策略σ∗，一般用最优状态动作值函数形式化表征期望回报当智能体的数量超过一个，同时环境的改变和每个智能体的回报取决于所有智能体的动作和当前状态时则称为多智能体马尔可夫决策过程。

2.2 随机博弈（Stochastic Games，SG）

随机博弈可以看成MDP向多人博弈的推广，由如下的六元组定义：N,S,Ai,P,Ri,γ，其中N为博弈玩家的个数，当玩家的个数为1时，即退化为MDP，Ai为第i个玩家的动作，A-i为除第i个玩家外其他玩家的动作，记A=A1×A2×…×An，Ri为第i个玩家的回报函数，当每个玩家的回报函数相同时则称此博弈为团队博弈（Team Games）。

2.3 部分可观察的随机博弈（Partially Observable SG，POSG）

部分可观察的随机博弈（POSG）是在随机博弈的基础上对玩家所能观察到的信息进行了一定的约束，具体表示为N,S,Ai,P,Ri,γ,OBi,O，其中OBi为第i个玩家的观测集，联合观测集为OB=OB1×OB2×…×OBn，O为S×A→[]0,1的观测函数。去中心化的部分可观察马尔可夫决策过程（Dec-POMDP）是特殊情况下的POMDP，即所有智能体的回报函数都相同：R1=R2=…=Rn。

2.4 纳什均衡

其中，σi∈Πi，Πi是玩家i所有可能的策略集合。

2.5 元博弈（Metagame）

对于n人一般式博弈其关于智能体i的一阶元博弈iG可以表示成iG=N,Ai,…,，其中Fi表示智能体i的反应函数空间。反应函数的定义为f:A-i→Ai。对于智能体i的任意反应函数f∈Fi，以及其他智能体的任意联合动作

3 标准型博弈

在标准型博弈中，通过博弈玩家的目标是否相同，划分为共同利益博弈和不同利益博弈，常见的共同利益博弈有团队博弈、势博弈和Dec-POMDP，研究共同利益博弈最大的优势在于可以使用具有理论保证的单智能体强化学习算法。

3.1 共同利益博弈

3.1.1 团队博弈

团队博弈被反复研究的重要原因是其对于构建分布式AI（DAI）至关重要。团队博弈中，每个智能体只需要维护自己的值函数，而且值函数只取决于当前的状态和动作，从而避免了考虑联合动作时的环境非平稳和维度爆炸问题。因此，很多单智能体算法可以运用在该问题上。如果博弈存在多个纳什均衡，即使每个智能体之间的学习目标并不冲突，也会导致智能体最终不会学到最优策略的问题。

Sandholm等[6]利用有偏好的动作选择和不完整的历史采样提出了最优自适应学习算法（Optimal Adaptive Learning，OAL），并证明该方法对于存在多个纳什均衡的团队博弈中都会收敛至最优纳什均衡，但是该方法在一般的随机博弈中收敛性并不能得到保证。所以，在OAL算法基础上，Arslan等[7]提出了随机博弈的去中心化Q-learning算法，并借助双时间尺度分析以团队博弈问题为例，证明了算法在大量的随机博弈中都会稳定收敛到最优纳什均衡。

团队博弈中，获得最优解的关键是如何解决智能体之间的合作关系。Mao等提出ATT-MADDPG算法[8]，算法通过一个集中的ctitic来收集其他玩家的信息和策略，并在集中critic中嵌入注意力机制以自适应的方式对其他玩家的动态联合策略建模，当玩家的策略发生改变时，相关的注意权重就会自适应地改变，智能体就会快速地调整自己的策略。在多智能体系统中，智能体的交互并不是一直存在，某个特定的智能体也不是一直处于和其他智能体交互的状态，Liu等利用完全图对智能体的关系进行建模，提出基于两阶段注意力网络的博弈抽象机制（G2ANet）[9]，并在Traffic Junction和Predator-Prey场景下证明该方法可以简化学习过程。Zhu等为解决智能体之间通信问题，提出Partaker-Sharer框架[10]，通过在每个时间步彼此共享智能体的最大Q值来加速学习过程，并在Predator-Prey场景下验证了算法的有效性。

Yang等借用了平均场论（Mean Field Theory，MFT）的思想，其对多智能体系统给出了一个近似假设：对某个智能体，其他所有智能体对其产生的作用可以用一个均值替代，提出了平均场多智能体强化学习算法（Mean Field）[11]，将转化为只包含相邻智能体相互作用的形式：表示邻居节点的个数。Anahtarci等[12]对智能体

其中，N(j)表示智能体j邻居智能体的标签集，Nj=之间的交互作用进行近似，降低智能体交互的复杂度，并且在理论上给出了收敛性证明，能够收敛到纳什均衡点。针对智能体的数量接近无限的情况，Elie等[13]在仅依赖平均场博弈的基本动力学假设的条件下，根据每个学习迭代步骤中出现的累积误差来量化近似纳什均衡的质量，首次展示了无模型学习算法向非平稳MFG均衡的收敛。

除上述方法外，分解MDPs也可以有效解决团队博弈问题，回报函数可能只与状态的部分特征有关，而与其他特征是独立的，利用因子化的表达，可以避免在整个状态-动作空间进行迭代求解。受分解MDPs思想的启发，Vlassis等[14]将多智能体系统视为一个大型马尔可夫决策过程（MDP），基于动态贝叶斯网络和协调图（coordination graphs）使用因式分解将线性值函数作为联合值函数的近似值，值函数的这种分解允许智能体在行动时协调其动作，有效解决状态和动作空间中的指数爆炸问题，最终可以找到全局最优联合动作。

然而，协调图在实际应用中可能并不总是可用的，理想的方法是让智能体从任务中自动学习值函数分解，深度神经网络是学习这类分解的有效方法，因此多种特殊的神经网络结构被提出，典型的算法包括VDN、QMIX、QTRAN、Qatten和QPD等。VDN[15]在值函数可分解的假设下要求联合值函数是每个智能体值函数的线性和，即

由于线性假设这个前提条件，VDN算法所适用的场景比较少。为此，使用神经网络近似联合值函数的算法QMIX[16]被提出，QMIX利用集中式训练的优势，使用全局状态进行训练但QMIX为了保证独立全局最大化操作，假设联合值函数对个体值函数是单调的，用公式来表示为：

QTRAN[17]算法结合了上述VDN和QMIX的优点，认为直接用神经网络去逼近联合Q函数相对困难，因而将整个逼近过程分为两步：首先采用VDN的方式得到加和的联合值函数，作为联合值函数的近似，接着去拟合加和的联合值函数与联合值函数的差值。然而，不管是VDN算法的累加性还是QMIX算法的单调性，都从一定程度上限制了联合值函数和每个智能体的值函数之间的关系，假设过于严格。Qatten[18]算法在不引入附加假设和约束条件的情况下，首次从理论上推导出任意数量的智能体的联合值函数和各智能体的值函数的广义形式，提出基于多头注意力机制的值函数混合网络来近似联合值函数和分解单个值函数，算法在星际争霸SMAC环境中进行实验，取得良好效果。QPD[19]是另外一种值函数的分解方法，使用积分梯度的方法，沿轨迹路径直接分解联合值函数，为智能体分配信度。团队博弈下的主要算法优缺点如表1所示。

表1 团队博弈下的主要算法的优缺点Table 1 Advantages and disadvantages of main algorithms under team game

3.1.2 随机势博弈（SPG）

博弈中，如果每个玩家对于自身目标改变或策略选取，都可以映射到某个全局函数中去，这个函数就叫做势函数（potential function），这个博弈称为势博弈（potential game）。一般来说，势博弈可以被看作多智能体博弈的“单智能体成分”[20]，因为所有智能体在SPG中的利益都被描述为一个单一的势函数。

将势博弈推广至随机势博弈后，问题的复杂度会提高。随机博弈下，玩家的策略不仅要考虑自己的状态还要考虑其他玩家的行动，Macua等[21]研究了一般形式的势博弈，即策略与状态及行动时间都有关，并证明了在此前提下存在纳什均衡，同时理论证明了纯策略的势博弈中的纳什均衡可以通过求解MDP来找到[22]。Mazumdar等[23]针对势博弈提出了基于策略的动态更新算法，并应用在Morse-Smale游戏中，证明了该算法可以收敛到局部纳什均衡。在复杂的多智能体系统中，有效的学习需要所有参与的智能体之间高度协调，但是智能体之间的协调和通信往往是低效的，Chen[24]提出了集中训练和探索，并通过policy distillation来分散执行来促进智能体之间的协调和有效的学习。

3.1.3 Dec-POMDP

在Dec-POMDP中，多智能体的目标是在能观察到的局部信息基础上实现全部奖励的最大化，因此在共同利益博弈中解决Dec-POMDP问题是十分困难的，目前大多数Dec-POMDP的解决算法，包括上面的VDN、QMIX和QTRAN等算法，都是基于集中式训练和分散式执行（CTDE）的学习框架。在表示智能体的局部策略时，通常使用随机有限状态控制器，这样可以将Dec-POMDP表述为非线性规划问题，从而使用现有的优化算法，从Dec-POMDP到连续状态MDP的转换，称为占领状态MDP（occupancy-state MDP）。占用状态本质上是关于隐藏状态和观测-行动对的联合历史分布，这两者的区别是在标准的MDP中，智能体的学习目标是最优状态动作值函数，而oMDP中的智能体的学习目标是占用状态和联合行动的最优值函数，这些最优值函数往往都是分段线性的，最重要的是这些限制会使得智能体最终会收敛至全局最优而不是局部最优。

Li在系统仅部分观测时，提出生成式注意多智能体网络[25]直接对底层的生成行为的分布进行逼近，同时模型还通过在生成过程中采用混合密度来支持具有多模态分布的多智能体行为，并对缺失行为进行推断（Generative Attention），实验证明该模型可以捕获具有线性复杂度的智能体交互，处理不断演化的交互结构。在多智能体强化学习的研究很少考虑训练后的策略对新任务的迁移能力，这使得训练好的策略很难应用至更复杂的多智能体任务，为解决上述问题Ryu等提出基于多层图注意网络和多智能体AC算法[26]的模型，并证明了所提出的模型在多个混合协同和竞争任务下的性能优于现有方法。除了上述方法外，解决Dec-POMDP问题的方法还包括蒙特卡罗策略迭代法[27]，以及一种通过维护智能体之间的共享内存来分散POMDP的方法[28]。

3.2 不同利益博弈

不同利益博弈是指玩家的学习目标不同，根据所有玩家收益之和是否为零分为有限零和、一般和博弈。

3.2.1 有限零和博弈

有限零和博弈是指参与博弈的玩家个数有限，并且是严格的竞争关系，所有玩家的总体收益和支出的总和为零。在两人零和博弈中，由于两个玩家的学习目标完全相反，其纳什均衡解本质上是一个鞍点。Adler[29]证明了两人零和博弈和线性优化的等价性，即两人零和博弈可以构建为一个线性优化问题，任意一个线性优化问题也可以简化为一个零和博弈问题。在解决两人零和博弈问题中最典型的方法是最小最大值定理（The Minimax Theorem），其可以表示为如下公式：

然而，该定理并不适用于回报函数为非凸非凹的博弈。对于离散动作空间下的零和博弈，Shapley给出了第一个值迭代的方法[30]，证明了HShapley在两人零和博弈中是压缩映射，且可以收敛至纳什均衡。与Shapley基于模型的值迭代方法不同，Littman针对两人零和博弈提出了无模型的Minimax-Q算法[31]，Minimax-Q中的Minimax指的是使用最小最大值定理构建线性规划来求解每个特定状态的纳什均衡策略，Q指的是借用Q-learning中的TD方法来迭代状态值函数或动作-状态值函数。随后，Littman证明了与Q-learning相似的假设下，Minimax-Q算法的Bellman算子也是压缩映射，并且会收敛到唯一的不动点[32]，但是上述算法还是基于Q表的，因此无法应用到动作和状态空间很大的场景中。Fan等[33]结合DQN和最小最大定理提出解决两人零和博弈问题的Minimax-DQN算法，并量化了该方法求出的策略和纳什均衡之间的差异。Goodfellow等在2014年提出了生成对抗网络（GANs）利用神经网络使得求解这类问题变为可能[34]，在GANs中，两个神经网络参数化模型（生成器G和鉴别器D）进行零和博弈。生成器接收随机变量并生成“假”样本，鉴别器则用于判断输入的样本是真实的还是虚假的。两者通过相互对抗来获得彼此性能的提升。上述方法依然无法解决多智能体算法训练不稳定、智能体对环境的变化很敏感和容易陷入局部最优等问题。Li等提出M3DDPG算法[35]，核心是在训练过程中使得每个智能体都表现良好，即使对手以最坏的方式反应。

在寻找纳什均衡时，以相同的步长实现梯度-下降-上升（Gradient-Descent-Ascent，GDA），相当于在一个算法中对两个智能体应用了策略梯度方法。通过对步长的微调，GDA方法可以有效地解决部分两人零和博弈问题。Zhang等证明了当两人零和博弈中的回报函数都是线性时，交替更新比同步更新收敛的速度更快[36]。但是在双线性模型中，收敛性并不能得到保证。Mertikopoulos等[37]提出乐观镜像下降法（optimistic mirror descent）解决了双线性模型中的收敛问题，并在CelebA和CIFAR-10数据集中进行了验证。当回报函数为非凸非凹时，GDA方法也有不足，一是GDA算法可能不再收敛，二是算法收敛的点可能连局部最优都不是。为解决此问题，Jin等引入局部Stackelberg均衡，并在此基础上建立了与GDA算法的联系，证明了GDA的所有稳定极限点都是局部Stackelberg均衡点[38]。Fiez等[39]通过证明GDA算法中的收敛点为零和博弈中Stackelberg均衡的充分条件，建立了纳什均衡和Stackelberg均衡之间的联系。Zhang等[40]对GDA算法使用了“光滑化”的技巧，使得算法可以在非凸-凹的极小-极大问题的两类常见形式上收敛至最优结果。有限零和博弈下主要算法的优缺点如表2所示。

表2 有限零和博弈下主要算法的优缺点Table 2 Advantages and disadvantages of main algorithms under finite zero-sum game

3.2.2 有限一般和博弈

求解一般和随机博弈的计算复杂度是PPAD，而求解零和博弈的计算复杂度是P-complete[41]，所以解决一般和的随机博弈问题的难度比零和的随机博弈要困难很多。Herings等[42]引用拓扑学中同伦思想，提出一种可以找到求解多个独立MDPs和多人随机博弈的均衡解之间的同伦路径算法，从而使得多人随机博弈问题转化为求解多个独立MDPs问题，但是这种方法只能应用在状态集很小的两人博弈中。随后，一系列基于值的算法被提出来解决一般和随机博弈。这些方法大多采用经典Q-learning作为中心控制器，不同之处在于中心控制器运用何种均衡来引导智能体在迭代中逐渐收敛。例如，Nash-Q算法采用的就是纳什均衡，而correlated-Q算法采用的则是相关均衡（correlated equilibrium）。

传统Q-learning算法应用于多智能体系统时，每个智能体的策略都在随着训练的进行而变化，对每个智能体来说环境都是不稳定的，而策略梯度算法应用于多智能体系统时通常表现出很高的方差。Lowe等提出一种Actor-Critic策略梯度算法的扩展算法[43]，并利用集中训练分散执行框架，证明该算法在竞争和合作场景下都能有效收敛。在解决多智能体协调问题中，Stackelberg均衡在帕累托优势方面比Nash均衡具有更好的收敛性，Zhang等定义了寻找Stackelberg均衡的双层强化学习问题，并提出了一种新的双层AC学习方法[44]，允许智能体拥有不同的知识库，并在矩阵博弈中证明了双层AC可以收敛至Stackelberg均衡。

对于Stackelberg均衡，Blum等[45]研究了在大型一般和游戏中计算Stackelberg均衡的复杂性。证明了有效地计算零和博弈的纳什均衡是有效计算的大型一般和博弈的Stackelberg均衡的充分条件。Friend-or-Foe Q-Learning算法[46]（FFQ）也是从Minimax-Q算法拓展而来，对于某个智能体运用FFQ算法，是将除该智能体以外的所有智能体分为两组，一组称为friend的智能体帮助其一起最大化其奖励回报，另一组称为foe的智能体对抗它并降低它的奖励回报，这样多智能体的一般和博弈就转化为了两个智能体的零和博弈。但是此类算法所共有的缺陷是算法的假设条件过于苛刻，运用至现实场景中，收敛性往往无法保证。

除了集中式Q-Learning算法，分散式Q-Learning算法也因其可扩展性而被广泛的关注，并且分散式QLearning算法结合two-timescale随机分析在强化学习中取得了很多不错的结果[47]。two-timescale随机分析证明了两个耦合且变化速度不同的随机过程，如果固定慢过程，则快过程一定会收敛至某个极限点。Prasad等[48]将two-timescale随机分析运用到critic网络和actor网络，证明了如果critic网络比actor网络更新得更快，它可以确保训练在一般和随机博弈中达到一个平稳的局部纳什均衡。Heusel等[49]提出two-timescale更新规则（TTUR），在任意GAN损失函数上使用随机梯度下降训练GAN，并证明了在一般和博弈中可以收敛于局部纳什均衡。通过直接策略搜索收敛到纳什均衡的方法在早期只能适用于两人两动作的博弈，应用范围极其有限，虽然随着GANs的出现，解决了特定场景下的局部纳什均衡问题，但并未取得重大突破，主要原因是损失函数的可导性一般不成立。

4 扩展式博弈

如果效用函数是共有知识，则称这样的博弈为完全信息博弈，如围棋、象棋，否则为非完全信息博弈，如德州扑克。

4.1 完全信息的扩展式博弈

纳什在博弈论中主要的贡献是证明了在有限玩家有限次标准型博弈下，一定存在混合策略的纳什均衡。但是这个纳什均衡是假设玩家在决策时，其他玩家的策略不会改变，但在扩展式博弈中先决策玩家无法知道后决策玩家的策略，所以会导致不可置信的纳什均衡存在，因此扩展式博弈中均衡解应该在每个子博弈中都是纳什均衡解，这时的解称为子博弈精炼纳什均衡。求解子博弈精炼纳什均衡最典型的算法是alpha-beta修剪算法，该算法通过逆向归纳从最底部的子博弈中求出纳什均衡，然后通过深度优先搜索算法不断将上层信息节点加入其中，形成新的子博弈并求出新的纳什均衡，最终在搜索完整个博弈树时求出的纳什均衡即为子博弈精炼纳什均衡。近年来，完全信息的扩展式博弈最大的突破是AlphaGo系列，AlphaGo系列使用蒙特卡洛树搜索的框架进行模拟，并在学习策略时中使用监督学习，有效地利用人类棋手的棋谱，通过强化学习，从左右互搏中提高自己，超越人类棋手水平。

4.2 不完全信息的扩展式博弈

现实中博弈往往以不完全信息的扩展式博弈存在，如即时战略游戏和军事对抗，不完全信息的扩展式博弈被认为是下一代人工智能的重难点之一。解决不完全信息的扩展式博弈主要有三个难点，一是子博弈之间相互关联，二是存在状态不可分的信息集，这使得强化学习中基于状态的值估计方法不再适用，三是博弈的求解规模比较大，如桥牌和德州扑克的信息集数目分别为1067和10162。近几年以德州扑克为例，不完全信息的扩展式博弈取得了不错的进展。

在不完全信息扩展式博弈中，由于策略之间的相互影响，直接对联合策略进行建模很难实现，Tian等基于策略变化密度提出了联合策略搜索（JPS）方法[50]，该方法可以在不重新评估整个博弈的情况下，迭代地改进不完全信息博弈中协作智能体的联合策略，并在网格世界中对算法性能进行了验证。解决不完全信息博弈主要有CFR系列和NFSP系列算法，两个系列算法的验证环境主要为德州扑克。

4.2.1 反事实遗憾值最小化算法（CFR）

记Pσ i(s)为玩家i从初始状态出发，遵循策略σ到达状态s的概率，Pσ-i(s)为从初始状态出发，除玩家i外，所有玩家都遵循策略σ到达状态s的概率，Pσ i(z|s)玩家i从状态s出发，遵循策略σ到达终止状态z的概率，ui(z)为到达终止状态的效用函数，反事实值的定义如下：

图2 CFR算法迭代步骤Fig.2 Iteration steps of CFR

CFR算法结合了遗憾值最小化算法[51]和平均策略，通过最小化单个信息集合上的遗憾值来达到最小化全局遗憾值的目标，最终使得博弈过程中的平均策略趋近于纳什均衡。由于需要遍历整个博弈树，时间复杂度和收敛速度慢是算法的主要缺点。

为了减少CFR算法的时间复杂度，Zhou等提出的Lazy-CFR[52]针对原始CFR必须在每一轮中遍历整个游戏树的缺点，采用惰性更新策略，在只需要访问部分博弈节点条件下，取得和CFR同等效率。对于CFR算法的改进还有最佳响应剪枝算法（Best-Response Pruning，BRP）[53]，Brown等证明了在使用CFR算法时加入BRP会减少对于收敛到纳什均衡没有帮助的动作，从而加速收敛和节约空间。

Lanctot等提出了一类基于蒙特卡洛抽样的在线算法（MCCFR）[54]，包括基于结果抽样的CFR算法和基于外部抽样的CFR算法，两者都可以计算一个近似纳什均衡。虽然MCCFR算法减少了CFR算法的时间复杂度，但是由于蒙特卡洛搜索本身会带来高方差，所以Schmid等以没有访问到的节点的平均效用值作为baseline提出了减小方差MCCFR算法[55]（Variance Reduction MCCFR，VR-MCCFR），有效缓解了高方差的问题，并且从理论上证明了该方法的无偏性。MCCFR算法和VR-MCCFR算法都是基于表格的CFR，这就要求大量的领域知识来对状态节点进行抽象处理，所以上述算法的性能和扩展性都不理想。Li等提出一种不完全信息博弈的双神经网络表示方法（Double Neural Counterfactual Regret Minimization，DNCRM）[56]，其中一个网络表示累积遗憾，另一个网络表示平均策略，并在One-Card-Poker游戏中证明了该方法的收敛速度优于其他算法。

Waugh等使用回归树作为函数近似器，提出回归CFR算法[57]，虽然一定程度上提升了性能，但是该算法仍有两个缺点。首先，关于信息集的特征仍需要先验知识。其次，回归CFR还是需要遍历整个博弈树，这使得它在非简单博弈中的时间复杂度仍然很高。随着神经网络的出现，可以利用神经网络强大的拟合能力来作为函数近似器，这就是Deep-CFR算法[58]，该算法训练一个价值网络来估计反事实值，同时，训练策略网络来近似所有迭代的平均策略。但是Deep-CFR算法要求智能体记住之前所有的历史信息，然而大多数深度强化学习中的智能体并没有循环神经网络。同时，该算法的目标是引导智能体获得最大化平均回报，但是对于某些没有终止状态的应用场景就无法最大化平均回报，从而使得该算法失效。

Steinberger使用函数近似和部分树遍历来泛化博弈的状态空间，提出Single Deep CFR（SD-CFR）算法[59]，该算法直接从过去迭代的Q值网络缓冲区中提取平均策略，从而避免训练平均策略网络，具有较低的总体近似误差，提高了Deep-CFR的收敛速度。但是SD-CFR算法无法解决不完全信息博弈，Steinberger等改进上述算法提出基于遗憾的深度强化学习方法[60]（DREAM），一种CFR的神经网络形式，在保持低方差的前提下在不完全信息中收敛至纳什均衡。

Kash等[61]放宽智能体具有完美回忆的条件，提出局部无后悔学习（LONR），它使用类似Q学习的更新规则来允许在没有终端状态或完美回忆的情况下进行学习，并在NoSD游戏中实现了收敛性。CFR系列主要算法优缺点如表3所示。

表3 CFR系列主要算法优缺点分析Table 3 Analysis of advantages and disadvantages of CFR series algorithms

4.2.2 虚拟自我对弈算法（NFSP）

虚拟对弈（Fictitious Play）是根据对手的平均策略做出最佳反应来求解纳什均衡的一种算法，重复迭代后该算法在两人零和博弈、势博弈中的平均策略将会收敛到纳什均衡。但是FP算法对于对手的平均策略很敏感，很难运用至高维度大型问题中。Heinrich等提出广泛的虚拟对弈（Extensive Fictitious Play），将虚拟对弈的概念扩展到扩展式博弈。然而，状态在每个树节点中都以表的形式表示，因此泛化训练是不切实际的，而且平均策略的更新需要遍历整个游戏树，这就给大型游戏带来了维数灾难。Fudenberg等通过加入噪声引入随机虚拟对弈（Stochastic Fictitious Play，SFP）[62]，证明了该算法在零和博弈和势博弈上的收敛性，然而，当信息集的数目较大时，算法的性能较低。Heinrich等将FSP与神经网络函数近似结合，提出神经虚拟自我对弈（NFSP）算法[63]，玩家由Q-学习网络和监督式学习网络组成。算法通过贪婪深度Q学习（greedy deep Q-learning）计算最佳反应，通过对智能体历史行为的监督学习计算平均策略。随后，Heinrich又将NFSP推广至部分可观测的场景中，并在德州扑克上取得了不错的效果。作为NFSP算法的直接应用是OpenAI和牛津大学合作提出的LOLA算法（Learning with Opponent-Learning Awareness）[64]，让智能体在更新自己策略的同时，考虑到其他智能体的学习过程，每个LOLA智能体都调整自己的策略，用有利的方式塑造其他智能体的学习过程，该算法在重复囚徒困境博弈中收敛到了互惠策略。

但是NFSP在搜索空间和搜索深度规模较大的游戏中表现较差，同时，最佳反应依赖于深度Q-Learning的计算，这需要很长时间的计算才能收敛。为解决上述两个问题，蒙特卡洛神经虚拟自我对弈（Monte Carlo Neural Fictitious Self Play，MC-NFSP）和异步神经虚拟自我对弈（ANFSP）方法[65]被提出，MC-NFSP算法结合了NFSP与蒙特卡洛树搜索的优点在双方零和的棋牌游戏中评估了该方法。实验表明，在奥赛罗棋中，MC-NFSP将收敛到近似纳什均衡，但NFSP无法做到。ANFSP使用并行的actor来稳定和加速训练，多个玩家并行进行决策，并在监督学习中计算小批量的梯度。与NFSP相比，这减少了数据存储所需的内存，并在双人零和扑克游戏中进行了实验验证，与NFSP相比，ANFSP可以更加稳定和快速地接近近似纳什均衡。

除上述方法以外还可以通过在强化学习中加入搜索、修改更新方式和对手建模等方法解决非完全信息博弈问题。Brown等将搜索加入强化算法中提出ReBeL算法[66]并推广到不完全信息博弈中，在利用少量领域知识的前提下取得良好结果。

利用强化学习AC算法中的优势值的定义（A=Q−V），即优势值量化了选择某个行为的优势，同时也是没有选择某个行为的劣势，而这正好符合非完全信息博弈中遗憾值的定义，Srinivasan等[67]基于这个思想提出三种不同的更新策略，并与AC算法和CFR算法在简化版的德州扑克环境进行了验证。基于不确定性的量化理论，从效用的不确定性进行奖励重塑和模型的不确定性增加探索，对非完全信息博弈条件的不确定性进行量化，提出自适应的切换方法（Uncertainty Fueled opponent），并与经典的CFR和NFSP算法在德州扑克环境下进行了比较，该方法都能稳定地超越CFR和NFSP。

以德州扑克为代表的非完全信息扩展式博弈虽然在CFR和NFSP系列算法下取得了突破性的进展，但是远没有彻底解决非完全信息扩展式博弈，非完全信息扩展式博弈仍然是深度强化学习后续突破的重难点。要想解决这类问题可能首先需要解决两个问题：一是如何量化非完全信息下的信息的不确定性，环境的非平稳性；二是如何科学高效解决多智能体之间的沟通、协作问题。NFSP系列主要算法优缺点如表4所示。

表4 NFSP系列主要算法优缺点分析Table 4 Analysis of advantages and disadvantages of NFSP series algorithms

5 多智能体博弈强化学习算法的重难点

博弈论主要是冲突环境下的决策理论，将完善的博弈理论加入到强化学习获得很多了令人惊喜的结果，特别是对于一些无法解决的不完全信息博弈问题，解决上述问题最主要的算法有CFR系列算法和NFSP系列算法，CFR系列算法存在的主要难点：一是要求智能体具有完美回忆，这在很多实际博弈场景中很难满足；二是算法的收敛性很难保证；三是由于要遍历很多博弈节点，因此需要大量内存空间。NFSP系列算法存在的主要难点有：一是NFSP系列算法依赖于off-policy的深度Q值网络，因此在搜索规模大、即时策略场景下很难收敛；二是在训练时智能体都是独立更新，没有利用对手的信息；三是NFSP的最佳响应计算依赖于Deep Q-learning，收敛时间长且计算量大。除以上难点外，当前博弈强化学习算法还需要在以下几个方面重点突破。

5.1 博弈强化学习算法的优化

5.1.1 收敛性

当前大多数的博弈强化学习算法主要以实验为基础，由于深度神经网络强大的拟合性，使得很多算法在大多数情况都可以较好的收敛，但是并没有从理论上给出严格的收敛性证明。同时对于有收敛性证明的算法，其收敛条件往往过于苛刻，如Nash-Q Learning算法、Mean Field算法要求在博弈的每个阶段都存在鞍点或者全局最优点，甚至不允许鞍点和全局最优点交替出现，这使得满足上述收敛条件的博弈几乎很少，所以该算法所能解决的问题有限。

5.1.2 求解法则

算法博弈论研究的著名学者Roughgarden证明了纳什均衡的求解是一个NP-hard问题。一些传统的数学分析算法，比如Lemke-Howso算法、全局牛顿算法、分布式原始对偶算法、投影梯度算法等用于求解博弈的Nash平衡时，其基本思路是在一定的假设条件下将Nash平衡的计算问题转换为某类优化问题、变分不等式问题或互补问题等再设计相关算法求解。但这类方法大多要求博弈参与人的支付函数具有较高的光滑性，并且这些算法本身常常依赖初始点的选取，求解复杂度过高，有时因为求解时间过长导致最后无法求出正确的纳什均衡值，这些都在一定程度上限制了这类算法的应用范围。

5.2 博弈强化学习算法的模型

将博弈理论融入到强化学习中，用博弈论的知识来引导智能体的学习过程，但是在具体的建模过程中考虑的因素较少，导致模型过度简化。例如，Nash-Q算法采用的就是纳什均衡、correlated-Q算法采用的是相关均衡而Friend-or-Foe Q-Learning算法将多个智能体简化为Friend和Foe两组，都没有考虑在实际博弈过程中可能会出现的其他情况，如不可置信的威胁和有限理性等，这些因素都会影响博弈强化学习算法模型的科学性和合理性。同时，算法的最终目标是想要获得最科学合理的纯策略，因此混合策略的纳什均衡一定程度上不满足实际要求，然而纯策略的纳什均衡并非所有博弈场景都存在。

5.3 博弈强化学习算法的通用性和扩展性

现有算法研究的主要范围局限于对称博弈，即博弈中的每个玩家的策略集和支付函数都是相同的。无论是Nash-Q Learning算法研究的Grid World Games还是CFR系列算法研究的德扑问题都是属于对称博弈。然而，对称博弈相比于非对称博弈是个很小的集合。由于非对称博弈中的玩家的策略集和支付函数是不相同的，所以在非对称博弈中对于问题的建模难度会比对称博弈大，同时遇到的不确定因素也会更多。然而从逼近和仿真现实博弈的角度来说，研究非对称博弈意义要大于对称博弈。

6 多智能体强化学习算法研究展望

6.1 基于智能优化算法求解纳什均衡

求解纳什均衡是个复杂优化问题，其优化目标函数往往具有不可导、不连续、存在多个局部最优解的特点，这些性质可能使得传统优化算法失效。群体智能算法是受生物机制启发的一类算法，在路径优化、网络优化等领域获得广泛应用，因此利用群体智能算法求解纳什均衡理论上是可行的。当前群体智能算法主要有两大类，一是以蚁群优化算法（Ant Colony Optimization，ACO）为代表；二是以粒子群算法（Particle Swarm Optimization，PSO）为代表。

ACO算法思想来源于蚂蚁寻食中的通信机制，蚂蚁在寻找食物过程中通过分泌信息素，通过信息素的浓度来选取最佳路径。对于ACO算法的改进有Max-Min Ant System（MMAS）和Ant Colony System（ACS）算法，MMAS算法的主要特征是在每一次迭代结束后，仅最优蚂蚁对其所经过的最优路径进行信息素更新，其他蚂蚁不参与更新，ACS加入伪随机比例规则和离线信息素更新规则，并且只对全局最优路径的信息素进行更新。

PSO算法是科学家们在观察鸟群觅食时利用计算机模拟鸟群的聚集行为总结出一种群智能算法，可以在全局随机搜索，算法在运行之前会在自身建立的搜寻空间中设置一群随机的粒子，粒子通过迭代的过程不断地更新自己的速度、位置逐渐朝着最优位置逼近，最终会找到最优解。因此，这些粒子可以认为是解决优化问题的随机解。其中，粒子会朝着最优解迭代，通过个体极值：Pbest是粒子在寻找最优解过程中遇到的最好位置，称为自身找到的最优解；Gbest表示整个搜索过程群体的最优位置，空间中所有的粒子都会利用这两个值得到最优解，进而不断更新自己。因此，借鉴生物进化理论和生物行为规律的群体智能算法来仿真和模拟博弈平衡解的动态实现过程可以成为了研究博弈问题均衡解的一种新的探索和途径，ACO和PSO算法的流程如图3所示。

图3 ACO和PSO算法的流图Fig.3 Flow chart of ACO and PSO

两类算法本质上都是智能优化算法，而求解纳什均衡本质上也是个优化问题，因此利用智能优化算法求解纳什均衡是可行的，但是ACO和PSO算法的主要区别在于PSO所需设置的参数较少，主要用于连续优化问题的求解；而ACO需设置的参数相对较多，主要用于离散优化问题的求解，因此在求解纳什均衡时可根据博弈具体场景确定问题类型来选择何种智能优化算法。

6.2 基于元博弈的算法模型

元博弈理论由Howard在1971年首次提出，其核心思想是在原有博弈的基础上构建一种假想的博弈。而在该博弈中，某个智能体的动作将是其他所有智能体联合动作的反应函数（Reaction Function）。对于一个n人一般式博弈以及该博弈中的某个联合动作a，如果存在一个元博弈ηG和这个元博弈的一个纯策略纳什均衡π，满足φ(π)=a，则称联合动作a为博弈G的一个元均衡。具体的，可以称a为元博弈ηG导出的一个元均衡。φ定义为元博弈中任意动作到基本博弈中的动作的映射。元均衡和纯策略的纳什均衡最主要的区别在于，不存在纯策略纳什均衡的博弈也存在元均衡，因为在任意一个一般式博弈中，至少存在一个元均衡，从该博弈的完全元博弈中推导出的元均衡一定存在。因此基于元均衡的算法模型更有利于求解最终的纯策略。

由于元博弈是从原始博弈的基础上推导而来，使得智能体的动作变成相应的反应函数，因此动作的数量是增加的。以三人矩阵博弈为例，||S=m为状态集的大小为玩家动作集的大小，因此双人矩阵博弈的空间复杂度为2mn3。扩展成元博弈321G后，玩家1的动作集大小为n2，玩家2的动作集大小为n3，玩家3的动作集大小为n5，所以元博弈321G的空间复杂度为2mn10。基于元博弈的算法模型虽然增加了空间复杂度，但是该模型在理论上可以保证纯策略的存在性。

6.3 基于复因子动力学扩展非对称博弈

非对称博弈问题的求解困难主要在于建模的复杂性，并且不确定因素相比较对称博弈更多。然而，如果能将复杂的非对称博弈与对称博弈联系起来，建立合适的转换关系，即将复杂的非对称博弈转换为多个相对简单的对称博弈，利用现有的解决对称博弈的理论方法进行求解，则在一定程度上解决非对称博弈变为可能。复制动力学本质上是一个微分方程系统，它描述了一个纯策略种群（或复制因子）如何随着时间演化。在它们最基本的形式中，它们符合生物的选择原则，即适者生存。具体来说，选择复制器的动态机制表达如下：

这个等式本质上比较了一个策略的收益和整个总体的平均收益。如果这种策略的得分高于平均水平，它将能够复制后代，如果得分低于平均水平，它在种群中的存在将减少，甚至有可能走向灭绝。同时，如果策略组合(x,y)是非对称博弈G=(S1,S2,A,B)的纳什均衡，并且对于所有的i,j，都有则x是单人博弈BT的纳什均衡，y是单人博弈A的纳什均衡，反之也正确。因此可以通过上述的定理结论将非对称博弈转换成为对称博弈，从而使用现有的对称博弈算法进行求解。

7 结论

本文从博弈论的角度出发，梳理了近年来出现的多智能体强化学习算法。首先简要介绍了多智能体系统的背景知识、主要难点和解决技术路线。为解决多智能体系统中智能体之间的相互关系和一些不存在最优解的实际问题，同时为了增加求解结果的合理性，博弈理论被引入强化学习算法中。文中以标准型博弈和扩展式博弈为分类方法，从共同利益博弈、不同利益博弈、完全信息博弈和不完全信息博弈等角度对多智能体深度强化学习算法进行了分类，对各类算法进行了横向的对比，指出了各类算法的优缺点，并从算法的收敛性、均衡解的求解方式和博弈问题的建模三个方面总结了当前博弈强化学习算法的重难点。针对上述存在的问题，结合智能优化算法、元博弈理论和复因子动力学给出了可能解决上述问题的具体研究方向。实现博弈强化学习在复杂、不确定系统中的优化控制问题，对于推动机器人控制和军事决策等各领域的发展有重要意义，特别是在未来智能化战争中，基于规则的智能体体现的往往是指挥科学，而基于强化学习的智能体可能会体现指挥艺术，而指挥艺术在未来战争中仍然发挥着不会替代的作用。所以，博弈强化学习可能在更加科学、合理的智能辅助决策系统越来越关键。