一般博弈中的近似最优无悔学习
提出了新的技术,将 DFG 的技术用于解决内部遗憾和交换遗憾,从而使得多人游戏中的学习动态能够收敛到近似相关均衡,同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。
Nov, 2021
本文研究了 Hedge 算法在 n 操作游戏中的运行,得出 Hedge 算法的乐观版本的遗憾率以及基础 Hedge 的收敛速率,对于多人游戏,我们使用 Blum 和 Mansour 的经典算法寻找均衡从而得到了我们的结果。
Jun, 2020
通过采用具有一种新颖形式的经验回忆的正则化学习算法,我们表明,在多人博弈的普通形式中,该类自适应算法能够实现更快的收敛速率,并实现对近似效率和粗略相关均衡的收敛,并且,对这种类型算法应用的每个玩家,他们的个体后悔降至 $O (T^{-3/4})$,而其效用之和则以 $O (T^{-1})$ 的速度趋于近似最优,在与该类算法相对应的算法维持更快的速率的同时,我们还表明了该类中的任何算法均可通过黑匣子降至 $ ilde {O}(T^{-1/2})$ 的速率来抵抗对手。
Jul, 2015
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
本论文证明具有低拟近似遗憾性质的学习算法在大类重复博弈中具有快速收敛到近似最优解的能力,包括使用基本对冲算法的算法。此外,作者对之前的结果进行了优化,并将该框架应用于动态人口博弈,并在大小和时间复杂度方面取得了改进。作者还提出了一种新的算法用于泊松回报任务,在效率和小损失方面都更有吸引力。
Jun, 2016
本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题,通过引入乐观学习机制使得该方法求解速度得到了显著提升,同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。
Jul, 2018
研究了两个智能体在重复对局中报酬和悔恨之间的权衡,提出了一种广义均衡概念,讨论了不同对手情况下的最优战略和可行方案,探究了利用这种广义均衡学习最优策略的方法。
May, 2023
使用乐观跟随正则化领导者算法结合适当的价值更新过程,在全信息一般和马尔可夫博弈中找到近似于 O (T^-1) 粗糙相关均衡。
Feb, 2024
本文通过使用具有时间不变学习率的乐观约束学习和自协调障碍,创新地组合学习动力学,成功地获得了广义和多人游戏中所有玩家的 swap regret,使每个玩家在 T 次游戏后都受到对数捆绑,同时在对抗性情形下保证了最佳的 sqrt (T) swap regret。
Apr, 2022
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014