Nov, 2023

遗憾匹配算法在博弈中的最后迭代收敛性质

PDF
TL;DR研究了基于遗憾匹配（RM+）及其变种的算法在求解大规模两人零和博弈中的最优策略时的迭代收敛性，并通过数值实验证明了部分实际变种算法在简单的 3×3 游戏中无法保证迭代收敛。进一步证明了基于平滑技术的最新变种算法，如 extragradient RM+ 和 smooth Predictive RM+ 在最优策略上存在渐进收敛以及 1/√t 的最优策略收敛。最后，引入了重启变种算法，并证明它们在最优策略上可达到线性级别的收敛速度。
regret matchinglast-iterate convergencevariantsasymptotic convergencenumerical optimization
发现论文，激发创造
  • 懊悔匹配 +: 博弈中的 (不) 稳定性和快速收敛

    研究 Regret Matching + 算法及其变体在解决大规模博弈中的应用，提出稳定化的解决方案，成功获取了在正态型博弈中的个体遗憾和社会遗憾的最优解，并在 clairvoyant 在线问题解决方面获得了理想结果。

    May, 2023

  • 广义博弈中的最后迭代收敛

    本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡，针对反事实遗憾最小化（CFR）算法存在的表示收敛的缺陷，提出了一些基于树形复合结构的乐观遗憾最小化算法，并给出了实验证明其在求解连续游戏时的有效性。

    Jun, 2021

  • 解决博弈中的高效收敛算法

    通过转换问题为一系列凸凹优化问题， ' 无悔算法 ' 在学习纳什均衡中取得竞争性表现，在离散时间反馈设置下实现最后迭代收敛。

    Aug, 2023

  • 受限周期性博弈中额外梯度法与乐观主义的最后收敛分离

    研究了乐观法和额外梯度法在受限周期游戏中的最终迭代行为，证明了与无限制周期游戏中的收敛性类似的分离结果。

    Jun, 2024

  • 关于零和博弈的收敛策略探讨

    本文研究了学习动态的最后迭代收敛问题，并提供了新的结果和技术，其中包括一类游戏模型及其动态下的结果，以及通过遗憾分析得到的性质，证明了具有有界二阶路径长度，而且无论玩家使用不同算法和预测机制，也能实现 O（1 /sqrt（T））的速率和最优 O（1）的后悔界。同时证明了 OMD 要么接近纳什均衡，要么在效率上优于强韧价格，最后，对一般和连续的游戏模型也进行了探讨。

    Mar, 2022

  • 快速学习游戏的最后迭代收敛需要健忘算法

    通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一，尤其流行的算法包括乐观的乘积权重更新（OMWU）和乐观的梯度下降 - 梯度上升（OGDA），本文证明了 OMWU 存在潜在的较慢的最后迭代收敛问题。

    Jun, 2024

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

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

    Jul, 2015

  • 博弈中的学习：快速收敛的稳健性

    本论文证明具有低拟近似遗憾性质的学习算法在大类重复博弈中具有快速收敛到近似最优解的能力，包括使用基本对冲算法的算法。此外，作者对之前的结果进行了优化，并将该框架应用于动态人口博弈，并在大小和时间复杂度方面取得了改进。作者还提出了一种新的算法用于泊松回报任务，在效率和小损失方面都更有吸引力。

    Jun, 2016

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

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

    Apr, 2021

  • 无悔学习中的最后迭代收敛：凸凹景观的约束极小极大优化

    本文研究了凸凹零和博弈问题，并提出了一种遵循在线学习框架的近似算法 Optimistic Multiplicative-Weights Update，在本地范围内表现出最后收敛性。

    Feb, 2020