Oct, 2020

无遗憾学习和混合纳什均衡：不能相互混合

PDF
TL;DR本文研究了 no-regret 动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader 的行为，证明了非严格的纳什均衡对于 no-regret 学习是不稳定的且不能吸引该动态系统的稳定状态，因此只有严格的纳什均衡是 no-regret 动力学的稳定限制点。
no-regret dynamicsn-player gamescorrelated equilibriaftrlnash equilibrium
发现论文，激发创造
  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

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

    Apr, 2021

  • 正则化学习下游戏中动态稳定性和战略稳定性的等效性

    通过研究正则化的无悔学习方法在有限游戏中的长期行为，我们发现玩家的实际策略如何随时间演变的理解非常有限，同时发现只有严格纳什均衡是稳定吸引的，进而揭示了玩家的日常对策的集合有理性的特性。我们进一步刻画了相应集合的稳定和收敛速率，并表明基于熵正则化的方法以几何速度收敛，而基于投影的方法在有限次迭代内收敛，即使是在带有被动反馈的并发奖励的情况下。

    Nov, 2023

  • 游戏学习对学习者是否有益？

    研究了两个智能体在重复对局中报酬和悔恨之间的权衡，提出了一种广义均衡概念，讨论了不同对手情况下的最优战略和可行方案，探究了利用这种广义均衡学习最优策略的方法。

    May, 2023

  • 乐观无悔动力加速

    本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题，通过引入乐观学习机制使得该方法求解速度得到了显著提升，同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。

    Jul, 2018

  • $\widetilde {O}(T^{-1})$ 在全信息 General-Sum Markov Games 中收敛到（粗糙）相关均衡

    使用乐观跟随正则化领导者算法结合适当的价值更新过程，在全信息一般和马尔可夫博弈中找到近似于 O (T^-1) 粗糙相关均衡。

    Feb, 2024

  • 广义博弈中简单非耦合无悔学习动态

    本文研究了在完备回忆且 n 个玩家泛化和值和的博弈中，如何从简单无耦合的后悔最小化学习动力学中导出 EFCE。研究结果提供了第一个收敛于 EFCE 的无耦合动力学，为该领域解决了开放性问题。

    Apr, 2021

  • 无悔动态和虚拟博弈

    研究了基于势能和无悔动态的关系，发现这些动态与虚拟博弈有联系，可提供收敛于纳什均衡的不同且更简洁的证明方法。

    Jul, 2012

  • 多人随机博弈中的学习

    本文研究多人随机博弈中同时学习的问题，通过生成算法获得相关均衡，包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium，并提供了一些能够多项式时间内解决的特殊情况。

    Oct, 2022

  • 游戏中的罚款调节动态与强韧学习程序

    通过一种启发式的学习方案，我们派生出了一种由惩罚项调整的复制者漂移的新类连续时间学习动态，这种惩罚调节的动态相当于玩家保留他们正在进行的回报的指数折扣总和，然后基于这些表现分数使用平滑最佳响应选择行动。借助这种内在的对偶，所提出的动态满足一种进化博弈理论的民间定理的变体，并且它们以（任意精度的）纳什均衡的逼近收敛于潜在游戏。受到交通工程应用的启发，我们进一步利用这种对偶来设计离散时间的，基于回报的学习算法，该算法具有这些收敛性质，并且仅需要玩家观察他们在游戏中的回报

    Mar, 2013

  • 多人零和游戏中相关均衡的几乎最优无悔学习

    提出了新的技术，将 DFG 的技术用于解决内部遗憾和交换遗憾，从而使得多人游戏中的学习动态能够收敛到近似相关均衡，同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。

    Nov, 2021