Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms

发表时间: 2019-11 · arXiv:1911.10635 (UIUC & Princeton)

原文: https://arxiv.org/abs/1911.10635

多智能体强化学习：理论与算法选择性综述
作者/机构: Kaiqing Zhang, Zhuoran Yang, Tamer Bas¸ar

A1 主要贡献（总结）

本文旨在对多智能体强化学习（MARL）领域提供一个选择性的综生，重点关注那些有理论分析支持的算法。近年来，强化学习（RL）在解决各种序列决策问题上取得了巨大成功，尤其是在围棋、扑克、机器人和自动驾驶等涉及多个智能体参与的场景中，这些场景自然地属于MARL的范畴。尽管MARL在经验上取得了成功，但其理论基础在文献中相对缺乏。

本文的核心贡献和研究目标如下：
1. 框架聚焦：主要关注两个代表性的MARL框架——马尔可夫/随机博弈（Markov/stochastic games）和扩展形式博弈（extensive-form games），这两种框架分别适用于不同类型的任务。
2. 任务分类：根据所处理任务的类型，将MARL算法分为三类进行回顾：
* 完全合作（fully cooperative）：所有智能体协同优化一个共同的长期回报。
* 完全竞争（fully competitive）：智能体的回报通常为零和。
* 混合型（mixed）：同时包含合作与竞争关系，回报为一般和（general-sum）。

1. 理论保证：重点回顾和关注那些具有收敛性和复杂度分析的MARL算法，其中大部分是近期的研究成果。
2. 新视角与分类法：本文提出并强调了现有MARL综述中相对较少探讨的几个新视角和分类法，这些视角部分源于作者自身的研究工作和兴趣：
   • 在MARL中讨论扩展形式博弈框架，作为对传统马尔可夫博弈框架的补充。
   • 总结了近期兴起的一个子领域：带网络连接的分布式MARL（decentralized MARL with networked agents）。
   • 将平均场（mean-field）机制引入MARL，作为处理大规模智能体群体的解决方案。
   • 强调了优化理论的最新进展，这些进展为MARL中基于策略的方法（尤其是在零和博弈中）的（非）收敛性问题提供了新的见解。
   • 回顾了部分在部分可观测设置下，未使用深度强化学习作为启发式解法的文献。

本文的目标不仅是评估该领域的现状，更重要的是为MARL的理论研究确定富有成效的未来研究方向，并激励更多研究者投身于这个充满挑战的领域。

A3 背景知识（缩写）

2.1 单智能体强化学习

强化学习智能体模型。强化学习智能体通过与环境互动来进行序列决策。环境通常被建模为一个无限时间范围的折扣马尔可夫决策过程（MDP），其形式化定义如下。

马尔可夫决策过程定义。一个马尔可夫决策过程由一个元组（S, A, P, R, γ）定义，其中S和A分别表示状态空间和动作空间；P : S × A → ∆(S)表示在给定任意状态s ∈ S和动作a ∈ A的情况下，到任意状态s' ∈ S的转移概率；R : S × A × S → R是奖励函数，决定了从(s, a)转移到s'时智能体收到的即时奖励；γ ∈ [0, 1)是折扣因子，用于权衡即时奖励和未来奖励。

MDP求解目标。作为一种标准模型，MDP被广泛用于描述对系统状态s具有完全可观测性的智能体的决策过程。在每个时间t，智能体面对系统状态st选择执行一个动作at，这导致系统转移到st+1 ∼ P(· | st, at)。此外，智能体收到一个即时奖励R(st, at, st+1)。解决MDP的目标是找到一个策略π : S → ∆(A)，即一个从状态空间S到动作空间A上分布的映射，使得at ∼ π(· | st)并且折扣累积奖励

被最大化。相应地，可以定义策略π下的动作价值函数（Q函数）和状态价值函数（V函数）为

对于任意s ∈ S和a ∈ A，它们分别是从(s0, a0) = (s, a)和s0 = s开始的折扣累积奖励。对应于最优策略π*的那些通常被称为最优Q函数和最优状态价值函数。

动态规划方法与强化学习。借助马尔可夫性质，最优策略可以通过动态规划/后向归纳方法获得，例如价值迭代和策略迭代算法【47, Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. 1. Athena Scientific Belmont, MA (2005)】，这些方法需要模型的知识，即转移概率和奖励函数的形式。而强化学习则是在不知道模型的情况下找到这样的最优策略。RL智能体通过与环境互动收集的经验来学习策略。大体上，RL算法可以分为两种主流类型，即基于价值的方法和基于策略的方法。

2.1.1 基于价值的方法

价值方法核心思想。基于价值的RL方法旨在找到状态-动作价值函数的一个良好估计，即最优Q函数$Q^{\pi^*}$。然后可以通过对Q函数估计采取贪婪动作来提取（近似）最优策略。最流行的基于价值的算法之一是Q学习【48, Watkins, C.J., Dayan, P.: Q-learning. Machine Learning 8(3-4), 279–292 (1992)】，其中智能体维护一个Q值函数的估计$\hat{Q}(s, a)$。当从状态-动作对(s, a)转移到下一个状态s'时，智能体收到一个回报r并根据以下方式更新Q函数：

其中α > 0是步长/学习率。在对α的某些条件下，可以证明Q学习几乎必然收敛到最优Q值函数【48, Watkins, C.J., Dayan, P.: Q-learning. Machine Learning 8(3-4), 279–292 (1992)】,【49, Szepesvari, C., Littman, M.L.: A unified analysis of value-function-based reinforcement- ´ learning algorithms. Neural Computation 11(8), 2017–2060 (1999)】，在有限状态和动作空间的情况下。此外，当与神经网络结合进行函数逼近时，深度Q学习在人类水平的控制应用中取得了巨大的经验性突破【10, Mnih, V., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)】。另一个流行的在线策略（on-policy）价值方法是SARSA，其收敛性在【50, Singh, S., et al.: Convergence results for single-step ´ on-policy reinforcement-learning algorithms. Machine Learning 38(3), 287–308 (2000)】中针对有限空间设置得到了证明。

蒙特卡洛树搜索（MCTS）。另一种流行且重要的基于价值的RL算法是蒙特卡洛树搜索（MCTS）【51, Chang, H.S., et al.: An adaptive sampling algorithm for solving Markov decision processes. Operations Research 53(1), 126–139 (2005)】,【52, Kocsis, L., Szepesvari, C.: Bandit based Monte-Carlo planning. In: European Conference on ´ Machine Learning, pp. 282–293. Springer (2006)】,【53, Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: International Conference on Computers and Games, pp. 72–83 (2006)】，它通过蒙特卡洛模拟构建搜索树来估计最优价值函数。树策略（tree policies）会明智地选择动作以平衡探索与利用，用于构建和更新搜索树。最常见的树策略是在树的每个节点上应用UCB1（UCB代表上置信界）算法，该算法最初是为随机多臂老虎机问题设计的【54, Agrawal, R.: Sample mean based index policies by O(logn) regret for the multi-armed bandit problem. Advances in Applied Probability 27(4), 1054–1078 (1995)】,【55, Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Machine Learning 47(2-3), 235–256 (2002)】，这产生了流行的UCT算法【52, Kocsis, L., Szepesvari, C.: Bandit based Monte-Carlo planning. In: European Conference on ´ Machine Learning, pp. 282–293. Springer (2006)】。关于MCTS非渐近收敛性的近期研究工作包括【56, Jiang, D., et al.: Feedback-based tree search for reinforcement learning. In: International Conference on Machine Learning, pp. 2284–2293 (2018)】和【57, Shah, D., Xie, Q., Xu, Z.: On reinforcement learning using Monte-Carlo tree search with supervised learning: Non-asymptotic analysis. arXiv preprint arXiv:1902.05213 (2019)】。

策略评估任务。此外，RL中关于价值函数的另一个重要任务是估计给定策略（不仅是最优策略）的价值函数。这个任务通常被称为策略评估，已通过遵循与(2.1)类似更新的算法来解决，命名为时间差分（TD）学习【58, Tesauro, G.: Temporal difference learning and TD-Gammon. Communications of the ACM 38(3), 58–68 (1995)】,【59, Tsitsiklis, J.N., Van Roy, B.: Analysis of temporal-diffference learning with function approximation. In: Advances in Neural Information Processing Systems, pp. 1075–1081 (1997)】,【60, Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press (2018)】。其他一些具有收敛保证的常见策略评估算法包括使用线性【61, Sutton, R.S., et al.: A convergent ´ O(n) algorithm for off-policy temporal-difference learning with linear function approximation. Advances in Neural Information Processing Systems 21(21), 1609–1616 (2008)】,【62, Sutton, R.S., et al.: Fast gradient-descent methods for temporal-difference learning with linear function approximation. In: International Conference on Machine Learning, pp. 993–1000 (2009)】,【63, Liu, B., et al.: Finite-sample analysis of proximal gradient TD algorithms. In: Conference on Uncertainty in Artificial Intelligence, pp. 504–513 (2015)】和非线性函数逼近【64, Bhatnagar, S., et al.: Convergent ´ temporal-difference learning with arbitrary smooth function approximation. In: Advances in Neural Information Processing Systems, pp. 1204–1212 (2009)】的梯度TD方法。有关策略评估的更详细综述，请参见【65, Dann, C., et al.: Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research 15, 809–883 (2014)】。

2.1.2 基于策略的方法

策略梯度方法。另一类RL算法直接在策略空间上搜索，该空间通常由参数化函数逼近器（如神经网络）估计，即$\pi(\cdot | s) \approx \pi_{\theta}(\cdot | s)$。因此，最直接的想法是沿着长期回报的梯度方向更新参数，这已通过策略梯度（PG）方法实现。作为该想法的关键前提，PG的闭式形式由【66, Sutton, R.S., et al.: Policy gradient methods for reinforcement learning with function approximation. In: Advances in Neural Information Processing Systems, pp. 1057–1063 (2000)】给出：

其中$J(\theta)$和$Q^{\pi}$分别是策略$\pi_{\theta}$下的期望回报和Q函数，$\nabla\log\pi_{\theta}(a|s)$是策略的得分函数，$\eta^{\pi_{\theta}}$是策略$\pi_{\theta}$下的状态占据度量，可以是折扣的或遍历的。然后，通过以不同方式估计梯度，提出了各种策略梯度方法，包括REINFORCE【67, Williams, R.J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8(3-4), 229–256 (1992)】、G(PO)MDP【68, Baxter, J., Bartlett, P.L.: Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research 15, 319–350 (2001)】和演员-评论家（actor-critic）算法【69, Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. In: Advances in Neural Information Processing Systems, pp. 1008–1014 (2000)】,【70, Bhatnagar, S., et al.: Natural actor-critic algorithms. Automatica 45(11), 2471–2482 (2009)】。类似的想法也适用于连续动作设置中的确定性策略，其PG形式最近由【71, Silver, D., et al.: Deterministic policy gradient algorithms. In: International Conference on Machine Learning, pp. 387–395 (2014)】导出。除了基于梯度的方法，其他一些策略优化方法也在许多应用中取得了最先进的性能，包括PPO【72, Schulman, J., et al.: Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)】、TRPO【73, Schulman, J., et al.: Trust region policy optimization. In: International Conference on Machine Learning, pp. 1889–1897 (2015)】、软演员-评论家【74, Haarnoja, T., et al.: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.01290 (2018)】。

与价值方法对比及其他方法。与基于价值的RL方法相比，基于策略的方法享有更好的收敛保证【69, Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. In: Advances in Neural Information Processing Systems, pp. 1008–1014 (2000)】,【75, Yang, Z., et al.: A finite sample analysis of the actor-critic algorithm. In: IEEE Conference on Decision and Control, pp. 2759–2764 (2018)】,【76, Zhang, K., et al.: Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprint arXiv:1906.08383 (2019)】,【77, Agarwal, A., et al.: Optimality and approximation with policy gradient methods in Markov decision processes. arXiv preprint arXiv:1908.00261 (2019)】，尤其是在使用神经网络进行函数逼近时【78, Liu, B., et al.: Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv:1906.10306 (2019)】,【79, Wang, L., et al.: Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150 (2019)】，这可以轻松处理大规模甚至连续的状态-动作空间。除了基于价值和策略的方法，还存在基于MDP的线性规划公式的RL算法；参见近期的工作【80, Chen, Y., Wang, M.: Stochastic primal-dual methods and sample complexity of reinforcement learning. arXiv preprint arXiv:1612.02516 (2016)】,【81, Wang, M.: Primal-dual π learning: Sample complexity and sublinear run time for ergodic Markov decision problems. arXiv preprint arXiv:1710.06100 (2017)】。

2.2 多智能体强化学习框架

MARL问题概述。同样，多智能体强化学习也处理序列决策问题，但涉及多个智能体。特别是，系统状态的演化和每个智能体收到的奖励都受到所有智能体联合动作的影响。更有趣的是，每个智能体都有自己的长期回报需要优化，这个回报现在是所有其他智能体策略的函数。这种通用模型在实践中有着广泛的应用，详见§5对几个著名例子的详细回顾。

MARL理论框架。通常，MARL存在两个看似不同但密切相关的理论框架，即马尔可夫/随机博弈和扩展形式博弈，下面将介绍。不同框架下的系统演化如图1所示。

图1：马尔可夫决策过程、马尔可夫博弈和扩展形式博弈的系统演化示意图，它们分别对应于单智能体和多智能体RL的框架。具体来说，在(a)的MDP中，智能体在输出动作a后观察状态s并从系统中获得奖励r；在(b)的MG中，所有智能体在观察系统状态s并各自收到奖励ri后，同时选择动作ai；在(c)的双人扩展形式博弈中，智能体交替做出选择动作ai的决策，并在博弈结束时各自收到奖励ri(z)，其中z是终端历史。在不完美信息的情况下，玩家2不确定他/她在博弈中的位置，这使得信息集非单例。

2.2.1 马尔可夫/随机博弈

马尔可夫博弈（MGs）。MDP的一个直接推广，用于捕捉多个智能体交织在一起的模型是马尔可夫博弈（MGs），也称为随机博弈【82, Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences 39(10), 1095–1100 (1953)】。源于开创性工作【83, Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 157–163 (1994)】，MGs的框架在文献中长期用于开发MARL算法，详见§4。我们下面介绍其形式化定义。

马尔可夫博弈的定义。一个马尔可夫博弈由一个元组(N, S, {Ai}i∈N, P, {Ri}i∈N, γ)定义，其中N = {1, · · · , N}表示N > 1个智能体的集合，S表示所有智能体观察到的状态空间，Ai表示智能体i的动作空间。令A := A1 × · · · × AN，则P : S × A → ∆(S)表示从任意状态s ∈ S到任意状态s' ∈ S对于任意联合动作a ∈ A的转移概率；Ri : S × A × S → R是奖励函数，决定了从(s, a)到s'的转移中智能体i收到的即时奖励；γ ∈ [0, 1)是折扣因子。

智能体目标与价值函数。在时间t，每个智能体i ∈ N根据系统状态st执行一个动作ait。系统然后转移到状态st+1，并奖励每个智能体i Ri(st, at, st+1)。智能体i的目标是通过找到策略πi : S → ∆(Ai)来优化其自身的长期回报，使得ait ∼ πi(· | st)。因此，智能体i的价值函数V i : S → R成为联合策略π : S → ∆(A)的函数，定义为π(a | s) := Πi∈N πi(ai | s)。具体来说，对于任何联合策略π和状态s ∈ S，

其中-i表示N中除智能体i之外的所有智能体的索引。因此，MG的解概念与MDP的不同，因为每个智能体的最优性能不仅由其自身策略控制，还由博弈中所有其他玩家的选择控制。最常见的解概念，纳什均衡（NE），定义如下【85, Bas¸ar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, vol. 23. SIAM (1999)】,【84, Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer Science & Business Media (2012)】。

纳什均衡定义。马尔可夫博弈(N, S, {Ai}i∈N, P, {Ri}i∈N, γ)的一个纳什均衡是一个联合策略π = (π1,, · · ·, πN,)，使得对于任意s ∈ S和i ∈ N

纳什均衡描述了一个均衡点π，任何智能体都没有动机从中偏离。换句话说，对于任何智能体i ∈ N，策略πi,是π-i,的最佳响应。作为MARL的标准学习目标，NE对于有限空间、无限时间范围的折扣MGs总是存在【84, Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer Science & Business Media (2012)】，但通常不唯一。大多数MARL算法都旨在收敛到这样一个均衡点（如果存在的话）。

马尔可夫博弈的普适性。马尔可夫博弈的框架足够通用，可以涵盖下面总结的各种MARL设置。

合作设置。在完全合作的设置中，所有智能体通常共享一个共同的奖励函数，即R1 = R2 = · · · = RN = R。我们注意到，这个模型在AI社区中也被称为多智能体MDPs（MMDPs）【86, Boutilier, C.: Planning, learning and coordination in multi-agent decision processes. In: Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195–210 (1996)】,【87, Lauer, M., Riedmiller, M.: An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In: International Conference on Machine Learning (2000)】，在控制/博弈论社区中被称为马尔可夫团队/团队马尔可夫博弈【88, Yoshikawa, T.: Decomposition of dynamic team decision problems. IEEE Transactions on Automatic Control 23(4), 627–632 (1978)】,【89, Ho, Y.C.: Team decision theory and information structures. Proceedings of the IEEE 68(6), 644–654 (1980)】,【90, Wang, X., Sandholm, T.: Reinforcement learning to play an optimal Nash equilibrium in team Markov games. In: Advances in Neural Information Processing Systems, pp. 1603– 1610 (2003)】,【91, Mahajan, A.: Sequential decomposition of sequential dynamic teams: Applications to realtime communication and networked control systems. Ph.D. thesis, University of Michigan (2008)】。此外，从博弈论的角度来看，这种合作设置也可以被视为马尔可夫势博弈（Markov potential games）的一个特例【92, Gonzalez-S ´ anchez, D., Hern ´ andez-Lerma, O.: Discrete-Time Stochastic Control and Dy- ´ namic Potential Games: The Euler-Equation Approach. Springer Science & Business Media (2013)】,【22, Zazo, S., Macua, S.V., Sanchez-Fern ´ andez, M., Zazo, J.: Dynamic potential games with con- ´ straints: Fundamentals and applications in communications. IEEE Transactions on Signal Processing 64(14), 3806–3821 (2016)】,【93, Valcarcel Macua, S., Zazo, J., Zazo, S.: Learning parametric closed-loop policies for Markov potential games. In: International Conference on Learning Representations (2018)】，其势函数是共同的累积奖励。考虑到这个模型，价值函数和Q函数对所有智能体都是相同的，这使得单智能体RL算法，例如Q学习更新(2.1)，可以在所有智能体被协调为一个决策者时应用。合作的全局最优现在构成了博弈的一个纳什均衡。

团队平均奖励模型。除了共同奖励模型，另一个稍微更通用且新兴的合作MARL模型考虑团队平均奖励【94, Kar, S., Moura, J.M., Poor, H.V.: QD-learning: A collaborative distributed strategy for multiagent reinforcement learning through consensus + innovations. IEEE Transactions on Signal Processing 61(7), 1848–1862 (2013)】,【23, Zhang, K., et al.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning, pp. 5867–5876 (2018)】,【95, Doan, T., Maguluri, S., Romberg, J.: Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 1626–1635 (2019)】。具体来说，允许智能体有不同的奖励函数，这些函数可能对每个智能体是私有的，而合作的目标是优化对应于平均奖励R¯(s, a, s') := N⁻¹ · Σi∈N Ri(s, a, s')的长期回报，对于任何(s, a, s') ∈ S × A × S。平均奖励模型允许智能体之间有更多的异质性，并将上述模型作为特例包含在内。它还保护了智能体之间的隐私，并促进了分布式MARL算法的发展【94, Kar, S., Moura, J.M., Poor, H.V.: QD-learning: A collaborative distributed strategy for multiagent reinforcement learning through consensus + innovations. IEEE Transactions on Signal Processing 61(7), 1848–1862 (2013)】,【23, Zhang, K., et al.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning, pp. 5867–5876 (2018)】,【96, Wai, H.T., et al.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, pp. 9649–9660 (2018)】。这种异质性也使得将通信协议纳入MARL以及分析通信高效的MARL算法成为必要。

竞争设置。MARL中的完全竞争设置通常被建模为零和马尔可夫博弈，即对于任何(s, a, s')，Σi∈N Ri(s, a, s') = 0。为了便于算法分析和计算上的可处理性，大多数文献都集中在两个相互竞争的智能体上【83, Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 157–163 (1994)】，其中一个智能体的奖励恰好是另一个智能体的损失。除了直接应用于博弈【83, Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 157–163 (1994)】,【2, Silver, D., et al.: Mastering the game of Go without human knowledge. Nature 550(7676), 354 (2017)】,【97, OpenAI: Openai dota 2 1v1 bot. https://openai.com/the-international/ (2017)】，零和博弈还作为鲁棒学习的模型，因为阻碍智能体学习过程的不确定性可以被看作是博弈中一个总是与智能体作对的虚拟对手【98, Jacobson, D.: Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games. IEEE Transactions on Automatic Control 18(2), 124–131 (1973)】,【99, Bas¸ar, T., Bernhard, P.: H∞ Optimal Control and Related Minimax Design Problems: A Dynamic Game Approach. Birkhauser, Boston. (1995) ¨】,【100, Zhang, K., Hu, B., Bas¸ar, T.: Policy optimization for H2 linear control with H∞ robustness guarantee: Implicit regularization and global convergence. arXiv preprint arXiv:1910.09496 (2019)】。因此，纳什均衡产生了一个优化最坏情况长期回报的鲁棒策略。

混合设置。混合设置也称为一般和博弈设置，其中对智能体之间的目标和关系没有限制【101, Hu, J., Wellman, M.P.: Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research 4(Nov), 1039–1069 (2003)】,【102, Littman, M.L.: Friend-or-Foe Q-learning in general-sum games. In: International Conference on Machine Learning, pp. 322–328 (2001)】。每个智能体都是自私的，其奖励可能与他人冲突。来自博弈论的均衡解概念，如纳什均衡【85, Bas¸ar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, vol. 23. SIAM (1999)】，对为这种通用设置开发的算法影响最大。此外，我们还包括了同时具有完全合作和竞争智能体的设置，例如，两个零和竞争团队，每个团队内部有合作智能体【103, Lagoudakis, M.G., Parr, R.: Learning in zero-sum team Markov games using factored value functions. In: Advances in Neural Information Processing Systems, pp. 1659–1666 (2003)】,【44, Zhang, K., et al.: Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02783 (2018)】,【3, OpenAI: Openai five. https://blog.openai.com/openai-five/ (2018)】，作为混合设置的实例。

2.2.2 扩展形式博弈

扩展形式博弈的适用性。尽管马尔可夫博弈是MARL的经典形式，但它们只能处理完全可观测的情况，即智能体在时间t对系统状态st和执行的动作at有完美的信息。然而，大量的MARL应用涉及只有部分可观测性的智能体，即博弈信息不完美。将马尔可夫博弈扩展到部分可观测情况是可行的，但即使在合作设置下解决起来也具有挑战性【36, Oliehoek, F.A., Amato, C.: A Concise Introduction to Decentralized POMDPs, vol. 1. Springer (2016)】,【104, Bernstein, D.S., et al.: The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research 27(4), 819–840 (2002)】。

扩展形式博弈框架。相比之下，另一个名为扩展形式博弈的框架【105, Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press (1994)】,【106, Shoham, Y., Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-theoretic, and Logical Foundations. Cambridge University Press (2008)】，可以方便地为多智能体决策建模不完美信息。这个框架根植于计算博弈论，并已证明在温和条件下存在多项式时间算法【107, Koller, D., Megiddo, N.: The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior 4(4), 528–552 (1992)】。我们简要介绍扩展形式博弈的框架如下。

扩展形式博弈的定义。一个扩展形式博弈由一个元组(N ∪ {c}, H, Z, A, {Ri}i∈N, τ, πc, S)定义，其中N = {1, . . . , N}表示N > 1个智能体的集合，c是一个称为“机会”或“自然”的特殊智能体，它有一个固定的随机策略，指定了环境的随机性。此外，A是智能体可以采取的所有可能动作的集合，H是所有可能历史的集合，每个历史都是从博弈开始时采取的一系列动作。令A(h) = {a | ha ∈ H}表示在非终端历史h之后可用的动作集合。假设一个智能体在历史h ∈ H下采取动作a ∈ A(h)，这会导致一个新的历史ha ∈ H。在所有历史中，Z ⊆ H是表示博弈完成的终端历史的子集。在终端历史处，每个智能体i ∈ N被分配一个效用，由函数Ri : Z → R决定。此外，τ : H → N ∪ {c}是指定在每个历史处哪个智能体采取行动的识别函数。如果τ(h) = c，机会智能体根据其策略πc采取一个动作a，即a ∼ πc(· | h)。此外，S是H的一个划分，使得对于任何s ∈ S和任何h, h' ∈ s，我们有τ(h) = τ(h')和A(h) = A(h')。换句话说，同一划分中的历史h和h'对于即将采取行动的智能体τ(h)来说是无法区分的。S中的元素被称为信息状态。

信息集与完美回忆。直观地，扩展形式博弈的不完美信息体现在智能体无法区分同一信息集中的历史。由于对于所有h, h' ∈ s和s ∈ S，我们有τ(h) = τ(h')和A(h) = A(h')，为了方便表示，在下文中，对于所有h ∈ s，我们让A(s)和τ(s)分别表示A(h)和τ(h)。我们还定义一个映射I : H → S，通过令I(h) = s如果h ∈ s。此外，我们只考虑H和A都是有限集的博弈。为了简化符号，对于任何两个历史h, h' ∈ H，如果h'可以通过从h采取一系列动作达到，我们称h为h'的前缀，记为h ≺ h'。在这种情况下，我们称h'为h的后缀。此外，我们始终假设博弈具有完美回忆，这意味着每个智能体都记得导致其当前信息状态的信息状态和动作序列。完美回忆的假设在文献中是常见的，它使得存在多项式时间算法来解决博弈【107, Koller, D., Megiddo, N.: The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior 4(4), 528–552 (1992)】。更重要的是，根据著名的库恩定理【108, Kuhn, H.: Extensive games and the problem op information. Contributions to the Theory of Games 2, 193–216 (1953)】，在这样的假设下，为了找到纳什均衡集，只需将推导限制在行为策略集上，这些策略将每个信息集s ∈ S映射到A(s)上的一个概率分布。对于任何i ∈ N，令Si = {s ∈ S : τ(s) = i}为智能体i的信息状态集。智能体的一个联合策略表示为π = (π1, . . . , πN)，其中πi : Si → ∆(A(s))是智能体i的策略。对于任何历史h和任何联合策略π，我们定义h在π下的到达概率为

它指定了当所有智能体都遵循π时h被创建的概率。我们类似地定义信息状态s在π下的到达概率为ηπ(s) = Σh∈s ηπ(h)。智能体i ∈ N的期望效用因此由Σz∈Z ηπ(z) · Ri(z)给出，为简单起见记为Ri(π)。现在我们准备介绍扩展形式博弈的解概念，即纳什均衡及其ε-近似，如下所示。

ε-纳什均衡定义。一个由(N ∪ {c}, H, Z, A, {Ri}i∈N, τ, πc, S)表示的扩展形式博弈的ε-纳什均衡是一个联合策略π = (π1,, · · ·, πN,)，使得对于任何i ∈ N，

这里π-i表示N \ {i}中智能体的联合策略，其中对于所有j ∈ N \ {i}，智能体j采用策略πj。此外，如果ε = 0，π构成一个纳什均衡。

不同设置。扩展形式博弈通常用于建模非合作设置。具体来说，效用为零和/常数和，即Σi∈N Ri = k（k为常数），对应于完全竞争设置；一般和效用函数导致混合设置。更重要的是，不同信息结构的设置也可以通过扩展形式博弈来表征。特别地，完美信息博弈是指每个信息集都是单例的博弈，即对于任何s ∈ S，|s| = 1；不完美信息博弈是指存在s ∈ S，|s| > 1的博弈。换句话说，在不完美信息下，用于决策的信息状态s代表了多个可能的历史，而智能体无法区分它们。

零和不完美信息博弈。在各种设置中，零和不完美信息设置一直是连接MARL和扩展形式博弈的理论研究的主要焦点【109, Zinkevich, M., et al.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729– 1736 (2008)】,【110, Heinrich, J., Lanctot, M., Silver, D.: Fictitious self-play in extensive-form games. In: International Conference on Machine Learning, pp. 805–813 (2015)】,【111, Srinivasan, S., et al.: Actor-critic policy optimization in partially observable multiagent environments. In: Advances in Neural Information Processing Systems, pp. 3422–3435 (2018)】,【112, Omidshafiei, S., et al.: Neural replicator dynamics. arXiv preprint arXiv:1906.00190 (2019)】。它也激发了MARL算法，这些算法彻底改变了像扑克AI这样的竞争设置应用【113, Rubin, J., Watson, I.: Computer Poker: A review. Artificial Intelligence 175(5-6), 958–987 (2011)】,【8, Brown, N., Sandholm, T.: Superhuman AI for multiplayer Poker. Science 365, 885–890 (2019)】。

与马尔可夫博弈的联系。需要注意的是，定义2.2和2.4中的两种形式是相互关联的。特别地，对于同时移动的马尔可夫博弈，其他智能体的动作选择对一个智能体是未知的，这导致了不同的历史，这些历史可以被聚合成一个信息状态s。这些博弈中的历史就是联合动作的序列，而折扣累积奖励实例化了博弈结束时的效用。反过来，通过简单地在状态s为智能体j ≠ τ(s)设置Aj = ∅，扩展形式博弈就简化为具有状态依赖动作空间的马尔可夫博弈。关于这种联系的更详细讨论，请参见【114, Lanctot, M., et al.: Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908.09453 (2019)】。

其他MARL框架。文献中还存在其他一些MARL的理论框架，例如，范式博弈和/或重复博弈【115, Claus, C., Boutilier, C.: The dynamics of reinforcement learning in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 1998(746-752), 2 (1998)】,【116, Bowling, M., Veloso, M.: Rational and convergent learning in stochastic games. In: International Joint Conference on Artificial Intelligence, vol. 17, pp. 1021–1026 (2001)】,【117, Kapetanakis, S., Kudenko, D.: Reinforcement learning of coordination in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 2002, 326–331 (2002)】,【118, Conitzer, V., Sandholm, T.: Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Machine Learning 67(1-2), 23–43 (2007)】，以及部分可观测马尔可夫博弈【119, Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI Conference on Artificial Intelligence, pp. 709–715 (2004)】,【120, Amato, C., et al.: Decentralized ¨ control of partially observable markov decision processes. In: IEEE Conference on Decision and Control, pp. 2398–2405 (2013)】,【121, Amato, C., Oliehoek, F.A.: Scalable planning and learning for multiagent POMDPs. In: AAAI Conference on Artificial Intelligence (2015)】。然而，前一个框架可以看作是MGs的一个特例，状态集为单点；该框架下早期的MARL理论大多局限于小规模问题【116, Bowling, M., Veloso, M.: Rational and convergent learning in stochastic games. In: International Joint Conference on Artificial Intelligence, vol. 17, pp. 1021–1026 (2001)】,【118, Conitzer, V., Sandholm, T.: Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Machine Learning 67(1-2), 23–43 (2007)】,【117, Kapetanakis, S., Kudenko, D.: Reinforcement learning of coordination in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 2002, 326–331 (2002)】。而后一个框架中的MARL，在一般情况下本质上是难以解决的【104, Bernstein, D.S., et al.: The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research 27(4), 819–840 (2002)】,【119, Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI Conference on Artificial Intelligence, pp. 709–715 (2004)】，导致文献中理论相对稀缺。由于篇幅限制，我们在此不详细介绍这些模型。不过，我们将在§4中简要回顾一些这些模型下的MARL算法，特别是部分可观测设置。感兴趣的读者可以参考早期的综述【11, Busoniu, L., et al.: A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C 38(2), 156–172 (2008)】，以获取关于范式/重复博弈中MARL的更多讨论。

3 MARL理论中的挑战

MARL理论分析的挑战。尽管MARL是一个应用广泛的通用模型，但除了单智能体RL中出现的挑战外，它在理论分析中还面临几个挑战。我们下面总结了我们认为在发展MARL理论方面具有根本性的挑战。

3.1 学习目标不唯一

学习目标的多维性和模糊性。与单智能体RL中智能体目标是有效最大化长期回报不同，MARL的学习目标有时可能很模糊。事实上，正如【122, Shoham, Y., Powers, R., Grenager, T.: Multi-agent reinforcement learning: A critical survey. Technical Report (2003)】所论证的，许多早期MARL工作中，所解决问题的模糊性是其根本缺陷。确实，在分析MARL算法时需要考虑的目标可以是多维的。最常见的目标，即收敛到§2.2中定义的纳什均衡，在【122】中受到了挑战。根据定义，NE描述了如果任何算法最终收敛，没有智能体会偏离的点。在假设智能体都是理性的，并且能够进行完美的推理和无限的相互建模的情况下，这无疑是博弈论中一个合理的解概念。然而，在有界理性的情况下，智能体可能只能进行有限的相互建模【106, Shoham, Y., Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-theoretic, and Logical Foundations. Cambridge University Press (2008)】。因此，为收敛到NE而设计的学习动态可能不适用于实际的MARL智能体。相反，目标可能集中在为给定智能体和博弈中其他智能体的固定类别设计最佳学习策略。事实上，这两个目标在【122】中被分别称为“均衡议程”和“AI议程”。

收敛性之外的性能标准。此外，收敛（到均衡点）作为MARL算法分析的主要性能标准也存在争议。事实上，【123, Zinkevich, M., Greenwald, A., Littman, M.L.: Cyclic equilibria in Markov games. In: Advances in Neural Information Processing Systems, pp. 1641–1648 (2006)】认识到基于价值的MARL算法未能收敛到一般和马尔可夫博弈的静态NE，这激发了其中新的解概念“循环均衡”，在该均衡点上，智能体在一组静态策略中僵化地循环，即不收敛到任何NE策略。另外，【116, Bowling, M., Veloso, M.: Rational and convergent learning in stochastic games. In: International Joint Conference on Artificial Intelligence, vol. 17, pp. 1021–1026 (2001)】,【124, Bowling, M., Veloso, M.: Multiagent learning using a variable learning rate. Artificial Intelligence 136(2), 215–250 (2002)】将学习目标分为稳定和理性两部分，前者确保算法在给定预定义的目标对手算法类别时收敛，后者要求在其他智能体保持静止时收敛到最佳响应。如果所有智能体既稳定又理性，那么在这种情况下自然会收敛到NE。此外，遗憾（regret）的概念引入了另一个角度来捕捉智能体的理性，它衡量算法与事后最佳静态策略的性能【116, Bowling, M., Veloso, M.: Rational and convergent learning in stochastic games. In: International Joint Conference on Artificial Intelligence, vol. 17, pp. 1021–1026 (2001)】,【125, Bowling, M.: Convergence and no-regret in multiagent learning. In: Advances in Neural Information Processing Systems, pp. 209–216 (2005)】,【126, Blum, A., Mansour, Y.: Learning, regret minimization, and equilibria. Algorithmic Game Theory pp. 79–102 (2007)】。具有渐近零平均遗憾的无遗憾算法保证了对某些博弈均衡的收敛【127, Hart, S., Mas-Colell, A.: A reinforcement procedure leading to correlated equilibrium. In: Economics Essays, pp. 181–200. Springer (2001)】,【125, Bowling, M.: Convergence and no-regret in multiagent learning. In: Advances in Neural Information Processing Systems, pp. 209–216 (2005)】,【109, Zinkevich, M., et al.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729– 1736 (2008)】，这本质上保证了智能体不被他人利用。

回报优化之外的目标。除了关于优化回报的目标，其他一些特定于多智能体系统的目标也引起了越来越多的关注。例如，【128, Kasai, T., et al.: Learning of communication codes in multi-agent reinforcement learning problem. In: IEEE Conference on Soft Computing in Industrial Applications, pp. 1–6 (2008)】,【21, Foerster, J., et al.: Learning to communicate with deep multi-agent reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 2137–2145 (2016)】,【129, Kim, D., et al.: Learning to schedule communication in multi-agent reinforcement learning. In: International Conference on Learning Representations (2019)】研究学习通信，以便智能体更好地协调。对通信协议的这种关注自然地激发了最近对通信高效MARL的研究【130, Chen, T., et al.: Communication-efficient distributed reinforcement learning. arXiv preprint arXiv:1812.03239 (2018)】,【131, Lin, Y., et al.: A communication-efficient multi-agent actor-critic algorithm for distributed reinforcement learning. In: IEEE Conference on Decision and Control (2019)】,【132, Ren, J., Haupt, J.: A communication efficient hierarchical distributed optimization algorithm for multi-agent reinforcement learning. In: Real-world Sequential Decision Making Workshop at International Conference on Machine Learning (2019)】,【133, Kim, W., Cho, M., Sung, Y.: Message-dropout: An efficient training method for multi-agent deep reinforcement learning. In: AAAI Conference on Artificial Intelligence (2019)】。其他重要的目标包括如何学习而不对某些智能体过拟合【134, He, H., et al.: Opponent modeling in deep reinforce- ´ ment learning. In: International Conference on Machine Learning, pp. 1804–1813 (2016)】,【26, Lowe, R., et al.: Multi-agent actor-critic for mixed cooperative-competitive environments. In: Advances in Neural Information Processing Systems, pp. 6379–6390 (2017)】,【135, Grover, A., et al.: Learning policy representations in multiagent systems. In: International Conference on Machine Learning, pp. 1802– 1811 (2018)】，以及如何与恶意/对抗性或失败/功能失调的学习智能体一起鲁棒地学习【136, Gao, C., Mueller, M., Hayward, R.: Adversarial policy gradient for alternating Markov games. In: Workshop at International Conference on Learning Representations (2018)】,【137, Li, S., et al.: Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In: AAAI Conference on Artificial Intelligence (2019)】,【138, Zhang, X., et al.: Non-cooperative inverse reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 9482–9493 (2019)】。一些关于上述目标的工作仍处于起步阶段，只提供经验结果，为理论研究留下了充足的空间。

3.2 非平稳性

非平稳性挑战。MARL的另一个关键挑战在于多个智能体通常同时学习，导致每个智能体所面临的环境都是非平稳的。具体来说，一个智能体采取的行动会影响其他对手智能体的奖励以及状态的演化。因此，学习中的智能体需要考虑其他智能体的行为方式，并相应地适应联合行为。这使得为建立单智能体RL算法收敛性而设定的平稳性假设失效，即环境的平稳马尔可夫性质（个体奖励和当前状态仅依赖于前一状态和所采取的行动）被打破。这排除了在MARL中直接使用单智能体RL分析的数学工具。

独立学习者的困境。事实上，从理论上讲，如果智能体忽略这个问题，并假设环境是平稳的来优化自己的策略，这种智能体通常被称为独立学习者，那么算法可能会无法收敛【139, Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: International Conference on Machine Learning, pp. 330–337 (1993)】,【115, Claus, C., Boutilier, C.: The dynamics of reinforcement learning in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 1998(746-752), 2 (1998)】，除了一些特殊情况【37, Arslan, G., Yuksel, S.: Decentralized Q-learning for stochastic teams and games. IEEE ¨ Transactions on Automatic Control 62(4), 1545–1558 (2017)】,【38, Yongacoglu, B., Arslan, G., Yuksel, S.: Learning team-optimality for decentralized stochas- ¨ tic control and dynamic games. arXiv preprint arXiv:1903.05812 (2019)】。然而，在经验上，独立学习在实践中可能会取得令人满意的表现【140, Matignon, L., Laurent, G.J., Le Fort-Piat, N.: Independent reinforcement learners in cooperative Markov games: A survey regarding coordination problems. The Knowledge Engineering Review 27(1), 1–31 (2012)】,【141, Foerster, J., et al.: Stabilising experience replay for deep multi-agent reinforcement learning. In: International Conference of Machine Learning, pp. 1146–1155 (2017)】。作为MARL中最著名的问题，非平稳性在文献中早已被认识到【11, Busoniu, L., et al.: A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C 38(2), 156–172 (2008)】,【142, Tuyls, K., Weiss, G.: Multiagent learning: Basics, challenges, and prospects. AI Magazine 33(3), 41–41 (2012)】。最近一篇全面的综述【40, Hernandez-Leal, P., et al.: A survey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprint arXiv:1707.09183 (2017)】专门概述了最先进的多智能体学习算法如何建模和解决这一问题。因此，我们不再进一步讨论这个挑战，并建议感兴趣的读者参考【40】。

3.3 可扩展性问题

组合性质。为了处理非平稳性，每个个体智能体可能需要考虑联合动作空间，其维度随智能体数量呈指数增长。这也被称为MARL的组合性质【20, Hernandez-Leal, P., Kartal, B., Taylor, M.E.: A survey and critique of multiagent deep reinforcement learning. arXiv preprint arXiv:1810.05587 (2018)】。大量的智能体使得MARL的理论分析，特别是收敛性分析变得复杂。这一论点得到了事实的支持，即双人零和设置的MARL理论比具有两个以上智能体的一般和设置的理论更为广泛和先进，详见§4的详细比较。解决可扩展性问题的一个可能方法是额外假设价值函数或奖励函数在动作依赖方面具有分解结构；参见【143, Guestrin, C., Lagoudakis, M., Parr, R.: Coordinated reinforcement learning. In: International Conference on Machine Learning, pp. 227–234 (2002)】,【144, Guestrin, C., Koller, D., Parr, R.: Multiagent planning with factored MDPs. In: Advances in Neural Information Processing Systems, pp. 1523–1530 (2002)】,【145, Kok, J.R., Vlassis, N.: Sparse cooperative Q-learning. In: International Conference on Machine learning, pp. 61–69 (2004)】的原始启发式思想，以及【146, Sunehag, P., et al.: Value-decomposition networks for cooperative multi-agent learning based on team reward. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 2085–2087 (2018)】,【147, Rashid, T., et al.: QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In: International Conference on Machine learning, pp. 681–689 (2018)】的近期经验进展。相关的理论分析直到最近才建立【148, Qu, G., Li, N.: Exploiting fast decaying and locality in multi-agent MDP with tree dependence structure. In: IEEE Conference on Decision and Control (2019)】，该工作考虑了一种特殊的依赖结构，并开发了一种可证明收敛的基于模型的算法。

深度MARL理论的挑战。MARL的另一个理论挑战，独立于但因可扩展性问题而恶化，是为深度多智能体RL建立理论。特别是，可扩展性问题使得在MARL中使用函数逼近，尤其是深度神经网络成为必要。尽管在经验上取得了成功，但深度MARL的理论分析几乎是一个未知的领域，这归因于目前对深度学习理论的理解有限，更不用说深度RL理论了。这被列为§6的未来研究方向之一。

3.4 多样的信息结构

信息结构复杂性。与单智能体情况相比，MARL的信息结构，即在训练和执行时谁知道什么，更为复杂。例如，在马尔可夫博弈的框架中，为了每个智能体做出决策，观察瞬时状态st就足够了，因为从S到∆(Ai)的局部策略πi包含了均衡策略。另一方面，对于扩展形式博弈，在常见的完美回忆假设下，每个智能体可能需要回忆过去决策的历史。此外，作为自利智能体，每个智能体几乎无法访问对手的策略或奖励，最多只能访问他们采取的动作样本。这种部分信息加剧了由非平稳性引起的问题，因为样本很难恢复对手底层策略的确切行为，从而增加了单个智能体所见的非平稳性。极端情况是前面提到的独立学习方案，它假设只可观测到局部动作和

图2：MARL中三种代表性的信息结构。具体来说，在(a)中，存在一个中央控制器，可以聚合来自智能体的信息，例如联合动作、联合奖励和联合观察，甚至为所有智能体设计策略。中央控制器和智能体之间交换的信息因此可以包括来自智能体的一些私有观察，以及控制器为每个智能体设计的局部策略。在(b)和(c)中，没有这样的中央控制器，因此都称为分布式结构。在(b)中，智能体通过一个可能随时间变化的通信网络连接，因此局部信息可以通过仅与每个智能体的邻居进行信息交换来在网络中传播。(b)在合作MARL设置中更常见。在(c)中，智能体是完全分布式的，彼此之间没有明确的信息交换。相反，每个智能体根据其局部观察做出决策，没有任何协调和/或数据聚合。然而，不同智能体的局部观察可能包含一些全局信息，例如，其他智能体的联合动作，即控制共享信息结构【149】。这种完全分布式的结构也可以在许多博弈论学习算法中找到。
奖励，并且通常不收敛【139, Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: International Conference on Machine Learning, pp. 330–337 (1993)】。

不同信息结构下的学习方案。由不同信息结构产生的学习方案为理论分析带来了不同程度的困难。具体来说，为了缓解上述的部分信息问题，大量工作假设存在一个中央控制器，可以收集联合动作、联合奖励和联合观察等信息，甚至为所有智能体设计策略【119, Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI Conference on Artificial Intelligence, pp. 709–715 (2004)】,【150, Oliehoek, F.A., Amato, C.: Dec-POMDPs as non-observable MDPs. IAS Technical Report (IAS-UVA-14-01) (2014)】,【26, Lowe, R., et al.: Multi-agent actor-critic for mixed cooperative-competitive environments. In: Advances in Neural Information Processing Systems, pp. 6379–6390 (2017)】,【141, Foerster, J., et al.: Stabilising experience replay for deep multi-agent reinforcement learning. In: International Conference of Machine Learning, pp. 1146–1155 (2017)】,【28, Gupta, J.K., Egorov, M., Kochenderfer, M.: Cooperative multi-agent control using deep reinforcement learning. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 66–83 (2017)】,【151, Foerster, J.N., et al.: Counterfactual multiagent policy gradients. In: AAAI Conference on Artificial Intelligence (2018)】,【152, Dibangoye, J., Buffet, O.: Learning to act in decentralized partially observable MDPs. In: International Conference on Machine Learning, pp. 1233–1242 (2018)】,【130, Chen, T., et al.: Communication-efficient distributed reinforcement learning. arXiv preprint arXiv:1812.03239 (2018)】,【147, Rashid, T., et al.: QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In: International Conference on Machine learning, pp. 681–689 (2018)】。这种结构催生了流行的“中心化学习-分布式执行”学习方案，该方案源于部分可观测设置的规划工作，即Dec-POMDPs【119, Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI Conference on Artificial Intelligence, pp. 709–715 (2004)】,【150, Oliehoek, F.A., Amato, C.: Dec-POMDPs as non-observable MDPs. IAS Technical Report (IAS-UVA-14-01) (2014)】,【153, Kraemer, L., Banerjee, B.: Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing 190, 82–94 (2016)】，并被最近的（深度）MARL工作广泛采用【26, Lowe, R., et al.: Multi-agent actor-critic for mixed cooperative-competitive environments. In: Advances in Neural Information Processing Systems, pp. 6379–6390 (2017)】,【141, Foerster, J., et al.: Stabilising experience replay for deep multi-agent reinforcement learning. In: International Conference of Machine Learning, pp. 1146–1155 (2017)】,【28, Gupta, J.K., Egorov, M., Kochenderfer, M.: Cooperative multi-agent control using deep reinforcement learning. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 66–83 (2017)】,【151, Foerster, J.N., et al.: Counterfactual multiagent policy gradients. In: AAAI Conference on Artificial Intelligence (2018)】,【130, Chen, T., et al.: Communication-efficient distributed reinforcement learning. arXiv preprint arXiv:1812.03239 (2018)】,【147, Rashid, T., et al.: QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In: International Conference on Machine learning, pp. 681–689 (2018)】。对于合作设置，这种学习方案极大地简化了分析，允许使用单智能体RL分析的工具。然而，对于具有异构智能体的非合作设置，这种方案并不能显著简化分析，因为智能体的学习目标不一致，见§3.1。

分布式学习方案。然而，通常在许多应用中，这样的中央控制器并不存在，除了那些可以轻松访问模拟器的应用，如视频游戏和机器人技术。因此，完全分布式的学习方案更受青睐，其中包括前面提到的独立学习方案作为特例。为了解决独立学习中的不收敛问题，通常允许智能体通过通信网络与其邻居交换/共享局部信息【94, Kar, S., Moura, J.M., Poor, H.V.: QD-learning: A collaborative distributed strategy for multiagent reinforcement learning through consensus + innovations. IEEE Transactions on Signal Processing 61(7), 1848–1862 (2013)】,【154, Macua, S.V., et al.: Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control 60(5), 1260–1274 (2015)】,【155, Macua, S.V., et al.: Di ´ ffdac: Distributed actor-critic for average multitask deep reinforcement learning. arXiv preprint arXiv:1710.10363 (2017)】,【23, Zhang, K., et al.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning, pp. 5867–5876 (2018)】,【43, Zhang, K., Yang, Z., Bas¸ar, T.: Networked multi-agent reinforcement learning in continuous spaces. In: IEEE Conference on Decision and Control, pp. 2771–2776 (2018)】,【44, Zhang, K., et al.: Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02783 (2018)】,【156, Lee, D., Yoon, H., Hovakimyan, N.: Primal-dual algorithm for distributed reinforcement learning: Distributed GTD. In: IEEE Conference on Decision and Control, pp. 1967–1972 (2018)】,【96, Wai, H.T., et al.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, pp. 9649–9660 (2018)】,【95, Doan, T., Maguluri, S., Romberg, J.: Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 1626–1635 (2019)】,【157, Doan, T.T., Maguluri, S.T., Romberg, J.: Finite-time performance of distributed temporal difference learning with linear function approximation. arXiv preprint arXiv:1907.12530 (2019)】,【158, Suttle, W., et al.: A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. arXiv preprint arXiv:1903.06372 (2019)】,【131, Lin, Y., et al.: A communication-efficient multi-agent actor-critic algorithm for distributed reinforcement learning. In: IEEE Conference on Decision and Control (2019)】。我们将这种设置称为带网络智能体的分布式设置。在这种设置下，收敛的理论分析成为可能，其难度介于单智能体RL和通用MARL算法之间。图2描绘了三种不同的信息结构。

A2 方法细节（缩写）

本节选择性地回顾MARL算法，并根据其要解决的任务进行分类。我们在此只回顾那些专注于理论研究的工作，这些工作大多建立在§2.2中介绍的两个代表性MARL框架之上：完全可观测的马尔可夫博弈和扩展形式博弈。由于合作设置下部分可观测马尔可夫博弈（即Dec-POMDP问题）的理论比一般部分可观测马尔可夫博弈的MARL理论更为成熟，我们也在§4.1中对其进行了简要总结。

4.1 合作设置

合作MARL构成了MARL设置的很大一部分，其中所有智能体相互协作以实现某些共同的目标。大多数有理论分析支持的合作MARL算法都是为以下更具体的设置设计的。

4.1.1 同质智能体

同质智能体的定义。大部分合作MARL设置涉及具有共同奖励函数的同质智能体，该函数使所有智能体的利益保持一致。在智能体数量庞大的极端情况下，这种同质性也表明智能体在系统演化中扮演着可互换的角色，几乎无法相互区分。下面我们详细阐述同质性。

多智能体MDP与马尔可夫团队。考虑一个如定义2.2中的马尔可夫博弈，其中R1 = R2 = · · · = RN = R，奖励R : S × A × S → R受联合动作A = A1 × ··· × AN的影响。因此，所有智能体的Q函数是相同的。因此，一个直接的算法是在每个智能体上执行标准的Q学习更新(2.1)，但在联合动作空间a' ∈ A上取最大值。当状态和动作空间都有限时，【49, Szepesvari, C., Littman, M.L.: A unified analysis of value-function-based reinforcement- ´ learning algorithms. Neural Computation 11(8), 2017–2060 (1999)】,【159, Littman, M.L.: Value-function reinforcement learning in Markov games. Cognitive Systems Research 2(1), 55–66 (2001)】已经证明了其能收敛到最优/均衡Q函数。

均衡策略收敛性问题。然而，Q函数的收敛并不必然意味着马尔可夫团队均衡策略的收敛，因为如果均衡策略不唯一，并且智能体未能就选择哪一个达成一致，那么在每个智能体处提取的任何均衡策略组合都可能不构成一个均衡策略。因此，只有在假设均衡是唯一的【159, Littman, M.L.: Value-function reinforcement learning in Markov games. Cognitive Systems Research 2(1), 55–66 (2001)】，或者智能体被协调进行均衡选择时，才能保证收敛到NE策略。后一个想法首先在合作重复博弈设置中得到验证【115, Claus, C., Boutilier, C.: The dynamics of reinforcement learning in cooperative multiagent systems. AAAI Conference on Artificial Intelligence 1998(746-752), 2 (1998)】，这是马尔可夫团队的一个特例，状态集为单点，其中智能体是联合动作学习者（JAL），为联合动作维护一个Q值，并学习所有其他智能体的经验模型。在【115】中声称收敛到均衡点，但没有正式证明。对于实际的马尔可夫团队，这种协调在【90, Wang, X., Sandholm, T.: Reinforcement learning to play an optimal Nash equilibrium in team Markov games. In: Advances in Neural Information Processing Systems, pp. 1603– 1610 (2003)】中得到了利用，该文提出了最优自适应学习（OAL），这是第一个可证明收敛到均衡策略的MARL算法。具体来说，OAL首先学习博弈结构，并在每个状态下构建虚拟博弈，这些博弈相对于一个有偏集合是弱无环的。通过引入受【160, Young, H.P.: The evolution of conventions. Econometrica: Journal of the Econometric Society pp. 57–84 (1993)】启发的有偏自适应博弈学习算法，可以证明OAL收敛到NE。

可扩展性与算法设计。除了均衡选择，马尔可夫团队（与单智能体RL相比）特有的另一个微妙之处是需要解决可扩展性问题，见§3.3。由于独立Q学习可能无法收敛【139, Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: International Conference on Machine Learning, pp. 330–337 (1993)】，早期为MMDPs开发可扩展且收敛的算法的尝试之一是【87, Lauer, M., Riedmiller, M.: An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In: International Conference on Machine Learning (2000)】，该文倡导一种分布式Q学习算法，该算法对于确定性有限MMDPs收敛。每个智能体只维护一个状态s和局部动作ai的Q表，并相继在联合动作a'上取最大化。每个个体智能体无法获取其他智能体的动作及其历史。关于奖励或价值函数分解的一些其他启发式方法（没有理论支持）已被提出来缓解可扩展性问题【143, Guestrin, C., Lagoudakis, M., Parr, R.: Coordinated reinforcement learning. In: International Conference on Machine Learning, pp. 227–234 (2002)】,【144, Guestrin, C., Koller, D., Parr, R.: Multiagent planning with factored MDPs. In: Advances in Neural Information Processing Systems, pp. 1523–1530 (2002)】,【145, Kok, J.R., Vlassis, N.: Sparse cooperative Q-learning. In: International Conference on Machine learning, pp. 61–69 (2004)】,【146, Sunehag, P., et al.: Value-decomposition networks for cooperative multi-agent learning based on team reward. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 2085–2087 (2018)】,【147, Rashid, T., et al.: QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In: International Conference on Machine learning, pp. 681–689 (2018)】。最近，【161, Son, K., et al.: QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 5887–5896 (2019)】为证明这种价值分解思想的合理性提供了严格的条件表征。该方向的另一个近期理论工作是【148, Qu, G., Li, N.: Exploiting fast decaying and locality in multi-agent MDP with tree dependence structure. In: IEEE Conference on Decision and Control (2019)】，它施加了一种特殊的依赖结构，即单向树，从而可以证明整体MMDP的（近）最优策略可以被局部策略很好地近似。最近，【38, Yongacoglu, B., Arslan, G., Yuksel, S.: Learning team-optimality for decentralized stochas- ¨ tic control and dynamic games. arXiv preprint arXiv:1903.05812 (2019)】研究了共同利益博弈，其中包括马尔可夫团队作为一个例子，并开发了一种仅依赖于状态、局部动作和奖励的分布式RL算法。与独立Q学习【139, Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: International Conference on Machine Learning, pp. 330–337 (1993)】具有相同的信息结构，该算法保证收敛到团队最优均衡策略，而不仅仅是均衡策略。这一点很重要，因为通常次优均衡的表现可能比最优均衡差得多【38】。

基于策略的方法。对于基于策略的方法，据我们所知，该设置下唯一的收敛保证存在于【162, Perolat, J., Piot, B., Pietquin, O.: Actor-critic fictitious play in simultaneous move multistage games. In: International Conference on Artificial Intelligence and Statistics (2018)】。作者提出了双时间尺度的演员-评论家虚拟博弈算法，其中在较慢的时间尺度上，演员将当前策略与相对于局部Q值估计的最佳响应策略混合，而在较快的时间尺度上，评论家执行策略评估，仿佛所有智能体的策略都是静止的。对于具有共同（也包括零和，见§4.2.2）奖励的同时移动多阶段博弈，建立了收敛性，这是一种具有初始和吸收状态，并且每个状态只被访问一次的特殊马尔可夫团队。

马尔可夫势博弈。从博弈论的角度来看，一个更通用的包含合作的框架是势博弈【163, Monderer, D., Shapley, L.S.: Potential games. Games and Economic Behavior 14(1), 124–143 (1996)】，其中存在一个所有智能体共享的势函数，使得如果任何智能体单方面改变其策略，其奖励的变化等于（或成比例于）势函数的变化。尽管大多数势博弈是无状态的，但一个名为马尔可夫势博弈（MPGs）的扩展在建模序列决策方面获得了越来越多的关注【92, Gonzalez-S ´ anchez, D., Hern ´ andez-Lerma, O.: Discrete-Time Stochastic Control and Dy- ´ namic Potential Games: The Euler-Equation Approach. Springer Science & Business Media (2013)】,【22, Zazo, S., Macua, S.V., Sanchez-Fern ´ andez, M., Zazo, J.: Dynamic potential games with con- ´ straints: Fundamentals and applications in communications. IEEE Transactions on Signal Processing 64(14), 3806–3821 (2016)】，它包括其演化受联合动作影响的马尔可夫状态。实际上，MMDPs/马尔可夫团队构成了MPGs的一个特例，其势函数是共同奖励；这种动态博弈也可以被看作是在策略上等价于马尔可夫团队，使用例如【164, Bas¸ar, T., Zaccour, G.: Handbook of Dynamic Game Theory. Springer (2018)】中的术语。在这个模型下，【93, Valcarcel Macua, S., Zazo, J., Zazo, S.: Learning parametric closed-loop policies for Markov potential games. In: International Conference on Learning Representations (2018)】为马尔可夫博弈成为MPG提供了可验证的条件，并显示了在MPG中寻找闭环NE与解决单智能体最优控制问题之间的等价性。因此，单智能体RL算法可以被用来解决这个MARL问题。

平均场机制。解决可扩展性问题的另一个思路是将设置带入平均场机制，即有大量同质智能体的场景。每个智能体对整个多智能体系统的影响因此可以变得无穷小，导致所有智能体都是可互换/无法区分的。然而，与其他智能体的互动仅通过一些平均场量来捕捉，例如平均状态或状态的经验分布。每个智能体只需要找到对平均场的最佳响应，这大大简化了分析。这种多智能体系统的平均场观点已通过平均场博弈（MFGs）模型【165, Huang, M., et al.: Individual and mass behaviour in large population ´ stochastic wireless power control problems: Centralized and Nash equilibrium solutions. In: IEEE Conference on Decision and Control, pp. 98–103 (2003)】,【166, Huang, M., et al.: Large population stochastic dynamic games: ´ Closed-loop Mckean-Vlasov systems and the Nash certainty equivalence principle. Communications in Information & Systems 6(3), 221–252 (2006)】,【167, Lasry, J.M., Lions, P.L.: Mean field games. Japanese Journal of Mathematics 2(1), 229–260 (2007)】,【168, Bensoussan, A., et al.: Mean Field Games and Mean Field Type Control Theory, vol. 101. Springer (2013)】,【169, Tembine, H., Zhu, Q., Bas¸ar, T.: Risk-sensitive mean-field games. IEEE Transactions on Automatic Control 59(4), 835–850 (2013)】、具有平均场共享的团队模型【170, Arabneydi, J., Mahajan, A.: Team optimal control of coupled subsystems with mean-field sharing. In: IEEE Conference on Decision and Control, pp. 1669–1674 (2014)】,【171, Arabneydi, J.: New concepts in team theory: Mean field teams and reinforcement learning. Ph.D. thesis, McGill University (2017)】以及具有平均场动作的博弈模型【172, Yang, Y., et al.: Mean field multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 5571–5580 (2018)】来处理。

平均场机制下的MARL。这些模型中的MARL直到最近才被探索，主要是在MFGs的非合作设置中，详见§4.3的更详细回顾。关于合作设置，最近的工作【175, Subramanian, J., Seraj, R., Mahajan, A.: Reinforcement learning for mean-field teams. In: Workshop on Adaptive and Learning Agents at International Conference on Autonomous Agents and Multi-Agent Systems (2018)】研究了具有平均场共享的马尔可夫团队的RL【170, Arabneydi, J., Mahajan, A.: Team optimal control of coupled subsystems with mean-field sharing. In: IEEE Conference on Decision and Control, pp. 1669–1674 (2014)】,【176, Arabneydi, J., Mahajan, A.: Linear quadratic mean field teams: Optimal and approximately optimal decentralized solutions. arXiv preprint arXiv:1609.00056 (2016)】,【171, Arabneydi, J.: New concepts in team theory: Mean field teams and reinforcement learning. Ph.D. thesis, McGill University (2017)】。与MFG相比，该模型考虑的智能体共享一个仅依赖于局部状态和平均场的共同奖励函数，这鼓励了智能体之间的合作。此外，术语“平均场”指的是有限群体的状态的经验平均，而不是MFG中无限群体的期望和概率分布。基于特定模型【170, Arabneydi, J., Mahajan, A.: Team optimal control of coupled subsystems with mean-field sharing. In: IEEE Conference on Decision and Control, pp. 1669–1674 (2014)】的动态规划分解，几种流行的RL算法可以轻松地转化为解决此设置【175】。最近，【177, Carmona, R., Lauriere, M., Tan, Z.: Linear-quadratic mean-field reinforcement learning: ` Convergence of policy gradient methods. arXiv preprint arXiv:1910.04295 (2019)】,【178, Carmona, R., Lauriere, M., Tan, Z.: Model-free mean-field reinforcement learning: Mean- ` field MDP and mean-field Q-learning. arXiv preprint arXiv:1910.12802 (2019)】从平均场控制（MFC）模型的角度来解决问题，以模拟大规模合作决策者。策略梯度方法被证明在【177】中对线性二次MFC收敛，然后平均场Q学习被证明在【178】中对一般MFC收敛。

4.1.2 带网络智能体的分布式范式

异构合作智能体。在许多实际的多智能体系统中，合作智能体并非总是同质的。智能体可能有不同的偏好，即奖励函数，但他们仍然组成一个团队来最大化团队平均奖励R¯的回报，其中R¯(s, a, s') = N⁻¹ · Σi∈N Ri(s, a, s')。更微妙的是，奖励函数有时不能与他人共享，因为偏好对每个智能体是私有的。这种设置在工程系统中有着广泛的应用，如传感器网络【179, Rabbat, M., Nowak, R.: Distributed optimization in sensor networks. In: International Symposium on Information Processing in Sensor Networks, pp. 20–27 (2004)】、智能电网【180, Dall’Anese, E., Zhu, H., Giannakis, G.B.: Distributed optimal power flow for smart microgrids. IEEE Transactions on Smart Grid 4(3), 1464–1475 (2013)】,【181, Zhang, K., et al.: Dynamic power distribution system management with a locally connected communication network. IEEE Journal of Selected Topics in Signal Processing 12(4), 673–687 (2018)】、智能交通系统【12, Adler, J.L., Blue, V.J.: A cooperative multi-agent transportation management and route guidance system. Transportation Research Part C: Emerging Technologies 10(5), 433–454 (2002)】,【182, Zhang, K., et al.: Dynamic operations and pricing of electric unmanned aerial vehicle systems and power networks. Transportation Research Part C: Emerging Technologies 92, 472–485 (2018)】和机器人技术【183, Corke, P., Peterson, R., Rus, D.: Networked robots: Flying robot navigation using a sensor net. Robotics Research pp. 234–243 (2005)】。

分布式范式。作为§4.1.1中同质设置的一个特例，指定的设置肯定需要更多的协调，例如，不知道其他智能体的奖励函数就无法在本地估计全局价值函数。在有中央控制器的情况下，§4.1.1中回顾的大多数MARL算法都直接适用，因为控制器可以收集和平均奖励，并将信息分发给所有智能体。然而，由于成本、可扩展性或鲁棒性等问题，这样的控制器在大多数上述应用中可能不存在【179, Rabbat, M., Nowak, R.: Distributed optimization in sensor networks. In: International Symposium on Information Processing in Sensor Networks, pp. 20–27 (2004)】,【180, Dall’Anese, E., Zhu, H., Giannakis, G.B.: Distributed optimal power flow for smart microgrids. IEEE Transactions on Smart Grid 4(3), 1464–1475 (2013)】,【184, Zhang, K., et al.: Distributed learning of average belief over networks using sequential observations. Automatica (2019)】。相反，智能体可能能够通过一个可能随时间变化且稀疏的通信网络与邻居交换/共享信息，如图2(b)所示。尽管在这种分布式范式下的MARL是必要的，但与解决静态/单阶段优化问题的分布式/共识算法的大量结果相比，它研究得相对较少【185, Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control 54(1), 48–61 (2009)】,【186, Agarwal, A., Duchi, J.C.: Distributed delayed stochastic optimization. In: Advances in Neural Information Processing Systems, pp. 873–881 (2011)】,【187, Jakovetic, D., Xavier, J., Moura, J.M.: Cooperative convex optimization in networked systems: Augmented lagrangian algorithms with directed gossip communication. IEEE Transactions on Signal Processing 59(8), 3889–3902 (2011)】,【188, Tu, S.Y., Sayed, A.H.: Diffusion strategies outperform consensus strategies for distributed estimation over adaptive networks. IEEE Transactions on Signal Processing 60(12), 6217– 6234 (2012)】，后者不像RL那样涉及系统动态，也不将长期目标作为序列决策问题来最大化。

学习最优策略。最重要的目标是学习最优联合策略，而每个智能体只能访问网络上的本地和邻近信息。带网络智能体的MARL思想可以追溯到【189, Varshavskaya, P., Kaelbling, L.P., Rus, D.: Efficient distributed reinforcement learning through agreement. In: Distributed Autonomous Robotic Systems, pp. 367–378 (2009)】。据我们所知，该设置下第一个可证明收敛的MARL算法来自【94, Kar, S., Moura, J.M., Poor, H.V.: QD-learning: A collaborative distributed strategy for multiagent reinforcement learning through consensus + innovations. IEEE Transactions on Signal Processing 61(7), 1848–1862 (2013)】，它将共识+创新的思想融入标准Q学习算法，产生了QD学习算法，更新规则如下：

其中αt,s,a, βt,s,a > 0是步长，$N_i^t$表示在时间t智能体i的邻居集合。与Q学习更新(2.1)相比，QD学习增加了一个创新项，该项捕捉了其邻居Q值估计的差异。在步长满足某些条件下，该算法保证在表格设置下收敛到最优Q函数。

基于策略的分布式算法。由于可扩展性问题，函数逼近在MARL中至关重要，这需要发展基于策略的算法。我们的工作【23, Zhang, K., et al.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning, pp. 5867–5876 (2018)】为此设置提出了演员-评论家算法。具体来说，每个智能体用参数$θ_i ∈ R^{m_i}$参数化自己的策略$\pi_i(\theta_i) : S → ∆(A_i)$，回报的策略梯度首先被推导为

其中Q是联合策略π下对应于R¯的全局价值函数，定义为$π_θ(a | s) := Π_{i∈N} \pi_i(\theta_i)(a_i | s)$。与(2.2)类似，(4.1)中的策略梯度涉及局部得分函数$∇_{θ_i} \log \pi_i(\theta_i)(s, a_i)$与全局Q函数$Q^θ$的乘积的期望。然而，后者无法在每个智能体处单独估计。因此，通过将$Q^θ(·, ·)$的每个局部副本参数化为智能体i的$Q^θ(·, ·; ω_i)$，我们提出了以下基于共识的TD学习用于评论家步骤，即估计$Q^θ(·, ·)$：

其中β > 0是步长，δi是使用$Q(·, ·; ω_i)$计算的局部TD误差。在(4.2)中的第一个关系执行标准的TD更新，然后是邻居估计$ω_j^t$的加权组合。这里的权重$c_t(i, j)$由通信网络的拓扑结构决定，只有当两个智能体i和j在时间t连接时才为非零值。它们还需要在期望上满足双随机性质，以便$ω_i^t$在收敛时对所有i ∈ N达到一个共识值。然后，每个智能体i在演员步骤中，使用其自己的Q函数估计$Q^θ(·, ·; ω_i^t)$，遵循(4.1)给出的随机策略梯度来更新其策略。在【23】中还介绍了一种变体算法，它不依赖于Q函数，而是依赖于状态价值函数逼近来估计全局优势函数。

分布式算法的收敛性与扩展。考虑到这些，当使用线性函数进行价值函数逼近时，【23, Zhang, K., et al.: Fully decentralized multi-agent reinforcement learning with networked agents. In: International Conference on Machine Learning, pp. 5867–5876 (2018)】为这些分布式演员-评论家算法建立了几乎必然收敛性。类似的思想也扩展到了连续空间设置【43, Zhang, K., Yang, Z., Bas¸ar, T.: Networked multi-agent reinforcement learning in continuous spaces. In: IEEE Conference on Decision and Control, pp. 2771–2776 (2018)】，其中通常使用确定性策略梯度（DPG）方法。DPG需要离策略探索，即一个随机的行为策略，因为确定性的在线策略可能探索性不足。然而，在多智能体设置中，由于其他智能体的策略未知，DPG的通用离策略方法【71, Silver, D., et al.: Deterministic policy gradient algorithms. In: International Conference on Machine Learning, pp. 387–395 (2014)】不适用。受统一了随机PG（SPG）和DPG的期望策略梯度（EPG）方法【190, Ciosek, K., Whiteson, S.: Expected policy gradients for reinforcement learning. arXiv preprint arXiv:1801.03326 (2018)】的启发，我们开发了一种保持在线策略但减少了一般SPG方差的算法【43】。具体来说，我们推导了EPG的多智能体版本，并在此基础上开发了可以以分布式方式实现的演员步骤，而评论家步骤仍然遵循(4.2)。当使用线性函数逼近时，该算法的收敛性也得到了建立【43】。同样，【158, Suttle, W., et al.: A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. arXiv preprint arXiv:1903.06372 (2019)】考虑了将【23】扩展到离策略设置，建立在评论家的强调时间差分（ETD）方法【191, Sutton, R.S., Mahmood, A.R., White, M.: An emphatic approach to the problem of offpolicy temporal-difference learning. Journal of Machine Learning Research 17(1), 2603– 2631 (2016)】之上。通过将ETD(λ)【192, Yu, H.: On convergence of emphatic temporal-difference learning. In: Conference on Learning Theory, pp. 1724–1751 (2015)】的分析纳入【23】，也建立了几乎必然的收敛保证。同时，【193, Zhang, Y., Zavlanos, M.M.: Distributed off-policy actor-critic reinforcement learning with policy consensus. arXiv preprint arXiv:1903.09255 (2019)】为相同设置提出了另一种离策略算法，其中智能体不共享其价值函数的估计。相反，智能体旨在就全局最优策略估计达成共识。该算法具有局部评论家和共识演员，也建立了可证明的收敛性。

多任务设置。除了多智能体设置外，分布式网络智能体的RL也在多任务设置中进行了研究。在某种意义上，前者可以被视为后者的简化版本，其中每个智能体处理一个不受其他智能体影响的独立MDP，而目标仍然是学习考虑所有智能体平均奖励的最优联合策略。【194, Pennesi, P., Paschalidis, I.C.: A distributed actor-critic algorithm and applications to mobile sensor network coordination problems. IEEE Transactions on Automatic Control 55(2), 492–497 (2010)】提出了一种分布式演员-评论家算法，假设状态、动作和奖励都是每个智能体的局部信息。每个智能体执行一个基于局部TD的评论家步骤，然后是一个基于共识的演员步骤，该步骤遵循使用从邻居交换的信息计算的梯度。平均回报的梯度被证明在迭代趋于无穷时收敛到零。【155, Macua, S.V., et al.: Di ´ ffdac: Distributed actor-critic for average multitask deep reinforcement learning. arXiv preprint arXiv:1710.10363 (2017)】为该设置开发了Diff-DAC，这是另一种分布式演员-评论家算法，源于对偶理论。其更新类似于【23】中的更新，但提供了额外的见解，即演员-评论家实际上是解决线性规划的对偶上升法的一个实例。

有限样本分析。请注意，所有上述收敛保证都是渐近的，即算法在迭代次数趋于无穷时收敛，并且仅限于使用线性函数逼近的情况。这未能量化使用有限迭代和/或样本时的性能，更不用说使用深度神经网络等非线性函数时。作为在该设置下进行更通用函数逼近的有限样本分析的初步步骤，我们在【44, Zhang, K., et al.: Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02783 (2018)】中考虑了批量RL算法【195, Lange, S., Gabel, T., Riedmiller, M.: Batch reinforcement learning. In: Reinforcement Learning, pp. 45–73. Springer (2012)】，特别是拟合Q迭代（FQI）【196, Riedmiller, M.: Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method. In: European Conference on Machine Learning, pp. 317–328 (2005)】,【197, Antos, A., Szepesvari, C., Munos, R.: Fitted Q-iteration in continuous action-space MDPs. ´ In: Advances in Neural Information Processing Systems, pp. 9–16 (2008)】的分布式变体。请注意，我们关注FQI，因为它在将深度神经网络用于函数逼近时，激发了著名的深度Q学习算法【10, Mnih, V., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)】。我们研究了FQI变体，用于合作设置（带网络智能体）和竞争设置（两队网络智能体，详见§4.2.1）。在前者中，所有智能体合作迭代更新全局Q函数估计，通过将目标值作为响应拟合非线性最小二乘。具体来说，令F为Q函数逼近的函数类，${(s_j, {a_{ij}}{i∈N}, s'_j)}}}$为所有智能体可用的n个批量转移数据集，${r_{ij{j∈[n]}$为每个智能体私有的局部奖励样本，$y Q_i^t(s'} = r_{ij} + γ · \max_{a∈Aj, a)$为局部目标值，其中$Q_i^t$是智能体i在迭代t时的Q函数估计。然后，所有智能体合作通过解决以下问题找到一个共同的Q函数估计：

由于$y_i$只为智能体i所知，(4.3)中的问题与【185, Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control 54(1), 48–61 (2009)】,【186, Agarwal, A., Duchi, J.C.: Distributed delayed stochastic optimization. In: Advances in Neural Information Processing Systems, pp. 873–881 (2011)】,【187, Jakovetic, D., Xavier, J., Moura, J.M.: Cooperative convex optimization in networked systems: Augmented lagrangian algorithms with directed gossip communication. IEEE Transactions on Signal Processing 59(8), 3889–3902 (2011)】,【188, Tu, S.Y., Sayed, A.H.: Diffusion strategies outperform consensus strategies for distributed estimation over adaptive networks. IEEE Transactions on Signal Processing 60(12), 6217– 6234 (2012)】,【198, Hong, M., Chang, T.H.: Stochastic proximal gradient consensus over random networks. IEEE Transactions on Signal Processing 65(11), 2933–2948 (2017)】,【199, Nedic, A., Olshevsky, A., Shi, W.: Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization 27(4), 2597–2633 (2017)】中的分布式/共识优化公式一致，如果F使得$Σ)]^2$对每个i是凸的，则其中的算法可以实现其全局最优解。如果F是线性函数类，情况确实如此。然而，仅通过有限次迭代的分布式优化算法（实践中常见），智能体可能无法达到精确共识，导致每个智能体的Q函数估计偏离(4.3)的实际最优值。当使用非线性函数逼近时，也存在这种误差。考虑到由分布式计算引起的这种误差，我们遵循源自单智能体批量RL【200, Munos, R.: Performance bounds in p-norm for approximate value iteration. SIAM Journal on Control and Optimization 46(2), 541–561 (2007)】,【201, Munos, R., Szepesvari, C.: Finite-time bounds for fitted value iteration. Journal of Machine ´ Learning Research 9(May), 815–857 (2008)】,【197, Antos, A., Szepesvari, C., Munos, R.: Fitted Q-iteration in continuous action-space MDPs. ´ In: Advances in Neural Information Processing Systems, pp. 9–16 (2008)】,【202, Antos, A., Szepesvari, C., Munos, R.: Learning near-optimal policies with Bellman-residual ´ minimization based fitted policy iteration and a single sample path. Machine Learning 71(1), 89–129 (2008)】,【203, Farahmand, A.m., Szepesvari, C., Munos, R.: Error propagation for approximate policy and ´ value iteration. In: Advances in Neural Information Processing Systems, pp. 568–576 (2010)】的误差传播分析，来建立所提出算法的有限样本性能，即算法输出的准确性如何依赖于函数类F、每次迭代内的样本数n和迭代次数t。}^n [y_{ij} - f(s_j, a_{1j}, · · ·, a_{Nj

策略评估。除了控制任务，该设置下的一系列算法仅关注策略评估任务，即演员-评论家算法的评论家步骤。当策略固定时，该任务具有更简洁的公式，因为采样分布变得平稳，且在线性函数逼近下目标变为凸。这促进了有限时间/样本分析，与大多数只有渐近保证的控制算法形成对比。具体来说，在联合策略π下，假设每个智能体用线性函数类${V_ω(s) := φ^T(s)ω : ω ∈ R^d}$参数化价值函数，其中$φ(s) ∈ R^d$是状态s的特征向量，$ω ∈ R^d$是参数向量。为方便表示，令$Φ := (· · · ; φ^T(s); · · · ) ∈ R^{|S|×d}$，$D = \text{diag}[{\eta^π(s)}{s∈S}] ∈ R^{|S|×|S|}$是由状态占据度量$η^π$构建的对角矩阵，$\bar{R}^π(s) = N^{-1} · Σ$，其(s, s')元素为$[P^π]} R_{i,π}(s)$，其中$R_{i,π}(s) = E_{a∼π(· | s),s'∼P(· | s,a)}[R_i(s, a, s')]$，以及$P^π ∈ R^{|S|×|S|{s,s'} = Σ π(a | s)P(s' | s, a)$。那么，所有智能体的目标是联合最小化与团队平均奖励相关的均方投影贝尔曼误差（MSPBE）：

其中$Π_Φ : R^{|S|} → R^{|S|}$定义为$Π_Φ := Φ(Φ^TDΦ)^{-1}Φ^TD$，是到子空间${Φω : ω ∈ R^d}$的投影算子，$A := E{φ(s)[φ(s) - γφ(s')]\^T}$，$C := E[φ(s)φ^T(s)]$，以及$b := E[\bar{R}^π(s)φ(s)]$。通过用样本替换期望并使用Fenchel对偶性，(4.4)的有限和版本可以重新表述为一个分布式鞍点问题：

其中n是数据大小，$A_j$, $C_j$和$b_i$分别是A, C和$b_i := E[R_{i,π}(s)φ(s)]$的经验估计，使用样本j。注意(4.5)在ω上是凸的，在${λ_i}_{i∈N}$上是凹的。使用MSPBE作为目标在多智能体策略评估中是标准的【154, Macua, S.V., et al.: Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control 60(5), 1260–1274 (2015)】,【156, Lee, D., Yoon, H., Hovakimyan, N.: Primal-dual algorithm for distributed reinforcement learning: Distributed GTD. In: IEEE Conference on Decision and Control, pp. 1967–1972 (2018)】,【96, Wai, H.T., et al.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, pp. 9649–9660 (2018)】,【95, Doan, T., Maguluri, S., Romberg, J.: Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 1626–1635 (2019)】,【157, Doan, T.T., Maguluri, S.T., Romberg, J.: Finite-time performance of distributed temporal difference learning with linear function approximation. arXiv preprint arXiv:1907.12530 (2019)】，而鞍点重构的思想已在【154, Macua, S.V., et al.: Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control 60(5), 1260–1274 (2015)】,【156, Lee, D., Yoon, H., Hovakimyan, N.: Primal-dual algorithm for distributed reinforcement learning: Distributed GTD. In: IEEE Conference on Decision and Control, pp. 1967–1972 (2018)】,【96, Wai, H.T., et al.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, pp. 9649–9660 (2018)】,【204, Cassano, L., Yuan, K., Sayed, A.H.: Multi-agent fully decentralized off-policy learning with linear convergence rates. arXiv preprint arXiv:1810.07792 (2018)】中采用。注意在【204】中，提倡使用MSPBE的一个变体，名为H-截断λ-加权MSPBE，以控制解偏离实际均方贝尔曼误差最小化器的偏差。

策略评估算法综述。考虑到(4.4)的公式，【156, Lee, D., Yoon, H., Hovakimyan, N.: Primal-dual algorithm for distributed reinforcement learning: Distributed GTD. In: IEEE Conference on Decision and Control, pp. 1967–1972 (2018)】开发了一种基于梯度TD的方法的分布式变体，并使用常微分方程（ODE）方法建立了渐近收敛性。在【96, Wai, H.T., et al.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, pp. 9649–9660 (2018)】中，提出了一种结合动态共识【205, Qu, G., Li, N.: Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems 5(3), 1245–1260 (2017)】和SAG算法【206, Schmidt, M., Le Roux, N., Bach, F.: Minimizing finite sums with the stochastic average gradient. Mathematical Programming 162(1-2), 83–112 (2017)】的双重平均方案，以线性速率解决鞍点问题(4.5)。【204, Cassano, L., Yuan, K., Sayed, A.H.: Multi-agent fully decentralized off-policy learning with linear convergence rates. arXiv preprint arXiv:1810.07792 (2018)】将方差缩减的思想，特别是【207, Ying, B., Yuan, K., Sayed, A.H.: Convergence of variance-reduced learning under random reshuffling. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 2286–2290 (2018)】中的AVRG，融入到基于梯度TD的策略评估中。该方法实现了与【96】相同的线性速率，并声称具有三个优点：i) 数据无关的内存需求；ii) 使用资格迹【208, Singh, S.P., Sutton, R.S.: Reinforcement learning with replacing eligibility traces. Machine Learning 22(1-3), 123–158 (1996)】；iii) 采样中无需同步。最近，标准的TD学习【58, Tesauro, G.: Temporal difference learning and TD-Gammon. Communications of the ACM 38(3), 58–68 (1995)】，而不是梯度TD，已被推广到这种MARL设置，特别关注有限样本分析【95, Doan, T., Maguluri, S., Romberg, J.: Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 1626–1635 (2019)】,【157, Doan, T.T., Maguluri, S.T., Romberg, J.: Finite-time performance of distributed temporal difference learning with linear function approximation. arXiv preprint arXiv:1907.12530 (2019)】。分布式TD(0)首先在【95】中研究，使用了源于【209, Bhandari, J., Russo, D., Singal, R.: A finite time analysis of temporal difference learning with linear function approximation. In: Conference On Learning Theory, pp. 1691–1692 (2018)】的证明技术，该技术需要在迭代上进行投影，并且数据样本需要是独立同分布（i.i.d.）的。此外，受【210, Srikant, R., Ying, L.: Finite-time error bounds for linear stochastic approximation and TD learning. In: Conference on Learning Theory, pp. 2803–2830 (2019)】的最新进展启发，【157】提供了更通用的分布式TD(λ)算法的有限时间性能，既不需要投影也不需要i.i.d.噪声假设。

独立智能体设置下的策略评估。网络化智能体的策略评估也在独立智能体与独立MDPs交互的设置下进行了研究。【154, Macua, S.V., et al.: Distributed policy evaluation under multiple behavior strategies. IEEE Transactions on Automatic Control 60(5), 1260–1274 (2015)】研究了基于重要性采样技术的离策略评估。由于MDPs之间没有耦合，智能体不需要知道其他智能体的动作。然后提出了基于扩散的分布式GTD，并证明了其在均方意义上以亚线性速率收敛。在【211, Stankovic, M.S., Stankovi ´ c, S.S.: Multi-agent temporal-di ´ fference learning with linear function approximation: Weak convergence under time-varying network topologies. In: IEEE American Control Conference, pp. 167–172 (2016)】中，设计了两种TD学习的变体，即GTD2和TDC【62, Sutton, R.S., et al.: Fast gradient-descent methods for temporal-difference learning with linear function approximation. In: International Conference on Machine Learning, pp. 993–1000 (2009)】，用于此设置，并通过【212, Stankovic, M.S., Ili ´ c, N., Stankovi ´ c, S.S.: Distributed stochastic approximation: Weak con- ´ vergence and network design. IEEE Transactions on Automatic Control 61(12), 4069–4074 (2016)】中的一般随机逼近理论证明了在智能体由时变通信网络连接时的弱收敛性。注意【204】也考虑了独立MDP设置，并建立了与实际MARL设置相同的结果。

其他学习目标。对于带网络智能体的分布式MARL，还探索了其他一些学习目标。【213, Zhang, H., et al.: Data-driven optimal consensus control for discretetime multi-agent systems with unknown dynamics using reinforcement learning method. IEEE Transactions on Industrial Electronics 64(5), 4091–4100 (2016)】考虑了最优共识问题，其中网络上的每个智能体跟踪其邻居以及一个领导者的状态，以便通过联合策略最小化共识误差。然后引入了一种策略迭代算法，随后是一种使用神经网络进行函数逼近的实用演员-评论家算法。在【214, Zhang, Q., Zhao, D., Lewis, F.L.: Model-free reinforcement learning for fully cooperative multi-agent graphical games. In: International Joint Conference on Neural Networks, pp. 1–6 (2018)】中也采用了类似的共识误差目标，称为合作多智能体图博弈。利用中心化评论家-分布式演员方案来开发离策略RL算法。

通信效率。作为该设置下算法设计的关键要素，通信效率最近引起了越来越多的关注【130, Chen, T., et al.: Communication-efficient distributed reinforcement learning. arXiv preprint arXiv:1812.03239 (2018)】,【132, Ren, J., Haupt, J.: A communication efficient hierarchical distributed optimization algorithm for multi-agent reinforcement learning. In: Real-world Sequential Decision Making Workshop at International Conference on Machine Learning (2019)】,【131, Lin, Y., et al.: A communication-efficient multi-agent actor-critic algorithm for distributed reinforcement learning. In: IEEE Conference on Decision and Control (2019)】。具体来说，【130】开发了懒惰聚合策略梯度（LAPG），一种分布式PG算法，可以通过明智地设计通信触发规则来减少智能体与中央控制器之间的通信轮次。【132】解决了与【96】相同的策略评估问题，并通过提出一种不同于【23】,【96】,【156】中使用的双随机矩阵的混合矩阵，开发了一种分层分布式算法，该算法允许智能体之间的单向信息交换以节省通信。相比之下，【131】中的分布式演员-评论家算法通过在每次迭代中仅传输其状态向量的一个标量条目来减少通信，同时保持了与【23】中一样的可证明收敛性。

4.1.3 部分可观测模型

部分可观测设置的挑战。我们通过简要介绍一类重要但具有挑战性的模型来完成对合作设置的概述，在这些模型中，智能体面临部分可观测性。尽管在实践中很常见，但与前面提到的完全可观测设置相比，该设置下MARL算法的理论分析仍然相对稀缺。通常，这种设置可以被建模为分布式POMDP（Dec-POMDP）【36, Oliehoek, F.A., Amato, C.: A Concise Introduction to Decentralized POMDPs, vol. 1. Springer (2016)】，它与MMDP/马尔可夫团队模型（§2.2.1）共享几乎所有元素，如奖励函数和转移模型，只是现在每个智能体只有对系统状态s的局部观测。由于无法访问其他智能体的观测，单个智能体无法维持一个全局信念状态，这是单智能体POMDP中决策的充分统计量。因此，已知Dec-POMDP是NEXP完备的【104, Bernstein, D.S., et al.: The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research 27(4), 819–840 (2002)】，在最坏情况下需要超指数时间来解决。

Dec-POMDP的规划/学习算法。开发Dec-POMDP的规划/学习算法的兴趣日益增加。大多数算法基于中心化学习-分布式执行方案。具体来说，分布式问题首先被重新表述为一个中心化问题，该问题可以在一个拥有所有智能体观测数据的中央控制器（或生成数据的模拟器）上解决。然后使用数据优化/学习策略，并分发给所有智能体执行。有限状态控制器（FSCs）通常用于表示每个智能体的局部策略【215, Bernstein, D.S., et al.: Policy iteration for decentralized control of Markov decision processes. Journal of Artificial Intelligence Research 34, 89–132 (2009)】,【216, Amato, C., Bernstein, D.S., Zilberstein, S.: Optimizing fixed-size stochastic controllers for POMDPs and decentralized POMDPs. Autonomous Agents and Multi-Agent Systems 21(3), 293–320 (2010)】，它将局部观测历史映射到动作。在【217, Liu, M., et al.: Stick-breaking policy learning in DecPOMDPs. In: International Joint Conference on Artificial Intelligence (2015)】中提出了一种贝叶斯非参数方法来确定可变大小FSC的控制器大小。为了有效解决中心化问题，提出了一系列自顶向下的算法。在【150, Oliehoek, F.A., Amato, C.: Dec-POMDPs as non-observable MDPs. IAS Technical Report (IAS-UVA-14-01) (2014)】中，Dec-POMDP被转换为不可观测MDP（NOMDP），这是一种中心化序列决策问题，然后通过一些启发式树搜索算法来解决。作为NOMDP转换的扩展，【218, Dibangoye, J.S., et al.: Optimally solving Dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research 55, 443–497 (2016)】,【152, Dibangoye, J., Buffet, O.: Learning to act in decentralized partially observable MDPs. In: International Conference on Machine Learning, pp. 1233–1242 (2018)】将Dec-POMDP转换为占据状态MDP（oMDP），其中占据状态是隐藏状态和观测联合历史的分布。由于oMDP的价值函数具有分段线性和凸性，因此开发了可处理的规划【218】和基于价值的学习【152】算法。

计算效率改进。为了进一步提高计算效率，还提出了一些基于采样的规划/学习算法。特别地，【219, Wu, F., Zilberstein, S., Chen, X.: Rollout sampling policy iteration for decentralized POMDPs. In: Conference on Uncertainty in Artificial Intelligence (2010)】和【220, Wu, F., Zilberstein, S., Jennings, N.R.: Monte-Carlo expectation maximization for decentralized POMDPs. In: International Joint Conference on Artificial Intelligence (2013)】分别提出了使用策略迭代的蒙特卡洛采样和期望最大化算法。此外，蒙特卡洛树搜索已应用于特殊类别的Dec-POMDP，例如多智能体POMDP【121, Amato, C., Oliehoek, F.A.: Scalable planning and learning for multiagent POMDPs. In: AAAI Conference on Artificial Intelligence (2015)】和多机器人主动感知【221, Best, G., et al.: Dec-MCTS: Decentralized planning for multi-robot active perception. International Journal of Robotics Research pp. 1–22 (2018)】。此外，基于策略梯度的算法也可以为这种中心化学习方案开发【152, Dibangoye, J., Buffet, O.: Learning to act in decentralized partially observable MDPs. In: International Conference on Machine Learning, pp. 1233–1242 (2018)】，具有中心化评论家和分布式演员。在这种方案下，也可以为具有有限状态-动作空间的表格设置建立有限样本分析【222, Amato, C., Zilberstein, S.: Achieving goals in decentralized POMDPs. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 593–600 (2009)】,【223, Banerjee, B., et al.: Sample bounded distributed reinforcement learning for decentralized POMDPs. In: AAAI Conference on Artificial Intelligence (2012)】。

Dec-POMDP的分布式学习。也进行了一些尝试以在Dec-POMDP中实现分布式学习。当智能体共享一些共同的信息/观测时，【224, Nayyar, A., Mahajan, A., Teneketzis, D.: Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions on Automatic Control 58(7), 1644–1658 (2013)】提出将问题重新表述为一个中心化的POMDP，其中共同信息是虚拟中央控制器的观测。这样，每个智能体可以单独解决这个中心化的POMDP。在【225, Arabneydi, J., Mahajan, A.: Reinforcement learning in decentralized stochastic control systems with partial history sharing. In: IEEE American Control Conference, pp. 5449–5456 (2015)】中，重新表述的POMDP被有限状态MDP以指数递减的逼近误差近似，然后通过Q学习解决。最近，【39, Zhang, K., Miehling, E., Bas¸ar, T.: Online planning for decentralized stochastic control with partial history sharing. In: IEEE American Control Conference, pp. 167–172 (2019)】开发了一种基于树搜索的算法来解决这个中心化的POMDP，有趣的是，这与直接解决Dec-POMDP的启发式方法【121, Amato, C., Oliehoek, F.A.: Scalable planning and learning for multiagent POMDPs. In: AAAI Conference on Artificial Intelligence (2015)】,【221, Best, G., et al.: Dec-MCTS: Decentralized planning for multi-robot active perception. International Journal of Robotics Research pp. 1–22 (2018)】相呼应，但具有更坚实的理论基础。注意，在【225】和【39】中，所有智能体都使用一个共同的随机数生成器，以避免智能体之间的通信并实现分布式学习方案。

4.2 竞争设置

竞争设置概述。竞争设置通常被建模为零和博弈。在计算上，解决双人零和博弈与多人零和博弈之间存在巨大的障碍。特别是，即使是最简单的三人矩阵博弈，也已知是PPAD完备的【226, Papadimitriou, C.H.: On inefficient proofs of existence and complexity classes. In: Annals of Discrete Mathematics, vol. 51, pp. 245–250. Elsevier (1992)】,【227, Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39(1), 195–259 (2009)】。因此，大多数关于竞争MARL的现有结果都集中在双人零和博弈上，即在定义2.2和2.4中N = {1, 2}且R1 + R2 = 0。在本节的其余部分，我们回顾了那些能够可证明地在双人马尔可夫或扩展形式博弈中找到纳什（等价于鞍点）均衡的方法。现有算法主要可分为两类：基于价值的方法和基于策略的方法，下面将分别介绍。

4.2.1 基于价值的方法

基于价值方法的核心思想。与单智能体MDP中类似，基于价值的方法旨在找到一个最优价值函数，从中可以提取出联合纳什均衡策略。此外，已知最优价值函数是贝尔曼算子的唯一不动点，可以通过动态规划类型的方法获得。

双人零和马尔可夫博弈的价值函数。具体来说，对于同时移动的马尔可夫博弈，(2.3)中定义的价值函数满足$V^{1,\pi_1,\pi_2} = -V^{2,\pi_1,\pi_2}$。因此，任何纳什均衡$\pi^ = (\pi_{1,}, \pi_{2,})$都满足

与范式/矩阵零和博弈中的极小极大定理【228, Von Neumann, J., Morgenstern, O., Kuhn, H.W.: Theory of Games and Economic Behavior (commemorative edition). Princeton University Press (2007)】类似，对于具有有限状态和动作空间的双人零和马尔可夫博弈，可以定义最优价值函数$V^ : S → R$为

那么(4.6)意味着$V^{1,\pi_{1,},\pi_{2,}}$与$V^$一致，任何达到(4.7)中上确界和下确界的策略对$\pi_1$和$\pi_2$都构成一个纳什均衡。此外，与MDP类似，【82, Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences 39(10), 1095–1100 (1953)】表明$V^$是贝尔曼方程的唯一解，并且可以基于$V^$构造纳什均衡。具体来说，对于任何$V : S → R$和任何$s ∈ S$，我们定义

其中$Q^V(s, ·, ·)$可以被看作是$R^{|A_1|×|A_2|}$中的一个矩阵。然后我们通过求解一个关于$Q^V(s, ·, ·)$作为收益矩阵的矩阵零和博弈来定义贝尔曼算子$T^$，即对于任何$s ∈ S$，可以定义

这里我们使用Value(·)来表示矩阵零和博弈的最优值，这可以通过求解一个线性规划【229, Vanderbei, R.J., et al.: Linear Programming. Springer (2015)】得到。因此，贝尔曼算子$T^$在∞-范数下是γ-压缩的，(4.7)中的V是贝尔曼方程$V = T^V$的唯一解。此外，令$p_1(V), p_2(V)$为(4.9)中优化问题的任意解，我们有$\pi^ = (p_1(V^), p_2(V^))$是定义2.3指定的纳什均衡。因此，基于贝尔曼算子$T^$，【82】提出了价值迭代算法，它创建了一个价值函数序列${V_t}{t≥1}$，满足$V = T^V_t$，并以线性速率收敛到$V^$。具体来说，我们有

价值迭代与策略迭代。此外，价值迭代更新可以分解为两个步骤。具体来说，令$\pi_1$为玩家1的任意策略，V为任意价值函数，我们定义贝尔曼算子$T^{\pi_1}$为

其中$Q^V$在(4.8)中定义。然后我们可以等价地将价值迭代更新写为

这种分解激发了双人零和博弈的策略迭代算法，该算法在例如【230, Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science 12(5), 359–370 (1966)】,【231, Van Der Wal, J.: Discounted markov games: Generalized policy iteration method. Journal of Optimization Theory and Applications 25(1), 125–138 (1978)】,【232, Rao, S.S., Chandrasekaran, R., Nair, K.: Algorithms for discounted stochastic games. Journal of Optimization Theory and Applications 11(6), 627–637 (1973)】,【233, Patek, S.D.: Stochastic and shortest path games: Theory and algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1997)】,【234, Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2- player turn-based stochastic games with a constant discount factor. Journal of the ACM 60(1), 1 (2013)】中针对这种马尔可夫博弈的不同变体进行了研究。特别地，从玩家1的角度来看，策略迭代创建了一个序列${\mu_t, V_t}{t≥0}$，满足

即，$V$以线性收敛速率单调增加到$V^*$。}$是$T^{\mu_{t+1}}$的不动点。玩家2的更新可以类似地构造。根据(4.10)的定义，贝尔曼算子$T^{\mu_{t+1}}$是γ-压缩的，其不动点对应于与$(\mu_{t+1}, Br(\mu_{t+1}))$相关的价值函数，其中$Br(\mu_{t+1})$是玩家2在玩家1采用$\mu_{t+1}$时的最佳响应策略。因此，在策略迭代的每一步中，玩家首先根据当前函数$V_t$找到一个改进的策略$\mu_{t+1}$，然后通过假设对手扮演最佳反制策略$Br(\mu_{t+1})$来获得一个保守的价值函数。在【234, Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2- player turn-based stochastic games with a constant discount factor. Journal of the ACM 60(1), 1 (2013)】中已经证明，对于回合制零和马尔可夫博弈，价值函数序列${V_t}_{t≥0

Minimax-Q学习。需要注意的是，价值迭代和策略迭代算法都是基于模型的，因为需要计算(4.11)和(4.12)中的贝尔曼算子$T^{\mu_{t+1}}$。通过数据驱动的近似估计贝尔曼算子，【83, Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 157–163 (1994)】提出了minimax-Q学习，它将著名的Q学习算法【48, Watkins, C.J., Dayan, P.: Q-learning. Machine Learning 8(3-4), 279–292 (1992)】从MDPs扩展到零和马尔可夫博弈。具体来说，minimax-Q学习是一种在线、离策略的表格方法，它基于转移数据${(s_t, a_t, r_t, s't)}$更新动作-价值函数$Q : S × A → R$，其中$s't$是跟随$(s_t, a_t)$的下一个状态，$r_t$是奖励。在第t次迭代中，它只更新$Q(s_t, a_t)$的值，并保持Q的其他条目不变。
具体来说，我们有

其中$α_t ∈ (0, 1)$是步长。如【49, Szepesvari, C., Littman, M.L.: A unified analysis of value-function-based reinforcement- ´ learning algorithms. Neural Computation 11(8), 2017–2060 (1999)】所示，在与单智能体Q学习【48】相似的条件下，由(4.13)生成的函数Q收敛到最优动作-价值函数$Q^ = Q^{V^}$，该函数由(4.7)和(4.8)组合定义。此外，略微滥用符号，如果我们为动作-价值函数定义贝尔曼算子$T^$为

那么我们有$Q^$是$T^$的唯一不动点。由于(4.13)中的目标值$r_t+γ·Value[Q(s'_t, ·, ·)]$是$(T^Q)(s_t, a)$的估计量，minimax-Q学习可以被看作是计算$T^*$不动点的随机逼近算法。继【83】之后，minimax-Q学习被进一步扩展到函数逼近设置，其中(4.13)中的Q由一类参数化函数逼近。然而，即使是对于线性函数逼近的minimax-Q学习，其收敛保证也尚未被很好地理解。这种线性价值函数逼近也适用于一类重要的具有连续状态-动作空间的零和MG实例，即线性二次（LQ）零和博弈【99, Bas¸ar, T., Bernhard, P.: H∞ Optimal Control and Related Minimax Design Problems: A Dynamic Game Approach. Birkhauser, Boston. (1995) ¨】,【235, Al-Tamimi, A., Abu-Khalaf, M., Lewis, F.L.: Adaptive critic designs for discrete-time zerosum games with application to H∞ control. IEEE Transactions on Systems, Man, and Cybernetics, Part B 37(1), 240–247 (2007)】,【236, Al-Tamimi, A., Lewis, F.L., Abu-Khalaf, M.: Model-free Q-learning designs for linear discrete-time zero-sum games with application to H∞ control. Automatica 43(3), 473–481 (2007)】，其中奖励函数是关于状态和动作的二次函数，而转移模型遵循线性动态。在这种设置下，可以保证基于Q学习的算法收敛到NE【236】。}, a_{2t

批量RL与有限样本分析。为了涵盖通用的函数类别，批量RL的框架【237, Lagoudakis, M.G., Parr, R.: Value function approximation in zero-sum Markov games. In: Conference on Uncertainty in Artificial Intelligence, pp. 283–292 (2002)】,【200, Munos, R.: Performance bounds in p-norm for approximate value iteration. SIAM Journal on Control and Optimization 46(2), 541–561 (2007)】,【201, Munos, R., Szepesvari, C.: Finite-time bounds for fitted value iteration. Journal of Machine ´ Learning Research 9(May), 815–857 (2008)】,【197, Antos, A., Szepesvari, C., Munos, R.: Fitted Q-iteration in continuous action-space MDPs. ´ In: Advances in Neural Information Processing Systems, pp. 9–16 (2008)】,【202, Antos, A., Szepesvari, C., Munos, R.: Learning near-optimal policies with Bellman-residual ´ minimization based fitted policy iteration and a single sample path. Machine Learning 71(1), 89–129 (2008)】,【238, Farahmand, A.m., et al.: Regularized policy iter- ´ ation with nonparametric function spaces. Journal of Machine Learning Research 17(1), 4809–4874 (2016)】可以适应多智能体设置，如最近的工作【239, Yang, Z., Xie, Y., Wang, Z.: A theoretical analysis of deep Q-learning. arXiv preprint arXiv:1901.00137 (2019)】,【44, Zhang, K., et al.: Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02783 (2018)】。如§4.1.2中为合作批量MARL所述，每个智能体通过使用目标值拟合最小二乘来迭代更新Q函数。具体来说，令F为感兴趣的函数类，${(s_i, a_1, a_2, r_i, s'i)}$为数据集。对于任何t ≥ 0，令$Q_t$为第t次迭代的当前迭代值，并定义$y_i = r_i + γ · Value[Q_t(s'_i, ·, ·)]$对于所有i ∈ [n]。然后我们通过在F中求解一个最小二乘回归问题来更新$Q_t$，即

在这种双人零和马尔可夫博弈设置中，【239, Yang, Z., Xie, Y., Wang, Z.: A theoretical analysis of deep Q-learning. arXiv preprint arXiv:1901.00137 (2019)】建立了Q函数估计的有限样本误差界。

其他有限样本分析与在线设置。关于其他有限样本分析，最近，【240, Jia, Z., Yang, L.F., Wang, M.: Feature-based Q-learning for two-player stochastic games. arXiv preprint arXiv:1906.00423 (2019)】研究了零和回合制随机博弈（TBSG），这是一种简化的零和MG，当转移模型嵌入某个特征空间并且有生成模型可用时。为该设置提出了两种基于Q学习的算法并进行了分析。【35, Sidford, A., et al.: Solving discounted stochastic two-player games with near-optimal time and sample complexity. arXiv preprint arXiv:1908.11071 (2019)】通过扩展先前用于MDP的近优Q学习算法【241, Sidford, A., et al.: Near-optimal time and sample complexities for solving Markov decision processes with a generative model. In: Advances in Neural Information Processing Systems, pp. 5186–5196 (2018)】，为具有生成模型的通用零和TBSG提出了实现近优样本复杂度的算法。在在线设置中，学习者只控制其中一个玩家与任意对手对战，【242, Wei, C.Y., Hong, Y.T., Lu, C.J.: Online reinforcement learning in stochastic games. In: Advances in Neural Information Processing Systems, pp. 4987–4997 (2017)】提出了UCSG算法，用于平均奖励零和MGs，使用了“面对不确定性时的乐观主义”原则【243, Auer, P., Ortner, R.: Logarithmic online regret bounds for undiscounted reinforcement learning. In: Advances in Neural Information Processing Systems, pp. 49–56 (2007)】,【244, Jaksch, T., Ortner, R., Auer, P.: Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11(Apr), 1563–1600 (2010)】。UCSG被证明在与任意对手竞争时，相对于博弈价值实现了亚线性遗憾，并且如果对手采取乐观的最佳响应，则实现O(poly(1/ε))的样本复杂度。

不完美信息零和博弈。此外，当涉及不完美信息的零和博弈时，【245, Koller, D., Megiddo, N., von Stengel, B.: Fast algorithms for finding randomized strategies in game trees. Computing 750, 759 (1994)】,【246, Von Stengel, B.: Efficient computation of behavior strategies. Games and Economic Behavior 14(2), 220–246 (1996)】,【247, Koller, D., Megiddo, N., Von Stengel, B.: Efficient computation of equilibria for extensive two-person games. Games and economic behavior 14(2), 247–259 (1996)】,【248, Von Stengel, B.: Computing equilibria for two-person games. Handbook of Game Theory with Economic Applications 3, 1723–1759 (2002)】提出使用序列形式表示法将扩展形式博弈转换为范式博弈，从而可以通过线性规划找到均衡。此外，通过将状态空间提升到信念状态空间，【249, Parr, R., Russell, S.: Approximating optimal policies for partially observable stochastic domains. In: International Joint Conference on Artificial Intelligence, pp. 1088–1094 (1995)】,【250, Rodriguez, A.C., Parr, R., Koller, D.: Reinforcement learning using approximate belief states. In: Advances in Neural Information Processing Systems, pp. 1036–1042 (2000)】,【251, Hauskrecht, M.: Value-function approximations for partially observable Markov decision processes. Journal of Artificial Intelligence Research 13, 33–94 (2000)】,【119, Hansen, E.A., Bernstein, D.S., Zilberstein, S.: Dynamic programming for partially observable stochastic games. In: AAAI Conference on Artificial Intelligence, pp. 709–715 (2004)】,【252, Buter, B.J.: Dynamic programming for extensive form games with imperfect information. Ph.D. thesis, Universiteit van Amsterdam (2012)】已将动态规划方法应用于零和随机博弈。这两种方法都保证找到纳什均衡，但仅对小规模问题有效。最后，具有UCB类型动作选择规则的MCTS【51, Chang, H.S., et al.: An adaptive sampling algorithm for solving Markov decision processes. Operations Research 53(1), 126–139 (2005)】,【52, Kocsis, L., Szepesvari, C.: Bandit based Monte-Carlo planning. In: European Conference on ´ Machine Learning, pp. 282–293. Springer (2006)】,【53, Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: International Conference on Computers and Games, pp. 72–83 (2006)】也可以应用于具有不完全信息的双人回合制博弈【52, Kocsis, L., Szepesvari, C.: Bandit based Monte-Carlo planning. In: European Conference on ´ Machine Learning, pp. 282–293. Springer (2006)】,【253, Cowling, P.I., Powley, E.J., Whitehouse, D.: Information set Monte Carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games 4(2), 120–143 (2012)】,【254, Teraoka, K., Hatano, K., Takimoto, E.: Efficient sampling method for Monte Carlo tree search problem. IEICE Transactions on Information and Systems 97(3), 392–398 (2014)】,【255, Whitehouse, D.: Monte Carlo tree search for games with hidden information and uncertainty. Ph.D. thesis, University of York (2014)】,【256, Kaufmann, E., Koolen, W.M.: Monte-Carlo tree search by best arm identification. In: Advances in Neural Information Processing Systems, pp. 4897–4906 (2017)】，这为最近深度RL在围棋博弈中的成功奠定了基础【1, Silver, D., et al.: Mastering the game of Go with deep neural networks and tree search. Nature 529(7587), 484–489 (2016)】。此外，这些方法被证明收敛到博弈的极小极大解，因此可以看作是minimax-Q学习与蒙特卡洛采样的对应物。

4.2.2 基于策略的方法

基于策略方法的扩展。§2.1.2中介绍的基于策略的强化学习方法也可以扩展到多智能体设置。与寻找贝尔曼算子的不动点不同，相当数量的方法只关注单个智能体，旨在最大化该智能体的期望回报，而不考虑其他智能体的策略。具体来说，从单个智能体的角度来看，由于其他智能体也在调整其策略，环境是时变的。基于策略的方法旨在通过最小化（外部）遗憾来在其他智能体任意行动时实现最优性能，即找到一个动作序列，其表现几乎与事后看来最优的固定策略一样好。一个平均总遗憾可以忽略不计的算法被称为无遗憾或Hannan一致的【257, Hannan, J.: Approximation to Bayes risk in repeated play. Contributions to the Theory of Games 3, 97–139 (1957)】。任何Hannan一致的算法在重复范式博弈中都具有以下两个理想性质。首先，当其他智能体采用平稳策略时，由该算法构建的时间平均策略收敛到最佳响应策略（针对其他智能体使用的策略）。其次，更有趣的是，在双人零和博弈中，当两个玩家都采用Hannan一致的算法并且他们的平均总遗憾都不超过ε时，他们的时间平均策略构成一个2ε-近似纳什均衡【126, Blum, A., Mansour, Y.: Learning, regret minimization, and equilibria. Algorithmic Game Theory pp. 79–102 (2007)】。因此，任何Hannan一致的单智能体强化学习算法都可以通过自博弈应用于寻找双人零和博弈的纳什均衡。这些方法大多属于以下两个家族之一：虚拟博弈【258, Brown, G.W.: Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation 13(1), 374–376 (1951)】,【259, Robinson, J.: An iterative method of solving a game. Annals of Mathematics pp. 296–301 (1951)】和反事实遗憾最小化【109, Zinkevich, M., et al.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729– 1736 (2008)】，下面将进行总结。

虚拟博弈。虚拟博弈是博弈论中研究的一种经典算法，玩家重复进行博弈，每个玩家采用对其他智能体平均策略的最佳响应策略。该方法最初是为解决范式博弈而提出的，范式博弈是定义2.2中定义的马尔可夫博弈的简化，其中S为单点且γ = 0。具体来说，对于N个智能体的任何联合策略π ∈ ∆(A)，我们让π−i表示除玩家i之外所有玩家的边际策略。对于任何t ≥ 1，假设智能体在前t个阶段中玩了${a_τ : 1 ≤ τ ≤ t}$。我们定义$x_t$为${a_τ : 1 ≤ τ ≤ t}$的经验分布，即对于任何a ∈ A，$x_t(a) = t^{-1} Σ_{τ=1}^t 1{a_t = a}$。然后，在第t阶段，每个智能体i根据对$x_{-i}^t$的最佳响应策略采取动作$a_i^t ∈ A_i$。换句话说，每个智能体都扮演着对抗从历史数据中推断出的其他智能体策略的最佳反制策略。这里，对于任何ε > 0和任何π ∈ ∆(A)，我们用$Br_ε(π_{−i})$表示玩家i的ε-最佳响应策略，它满足

此外，我们定义$Br_ε(π)$为联合策略$(Br_ε(π_{−1}), . . . , Br_ε(π_{−N})) ∈ ∆(A)$，如果ε = 0，则在$Br_ε$中省略下标ε。通过这个符号，将每个a ∈ A视为∆(A)的一个顶点，我们可以等价地将虚拟过程写为

当t → ∞时，(4.17)中的更新可以近似地由一个微分包含【260, Bena¨ım, M., Hofbauer, J., Sorin, S.: Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization 44(1), 328–348 (2005)】来表征

这被称为连续时间虚拟博弈。虽然众所周知(4.17)中的离散时间虚拟博弈不是Hannan一致的【261, Hart, S., Mas-Colell, A.: A general class of adaptive strategies. Journal of Economic Theory 98(1), 26–54 (2001)】,【160, Young, H.P.: The evolution of conventions. Econometrica: Journal of the Econometric Society pp. 57–84 (1993)】，但【262, Monderer, D., Samet, D., Sela, A.: Belief affirming in learning processes. Journal of Economic Theory 73(2), 438–452 (1997)】,【263, Viossat, Y., Zapechelnyuk, A.: No-regret dynamics and fictitious play. Journal of Economic Theory 148(2), 825–842 (2013)】表明(4.18)中的连续时间虚拟博弈是Hannan一致的。此外，使用随机逼近的工具【264, Kushner, H.J., Yin, G.G.: Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York, NY (2003)】,【261, Hart, S., Mas-Colell, A.: A general class of adaptive strategies. Journal of Economic Theory 98(1), 26–54 (2001)】，基于平滑或随机扰动等技术的各种离散时间虚拟博弈的修改已被证明收敛到连续时间虚拟博弈，因此是Hannan一致的【265, Fudenberg, D., Levine, D.K.: Consistency and cautious fictitious play. Journal of Economic Dynamics and Control 19(5-7), 1065–1089 (1995)】,【266, Hofbauer, J., Sandholm, W.H.: On the global convergence of stochastic fictitious play. Econometrica 70(6), 2265–2294 (2002)】,【267, Leslie, D.S., Collins, E.J.: Generalised weakened fictitious play. Games and Economic Behavior 56(2), 285–298 (2006)】,【268, Bena¨ım, M., Faure, M.: Consistency of vanishingly smooth fictitious play. Mathematics of Operations Research 38(3), 437–450 (2013)】,【269, Li, Z., Tewari, A.: Sampled fictitious play is hannan consistent. Games and Economic Behavior 109, 401–412 (2018)】。因此，将这些方法与自博弈相结合，可以证明能够找到双人零和范式博弈的纳什均衡。

扩展到RL设置的虚拟博弈。此外，虚拟博弈方法也已扩展到无需模型知识的RL设置。具体来说，使用序列形式表示，【110, Heinrich, J., Lanctot, M., Silver, D.: Fictitious self-play in extensive-form games. In: International Conference on Machine Learning, pp. 805–813 (2015)】提出了第一个用于扩展形式博弈的虚拟博弈算法，该算法在实现上等价于范式博弈的广义弱化虚拟博弈【267, Leslie, D.S., Collins, E.J.: Generalised weakened fictitious play. Games and Economic Behavior 56(2), 285–298 (2006)】。其关键见解是，范式策略的凸组合可以使用实现概率写成行为策略的加权凸组合。具体来说，回想智能体i的信息状态集表示为$S_i$。当博弈具有完美回忆时，每个$s_i ∈ S_i$唯一地定义了智能体i为达到状态$s_i$而进行的一系列动作$σ_{s_i}$。然后，智能体i的任何行为策略$π_i$都会为智能体i的每个序列σ导出实现概率$Rp(π_i; ·)$，定义为$Rp(π_i; σ) = Π_{(σ_{s'},a)≺σ} π_i(a | s')$，其中乘积取所有$s' ∈ S_i$和$a ∈ A_i$使得$(σ_{s'}, a)$是σ的子序列。使用实现概率的符号，对于智能体i的任意两个行为策略π和π'，和为

是π和π'的混合策略，权重分别为λ ∈ (0, 1)和1 - λ。然后，结合(4.16)和(4.19)，【110】中的虚拟博弈算法计算一个策略序列${π_t}{t≥1}$。具体来说，在第t次迭代中，任何智能体i首先计算$ε : S × A_1 → R$定义为}$-最佳响应策略$π_{i}^{t+1} ∈ Br_{ε_{t+1}}(π_{-i}^t)$，然后将$π_{i}^{t+1}$构造为$π_i^t$和$π^{t+1}$的混合策略，权重分别为$1 - α_{t+1}$和$α_{t+1}$。这里，$ε_t$和$α_t$都随着t趋于无穷而收敛到零，并且我们还有$Σ_{t≥1} α_t = ∞$。然而，我们注意到，尽管这种方法通过自博弈可证明地收敛到零和博弈的纳什均衡，但由于需要在每次迭代中遍历博弈的所有状态，它存在维度诅咒的问题。为了提高计算效率，【110】还提出了一个数据驱动的虚拟自博弈框架，其中最佳响应是通过拟合Q迭代【270, Ernst, D., Geurts, P., Wehenkel, L.: Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6(Apr), 503–556 (2005)】,【200, Munos, R.: Performance bounds in p-norm for approximate value iteration. SIAM Journal on Control and Optimization 46(2), 541–561 (2007)】为单智能体RL问题计算的，策略混合通过监督学习来学习。这个框架后来被【271, Heinrich, J., Silver, D.: Self-play Monte-Carlo tree search in computer Poker. In: Workshops at AAAI Conference on Artificial Intelligence (2014)】,【25, Heinrich, J., Silver, D.: Deep reinforcement learning from self-play in imperfect-information games. arXiv preprint arXiv:1603.01121 (2016)】,【30, Kawamura, K., Mizukami, N., Tsuruoka, Y.: Neural fictitious self-play in imperfect information games with many players. In: Workshop on Computer Games, pp. 61–74 (2017)】,【31, Zhang, L., et al.: Monte Carlo neural fictitious self-play: Approach to approximate Nash equilibrium of imperfect-information games. arXiv preprint arXiv:1903.09569 (2019)】采用，以整合其他单RL方法，如深度Q网络【10】和蒙特卡洛树搜索【53, Coulom, R.: Efficient selectivity and backup operators in Monte-Carlo tree search. In: International Conference on Computers and Games, pp. 72–83 (2006)】,【52, Kocsis, L., Szepesvari, C.: Bandit based Monte-Carlo planning. In: European Conference on ´ Machine Learning, pp. 282–293. Springer (2006)】,【272, Browne, C.B., et al.: A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4(1), 1–43 (2012)】。此外，在最近的一项工作中，【162, Perolat, J., Piot, B., Pietquin, O.: Actor-critic fictitious play in simultaneous move multistage games. In: International Conference on Artificial Intelligence and Statistics (2018)】为具有同时移动的零和多阶段博弈（零和随机博弈的一个特例）提出了一个平滑虚拟博弈算法【265, Fudenberg, D., Levine, D.K.: Consistency and cautious fictitious play. Journal of Economic Dynamics and Control 19(5-7), 1065–1089 (1995)】。他们的算法将演员-评论家框架【69, Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. In: Advances in Neural Information Processing Systems, pp. 1008–1014 (2000)】与虚拟自博弈相结合，并通过策略评估隐式地推断对手的策略。具体来说，当两个玩家采用联合策略$π = (π_1, π_2)$时，从玩家1的角度来看，它通过时间差分学习【273, Sutton, R.S., Barto, A.G.: A temporal-difference model of classical conditioning. In: Proceedings of the Annual Conference of the Cognitive Science Society, pp. 355–378 (1987)】估计$Q^{π_1,π_2}$来隐式推断$π_2$，其中$Q^{π_1,π_2

这是玩家1的动作-价值函数，由$π_2$边缘化。此外，最佳响应策略是通过对$Q^{π_1,π_2}$采取软贪婪策略来获得的，即

其中η > 0是平滑参数。最后，该算法通过使用双时间尺度更新【274, Borkar, V.S.: Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press (2008)】,【264, Kushner, H.J., Yin, G.G.: Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York, NY (2003)】同时执行策略评估和(4.20)中的策略更新来获得，这确保了在使用自博弈时，策略更新可以由一个常微分方程来表征，其渐近稳定解是博弈的一个平滑纳什均衡。

反事实遗憾最小化（CFR）。另一族流行的基于策略的方法是基于反事实遗憾最小化（CFR）的思想，最早由【109, Zinkevich, M., et al.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729– 1736 (2008)】提出，这是解决大规模扩展形式博弈的一项突破。此外，从理论角度看，与通过随机逼近进行渐近分析的虚拟博弈算法相比，可以使用在线学习的工具【275, Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press (2006)】建立明确的遗憾界，从而得出收敛到纳什均衡的速率。具体来说，当N个智能体用${π_t : 1 ≤ t ≤ T}$进行T轮扩展形式博弈时，玩家i的遗憾定义为

其中最大值取自玩家i所有可能的策略。接下来，在定义反事实遗憾的概念之前，我们首先介绍一些符号。回想一下，我们在(2.4)中定义了到达概率$η^π(h)$，它可以分解为每个智能体贡献的乘积。也就是说，对于每个i ∈ U ∪ {c}，我们可以将涉及$π_i$的概率项组合成$η_i^π(h)$，并写成$η^π(h) = Π_{i∈N ∪{c}} η_i^π(h) = η_i^π(h) · η_{-i}^π(h)$。此外，对于满足h ≺ h'的任意两个历史h, h' ∈ H，我们定义条件到达概率$η^π(h' | h)$为$η^π(h')/η^π(h)$，并类似地定义$η_i^π(h' | h)$。对于任何$s ∈ S_i$和任何$a ∈ A(s)$，我们定义$Z(s, a) = {(h, z) ∈ H × Z | h ∈ s, ha ≺ z}$，它包含了信息状态s中所有可能的历史与在s处采取行动a后的终端历史的对。然后，反事实价值函数定义为

这是智能体i在已经玩到状态s的情况下获得的期望效用。我们还定义$V_{CF}^i(π, s) = Σ_{a∈A(s)} Q_{CF}^i(π, s, a) · π_i(a | s)$。那么$Q_{CF}^i(π, s, a)$和$V_{CF}^i(π, s)$之间的差异可以看作是信息状态$s ∈ S_i$处动作a的价值，智能体i在状态s的反事实遗憾定义为

此外，如【109, Zinkevich, M., et al.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729– 1736 (2008)】的定理3所示，(4.23)中定义的反事实遗憾为(4.21)中的总遗憾提供了一个上界：

其中我们让$x^+$表示任何$x ∈ R$的$\max{x,0}$。这个界为反事实遗憾最小化算法奠定了基础。具体来说，为了最小化(4.21)中的总遗憾，只需最小化每个信息状态的反事实遗憾，这可以通过任何在线学习算法实现，如EXP3【276, Auer, P., et al.: The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32(1), 48–77 (2002)】、Hedge【277, Vovk, V.G.: Aggregating strategies. Proceedings of Computational Learning Theory (1990)】,【278, Littlestone, N., Warmuth, M.K.: The weighted majority algorithm. Information and Computation 108(2), 212–261 (1994)】,【279, Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games and Economic Behavior 29(1-2), 79–103 (1999)】和遗憾匹配【280, Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000)】。所有这些方法都确保反事实遗憾对于所有$s ∈ S_i$都是$O(\sqrt{T})$，这导致总遗憾的上界为$O(\sqrt{T})$。因此，将CFR类型的方法与自博弈应用于零和双人扩展形式博弈，平均策略在T步后是一个$O(1/\sqrt{T})$-近似纳什均衡。特别地，vanilla CFR算法通过遗憾匹配更新策略，这使得对于所有$s ∈ S_i$，$Reg_i^T(s) ≤ R_{i,max} · \sqrt{|A_i|} · \sqrt{T}$，其中我们引入了

因此，由(4.24)，智能体i的总遗憾由$R_{i,max} · |S_i| · \sqrt{|A_i|} · \sqrt{T}$界定。

CFR的变体和改进。vanilla CFR的一个缺点是每次迭代都需要遍历整个博弈树，这在计算上可能是禁止的。自开创性工作【109, Zinkevich, M., et al.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729– 1736 (2008)】以来，已经提出了许多CFR变体以提高计算效率。例如，【281, Lanctot, M., et al.: Monte Carlo sampling for regret minimization in extensive games. In: Advances in Neural Information Processing Systems, pp. 1078–1086 (2009)】,【282, Burch, N., et al.: Efficient Monte Carlo counterfactual regret minimization in games with many player actions. In: Advances in Neural Information Processing Systems, pp. 1880–1888 (2012)】,【283, Gibson, R., et al.: Generalized sampling and variance in counterfactual regret minimization. In: AAAI Conference on Artificial Intelligence (2012)】,【284, Johanson, M., et al.: Efficient Nash equilibrium approximation through Monte Carlo counterfactual regret minimization. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 837–846 (2012)】,【285, Lisy, V., Lanctot, M., Bowling, M.: Online Monte Carlo counterfactual regret minimization for search in imperfect information games. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 27–36 (2015)】,【286, Schmid, M., et al.: Variance reduction in Monte Carlo counterfactual regret minimization (VR-MCCFR) for extensive form games using baselines. In: AAAI Conference on Artificial Intelligence, vol. 33, pp. 2157– 2164 (2019)】将CFR与蒙特卡洛采样相结合；【287, Waugh, K., Morrill, D., Bagnell, J.A., Bowling, M.: Solving games with functional regret estimation. In: AAAI Conference on Artificial Intelligence (2015)】,【288, Morrill, D.: Using regret estimation to solve games compactly. Ph.D. thesis, University of Alberta (2016)】,【289, Brown, N., Lerer, A., Gross, S., Sandholm, T.: Deep counterfactual regret minimization. In: International Conference on Machine Learning, pp. 793–802 (2019)】提出通过回归估计反事实价值函数；【290, Brown, N., Sandholm, T.: Regret-based pruning in extensive-form games. In: Advances in Neural Information Processing Systems, pp. 1972–1980 (2015)】,【291, Brown, N., Kroer, C., Sandholm, T.: Dynamic thresholding and pruning for regret minimization. In: AAAI Conference on Artificial Intelligence (2017)】,【292, Brown, N., Sandholm, T.: Reduced space and faster convergence in imperfect-information games via pruning. In: International Conference on Machine Learning, pp. 596–604 (2017)】通过修剪博弈树中的次优路径来提高计算效率；【293, Tammelin, O.: Solving large imperfect information games using CFR+. arXiv preprint arXiv:1407.5042 (2014)】,【294, Tammelin, O., et al.: Solving heads-up limit Texas Hold’em. In: International Joint Conference on Artificial Intelligence (2015)】,【295, Burch, N., Moravcik, M., Schmid, M.: Revisiting CFR+ and alternating updates. Journal of Artificial Intelligence Research 64, 429–443 (2019)】分析了一个名为CFR+的修改版本的性能，【296, Zhou, Y., et al.: Lazy-CFR: A fast regret minimization algorithm for extensive games with imperfect information. arXiv preprint arXiv:1810.04433 (2018)】提出了具有近优遗憾上界的懒惰更新。

CFR与策略梯度方法的关系。此外，最近在【111, Srinivasan, S., et al.: Actor-critic policy optimization in partially observable multiagent environments. In: Advances in Neural Information Processing Systems, pp. 3422–3435 (2018)】中表明，CFR与策略梯度方法密切相关。为了看到这一点，对于任何联合策略π和任何i ∈ N，我们定义智能体i的动作-价值函数，记为$Q_i^π$，为

也就是说，$Q_i^π(s, a)$是当智能体遵循策略π并且智能体i在信息状态$s ∈ S_i$处采取动作a时，智能体i的期望效用，条件是s被达到。在【111】中已经表明，(4.22)中的$Q_{CF}^i$通过$Q_{CF}^i(π, s, a) = Q_i^π(s, a) · [Σ_{h∈s} η_{-i}^π(h)]$与(4.25)中的$Q_i^π$相连接。此外，在表格设置中，我们将联合策略π视为一个表${π_i(a | s) : s ∈ S_i, a ∈ A(s)}$，对于任何$s ∈ S_i$和任何$a ∈ A(s)$，$R_i(π)$的策略梯度可以写为

因此，优势演员-评论家（A2C）算法【69, Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. In: Advances in Neural Information Processing Systems, pp. 1008–1014 (2000)】等价于一个特定的CFR算法，其中策略更新规则由广义无穷小梯度上升算法【297, Zinkevich, M.: Online convex programming and generalized infinitesimal gradient ascent. In: International Conference on Machine Learning, pp. 928–936 (2003)】指定。因此，【111】证明了表格A2C算法的遗憾由$|S_i| · [1 + |A_i| · (R_{i,max})^2] · \sqrt{T}$界定。继这项工作之后，【112, Omidshafiei, S., et al.: Neural replicator dynamics. arXiv preprint arXiv:1906.00190 (2019)】表明，当策略是表格形式并由softmax函数参数化时，A2C等价于使用Hedge更新策略的CFR。此外，【298, Lockhart, E., et al.: Com- ´ puting approximate equilibria in sequential adversarial games by exploitability descent. arXiv preprint arXiv:1903.05614 (2019)】提出了一种称为可利用性下降的策略优化方法，其中策略使用演员-评论家进行更新，假设对手扮演最佳反制策略。该方法等价于使用Hedge的CFR-BR算法【299, Johanson, M., et al.: Finding optimal abstract strategies in extensive-form games. In: AAAI Conference on Artificial Intelligence, pp. 1371–1379 (2012)】。因此，【111】,【112】,【298】表明，MARL的演员-评论家和策略梯度方法可以被表述为CFR方法，因此保证了在零和扩展形式博弈中收敛到纳什均衡。

其他策略优化方法。此外，除了上面介绍的虚拟博弈和CFR方法，还为特殊类别的双人零和随机博弈或扩展形式博弈提出了多种策略优化方法。例如，为具有同时移动的完美信息扩展博弈提出了蒙特卡洛树搜索方法。在【300, Schaeffer, M.S., Sturtevant, N., Schaeffer, J.: Comparing UCT versus CFR in simultaneous games (2009)】中表明，§4.2.1中介绍的具有UCB类型动作选择规则的MCTS方法在同时移动博弈中无法收敛到纳什均衡，因为UCB没有考虑对手可能采取的对抗性移动。为了解决这个问题，【301, Lanctot, M., Lisy, V., Winands, M.H.: Monte Carlo tree search in simultaneous move games with applications to Goofspiel. In: Workshop on Computer Games, pp. 28–43 (2013)】,【302, Lisy, V., et al.: Convergence of Monte Carlo tree search in ` simultaneous move games. In: Advances in Neural Information Processing Systems, pp. 2112–2120 (2013)】,【303, Tak, M.J., Lanctot, M., Winands, M.H.: Monte Carlo tree search variants for simultaneous move games. In: IEEE Conference on Computational Intelligence and Games, pp. 1–8 (2014)】,【304, Kovarˇ´ık, V., Lisy, V.: Analysis of hannan consistent selection for Monte Carlo tree search in ` simultaneous move games. arXiv preprint arXiv:1804.09045 (2018)】提出采用随机策略，并使用Hannan一致性方法（如EXP3【276】和遗憾匹配【280】）来更新策略。通过自博弈，【302】表明，通过任何ε-Hannan一致性策略更新方法获得的MCTS平均策略收敛到一个O(D²·ε)-纳什均衡，其中D是最大深度。

连续博弈中的策略梯度。最后，研究连续博弈（即具有连续状态-动作空间的博弈）中基于策略梯度的方法的兴趣日益浓厚。通过策略参数化，找到零和马尔可夫博弈的NE通常成为一个非凸非凹的鞍点问题【32, Mazumdar, E., Ratliff, L.J.: On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464 (2018)】,【305, Mazumdar, E.V., Jordan, M.I., Sastry, S.S.: On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.00838 (2019)】,【34, Zhang, K., Yang, Z., Bas¸ar, T.: Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In: Advances in Neural Information Processing Systems (2019)】,【306, Bu, J., Ratliff, L.J., Mesbahi, M.: Global convergence of policy gradient for sequential zerosum linear quadratic dynamic games. arXiv preprint arXiv:1911.04672 (2019)】。这种困难是固有的，即使在最简单的具有线性函数逼近的线性二次设置中也是如此【34, Zhang, K., Yang, Z., Bas¸ar, T.: Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In: Advances in Neural Information Processing Systems (2019)】,【306, Bu, J., Ratliff, L.J., Mesbahi, M.: Global convergence of policy gradient for sequential zerosum linear quadratic dynamic games. arXiv preprint arXiv:1911.04672 (2019)】。因此，大多数收敛结果是局部的【307, Mescheder, L., Nowozin, S., Geiger, A.: The numerics of GANs. In: Advances in Neural Information Processing Systems, pp. 1825–1835 (2017)】,【32, Mazumdar, E., Ratliff, L.J.: On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464 (2018)】,【308, Adolphs, L., et al.: Local saddle point optimization: A curvature exploitation approach. arXiv preprint arXiv:1805.05751 (2018)】,【309, Daskalakis, C., Panageas, I.: The limit points of (optimistic) gradient descent in min-max optimization. In: Advances in Neural Information Processing Systems, pp. 9236–9246 (2018)】,【310, Mertikopoulos, P., et al.: Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In: International Conference on Learning Representations (2019)】,【311, Fiez, T., Chasnov, B., Ratliff, L.J.: Convergence of learning dynamics in Stackelberg games. arXiv preprint arXiv:1906.01217 (2019)】,【305, Mazumdar, E.V., Jordan, M.I., Sastry, S.S.: On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.00838 (2019)】,【33, Jin, C., Netrapalli, P., Jordan, M.I.: Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv:1902.00618 (2019)】，因为它们解决了局部NE点周围的收敛行为。尽管如此，已经表明，vanilla梯度下降-上升（GDA）更新（等同于MARL中的策略梯度更新）无法收敛到局部NE，原因要么是极限环等非收敛行为【307, Mescheder, L., Nowozin, S., Geiger, A.: The numerics of GANs. In: Advances in Neural Information Processing Systems, pp. 1825–1835 (2017)】,【309, Daskalakis, C., Panageas, I.: The limit points of (optimistic) gradient descent in min-max optimization. In: Advances in Neural Information Processing Systems, pp. 9236–9246 (2018)】,【312, Balduzzi, D., et al.: The mechanics of n-player differentiable games. In: International Conference on Machine Learning, pp. 363–372 (2018)】,【310, Mertikopoulos, P., et al.: Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In: International Conference on Learning Representations (2019)】，要么是GDA动态存在非纳什稳定极限点【308, Adolphs, L., et al.: Local saddle point optimization: A curvature exploitation approach. arXiv preprint arXiv:1805.05751 (2018)】,【305, Mazumdar, E.V., Jordan, M.I., Sastry, S.S.: On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.00838 (2019)】。共识优化【307】、辛梯度调整【312】和外梯度法【310】被提倡用来缓解均衡点周围的振荡行为；而【308】,【305】利用曲率信息，使得所提出更新的所有稳定极限点都是局部NE。超越纳什均衡，【33, Jin, C., Netrapalli, P., Jordan, M.I.: Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv:1902.00618 (2019)】,【311, Fiez, T., Chasnov, B., Ratliff, L.J.: Convergence of learning dynamics in Stackelberg games. arXiv preprint arXiv:1906.01217 (2019)】考虑了基于梯度的斯塔克尔伯格均衡学习，这仅对应于零和博弈中的单边均衡解，即极小极大或极大极小，因为在非凸非凹问题中，哪个玩家先行动的顺序至关重要。【33】引入了局部极小极大点作为解的概念，并表明GDA在温和条件下收敛到局部极小极大点。【311】提出了一种双时间尺度算法，其中跟随者使用梯度博弈更新规则，而不是精确的最佳响应策略，该算法已被证明收敛到斯塔克尔伯格均衡。在更强的梯度主导假设下，【313, Sanjabi, M., Razaviyayn, M., Lee, J.D.: Solving non-convex non-concave min-max games under Polyak-Łojasiewicz condition. arXiv preprint arXiv:1812.02878 (2018)】,【314, Nouiehed, M., et al.: Solving a class of non-convex min-max games using iterative first order methods. arXiv preprint arXiv:1902.08297 (2019)】表明，嵌套梯度下降法以亚线性速率收敛到外循环问题（即极小极大问题）的平稳点。

连续博弈结果在MARL中的局限与进展。我们注意到，这些收敛结果是为具有不可知成本/奖励函数的一般连续博弈开发的，这意味着函数可能有各种形式，只要它们对每个智能体的策略参数是可微的，有时甚至是（利普希茨）平滑的。对于MARL，这等价于要求长期回报具有可微性/平滑性，这依赖于博弈的性质以及策略参数化的性质。这种假设通常非常严格。例如，利普希茨平滑假设在LQ博弈中全局不成立【34, Zhang, K., Yang, Z., Bas¸ar, T.: Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In: Advances in Neural Information Processing Systems (2019)】,【315, Mazumdar, E., Ratliff, L.J., Jordan, M.I., Sastry, S.S.: Policy-gradient algorithms have no guarantees of convergence in continuous action and state multi-agent settings. arXiv preprint arXiv:1907.03712 (2019)】,【306, Bu, J., Ratliff, L.J., Mesbahi, M.: Global convergence of policy gradient for sequential zerosum linear quadratic dynamic games. arXiv preprint arXiv:1911.04672 (2019)】，这是一种特殊类型的MGs。幸运的是，由于LQ设置的特殊结构，【34】提出了几种投影嵌套策略梯度方法，保证全局收敛到NE，并建立了收敛速率。这似乎是MARL中首个此类结果。这些结果随后被作者的后续工作【100, Zhang, K., Hu, B., Bas¸ar, T.: Policy optimization for H2 linear control with H∞ robustness guarantee: Implicit regularization and global convergence. arXiv preprint arXiv:1910.09496 (2019)】中的技术改进，对于更一般类别的此类博弈，可以移除更新中的投影步骤。最近，【306】也独立地用不同的技术改进了【34】中的结果。

4.3 混合设置

混合设置的挑战。与完全协作和完全竞争的设置形成鲜明对比，混合设置因其臭名昭著的挑战性而研究得相对较少。即使在最简单的双人一般和范式博弈中，找到纳什均衡也是PPAD完备的【316, Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3), 14 (2009)】。此外，【123, Zinkevich, M., Greenwald, A., Littman, M.L.: Cyclic equilibria in Markov games. In: Advances in Neural Information Processing Systems, pp. 1641–1648 (2006)】证明了价值迭代方法无法为一般和马尔可夫博弈找到平稳的纳什或相关均衡。最近，有研究表明，vanilla策略梯度方法在一般和连续博弈中会避开一个不可忽略的纳什均衡子集【32, Mazumdar, E., Ratliff, L.J.: On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464 (2018)】，包括LQ一般和博弈【315, Mazumdar, E., Ratliff, L.J., Jordan, M.I., Sastry, S.S.: Policy-gradient algorithms have no guarantees of convergence in continuous action and state multi-agent settings. arXiv preprint arXiv:1907.03712 (2019)】。因此，需要在博弈或算法上利用额外的结构，以确保在混合设置中实现可证明收敛的MARL。

基于价值的方法。在相对严格的假设下，一些将Q学习【48, Watkins, C.J., Dayan, P.: Q-learning. Machine Learning 8(3-4), 279–292 (1992)】扩展到混合设置的基于价值的方法被保证能找到一个均衡。特别地，【101, Hu, J., Wellman, M.P.: Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research 4(Nov), 1039–1069 (2003)】为一般和马尔可夫博弈提出了Nash-Q学习算法，其中维护N个动作-价值函数$Q_N = (Q_1, . . . , Q_N) : S × A → R^N$，这些函数使用贝尔曼算子的基于样本的估计器进行更新。具体来说，令$R_N = (R_1, . . . , R_N)$表示智能体的奖励函数，Nash-Q使用以下贝尔曼算子：

其中Nash[$Q_N(s', ·)$]是阶段博弈的纳什均衡的目标值，该博弈的奖励为${Q_N(s', a)}_{a∈A}$。对于零和博弈，我们有$Q_1 = -Q_2$，因此(4.26)中定义的贝尔曼算子等价于minimax-Q学习【83, Littman, M.L.: Markov games as a framework for multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 157–163 (1994)】使用的(4.14)中的算子。此外，【101】在严格的假设下建立了收敛到纳什均衡的结论，即算法每次迭代中的Nash[$Q_N(s', ·)$]都有唯一的纳什均衡。此外，【102, Littman, M.L.: Friend-or-Foe Q-learning in general-sum games. In: International Conference on Machine Learning, pp. 322–328 (2001)】提出了“朋友或敌人”Q学习算法，其中每个智能体将其他智能体视为“朋友”或“敌人”。在这种情况下，Nash[$Q_N(s', ·)$]可以通过线性规划高效计算。该算法可以看作是minimax-Q学习的推广，并且对于双人零和博弈和具有唯一均衡的协调博弈，保证了纳什均衡收敛。此外，【317, Greenwald, A., Hall, K., Serrano, R.: Correlated Q-learning. In: International Conference on Machine Learning, pp. 242–249 (2003)】提出了相关Q学习，它用计算相关均衡【318, Aumann, R.J.: Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics 1(1), 67–96 (1974)】（一个比纳什均衡更通用的均衡概念）来代替(4.26)中的Nash[$Q_N(s', ·)$]。在最近的一项工作中，【319, Perolat, J., et al.: Learning Nash Equilibrium for General-Sum Markov Games from Batch Data. In: International Conference on Artificial Intelligence and Statistics, pp. 232–241 (2017)】提出了一种批量RL方法，通过贝尔曼残差最小化【320, Maillard, O.A., et al.: Finite-sample analysis of Bellman residual minimization. In: Asian Conference on Machine Learning, pp. 299–314 (2010)】来找到近似纳什均衡。他们证明了经验贝尔曼残差的全局最小化器是一个近似纳什均衡，并随后对算法进行了误差传播分析。同样在批量RL领域，【44, Zhang, K., et al.: Finite-sample analyses for fully decentralized multi-agent reinforcement learning. arXiv preprint arXiv:1812.02783 (2018)】考虑了一种简化的混合设置用于分布式MARL：两队合作的网络智能体在一个零和马尔可夫博弈中竞争。提出了一种FQI的分布式变体，其中一个团队内的智能体合作解决(4.3)，而两个团队实质上解决(4.15)。然后为所提出的算法建立了有限样本误差界。

独立学习与弱非循环博弈。为了解决可扩展性问题，独立学习是首选，但通常无法收敛【139, Tan, M.: Multi-agent reinforcement learning: Independent vs. cooperative agents. In: International Conference on Machine Learning, pp. 330–337 (1993)】。【37, Arslan, G., Yuksel, S.: Decentralized Q-learning for stochastic teams and games. IEEE ¨ Transactions on Automatic Control 62(4), 1545–1558 (2017)】提出了一种分布式Q学习，这是Q学习的一种双时间尺度修改，保证几乎必然地收敛到弱非循环马尔可夫博弈的均衡。每个智能体只观察局部动作和奖励，既不观察也不跟踪他人的动作。所有智能体被指示在许多连续阶段使用相同的平稳基线策略，称为探索阶段。在探索阶段结束时，所有智能体同步更新其基线策略，这使得环境在足够长的时间内保持平稳，并使得基于Q学习的方法能够收敛。请注意，这些算法也可以应用于合作设置，因为这些博弈包括马尔可夫团队作为特例。

基于策略的方法。对于连续博弈，由于其中存在普遍的负面结果，【32, Mazumdar, E., Ratliff, L.J.: On the convergence of gradient-based learning in continuous games. arXiv preprint arXiv:1804.05464 (2018)】引入了一类新的博弈，即莫尔斯-斯梅尔博弈，其梯度动力学对应于类梯度流。然后，利用动力系统理论的工具，可以对PG方法几乎必然收敛到极限环、纳什均衡或非纳什不动点做出明确的陈述。此外，【312, Balduzzi, D., et al.: The mechanics of n-player differentiable games. In: International Conference on Machine Learning, pp. 363–372 (2018)】,【321, Letcher, A., et al.: Differentiable game mechanics. Journal of Machine Learning Research 20(84), 1–40 (2019)】研究了博弈动力学的二阶结构，将其分解为两个部分。第一个部分，称为对称部分，与势博弈相关，它在某个隐式函数上产生梯度下降；第二个部分，称为反对称部分，与哈密顿博弈相关，它遵循某个守恒定律，受经典力学系统分析的启发。梯度下降收敛到两种博弈的纳什均衡这一事实，激发了辛梯度调整算法的发展，该算法找到博弈的稳定不动点，这些不动点构成了零和博弈的所有局部纳什均衡，以及一般和博弈的局部NE的一个子集。【322, Chasnov, B., et al.: Convergence analysis of gradientbased learning with non-uniform learning rates in non-cooperative multi-agent settings. arXiv preprint arXiv:1906.00731 (2019)】在确定性设置（具有精确PG）和随机设置（具有无偏PG估计）中，为连续博弈的稳定局部纳什均衡的邻域提供了有限时间的局部收敛保证。此外，【322】还探讨了非均匀学习率对学习动力学和收敛速率的影响。【311, Fiez, T., Chasnov, B., Ratliff, L.J.: Convergence of learning dynamics in Stackelberg games. arXiv preprint arXiv:1906.01217 (2019)】也考虑了一般和斯塔克尔伯格博弈，并表明与零和情况相同的双时间尺度算法更新现在几乎必然仅收敛到稳定吸引子。它还为局部收敛到稳定斯塔克尔伯格均衡邻域建立了有限时间性能。与零和类完全类似，这些连续博弈的收敛结果不直接适用于马尔可夫博弈中的MARL，因为它们建立在长期回报的可微性/平滑性之上，这对于一般MGs（例如，LQ博弈【315, Mazumdar, E., Ratliff, L.J., Jordan, M.I., Sastry, S.S.: Policy-gradient algorithms have no guarantees of convergence in continuous action and state multi-agent settings. arXiv preprint arXiv:1907.03712 (2019)】）可能不成立。此外，这些收敛结果大多是局部的而非全局的。

自博弈与粗糙相关均衡。除了连续博弈，§4.2.2中总结的基于策略的方法也可以通过自博弈应用于混合设置。这种方法的有效性基于博弈论和在线学习之间的一个基本联系——如果每个智能体的外部遗憾不超过ε，那么他们的平均策略构成一般和范式博弈的一个ε-近似粗糙相关均衡【280, Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000)】,【261, Hart, S., Mas-Colell, A.: A general class of adaptive strategies. Journal of Economic Theory 98(1), 26–54 (2001)】,【323, Hart, S., Mas-Colell, A.: Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review 93(5), 1830–1836 (2003)】。因此，尽管通常我们无法找到纳什均衡，但通过自博弈的策略优化保证了在这些范式博弈中找到一个粗糙相关均衡。

平均场机制。在非合作设置中，可扩展性问题也可以在平均场机制中得到缓解，正如§4.1.1中讨论的合作设置一样。对于一般和博弈，【172, Yang, Y., et al.: Mean field multi-agent reinforcement learning. In: International Conference on Machine Learning, pp. 5571–5580 (2018)】提出了一种Nash-Q学习算法的修改，其中其他智能体的动作由它们的经验平均来近似。也就是说，每个智能体i的动作价值函数被参数化为$Q_i(s, a_i, \mu_{a_{-i}})$，其中$\mu_{a_{-i}}$是${a_j : j \neq i}$的经验分布。这种平均场Nash-Q学习算法的渐近收敛性也得到了建立。

平均场博弈（MFG）。此外，大多数平均场RL算法都专注于解决平均场博弈模型。在平均场博弈中，每个智能体i有一个局部状态$s_i ∈ S$和一个局部动作$a_i ∈ A$，与其他智能体的交互通过一个聚合效应μ（也称为平均场项）来捕捉，该效应是智能体局部状态和动作经验分布的函数。具体来说，在第t个时间步，当智能体i在状态$s_{it}$采取动作$a_{it}$并且平均场项为$μ_t$时，它收到一个即时奖励$R(s_{it}, a_{it}, μ_t)$，其局部状态演化为$s_{it+1} ∼ P(· | s_{it}, a_{it}, μ_t) ∈ ∆(S)$。因此，从智能体i的角度来看，它不是参与一个多智能体博弈，而是面临一个由平均场项序列${μ_t}{t≥0}$参数化的时变MDP，而这个序列又由所有智能体的状态和动作决定。MFGs中的解概念是平均场均衡，它是一个策略和平均场项的序列对${\pi^_t, μ^_t}$，满足以下两个条件：(1) $\pi^ = {\pi^t}$是μ = ${μ^t}$指定的时变MDP的最优策略，(2) μ是在每个智能体都遵循策略$\pi^$时生成的。离散时间MFGs的平均场均衡的存在性已在【324, Saldi, N., Bas¸ar, T., Raginsky, M.: Markov–Nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization 56(6), 4256–4287 (2018)】,【325, Saldi, N., Bas¸ar, T., Raginsky, M.: Approximate Nash equilibria in partially observed stochastic games with mean-field interactions. Mathematics of Operations Research (2019)】,【326, Saldi, N.: Discrete-time average-cost mean-field games on Polish spaces. arXiv preprint arXiv:1908.08793 (2019)】,【327, Saldi, N., Bas¸ar, T., Raginsky, M.: Discrete-time risk-sensitive mean-field games. arXiv preprint arXiv:1808.03929 (2018)】中研究，它们的构造性证明表明平均场均衡可以通过不动点迭代获得。具体来说，可以构造一个策略和平均场项的序列${\pi^{(i)}}{i≥0}$和${μ^{(i)}}}}$，使得${\pi^{(i){t≥0}$解决了由$μ^{(i)}$指定的时变MDP，而$μ^{(i+1)}$是在所有玩家都采用策略$\pi^{(i)}$时生成的。遵循这一议程，提出了各种无模型RL方法来解决MFGs，其中${\pi^{(i)}}$生成的平均场项。请注意，上述工作主要关注有限时间范围【330】,【331】或平稳平均场均衡【328】,【24】,【329】的设置。相反，最近的工作【332, Anahtarci, B., Kariksiz, C.D., Saldi, N.: Value iteration algorithm for mean-field games. arXiv preprint arXiv:1909.01758 (2019)】,【333, Zaman, M.A.u., et al.: Approximate equilibrium computation for discrete-time linear-quadratic mean-field games. Submitted to IEEE American Control Conference (2020)】考虑了无限时间范围设置中可能非平稳的平均场均衡，并开发了为无模型RL算法奠定基础的均衡计算算法。}$通过单智能体RL（如Q学习【328, Guo, X., et al.: Learning mean-field games. arXiv preprint arXiv:1901.09585 (2019)】和基于策略的方法【24, Subramanian, J., Mahajan, A.: Reinforcement learning in stationary mean-field games. In: International Conference on Autonomous Agents and Multi-Agent Systems, pp. 251–259 (2019)】,【329, Fu, Z., et al.: Actor-critic provably finds Nash equilibria of linear-quadratic mean-field games. arXiv preprint arXiv:1910.07498 (2019)】）近似求解，而${μ^{(i)}}_{i≥0}$通过采样估计。此外，【330, Hadikhanloo, S., Silva, F.J.: Finite mean field games: Fictitious play and convergence to a first order continuous mean field game. Journal de Mathematiques Pures et Appliqu ´ ees ´ (2019)】,【331, Elie, R., et al.: Approximate fictitious play for mean field games. arXiv preprint arXiv:1907.02633 (2019)】最近提出了平均场状态的虚拟博弈更新，其中$μ^{(i+1)} = (1 - α^{(i)}) · μ^{(i)} + α^{(i)} · \hat{μ}^{(i+1)}$，α(i)是学习率，$\hat{μ}^{(i+1)}$是由策略$\pi^{(i)

A4 应用亮点（总结）

本节简要回顾了由前一节介绍的方法驱动的MARL最近的经验性成功。下面，我们重点关注§4中回顾的三个MARL设置，并为每个设置突出四个代表性且实际的应用，如图3所示。

图3：MARL近期成功的四个代表性应用：无人机、围棋、扑克游戏和团队对战视频游戏。

5.1 合作设置

无人机

无人机（UAVs）应用概述。MARL的一个突出应用是控制实际的多智能体系统，其中大部分是合作和分布式的。场景示例包括机器人团队导航【183】、智能电网运营【180】以及移动传感器网络的控制【16】。这里我们选择无人机（UAVs）【334, 335, 336, 337, 338, 339】作为多智能体自主系统最近兴起的一个代表性应用场景。具体来说，一个UAV团队被部署来完成一个合作任务，通常没有任何中央控制器的协调，即以分布式方式进行。每个UAV通常配备有通信设备，以便它们可以与一些队友交换信息，前提是它们在其感知和覆盖范围内。因此，该应用自然地符合我们在§4.1.2中提倡的带网络智能体的分布式范式，如图2(b)所示。由于UAVs的高机动性，智能体之间的通信链路确实是时变和脆弱的，使得（在线）合作极具挑战性。因此，在合作UAVs的背景下出现了各种挑战，其中一些最近已由MARL解决。

MARL在UAVs中的具体应用。在【334】中，考虑了UAVs的最优链路发现和选择问题。每个UAV u ∈ U 能够感知本地可用信道，并在与另一个智能体v ∈ U 共享的公共信道上选择一个连接链路。每个UAV u 都有其本地信道集Cu，且Cu ∩ Cv ≠ ∅。当两个相邻的UAV同时在同一信道上宣布其消息时，它们之间就建立了一个连接链路。每个UAV的局部状态是前一个消息是否成功发送，其动作是选择一对(v, chu)，其中v是u可以到达的队友，chu是其本地信道。本地信道chu ∈ Cu的可用性被建模为概率性的，奖励Ru由成功发送的消息数量计算。本质上，【334】中的算法基于独立Q学习【139】，但使用了两种启发式方法来提高可处理性和收敛性能：通过分数切片，它独立处理动作空间的每个维度（分数），并通过所有分数的平均值来估计实际的Q值；通过相互采样，它共享状态-动作对和相互Q函数参数。
【335】解决了区域覆盖问题，其中UAVs旨在完全覆盖一个未知区域，同时最小化其视野之间的重叠部分。该问题被建模为一个马尔可夫团队，整体状态s是所有局部状态si的拼接，si被定义为其在环境中的三维位置坐标。每个智能体选择朝不同方向前进，或上升下降，产生6种可能的动作。开发了一个基于联合动作空间的多智能体Q学习，并使用线性函数逼近。
相比之下，【337】关注UAV网络中的频谱共享。在远程传感任务下，UAVs被分为两类：提供中继服务的中继UAVs和其他为剩余执行传感任务的UAVs获取频谱接入的UAVs。这样的问题可以被建模为一个确定性MMDP，因此可以通过【87】中提出的分布式Q学习来解决，并保证最优性。
此外，【339】考虑了多个UAVs同时进行目标分配和路径规划的问题。具体来说，一个UAV团队旨在覆盖所有目标Tj，同时避免与威胁区域Di以及其他UAVs发生碰撞。通过在奖励函数中惩罚碰撞，这样的问题可以被表征为一个包含合作和竞争智能体的混合MARL设置。因此，采用了【26】中提出的MADDPG算法，采用中心化学习-分布式执行的方案。
其他可以由MARL解决的任务包括：使用基于Q学习的方法在UAV赋能的通信网络中进行资源分配【338】，以及在纯粹中心化的方式下使用策略优化方法进行UAV机队控制的空中监视和基地防御【336】。

学习通信

学习通信问题。合作MARL的另一个应用旨在在没有明确人类监督的情况下，促进智能体团队之间的沟通和协调。这类问题通常被表述为涉及N个智能体的Dec-POMDP，这与定义2.2中介绍的马尔可夫博弈类似，只是每个智能体无法观察状态s ∈ S，并且每个智能体具有相同的奖励函数R。更具体地说，我们假设每个智能体i ∈ N通过一个有噪声的观测信道Oi : S → P(Yi)从集合Yi接收观测，使得当环境处于状态s时，智能体i观察到一个随机变量yi ∼ Oi(· |s)。请注意，当存在一个中央规划器收集每个智能体的观测并为每个智能体决定动作时，该模型可以被视为一个POMDP。由于观测信道有噪声，在这种模型中，智能体需要相互通信，以便更好地推断底层状态并做出最大化所有智能体共享的期望回报的决策。设$N_i^t ⊆ N$是智能体i在时间步t的邻居，即智能体i能够在时间t从任何智能体$j ∈ N_i^t$接收消息$m_{j \to i}^t$。设$I_i^t$表示智能体i截至时间t收集的信息，定义为

它包含了其在之前时间步收集的历史和在时间t收到的观测。利用信息$I_i^t$，智能体i采取一个动作$a_i^t ∈ A_i$，并向所有$i ∈ N_j^t$的智能体j广播消息$m_{i \to j}^t$。也就是说，智能体i的策略$π_i^t$是从$I_i^t$到一个（随机）动作$a_i^t = (a_i^t, {m_{i \to j}^t : i ∈ N_j^t})$的映射，即$a_i^t ∼ π_i^t(· | I_i^t)$。注意到信息集$I_i^t$的大小随着t的增长而增长。为了处理内存问题，通常首先通过循环神经网络（RNN）或长短期记忆（LSTM）【340】将$I_i^t$嵌入一个固定的潜在空间，并在此嵌入特征之上定义价值和策略函数。此外，该研究领域的大多数现有工作都采用中心化学习的范式，并利用权重共享或注意力机制【341】等技术来提高计算效率。通过中心化学习，Q学习和演员-评论家等单智能体RL算法可以直接适用。

学习通信的算法。特别地，【21】首次提出通过深度Q学习来解决学习通信的问题。他们建议使用两个Q网络，分别管理采取动作ai ∈ A和产生消息。他们的训练算法是深度循环Q学习（DRQN）【342】的扩展，它结合了RNN和深度Q学习【10】。继【21】之后，各种工作【343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354】提出了多种神经网络架构来促进智能体之间的沟通。这些工作将单智能体RL方法与深度学习的新发展相结合，并通过实证研究展示其性能。在这些工作中，【346, 345, 348, 353, 354】报告了当RL算法从零开始用文本或图像输入进行训练时，智能体之间出现了计算性通信协议。我们评论说，由于中心化学习，这些工作中使用的算法更类似于单智能体RL。有关多智能体通信的更详细概述，我们建议感兴趣的读者参考【42】的第6节和【20】的第3节。

5.2 竞争设置

关于竞争设置，下面我们重点介绍MARL在围棋和德州扑克中的最新应用，它们分别是双人完美信息和部分信息扩展形式博弈的典型实例。

围棋

围棋游戏规则与模型。围棋是一种由两名竞争玩家进行的棋盘游戏，目标是在棋盘上包围比对手更多的领地。这两名玩家分别使用白色或黑色的棋子，轮流将棋子放在19×19的棋盘上，代表他们的领地。在每一步中，玩家可以将棋子放在棋盘上总共361个未被占用的位置中的任意一个。一旦放在棋盘上，棋子就不能移动。但当棋子被对方的棋子完全包围时，它们将从棋盘上被移除。当双方都不愿意或无法再走一步时，游戏结束，胜者通过计算领地面积和被俘获的棋子数量来确定。

围棋的MARL模型。围棋可以被看作是一个具有确定性状态转移的双人零和马尔可夫博弈，奖励只在游戏结束时出现。这个马尔可夫博弈的状态是棋盘的当前配置，奖励为1或-1，分别代表赢或输。具体来说，对于任何状态s ∈ S，我们有r1(s) + r2(s) = 0，当s是终止状态时，r1(s), r2(s) ∈ {1, -1}，否则r1(s) = r2(s) = 0。令$V_i^*(s)$表示玩家i ∈ {1, 2}的最优价值函数。因此，在这种情况下，$[1 + V_i(s)]/2$是当当前状态为s且双方都遵循纳什均衡策略时，玩家i ∈ {1, 2}获胜的概率。此外，由于这个马尔可夫博弈是回合制的，已知两名玩家的纳什均衡策略是确定性的【234】。此外，由于棋盘的每种配置都可以由两名玩家的一系列移动构建而成（因为转移是确定性的），我们也可以将围棋视为一个具有完美信息的扩展形式博弈。由于其巨大的状态空间，这个问题极具挑战性。据【355】估计，状态空间的大小超过$10^{360}$，这使得任何传统的强化学习或搜索算法都无法使用。

AlphaGo。一个重大的突破是由【1】中介绍的AlphaGo实现的，这是第一个在全尺寸棋盘上击败人类职业选手的计算机围棋程序。AlphaGo整合了深度学习和强化学习的多种思想，并通过使用深度卷积神经网络（CNN）【356】来表示策略和价值函数，从而应对巨大状态空间的挑战。具体来说，策略网络和价值网络都是13层的CNN，具有相同的架构，一个棋盘配置由48个特征表示。因此，策略和价值网络都接受大小为19×19×48的输入。这两个网络通过一种新颖的组合方式进行训练，即结合了来自人类专家数据的监督学习和来自蒙特卡洛树搜索（MCTS）及自博弈的强化学习。具体来说，在第一阶段，策略网络通过监督学习进行训练，以预测人类玩家的动作，数据集包含来自KGS围棋服务器的3000万个位置。也就是说，对于数据集中的任何状态-动作对(s, a)，动作a被视为响应变量，状态s被视为协变量。策略网络的权重通过随机梯度上升进行训练，以最大化似然函数。在通过监督学习初始化策略网络后，在流水线的第二阶段，策略和价值网络都通过强化学习和自博玩进行训练。具体来说，新数据由当前策略网络和策略网络的随机先前迭代之间进行的博弈生成。此外，策略网络遵循策略梯度进行更新，价值网络旨在找到与策略网络相关的价值函数，并通过最小化均方预测误差进行更新。最后，在下棋时，策略和价值网络的当前迭代被结合起来，通过MCTS进行前瞻性搜索，以产生一个改进的策略。AlphaGo采取的实际行动由这样的MCTS策略决定。此外，为了提高计算效率，AlphaGo使用异步和分布式的MCTS版本来加速模拟。

AlphaGo Zero。自AlphaGo问世以来，一个改进版本，即AlphaGo Zero，在【2】中被提出。与vanilla AlphaGo相比，AlphaGo Zero不使用监督学习来初始化策略网络。相反，策略和价值网络完全通过强化学习和自博弈从零开始训练。此外，AlphaGo Zero中的策略和价值网络不是共享相同网络架构的独立函数，而是被聚合成一个单一的神经网络结构。具体来说，策略和价值函数由$(p(s), V(s)) = f_θ(s)$表示，其中s ∈ S是表示当前棋盘的状态，fθ是一个参数为θ的深度CNN，V(s)是对应于价值函数的标量，p(s)是表示策略的向量，即对于每个条目a ∈ A，$p_a(s)$是在状态s采取动作a的概率。因此，在这样的网络结构下，策略和价值网络自动共享相同的状态低层表示。此外，网络fθ的参数θ通过自博弈和MCTS进行训练。具体来说，在每个时间步t，基于fθ给出的策略p和价值V，可以获得一个MCTS策略$π_t$，并根据策略$π_t(s_t)$执行一个移动。这个模拟过程一直持续到当前游戏结束。然后记录第t个时间步的结果$z_t ∈ {1, -1}$，从第t个时间步的玩家的角度来看。然后，通过在损失函数`t上执行一个随机梯度步骤来更新参数θ，该损失函数定义为

因此，`t是价值函数的均方预测误差、策略网络和MCTS策略之间的交叉熵损失以及用于正则化的权重衰减项的总和。据报道，AlphaGo Zero击败了之前AlphaGo的最强版本，并且它还展示了以前未被发现的非标准围棋策略。最后，AlphaGo Zero中采用的技术已推广到其他具有挑战性的棋盘游戏。具体来说，【357】提出了AlphaZero程序，该程序通过自博弈和零人类知识的强化学习进行训练，并在国际象棋、将棋和围棋等游戏中取得了超人的表现。

德州扑克

德州扑克概述。MARL在竞争设置中的另一个卓越应用成就集中在开发德州扑克的人工智能上，这是扑克最流行的变种之一。德州扑克通常由两个或更多玩家进行，每个玩家首先会面朝下发两张私牌。然后分三轮面朝上发五张公共牌。在每一轮中，每个玩家有四种可能的行动——看牌、跟注、加注和弃牌。所有牌发完后，每个未弃牌的玩家总共有七张牌，包括五张公共牌和两张私牌。然后，这些玩家中的每一个都从这七张牌的所有组合中找出最好的五张牌扑克手牌。手牌最好的玩家是赢家，并赢得该手牌中所有玩家下的赌注，也称为底池。请注意，德州扑克的每一手牌在三轮后结束，玩家的收益只有在手牌结束后才知道。还要注意的是，每个玩家都不知道其他玩家的私牌。因此，德州扑克是具有不完全信息的多人扩展形式博弈的一个实例。当只有两名玩家时，该游戏称为单挑。当赌注大小和允许的加注次数都固定时，该游戏称为限注德州扑克。然而，在无限注德州扑克中，每个玩家可以下注或加注任何金额，最高可达该玩家在桌上的所有钱，只要它超过之前的下注或加注。

德州扑克AI发展。二十多年来，人们一直在寻求开发超人计算机扑克程序【358, 113】。各种方法已在简单的扑克变种如库恩扑克【359】和勒杜克德州扑克【360】中显示出成功。然而，完整的德州扑克要具有挑战性得多，并且直到最近才取得了一些突破。德州扑克的最简单版本是单挑限注德州扑克（HULHE），总共有$3.9 × 10^{14}$个信息集【361】，玩家需要在每个信息集处采取行动。【361】首次报道通过CFR+【293, 294】（反事实遗憾最小化【109】的一个变体）将HULHE求解到近似纳什均衡。随后，其他方法如神经虚拟自博弈【25】和带自博弈的蒙特卡洛树搜索【362】也已成功用于解决HULHE。

HUNL的突破。尽管取得了这些突破，但用人工智能解决单挑无限注德州扑克（HUNL）直到最近仍然是一个开放问题，它有超过$6 × 10^{161}$个信息集，这是一个天文数字。因此，在HUNL中，遍历所有信息集（以今天的计算能力）是不可能的，这使得应用像【361】中的CFR+变得不可行。最近，由DeepStack【363】和Libratus【364】两个独立开发的计算机扑克程序取得了突破性成就，它们首次在HUNL中击败了人类职业扑克玩家。这两个程序都采用CFR作为其算法框架的骨干，但采用不同的策略来处理游戏的巨大规模。具体来说，DeepStack应用深度学习来学习游戏的良好表示，并提出了深度反事实价值网络来整合深度学习和CFR。此外，DeepStack采用有限深度前瞻规划，将巨大的$6 × 10^{161}$个信息集减少到不超过$10^{17}$个信息集，从而使得枚举所有信息集成为可能。相比之下，Libratus不使用任何深度学习技术。相反，它通过计算游戏的抽象来减小游戏的规模，这是可能的，因为许多信息集非常相似。此外，它通过使用不完美信息博弈的子博弈分解技术【365, 366, 367】以及构建子博弈的细粒度抽象来进一步降低复杂性。当抽象构建好后，使用蒙特卡洛CFR【281, 282, 283】的改进版本来计算策略。此外，最近，基于Libratus，【8】提出了Pluribus，一个计算机扑克程序，它已被证明在六人无限注德州扑克中比顶级人类专业人士更强。Pluribus的成功归功于文献中出现的以下技术：大规模不完美信息博弈的抽象和子博弈分解、蒙特卡洛CFR、自博弈和深度有限搜索。

其他应用

星际争霸II。此外，MARL的另一个流行试验平台是星际争霸II【368】，这是一款非常受欢迎的多人实时策略电脑游戏。该游戏可以被表述为一个具有部分观测的多智能体马尔可夫博弈，其中每个玩家只对游戏状态有有限的信息。为星际争霸II设计强化学习系统极具挑战性，因为它需要在不确定性和不完全信息下做出决策，考虑长期的最优策略，并设计能够引发学习的良好奖励函数。自发布以来，星际争霸II的完整游戏和子游戏版本都引起了巨大的研究兴趣。最近由【369】提出的AlphaStar在该游戏中取得了突破，它在零和双人完整游戏星际争霸II中展示了超人的表现。其强化学习算法结合了用于策略和价值函数参数化的LSTM、用于策略更新的异步演员-评论家【370】以及用于均衡发现的神经虚拟自博弈【25】。

5.3 混合设置

混合设置的研究现状。与合作和竞争设置相比，混合设置下的MARL研究相对较少。该设置下的一个应用是多人扑克。正如我们在§5.2中提到的，【8】中介绍的Pluribus在六人无限注德州扑克中展示了超人的表现。此外，作为§5.1中介绍的学习通信问题的扩展，有一系列研究旨在应用MARL来解决学习社会困境的问题，这通常被表述为一个具有部分信息的多智能体随机博弈。因此，在这些设置下提出的大多数算法都结合了RNN或LSTM来学习智能体经历的历史的表示，并且这些算法的性能通常通过实验结果来展示；例如，参见【19, 371, 372】及其参考文献。

Dota 2。此外，混合设置的另一个例子是智能体被分为两个对立的团队进行零和博弈。团队的奖励由该团队内的每个玩家共享。与双人零和博弈相比，这种设置更具挑战性，因为它既需要考虑队友之间的合作，也需要考虑与对方团队的竞争。这种情况的一个突出试验平台是Dota 2视频游戏，其中两个团队，每个团队有五名玩家，旨在征服对方团队的基地并保卫自己的基地。每个玩家独立控制一个被称为英雄的强大角色，并且只能通过屏幕上的视频输出来观察游戏状态。因此，Dota 2是一个由两个团队进行的零和马尔可夫博弈，每个智能体对游戏的信息都不完全。对于这个具有挑战性的问题，2018年，OpenAI提出了OpenAI Five AI系统【3】，该系统具有超人的表现，并在电子竞技游戏中击败了人类世界冠军。其算法框架整合了用于学习良好表示的LSTM和用于策略学习的近端策略优化【72】与自博弈。此外，为了平衡有效的协调和通信成本，OpenAI Five没有在团队之间设置明确的通信渠道，而是通过一个名为“团队精神”的超参数来塑造奖励，以平衡每个英雄的个人奖励函数和团队平均奖励函数之间的相对重要性。

A5 结论与未来方向（总结）

多智能体强化学习（MARL）鉴于其在涉及多个动作和信息耦合的智能体进行序列决策的普遍性，长期以来一直是强化学习领域中一个活跃且重要的研究方向。与其巨大的经验成功形成鲜明对比的是，MARL算法的理论理解被公认为具有挑战性且在文献中相对缺乏。确实，为MARL建立一个全面的理论需要跨越动态规划、博弈论、优化理论和统计学等领域的工具，将这些工具统一并在一个框架内进行研究并非易事。

本章对近期主要由理论分析支持的MARL算法进行了选择性综述，并介绍了一些已被解决的高难度应用。我们遵循经典综述【11】的思路，将算法分为三组：解决完全合作问题、完全竞争问题以及两者混合问题的算法。与现有的MARL综述不同，本章强调了MARL理论的几个新视角和分类法，其中一些源于我们自己的研究努力和兴趣。我们注意到，我们的综述不应被视为全面的，而应被视为由我们自己的兴趣和专业知识决定的重点综述，这应该会吸引有相似兴趣的研究人员，并为这个广泛主题领域的未来研究方向提供刺激。因此，我们确定了以下对MARL理论未来研究至关重要且开放的途径。

部分可观测设置：在许多实际的MARL应用中，系统状态和其他智能体动作的部分可观测性是典型且不可避免的。通常，这些设置可以建模为部分可观测随机博弈（POSG），其中包括具有共同奖励函数的合作设置，即Dec-POMDP模型，作为一个特例。然而，正如§4.1.3所指出的，即使是合作任务也是NEXP完备的【104】，并且难以解决。实际上，与POMDP中仅需对状态建立信念相比，POSG中用于最优决策的信息状态可能非常复杂，并涉及对对手策略的信念生成【119】。这种困难本质上源于智能体因其从模型中获得的自身观测而产生的异构信念，这是§3中提到的由于各种信息结构而导致的MARL的固有挑战。从推广用于解决Dec-POMDP的中心化学习-分布式执行方案【121, 152】来解决POSG开始可能是可行的。

深度MARL理论：如§3.3所述，使用深度神经网络进行函数逼近可以解决MARL中的可扩展性问题。实际上，最近MARL的大多数经验成功都源于DNN的使用【25, 26, 27, 28, 29】。然而，由于缺乏理论支持，我们在本章中没有包含这些算法的细节。最近，已经有少数尝试去理解几种单智能体深度RL算法的全局收敛性，例如神经TD学习【373】和神经策略优化【79, 78】，当使用过参数化神经网络【374, 375】时。因此，将这些结果扩展到多智能体设置，作为迈向深度MARL理论理解的第一步，是很有希望的。

基于模型的MARL：文献中很少有MARL算法是基于模型的，即首先估计MARL模型，然后将其用作名义模型来设计算法，这可能有点令人惊讶。据我们所知，现有的基于模型的MARL算法仅包括早期的【376】中解决单控制器随机博弈（一种特殊的零和MG）的算法；以及后来的改进版【377】，名为R-MAX，用于零和MG。这些算法也建立在“面对不确定性时的乐观主义”原则之上【243, 244】，与前面提到的几种无模型算法一样。考虑到基于模型的RL的最新进展，特别是其在某些情况下相对于无模型方法的已证优势【378, 379】，将这些结果推广到MARL以提高其样本效率是值得的。

策略梯度方法的收敛性：如§4.3所述，vanilla策略梯度方法在一般MARL中的收敛结果大多是负面的，即在许多情况下它甚至可能避开局部NE点。这本质上与MARL中的非平稳性挑战有关，见§3.2。尽管已经提出了一些补救措施【312, 321, 322, 311】来稳定一般连续博弈中的收敛，但这些假设在MARL中不易验证/满足，例如，即使在最简单的LQ设置中【315】，因为它们不仅依赖于模型，还依赖于策略参数化。由于这种微妙之处，探索MARL中基于策略的方法的（全局）收敛性可能很有趣，可能从简单的LQ设置开始，即一般和LQ博弈，类似于零和对应物【34, 306】的研究。这种探索也可能受益于非凸-（非）凹优化【380, 33, 314】的最新进展。

具有鲁棒性/安全性考量的MARL：关于MARL中非唯一学习目标的挑战（见§3.1），我们认为在MARL中考虑鲁棒性和/或安全约束是有价值的。据我们所知，这仍然是一个相对未知的领域。实际上，安全RL已被认为是单智能体设置中最重大的挑战之一【381】。当有多个可能具有冲突目标的智能体时，保证安全变得更加复杂，因为安全要求现在涉及到所有智能体的耦合。一个直接的模型是受约束的多智能体MDPs/马尔可夫博弈，其中约束表征了安全要求。在该设置下进行具有可证明安全保证的学习并非易事，但对于某些安全关键的MARL应用（如自动驾驶【9】和机器人技术【5】）是必要的。此外，考虑对对抗性智能体的鲁棒性也是自然的，特别是在分布式/合作MARL设置中，如【23, 130, 96】，其中对手可能以匿名方式干扰学习过程——这是分布式系统中的常见情况。最近在对抗拜占庭对手的鲁棒分布式监督学习方面的发展【382, 383】可能在这方面有用。