《论多智能体决策的复杂性：从博弈学习到部分监控》115页

多智能体强化学习（MARL）理论的一个核心问题是，了解哪些结构条件和算法原理会导致样本高效学习保证，以及当我们从少数智能体转向多数智能体时，这些考虑因素会发生怎样的变化。我们在多智能体互动决策的一般框架中研究了这一问题，包括具有函数逼近的马尔可夫博弈和具有强盗反馈的正态博弈。我们的重点是均衡计算，其中集中式学习算法旨在通过控制与（未知）环境交互的多个智能体来计算均衡。我们的主要贡献如下

• 提供了多智能体决策最优样本复杂度的上下限，其基础是决策估计系数（Decision-Estimation Coefficient）的多智能体广义化；决策估计系数是 Foster 等人（2021 年）在与我们的设置相对应的单智能体中引入的一种复杂度度量。与单智能体环境下的最佳结果相比，我们的上界和下界都有额外的差距。我们的研究表明，任何 “合理 ”的复杂性度量都无法弥补这些差距，这凸显了单个智能体与多个智能体之间的显著差异。

• 表征多智能体决策的统计复杂性，等同于表征单智能体决策的统计复杂性，只不过奖励是隐藏的（无法观察到的），这个框架包含了部分监控问题的变体。由于这种联系，我们尽可能地描述了隐藏奖励交互决策的统计复杂性。

在此基础上，提供了几个新的结构性结果，包括：1）多智能体决策的统计复杂性可以降低到单智能体决策的统计复杂性的条件；2）可以避免所谓的多智能体诅咒的条件。

由于篇幅所限，正文对研究结果作了非正式的概述，详细说明放在附录的第 I 部分。第 II 部分给出了示例。附录组织概览见附录 A。