Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games

Nonergodic convergence of learning dynamics in games has been widely studied recently because of its importance in both theory and practice. In this paper, we focus on a broad class of popular learning dynamics based on optimistic follow the regularized leader (OFTRL), including the optimistic multiplicative weights update (OMWU) algorithm and the conceptual prox algorithm. In this paper, we focus on two-player zero-sum games (matrix games), and we show a separation result between the last-iterate, random-iterate, and best-iterate convergence properties of OFTRL. We start by proving that OFTRL cannot achieve any uniform (instance-independent) last-iterate convergence rate in stark contrast with its $O(1/T)$ uniform convergence to an equilibrium of the game for the average iterates and despite several OFTRL dynamics being known to converge asymptotically in the last iterate. We also prove several lower bounds for the uniform random-iterate convergence rate of OFTRL measured by the average duality gap. In particular, we show that OMWU cannot achieve a polynomial uniform random-iterate convergence. Finally, we prove that OMWU achieves a $O(T^{-1/6})$ uniform best-iterate convergence rate for the specific case of $2\times 2$ matrix games. Our results challenge the conventional wisdom that last-iterate, random-iterate and best-iterate convergence rates are essentially equivalent as has been shown for other popular learning algorithms, such as optimistic gradient descent ascent.

Funding: Y. Cai was supported by the National Science Foundation [Grants CCF-1942583 (CAREER) and CCF-2342642]. G. Farina was supported by the National Science Foundation [Grant CCF-2443068 (CAREER)]. J. Grand-Clément was supported by Hi! Paris and Agence Nationale de la Recherche [Grant 11-LABX-0047]. C. Kroer was supported by the Office of Naval Research [Grants N00014-22-1-2530 and N00014-23-12374] and the National Science Foundation [Grants IIS-2147361 and IIS-2238960]. H. Luo was supported by the National Science Foundation [Grant IIS-1943607]. W. Zheng was supported by the National Science Foundation [Grants CCF-1942583 (CAREER) and CCF-2342642] and the Center for Algorithms, Data, and Market Design at Yale (CADMY) [research fellowship].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2025.2166.