May, 2018

凸凹博弈的更快率

PDF
TL;DR研究使用无遗憾算法计算特定类别的凸 - 凹游戏的平衡，展示了特定游戏类别可实现 O (1/T^2) 的速率，同时展示了此类无遗憾技术在采用额外曲率假设的情况下甚至可以实现线性速率，文中讨论的无遗憾算法可实现的有效范围包括乐观预测算法、Frank-Wolfe 方法等。
no-regret algorithmsequilibriaconvex-concave gamesoptimistic prediction algorithmsfrank-wolfe method
发现论文，激发创造
  • 乐观无悔动力加速

    本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题，通过引入乐观学习机制使得该方法求解速度得到了显著提升，同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。

    Jul, 2018

  • 正则化学习在博弈中的快速收敛

    通过采用具有一种新颖形式的经验回忆的正则化学习算法，我们表明，在多人博弈的普通形式中，该类自适应算法能够实现更快的收敛速率，并实现对近似效率和粗略相关均衡的收敛，并且，对这种类型算法应用的每个玩家，他们的个体后悔降至 $O (T^{-3/4})$，而其效用之和则以 $O (T^{-1})$ 的速度趋于近似最优，在与该类算法相对应的算法维持更快的速率的同时，我们还表明了该类中的任何算法均可通过黑匣子降至 $ ilde {O}(T^{-1/2})$ 的速率来抵抗对手。

    Jul, 2015

  • （马尔可夫）潜力博弈中的纳什均衡收敛和无悔保证

    本研究主要探讨了潜在博弈、马尔可夫潜在博弈和 Frank-Wolfe 算法在随机成本和强盗反馈下的应用，提出了一种具有足够探索性和递归梯度估计的变种算法，能证明收敛于纳什均衡并对每个参与者实现亚线性遗憾。该算法同时在潜在博弈中实现了纳什遗憾和 $O (T^{4/5})$ 的遗憾上界，匹配了现有最佳结果，无需额外的投影步骤。通过精确平衡过去样本的重复使用和新样本的探索，我们将结果扩展到了马尔可夫潜在博弈中，将现有最佳纳什遗憾从 $O (T^{5/6})$ 改进至 $O (T^{4/5})$。此外，我们的算法不需要了解游戏的任何信息，如分布误差系数，这提供了更灵活的实际实施。实验结果证实了我们的理论发现，并强调了我们方法的实际有效性。

    Apr, 2024

  • $\widetilde {O}(T^{-1})$ 在全信息 General-Sum Markov Games 中收敛到（粗糙）相关均衡

    使用乐观跟随正则化领导者算法结合适当的价值更新过程，在全信息一般和马尔可夫博弈中找到近似于 O (T^-1) 粗糙相关均衡。

    Feb, 2024

  • 连续博弈中的自适应学习：最优遗憾边界和纳什均衡收敛

    本文提出了一种基于乐观的镜像下降的无悔策略算法，可以在非稳态环境下实现 O (sqrt (T)) 的后悔度，并可在变分稳定游戏中收敛到纳什均衡。

    Apr, 2021

  • Fenchel 博弈中的无悔动态：算法凸优化的统一框架

    研究了凸优化问题，提出了基于无遗憾游戏动力学的算法框架，并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质，证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况，并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。

    Nov, 2021

  • 关于凸优化和非凸优化的在线 Frank-Wolfe 算法

    探讨在线变体的 Frank-Wolfe 算法，包括简单迭代更新和非自适应步长规则，研究凸和非凸损失的多个新结果，并基于对随机 Frank-Wolfe 算法的改进分析得出在强凸随机成本时的遗憾界和任何时刻的最优性为 O (log^3T/T) 和 O (log^2T/T) ; 此外，该在线算法即使在损失非凸的情况下也能收敛，以速率 O (1/T 的平方根) 找到时变 / 随机损失的稳态点。

    Oct, 2015

  • 游戏中的套期保值：外部和换手遗憾更快的收敛

    本文研究了 Hedge 算法在 n 操作游戏中的运行，得出 Hedge 算法的乐观版本的遗憾率以及基础 Hedge 的收敛速率，对于多人游戏，我们使用 Blum 和 Mansour 的经典算法寻找均衡从而得到了我们的结果。

    Jun, 2020

  • 多人零和游戏中相关均衡的几乎最优无悔学习

    提出了新的技术，将 DFG 的技术用于解决内部遗憾和交换遗憾，从而使得多人游戏中的学习动态能够收敛到近似相关均衡，同时分析了 Blum 和 Mansour 算法中的近似最优遗憾保证。

    Nov, 2021

  • 非凸博弈中高效的遗憾最小化

    本文探讨了在非凸损失函数的重复博弈中如何最小化遗憾，并给出了基于梯度下降的方法来实现最优遗憾并保证收敛到平衡点。

    Jul, 2017