无悔动态和虚拟博弈
本文研究了 no-regret 动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader 的行为,证明了非严格的纳什均衡对于 no-regret 学习是不稳定的且不能吸引该动态系统的稳定状态,因此只有严格的纳什均衡是 no-regret 动力学的稳定限制点。
Oct, 2020
研究了凸优化问题,提出了基于无遗憾游戏动力学的算法框架,并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质,证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况,并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。
Nov, 2021
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题,通过引入乐观学习机制使得该方法求解速度得到了显著提升,同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。
Jul, 2018
我们介绍了一种简单的广义形式虚拟博弈算法,用于寻找二人零和游戏的均衡点,该算法实现等价于 Fictitious Play 的广义形式。与类似的广义形式虚拟博弈算法和反事实遗憾最小化算法相比,我们比较了其性能。这三种算法在减少存储需求和计算复杂度方面具有相同的优势,该新算法直观且容易实现,是寻求快速且简便的游戏求解工具的一个吸引人的选择。
Oct, 2023
研究了两个智能体在重复对局中报酬和悔恨之间的权衡,提出了一种广义均衡概念,讨论了不同对手情况下的最优战略和可行方案,探究了利用这种广义均衡学习最优策略的方法。
May, 2023
本文研究了虚拟博弈在寻找二人博弈的纳什均衡时的表现,证明虚拟博弈无法找到一个加法近似保证显著优于 1/2 的解。我们的结论适用于 2 人游戏并且玩家的得分在 [0,1] 范围内。
Mar, 2011
本文研究了在完备回忆且 n 个玩家泛化和值和的博弈中,如何从简单无耦合的后悔最小化学习动力学中导出 EFCE。研究结果提供了第一个收敛于 EFCE 的无耦合动力学,为该领域解决了开放性问题。
Apr, 2021
本文提出了一种新的在线学习方法,用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值,并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性,并证明了只要逼近函数能够实现后悔值,方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广;在我们的工作中,抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。
Nov, 2014
本研究在多智能体竞争的环境下对零和结构化 Markov 博弈问题的策略优化算法进行了提出和分析,考虑通过上置界乐观算法与虚拟博弈相结合的同时策略优化,从而使双方智能体的总体最优性差距以 $\widetilde {O}(\sqrt {K})$ 的速度收敛,其中 $K$ 为回合数量。
Jul, 2022