(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm · 2026
Read (Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games by Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23248.txt.
Introduction
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, and Tuomas Sandholm prove slow-convergence bounds for a leading online learning algorithm. Follow the Regularized Leader is the premier method for online optimization. Its behavior in potential games, though studied for decades, remained poorly understood.
The authors show it can take exponential, even doubly exponential, time to reach a Nash equilibrium. The result holds for two-player potential games, any permutation-invariant regularizer, and even tiny learning rates. Such bounds redraw expectations for learning in games. Vanishing learning rates do not rescue the algorithm in the proof, which closes a common hope for practitioners.
Catalog record
| CREATOR | Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 127 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-23248
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm Abstract Follow the regularized leader ( FTRL ) (\texttt{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 ) ) \exp(O_{\epsilon}(1/\epsilon^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. 1 Introduction Multiplicative weights update ( MWU ) is the quintessential online algorithm [ Littlestone and Warmuth 1994 ] , attaining the optimal regret bound in many fundamental online learning problems [ Fan et al. 2025 ] . It has found applications in diverse areas ranging from approximation algorithms to boosting in machine learning [ Arora et al. 2012 ] . MWU is an instantiation of the seminal online learning paradigm follow the regularized leader (\texttt{FTRL}) [ Kalai and Vempala 2005 ] . Viewed differently, MWU can also be cast as an instance of online mirror descent (\texttt{MD}) [ Nemirovski and Yudin 1983 ] . A celebrated connection inextricably links the no-regret property, attained by algorithms such as FTRL and MD , to coarse correlated equilibria (CCEs) , a seminal game-theoretic solution concept [ Moulin and Vial 1978 , Aumann 1974 ] . Specifically, if each player in a multi-player game employs a no-regret algorithm to update its strategy, the average correlated distribution of play converges to the set of CCEs. This connection, however, provides no information about the last-iterate convergence of the dynamics. Characterizing the convergence of MWU and other online algorithms has received extensive attention. Kleinberg et al. 2009 first established that MWU converges to Nash equilibria for almost all potential games. In this setting, players are effectively ascending a global potential function; thus, the dynamics can be viewed through the lens of constrained optimization, with Nash equilibria corresponding to first-order stationary points. Non-asymptotic rates soon emerged for some versions of MD , most notably gradient descent, but despite decades of research on this topic, a major question remained hitherto wide open: How many iterations are needed for FTRL algorithms to converge in potential games? Viewed differently, can MWU or FTRL efficiently find first-order stationary points in constrained optimization? Although MWU has been shown to asymptotically converge in potential games—at least when the set of Nash equilibria comprises isolated points, a condition that holds for almost all potential games [ Kleinberg et al. 2009 , Palaiopanos et al. 2017 ] —this result has not been extended to the general class of FTRL . FTRL presents distinct challenges that complicate the analysis compared to algorithms such as gradient descent. For example, it can exhibit spurious fixed points : due to its history dependence, the dynamics may stagnate even when the current strategy is highly suboptimal relative to the observed utility ( Example 3.3 ). 1.1 Our results We provide new upper and lower bounds for the convergence of FTRL in potential games and constrained optimization. Our first positive result goes beyond FTRL and covers the entire class of no-regret dynamics. We establish a non-asymptotic rate of convergence to Nash equilibria, provided the updates are alternating and lazy —the player performs an update only when the proposed strategy guarantees a sufficient improvement. Theorem 1.1 . In any potential game, alternating \epsilon -lazy no-regret dynamics converge to an \epsilon -Nash equilibrium after at most \exp(O_\epsilon(1/\epsilon^2)) iterations. Figure 1 : Illustration of our results: FTRL algorithms have the potential property (right), but can take exponential time to converge (left). The proof proceeds by bounding the number of updates that can occur and then deriving a recursion for the time required between successive updates, paving the way to Theorem 1.1 . To put this into context, it is well-known that no-regret dynamics can fail to converge to Nash equilibria in potential games [ Kleinberg et al. 2009 ] ; Theorem 1.1 offers a natural way to circumvent those impossibility results. Turning to the special case of FTRL , we show that, for sufficiently small learning rate, the potential value is nondecreasing ( Figure 1 , right), and this does not require alternation nor laziness ( Proposition 3.2 ). As a result, FTRL is bound to converge to a set in which the value of the potential is constant. While Theorem 1.1 only establishes an exponential upper bound in 1/\epsilon^{2} , our next result justifies this by establishing a fundamental barrier for FTRL dynamics, which manifests itself with or without alternation or laziness. Theorem 1.2 . In two-player m\times m potential games, FTRL can take 2^{\Omega(m\log m)} iterations to converge to an \epsilon -Nash equilibrium for \epsilon=1/{\mathsf{poly}}(m) . This holds for any permutation-invariant regularizer and learning rate \eta^{(t)}=1/t^{\alpha} for \alpha\in[0,1) . Crucially, this theorem applies to any member of FTRL with a permutation invariant regularizer, which encompasses most common incarnations of FTRL ( Figure 1 , left). By virtue of known equivalences, Theorem 1.2 thereby circumscribes specific MD algorithms as well, most notably MWU . Furthermore, Theorem 1.2 holds even under a vanishing learning rate \eta^{(t)}=1/t^{\alpha} for \alpha\in[0,1) . The analytical challenge in this regime stems from the propensity of FTRL to mix actions, especially when the learning rate is close to zero. Another notable aspect of our lower bound construction is that it tightly mirrors the mechanism driving our upper bound. Finally, we turn our attention to n -player potential games. We analyze fictitious play ( FP ) [ Robinson 1951 , Brown 1951 ] , the foundational learning algorithm in games, which can be viewed as the extreme version of FTRL when \eta\to\infty . We show that FP can take doubly exponentially many iterations to converge to a Nash equilibrium. Theorem 1.3 . There is an n -player binary-action potential game in which FP takes 2^{\Omega(2^{n})} iterations to reach an \epsilon -Nash equilibrium for \epsilon=1/2^{n} . This constitutes an exponentially stronger lower bound relative to prior work [ Panageas et al. 2023 , Brandt et al. 2013 ] . From a technical standpoint, our multi-player construction distills the essential property behind the two-player lower bound by making a connection to a classic graph-theoretic problem connected to coding theory ( Section 5 ). 1.2 Related work Learning in potential games There is a rich literature on the convergence of learning dynamics in potential games. Unlike general games, potential games always admit a pure Nash equilibrium, and better-response dynamics converge to one [ Rosenthal 1973 , Monderer and Shapley