基于模型的多智能体强化学习在零和 Markov 博弈中的近似最优样本复杂度

MMJul, 2020

基于模型的多智能体强化学习在零和 Markov 博弈中的近似最优样本复杂度

Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity

Kaiqing Zhang, Sham M. Kakade, Tamer Başar, Lin F. Yang

TL;DR本文探究了基于模型的强化学习算法在多智能体环境中的样本复杂度，通过两人零和马尔科夫博弈问题的研究发现，此种算法的样本复杂度为大 O （SA（1-γ）-3ε-2）, 优于其他方法，但其依赖于动作空间大小，存在一定局限性。

Abstract

model-based reinforcement learning (RL), which finds an optimal policy using an empirical model, has long been recognized as one of the corner stones of RL. It is especially suitable for multi-agent rl (MARL), as

model-based reinforcement learning multi-agent rl sample complexity nash equilibrium value marl setting

发现论文，激发创造

无模型改进的零和马尔科夫博弈的高效样本算法

为了解决两个玩家零和马尔可夫博弈问题，在多智能体强化学习的理论研究中引起了越来越多的关注。通过提出一种无模型的基于阶段的 Q 学习算法，我们展示了该算法能够与最佳的有模型算法达到相同的样本复杂度，进而首次证明了无模型算法在与模型有关的 $H$ 上的依赖性上能够达到相同的最优性。

Aug, 2023

基于模型的多智能体强化学习：最新进展和前景展望

本文回顾了现有的关于基于模型的多智能体强化学习的研究，包括理论分析、算法和应用，并分析了基于模型的多智能体强化学习的优势和潜力。此外，我们提供了算法的详细分类，并根据多智能体情景中固有的挑战指出每个算法的优点和缺点。最后，我们总结了这一领域未来发展的有前途的方向。

Mar, 2022

改进分散式多智能体强化学习的无模型算法

本文针对多智能体强化学习算法在代理数目增多时出现的采样复杂度指数级增长的现象，提出了一些去中心化的学习算法，并在几个关键的方面上做了优化，同时通过数值仿真验证我们理论的有效性。

Oct, 2021

基于模型的自我对弈强化学习的严密分析

本文针对多智能体马尔科夫博弈提出了一种基于模型的算法 Nash-VI，在理论上证明其具有较高的样本利用率，并且在实验中证明了其优于现有的基于模型的方法和一些基于无模型的算法，输出单个 Markov 策略且易于存储和执行。

Oct, 2020

高效的多智能体强化学习规划

多智能体强化学习算法（MARL）通过采取模型化方法来提高样本效率并在多个任务中表现出可比或更好的性能。

May, 2024

多智体决策的复杂性：从博弈中的学习到部分监控

本文研究了多智能体强化学习中的样本效率、均衡计算和统计复杂性等问题，提出了一系列新的结构性结果，并阐述了决策时附带隐藏报酬的统计复杂度。

May, 2023

高效的样本有效的多智能体强化学习：优化视角

我们研究了多智能体强化学习 (MARL) 在一般和马尔可夫博弈 (MG) 下具有一般函数逼近的情况。通过引入一种新颖的复杂度度量，即多智能体解耦系数 (MADC)，我们旨在找到基于样本高效学习的最小假设。利用该度量，我们提出了首个统一的算法框架，可以在低 MADC 的情况下保证在模型为基础和模型无关的 MARL 问题中学习纳什均衡、粗粒度相关均衡和相关均衡的样本效率性。此外，我们还展示了与现有工作相比，我们的算法提供了可比较的次线性遗憾。此外，我们的算法结合了一个均衡求解器和一个单一目标优化次程序，用于求解每个确定性联合策略的正则化收益，从而避免在数据相关的约束条件下求解约束优化问题 (Jin et al. 2020; Wang et al. 2023)，或在复杂的多目标优化问题 (Foster et al. 2023) 中执行抽样过程，因此更适合于实证实现。

Oct, 2023

自适应约束下的自训练近最优强化学习

多智能体强化学习中，通过引入自适应约束，我们设计一种基于消除的算法，在低批次复杂度下实现了对马尔可夫博弈的极小后悔，并且证明了匹配上界的批次复杂度下限，进一步地在理解低适应性的多智能体强化学习方面提供了首个一系列结果。

Feb, 2024

部分可观马尔可夫博弈中高效学习的样本有效强化学习

本文研究了多智能体强化学习在部分可观察性下的挑战性任务，其中每个智能体只能看到自己的观察和动作。我们通过考虑广义模型的部分可观察马尔科夫博弈，证明了一个富裕的子类可以使用样本高效的学习方法，从而找到弱显式部分可观察马尔科夫博弈的近似纳什均衡、相关均衡以及粗略相关均衡，当代理数量很小时可在多项式样本复杂度内学得。

Jun, 2022

通过生成模型在模型为基础的强化学习中突破样本量限制

研究强化学习的样本效率，证明了两种算法的最小最优性，同时实现了目标准确率的最小最优样本复杂度，这是目前首次提供涵盖整个样本范围的最小最优保证。

May, 2020