AlphaGo原来是这样运行的，一文阐述多智能体强化学习

在这篇综述性文章中，作者详尽地介绍了多智能强化学习的理论基础，并阐述了解决各类多智能问题的经典算法。此外，作者还以 AlphaGo、AlphaStar为例，概述了多智能体强化学习的实际应用。

近年来，随着强化学习（reinforcement learning）在多个应用领域取得了令人瞩目的成果，并且考虑到在现实场景中通常会同时存在多个决策个体（智能体），部分研究者逐渐将眼光从单智能体领域延伸到多智能体。

本文将首先简要地介绍多智能体强化学习（multi-agent reinforcement learning, MARL）的相关理论基础，包括问题的定义、问题的建模，以及涉及到的核心思想和概念等。然后，根据具体应用中智能体之间的关系，将多智能体问题分为完全合作式、完全竞争式、混合关系式三种类型，并简要阐述解决各类多智能体问题的经典算法。最后，本文列举深度强化学习在多智能体研究工作中提出的一些方法（multi-agent deep reinforcement learning）。

1. 强化学习和多智能体强化学习

我们知道，强化学习的核心思想是“试错”（trial-and-error）：智能体通过与环境的交互，根据获得的反馈信息迭代地优化。在 RL 领域，待解决的问题通常被描述为马尔科夫决策过程。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 1：强化学习的框架（同时也表示了马尔科夫决策过程）。图源：[1]

当同时存在多个智能体与环境交互时，整个系统就变成一个多智能体系统（multi-agent system）。每个智能体仍然是遵循着强化学习的目标，也就是是最大化能够获得的累积回报，而此时环境全局状态的改变就和所有智能体的联合动作（joint action）相关了。因此在智能体策略学习的过程中，需要考虑联合动作的影响。

1.1 多智能体问题的建模——博弈论基础

马尔科夫决策过程拓展到多智能体系统，被定义为马尔科夫博弈（又称为随机博弈，Markov/stochastic game）。当我们对博弈论有一定了解后，能够借助博弈论来对多智能体强化学习问题进行建模，并更清晰地找到求解问题的方法。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 2：马尔科夫博弈过程。图源：[2]

在马尔科夫博弈中，所有智能体根据当前的环境状态（或者是观测值）来同时选择并执行各自的动作，该各自动作带来的联合动作影响了环境状态的转移和更新，并决定了智能体获得的奖励反馈。它可以通过元组 < S,A1,...,An,T,R1,...,Rn > 来表示，其中 S 表示状态集合，Ai 和 Ri 分别表示智能体 i 的动作集合和奖励集合，T 表示环境状态转移概率，表示损失因子。此时，某个智能体 i 获得的累积奖励的期望可以表示为：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

对于马尔科夫博弈，纳什均衡（Nash equilibrium）是一个很重要的概念，它是在多个智能体中达成的一个不动点，对于其中任意一个智能体来说，无法通过采取其他的策略来获得更高的累积回报，在数学形式上可以表达为：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

在该式中，π^表示智能体 i 的纳什均衡策略。

值得注意的是，纳什均衡不一定是全局最优，但它是在概率上最容易产生的结果，是在学习时较容易收敛到的状态，特别是如果当前智能体无法知道其他智能体将会采取怎样的策略。这里举个简单的例子来帮助理解，即博弈论中经典的囚徒困境。根据两个人不同的交代情况，判刑的时间是不一样的：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

在这个表格中，当 A 和 B 都选择撒谎时，能够达到全局最优的回报。但是每个个体都不知道另外的个体会做出怎样的行为，对于 A 或者是来 B 说，如果改成选择坦白，则能够获得更优的回报。实际上，对于 A 或者 B 来说，此时不管另外的个体选择了哪种行为，坦白是它能够获得最优回报的选择。所以，最终会收敛到 A 和 B 都选择坦白，即囚徒困境中的纳什均衡策略。

均衡求解方法是多智能体强化学习的基本方法，它对于多智能体学习的问题，结合了强化学习的经典方法（如 Q-learning）和博弈论中的均衡概念，通过 RL 的方法来求解该均衡目标，从而完成多智能体的相关任务。这种思路在后面介绍具体的学习方法中会有所体现。

相比于单智能体系统，强化学习应用在多智能体系统中会遇到哪些问题和挑战？

环境的不稳定性：智能体在做决策的同时，其他智能体也在采取动作；环境状态的变化与所有智能体的联合动作相关；

智能体获取信息的局限性：不一定能够获得全局的信息，智能体仅能获取局部的观测信息，但无法得知其他智能体的观测信息、动作和奖励等信息；

个体的目标一致性：各智能体的目标可能是最优的全局回报；也可能是各自局部回报的最优；

可拓展性：在大规模的多智能体系统中，就会涉及到高维度的状态空间和动作空间，对于模型表达能力和真实场景中的硬件算力有一定的要求。

1.2 多智能体问题的求解——多智能体强化学习算法介绍

对于多智能体强化学习问题，一种直接的解决思路：将单智能体强化学习方法直接套用在多智能体系统中，即每个智能体把其他智能体都当做环境中的因素，仍然按照单智能体学习的方式、通过与环境的交互来更新策略；这是 independent Q-learning 方法的思想。这种学习方式固然简单也很容易实现，但忽略了其他智能体也具备决策的能力、所有个体的动作共同影响环境的状态，使得它很难稳定地学习并达到良好的效果。

在一般情况下，智能体之间可能存在的是竞争关系（非合作关系）、半竞争半合作关系（混合式）或者是完全合作关系，在这些关系模式下，个体需要考虑其他智能体决策行为的影响也是不一样的。参考综述[3]，接下来的部分将根据智能体之间的关系，按照完全竞争式、半竞争半合作、完全合作式来阐述多智能体问题的建模以及求解方法。

1.2.1 智能体之间是完全竞争关系

minimax Q-learning 算法用于两个智能体之间是完全竞争关系的零和随机博弈。首先是最优值函数的定义：对于智能体 i，它需要考虑在其他智能体（i-）采取的动作（a-）令自己（i）回报最差（min）的情况下，能够获得的最大（max）期望回报。该回报可以表示为：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

在式子中，V 和 Q 省略了智能体 i 的下标，是因为在零和博弈中设定了 Q1=-Q2，所以上式对于另一个智能体来说是对称等价的。这个值函数表明，当前智能体在考虑了对手策略的情况下使用贪心选择。这种方式使得智能体容易收敛到纳什均衡策略。

在学习过程中，基于强化学习中的 Q-learning 方法，minimax Q-learning 利用上述 minimax 思想定义的值函数、通过迭代更新 Q 值；动作的选择，则是通过线性规划来求解当前阶段状态 s 对应的纳什均衡策略。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 3：minimax-Q learning 算法流程。图源[4]

minimax Q 方法是竞争式博弈中很经典的一种思想，基于该种思想衍生出很多其他方法，包括 Friend-or-Foe Q-learning、correlated Q-learning，以及接下来将要提到的 Nash Q-learning。

1.2.2 智能体之间是半合作半竞争（混合）关系

双人零和博弈的更一般形式为多人一般和博弈（general-sum game），此时 minimax Q-learning 方法可扩展为 Nash Q-learning 方法。当每个智能体采用普通的 Q 学习方法，并且都采取贪心的方式、即最大化各自的 Q 值时，这样的方法容易收敛到纳什均衡策略。Nash Q-learning 方法可用于处理以纳什均衡为解的多智能体学习问题。它的目标是通过寻找每一个状态的纳什均衡点，从而在学习过程中基于纳什均衡策略来更新 Q 值。

具体地，对于一个智能体 i 来说，它的 Nash Q 值定义为：

此时，假设了所有智能体从下一时刻开始都采取纳什均衡策略，纳什策略可以通过二次规划（仅考虑离散的动作空间，π是各动作的概率分布）来求解。

在 Q 值的迭代更新过程中，使用 Nash Q 值来更新：

可以看到，对于单个智能体 i，在使用 Nash Q 值进行更新时，它除了需要知道全局状态 s 和其他智能体的动作 a 以外，还需要知道其他所有智能体在下一状态对应的纳什均衡策略π。进一步地，当前智能体就需要知道其他智能体的 Q(s')值，这通常是根据观察到的其他智能体的奖励和动作来猜想和计算。所以，Nash Q-learning 方法对智能体能够获取的其他智能体的信息（包括动作、奖励等）具有较强的假设，在复杂的真实问题中一般不满足这样严格的条件，方法的适用范围受限。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 4：nash-Q learning 算法流程。图源：[5]

1.2.3 智能体之间是完全合作关系

前面提到的智能体之间的两种关系，都涉及到了个体和个体的相互竞争，所以对于个体来说，在策略学习过程中考虑对方（更一般地，其他智能体）的决策行为，才能够做出更好地应对动作，这是比较容易理解的。那么，如果智能体之间完全是合作关系，个体的决策也要考虑其他智能体的决策情况吗？实际上，“合作”意味着多个智能体要共同完成一个目标任务，即这个目标的达成与各个体行为组合得到的联合行为相关；如果个体“一意孤行”，那么它很难配合其他队友来共同获得好的回报。所以，智能体的策略学习仍然需要考虑联合动作效应，要考虑其他具有决策能力的智能体的影响。

怎样实现在智能体策略学习过程中考虑其他协作智能体的影响呢？这个问题我们可以分类讨论，分类的依据是具体问题对于智能体协作的条件要求，即智能体通过协作获得最优回报时，是否需要协调机制:

不需要协作机制

对于一个问题（或者是任务），当所有智能体的联合最优动作是唯一的时候，完成该任务是不需要协作机制的。这个很容易理解，假设对于环境中的所有智能体 存在不只一个最优联合动作，即有 和，那么 A 和 B 之间就需要协商机制，决定是同时取π，还是同时取 h；因为如果其中一个取π、另一个取 h，得到的联合动作就不一定是最优的了。Team Q-learning 是一种适用于不需要协作机制的问题的学习方法，它提出对于单个智能体 i，可以通过下面这个式子来求出它的最优动作 hi：

Distributed Q-learning 也是一种适用于不需要协作机制的问题的学习方法，不同于 Team Q-learning 在选取个体最优动作的时候需要知道其他智能体的动作，在该方法中智能体维护的是只依据自身动作所对应的 Q 值，从而得到个体最优动作。

隐式的协作机制

在智能体之间需要相互协商、从而达成最优的联合动作的问题中，个体之间的相互建模，能够为智能体的决策提供潜在的协调机制。在联合动作学习（joint action learner，JAL）[6]方法中，智能体 i 会基于观察到的其他智能体 j 的历史动作、对其他智能体 j 的策略进行建模。在频率最大 Q 值（frequency maximum Q-value, FMQ）[7]方法中，在个体 Q 值的定义中引入了个体动作所在的联合动作取得最优回报的频率，从而在学习过程中引导智能体选择能够取得最优回报的联合动作中的自身动作，那么所有智能体的最优动作组合被选择的概率也会更高。

JAL 和 FMQ 方法的基本思路都是基于均衡求解法，但这类方法通常只能处理小规模（即智能体的数量较少）的多智能体问题：在现实问题中，会涉及到大量智能体之间的交互和相互影响，而一般的均衡求解法受限于计算效率和计算复杂度、很难处理复杂的情况。在大规模多智能体学习问题中，考虑群体联合动作的效应，包括当前智能体受到的影响以及在群体中发挥的作用，对于智能体的策略学习是有较大帮助的。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

基于平均场理论的多智能体强化学习（Mean Field MARL, MFMARL）方法是 UCL 学者在 2018 年 ICML 会议上提出的一种针对大规模群体问题的方法，它将传统强化学习方法（Q-learning）和平均场理论（mean field theory）相结合。平均场理论适用于对复杂的大规模系统建模，它使用了一种简化的建模思想：对于其中的某个个体，所有其他个体产生的联合作用可以用一个 “平均量” 来定义和衡量。此时，对于其中一个个体来说，所有其他个体的影响相当于一个单体对于它的影响，这样的建模方式能够有效处理维度空间和计算量庞大的问题。

MFMARL 方法基于平均场理论的建模思想，将所有智能体看作一个“平均场”，个体与其他智能体之间的关系可以描述为个体和平均场之间的相互影响，从而简化了后续的分析过程。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 5：基于平均场理论的多智能体建模方式，单个智能体只考虑与相邻的其他智能体（蓝色球体区域）的相互作用。图源：[8]

首先，为了处理集中式全局值函数的学习效果会受到智能体数量（联合动作的维度）的影响，对值函数进行分解。对于单个智能体 j，它的值函数 Qj(s,a)包含了与所有 Nj 个相邻智能体 k 之间的相互作用：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

然后，将平均场理论的思想结合到上式中。考虑离散的动作空间，单个智能体的动作采用 one-hot 编码的方式，即 aj=[h(aj_1), ... h(aj_d)]，其中 h(aj_i)=1 if aj=aj_i ?: 0；其他相邻智能体的动作可以表示为平均动作 bar和一个波动δ的形式：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

利用泰勒二阶展开，得到

AlphaGo原来是这样运行的，一文详解多智能体强化学习

该式子即是将当前智能体 j 与其他相邻智能体 k 的相互作用，简化为当前智能体 j 和虚拟智能体 bar的相互作用，是平均场思想在数学形式上的体现。此时，在学习过程中，迭代更新的对象为平均场下的 Q(s,aj,bar)值（即 MF-Q），有：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

在更新中使用 v 而不是使用 max Q 的原因在于：对 Q 取 max，需要相邻智能体策略 bar的合作，而对于智能体 j 来说是无法直接干涉其他智能体的决策情况；另一方面，贪心的选择依旧会导致学习过程受到环境不稳定性的影响。

对应地，智能体 j 的策略也会基于 Q 值迭代更新，使用玻尔兹曼分布有：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

原文证明了通过这样的迭代更新方式，bar最终能够收敛到唯一平衡点的证明，并推出智能体 j 的策略πj 能够收敛到纳什均衡策略。

显式的协作机制

关于显式的协作机制，我们将通过多智能体深度强化学习在多机器人领域的应用中会简单介绍（主要是人机之间的交互，考虑现存的一些约束条件 / 先验规则等）。

2. 多智能体深度强化学习

随着深度学习的发展，利用神经网络的强大表达能力来搭建逼近模型（value approximation）和策略模型（常见于 policy-based 的 DRL 方法）。深度强化学习的方法可以分为基于值函数（value-based）和基于策略（policy-based）两种，在考虑多智能体问题时，主要的方式是在值函数的定义或者是策略的定义中引入多智能体的相关因素，并设计相应的网络结构作为值函数模型和策略模型，最终训练得到的模型能够适应（直接或者是潜在地学习到智能体相互之间的复杂关系），在具体任务上获得不错的效果。

2.1 policy-based 的方法

在完全合作的 setting 下，多智能体整体通常需要最大化全局的期望回报。前面提到一种完全集中式的方式：通过一个中心模块来完成全局信息的获取和决策计算，能够直接地将适用于单智能体的 RL 方法拓展到多智能体系统中。但通常在现实情况中，中心化的控制器（centralized controller）并不一定可行，或者说不一定是比较理想的决策方式。而如果采用完全分布式的方式，每个智能体独自学习自己的值函数网络以及策略网络、不考虑其他智能体对自己的影响，无法很好处理环境的不稳定问题。利用强化学习中 actor-critic 框架的特点，能够在这两种极端方式中找到协调的办法。

1. 多智能体 DDPG 方法（Multi-Agent Deep Deterministic Policy Gradient, MADDPG）

AlphaGo原来是这样运行的，一文详解多智能体强化学习

这种方法是在深度确定策略梯度（Deep Deterministic Policy Gradient，DDPG）方法的基础上、对其中涉及到的 actor-critic 框架进行改进，使用集中式训练、分布式执行的机制（centralized training and decentralized execution），为解决多智能体问题提供了一种比较通用的思路。

MADDPG 为每个智能体都建立了一个中心化的 critic，它能够获取全局信息（包括全局状态和所有智能体的动作）并给出对应的值函数 Qi(x,a1,...,an)，这在一定程度上能够缓解多智能体系统环境不稳定的问题。另一方面，每个智能体的 actor 则只需要根据局部的观测信息作出决策，这能够实现对多智能体的分布式控制。

在基于 actor-critic 框架的学习过程中，critic 和 actor 的更新方式和 DDPG 类似。对于 critic，它的优化目标为：

对于 actor，考虑确定性策略μi(ai|oi)，策略更新时的梯度计算可以表示为：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 6：中心化的 Q 值学习（绿色）和分布式的策略执行（褐色）。Q 值获取所有智能体的观测信息 o 和动作 a，策略π根据个体的观测信息来输出个体动作。图源：[9]

在 MADDPG 中，个体维护的中心化 Q 值需要知道全局的状态信息和所有智能体的动作信息，此时假设了智能体能够通过通信或者是某种方式得知其他智能体的观测值和策略，这种假设前提过于严格。MADDPG 进一步提出了可以通过维护策略逼近函数 hat{miu}来估计其他智能体的策略，通过对其他智能体的行为建模使得维护中心化的 Q 值、考虑联合动作效应对单个个体来说是可行的。智能体 i 在逼近第 j 个智能体的策略函数时，其优化目标是令策略函数能够近似经验样本中智能体 j 的行为，同时考虑该策略的熵，可表示为：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

除了考虑联合动作以外，MADDPG 在处理环境不稳定问题方面还使用了策略集成（policies ensemble）的技巧。由于环境中的每个智能体的策略都在迭代更新，因此很容易出现单个智能体的策略对其他智能体的策略过拟合，即当其他智能体的策略发生改变时，当前得到的最优策略不一定能很好的适应其他智能体的策略。为了缓和过拟合问题，MADDPG 提出了策略集成的思想，即对于单个智能体 i，它的策略μi 是由多个子策略μi^k 构成的集合。在一个 episode 中，只使用一种从集合中采样得到的子策略进行决策和完成交互。在学习过程中最大化的目标是所有子策略的期望回报，即

每个子策略的更新梯度为：

总的来说，MADDPG 的核心是在 DDPG 算法的基础上，对每个智能体使用全局的 Q 值来更新局部的策略，该方法在完全合作、完全竞争和混合关系的问题中都能取得较好效果。算法流程如下所示：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 7：MADDPG 算法流程。图源：[9]

2. 反事实多智能体策略梯度法方法（Counterfactual Multi-Agent Policy Gradients, COMA）

AlphaGo原来是这样运行的，一文详解多智能体强化学习

在合作式的多智能体学习问题中，每个智能体共享奖励（即在同一个时刻获得相同的奖励），此时会存在一个 “置信分配” 问题（credit assignment）：如何去评估每个智能体对这个共享奖励的贡献？

COMA 方法在置信分配中利用了一种反事实基线：将智能体当前的动作和默认的动作进行比较，如果当前动作能够获得的回报高于默认动作，则说明当前动作提供了好的贡献，反之则说明当前动作提供了坏的贡献；默认动作的回报，则通过当前策略的平均效果来提供（即为反事实基线）。在对某个智能体和基线进行比较的时，需要固定其他智能体的动作。当前策略的平均效果和优势函数的定义如下：

AlphaGo原来是这样运行的，一文详解多智能体强化学习

AlphaGo原来是这样运行的，一文详解多智能体强化学习

COMA 方法结合了集中式训练、分布式执行的思想：分布式的个体策略以局部观测值为输入、输出个体的动作；中心化的 critic 使用特殊的网络结构来输出优势函数值。

具体地，critic 网络的输入包括了全局状态信息 s、个体的局部观测信息 o、个体的编号 a 以及其他智能体的动作，首先输出当前智能体不同动作所对应的联合 Q 值。然后， 再经过 COMA 模块，使用输入其中的智能体当前策略和动作，计算反事实基线以及输出最终的优势函数。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

图 8：(a) COMA 方法中的 actor-critic 框架图，(b) actor 的网络结构，(c) critic 的网络结构（包含了核心的 COMA 模块来提供优势函数值）。图源：[10]

2.2 value-based 的方法

在前面提到的 policy-based 方法中，中心化的值函数是直接使用全局信息进行建模，没有考虑个体的特点。在多智能体系统是由大规模的多个个体构成时，这样的值函数是难以学习或者是训练到收敛的，很难推导出理想的策略。并且仅依靠局部观测值，无法判断当前奖励是由于自身的行为还是环境中其他队友的行为而获得的。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

值分解网络（value decomposition networks, VDN）由 DeepMind 团队在 2018 年提出，该方法的核心是将全局的 Q(s,a)值分解为各个局部 Qi(si,ai)的加权和，每个智能体拥有各自的局部值函数。

AlphaGo原来是这样运行的，一文详解多智能体强化学习

这样的分解方式，在联合动作 Q 值的结构组成方面考虑了个体行为的特性，使得该 Q 值更易于学习。另一方面，它也能够适配集中式的训练方式，在一定程度上能够克服多智能体系统中环境不稳定的问题。在训练过程中，通过联合动作 Q 值来指导策略的优化，同时个体从全局 Q 值中提取局部的 Qi 值来完成各自的决策（如贪心策略 ai=argmax Qi），实现多智能体系统的分布式控制。