长期以来，人们已经认识到，由于状态和动作空间的大小在代理数量上呈指数级增长，多代理强化学习（MARL）面临着显著的可扩展性问题。在本文中，我们识别了一类丰富的网络MARL问题，其中模型表现出局部依赖结构，允许以可扩展的方式解决该问题。具体而言，我们提出了一种可扩展的演员-评论家（SAC）方法，该方法可以学习接近最优的局部策略，以优化平均奖励，并根据局部邻域的状态动作空间大小（而不是整个网络）进行复杂度缩放。我们的结果集中在识别和利用指数衰减特性上，该特性确保代理对彼此的影响在它们的图形距离上以指数方式快速衰减。
由于其在游戏（Silver等人，2016；Mnih等人，2015）、机器人（Duan等人，2016）和自动驾驶（Li等人，2019）等一系列领域中令人印象深刻的性能，强化学习（RL）已成为决策和控制的一种有前途的工具，人们对RL在多智能体系统中的使用重新产生了兴趣，即多智能体RL（MARL）。与单代理RL相比，MARL的多代理方面带来了额外的挑战。一个核心挑战是可扩展性。即使单个代理的状态或动作空间很小，全局状态空间或动作空间也可以从代理数量呈指数级增长的一组大小中取值。这种“维度诅咒”在许多情况下使问题变得棘手。例如，RL算法（如时间差（TD）学习或Q学习）需要存储Q函数（Bertsekas和Tsitsiklis，1996），其大小与状态动作空间相同，在MARL中，状态动作空间的n呈指数级大。在文献中，在各种设置中观察到了这种可伸缩性问题，包括Blondel和Tsisiklis（2000）；Papadimitriou和Tsitsiklis（1999）；Zhang等人（2019）；卡恩斯和科勒（1999）；Guestrin等人（2003）。为了解决可扩展性问题，近年来出现的一种有希望的方法是利用问题结构，例如（Gu等人，2020；Qu和Li，2019；Qu等人，2019）。一种有前景的结构形式是强制局部交互，即代理与图相关联，它们只与图中的附近代理交互。这种局部交互在联网系统中很常见，包括流行病（Mei等人，2017）、社交网络（Chakrabarti等人，2008；Llas等人，2003）、通信网络（Zocca，2019；Vogels等人，2003年）、排队网络（Papadimitriou和Tsitsiklis，1999）、智能交通（Zhang和Pavone，2016）、智能建筑系统（Wu等人，2016；Zhang等人，2017年）。与局部相互作用相关的一个强大特性是所谓的指数衰减特性（Qu等人，2019），也称为相关性衰减（Gamarnik，2013；Gamarni等人，2014）或空间衰减（Bamieh等人，2002；Motee和Jadbabaie，2008），其表示，代理对彼此的影响在其图形距离内呈指数衰减。指数衰减特性通常导致优化和控制的可扩展分布式算法的潜力（Gamarnik，2013；Bamieh等人，2002；Motee和Jadbabaie，2008），并已证明对MARL有效，例如Qu等人（2019）。尽管利用MARL中的局部相互作用和指数衰减已被证明是有效的，但迄今为止，仅在将总报酬贴现作为目标的情况下得出了结果，例如，（Qu等人，2019）。这是自然的，因为关注平均报酬（即平稳性报酬）的结果更难推导，并且需要不同的技术，即使在单代理RL设置中也是如此（Tsitsiklis和Van Roy，1999）。然而，在许多联网系统应用中，平均报酬是一个更自然的目标。例如，在通信网络中，最常见的目标是系统在平稳性方面的性能（例如吞吐量）。在本文中，我们的目标是导出网络系统中平均奖励MARL的结果。然而，目前尚不清楚是否有可能获得与Qu等人（2019）类似的结果，后者侧重于折扣奖励。在平均报酬情况下，Qu等人（2019）利用的指数衰减特性一般不再成立，因为平均报酬情况可以在最坏情况下捕获某些NP难问题。例如，Blondel和Tsitsiklis（2000）；惠特尔（1988）；Papadimitriou和Tsitsiklis（1999）都指出，这种具有产品状态和动作空间的马尔可夫决策过程（MDP）本质上是组合的，并且在最坏的情况下从计算复杂性的角度来看是难以解决的。
