OMWU在博弈学习中最佳迭代收敛快，但最后迭代收敛极慢。
On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
- 提出双阶段分析法，揭示最佳迭代收敛机制
- 证明2×2博弈中最佳迭代率达O(T⁻¹⁄⁶)，远超最后迭代
- 挑战随机迭代等价于最佳迭代的传统认知，适合博弈学习研究者
非遍历收敛在博弈学习中备受关注。近期研究（Cai et al., 2024）表明，包括乐观乘法权重更新（OMWU）在内的广泛学习动态，在简单2×2矩阵博弈中可能表现出任意缓慢的最后迭代收敛，尽管这些算法在最后迭代中仍具渐近收敛性。然而，它们在更弱准则下是否实现快速非遍历收敛尚不明确，例如最佳迭代收敛。本文证明：在2×2矩阵博弈中，OMWU可实现O(T⁻¹⁄⁶)的最佳迭代收敛率，与之形成鲜明对比的是其缓慢的最后迭代收敛。此外，我们建立下界，证明OMWU无法实现任何多项式随机迭代收敛率，以所有迭代的期望对偶间隙衡量。该结果挑战了传统观念——即随机迭代收敛等价于最佳迭代收敛，而后者常以前者为代理。我们的分析揭示了与动态后悔的新关联，并提出一种新颖的两阶段最佳迭代收敛方法，具有独立研究价值。
原文摘要 · Abstract (English)
Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update (OMWU), can exhibit arbitrarily slow last-iterate convergence even in simple $2 \times 2$ matrix games, despite many of these dynamics being known to converge asymptotically in the last iterate. It remains unclear, however, whether these algorithms achieve fast non-ergodic convergence under weaker criteria, such as best-iterate convergence. We show that for $2\times 2$ matrix games, OMWU achieves an $O(T^{-1/6})$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games. Furthermore, we establish a lower bound showing that OMWU does not achieve any polynomial random-iterate convergence rate, measured by the expected duality gaps across all iterates. This result challenges the conventional wisdom that random-iterate convergence is essentially equivalent to best-iterate convergence, with the former often used as a proxy for establishing the latter. Our analysis uncovers a new connection to dynamic regret and presents a novel two-phase approach to best-iterate convergence, which could be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。