Timezone: »

 
Poster
On the Rate of Convergence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Beyond
Angeliki Giannou · Emmanouil-Vasileios Vlatakis-Gkaragkounis · Panayotis Mertikopoulos

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »

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 asspecial 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 – fromfull 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.

Keywords: Optimization · Bandits

Author Information

Angeliki Giannou (University of Wisconsin Madison)
Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University)
Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research) and Criteo AI Lab)

More from the Same Authors