Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games
Operations Research · 2026-11 · 74 (6) · 3322-3341
DOI: 10.1287/opre.2025.2166 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, 2026-11. Verfasst von Yang Cai und 6 weiteren Autor:innen. Die Arbeit nennt 85 Literaturangaben.
Abstract (Originalsprache)
Convergence of Optimistic Learning in Games and the Role of Forgetfulness Online learning algorithms solve games by repeatedly updating players’ strategies. A natural hope is that the latest strategy improves at a predictable rate. This paper shows that this intuition can fail for optimistic follow-the-regularized-leader methods, including the widely used optimistic multiplicative weights algorithm. In two-player zero-sum games, the authors separate three notions of nonergodic performance: last-iterate, random-iterate, and best-iterate convergence. They prove that no instance-independent last-iterate rate exists for the broad algorithmic family and establish strong lower bounds for random iterates. Yet, a useful positive result remains; in 2 × 2 games, optimistic multiplicative weights achieve a uniform best-iterate rate. The analysis traces the slowdown to a lack of “forgetfulness”; accumulated past losses can keep the dynamics moving away from equilibrium long after they reach its neighborhood. The results suggest that practitioners should distinguish carefully between the latest strategy, a randomly selected strategy, and the best observed strategy when evaluating learning dynamics.
Zitieren
APA
Cai, Y., Farina, G., Grand-Clément, J., Kroer, C., Lee, C., Luo, H., & Zheng, W. (2026). Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games. Operations Research, 74(6), 3322-3341. https://doi.org/10.1287/opre.2025.2166
Vancouver
Cai Y, Farina G, Grand-Clément J, Kroer C, Lee C, Luo H, et al. Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games. Operations Research. 2026;74(6):3322-3341. doi:10.1287/opre.2025.2166
BibTeX
@article{Cai2026,
author = {Cai, Yang and Farina, Gabriele and Grand-Clément, Julien and Kroer, Christian and Lee, Chung-Wei and Luo, Haipeng and Zheng, Weiqiang},
title = {Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games},
journal = {Operations Research},
year = {2026},
volume = {74},
number = {6},
pages = {3322--3341},
doi = {10.1287/opre.2025.2166}
}
EUVIMED