用对数障碍正则实现零和博弈的最优最后迭代收敛
Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
- 引入对数障碍正则化，结合双侧分析框架
- 在高概率下达到 O~(t^{-1/4}) 的可利用差距收敛率
- 适用于在线学习与扩展形式博弈场景
我们研究零和矩阵博弈中学习极小极大策略的问题。Fiegel 等人（2025）最近证明，在玩家解耦的情况下，实现最后迭代收敛更困难，其可利用差距的下界为 Omega(t^{-1/4})。尽管文献中提出了一些在线镜像下降算法，但尚未真正达到该收敛速率。本文表明，采用对数障碍正则化并配合双侧分析，可在高概率下实现 O~(t^{-1/4}) 的收敛。此外，我们将该方法扩展至扩展形式博弈，同样获得相同收敛速率的理论保证。
原文摘要 · Abstract (English)
We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t^{-1/4}) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。