快速交换后悔值最小化及其在近似相关均衡中的应用
本文研究了 Hedge 算法在 n 操作游戏中的运行,得出 Hedge 算法的乐观版本的遗憾率以及基础 Hedge 的收敛速率,对于多人游戏,我们使用 Blum 和 Mansour 的经典算法寻找均衡从而得到了我们的结果。
Jun, 2020
我们提供了一种新颖的从交换后悔最小化到外部后悔最小化的约简方法,该方法改进了 Blum-Mansour 和 Stolz-Lugosi 的经典约简,不需要动作空间的有限性。我们的结果表明,只要存在某个假设类的无外部后悔算法,同样必然存在该类别的无交换后悔算法。对于使用专家建议的学习问题,我们的结果表明,在 log (N)^{O (1/ε)} 轮迭代中并且每次迭代的复杂度为 O (N),可以保证交换后悔受到 ε 的约束,而 Blum-Mansour 和 Stolz-Lugosi 的经典约简则需要 O (N/ε^2) 轮迭代和至少 Ω(N^2) 的复杂度。我们的结果还带有一个相关的下界,与 [BM07] 中的下界相反,该下界适用于具有遗忘性和限制的 κ1 的对手和学习者,以及可以使用专家分布的情况,从而说明轮数必须是 Ω(N/ε^2) 或以指数的方式与 1/ε 成反比。我们的约简意味着,如果在某个游戏中可以进行无后悔学习,那么该游戏必须具有近似的相关均衡,具有任意好的近似程度。这加强了无后悔学习所暗示的粗略相互相关均衡的存在。重要的是,它提供了一种存在相关均衡的充分条件,大大扩展了行动集有限的要求,从而回答了 [DG22; Ass+23] 中未解决的问题。此外,它还回答了关于均衡计算和 / 或游戏学习的几个未解决问题。
Oct, 2023
本文通过使用具有时间不变学习率的乐观约束学习和自协调障碍,创新地组合学习动力学,成功地获得了广义和多人游戏中所有玩家的 swap regret,使每个玩家在 T 次游戏后都受到对数捆绑,同时在对抗性情形下保证了最佳的 sqrt (T) swap regret。
Apr, 2022
本文提出一种针对不完全信息的博弈模式下具有更快学习速度的学习动态方案,并对其进行实验验证。其中,主要技术贡献为通过预测实现加速 Phi-regret 最小化,并通过对于有结构的马尔科夫链的细致扰动分析,表征与之相关的 fixed points 的稳定性。
Feb, 2022
我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度,我们证明了在广义形式博弈中,假设 PPAD 不属于 TIME (n^polylog (n)),任何多项式时间学习算法至少需要 2^log_2^{1-o (1)}(|I|) 次迭代才能收敛于 ε- 近似相关均衡集合,同时我们给出了无耦合动态的方法,在对数次迭代中达到 ε- 近似相关均衡的贝叶斯博弈,无需考虑类型的数量。
Jun, 2024
我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法,以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率,本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法,达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
Jan, 2024
提出了新的技术,将 DFG 的技术用于解决内部遗憾和交换遗憾,从而使得多人游戏中的学习动态能够收敛到近似相关均衡,同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。
Nov, 2021
本文提出两种新算法:平衡在线镜像下降和平衡对策后悔最小化,通过整合平衡探索策略到它们的经典对应物算法,解决学习不完美信息的广义零和游戏的近似 Nash 均衡问题。同时,将结果推广到学习多人游戏的粗略相关均衡。
Feb, 2022
本文介绍了一种松弛的 Nash 平衡概念,即 σ 平滑的 Nash 平衡,通过使用随机化算法和多项式时间确定性算法,在常数参数范围内,可以更有效地找到近似的 σ 平滑的 Nash 平衡。
Sep, 2023
研究使用无遗憾算法计算特定类别的凸 - 凹游戏的平衡,展示了特定游戏类别可实现 O (1/T^2) 的速率,同时展示了此类无遗憾技术在采用额外曲率假设的情况下甚至可以实现线性速率,文中讨论的无遗憾算法可实现的有效范围包括乐观预测算法、Frank-Wolfe 方法等。
May, 2018