Skip to Main content Skip to Navigation
Conference papers

The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond

Abstract : In this paper, we examine the convergence rate of a wide range of regularized methods for learning in games. To that end, we propose a unified algorithmic template that we call "follow the generalized leader" (FTGL), and which includes as special cases the canonical "follow the regularized leader" algorithm, its optimistic variants, extra-gradient schemes, and many others. The proposed framework is also sufficiently flexible to account for several different feedback models-from full information to bandit feedback. In this general setting, we show that FTGL algorithms converge locally to strict Nash equilibria at a rate which does not depend on the level of uncertainty faced by the players, but only on the geometry of the regularizer near the equilibrium. In particular, we show that algorithms based on entropic regularization-like the exponential weights algorithm-enjoy a linear convergence rate, while Euclidean projection methods converge to equilibrium in a finite number of iterations, even with bandit feedback.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03357715
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Wednesday, September 29, 2021 - 2:56:55 AM
Last modification on : Wednesday, July 6, 2022 - 4:19:31 AM
Long-term archiving on: : Thursday, December 30, 2021 - 6:11:26 PM

File

StrictRates.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03357715, version 1

Citation

Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos. The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond. NeurIPS 2021 - 35th International Conference on Neural Information Processing Systems, Dec 2021, Virtual, Unknown Region. pp.1-28. ⟨hal-03357715⟩

Share

Metrics

Record views

131

Files downloads

227