Feb, 2024

独立线性函数逼近的马尔可夫博弈的优化样本复杂度

PDF
TL;DR本文首次通过对 Wang 等人 (2023) 的 AVLPR 框架进行优化，应用基于数据的悲观估计来解决 “多智能体诅咒”，并提出了新颖的 “动作相关奖励” 方法，通过拓展选择插件算法的范围，结合单智能体强化学习领域的最新技术，提出了一种同时解决了多智能体诅咒问题、达到了最佳的 O (T^-1/2) 收敛速率以及避免了多项式依赖的算法。
markov gamesmulti-agent reinforcement learningcurse of multi-agentsavlpr frameworkaction-dependent bonuses
发现论文，激发创造
  • 在大状态空间中打破多智体的诅咒：独立线性函数逼近的马尔可夫博弈中的强化学习

    我们提出了一种新模型独立线性马尔可夫游戏，用于具有大状态空间和大量代理的多代理强化学习，该模型具有独立线性函数逼近，并为其设计了新算法以学习 Markov 粗糙关联均衡和 Markov 相关均衡，其采样复杂度只随着每个代理自己的函数类复杂度以多项式方式扩展，从而打破了多代理的诅咒。

    Feb, 2023

  • 大规模马尔可夫潜在博弈的独立策略梯度：更快收敛速率，函数逼近和游戏无关收敛

    本文研究策略梯度方法在 Markov 潜在博弈多智能体强化学习问题上的全局非渐进收敛性质，提出新的独立策略梯度算法，证明算法达到 epsilon-Nash 平衡的迭代复杂度为 O (1/epsilon^2)，并在利用函数逼近的样本算法中，建立了样本复杂度为 O (1/epsilon^5) 的界限。同时，还找到了一类独立策略梯度算法，可在玩家对游戏类型无感知的情况下，实现零和马尔科夫博弈和合作马尔科夫博弈的收敛性。通过实验验证了理论成果的优点和有效性。

    Feb, 2022

  • 通过函数逼近证明的高效去中心化多智能体强化学习

    提出了第一种能够在分布式系统下使用函数逼近算法解决多代理强化学习的方法，此算法总能输出马尔可夫序列最优解，并且实现了根据多样性相关均衡（CCE）找到Ɛ- 最优解的最优速率，同时，还提出了一种能够在多样性相关均衡（CCE）中找到策略类受限一致均衡的分布式算法。

    Feb, 2023

  • 独立功能逼近的强化学习与马尔可夫博弈：在局部访问模型下改进的样本复杂度界限

    学习大状态和动作空间中的均衡、克服多项机构所带来的麻烦是一个具有挑战性的问题，最近的研究尝试通过使用独立的线性函数类来逼近每个代理的边际 Q 值来解决这个问题。我们介绍了一种新算法 Lin-Confident-FTRL，用于学习具有本地对模拟器访问能力的粗粒度相关均衡（CCE），并具有证明最优准确性界限 O（ϵ^-2）的可扩展性和抛弃了对动作空间的线性依赖。此外，我们对 Linear-Confident-FTRL 的分析广泛地推广了单机器人局部规划文献中的虚拟策略迭代技术，从而在假设对模拟器具有随机访问权时得到了一个新的计算有效的算法，并获得了更紧凑的样本复杂度界限。

    Mar, 2024

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

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

    Oct, 2023

  • 线性函数逼近下的近似极小极大离线强化学习：单智能体 MDP 和马尔科夫博弈

    本文提出了一种基于悲观主义的离线线性 MDP 算法，核心是使用参考函数进行不确定性分解并利用理论分析证明，该算法可以匹配性能下限并且该技术可以扩展到两人零和马尔可夫博弈，验证了算法的极小极大最优性。这是目前关于使用线性函数逼近的单智能体 MDPs 和 MGs 的第一个有效的极小极大最优算法。

    May, 2022

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

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

    Jun, 2022

  • 马尔科夫博弈中的离线学习和一般函数逼近

    研究离线多智体强化学习在马尔科夫博弈中学习近似均衡，提供适用于一般函数逼近的新框架以处理所有三种均衡，此框架利用 Bellman 一致压缩和数据覆盖条件，与之前的算法框架相比，其保证更好且能够处理更广泛的情况。

    Feb, 2023

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

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

    Oct, 2021

  • 基于平均奖励的马尔可夫决策过程更为精确的无模型强化学习

    我们提出了多种经过证明有效的无模型强化学习算法，包括基于参考优势分解的在线无模型强化学习算法以及适用于模拟器环境的无模型强化学习算法，在平均报酬马尔科夫决策过程中实现更好的折扣估计和置信区间的高效构建。

    Jun, 2023