2024/06/15 by Yang Cai, Cai, Yang, Gabriele Farina +11 · 4 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2406.10631
openalex publication_date 2024/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimistic multiplicative weights update (OMWU) and optimistic gradient-descent-ascent (OGDA). While both algorithms enjoy O(1/T) ergodic convergence to Nash equilibrium in two-player zero-sum games, OMWU offers several advantages including logarithmic dependence on the size of the payoff matrix and \widetildeO(1/T) convergence to coarse correlated equilibria even in general-sum games. However, in terms of last-iterate convergence in two-player zero-sum games, an increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks at a rate of O(1/√(T)), while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose? Somewhat surprisingly, we show that the former is true. More generally, we prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small δ>0, there exists a 2× 2 matrix game such that the algorithm admits a constant duality gap even after 1/δ rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-regularized-leader algorithms.