(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915763782156288 |
|---|---|
| author | Anagnostides, Ioannis Panageas, Ioannis Patris, Nikolas Sandholm, Tuomas |
| author_facet | Anagnostides, Ioannis Panageas, Ioannis Patris, Nikolas Sandholm, Tuomas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_23248 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | (Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games Anagnostides, Ioannis Panageas, Ioannis Patris, Nikolas Sandholm, Tuomas Computer Science and Game Theory 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. |
| title | (Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.23248 |