Separation of Nonergodic Uniform Convergence Rates for Regularized Learning in Games

References

• Abernethy JD, Hazan E, Rakhlin A (2008) Competing in the dark: An efficient algorithm for bandit linear optimization. Servedio RA, Zhang T, eds. Proc. 21st Annual Conf. Learn. Theory (Omnipress, Madison, WI), 263–274.Google Scholar
• Aggarwal G, Badanidiyuru A, Balseiro SR, Bhawalkar K, Deng Y, Feng Z, Goel G, et al. (2024) Auto-bidding and auctions in online advertising: A survey. ACM SIGecom Exchanges 22(1):159–183.Crossref, Google Scholar
• Anagnostides I, Panageas I, Farina G, Sandholm T (2022) On last-iterate convergence beyond zero-sum games. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Internat. Conf. Machine Learn. (PMLR, Cambridge, MA), 536–581.Google Scholar
• Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: A meta-algorithm and applications. Theory Comput. 8(1):6.Crossref, Google Scholar
• Arunachaleswaran ER, Collina N, Kannan S, Roth A, Ziani J (2025) Algorithmic collusion without threats. Meka R, ed. Innovations Theoret. Comput. Sci. Conf. (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 10:1–10:21.Google Scholar
• Ba W, Lin T, Zhang J, Zhou Z (2025) Doubly optimal no-regret online learning in strongly monotone games with bandit feedback. Oper. Res. 73(6):3219–3244.Link, Google Scholar
• Bailey JP, Piliouras G (2018) Multiplicative weights update in zero-sum games. Tardos É, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 321–338.Google Scholar
• Bailey J, Piliouras G (2019) Fast and furious learning in zero-sum games: Vanishing regret with non-vanishing step sizes. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 12977–12987.Google Scholar
• Bakhtin A, Brown N, Dinan E, Farina G, Flaherty C, Fried D, Goff A, et al. (2022) Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science 378(6624):1067–1074.Crossref, Google Scholar
• Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Bousquet O, Hanneke S, Moran S, Van Handel R, Yehudayoff A (2021) A theory of universal learning. Khuller S, Vassilevska Williams V, eds. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 532–541.Google Scholar
• Braverman M, Mao J, Schneider J, Weinberg M (2018) Selling to a no-regret buyer. Tardos É, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 523–538.Google Scholar
• Brown GW (1951) Iterative solution of games by fictitious play. Koopmans TC, ed. Activity Analysis of Production and Allocation (John Wiley, New York), 374–376.Google Scholar
• Brown N, Sandholm T (2018) Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science 359(6374):418–424.Crossref, Google Scholar
• Brown N, Sandholm T (2019) Superhuman AI for multiplayer poker. Science 365(6456):885–890.Crossref, Google Scholar
• Cai Y, Oikonomou A, Zheng W (2022) Finite-time last-iterate convergence for learning in multi-player games. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Adv. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 33904–33919.Google Scholar
• Cai Y, Farina G, Grand-Clément J, Kroer C, Lee CW, Luo H, Zheng W (2024) Fast last-iterate convergence of learning in games requires forgetful algorithms. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds. Thirty-Eighth Annual Conf. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 23406–23434.Google Scholar
• Calvano E, Calzolari G, Denicolò V, Pastorello S (2020) Artificial intelligence, algorithmic pricing, and collusion. Amer. Econom. Rev. 110(10):3267–3297.Crossref, Google Scholar
• Cesa-Bianchi N, Cesari T, Colomboni R, Fusco F, Leonardi S (2024) Bilateral trade: A regret minimization perspective. Math. Oper. Res. 49(1):171–203.Link, Google Scholar
• Chen X, Deng X, Teng SH (2009) Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3):14.Crossref, Google Scholar
• Daskalakis C, Panageas I (2018) The limit points of (optimistic) gradient descent in min-max optimization. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 9256–9266.Google Scholar
• Daskalakis C, Panageas I (2019) Last-iterate convergence: Zero-sum games and constrained min-max optimization. Blum A, ed. 10th Innovations Theoret. Comput. Sci. Conf., Leibniz Internat. Proc. Informatics, vol. 124 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 27:1–27:18.Google Scholar
• Daskalakis C, Fishelson M, Golowich N (2021) Near-optimal no-regret learning in general games. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 27604–27616.Google Scholar
• Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. Comm. ACM 52(2):89–97.Crossref, Google Scholar
• Daskalakis C, Ilyas A, Syrgkanis V, Zeng H (2018) Training GANs with optimism. Proc. 6th Internat. Conf. Learn. Representations, https://openreview.net/forum?id=SJJySbbAZ.Google Scholar
• Deng X, Hu X, Lin T, Zheng W (2022) Nash convergence of mean-based learning algorithms in first price auctions. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. Proc. ACM Web Conf. 2022 (Association for Computing Machinery, New York), 141–150.Google Scholar
• Dütting P, Feldman M, Talgam-Cohen I (2024) Algorithmic contract theory: A survey. Foundations Trends Theoret. Comput. Sci. 16(3–4):211–411.Crossref, Google Scholar
• Duvocelle B, Mertikopoulos P, Staudigl M, Vermeulen D (2023) Multiagent online learning in time-varying games. Math. Oper. Res. 48(2):914–941.Link, Google Scholar
• Farina G, Kroer C, Sandholm T (2021) Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. Proc. AAAI Conf. Artificial Intelligence 35(6):5363–5371.Crossref, Google Scholar
• Farina G, Kroer C, Sandholm T (2025) Better regularization for sequential decision spaces: Fast convergence rates for Nash, correlated, and team equilibria. Oper. Res. 73(5):2430–2457.Link, Google Scholar
• Farina G, Kroer C, Lee CW, Luo H (2022a) Clairvoyant regret minimization: Equivalence with Nemirovski’s conceptual prox method and extension to general convex games. Preprint, submitted August 31, https://arxiv.org/abs/2208.14891.Google Scholar
• Farina G, Lee CW, Luo H, Kroer C (2022b) Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (PMLR, Cambridge, MA), 6337–6357.Google Scholar
• Flaspohler GE, Orabona F, Cohen J, Mouatadid S, Oprescu M, Orenstein P, Mackey L (2021) Online learning with optimism and delay. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (PMLR, Cambridge, MA), 3363–3373.Google Scholar
• Freund Y, Schapire RE (1996) Game theory, on-line prediction and boosting. Blum A, Kearns MJ, eds. Proc. Ninth Annual Conf. Comput. Learn. Theory (Association for Computing Machinery, New York), 325–332.Google Scholar
• Freund Y, Schapire RE (1999) Adaptive game playing using multiplicative weights. Games Econom. Behav. 29(1–2):79–103.Crossref, Google Scholar
• Golowich N, Pattathil S, Daskalakis C (2020) Tight last-iterate convergence rates for no-regret learning in multi-player games. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 20766–20778.Google Scholar
• Gorbunov E, Taylor A, Gidel G (2022) Last-iterate convergence of optimistic gradient method for monotone variational inequalities. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Adv. Neural Inform. Processing Systems, vol. 35 (Curran Associates, Inc., Red Hook, NY), 21858–21870.Google Scholar
• Hart S, Mas-Colell A (2000) A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5):1127–1150.Crossref, Google Scholar
• Hart S, Mas-Colell A (2003) Uncoupled dynamics do not lead to Nash equilibrium. Amer. Econom. Rev. 93(5):1830–1836.Crossref, Google Scholar
• Hartline JD, Long S, Zhang C (2024) Regulation of algorithmic collusion. Proc. Sympos. Comput. Sci. Law (Association for Computing Machinery, New York), 98–108.Google Scholar
• Ho CJ, Slivkins A, Vaughan JW (2014) Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. Babaioff M, Conitzer V, Easley DA, eds. Proc. Fifteenth ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 359–376.Google Scholar
• Hsieh Y-G, Antonakopoulos K, Mertikopoulos P (2021) Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. Belkin M, Kpotufe S, eds. Proc. Thirty Fourth Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 134 (PMLR, Cambridge, MA), 2388–2422.Google Scholar
• Hsieh YG, Iutzeler F, Malick J, Mertikopoulos P (2019) On the convergence of single-call stochastic extra-gradient methods. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 6936–6946.Google Scholar
• Jordan M, Lin T, Zhou Z (2025) Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback. Oper. Res. 73(3):1675–1702.Link, Google Scholar
• Kolumbus Y, Nisan N (2022) Auctions between regret-minimizing agents. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. Proc. ACM Web Conf. 2022 (Association for Computing Machinery, New York), 100–111.Google Scholar
• Koolen WM, Warmuth MK, Kivinen J (2010) Hedging structured concepts. Tauman Kalai A, Mohri M, eds. COLT 2010 Proc. 23rd Annual Conf. Learn. Theory (Omnipress, Madison, WI), 93–105.Google Scholar
• Kumar R, Schneider J, Sivan B (2024) Strategically-robust learning algorithms for bidding in first-price auctions. Bergemann D, Kleinberg R, Sabán D, eds. Proc. 25th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 893–893.Google Scholar
• Lazarsfeld J, Piliouras G, Sim R, Skoulakis S (2025) Optimism without regularization: Constant regret in zero-sum games. Belgrave D, Zhang C, Lin H, Pascanu R, Koniusz P, Ghassemi M, Chen N, eds. Adv. Neural Inform. Processing Systems, vol. 38 (Curran Associates, Inc., Red Hook, NY), 121723–121758.Google Scholar
• Lee CW, Kroer C, Luo H (2021) Last-iterate convergence in extensive-form games. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 14293–14305.Google Scholar
• Liu Y, Oikonomou A, Zheng W, Cai Y, Cohan A (2024) A meta-algorithm for aligning LLMs with general preferences. NeurIPS 2024 Workshop Fine-Tuning Modern Machine Learn. Principles Scalability. https://openreview.net/forum?id=ZPPLKEnrPf.Google Scholar
• Luo H (2022a) CSCI 659 lecture 2. Accessed July 31, 2026, https://haipeng-luo.net/courses/CSCI659/2022_fall/lectures/lecture2.pdf.Google Scholar
• Luo H (2022b) CSCI 659 lecture 5. Accessed July 31, 2026, https://haipeng-luo.net/courses/CSCI659/2022_fall/lectures/lecture5.pdf.Google Scholar
• Mertikopoulos P, Papadimitriou C, Piliouras G (2018) Cycles in adversarial regularized learning. Czumaj A, ed. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2703–2717. Google Scholar
• Mertikopoulos P, Lecouat B, Zenati H, Foo CS, Chandrasekhar V, Piliouras G (2019) Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. Proc. 7th Internat. Conf. Learn. Representations, https://openreview.net/forum?id=Bkg8jjC9KQ.Google Scholar
• Mokhtari A, Ozdaglar AE, Pattathil S (2020) Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM J. Optim. 30(4):3230–3251.Crossref, Google Scholar
• Moravčík M, Schmid M, Burch N, Lisý V, Morrill D, Bard N, Davis T, Waugh K, Johanson M, Bowling M (2017) DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science 356(6337):508–513.Crossref, Google Scholar
• Mordukhovich BS, Peña JF, Roshchina V (2010) Applying metric regularity to compute a condition measure of a smoothing algorithm for matrix games. SIAM J. Optim. 20(6):3490–3511.Crossref, Google Scholar
• Munos R, Valko M, Calandriello D, Azar MG, Rowland M, Guo ZD, Tang Y, et al. (2024) Nash learning from human feedback. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (PMLR, Cambridge, MA), 36743–36768.Google Scholar
• Muthukumar V, Phade S, Sahai A (2025) On the impossibility of convergence of mixed strategies with no-regret learning. Math. Oper. Res. 50(4):2794–2833.Link, Google Scholar
• Nekipelov D, Syrgkanis V, Tardos E (2015) Econometrics for learning agents. Roughgarden T, Feldman M, Schwarz M, eds. Proc. Sixteenth ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1–18.Google Scholar
• Nemirovski A (2004) Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Crossref, Google Scholar
• Panageas I, Patris N, Skoulakis S, Cevher V (2023) Exponential lower bounds for fictitious play in potential games. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Adv. Neural Inform. Processing Systems, vol. 36 (Curran Associates, Inc., Red Hook, NY), 32401–32423.Google Scholar
• Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532. Crossref, Google Scholar
• Perolat J, De Vylder B, Hennes D, Tarassov E, Strub F, de Boer V, Muller P, et al. (2022) Mastering the game of Stratego with model-free multiagent reinforcement learning. Science 378(6623):990–996.Crossref, Google Scholar
• Perolat J, Munos R, Lespiau JB, Omidshafiei S, Rowland M, Ortega P, Burch N, et al. (2021) From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (PMLR, Cambridge, MA), 8525–8535.Google Scholar
• Popov LD (1980) A modification of the Arrow–Hurwicz method for search of saddle points. Math. Notes Acad. Sci. USSR 28:845–848.Google Scholar
• Rakhlin S, Sridharan K (2013) Optimization, learning, and games with predictable sequences. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems, vol. 26 (Curran Associates, Inc., Red Hook, NY), 3066–3074.Google Scholar
• Robinson J (1951) An iterative method of solving a game. Ann. Math. 54(2):296–301.Crossref, Google Scholar
• Sato Y, Akiyama E, Farmer JD (2002) Chaos in learning a simple two-person game. Proc. Natl. Acad. Sci. USA 99(7):4748–4751.Crossref, Google Scholar
• Swamy G, Dann C, Kidambi R, Wu S, Agarwal A (2024) A minimaximalist approach to reinforcement learning from human feedback. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (PMLR, Cambridge, MA), 47345–47377.Google Scholar
• Syrgkanis V, Agarwal A, Luo H, Schapire RE (2015) Fast convergence of regularized learning in games. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 28 (Curran Associates, Inc., Red Hook, NY), 2989–2997.Google Scholar
• Takimoto E, Warmuth MK (2003) Path kernels and multiplicative updates. J. Machine Learn. Res. 4(5):773–818. Google Scholar
• Tammelin O, Burch N, Johanson M, Bowling M (2015) Solving heads-up limit Texas hold’em. Yang Q, Wooldridge MJ, eds. Proc. Twenty-Fourth Internat. Joint Conf. Artificial Intelligence (AAAI Press/International Joint Conferences on Artificial Intelligence, Palo Alto, CA), 645–652.Google Scholar
• Tseng P (1995) On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60(1–2):237–252.Crossref, Google Scholar
• van Erven T (2021) Why FTRL is better than online mirror descent. Accessed May 22, 2024, https://www.timvanerven.nl/blog/ftrl-vs-omd/.Google Scholar
• Vlatakis-Gkaragkounis EV, Flokas L, Lianeas T, Mertikopoulos P, Piliouras G (2020) No-regret learning and mixed Nash equilibria: They do not mix. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 1380–1391.Google Scholar
• Wang M, Ma C, Chen Q, Meng L, Han Y, Xiao J, Zhang Z, Huo J, Su WJ, Yang Y (2025) Magnetic preference optimization: Achieving last-iterate convergence for language model alignment. Proc. 13th Internat. Conf. Learn. Representations, https://openreview.net/forum?id=PDnEDS244P.Google Scholar
• Wei CY, Lee CW, Zhang M, Luo H (2021) Linear last-iterate convergence in constrained saddle-point optimization. Proc. 13th Internat. Conf. Learn. Representations, https://openreview.net/forum?id=a3PmRgAB5T.Google Scholar
• Wu Y, Sun Z, Yuan H, Ji K, Yang Y, Gu Q (2025a) Self-play preference optimization for language model alignment. Thirteenth Internat. Conf. Learn. Representations.Google Scholar
• Wu Y, Viano L, Chen Y, Zhu Z, Antonakopoulos K, Gu Q, Cevher V (2025b) Multi-step alignment as Markov games: An optimistic online gradient descent approach with convergence guarantees. Preprint, submitted February 18, https://arxiv.org/abs/2502.12678.Google Scholar
• Zhang Y, Yu D, Peng B, Song L, Tian Y, Huo M, Jiang N, Mi H, Yu D (2025) Iterative Nash policy optimization: Aligning LLMs with general preferences via no-regret learning. Proc. 13th Internat. Conf. Learn. Representations, https://openreview.net/forum?id=Pujt3ADZgI.Google Scholar
• Zhou R, Fazel M, Du SS (2025) Extragradient preference optimization (EGPO): Beyond last-iterate convergence for Nash learning from human feedback. Conf. Language Modeling, https://openreview.net/forum?id=EP7mAqx2BO.Google Scholar
• Zhou Z, Mertikopoulos P, Moustakas AL, Bambos N, Glynn P (2021) Robust power management via learning and game design. Oper. Res. 69(1):331–345.Link, Google Scholar
• Zinkevich M, Johanson M, Bowling M, Piccione C (2007) Regret minimization in games with incomplete information. Platt J, Koller D, Singer Y, Roweis S, eds. Adv. Neural Inform. Processing Systems, vol. 20 (Curran Associates, Inc., Red Hook, NY), 1729–1736.Google Scholar