News Message

强化学习2021论文

by wittx 2022-03-21

多智能体强化学习2021论文（一）MAPPO & IPPO

论文标题The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games，原文https://arxiv.org/abs/2103.01955
本文研究了研究了多智能体PPO (MAPPO)算法，一种采用集中值函数的多智能体PPO变体，最后在星际SMAC任务以及多智能体任务中验证了算法效果。这篇文章的研究说明了，即使是最简单的，不进行任何算法或者网络架构变动的PPO算法，只要使用一些技巧，也能在多智能体任务中取得较好的效果。
背景
首先要回顾一篇论文：Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?
论文地址：https://arxiv.org/abs/2011.09533
这篇文章中提到，可以直接将PPO算法应用到SMAC任务中，构建一个像IQL一样的IPPO（independent PPO）算法，这样简单的算法也能在部分任务上取得了超越QMIX的效果。
PPO算法：

PPO算法是对TRPO算法的进一步优化，主要使用了重要性采样，和策略更新裁剪等思想。这里用的是带clip的PPO，clip的目的是防止策略更新的幅度太大或者太小。
原文中的PPO还使用了Generalized Advantage Estimation (GAE)，使用了GAE后优势函数如下：

其中

GAE的大致想法是对从1步到n步计算出的各个优势函数进行加权，加权计算出的均值为最后的优势函数，这样做可以减小方差。
最后的actor目标函数为：

Critic目标函数为：

总体的目标函数为：

其中a为智能体的数量。
IPPO算法将PPO算法扩展到多智能体任务中，每个智能体都独立运行一套PPO算法，这个想法虽然简单，但却很有效。实验结果表明，在一些任务中IPPO能够达到SOTA。

这篇文章认为，PPO的策略裁剪机制在SMAC任务中非常有效。PPO算法的稳定性更好，因此在多智能体系统非稳态的环境中，IPPO的学习稳定性优于IAC（independent actor-critic）和IQL（independent q-learning），所以性能更好。
同时，在部分SMAC的任务中，智能体是完全协作的，引入中心化的机制未必会让性能提升。
对于QMIX等中心化的算法来说，尚不清楚全局信息state起作用的机制。

算法
IPPO算法说明了将PPO应用到多智能体系统中是十分有效的。本文则更进一步，将IPPO算法扩展为MAPPO。区别是PPO的critic部分使用全局状态state而不是observation作为输入。
同时，文章还提供了五个有用的建议：
1.Value normalization: 使用PopArt对 value进行normalization。PopArt是一种多任务强化学习的算法，将不同任务的奖励进行处理，只需要训练一个智能体就可以同时解决多种任务。这篇文章认为，使用PopArt是有帮助的。
2.Agent Specific Global State: 采用 agent-specific 的全局信息，直接使用各个智能体observation联合起来可能会导致维度过高，而使用state又可能导致丢失信息。本文使用了一种特殊的state，包含了更多的信息。本文作者认为SMAC中原有的全局state存在信息遗漏，其所包含的信息甚至少于agent的局部观测量，这也是直接将MAPPO应用在 StarCraftII中性能表现不佳的重要原因。
3.Training Data Usage: 防止同一份数据训练次数过多。简单任务中推荐使用 15 training epochs，而对于较难的任务，尝试 10 或者 5 training epochs。除此之外，尽量使用一整份的训练数据，而不要切成很多小份的mini-batch训练。
4.Action Masking: 在多智能体任务中经常出现 agent 无法执行某些 action 的情况，建议无论前向执行还是反向传播时，都应将这些无效动作屏蔽掉，使其不参与动作概率计算。
5.Death Masking: 在多智能体任务中，也经常会出现agent死亡的情况。当 agent 死亡后，应当仅保留其 agent id，将其他信息屏蔽。

实验
首先是消融实验，验证改进后的熵的有效性。
采用了这五条建议之后，MAPPO算法的效果能够超越QMIX，和SOTA算法RODE相比。

同时也做了消融实验，验证了这五条建议的有效性：

多智能体强化学习2021论文（二）RODE

论文标题RODE: Learning Roles to Decompose Multi-Agent Tasks，原文https://arxiv.org/abs/2010.01523，发表于ICLR 2021。

本文提出了一种基于角色的多智能体强化学习方法，用一个角色选择器将联合动作空间分解为有限的动作行动空间，对应不同的角色。智能体在进行决策的时候策略分为两层，先选角色，再根据角色来选策略。通过分角色和分层，可以解决多智能体环境下联合动作状态空间过大的问题。本文在SMAC环境下进行实验，大多数场景下都达到了SOTA，同时做了消融实验，验证模块有效。

背景

Dec-POMDP，CTDE框架，QMIX、MAVEN等value-based的值分解算法。

另外，有几篇有类似思想的相关论文。

ROMA：用互信息来分角色学习。https://zhuanlan.zhihu.com/p/261383886

ASN：手动划分动作和观测空间。https://zhuanlan.zhihu.com/p/199072017

算法

首先定义了角色和子任务的概念：

所有角色的动作空间的并集，就是原始的动作空间。

算法的网络图如下所示：

一共分为三个部分，a是学习动作表示，b是角色选择器，c是每个角色的决策。

首先是第一部分，学习一种新的动作表示方式，即一个动作编码器：

，能将原始的one-hot动作映射到d维的新动作空间上

。

学习动作编码器是为了方便后续的动作分解。新的动作表示应当与原始的动作表示效果相同，即能生成相同的状态和奖励。损失函数如下所示：

z是新的状态表示。p是一个能表示状态转移函数的网络，能根据z来预测下一时刻的观测量和奖励。这里采用监督学习的方式，将预测值和真实值做差，求loss。最小化这个loss，就说明使用z和使用原始的动作能达到相同的效果。

在学习了新动作表示z之后，再对z进行聚类。本文是采用K-means方法进行聚类的。设置k个角色，用与环境交互生成的样本进行聚类，将聚到一类的动作组成同一角色的动作空间。同时角色是动态变化的，每隔一定时间步后会重新进行聚类。

然后智能体就可以进行决策了。这里采用了分层的方式，降低了决策粒度。上层是网络图中的b模块，下层是图中的c模块。上层为智能体选择合适的角色，下层根据角色去为智能体选择动作。

上层的动作数是角色的数量。这里使用了DQN算法。同时为了强调z的作用，使用如下方式将z的信息编码入Q值中：

这里的

是对智能体j能执行的动作求一个平均。

之后计算点积：

其中

是根据状态动作历史求出的普通的q值。

然后，使用QMIX算法的思想，将所有智能体的q值拟合为总体的q值，用总q值求loss。

下层是为每个角色选动作，动作空间是聚类后的角色动作空间。同样算法是用DQN，思想与上层的方法类似。

实验

首先是验证学习到的新动作表示是否有效。

可以看到对z聚类后的结果，和原始的动作是能够对应的。

接着在SMAC的复杂任务下进行测试，达到了SOTA水平。

最后用消融实验验证了添加的模块有效。

多智能体强化学习2021论文（三）VDAC

论文标题Value-Decomposition Multi-Agent Actor-Critics，原文https://arxiv.org/abs/2007.12306，发表于AAAI 2021。

本文将QMIX中的值分解思想扩展到policy-based的论算法里面，提出了一种actor-critic架构的对V值分解方法VDAC。证明了VDAC的收敛性。在SMAC上与COMA、IAC等算法比对，同时做了消融实验验证模块有效。

背景

协作式多智能体任务，Dec-POMDP，CTDE框架，VDN、QMIX等value-based的值分解算法。COMA、MADDPG等policy-based的MARL方法。

总体上来看，对于policy-based的多智能体算法，梯度是：

算法

首先提出了一种朴素的多智能体ac（naive central critic）算法。使用td-error来进行梯度更新。

然后对这里的V进行分解（Value Decomposition Actor-Critic），和VDN、QMIX类似。

对应的两种分解方法，线性分解和单调分解：

对应的两种loss：

然后证明了一下算法的收敛性。简单来说，就是证明作为baseline的V梯度是0。由于V和动作无关，所以可以得出：

这就和单智能体的情况一样了。因此剩下的梯度是：

实验

都是SMAC中简单地图的实验。

几个消融实验，分别验证使用td-error，使用mixing net等模块的有效性。

多智能体强化学习2021论文（四）CMAE

论文标题Cooperative Exploration for Multi-Agent Deep Reinforcement Learning，原文http://proceedings.mlr.press/v139/liu21j/liu21j.pdf，发表于ICML 2021。

本文提出了一种新的多智能体探索算法，将高维的状态空间投影到低维的受限状态空间，从受限空间中选择目标，并训练探索策略来实现目标，并且根据目标重塑的奖励函数。最后在MPE、SMAC等环境中展开实验，与QMIX、EITI、EDTI等算法比对，同时做了消融实验验证模块有效。

背景

多智能体强化学习，Dec-POMDP和CTDE，VDN、QMIX等value-based的值分解算法。

EITI和EDTI两篇多智能体探索的算法，可见https://zhuanlan.zhihu.com/p/317863684

算法

智能体的策略分为探索策略μ和目标策略π两个部分，目标策略用来最大化return，探索策略用来从未被探索的状态中收集数据。采样的时候使用

的形式结合两种策略来进行采样。算法的整体框架如下所示：

其中目标策略是使用buffer中的数据正常更新的。

而探索目标则是使用另一套更新方式，当状态达到共享目标g时，为奖励函数加上额外的奖励。

共享目标g是一种鼓励探索的设置，如果状态为g，说明探索做得比较好。

本文的一个重点是求g。由于多智能体的环境复杂，状态空间较大，所以需要先将普通的状态空间投影到受限状态空间，将高维状态空间投影到低维空间：

Sk就是求得的受限空间，projk是投影函数，k是受限状态空间中受限状态的个数。

这里使用了一个计数器c来计算在受限状态空间中一个特定的受限状态出现的次数（c越小，表示探索得越多）。现在，g的计算方式为：

另一个问题是如何求出好的受限状态空间，实际上是要求出最佳的k，即k*。本文使用了树

来存储受限状态空间。在树中，每个受限状态空间有一个u值，每次根据u值softmax采样，来选出受限状态空间。

u值是用c来算出来的，先求得一个分布：

再求出一个标准熵：

u值是它的相反数

u值越大，所对应的受限状态空间的探索能力越好。

根据u求出最好的k。

这一部分的流程为：

最后是受限状态空间树的扩展。每隔一段episode，空间树就会被扩展，算法流程为：

实验

MPE中的实验，分为稀疏奖励和稠密奖励。

SMAC中的实验：

消融实验

多智能体强化学习2021论文（五）QPLEX

论文标题QPLEX: Duplex Dueling Multi-agent Q-learning，原文https://arxiv.org/abs/2008.01062，发表于ICLR 2021。

本文提出了一种新的MARL方法，称为双Dueling多智能体q学习(QPLEX)，采用双Dueling网络结构来分解联合值函数。这种双Dueling结构将IGM原理转化为了易于实现的优势函数约束，从而实现高效的值函数学习。在SMAC等环境中展开实验，取得了良好的效果。

背景

多智能体强化学习，Dec-POMDP和CTDE，VDN、QMIX、QTRAN、WQMIX等多智能体值分解算法。

在值分解方法中，为了满足IGM条件（QTRAN论文提出，联合Q值取最优时的联合动作与单个智能体的Q值取最优的局部动作一致），VDN有单调性约束，QMIX有可加性约束：

这些约束限制了联合值函数的表达能力，在一些复杂任务中，可能会无法求出最优解。

算法

引入了dueling DQN的思想，将Q表示为V和Advantage加和的形式。

那么，由于V和动作无关，对于Q的IGM条件就转化为了对于A的IGM条件：

对于Q的IGM和对于A的IGM是等价的。

所以，本文中的联合Q值不是直接计算出来的，而是通过联合V和联合A的加和计算得来的。也就是将联合Q的分解变为了对联合V和联合A的分解。

算法的框架图：

值得注意的是，这里计算tot的联合值时没有像QMIX那样使用mixing net，而是使用了transform，用多头注意力机制来计算各个值的权重：

其中：

当然，还是要保证这个权重值大于0。

最后，联合Q值可以推导成：

其中的前一项，就是VDN中的线性加和。后一项可以当作对VDN的修正。因此，QPLEX算法比VDN等算法拥有更强的表示能力。

实验

矩阵游戏实验。QMIX无法解决的问题，QPLEX可以解决。

SMAC中的实验，分为online和offline两个部分。offline的数据是由QMIX跑出来的。

多智能体强化学习2021论文（六）EMC

论文标题 Episodic Multi-agent Reinforcement Learning with Curiosity-driven Exploration，原文https://arxiv.org/abs/2111.11032，发表于NeurIPS 2021。

本文在MARL中提出了一种用于MARL的基于预测的好奇心内在奖励，以及结合了Episodic Memory技术，提高了多智能体的探索效率。在单智能体的Q值上使用状态预测内在奖励，在联合Q上用Episodic Memory Deep Q-Networks来加强约束。最后在Predator Prey、SMAC等环境下进行实验和消融实验，验证了算法的效果。

背景

多智能体强化学习，Dec-POMDP和CTDE等内容。可以参考本专栏之前的一系列文章。

除此之外，本文还用到了两项技术。一个是基于状态预测的好奇心内在奖励。好奇心驱动是使用内在奖励鼓励agent探索更陌生的状态。其中一类方法是基于状态预测误差的方法，将预测值与真值的距离作为内在奖励，可以鼓励探索。（预测某一个状态时，如果对该状态的了解很少，误差就会高，从而驱使智能体对该状态进行探索。）

这一部分的知识，可以参考论文ICM （Curiosity-driven exploration

by self-supervised prediction）和RND（Exploration by random network distillation）

本文用到的另一项技术是Episodic Memory ，主要用到了Model-Free Episodic Control和EMDQN（Episodic Memory Deep Q-Networks）这两篇论文中的知识。

这一部分可以参考https://zhuanlan.zhihu.com/p/146191426。

简单来说，就是采样后存储状态动作对(s,a)的最高累积奖励：

每次采样后都更新状态和动作的最高累加奖励，用H记录下来。之后用H去辅助Q值的训练。

这样可以提升Q值训练的效率。

算法

框架图：

总体上，还是用了值分解的思路，每个智能体都求一个局部Q，局部Q加和就是联合Q（这里可以使用VDN 、QMIX、 QPLEX等方法去算联合Q值，都可以与本文的算法结合）。

针对于局部Q，使用了一个预测器去预测其值，然后算预测值和实际值的误差，当作内在奖励。

内在奖励会加到reward里面，帮助算td-error：

另外就是episodic memory的部分，这一部分是用联合Q值Qtot算的。H值计算方式如下：

最后的损失函数是：

实验

gridworld game测试了各种算法加上EMC的效果：

捕食者-猎物环境：

SMAC环境：

消融实验，分别测了一下两个模块的有效性：

多智能体强化学习2021论文（七）FOP

论文标题 FOP: Factorizing Optimal Joint Policy of Maximum-Entropy Multi-Agent Reinforcement Learning，原文http://proceedings.mlr.press/v139/zhang21m/zhang21m.pdf，发表于ICML 2021。

本文提出的方法属于分解的方法，对最大熵多智能体强化学习进行分解，将联合策略分解为局部策略，并证明了其收敛性。最后在matrix game、MTQ game、SMAC等环境下进行实验和消融实验，验证了算法的效果。

背景

多智能体强化学习，Dec-POMDP和CTDE等内容。参考之前的文章。

值分解方法，VDN、QMIX、QTRAN等算法，IGM条件和各种值分解方法的约束条件等内容。

除此之外，本文主要用到最大熵强化学习的思想，需要了解soft q-earning 和soft actor-critic等算法的思想。可以参考文章https://zhuanlan.zhihu.com/p/70360272。

简单来说，SAC属于最大熵强化学习，优化目标不仅包含reward，还包含策略的熵。最大化策略的熵值，可以使策略更随机，能够加强探索能力和策略的鲁棒性。

算法

本文提出的方法是policy-based的方法，但是仍然采用了值分解的思想，只不过分解的是联合policy。

对应IGM条件，本文提出了IGO（Individual-Global-Optimal）条件：

联合策略等于所有局部策略的乘积，同样，当所有局部策略取到最优，联合策略取到最优。IGO条件可以看作是IGM条件扩展到policy-based的算法上。

本文提出的FOP算法的思想很简单，就是将多智能体的联合SAC分解为局部的SAC。

联合SAC的优化目标是：

联合策略由贝尔曼方程得出：

最优联合Q为：

最优联合策略为：

同样地，对于每一个智能体，最优局部策略为：

将这几个式子带入IGO条件的公式（4），可以得到：

α和αi都是SAC中的温度参数。

之后证明了收敛性（不过论文里没有找到补充材料）。

算法的整体框架如下所示：

主要是局部Q，局部V，联合V，权重网络，局部策略网络等几个网络。

权值网络是计算温度参数，即：

局部Q，局部V，联合V，策略网络都是用soft方式计算的，FOP对联合Q进行分解：

局部Q，联合V，和权值网络由td-error优化：

局部V是由下式优化的：

最后是策略网络，和SAC类似，可以通过优化KL散度来优化策略：

由于V中没有对策略的梯度，最后可以写成：

实验

非单调矩阵游戏的实验：

The Max of Two Quadratic Game (MTQ)上的实验：

SMAC上的实验：

消融实验，在矩阵游戏上对温度参数的消融：

在MTQ上不同退火方式消融：

多智能体强化学习2021论文（八）FACMAC

论文标题 FACMAC: Factored Multi-Agent Centralised Policy Gradients，原文https://arxiv.org/abs/2003.06709，发表于NeurIPS 2021。

本文提出一种对MADDPG的改进算法FACMAC，将QMIX等论文的值分解思想引入到actor-critic算法的critic中，对critic的Q值进行分解，与QMIX等论文不同的是，这里的分解没有单调性约束。同时，FACMAC使用了一个集中式的策略梯度估计器，计算梯度时对所有智能体的策略求梯度，而不是对单个智能体的策略求梯度。实验部分在连续环境MPE、Multi-agent MuJoCo，以及离散环境SMAC下进行实验和消融实验，验证了算法的效果。

背景

多智能体强化学习，Dec-POMDP和CTDE等内容。可以参考本专栏之前的一系列文章。

值分解方法，VDN、QMIX、QTRAN等算法，IGM条件等内容。

MADDPG算法，论文原文https://arxiv.org/abs/1706.02275，可以参考专栏https://zhuanlan.zhihu.com/p/53811876的讲解。

在MADDPG中，每个智能体的策略更新方式如下：

x是智能体observation的集合。所以在MADDPG中，每个智能体学习一个中心化的Q，然后用这个Q取指导策略的更新。

算法

本文的思想比较简单，就是对MADDPG做了两点改进。首先是引入VDN、QMIX等论文的值分解思想，不再直接计算Q，而是由局部Q拟合出Q_tot。

更新方式也和值分解方法相同：

FACMAC将值分解的思想引入到multi-agent actor-critic架构下，类似的想法在DOP（https://arxiv.org/abs/2007.12322）和VDAC（ https://arxiv.org/abs/2007.12306）等论文中也出现过。

在智能体数量增多时，值分解的Q避免了维度爆炸的问题，效率更高。

另外，由于策略是由policy网络求出的，不需要贪心地根据Q来选择动作，自然就不需要满足IGM条件。所以这里对Q的分解不需要满足单调性假设，算法在解决非单调任务时效果更好。

FACMAC的另一点改进是计算梯度的方式，即使用centralised policy gradient (CPG)。MADPPG中，更新policy时，对于智能体i，Q的输入包含有所有智能体的动作，其中只有智能体i的动作是由policy算出的，其他智能体的动作都是存储在buffer中的动作。更新时只更新智能体i的策略梯度