(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games

Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:2577-2613, 2026.

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_{\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-anagnostides26b, title = {({D}oubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games}, author = {Anagnostides, Ioannis and Panageas, Ioannis and Patris, Nikolas and Sandholm, Tuomas}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {2577--2613}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/anagnostides26b/anagnostides26b.pdf}, url = {https://proceedings.mlr.press/v306/anagnostides26b.html}, 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_{\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.} }
Endnote
%0 Conference Paper %T (Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games %A Ioannis Anagnostides %A Ioannis Panageas %A Nikolas Patris %A Tuomas Sandholm %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-anagnostides26b %I PMLR %P 2577--2613 %U https://proceedings.mlr.press/v306/anagnostides26b.html %V 306 %X 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_{\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.
APA
Anagnostides, I., Panageas, I., Patris, N. & Sandholm, T.. (2026). (Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:2577-2613 Available from https://proceedings.mlr.press/v306/anagnostides26b.html.

Related Material