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

Angeliki Giannou, Emmanouil V. Vlatakis-Gkaragkounis, Panayotis MertikopoulosNeurIPS 2021 · OpenReview

Introduction

In game theory, a fundamental question is whether players can reach a Nash equilibrium simply by observing their past performance and adapting their strategies. While it is known that certain algorithms, such as "Follow the Regularized Leader" (FTRL), eventually converge to strict Nash equilibria, the speed of this convergence—especially under conditions of uncertainty—has historically remained an open question.

Existing literature predominantly provides qualitative results (guaranteeing eventual convergence) or focuses on "regret minimization," which measures a player's loss compared to the best fixed strategy in hindsight. However, minimizing regret is not mathematically equivalent to converging to an equilibrium. Furthermore, previous rate analyses often assumed "monotone" games or perfect information. This paper addresses this gap by introducing a unified framework called Follow the Generalized Leader (FTGL), providing the first quantitative convergence rates for a wide class of learning algorithms in finite games under various feedback models.

The Follow the Generalized Leader (FTGL) Framework

The authors propose FTGL as a flexible algorithmic template that encompasses several popular learning schemes:

  • Standard FTRL: The classic "vanilla" learning approach.
  • Optimistic FTRL (OptFTRL): Variants that utilize a "hint" or prediction of the next payoff.
  • Extra-gradient/Mirror-prox (EG/MP): Methods frequently used to stabilize training in complex systems like GANs.

Crucially, the FTGL framework is designed to handle multiple feedback environments, ranging from full information to the challenging "bandit" setting where players only observe their own realized rewards.

Feedback models and algorithm parameters in the FTGL framework.

The core mechanism of FTGL relies on a "regularized choice map." Players maintain a cumulative score for each action and select their next move by maximizing this score minus a penalty (the regularizer). To quantify convergence, the authors define a rate function ($\phi$) derived directly from the geometry of this regularizer.

Examples of algorithms, their regularizing kernels, and the resulting rate functions.

Key Insights and Convergence Rates

The theoretical analysis yields several profound insights into the dynamics of learning in games, validated through classic game-theoretic benchmarks like the Battle of the Sexes and Pigou’s Congestion Game.

The Geometry of Regularization Dictates Speed

The most significant finding is that the speed of convergence is dictated entirely by how the regularizer behaves near the boundary of the strategy space.

  • Entropic Regularization: Algorithms using steep regularizers, such as Multiplicative Weight Updates (Exponential Weights), achieve a linear (exponential) convergence rate.
  • Euclidean Regularization: Algorithms using non-steep regularizers, such as Projection Gradient Descent, achieve finite-time convergence. Players reach the exact Nash equilibrium after a specific number of steps and remain there.

Robustness to Uncertainty

Perhaps the most counter-intuitive finding is that the type of feedback does not alter the fundamental convergence rate. Whether players have full information or noisy bandit feedback, the "leader-following" nature of these algorithms is robust enough that the underlying rate (dictated by the regularizer's geometry) remains unchanged. The uncertainty only affects the constants, not the asymptotic rate class.

The Regret vs. Convergence Trade-off

In the domain of regret minimization, entropic regularization is generally considered superior. However, this paper demonstrates that for equilibrium convergence, Euclidean methods are actually faster (finite time versus exponential decay). This highlights a critical trade-off: the "best" algorithm depends entirely on whether the primary objective is to minimize individual cumulative loss or to rapidly reach a stable game state.

Limitations and Future Directions

While the FTGL framework provides robust quantitative rates, the analysis is currently limited to local convergence—it applies once players are already within a "neighborhood" of a strict Nash equilibrium, but does not guarantee how long it takes to find that neighborhood from a random initialization. Furthermore, the results are specific to strict Nash equilibria and do not cover mixed-strategy equilibria in non-zero-sum games, which remain notoriously difficult to solve.

Future work may explore the "polar shift" between regret minimization and equilibrium convergence, potentially leading to new multi-agent reinforcement learning algorithms that balance confident, rapid stabilization with robust loss minimization.

Summary updated

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 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.
BibTeX
@inproceedings{giannou2021convergence,
  author = {Angeliki Giannou and Emmanouil V. Vlatakis-Gkaragkounis and Panayotis Mertikopoulos},
  title = {{The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=TTSfIdFskv},
}
Figure