(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
Preprint
Abstract
Follow the regularized leader FTRL is the premier algorithm for online optimization. However, despite decades of research on its convergence in constrained optimization -- and potential games in particular -- its behavior remained hitherto poorly understood. In this paper, we establish that FTRL can take exponential time to converge to a Nash equilibrium in two-player potential games for any (permutation-invariant) regularizer and potentially vanishing learning rate. By known equivalences, this translates to an exponential lower bound for certain mirror descent counterparts, most notably multiplicative weights update. On the positive side, we establish the potential property for FTRL and obtain an exponential upper bound $\exp(O_ε(1/ε^2))$ for any no-regret dynamics executed in a lazy, alternating fashion, matching our lower bound up to factors in the exponent. Finally, in multi-player potential games, we show that fictitious play -- the extreme version of FTRL -- can take doubly exponential time to reach a Nash equilibrium. This constitutes an exponentially stronger lower bound for the foundational learning algorithm in games.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Independent and Decentralized Learning in Markov Potential GamesIEEE Transactions on Automatic Control, 2025
- On the Rate of Convergence of Fictitious PlayTheory of Computing Systems, 2013
- Efficient algorithms for online decision problemsJournal of Computer and System Sciences, 2005
- On the snake in the box problemJournal of Combinatorial Theory, Series B, 1988
- Dynamics of games and genes: Discrete versus continuous timeJournal of Mathematical Biology, 1983
- Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved uponInternational Journal of Game Theory, 1978
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- What is the Maximum Length of a d-Dimensional Snake?The American Mathematical Monthly, 1970
- Unit-Distance Error-Checking CodesIEEE Transactions on Electronic Computers, 1958