博士万字总结 || 多智能体强化学习(MARL)大总结与论文详细解读

2020 年 4 月 14 日 深度强化学习实验室

深度强化学习实验室报道

来源： ©PaperWeekly 原创 @李文浩-华东师范大学博士生

编辑：DeepRL

最近由于写论文的原因，梳理了一下近几年的多智能体强化学习（MARL）算法，在这里做一个总结。下面遵循综述 Is multiagent deep reinforcement learning the answer or the question? A brief survey 对多智能体强化学习算法的分类方法，将 MARL 算法分为以下四类：

Analysis of emergent behaviors（行为分析）
Learning communication（通信学习）
Learning cooperation（协作学习）
Agents modeling agents（智能体建模）

下面我将分别按照时间顺序对这四类算法中的一些典型工作进行详细讨论。

|| 行为分析

行为分析类别的算法主要是将单智能体强化学习算法（SARL）直接应用到多智能体环境之中，每个智能体之间相互独立，遵循 Independent Q-Learning [2] 的算法思路。本类别的工作相对来说比较早期，这里主要讨论以下两个工作：

[1] Tampuu, Ardi, et al. "Multiagent cooperation and competition with deep reinforcement learning." PloS one 12.4 (2017): e0172395.

[2] Gupta, Jayesh K., Maxim Egorov, and Mykel Kochenderfer. "Cooperative multi-agent control using deep reinforcement learning" International Conference on Autonomous Agents and Multiagent Systems. Springer, Cham, 2017.

论文标题：Multiagent Cooperation and Competition with Deep Reinforcement Learning

论文链接：https://arxiv.org/abs/1511.08779

这篇文章首次将 DQN 算法与 IQL 结合起来，并将其应用到 ALE 环境中的 Pong 游戏中（该游戏内部场景如下图所示，图片来源原论文）。

在这样一个环境中，每个智能体拥有独立的 Q network，独自采集数据并进行训练，都有对环境的全局观察，动作空间包含以下四个维度：上移、下移、保持不动以及击球（或称为开始游戏）。

作者为了全面的观察将 DQN 应用到多智能体环境下的各方面表现，通过设计回报函数的方式设计了完全协作环境、完全竞争环境以及非完全协作/竞争环境。具体回报函数设计如下：

完全协作环境：一方失球，则两方均获得 -1 的回报
完全竞争环境：一方失球，该方获得 -1 的回报；对方获得 +1 的回报
非完全协作/竞争环境：一方失球，该方获得 -1 的回报；对方获得的回报

最终的实验结果表明，在完全协作环境中，智能体学到的策略是尽可能长时间的不失球；而在完全竞争环境中，智能体学到的是如何更好的得分（即让对方失球）。

从这个结果可以看出，在将 DQN 直接应用到多智能体环境中，也能够达到一个比较好的性能，即便 IQL 算法是一个十分简单的算法，没有办法处理环境非平稳问题，但是依旧是一个比较强的基准算法。

由于是一篇比较早期的多智能体论文，因而文中还提到了一些比较有用的实验部分的细节问题：

Q 值的收敛与否一定程度上反映了 DQN 算法的收敛与否
在训练之前首先随机在环境中采样一些 state 作为测试集，监控这些 state 对应的最大的 Q 值平均值来判断算法收敛与否

论文标题：Cooperative Multi-Agent Control Using Deep Reinforcement Learning

论文链接：https://platformlab.stanford.edu/pdf/ALA2017_Gupta.pdf

本文将基于值函数的算法 DQN、基于策略梯度的算法 TRPO 以及演员-评论家算法 DDPG 与 IQL 算法以及循环神经网络（或前向神经网络）相结合，应用到局部观察的多智能体环境中。

其与前一篇 paper 的区别在于，为了增加算法在大规模场景下的可扩展性，所有的智能体都共享同一套参数。训练时所有智能体采样得到的样本进行汇总，用来更新共享的模型参数。

同时，为了进一步保证不同的智能体即使在共享参数的情况下也能够表现出不同的行为，其模型输入除了局部的观察外，还包括自身的索引。实验用到的仿真环境如下：

实验结果表明，在使用前向神经网络构建模型时，基于策略梯度的 TRPO 算法在最终性能上超越了另外两种算法；另外，使用循环神经网络构建模型时，性能超过使用前向神经网络的情况。

最后，文章还提出了一种课程学习的训练方法：假设我们的课程学习环境是先从 2 个智能体开始训练，逐渐增加到最多 10 个智能体。

我们首先构建一个迪利克雷分布，该分布的概率密度函数最大值点初始偏向于较少的智能体个数，每一次训练时都从这个分布中采样智能体的个数并进行强化学习算法的训练，直到算法在这些采样出的环境中的性能都达到了某个阈值。

那么接下来我们就改变迪利克雷分布的参数，来使得其概率密度函数最大值点逐渐偏向于较多的智能体个数。循环上述过程直到算法在 10 个智能体上也能达到比较好的性能，这样我们就完成了课程学习。

具体算法流程如下（图片来源原论文）：

|| 通信学习

属于这一类别的多智能体强化学习方法显式假设智能体之间存在信息的交互，并在训练过程中学习如何根据自身的局部观察来生成信息，或者来确定是否需要通信、与哪些智能体通信等等。在训练完毕后运行的过程中，需要显式依据其余智能体传递的信息来进行决策。

此部分主要讨论以下五个工作：

[1] Foerster, Jakob, et al. "Learning to communicate with deep multi-agent reinforcement learning" Advances in Neural Information Processing Systems. 2016.

[2] Sukhbaatar, Sainbayar, and Rob Fergus. "Learning multiagent communication with backpropagation" Advances in Neural Information Processing Systems . 2016.

[3] Peng, Peng, et al. "Multiagent bidirectionally-coordinated nets for learning to play starcraft combat games" arXiv preprint arXiv:1703.10069 2 (2017).

[4] Jiang, Jiechuan, and Zongqing Lu. "Learning attentional communication for multi-agent cooperation" Advances in Neural Information Processing Systems. 2018.

[5] Kim, Daewoo, et al. "Learning to Schedule Communication in Multi-agent Reinforcement Learning" arXiv preprint arXiv:1902.01554 (2019).

论文标题：Learning to Communicate with Deep Multi-Agent Reinforcement Learning

论文链接：https://arxiv.org/abs/1605.06676

这篇文章最先在深度多智能体强化学习中引入通信学习，其解决的强化学习问题是 Dec-POMDP 问题。换句话说，在 Dec-POMDP 中，所有智能体共享一个全局的回报函数，所以是一个完全协作环境，每个智能体只拥有自己的局部观察。文中假设通信信道是离散的，即智能体之间只能能传递离散的信息（即 one-hot 向量）。

本文采用的是 CTDE 框架（即中心化训练去中心化执行，Centralized Training Decentralized Execution），在训练时不对智能体之间的信息传递进行限制（由于是中心化的训练器，所以智能体之间的信息传递完全由这个训练器接管），甚至在训练时可以使用连续的信息。

但是训练完毕之后运行时，智能体之间才进行真正的通信，并且该通信信道是离散（如果训练时是连续的，则在运行时要对信息进行离散化）的。

本文提出了两种算法，后一种是前一种的改进版本，具体名称陈列如下：

Reinforced Inter-Agent Learning (RIAL)
Differentiable Inter-Agent Learning (DIAL)

下面对这两种算法分别讨论。

RIAL

由于本文限定通信信道是离散的，因而 RIAL 算法将生成的信息也作为一个离散的动作空间来考虑，并设定信息的维度为，并且原始的动作空间的维度为。

RIAL 算法将 DRQN 算法与 IQL 算法结合起来，并显式在智能体之间传输可学习的信息来增加智能体对于环境的感知，从而解决 IQL 面临的因为环境非平稳所带来的性能上的问题。但如果只使用一个 Q network，那么总的动作空间的维度就是。

为了解决这一问题，RIAL 算法使用了两个 Q-network，分别输出原始的动作以及离散的信息。并且 RIAL 算法中 Q network 的输入不仅仅是局部观察，还包括上一时间步其余智能体传递过来的信息。

另外还需提及的一点是，在多智能体环境中，采用 Experience Replay 反而会导致算法性能变差。这是因为之前收集的样本与现在收集的样本，由于智能体策略更新的原因，两者实际上是从不同的环境中收集而来，从而使得这些样本会阻碍算法的正常训练。

也有许多工作解决这一问题，但由于本文时间较早，因而只是简单的禁用 Experience Replay，但这将大大降低算法的数据有效性。算法框架如下图所示（图片来源原论文）：

另外，为了算法的可扩展性以及充分利用中心化学习的优势，RIAL 算法可以更改为每个智能体共享同一套模型参数，并且为了进一步对在任务中扮演不同觉得的智能体进行分辨，在 Q network 的输入中还可以额外加入智能体的索引号（可以看到前面讨论的 Cooperative multi-agent control using deep reinforcement learning [3] 同样借用了这种改进方案）。

DIAL

虽然 RIAL 算法可以在智能体之间共享参数，但它仍然没有充分利用中心化训练的优势。而且，智能体不会互相提供，有关其接收到的信息的发送方智能体的通信行为的反馈。

然而人类交流富有紧密的反馈循环。例如，在面对面互动时，听众会向发言者反馈一些非语言信息（例如眼神，微动作等），表明理解和兴趣的程度。RIAL 算法缺乏这种反馈机制，但是后者对于通信学习是非常重要的。

所以本文在 RIAL 的基础上提出了一种新的算法 DIAL，该算法通过通信信道讲梯度信息从信息接收方传回到信息发送方。

具体来说，在中心化训练时，信息发送方的信息动作输出直接连接到信息接收方，并且为了能够实现端到端训练，此时的信息将不再是离散值而是连续值。训练完毕之后执行时，通过这个实值的正负进行 one-hot 离散化。

其具体算法框架如上图所示。同时为了增加算法的鲁棒性，这个信息实值是从一个拥有固定方差的高斯分布中采样而来，该分布的均值即信息发送方生成的实值。

论文标题：Learning Multiagent Communication with Backpropagation

论文链接：https://arxiv.org/abs/1605.07736

本文与上文是同时期的不同工作（两者发布到 arXiv 上的时间只相差一天）。本文假设智能体之间传递的消息是连续变量（不像 RIAL 或者 DIAL 是离散的），文章采用的强化学习算法应该是 policy gradient 方法（论文本身没有指明，这个结论是从网络结构上推断而出）。

本文解决的也同样是 Dec-POMDP 问题，遵循的是中心化训练中心化执行 CTCE（Centralized Training Centralized Execution）框架，因而在大规模的多智能体环境下，由于网络输入的数据维度过大，会给强化学习算法的训练带来困难。

算法被命名为 CommNet，其框架如下图所示（图片来源原论文）：

该框架中所有灰色模块部分的参数均是所有智能体共享的，这一定程度上提升了算法的可扩展性。从上图可以看出，算法接收所有智能体的局部观察作为输入，然后输出所有智能体的决策（其实整个框架有一点图神经网络的意思，这里使用的聚合函数就是 mean 函数，然后整个图是一个星状图）。

本算法采用的信息传递方式是采用广播的方式，文中认为可以对算法做出些许修改，让每个智能体只接收其相邻个智能体的信息。

拿上图中间的框架图来说明，即上层网络每个模块的输入，不再都是所有智能体消息的平均，而是每个模块只接受满足条件的下层消息的输出，这个条件即下层模块对应的智能体位于其领域范围内。这样通过增加网络层数，即可增大智能体的感受野（借用计算机视觉的术语），从而间接了解全局的信息。

除此之外，文中还提出了两种对上述算法可以采取的改进方式：

可以对上图中间的结构加上 skip connection，类似于 ResNet。这样可以使得智能体在学习的过程中同时考虑局部信息以及全局信息，类似于计算机视觉领域 multi-scale 的思想
可以将灰色模块的网络结构换成 RNN-like，例如 LSTM 或者 GRU 等等，这是为了处理局部观察所带来的 POMDP 问题

论文标题：Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games

论文链接：https://arxiv.org/abs/1703.10069

本文提出了一个新的算法 BiCNet，同样假设智能体之间传递的信息是离散的，旨在解决 zero-sum Stochastic Game (SG) 问题（具体在后面讨论）。

算法基于演员-评论家算法框架，使用的是 DDPG 算法，并且考虑到算法在大规模多智能体环境下的可扩展性问题，智能体之间共享模型参数，并且算法假设每个智能体都拥有同样的全局观察（全局状态），这也是本文的局限之一。另外，BiCNet 同样遵循 CTCE 框架。

整体模型结构如下图所示（图片来源原论文）：

可以看出，BiCNet 通过中间的 Bi-RNN 层进行智能体之间的痛惜。算法伪代码如下（图片来源原论文）：

接下来我们聚焦在 BiCNet 解决的问题上，前面说到，BiCNet 是为了解决 zero-sum Stochastic Game（SG）而提出的，一般可以将多智能体竞争环境建模为 SG。一个 SG 可以形式化地被如下元组定义：

其中代表被所有智能体共享的全局状态；和代表竞争双方的智能体数目；和则分别代表两方智能体的动作空间；代表全局状态转移概率，则是智能体接收到的环境回报。

在 SG 中，对于某一方来说，其实是一个完全协作问题。为此，我们设计如下的全局回报函数：

其中：

对于我方智能体来说，其目标是最大化这样一个全局的期望累积回报；而对于敌方智能体来说，其目标则是最小化这样一个全局的期望累积回报。因而，我们就有了一个 Minimax game，对应的最优的 Q value 如下：

对于这样一个 minimax game，我们可以采用虽然可以采用 Minimax Q-Learning 这样的算法来去解决，但是对于复杂的高维多智能体环境，前者基本无法处理。

因而在本文中假设地方的 policy 是固定的（即敌方智能体遵循一个固定的策略，只有己方智能体的策略是不断更新的），所以上述 SG 就转化为了一个 MDP：

那么我们就可以使用类似 DDPG 这样的算法来去解这样一个 MDP 问题。

由于所有的智能体都共享同一套参数，并且对于环境的观察也是共享的全局观察，那么对于特定任务（例如足球比赛），如何体现智能体在角色上的差别呢？BiCNet 算法做出了以下两点改进：

设计新的回报函数
固定智能体在 Bi-RNN 的位置

对于第一点，我们展开讲一下（第二点比较直观），BiCNet 采用了类似后面要讲的 MADDPG 算法的方法（由于是不同多智能体算法类别内按时间顺序排列，类别之间的论文并没有按照时间先后顺序排列，所以这里会出现之后发表的工作反而先讨论的情况），每个智能体都拥有自己独立的回报函数：

这里的 top-K 论文没有具体说明如何选取，这里可以认为按照距离选取等。那么每个智能体也都拥有自己的 Q-value （虽然所有的智能体共享同一个 RNN，但是也因为这个原因，所以排在不同位置的智能体可以看成拥有不同的 Q-network），即：

这里说明一下，即使每一个智能体共享一个全局回报，这里所说的情况依然会发生，这也是为什么智能体可以通过放在 Bi-RNN 的不同位置来体现其在任务中扮演的角色的不同；而每个智能体使用不同的回报函数，只是增大了这种智能体之间的差异。

计算得到不同的 bellman errors 之后，就可以采用下述多智能体梯度定理（本文提出的，因为本文使用的 RNN 包含共享参数）以及 BPTT 来更新模型参数了：

换句话说，BiCNet 中所有的智能体都拥有独立的回报函数以及 Q-network 以及 policy network，但这些 network 中部分参数是共享的。这些智能体一起在环境中进行数据采样，最后将所有的数据集中起来，更新他们的共享部分的参数。

所以这样一看，将 BiCNet 和 MADDPG 相比较，其实就是共享 Q-network 以及 policy network 的拥有特定网络结构的 MADDPG？

论文标题：Learning Attentional Communication for Multi-Agent Cooperation

论文链接：https://arxiv.org/abs/1805.07733

前面我们讨论的三种算法，R(D)IAL、CommNet 以及 BiCNet，都是每一个时间步所有智能体之间都要进行通信，或者每个智能体与自己相邻的智能体进行通信，这在本文看来属于一个预定义的通信模式，不够灵活。

本文的出发点正是基于此，希望提出一个算法，能够让智能体在任何时刻，自己决定是否需要与其他智能体进行通信，以及与哪些智能体进行通信。

本文为了达到上述目标，提出了一个基于注意力机制的通信模型 ATOC，该模型基于智能体的局部观察，可同时适用于协作环境（共享一个全局的回报函数或者拥有各自的回报函数）以及竞争环境（实质也是协作环境，因为算法只控制一方）。

其基本思想是，通过其局部观察与动作（其实是策略网络的中间层输出）的编码，来决定其是否需要与其视野范围内的其他智能体进行通信，以及哪些智能体进行通信。

对于决定进行通信的智能体，我们称之为发起者（initiator），这个发起者从其视野范围内选择协作者共同形成一个通信群组，这个通信群组在整个 episode 中动态变化并且只在需要的时候存在。

本文采用一个双向的 LSTM 网络作为通信群组之间的通信信道（类似于 BiCNet），这个 LSTM 以通信群组中各个智能体的局部观察与动作的编码（之前提到的）作为输入，输出的 higher-level 的编码信息作为各智能体策略网络的额外输入，来指导协作策略的生成。

ATOC 算法采用的是演员-评论家框架，DDPG 算法，遵循 CTDE 框架，同时考虑到算法在大规模多智能体环境下的可扩展性，所有智能体共享策略网络、注意力单元以及通信信道的参数（parameter sharing 好像已经是标准设置了）。

整个算法的模型框架如下图所示（图片来源原论文）：

这里注意力模块来决定自身是否要成为发起者，但是并不是每一个时间步都需要做这样一个判断，而是每隔固定的个时间步，这是因为协作策略需要持续一段时间才能看到效果。注意力模块的训练过程是完全独立于整个强化算法的训练过程的，即注意力模块并不是通过端到端的方式来训练的。

具体来说，注意力模块是一个 RNN 网络，在每隔一个时间步（其实在环境中是个时间步），其以上一步的隐状态以及这一步智能体局部观察以及动作的编码作为输入，输出端是一个二分类器，判断其是否要成为发起者。

训练数据通过以下方式获得：对于每一个发起者及其通信群组，我们计算其通信群组中每一个智能体采用协作动作（即使用编码作为额外输入得到的动作）与不采用协作动作在 Q-value 上带来的差值的平均值：

然后我们将元组存起来作为训练集，在一个 episode 结束之后，对训练集中的数据采用下述二分类交叉熵损失函数进行拟合：

而强化部分则按照标准流程进行，算法伪代码如下（图片来源原论文）:

最后来说明以下为什么 ATOC 算法要选择视野范围之内的智能体建立通信群组，主要有以下两点原因：

邻近的智能体的局部观察更加相似，因而更容易互相理解
邻近的智能体之间更容易协作

一个发起者邻近的智能体可以分为以下三种：

其他发起者
被其他发起者选定的智能体
没有被其他发起者选定的智能体

每个发起者最多选择个智能体，选择的优先级：没有被其他发起者选定的智能体 > 被其他发起者选定的智能体 > 其他发起者。当一个智能体同时被多个发起者选择，则会同时在所有的通信群组中起作用。

具体来说，假定智能体同时被发起者和顺序选中，则其首先会加入到发起者的通信群组中，生成一个对应的编码：

这相当于智能体的编码被更新了一次；接着它再参与到发起者的通信群组中，再次更新自己的编码，并且上一次更新后的编码也会影响群组中其余智能体的编码更新：

这样，这种处于交界处的智能体就会起到一个信息桥梁的作用，使得局部的信息按照顺序逐步的传递到全局（但是这种传递遵循某个特定的顺序）。

另外，与 BiCNet 相比，ATOC 有以下相似以及改进点：

为了进一步凸显不同智能体在特定任务中的不同定位，固定其在 LSTM 中的位置
将 RNN 通信信道改为 LSTM，从而过滤掉无关信息

最后，ATOC 在竞争环境下的训练方式是与 baseline 对抗训练，而不是分别 self-play 最后再进行比较。

论文标题：Learning to Schedule Communication in Multi-agent Reinforcement Learning

论文链接：https://arxiv.org/abs/1902.01554

与 ATOC 相比，这篇工作关注的是另外一个问题。这里同样从 R(D)IAL、CommNet 以及 BiCNet 算法出发，这三种算法在每一个时间步所有的智能体之间都参与通信，或者是类似于 R(D)IAL 这样智能体两两之间相互传递信息，或者是像 CommNet 以及 BiCNet 这样所有的智能体都将自己的信息发送到通信信道中参与高级信息的生成。

但是在现实情况中，通信信道的带宽是有限的，如果所有智能体都往这个有限带宽的信道中发送信息，则容量一旦超出，就会出现信息丢失或者阻塞等等情况。ATOC 是通过限制每个发起者只能选择最多个智能体加入到通信群组中，但是其选取的方式十分简单。本文将通信领域 MAC (Medium Access Control) 方法引入到多智能体强化学习中，来解决上述问题。

本文提出的 SchedNet 算法，同样是解决 Dec-POMDP 问题，并遵循 CTDE 框架，基于演员-评论家算法。

具体来说，整个算法的框架如下图所示（图片来源原论文）：

整个框架分为三个部分，Actor 网络，Scheduler 以及 Critic 网络。对于 actor 网络部分，每一个智能体都有其独立的 actor 网络，该网络分为以下三个部分：

信息编码器（message Encoder）：
动作选择器 (Action Selector)：action selector
权重生成器（Weight Generator）：

是一个 mask 向量，代表哪些智能体能够将自己的信息发送到通信信道上，表示拼接操作。例如，并且则。

那么当每个智能体生成自己的权重之后，算法如何根据权重来生成 mask 向量呢？这里就涉及到 Scheduler 部分的 WSA（Weight- based Scheduling Algorithm）模块。具体来说，WSA 模块采用了两种在通信领域简单但高效地分配算法：

Top(k)：顾名思义，选择权重排名靠前的智能体
Softmax(k)：先将权重通过 softmax 函数转化为一个概率分布，再从这个概率分布中进行采样

WSA 模块的主要问题是，在中心化训练时我们自然可以收集到所有智能体的权重，但是在去中心化执行时，如何运行 WSA 模块呢？本文表明去中心化的 WSA 是目前通信领域的研究热点，具体方法可参见论文附录部分，因为内容不在本文讨论范围之内，就不详细展开了。

最后是 Critic 模块，该模块包含两个 heads，具体框架如下（图片来源原论文）：

注意这里有两个 heads 是因为在 SchedNet 中要训练两个不同的 policy，其中一个 policy 是权重生成器，它的动作空间是连续的，因而本文使用了 DDPG 算法，所以需要 Q value。

另一个 policy 则是真正的policy，它的动作空间是离散的，因而本文使用了普通的 actor-critic 算法，并且 critic 通过来计算，这样可以同时保证较小的方差以及偏差，因而需要 state value。

具体的权重生成器的参数以及（动作选择器-信息编码器，这两者当作一个网络的两部分来整体考虑）的参数更新方式如下：

|| 协作学习

此类工作并不显式地学习智能体之间的通信，而是将 multi-agent learning 领域的一些思想引入到 MARL 中。而这类方案又可以分为以下三个类别：

基于值函数的方法：

Sunehag, Peter, et al. "Value-decomposition networks for cooperative multi-agent learning" arXiv preprint arXiv:1706.05296 (2017).

Rashid, Tabish, et al. "QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning" arXiv preprint arXiv:1803.11485 (2018).

Son, Kyunghwan, et al. "QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning" arXiv preprint arXiv:1905.05408 (2019).

基于演员-评论家的方法：

Lowe, Ryan, et al. "Multi-agent actor-critic for mixed cooperative-competitive environments" Advances in Neural Information Processing Systems. 2017.

Foerster, Jakob N., et al. "Counterfactual multi-agent policy gradients" Thirty-Second AAAI Conference on Artificial Intelligence. 2018.

Wei, Ermo, et al. "Multiagent soft q-learning" 2018 AAAI Spring Symposium Series. 2018.

Iqbal, Shariq, and Fei Sha. "Actor-Attention-Critic for Multi-Agent Reinforcement Learning" arXiv preprint arXiv:1810.02912 (2018).

基于经验回放缓存的方法：

Foerster, Jakob, et al. "Stabilising experience replay for deep multi-agent reinforcement learning" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.

Omidshafiei, Shayegan, et al. "Deep decentralized multi-task multi-agent reinforcement learning under partial observability" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.

下面我们将从这三个方面分别进行讨论。

基于值函数的方法

论文标题：Value-Decomposition Networks For Cooperative Multi-Agent Learning

论文链接：https://arxiv.org/abs/1706.05296

基于值函数的方法可以说是多智能体强化学习算法最开始的尝试（例如 Independent Q-Learning， IQL 算法）。虽然前面也提到将 IQL 算法与 DQN 算法结合能够在多智能体问题上取得比较好的效果，但是对于较为复杂的环境，IQL 还是无法很好地处理由于环境非平稳而带来的问题。

而中心化的方法，即将所有智能体的状态空间以及动作空间合并，当作一个智能体来考虑的方法，虽然能够较好的处理环境非平稳性问题，但是也存在以下缺陷：

在大规模多智能体环境中算法可扩展性较差
由于所有智能体联合训练，一旦某个智能体较早学到一些有用的策略，则其余智能体会选择较为懒惰的策略。这是因为其余智能体由于进度较慢，从而做出的策略会阻碍已经学到一些策略的智能体，从而使得全局汇报下降（来源原论文）

本文提出的 VDN 方法的基本思想是，中心化地训练一个联合的 Q network，但是这个联合的网络是由所有智能体局部的 Q networks 加和得到，这样不仅可以通过中心化训练处理由于环境非平稳带来的问题，而且由于实际是在学习每个智能体的局部模型，因而解耦智能体之间复杂的相互关系。

最后，由于训练完毕后每个智能体拥有只基于自己局部观察的 Q network，可以实现去中心化执行，即 VDN 遵循 CTDE 框架，并且解决的是 Dec-POMDP 问题。

具体来说，本文做出了如下假设：

这里之所以使用而不是是因为我们解决的是 POMDP 问题，并且也因为此，这里的 Q network 是使用 LSTM 构建。

我们注意到，上述分解满足一个很好的性质，即对左边的联合 Q function 进行操作，等价于对右边每一个局部 Q function 分别进行。这样可以保证训练完毕后去中心化执行时，即使整个系统只基于局部观察进行决策，其策略也是与基于全局观察进行决策是一致的。

下面我们简单推导一下上式是怎样得到的。假定整个多智能体系统中包含两个智能体，并且全局回报函数是每个智能体的局部回报函数的加和，

，那么我们有：

但是我们看到分解后的 Q 函数是基于全局观察的。这里我们可以假设相比于会更加依赖于，并且即使使用不能准确估计。

但由于我们使用的网络结构是 LSTM，那么估计误差是可以缩小的，并且还可以通过智能体之间的通信来进一步减小误差，所以本文假设：

同时还是为了算法在大规模环境下的可扩展性以及为了避免上面提到的中心化训练带来的第二个问题，VDN 采用了 parameter sharing 方法，并因此提出了 Agent Invariance 的定义（图片来源原论文）：

即使用 parameter sharing 的多智能体系统均满足这一性质。但是实际上并不是所有的多智能体系统都应该满足这一性质，因为不同的智能体在特定任务中，即使观测到同样的局部观察，其策略也是不同的。

为了解决这一问题，VDN（像其他方法一样），在输入中引入了类似于智能体索引号这样的额外信息来表示智能体的不同角色。这样，我们说整个多智能体系统是 conditionally agent invariant。

整个算法的框架如下图所示（图片来源原论文）：

最后本文进行了如下对比实验，baseline 模型设置如下（图片来源原论文）：

我们可以看到，实验为了减小 value decompostion 带来的误差，显式加入了通信模块，并分为高层通信以及低层通信（低层通信其实是互相共享局部观察），不同 baseline 具体网络结构以及部分实验结果对比如下图所示（图片来源原论文）：

论文标题：QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning

论文链接：https://arxiv.org/abs/1803.11485

QMIX 算法是 VDN 算法的后续工作，它的出发点是 VDN 做联合 Q-value 分解时只是进行简单的加和，这种做法会使得学到的局部 Q 函数表达能力有限，没有办法捕捉到智能体之间更复杂的相互关系，因而对 VDN 算法进行了修改。

具体来说，本文认为联合 Q 函数以及局部 Q 函数需要满足下述约束：

而 VDN 提出的加和分解方式只是满足这一约束的一个特例。QMIX 认为上述约束可以泛化到一个更大的单调函数族中，上述约束是这个单调函数族的必要非充分条件。这个单调函数族满足下面的约束：

为了使得学到的联合 Q 函数以及局部 Q 函数满足上述条件，QMIX 使用了如下包含 agent network、mixing network 以及 hypernetworks 的架构（图片来源原论文），注意到，QMIX 由于 mixing network 是一个非线性网络的原因，其表达能力因而超过 VDN：

实际上，约束 使得 mixing network 关于每一个局部 Q-value 的权重必须非负，这也是为什么 mixing network 中的 hyperneteorks 会加绝对值操作或者 ReLU 操作的原因。

另外，我们注意到，每个时刻的全局状态作为 mixing network 的额外输入，这个出发点与 VDN 一样，即每个智能体只依赖于局部观察可能无法准确估计其局部 Q 函数，在 VDN 中通过低层或者高层通信来引入全局信息，而 QMIX 中则更加直接。

最后实验结果也表明加上这一全局信息会大幅提升性能（图片来源原论文，NS 代表不加入全局状态作为输入）：

论文标题：QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement learning

论文链接：https://arxiv.org/abs/1905.05408

QTRAN 算法是对 VDN 以及 QMIX 算法的进一步改进（所以这三个工作是一条线），本文认为直接根据局部 Q 函数采用神经网络去逼近联合 Q 函数是一件比较困难的事情，因而将整个逼近过程分为两步：

首先采用 VDN 的方式得到加和的局部 Q 函数，作为联合 Q 函数的近似，接着去拟合局部 Q 函数与联合 Q 函数的差值，并证明了以下定理：

其中：

这里的代表局部得到的 action 的集合。并且定义一个 transformed joint-action value function (其实就是加和，用来逼近联合 Q 函数)。

为了满足上述定理，QTRAN 提出了两个算法 QTRAN-base 以及 QTRAN-alt，下面是这两个算法的结构图（图片来源原论文）：

我们先来看看 QTRAN-base 方法，该方法模型分为三部分：

独立 Q 网络：
联合 Q 网络：
联合 V 网络：

整体的损失函数如下：

其中：

接下来，本文认为约束：

对于非的 action 的约束过于松弛（因为训练数据中的数据很少，因而大部分的数据都是满足第二个约束），会使得算法很难拟合联合 Q 函数。

为此，本文提出了一个新的定理，即将上述约束中的第二个约束替换为下面一个更强的约束，最终得到的结果是一致的：

这个约束更多的聚焦于非的训练数据（这一部分数据占训练初期训练集的大部分）。为了满足这一约束，我们需要把上面列出的第三个损失函数替换如：

其中：

以上就是 QTRAN-alt 算法。

基于演员-评论家的方法

将单智能体强化学习算法扩展到多智能体环境中，最简单就是 IQL 类别方法，但是此类方法在复杂环境中无法处理由于环境非平稳带来的问题；另一方面，虽然中心化方法能够处理上述问题，但是与 IQL 相比又失去了较好的可扩展性。

前面介绍的基于 value-based 方法通过 value decomposition 方式来解决可扩展性问题，那么对于基于演员-评论家方法，由于其结构的特殊性，我们可以通过中心化学习（共享/独立）评论家但是每个智能体独立的演员，来很好的处理算法可扩展性问题的同时，拥有很好的抗环境非平稳能力。

论文标题：Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments

论文链接：https://arxiv.org/abs/1706.02275

本文提出的 MADDPG 算法将 DDPG 算法扩展到多智能体环境中，MADDPG 算法假定每一个智能体拥有自己独立的 critic network 以及 actor network，并且假定每个智能体拥有自己独立的回报函数，这样 MADDPG 算法就可以同时解决协作环境、竞争环境以及混合环境下的多智能体问题。

但是 MADDPG 算法假定每个智能体在训练时都能够获取其余所有智能体的局部观察以及动作，因而即使每个智能体的 critic network 是独立的，训练时也需要中心化训练，因而遵循 CTDE 框架。

MADDPG 算法框架如下图所示（图片来源原论文）：

由于每个智能体的 critic 网络是基于全局信息的，因而可以处理环境非平稳问题。每个智能体 actor network 的梯度通过如下方式计算：

critic network 的损失函数如下：

算法伪代码如下：

另外，算法还进行了两点改进。其一，由于算法假设中心化训练每个智能体的 critic network 时，需要知晓所有智能体当前时间步的局部观察以及动作，本文认为知晓每个智能体的动作（即策略）是一个比较强的假设，因而提出了一个估计其余智能体 policy 的方法。

具体来说，每个智能体均维护一个其余智能体 actor network 的估计，通过历史每个智能体的数据，使用以下损失函数监督训练这个估计的 actor network：

因而估计的 Q-value 通过如下方式计算：

另外，在多智能体环境中，本文认为训练出的针对每个智能体的 policy 容易对其余智能体过拟合，但是其余智能体的 policy 随着训练过程的进行是不断更新的，因而本文希望通过给每个智能体同时训练 k 个 actor network 的方式，使得智能体对于其他智能体策略的变化更加鲁棒。

具体来说，每个 episode 开始前，都从 k 个 actor 中随机采样一个来进行训练，并且每个 actor 都有独立的 experience replay。每个 actor 参数梯度计算方式如下：

论文标题：Counterfactual Multi-Agent Policy Gradients

论文链接：https://arxiv.org/abs/1705.08926

本文提出的算法 COMA 旨在解决 Dec-POMDP 问题中的 multi-agent credit assignment 问题，即多智能体信用分配问题。这个问题简单概括来说，由于 Dec-POMDP 问题中所有智能体共享同一个全局回报，因而每个智能体不知道自己的行为到底对这个全局回报产生了多大的影响，这就是多智能体信用分配问题。

COMA 算法与 MADDPG 一样，遵循 CTDE 训练框架，但是因为解决的是 Dec-POMDP 问题，所以所有的智能体共享一个联合的 critic network，该 network 与 MADDPG 一样，基于所有智能体的局部观察以及动作，但是 actor network 是独立的并且只基于局部观察。

COMA 与 MADDPG 在 actor network 上的不同之处在于前者使用的是 GRU 网络，为了更好的处理局部观察问题，但是后者使用的则是普通的 DNN。COMA 算法具体框架如下图所示：

COMA 使用的是 vanilla 的 actor-critic 方法，其核心之处在于引入了一个 counterfactual 的 baseline 函数。这个思路是受到 difference rewards 方法启发的（具体可参见 [4] [5]），该方法通过比较智能体遵循当前 actor network 进行决策得到的全局回报与遵循某个默认策略进行决策得到的全局回报，来解决多智能体信用分配问题。

但是这种方法包括以下几个问题：

由于需要知道遵循某个默认策略得到的全局回报，需要重复访问仿真环境；
该默认策略得到的回报可能并不在仿真器的建模之中，因而需要进行估计；
该默认策略的选取是完全主观的。

COMA 算法通过使用联合的 critic 来去计算每个智能体独自的优势函数来解决上述问题，该优势函数计算的是智能体遵循当前 actor network 进行决策得到的全局回报与一个反事实 baseline 之间的差值，这个反事实 baseline 通过求得该智能体 Q-value 的期望值得到，即：

算法伪代码如下：

论文标题：Multiagent Soft Q-Learning

论文链接：https://arxiv.org/abs/1804.09817

本文提出了一个类似于 MADDPG 的遵循 CTDE 框架的 MASQL（论文中没有这样进行缩写）算法，本质上是将 Soft Q-Learning 算法迁移到多智能体环境中，因而与将 DDPG 算法迁移到多智能体环境中的 MADDPG 算法类似，不过 MASQL 算法解决的是 Dec-POMDP 问题。

与 MADDPG 相比，MASQL 算法并不只是换了一种单智能体算法并将其迁移到多智能体环境，而是为了解决 Dec-POMDP 中的 relative overgeneralization 问题 [6]，该问题可简单描述如下（具体后面我们再进行分析）：

考虑一个如下图所示的 continuous game，坐标轴是两个智能体能够采取的动作，曲面代表联合动作对应的全局回报。虽然联合动作相比于联合动作拥有更高的全局回报，但是对于智能体来说，执行动作带来的期望收益要低于执行动作带来的期望收益，那么整体就会收敛到（次优）点。

接下来我们看看 relative overgeneralization 问题会如何影响到 multi-agent actor-critic 算法。对于一个 Dec-POMDP 问题，我们有如下多智能体（随机）策略梯度定理（本文证明得来）：

我们再来对比一下单智能体的（随机）策略梯度定理：

可以看到现在某个特定智能体的策略梯度是根据以下来放缩的：

这一项相当于根据其余智能体当前策略得到的一个期望联合 Q-value。

这样一个策略梯度的估计公式存在以下几个问题：

由于策略梯度是由根据其余智能体当前策略得到的一个期望联合 Q-value 来进行放缩的，其余智能体的当前策略不一定是最优的回应该智能体的策略，会导致策略梯度估计不准确；
即使我们解决了第一个问题，依旧存在前面提到的 relative overgeneralization 问题。

MADDPG 算法虽然通过中心化学习一个联合的 critic 可以尽可能保证第一个问题得以解决，但是第二个问题依旧存在。下面我们详细讨论为什么 MASQL 算法可以解决第二个问题。首先我们简单回顾一下 Soft Q-Learning 方法。

SQL 方法目的在于解决最优策略不是唯一的的任务，因而尝试学习一个最优策略的分布，从而学到所有可能的最优策略。为了实现这个目标，其实是求得下列优化问题的最优解：

为了解决上述问题，SQL 类似 Q-learning 方法，引入了 Soft-Q function 以及 Soft-V function：

并且我们可以采用以下 Soft Q-iteration 方法迭代求解得到上述两个最优值：

那么上述最优策略可以通过这两个函数来进行表示：

然而，直接使用这个策略在环境中进行采样非常困难，因而 SQL 方法采用 Stein Variational Gradient Descent (SVGD) 方法最小化以下 KL 散度来对这个最优策略进行估计：

因而 SQL 方法需要学习一个 Q function 以及 policy，可以被看作是一个 actor-critic 方法（但与实际的 actor-critic 方法还是不同的，将其看作 AC 方法只是为了能够实现 CTDE 框架）。接下来我们将其扩展到多智能体环境中，具体算法伪代码如下：

MASQL 算法与 MADDPG 算法一样，使用了一个中心化的 criti；但与 MADDPG 不同，每个智能体的 policy 不是只输出自己的action，而是输出所有智能体的 joint action，然后与环境交互时从中选取属于自己的 action。值从大到小意味着在训练初期会尽可能探索更大的 policy space，随着训练的进行会逐步收敛到最优的 policy 上，这样就可以解决上述第二个问题。

本文的实验设置也是为了表明 MASQL 相比 MADDPG 在解决 relative overgeneralization 问题上的有效性：

论文标题：Actor-Attention-Critic for Multi-Agent Reinforcement Learning

论文链接：https://arxiv.org/abs/1810.02912

本文提出的 MAAC 算法是在 MADDPG 上进行了一些修改，将 MADDPG 采用的 DDPG 算法替换为 SAC（soft actor-critic）算法，并将 COMA 提出的 counterfactual baseline 引入进来，因而可以同时处理协作、竞争以及混合环境，遵循 CTDE 框架。

其核心思想体现在，对于 MADDPG 算法，其每个智能体对应的 Q function 都是将其余智能体的局部观察以及动作无差别的作为输入，但是在现实场景中，智能体对于其余智能体的关注度是不一样的。

为此，MAAC 算法将注意力机制引入到 Q function 的构建之中，具体来说，每个智能体的 Q-function 网络结构如下（图片来源原论文）：

具体来说，每个智能体的 Q function 如下所示：

其中：

本文注意力机制采用的是多头注意力机制。由于在每个智能体的 Q function 中存在共享参数，因而优化目标与 MADDPG 不同：

其中：

最后，在更新策略网络的参数时，引入 COMA 提出的 counterfactual baseline：

算法伪代码如下：

基于经验回放（ER）的方法

Foerster, Jakob, et al. "Stabilising experience replay for deep multi-agent reinforcement learning" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.

由于这部分要介绍的两个工作主要聚焦于使用 ER 训练 Q-function 时增加稳定性（CommNet 甚至因为 ER 在 multi-agent 环境下的不稳定性而禁用了 ER），这两个方法前者遵循 CTDE 框架，并且类似 MADDPG 方法一样，均假设每个智能体拥有自己独立的 Q-function；后者则是完全独立的 IQL。这两个方法都是基于 Q-Learning 算法。

Omidshafiei, Shayegan, et al. 的工作致力解决 partial observation 的问题，因而采用的是 DRQN 算法，本文提出采用 ER 训练 DRQN 时应当采用如下方式，并提出了 concurrent experience replay trajectories 的概念（图片来源原论文）：

即每个智能体在独立训练自己的 Q-function 时，从 ER 中 sample 出来的数据需要从 episode 层面以及时间层面上对齐。

Foerster, Jakob, et al. 则是从 importance sampling 的角度来考虑这个问题。对于某个智能体的 Q-function，我们有：

而

就是导致 ER 在多智能体环境下不稳定的原因。

具体来说，不同时刻收集的数据是不同的，但是我们将其直接拿来使用，就像 on-policy 的方法使用 off-policy 的数据一样。

因而，本文基于 importance sampling 方法，把每一时刻的作为额外项存入ER，即每一时刻存入如下五元组：

并将训练 Q-function 时的损失函数改为：

注意到以上 Q-function 基于全局观察。

下面我们再看看局部观察的情况。首先我们定义一个增广状态空间已经对应的观察函数，回报函数

以及状态转移函数：

那么对应的贝尔曼方程为：

将其展开，我们有：

这时候我们可以看到依旧是导致不稳定问题的部分原因（完全的是因为），但因为不是全部，因而采用上述损失函数在部分观察的环境下只是一种估计。

|| 智能体建模

这一类方法主要聚焦于通过对其他智能体的策略、目标、类别等等建模来进行更好的协作或者更快地打败竞争对手。由于这一类方法我掌握的还不够全面，因而在这里简单的讨论几个估计其他智能体策略的相关工作。

Foerster, Jakob, et al. "Stabilising experience replay for deep multi-agent reinforcement learning" Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.

Rabinowitz, Neil C., et al. "Machine theory of mind" arXiv preprint arXiv:1802.07740 (2018).