乐观无悔动力加速
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
研究了凸优化问题,提出了基于无遗憾游戏动力学的算法框架,并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质,证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况,并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。
Nov, 2021
研究使用无遗憾算法计算特定类别的凸 - 凹游戏的平衡,展示了特定游戏类别可实现 O (1/T^2) 的速率,同时展示了此类无遗憾技术在采用额外曲率假设的情况下甚至可以实现线性速率,文中讨论的无遗憾算法可实现的有效范围包括乐观预测算法、Frank-Wolfe 方法等。
May, 2018
本文研究了学习动态的最后迭代收敛问题,并提供了新的结果和技术,其中包括一类游戏模型及其动态下的结果,以及通过遗憾分析得到的性质,证明了具有有界二阶路径长度,而且无论玩家使用不同算法和预测机制,也能实现 O(1 /sqrt(T))的速率和最优 O(1)的后悔界。同时证明了 OMD 要么接近纳什均衡,要么在效率上优于强韧价格,最后,对一般和连续的游戏模型也进行了探讨。
Mar, 2022
本文研究了 no-regret 动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader 的行为,证明了非严格的纳什均衡对于 no-regret 学习是不稳定的且不能吸引该动态系统的稳定状态,因此只有严格的纳什均衡是 no-regret 动力学的稳定限制点。
Oct, 2020
本文提出了一种新的在线学习方法,用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值,并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性,并证明了只要逼近函数能够实现后悔值,方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广;在我们的工作中,抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。
Nov, 2014
本文提出了针对分散式场景中双方零和博弈问题的算法,提供了最佳的诚实遗憾和对抗遗憾率,解决了收敛到游戏价值的对数项的开放问题,并通过乐观的镜像下降算法与鲁棒的乐观镜像下降算法的信号传递方案相结合,实现了最佳结果。
Feb, 2018
我们展示了一种称为 "Fast and Furious" 的学习方法,使得在二人零和博弈中时间平均遗憾减少且步长不为零成为可能,此学习方法为最小化 - 最大化优化和多智能体系统中的研究提供了新的标杆,即使是在最简单的情况下,我们的研究证明该方法的遗憾界限为 $\Theta (\sqrt {T})$,在学习率固定的情况下也会稳定收敛于确切的纳什均衡价值。
May, 2019
研究一种基于连续时间的在线优化策略族,证明其能够达到无遗憾学习。从传统的离散时间角度来看,这种方法可导出大量离散时间算法(包括一些经典遗憾分析算法)的无遗憾性质,并统一了许多经典的遗憾上界,得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。
Jan, 2014