MARL 算法汇总
0 Preliminaries
在多智能体强化学习算法中，两个主要的技术指标为合理性与收敛性。
- 1. 合理性（rationality）：在对手使用一个恒定策略的情况下，当前智能体能够学习并收敛到一个相对于对手策略的最优策略。
- 2. 收敛性（convergence）：在其他智能体也使用学习算法时，当前智能体能够学习并收敛到一个稳定的策略。通常情况下，收敛性针对系统中的所有的智能体使用相同的学习算法。
Q：为什么不能直接将单智能体强化学习算法直接移植到多智能体环境中？ A: 在多智能体环境中，每个 agent 的策略在训练的过程中都是不断变化的，这导致对每个 agent 来说，环境都是不稳定的，而在这种不稳定的环境中学习到的策略是毫无意义的。所以对于 Q-learning 这类方法，经验回放的方法（experience replay）是完全失效的。而对于 policy gradient 方法来说，随着 agent 数量增加，环境复杂度也增加，这就导致通过采样来估计梯度的优化方式，方差急剧增加。
1 完全竞争环境的MARL
1.1 Minimax-Q
Minimax-Q 主要应用于 二人零和随机博弈 中。
Minimax 算法 求解二人零和博弈的公式如下： 即，每个智能体最大化在与对手博弈中最差情况下的期望奖励值。可构建线性规划来求解每个特定状态的阶段博弈的纳什均衡策略。
所以这里 Minimax-Q 的 Minimax 指的是 Minimax 算法，而 Q 指的是借用 Q-learning 中的 TD 来迭代学习状态值函数或动作-状态值函数。
Minimax-Q 的优化目标：
缺点：
- • 线性规划的求解使得学习速度较慢；
- • Minimax-Q 算法能够找到多智能体强化学习的纳什均衡策略。但是假设对手使用的不是纳什均衡策略，而是一个较差的策略，则该算法无法让智能体根据对手的策略来调节优化自己的策略，而只能找到随机博弈的纳什均衡策略。这是由于 Minimax-Q 算法是一个 对手独立算法（opponent-independent algorithm），不论对手策略是怎么样的，都收敛到该博弈的纳什均衡策略。就算对手采用一个非常弱的策略，当前智能体也不能学习到一个比纳什均衡策略更好的策略。
2 完全合作环境的MARL
2.1 MAPPO
The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games https://arxiv.org/pdf/2103.01955.pdf
MAPPO 算法的基本思想是 中心式训练，分散式执行（Centealized Training and Decentralized Execution, CTDE）。
先回顾一下 PPO 算法。PPO 是一个经典的 on-policy 算法，从 TRPO 改进而来。从实现上来讲，它采用的是经典的 actor-critic 架构，actor 负责接收局部观测，并输出动作，critic 负责评估在当前状态下做出该动作的好坏。MAPPO 同样也采用 actor-critic 架构，不同之处在于这里的 critic 学的是一个 中心价值函数（Centralized Value Function），即此时 critic 能够观测到全局信息，包括其他 agent 的信息和环境的信息。
2.2 COMA
Counterfactual Multi-Agent Policy Gradients https://arxiv.org/pdf/1705.08926v1.pdf
COMA 算法的基本思想是 中心式训练，分散式执行（Centealized Training and Decentralized Execution, CTDE）。
作者提出集中训练的方法大致可以分为 在智能体之间传递梯度 以及 参数共享，这两种方法均没有在训练过程中利用额外的信息，相反，COMA在训练过程中会使用一个集中式的 critic 网络，但依然可以实现分布式执行。同时本文提出大多多智能体的工作都假设智能体之间完全协作，共用同一奖励，导致单个智能体难以推断自己对于团队成功的贡献，这就是所谓的多智能体 信用分配（credit assignment）问题，为此，本文通过利用一个 反事实基准（counter-factual baseline） 来区分不同智能体对系统奖励的贡献。
COMA 的三个主要创新点：
- 1. 采用了集中式的 critic；
- 2. 使用了反事实基准；
- 3. 利用 critic 表征对基准进行高效估计
2.2 VDN
Value-Decomposition Networks For Cooperative Multi-Agent Learning https://arxiv.org/pdf/1706.05296.pdf
智能体共享团队奖励会带来“credit assignment (信用分配) ” 问题，即利用该团队奖励拟合出的值函数不能评价每个智能体的策略对整体的贡献。在这篇文章中，同样存在这样的问题。同时，由于每个智能体都是局部观测，那么对其中一个智能体来说，其获得的团队奖励很有可能是其队友的行为导致的。也就是说该奖励值对该智能体来说，是“虚假奖励 (spurious reward signals) ”。因此，每个智能体独立使用强化学习算法学习 (即 Independent RL) 往往效果很差。这种虚假奖励还会伴随一种现象，作者称作 “lazy agent (惰性智能体) ”。当团队中的部分智能体学习到了比较好的策略并且能够完成任务时，其它智能体不需要做什么也能获得不错的团队奖励，这些智能体就被称作“惰性智能体”。
为了能够解决上述问题，作者提出了“值函数分解（Value-Decomposition）”的研究思路，将团队整体的值函数分解成 N 个子值函数，分别作为各智能体执行动作的依据。
2.3 QMIX
QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning https://arxiv.org/pdf/1803.11485.pdf
和 VDN 类似，QMIX 也是一种基于价值的方法，可以以集中的端到端方式训练分散策略。QMIX 采用了一个网络，将联合动作值估计为每个智能体值的复杂非线性组合（VDN是线性加和），且仅基于局部观测。并且在结构上施加约束，使联合动作值函数与每个智能体动作值函数之间是单调的，保证集中策略和分散策略之间的一致性。
3 合作-竞争混合型环境的MARL
3.1 MADDPG
Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments https://arxiv.org/pdf/1706.02275.pdf
MADDPG 算法的基本思想是 中心式训练，分散式执行（Centealized Training and Decentralized Execution, CTDE）。
在 MADDPG 中，一个重要的前提是：当我们知道所有 agent 的动作时，无论策略如何变化，我们的环境都是稳定的。
MADDPG 算法具有以下三点特征：
- 1. 通过学习得到的最优策略，在应用时只利用局部信息就能给出最优动作。
- 2. 不需要知道环境的动力学模型以及特殊的通信需求。
- 3. 该算法不仅能用于合作环境，也能用于竞争环境。
MADDPG 本质上还是一个 DPG 算法，针对每个智能体训练一个需要全局信息的 Critic 以及一个需要局部信息的 Actor，并且允许每个智能体有自己的奖励函数（reward function），因此可以用于合作任务或对抗任务。并且由于脱胎于DPG算法，因此动作空间可以是连续的。
3.2 Nash Q-Learning
Nash Q-Learning 是将 Minimax-Q 从 二人零和博弈 扩展到 多人一般和博弈 的算法。
Nash Q-Learning 在 合作性均衡 或 对抗性均衡 的环境中能够收敛到纳什均衡点，其收敛性条件是，在每一个状态的阶段博弈中，都能够找到一个全局最优点或者鞍点，只有满足这个条件，Nash Q-Learning 算法才能够收敛。
3.3 Independent Q-learning
Multi-Agent Cooperation and Competition with Deep Reinforcement Learning https://arxiv.org/pdf/1511.08779.pdf
IQL（Independent Q-learning）的思想简单粗暴，不用全局价值，仅使用单个 agent 的价值学习。
IQL 将其余智能体直接看作环境的一部分，也就是对于每个智能体都是在解决一个单智能体任务，很显然，由于环境中存在智能体，因此环境是一个非稳态的，这样就无法保证收敛性了，并且智能体会很容易陷入无止境的探索中，但是在工程实践上，效果还是比较可以的。
