ICLRSep, 2022

$O (T^{-1})$ 乐观正则化领导者策略在双人零和马尔科夫博弈中的收敛性

PDF
TL;DR证明了在 Markov 博弈中，基于乐观的 Follow-the-Regularized-Leader (OFTRL) 算法的平滑值更新，可在 T 次迭代中找到 $O (T^{-1})$ 的近似 Nash 均衡，该算法的关键改进是通过紧化 OFTRL 权重的代数不等式，使竞争者的遗憾之和大致是非负的，使得学习动态的二阶路径长度被限制，最终实现了 $O (T^{-1})$ 的收敛速率提高。
发现论文，激发创造
  • $\widetilde {O}(T^{-1})$ 在全信息 General-Sum Markov Games 中收敛到（粗糙）相关均衡

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

    Feb, 2024

  • 广义和马尔可夫博弈中相关均衡的近最优策略优化

    我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法，以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率，本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法，达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。

    Jan, 2024

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

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

    Jul, 2015

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

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

    Mar, 2022

  • 广义隐式 Follow-The-Regularized-Leader

    该研究提出了一种新的在线学习算法，即广义隐式 FTRL，该算法扩展了 FTRL 框架的范围，可恢复已知算法，设计新的更新规则，直接改善遗憾的最坏情况的上界。

    May, 2023

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

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

    Nov, 2021

  • 无遗憾学习和混合纳什均衡：不能相互混合

    本文研究了 no-regret 动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader 的行为，证明了非严格的纳什均衡对于 no-regret 学习是不稳定的且不能吸引该动态系统的稳定状态，因此只有严格的纳什均衡是 no-regret 动力学的稳定限制点。

    Oct, 2020

  • 零和马尔可夫博弈中政策优化的更快收敛

    本文提出了一种基于 OMWU 方法的单环路政策优化算法，并在二人零和马尔可夫博弈中，通过控制正则化的程度，实现了有限时间的最后一次线性收敛到达量子响应均衡点，并在全信息离散设置中实现了收敛结果。

    Oct, 2022

  • 从庞加莱回归到不完全信息博弈的收敛：通过正则化寻找均衡

    研究了在顺序不完美信息游戏中遵循规则的领导者动态，推广了 Poincaré 循环结果，并探讨了通过调整奖励来建立收敛保证的技术，进而构建了精确收敛到 Nash 平衡的算法，为零和二人不完美信息游戏的无模型算法提供了新思路。

    Feb, 2020

  • 在线非凸学习：跟随扰动领袖是最优的

    研究基于非凸损失的在线学习问题，证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率，进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。

    Mar, 2019