Apr, 2024

（马尔可夫）潜力博弈中的纳什均衡收敛和无悔保证

PDF
TL;DR本研究主要探讨了潜在博弈、马尔可夫潜在博弈和 Frank-Wolfe 算法在随机成本和强盗反馈下的应用，提出了一种具有足够探索性和递归梯度估计的变种算法，能证明收敛于纳什均衡并对每个参与者实现亚线性遗憾。该算法同时在潜在博弈中实现了纳什遗憾和 $O (T^{4/5})$ 的遗憾上界，匹配了现有最佳结果，无需额外的投影步骤。通过精确平衡过去样本的重复使用和新样本的探索，我们将结果扩展到了马尔可夫潜在博弈中，将现有最佳纳什遗憾从 $O (T^{5/6})$ 改进至 $O (T^{4/5})$。此外，我们的算法不需要了解游戏的任何信息，如分布误差系数，这提供了更灵活的实际实施。实验结果证实了我们的理论发现，并强调了我们方法的实际有效性。
potential gamesmarkov potential gamesfrank-wolfe algorithmnash equilibriumregret bound
发现论文，激发创造
  • Markov α-Potential Games: 平衡逼近和遗憾分析

    本篇论文提出了一种新的框架来研究多智能体在马尔可夫游戏中的相互作用：马尔可夫 α- 潜力游戏。对于两种重要且实际意义明显的游戏 - 马尔可夫拥塞游戏和扰动马尔可夫团队游戏，提供了 α- 潜力函数，并且介绍了用于近似计算马尔可夫 α- 潜力游戏中平稳 Nash 均衡的两种算法。数值实验表明在持续时间方面，每个算法的 Nash 后悔都呈亚线性增长，并证明简单算法有能力在马尔可夫 α- 潜力游戏中找到近似均衡。}

    May, 2023

  • 一般和式马尔可夫博弈的遗憾最小化和均衡收敛

    简而言之，本文提出了一种针对广义和博弈的、分散、计算高效的算法，其保证所有代理都使用时可以提供次线性遗憾保证，并且不需要代理之间的通信。该算法的主要观察结果是，通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。

    Jul, 2022

  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

    本文提出了一种基于乐观的镜像下降的无悔策略算法，可以在非稳态环境下实现 O (sqrt (T)) 的后悔度，并可在变分稳定游戏中收敛到纳什均衡。

    Apr, 2021

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

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

    Feb, 2022

  • 凸凹博弈的更快率

    研究使用无遗憾算法计算特定类别的凸 - 凹游戏的平衡，展示了特定游戏类别可实现 O (1/T^2) 的速率，同时展示了此类无遗憾技术在采用额外曲率假设的情况下甚至可以实现线性速率，文中讨论的无遗憾算法可实现的有效范围包括乐观预测算法、Frank-Wolfe 方法等。

    May, 2018

  • 马尔可夫博弈中独立学习和稀疏均衡计算的难度

    本文研究了去中心化多智能体强化学习问题中的不后悔算法，并探讨了自主学习能否在标准 Markov 博弈框架中实现无后悔学习。结果表明，无论是已知还是未知的博弈，该问题都无法以多项式时间实现无后悔学习，该文贡献了理论证明支持，提出了基于集聚方法的创新性应用，并发现了 SparseCCE 问题的下限，从而说明了近年来学者对于该问题的研究成果，并对博弈理论和强化学习算法研究方向提出了新的思考。

    Mar, 2023

  • Fenchel 博弈中的无悔动态：算法凸优化的统一框架

    研究了凸优化问题，提出了基于无遗憾游戏动力学的算法框架，并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质，证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况，并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。

    Nov, 2021

  • 对抗对手下的学习马尔科夫博弈：高效算法与基本极限

    本文研究了在零和游戏中应用没有遗憾学习算法对抗自适应对手并取得最优结果的问题，并给出了一组正负结果，其中提出的新算法在普通的策略类别小或对手策略类别小时，可取得平均的 regret 较小的结果。

    Mar, 2022

  • 马尔可夫势博弈的独立自然策略梯度的可证明快速收敛

    该研究使用独立自然策略梯度算法解决马尔科夫潜在博弈中的多智能体强化学习问题，证明了在引入次优间隙的情况下，使用具有提供精确策略评估的正交算子的独立自然策略梯度方法可以渐进地在 Ε-Nash 均衡中达到 Ο(1/Ε) 次迭代，这比之前的结果 Ο(1/Ε^2) 次迭代要好，并且与单智能体的情况相同，其可达到 Ο(1/Ε) 次迭代的阶数。通过合成潜在博弈和拥塞博弈的实证结果来验证理论上的界限。

    Oct, 2023

  • 可证明的基于策略梯度法的平均奖励马尔可夫潜力博弈方法

    研究马尔可夫潜势博弈在无限时间平均回报准则下，证明基于独立策略梯度和独立自然策略梯度的算法都能在全局收敛到纳什均衡点，同时提出了渐进性和底座条件，通过梯度和微分值函数的灵敏度边界为梯度方法奠定了基础，并证明了三种算法的收敛性以及具体的时间复杂度，当需要估计策略梯度时，我们提出了一个算法并给出了样本复杂度分析，最后通过模拟研究来验证结果。

    Mar, 2024