【综述】多智能体强化学习算法理论研究

报道：深度强化学习实验室
作者： 刘浚嘉
编辑：DeepRL

Image

虽然目前多智能体强化学习 MARL 在很多领域取得了不错的结果，但很少有相关的理论分析。本综述挑选并汇总了拥有理论支撑的 MARL 算法，主要是以下两种理论框架：

Markov / stochastic games 马尔可夫/随机博弈
extensive-form games 形式广泛的游戏

并关注以下三种类型的任务：

fully cooperative
fully competitive
a mix of the two

此外，本文还给出了一些MARL理论的新观点，包括 extensive-form games, decentralized MARL with networked agents, MARL in the mean-field regime, (non-)convergence of policy-based methods for learning in games, etc

1 Introduction

MARL 算法的面临以下问题

由于所有agent同时根据自己的利益改进其策略，每个agent所面对的环境变得 non-stationary。这打破了single agent环境中大多数理论分析的基本框架并使之无效。
随着agent数量的增长而呈指数增加的联合行动空间可能会导致可扩展性问题，这被称为 the combinatorial nature of MARL（Hernandez-Leal et al.，2018）。
The information structure（即 who knows）在MARL中也很重要，因为每个agent对他人观察的访问均受到限制，从而导致本地决策规则可能欠佳。

2 MARL Background

Image

2.1 Markov/Stochastic Games

Cooperative Setting

Competitive Setting

完全竞争的MARL一般被建模为 zero-sum Markov games 马尔可夫零和博弈，。为了便于算法的设计和分析，大部分文章只关注两个agents之间的竞争，一个agent的奖励正好是另一个的损失。此外，零和博弈还被用于 robust learning，因为阻碍agent学习过程的uncertainty可以被抽象为在博弈中总是与agent对抗的虚拟对手。

Mixed Setting

混合设定一般也被称作general-sum一般和博弈，其对agents的目标和关系没有任何限制。每个agent都是自私的，他们的奖励可能与他人的利益冲突。博弈论中的均衡解决方案概念，例如Nash均衡，对为此通用设置开发的算法具有最重要的影响。

此外，还有一些研究包同时含 fully cooperative and com- petitive agents 的设置，例如，两个零和 competitive 团队，每个团队中都有 coorperative agent的情况。

2.2 Extensive-Form Games

马尔可夫博弈的问题在于：只能处理完全观察到的情况，每个智能体对整个系统的状态和动作都有很清晰的认识。将马尔可夫博弈扩展到部分可观测的情况可能是适用的，但是即使在合作环境下，这也具有挑战性。

相反，extensive-form games 框架就可以处理信息不完备的多智能体决策问题。该框架植根于计算博弈论，并已被证明可以在温和条件下允许多项式时间复杂度的算法

Various Settings

Connection to Markov Games

3 Challenges

3.1 Non-Unique Learning Goals 目标不唯一

不同智能体间，学习的目标不唯一。被设计为收敛到NE的学习动力对于实际的MARLagent来说可能是不合理的。Instead, the goal may be focused on designing the best learning strategy for a given agent and a fixed class of the other agents in the game。

用 convergence（达到平衡点）作为MARL算法分析的主要性能标准还存在争议。因为 Zinkevich et al. (2006) 证实基于价值的MARL算法无法收敛到一般性和马尔可夫博弈的平稳NE，这激发了 cyclic equilibrium 的新解决方案概念。在该概念下，agent 通过一系列 stationary policies（即不收敛到任何NE策略）严格循环。或者，将学习目标分为 stable 和 relational 两个方面，前者在给定预定义的、有针对性的对手算法的情况下，确保算法收敛，而后者则要求在其他主体保持稳定时收敛到 best-response。如果所有agent都既稳定又理性，则在这种情况下自然会融合到NE

此外，regret 的概念为捕捉 agent 的 rationality 引入了另一个角度，与 the best hindsight static strategy 相比，它衡量了算法的性能（Bowling和Veloso，2001；Bowling，2005）。渐近平均零后悔的 No-regret algorithms 保证了某些博弈的均衡收敛性（Hart和Mas-Colell，2001；Bowling，2005；Zinkevich等，2008），这从根本上保证了该 agent 不会被其他 agent 利用。

Kasai等（2008），Foerster等（2016），Kim等（2019）研究了 learning to communicate 的方式，以便 agents 更好地进行协调。对通信协议的这种关注自然激发了最近对高通信效率的MARL的研究（Chen等，2018; Lin等，2019; Ren和Haupt，2019; Kim等，2019）。其他重要目标包括如何在不过度拟合某些 agent 的情况下进行学习（He等人，2016; Lowe等人，2017; Grover等人，2018），以及如何在恶意/对抗性或失败/功能失调的情况下稳健学习。（Gao等，2018; Li等，2019; Zhang等，2019）。

3.2 Non-Stationarity 非平稳

很明显，由于多智能体动作结果的相互影响，agent 需要考虑其他 agents 的 action 并相应地适应 joint action，导致了单智能体的马尔可夫假设不适用。
关于这方面的知识，可见 Hernandez-Leal 2017年的综述，该文章中特别概述了如何通过最新的 MARL 学习算法对其进行建模和解决。

3.3 Scalability Issue 可扩展性

为了处理非平稳性，每个 agent 都可能需要考虑联合动作空间，然而联合行动的规模会随着智能体的增加而成倍的增加。这也被称为MARL的 combinatorial nature（Hernandez-Leal et al.，2018）。
一种可能的补救措施是，另外假设关于动作依赖的价值或奖励函数的因式分解结构。
参见Guestrin（2002a，b）；Kok和Vlassis（2004）提出了原始的启发式思想，以及最近的 Sunehag et al. (2018); Rashid et al. (2018) 等。直到最近才建立了相关的理论分析**（Qu and Li，2019）**，该模型考虑了一种特殊的依赖结构，并开发了一种可证明的基于模型的收敛算法（不是RL）。

3.4 Various Information Structures 不同的信息结构

Image

中心化 MARL：大量工作都假设存在一个 centralized controller，该中央控制器可以收集信息，例如联合动作，联合奖励和联合观察，甚至为所有agent设计策略。(Hansen et al., 2004; Oliehoek and Amato, 2014; Lowe et al., 2017; Foerster et al., 2017; Gupta et al., 2017; Foerster et al., 2018; Dibangoye and Buffet, 2018; Chen et al., 2018; Rashid et al., 2018)。这种结构催生了流行的集中学习，分散执行 centralized-learning-decentralized-execution 的学习方案，该方案源于为部分观察的环境进行规划的工作，即Dec-POMDP。然而，通常这种中央控制器在许多应用中并不存在，除了那些可以轻松访问模拟器的应用之外，例如 video games 和 robotics。
完全去中心 MARL：为了解决独立学习中的收敛问题，通常允许agents通过通信网络与邻居交换/共享本地信息。(Kar et al., 2013; Macua et al., 2015, 2017; Zhang et al., 2018,a,b; Lee et al., 2018; Wai et al., 2018; Doan et al., 2019; Suttle et al., 2019; Doan et al., 2019; Lin et al., 2019)。我们将此设置称为 a decentralized one with networked agents。这样一来，就可以在这种情况下进行收敛的理论分析，其难度介于 SARL 和通用MARL算法之间。

4 MARL Algorithms with Theory

本文仅聚焦 Cooperative Setting 的情况下的详细理论，如果想了解 Competitive Setting 和 Mixed Setting，可以自行阅读标题下的链接。由于 Homogeneous Cooperative Agent 的情况过于 naive，本文就不提了，我比较感兴趣的是Decentralized Paradigm with Networked Agents，这也是最符合实际的模型。

Decentralized Paradigm with Networked Agents

在许多实际的multi-agent系统中，coorperative agents 并不总是同质的。
Agents可能有不同的偏好，即奖励函数，这时要让团队的平均回报最大化。有时奖励函数不能与其他 agents 共享，因为每个 agent 的偏好都是独立的。

这种设定常出现于诸如传感器网络（Rabbat和Nowak，2004），智能电网（Dall'Anese等，2013；Zhang等，2018a），智能交通系统（Adler和Blue，2002）和机器人技术（Corke等人，2005）等场景。

如果使用 central controller 的方式，上述大多数MARL算法都可直接适用，因为 central controller 可以收集平均奖励，并将信息分发给所有 agents。但是由于成本、可扩展性或健壮性方面的考虑，在大多数上述应用中可能都不存在这种控制器（Rabbat和Nowak，2004；Dall’Anese等，2013；Zhang等，2019）。
取而代之的是，agents 可以通过随时间变化且稀疏的通信网络与邻居共享/交换信息。

Learning Optimal Policy

如何仅通过网络访问本地和邻近信息来达到最优的联合策略。具有网络 agents 的MARL 想法可以追溯到Varshavskaya et al.（2009）。第一个可证明收敛的MARL算法是Kar等人提出的（2013），将 consensus + innovation 的思想纳入标准的Q学习算法，产生了具有以下更新的 _QD-learning_ 算法

Q-learning 相比，QD-learning 在步长上增加了 innovation 项，该项捕捉了来自其邻居的Q估计值的差异。With certian conditions on the stepsizes, 算法可以保证收敛到表格形式下的最优 Q 函数。

请注意，上述收敛保证都是渐近的，即算法随着迭代次数达到无穷大而收敛，并且仅限于线性函数近似的情况。当使用有限迭代和/或样本时，这无法量化性能，更不用说在利用诸如 DNN 之类的非线性函数时了。

当考虑更通用的函数逼近进行有限样本分析时，详见 Finite-sample analyses for fully decentralized multi-agent reinforcement learning 和 Batch reinforcement learning 的 batch RL 算法，特别是 the fitted-Q iteration (FQI) 的去中心化变体。

我们研究了FQI变体，既用于与网络代理的协作环境，也用于与两个团队的网络代理的竞争环境。在前一种设定中，所有智能体都通过将非线性最小二乘法与目标值拟合来迭代更新全局Q函数估计。

另一个问题：由于是对分布式系统进行有限次迭代，agents之间可能无法达成共识，导致了对最优 Q 值的估计偏离了实际值。我们可以根据源于 single-agent batch RL 的 error propagation 分析，建立所提出算法的有限样本下的性能评估。例如，算法输出的精度多大程度取决于函数F、每次迭代 n 内的样本数以及 t 的迭代数。

5 Conclusions and Future Directions

Partially observed settings

在许多实际的MARL应用程序中，系统状态和其他agent的行为的部分可观察性是典型且不可避免的。通常，可以将这些设置建模为 partially observed stochastic game (POSG)，在特殊情况下，该游戏包括具有 common reward function 的协作设定，即Dec-POMDP模型。然而，即使合作任务也是 NEXP-hard（Bernstein等，2002），难以解决。

实际上，与只需要相信状态的POMDPs相比，POSG中用于最佳决策的信息状态可能会非常复杂，并且涉及 belief generation over the opponents’ policies（Hansen等人，2004年）。
这种困难主要源于从模型中获得的自身观察结果所导致的agent异质性，这是第3节中提到的MARL固有的挑战，原因是信息结构多种多样。有可能首先将解决Dec-POMDP的 centralized-learning-decentralized-execution 方案（Amato和Oliehoek，2015; Dibangoye和Buffet，2018）推广到解决POSGs。

Deep MARL theory

使用DNN进行函数逼近可以解决MARL中的可伸缩性问题。实际上，最近在MARL中获得的大部分经验成功都来自DNN的使用（Heinrich和Silver，2016; Lowe等人，2017; Foerster等人，2017; Gupta等人，2017; Omidshafiei等人，2017）。但是，由于缺乏理论支持，我们在本章中没有包括这些算法的详细信息。最近，人们做出了一些尝试来理解几种 single agent DRL 算法的全局收敛性，例如 neural TD learning（Cai等，2019）和 neural policy optimization（Wang等，2019; Liu等2019年）。因此，有望将这些结果扩展到多智能体设定，作为迈向对DMARL的理论理解的第一步。

Model-based MARL

文献中很少有基于模型的MARL算法。据我们所知，目前仅有的基于模型的MARL算法包括Brafman和Tennenholtz（2000）中的早期算法，它解决了单控制器随机游戏，一种特殊的 zero-sum MG。后来在Brafman和Tennenholtz（2002）中对zero-sum MG进行了改进，名为R-MAX。这些算法也建立在面对不确定性时的 principle of optimism 上（Auer和Ortner，2007；Jaksch等，2010），就像前面提到的几种无模型的算法一样。考虑到基于模型的RL的最新进展，尤其是在某些情况下其优于无模型的RL的可证明优势（Tu and Recht，2018; Sun等，2019），有必要将这些结果推广到MARL以改进其 sample efficiency。

Convergence of policy gradient methods

一般MARL中的 vanilla PG 的收敛结果大部分为负，即在许多情况下甚至会避开本地NE点，这本质上与MARL中的非平稳性挑战有关。尽管已经提出了一些补救措施（Balduzzi等人，2018; Letcher等人，2019; Chasnov等人，2019; Fiez等人，2019）来稳定 general continuous games 的收敛性，但这些假设是即使在最简单的LQ设置中，也不容易在MARL中进行验证/满足（Mazumdar等人，2019），因为它们不仅取决于模型，而且还取决于策略参数化。由于这种微妙之处，探索基于策略的MARL方法的（全局）收敛可能很有趣，可能始于简单的LQ设置（即一般和LQ游戏），类似于 zero-sum counterpart 博弈。

MARL with robustness/safety concerns

考虑到多智能体会有不唯一的学习目标，我们认为在MARL中考虑稳健性和/或安全性约束是很有意义的。据我们所知，这仍然是一个相对未知的领域。实际上，safe RL已被认为是 single agent 中最重大的挑战之一（Garcia和Fernandez，2015）。由于可能存在多个目标冲突的代理，因此安全性变得更加重要，安全要求让我们必须考虑智能体间的的耦合。一种简单的模型是 constrained multi-agent MDPs/Markov games，其约束条件表征了安全性要求。在这种情况下，具有可证明的安全保证的学习并非易事，但对于一些对安全性至关重要的MARL应用（如自动驾驶（Shalev-Shwartz等，2016）和机器人技术（Kober等，2013））是必需的。

此外，当然也要考虑对抗对手的鲁棒性，特别是在分散/分布式合作MARL环境中，如Zhang等人所述 Zhang et al. (2018); Chen et al. (2018); Wai et al. (2018)。在这种情况下，对手可能以匿名方式干扰学习过程-这是分布式系统中的常见情况。在这种情况下，针对 Byzantine adversaries 的鲁棒分布式监督学习的最新发展 (Chen et al., 2017; Yin et al., 2018) 可能是有用的。

知乎地址：https://zhuanlan.zhihu.com/p/220581474

推荐阅读