连续博弈中的自适应学习:最优遗憾边界和纳什均衡收敛
研究了两个智能体在重复对局中报酬和悔恨之间的权衡,提出了一种广义均衡概念,讨论了不同对手情况下的最优战略和可行方案,探究了利用这种广义均衡学习最优策略的方法。
May, 2023
本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题,通过引入乐观学习机制使得该方法求解速度得到了显著提升,同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。
Jul, 2018
简而言之,本文提出了一种针对广义和博弈的、分散、计算高效的算法,其保证所有代理都使用时可以提供次线性遗憾保证,并且不需要代理之间的通信。该算法的主要观察结果是,通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。
Jul, 2022
研究了非协同凹性博弈中以赌徒反馈为学习手段的长期行为,证明了采用镜像下降算法的不懊悔学习算法在满足标准单调性条件下能以概率 1 收敛于 Nash 均衡,并推导出了其收敛速率的上界。
Oct, 2018
本研究主要探讨了潜在博弈、马尔可夫潜在博弈和 Frank-Wolfe 算法在随机成本和强盗反馈下的应用,提出了一种具有足够探索性和递归梯度估计的变种算法,能证明收敛于纳什均衡并对每个参与者实现亚线性遗憾。该算法同时在潜在博弈中实现了纳什遗憾和 $O (T^{4/5})$ 的遗憾上界,匹配了现有最佳结果,无需额外的投影步骤。通过精确平衡过去样本的重复使用和新样本的探索,我们将结果扩展到了马尔可夫潜在博弈中,将现有最佳纳什遗憾从 $O (T^{5/6})$ 改进至 $O (T^{4/5})$。此外,我们的算法不需要了解游戏的任何信息,如分布误差系数,这提供了更灵活的实际实施。实验结果证实了我们的理论发现,并强调了我们方法的实际有效性。
Apr, 2024
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014
研究了凸优化问题,提出了基于无遗憾游戏动力学的算法框架,并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质,证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况,并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。
Nov, 2021
本文重新审视了在线学习中的策略后悔问题,表明在某些情况下,外部后悔和策略后悔是不兼容的,而在自利智能体领域,如果使用某些算法,则可以保证外部后悔和策略后悔都是有利的。本文还介绍了一个新的均衡概念 —— 策略均衡,并表明粗略相关均衡是策略均衡的一个真子集。
Nov, 2018
本论文证明具有低拟近似遗憾性质的学习算法在大类重复博弈中具有快速收敛到近似最优解的能力,包括使用基本对冲算法的算法。此外,作者对之前的结果进行了优化,并将该框架应用于动态人口博弈,并在大小和时间复杂度方面取得了改进。作者还提出了一种新的算法用于泊松回报任务,在效率和小损失方面都更有吸引力。
Jun, 2016
本文提出了一种新的在线学习方法,用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值,并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性,并证明了只要逼近函数能够实现后悔值,方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广;在我们的工作中,抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。
Nov, 2014