On Last-Iterate Convergence Beyond Zero-Sum Games

Ioannis AnagnostidesIoannis PanageasGabriele FarinaTuomas Sandholm

article2022ICML60 citationsOutstanding Paper Runner Up

Establishes last-iterate convergence rates and optimal regret bounds for optimistic mirror descent across broader game classes beyond zero-sum settings, including polymatrix, strategically zero-sum, and potential games where players can use heterogeneous algorithms.

Listen

In multi-agent machine learning and decentralized systems, agents frequently learn and adapt through repeated interactions. Standard algorithmic guarantees focus on time-averaged performance, showing that the running average of play will approximate an equilibrium. However, time-average guarantees offer limited insight into the actual day-to-day state of a system, which can exhibit unstable, recurrent, or chaotic dynamics. Existing theoretical guarantees establishing last-iterate convergence—where the agents' immediate, final strategies stabilize directly at an equilibrium—have largely been confined to two-player zero-sum games under the restrictive assumption that all participants use identical learning dynamics.

The article evaluates whether and how last-iterate convergence can be extended beyond zero-sum settings to broader classes of games, while also accommodating heterogeneous learning algorithms among independent agents. To achieve this, the authors develop a theoretical framework that unifies regret-based analyses with dynamical systems theory. They evaluate learning dynamics—primarily optimistic mirror descent and optimistic gradient descent—across normal-form games, extensive-form games, potential and near-potential games, and unconstrained continuous formulations.

The article establishes several core theoretical and practical findings. First, across constant-sum polymatrix, strategically zero-sum, and zero-sum extensive-form games, optimistic dynamics bounded by utility variations guarantee bounded trajectory lengths. This ensures that algorithms reach an approximate Nash equilibrium within an optimal rate of iterations while incurring constant individual regret, even when agents deploy distinct algorithms or advanced prediction mechanisms. Second, in smooth games, optimistic dynamics exhibit a sharp dichotomy: they either stabilize near a Nash equilibrium or their cumulative social welfare strictly outperforms the baseline robust price of anarchy. Third, for potential and near-potential games, mirror descent converges to an approximate equilibrium in polynomial time, yielding constant regret under optimistic updates and unifying distributed learning dynamics in market exchange models. Finally, for continuous general-sum interactions, optimistic gradient descent converges linearly when the product of the payoff matrices has strictly negative real eigenvalues; however, even infinitesimal deviations can cause complete divergence, and converged states can experience severe efficiency losses compared to optimal coordination outcomes.

These findings provide foundational insights for designing and deploying independent automated agents in decentralized economic systems, auctions, and competitive machine learning models such as generative adversarial networks. They demonstrate that practitioners do not need to enforce homogeneous algorithms across participants to achieve stable equilibrium points in zero-sum, potential, or market-based structures. However, in general-sum continuous settings, relying on optimistic first-order gradient methods introduces severe operational risks, including vulnerability to small environment perturbations and costly failures to coordinate on socially optimal states.

For practitioners deploying multi-agent algorithms, the article supports using optimistic mirror descent with smooth regularizers and constant learning rates in competitive, extensive-form, and potential games. In continuous or general-sum games, systems designers should avoid assuming that first-order gradient stability translates into efficient outcomes, and should instead evaluate whether domain-specific coordination mechanisms are necessary. Further work is required to extend last-iterate convergence to non-smooth regularizers, examine multilinear multiplayer interactions, and design control mechanisms that reconcile stability with social welfare maximization.

The conclusions are theoretical in nature, relying on standard compact action spaces and specific structural assumptions such as spectral properties in continuous games and smoothness in regularizers. While confidence in the mathematical guarantees and corresponding benchmark simulations is high within the defined game classes, readers should exercise caution when extrapolating these stability guarantees to unstructured general-sum landscapes.

Carnegie Mellon University Optimized Markets, Inc.Strategic Machine, Inc.Strategy Robot, Inc.University of California, Irvine zero-sum game last-iterate convergence zero-sum games convex-concave games

arXiv: 2203.12056

Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). Its projected-gradient framework and regret bounds supply core online-learning ideas that the source brings into its analysis of agents’ game dynamics.
Paper: Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms, Kaiqing Zhang et al. (2019). This overview maps the cooperative, competitive, and general-sum settings whose differing convergence guarantees motivate the source’s move beyond zero-sum games.
Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). Its treatment of online convex optimization and regret provides useful groundwork for following the source’s regret-based analysis of learning dynamics.

No sufficiently relevant recommendations were found.

Cover for On Last-Iterate Convergence Beyond Zero-Sum Games

Abstract

Most existing results about last-iterate convergence of learning dynamics are limited to two-player zero-sum games, and only apply under rigid assumptions about what dynamics the players follow. In this paper we provide new results and techniques that apply to broader families of games and learning dynamics. First, we show that in a class of games that includes constant-sum polymatrix and strategically zero-sum games, the trajectories of dynamics such as optimistic mirror descent (OMD) exhibit a boundedness property, which holds even when players employ different algorithms and prediction mechanisms. This property enables us to obtain O(1/√T) rates and optimal O(1) regret bounds. Our analysis also reveals a surprising property: OMD either reaches arbitrarily close to a Nash equilibrium or it outperforms the robust price of anarchy in efficiency. Moreover, for potential games we establish convergence to an ε-equilibrium after O(1/ε^2) iterations for mirror descent under a broad class of regularizers, as well as optimal O(1) regret bounds for OMD variants. Our framework also extends to near-potential games, and unifies known analyses for distributed learning in Fisher’s market model. Finally, we analyze the convergence, efficiency, and robustness of optimistic gradient descent (OGD) in general-sum continuous games.

Topics

zero-sum game

Keywords

last-iterate convergence zero-sum games convex-concave games constant-sum polymatrix games near-potential games optimistic gradient descent Nash equilibrium no-regret learning stochastic games extensive-form games

1. Introduction
2. Preliminaries
3. Optimistic Learning in Games
3.3 Convergence of the Social Welfare
4. Convergence with the Potential Method
5. Continuous Games
6. Experiments
Acknowledgements
References
A. Proofs from Section 3
A.1 Smooth Convex-Concave Games
A.2 Bilinear Saddle-Point Problems
B. Proofs from Section 4
B.1 Near-Potential Games
B.2 Fisher Markets
C. Proofs from Section 5
D. Experiments

Knowls

Knowl 1 — RVU bounds imply bounded cumulative movement
theoretical result
Consider an $n$ -player game in which player $i$ chooses a strategy $x_i^{(t)}$ at iteration $t$ and has cumulative regret $\mathrm{Reg}_i^T$ . Suppose each player's learning algorithm satisfies, for every $T$ , an RVU bound of the form
$\mathrm{Reg}_i^T \le \alpha_i+\beta_i\sum_{t=1}^T\|u_i^{(t)}-u_i^{(t-1)}\|_\infty^2-\gamma_i\sum_{t=1}^T\|x_i^{(t)}-x_i^{(t-1)}\|_1^2,$
where $u_i^{(t)}$ is player $i$ 's utility vector, and the parameters satisfy $\gamma_i\ge 2(n-1)\sum_{j\ne i}\beta_j$ . If the game and play sequence also satisfy $\sum_i\mathrm{Reg}_i^T\ge 0$ for every $T$ , then
$\sum_{i=1}^n\gamma_i\sum_{t=1}^T\|x_i^{(t)}-x_i^{(t-1)}\|_1^2\le 2\sum_{i=1}^n\alpha_i.$
Thus cumulative squared movement is bounded independently of the time horizon. The result permits different players to use different regret-minimizing algorithms, provided their RVU parameters meet the stated condition.
Knowl 2 — Game classes with nonnegative total regret
theoretical result
The condition $\sum_i\mathrm{Reg}_i^T\ge 0$ for every horizon $T$ holds for two-player zero-sum games, zero-sum polymatrix games, constant-sum polymatrix games, strategically zero-sum games, and polymatrix strategically zero-sum games. The paper also establishes it for convex-concave zero-sum games and broader zero-sum minimax settings, including games whose minimax values agree and the stated quasiconvex-quasiconcave and zero-sum stochastic-game cases. Here a polymatrix game assigns pairwise games to graph edges, and a strategically zero-sum game has the same strategic incentives as a zero-sum game. For strategically zero-sum games with unequal payoff scales, the corresponding claim requires appropriately weighted regrets and learning rates; the unweighted statement applies under the paper's balanced-scale condition.
Knowl 3 — OMD reaches an approximate Nash equilibrium in finite time
theoretical result
Suppose players in a finite normal-form game use optimistic mirror descent (OMD), the sum of their regrets is nonnegative at every horizon, and each player's regularizer is smooth. Assume the norms used by the players satisfy $\|v\|\ge C\|v\|_1$ and $\|w\|_*\le C_*\|w\|_\infty$ , with positive constants $C,C_*$ . Let $G_i$ be a gradient-Lipschitz constant for player $i$ 's regularizer, let $\Omega_i$ be its maximum Bregman divergence over the strategy set, and let $\Omega_i'$ be the diameter of that set in the player's norm. With learning rate $\eta\le C/[4C_*(n-1)]$ , after more than $8\sum_i\Omega_i/\epsilon^2$ iterations there is an iterate that is an $\epsilon(C_*+2\max_i G_i\Omega_i'/\eta)$ -approximate Nash equilibrium. In particular, for fixed game and regularizer parameters, the required number of iterations scales as $O(1/\epsilon^2)$ ; the guarantee is for some iterate among those generated, not necessarily every iterate.
Knowl 4 — Optimal constant individual regret from bounded movement
theoretical result
Under the bounded-movement conditions for RVU algorithms—namely, nonnegative total regret at every horizon and $\gamma_i\ge2(n-1)\sum_{j\ne i}\beta_j$ —suppose all players have common RVU parameters $\alpha_i=\alpha$ , $\beta_i=\beta$ , and $\gamma_i=\gamma$ . Then every player's regret is bounded for all horizons by
$\mathrm{Reg}_i^T\le \alpha+\frac{2n(n-1)\alpha\beta}{\gamma}.$
For OMD with a common learning rate $\eta=1/[4(n-1)]$ , the paper gives $\mathrm{Reg}_i^T\le 8n\Omega_i\le8n\log|A_i|$ , where $A_i$ is player $i$ 's action set and $\Omega_i$ is the regularizer's initial Bregman-divergence bound. This is an $O(1)$ individual-regret guarantee, even though the players need not be in a two-player zero-sum game.
Knowl 5 — Heterogeneous mirror descent ascends potential games
theoretical result
Let $\Phi$ be a bounded potential on the product of players' mixed-strategy simplexes. Assume it satisfies the one-sided smoothness condition $\Phi(x)\le \Phi(\tilde x)-\langle\nabla\Phi(x),\tilde x-x\rangle+L\|\tilde x-x\|_2^2$ , and that each player's coordinate derivative of $\Phi$ equals a strictly increasing transformation $g_i$ of that player's action utility. If players use mirror descent with possibly different regularizers, each 1-strongly convex in Euclidean norm, and learning rate $\eta=1/(2L)$ , then
$\Phi(x^{(t+1)})-\Phi(x^{(t)})\ge\frac{1}{2\eta}\sum_{i=1}^n\|x_i^{(t+1)}-x_i^{(t)}\|_2^2\ge0.$
Consequently, the total squared movement of the iterates is bounded by the range of the bounded potential. For identity transformations $g_i$ , if the regularizers also have Lipschitz gradients, this movement bound yields an $\epsilon$ -approximate Nash equilibrium at some iterate after $O(1/\epsilon^2)$ iterations. The result applies to heterogeneous mirror-descent dynamics, not only to players sharing one regularizer.
Knowl 6 — Optimistic multiplicative weights has optimal regret in potential games
theoretical result
In a finite potential game, if every player uses optimistic multiplicative weights update (OMWU) with a sufficiently small fixed learning rate, then each player's cumulative regret is $O(1)$ , uniformly in the number of iterations. One sufficient learning-rate condition in the paper is, for every player $i$ ,
$\eta\le\min\left\{\frac{1}{2L},\frac{1}{2\sqrt{|A_i|(n-1)}},\frac{1}{4\sum_{j\ne i}\sqrt{|A_j|}}\right\},$
where $L$ is the potential's one-sided smoothness parameter, $n$ is the number of players, and $|A_i|$ is player $i$ 's number of actions. This establishes optimal constant individual regret for an optimistic learning method in potential games.
Knowl 7 — Near-potential games retain approximate potential ascent
theoretical result
Measure the distance between two games with the same action sets by the maximum, over players and unilateral deviations, of the difference in the utility improvement produced by that deviation. A game is $\delta$ -near-potential if such a distance of at most $\delta$ separates it from a potential game. If players use mirror descent with learning rate $\eta=1/(2L)$ , 1-strongly convex and smooth regularizers, and $L$ is the smoothness parameter of the nearby potential, then that bounded potential increases whenever the current profile is not an $O(\sqrt{\delta})$ -approximate Nash equilibrium. Thus the potential-game ascent guarantee is robust to this deviation-based perturbation, with the equilibrium accuracy degrading on the order of $\sqrt{\delta}$ .
Knowl 8 — Smooth games yield an equilibrium-or-welfare dichotomy
theoretical result
A game is $(\lambda,\mu)$ -smooth if, for every action profiles $a,a^*$ , the sum of utilities from players unilaterally switching to their actions in $a^*$ while others play $a$ is at least $\lambda\,\mathrm{SW}(a^*)-\mu\,\mathrm{SW}(a)$ . Let $\mathrm{OPT}$ be maximum social welfare and use OMD with suitable smooth regularizers and learning rate $\eta$ . For any $\gamma>0$ and a sufficiently long run of order $1/\gamma^2$ , either some iterate is an $O(\gamma)$ -approximate Nash equilibrium, or the average social welfare satisfies
$\frac{1}{T}\sum_{t=1}^T\mathrm{SW}(x^{(t)})\ge \frac{\lambda}{1+\mu}\,\mathrm{OPT}+\frac{\gamma^2}{16\eta(1+\mu)}.$
The second case strictly exceeds the welfare guarantee associated with the game's robust price of anarchy, $\lambda/(1+\mu)$ , by an additive term. The dichotomy relies on the possibility of negative cumulative regret when play remains far from equilibrium.
Knowl 9 — A spectral condition guarantees linear OGD convergence in two-player games
theoretical result
Consider unconstrained bilinear games with strategies $x,y\in\mathbb R^d$ and utilities $u_X(x,y)=x^\top Ay$ and $u_Y(x,y)=x^\top By$ , where $A,B\in\mathbb R^{d\times d}$ are square and full rank. Optimistic gradient descent updates each player's strategy using twice the current gradient minus the preceding gradient, with learning rate $\eta$ . If every eigenvalue of $A^\top B$ is real and strictly negative, then for $\eta\le1/(2\sqrt{\rho(A^\top B)})$ , where $\rho$ is spectral radius, OGD converges linearly to an equilibrium. This includes two-player zero-sum games, but also some general-sum games.
Knowl 10 — OGD converges in a multiplayer star polymatrix game under a spectral condition
theoretical result
Consider an unconstrained polymatrix game in which player 1 interacts with each of players $2,\ldots,n$ , and there are no interactions among the latter players. Let $A_{1,j}$ and $A_{j,1}$ be the payoff matrices for the two directions of interaction between player 1 and player $j$ . If the matrix
$M=\sum_{j=2}^n A_{1,j}A_{j,1}$
has only strictly negative real eigenvalues, then a sufficiently small positive OGD learning rate, determined by the spectrum of $M$ , yields linear convergence to an equilibrium. The condition is satisfied in the stated zero-sum polymatrix case. This extends the two-player spectral characterization to a structured multiplayer setting.
Knowl 11 — Convergent OGD can select an arbitrarily inefficient equilibrium
theoretical result
For arbitrarily large $R$ , consider two players with strategies in closed $\ell_1$ balls of radius $R$ in $\mathbb R^2$ and bilinear utilities $u_X(x,y)=x^\top Ay$ and $u_Y(x,y)=x^\top By$ , with
$A=\begin{pmatrix}1&-2\\-1&1\end{pmatrix},\qquad B=\begin{pmatrix}1&1\\1&-1\end{pmatrix}.$
For a sufficiently small OGD learning rate, play from any initialization converges to the equilibrium $(0,0)$ , whose social welfare is zero. Yet $(x^*,y^*)=((R,0),(R,0))$ is also an equilibrium and has social welfare $2R^2$ . Hence OGD's stable limit can be arbitrarily worse in welfare than another equilibrium, despite convergence from every initialization.
Knowl 12 — Arbitrarily small departures from zero-sum can destabilize OGD
theoretical result
For every $\epsilon>0$ , take two-player bilinear games with
$A=\begin{pmatrix}1&0\\0&\epsilon/2\end{pmatrix},\qquad B=\begin{pmatrix}-1&0\\0&\epsilon/2\end{pmatrix}.$
The Frobenius distance from zero-sum satisfies $\|A+B\|_F=\epsilon$ , but OGD diverges from any nontrivial initialization in the game $(A,B)$ . In the corresponding zero-sum game $(A,-A)$ , OGD converges for learning rates $\eta\le1/2$ . Thus arbitrarily small payoff perturbations can change OGD from convergent to divergent.
Knowl 13 — Linear Fisher-market dynamics are proportional response
model/method
In a linear Fisher market with agents $i$ , goods $j$ , budgets $B_i$ , and unit supply of each good, let $b_i(j)$ denote agent $i$ 's expenditure on good $j$ , $u_i(j)$ its value for that good, and $p(j)=\sum_i b_i(j)$ the price. The Shmyrev convex-program potential is
$\Phi(b)=\sum_{i,j}b_i(j)\log u_i(j)-\sum_j p(j)\log p(j),$
subject to each agent spending its budget and market spending on each good summing to its price. Its gradient coordinate is $\log(u_i(j)/p(j))-1$ . Applying mirror descent with negative-entropy regularization and transformation $g(z)=\log z-1$ gives the proportional-response update
$b_i^{(t+1)}(j)=B_i\frac{u_i(j)x_i^{(t)}(j)}{\sum_k u_i(k)x_i^{(t)}(k)},$
where $x_i^{(t)}(j)$ is the current allocation share. These distributed updates correspond to optimizing the market potential and converge to an equilibrium at rate $O(1/T)$ under the concavity result used in the paper.
Knowl 14 — Experiments show last-iterate convergence in poker extensive-form games
empirical result
The paper evaluates OMD with Euclidean regularization on the zero-sum Kuhn poker and Leduc poker benchmarks, representing each game as a bilinear saddle-point problem. Each run lasts 10,000 iterations; the plotted diagnostics track the saddle-point gap for both the last iterate and the time-average iterate. For each game, the tested learning rates are $1/(4\|A\|_2)$ , $1/(10\|A\|_2)$ , and $1/(20\|A\|_2)$ , where $A$ is the saddle-point payoff matrix and $\|A\|_2$ its spectral norm. The plots on page 9 show decreasing gaps for both diagnostics, with larger tested learning rates converging faster in these experiments.
Knowl 15 — No regular historical-gradient method is stable on every general-sum game
theoretical result
Consider a finite-memory first-order method of the form $x_i^{(t+1)}=\sum_{\tau=0}^K\alpha^{(\tau)}x_i^{(t-\tau)}+\sum_{\tau=0}^K\beta^{(\tau)}\nabla_{x_i}u_i(x^{(t-\tau)})$ . Define $S(z)=\sum_{\tau=0}^K\alpha^{(\tau)}z^{-\tau}$ and $G(z)=\sum_{\tau=0}^K\beta^{(\tau)}z^{-\tau}$ . If the method is regular, meaning $S(1)=1$ and $G(1)\ne0$ , then there exists a two-player game for which the method diverges from every nontrivial initialization. This class includes optimistic gradient descent. Therefore no method in this regular finite-history class guarantees stability over all general-sum games.

Coverage note — The detailed advanced-prediction variants and their additional normal-form experiments are omitted; the main RVU framework and its principal game-theoretic and continuous-game consequences are retained.

References

1.Abernethy, J. D., Bartlett, P. L., and Hazan, E. Blackwell approachability and no-regret learning are equivalent. In COLT 2011 - The 24th Annual Conference on Learning Theory, volume 19 of JMLR Proceedings, pp. 27–46. JMLR.org, 2011.
2.Adler, I., Daskalakis, C., and Papadimitriou, C. H. A note on strictly competitive games. In Internet and Network Economics, 5th International Workshop, WINE 2009, volume 5929 of Lecture Notes in Computer Science, pp. 471–474. Springer, 2009.
3.Aumann, R. J. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67–96, 1974.
4.Awerbuch, B., Azar, Y., and Epstein, A. The price of routing unsplittable flow. SIAM J. Comput., 42(1):160–177, 2013.
5.Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P. The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pp. 326–358. PMLR, 2021.
6.Babichenko, Y. Query complexity of approximate nash equilibria. In Symposium on Theory of Computing, STOC 2014, pp. 535–544. ACM, 2014.
7.Bailey, J. P. and Piliouras, G. Fast and furious learning in zero-sum games: Vanishing regret with non-vanishing step sizes. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 12977–12987, 2019.
8.Bielawski, J., Chotibut, T., Falniowski, F., Kosiorowski, G., Misiurewicz, M., and Piliouras, G. Follow-the-regularized-leader routes to chaos in routing games. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, volume 139 of Proceedings of Machine Learning Research, pp. 925–935. PMLR, 2021.
9.Birnbaum, B. E., Devanur, N. R., and Xiao, L. Distributed algorithms via gradient descent for fisher markets. In Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), pp. 127–136. ACM, 2011.
10.Blackwell, D. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1 – 8, 1956.
11.Blum, A., Hajiaghayi, M., Ligett, K., and Roth, A. Regret minimization and the price of total anarchy. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 373–382. ACM, 2008.
12.Cai, Y. and Daskalakis, C. On minmax theorems for multiplayer games. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 217–234. SIAM, 2011.
13.Cai, Y., Candogan, O., Daskalakis, C., and Papadimitriou, C. Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2):648–655, 2016.
14.Candogan, O., Ozdaglar, A. E., and Parrilo, P. A. A projection framework for near-potential games. In Proceedings of the 49th IEEE Conference on Decision and Control, CDC 2010, pp. 244–249. IEEE, 2010.
15.Candogan, O., Menache, I., Ozdaglar, A. E., and Parrilo, P. A. Flows and decompositions of games: Harmonic and potential games. Math. Oper. Res., 36(3):474–503, 2011.
16.Candogan, O., Ozdaglar, A. E., and Parrilo, P. A. Dynamics in near-potential games. Games Econ. Behav., 82:66–90, 2013.
17.Chen, C., Surana, A., Bloch, A. M., and Rajapakse, I. Multilinear control systems theory. SIAM Journal on Control and Optimization, 59(1):749–776, 2021.
18.Chen, G. and Teboulle, M. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538–543, 1993.
19.Chen, X., Deng, X., and Teng, S. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3):14:1–14:57, 2009.
20.Cheung, Y. K. and Piliouras, G. Chaos, extremism and optimism: Volume analysis of learning in games. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
21.Cheung, Y. K. and Tao, Y. Chaos of learning beyond zero-sum and coordination via game decompositions. In 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net, 2021.
22.Christodoulou, G. and Koutsoupias, E. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 67–73. ACM, 2005.
23.Christodoulou, G., Kovacs, A., and Schapira, M. Bayesian combinatorial auctions. J. ACM, 63(2):11:1–11:19, 2016.
24.Damme, E. V. Stability and Perfection of Nash Equilibria. Berlin: Springer-Verlag, 1987.
25.Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Blum, A. (ed.), 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, volume 124 of LIPIcs, pp. 27:1–27:18. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2019.
26.Daskalakis, C. and Papadimitriou, C. H. On a network generalization of the minmax theorem. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, volume 5556 of Lecture Notes in Computer Science, pp. 423–434. Springer, 2009.
27.Daskalakis, C., Fabrikant, A., and Papadimitriou, C. H. The game world is flat: The complexity of nash equilibria in succinct games. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, volume 4051 of Lecture Notes in Computer Science, pp. 513–524. Springer, 2006.
28.Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):195–259, 2009.
29.Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. Training gans with optimism. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net, 2018.
30.Daskalakis, C., Foster, D. J., and Golowich, N. Independent policy gradient methods for competitive reinforcement learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020l, 2020.
31.Daskalakis, C., Fishelson, M., and Golowich, N. Near-optimal no-regret learning in general games. CoRR, abs/2108.06924, 2021.
32.Deng, X., Hu, X., Lin, T., and Zheng, W. Nash convergence of mean-based learning algorithms in first price auctions. In WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, pp. 141–150. ACM, 2022.
33.Diakonikolas, J. and Wang, P. Potential function-based framework for making the gradients small in convex and min-max optimization. CoRR, abs/2101.12101, 2021.
34.Du, S. S. and Hu, W. Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, volume 89 of Proceedings of Machine Learning Research, pp. 196–205. PMLR, 2019.
35.Eisenberg, E. and Gale, D. Consensus of Subjective Probabilities: The Pari-Mutuel Method. The Annals of Mathematical Statistics, 30(1):165 – 168, 1959.
36.Feng, Z., Guruganesh, G., Liaw, C., Mehta, A., and Sethi, A. Convergence analysis of no-regret bidding algorithms in repeated auctions. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, pp. 5399–5406. AAAI Press, 2021.
37.Giannou, A., Vlatakis-Gkaragkounis, E., and Mertikopoulos, P. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pp. 2147–2148. PMLR, 2021.
38.Golowich, N., Pattathil, S., and Daskalakis, C. Tight last-iterate convergence rates for no-regret learning in multiplayer games. In Advances in Neural Information Processing Systems 2020, 2020a.
39.Golowich, N., Pattathil, S., Daskalakis, C., and Ozdaglar, A. E. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pp. 1758–1784. PMLR, 2020b.
40.Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A. C., and Bengio, Y. Generative adversarial nets. In Advances in Neural Information Processing Systems 2014, pp. 2672–2680, 2014.
41.Harker, P. T. and Pang, J.-S. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math. Program., 48(1–3):161–220, 1990.
42.Hart, S. and Mas-Colell, A. Uncoupled dynamics do not lead to nash equilibrium. The American Economic Review, 93(5):1830–1836, 2003.
43.Heliou, A., Cohen, J., and Mertikopoulos, P. Learning with bandit feedback in potential games. In Advances in Neural Information Processing Systems 30, 2017, pp. 6369–6378, 2017.
44.Hsieh, Y., Antonakopoulos, K., and Mertikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 2388–2422. PMLR, 2021.
45.Kalogiannis, F., Panageas, I., and Vlatakis-Gkaragkounis, E. Teamwork makes von neumann work: Min-max optimization in two-team zero-sum games. CoRR, abs/2111.04178, 2021.
46.Kearns, M. J., Littman, M. L., and Singh, S. P. Graphical models for game theory. In UAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, 2001, pp. 253–260. Morgan Kaufmann, 2001.
47.Koller, D., Megiddo, N., and von Stengel, B. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2), 1996.
48.Kuhn, H. W. A simplified two-person poker. In Kuhn, H. W. and Tucker, A. W. (eds.), Contributions to the Theory of Games, volume 1 of Annals of Mathematics Studies, 24, pp. 97–103. Princeton University Press, Princeton, New Jersey, 1950.
49.Lee, C.-W., Kroer, C., and Luo, H. Last-iterate convergence in extensive-form games. In NeurIPS, 2021.
50.Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. Global convergence of multi-agent policy gradient in markov potential games. ICLR, 2022.
51.Liang, T. and Stokes, J. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, volume 89 of Proceedings of Machine Learning Research, pp. 907–915. PMLR, 2019.
52.Lin, T., Zhou, Z., Mertikopoulos, P., and Jordan, M. I. Finite-time last-iterate convergence for multi-agent learning in games. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6161–6171. PMLR, 2020.
53.McMahan, H. B. Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, volume 15 of JMLR Proceedings, pp. 525–533. JMLR.org, 2011.
54.Mertikopoulos, P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff functions. Math. Program., 173(1-2):465–507, 2019.
55.Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 2703–2717. SIAM, 2018.
56.Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net, 2019.
57.Milgrom, P. and Roberts, J. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255–1277, 1990.
58.Mokhtari, A., Ozdaglar, A., and Pattathil, S. Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30:3230–3251, 2020a.
59.Mokhtari, A., Ozdaglar, A. E., and Pattathil, S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, volume 108 of Proceedings of Machine Learning Research, pp. 1497–1507. PMLR, 2020b.
60.Monderer, D. and Shapley, L. S. Potential games. Games and Economic Behavior, 14(1):124–143, 1996.
61.Moulin, H. and Vial, J. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 1978.
62.Palaiopanos, G., Panageas, I., and Piliouras, G. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp. 5872–5882, 2017.
63.Panageas, I., Trobst, T., and Vazirani, V. V. Combinatorial algorithms for matching markets via nash bargaining: One-sided, two-sided and non-bipartite. CoRR, abs/2106.02024, 2021.
64.Popov, L. D. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845–848, 1980.
65.Rakhlin, A. and Sridharan, K. Online learning with predictable sequences. In COLT 2013 - The 26th Annual Conference on Learning Theory, volume 30 of JMLR Workshop and Conference Proceedings, pp. 993–1019. JMLR.org, 2013.
66.Rockafellar, R. T. Convex analysis. Princeton University Press, Princeton, N. J., 1970.
67.Romanovskii, I. Reduction of a game with complete memory to a matrix game. Soviet Mathematics, 3, 1962.
68.Rosenthal, R. W. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65–67, 1973.
69.Roughgarden, T. Intrinsic robustness of the price of anarchy. J. ACM, 62(5):32:1–32:42, 2015.
70.Rubinstein, A. Settling the complexity of computing approximate two-player nash equilibria. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp. 258–265. IEEE Computer Society, 2016.
71.Sandholm, W. H. Population Games and Evolutionary Dynamics. MIT Press, 2010.
72.Sato, Y., Akiyama, E., and Farmer, J. D. Chaos in learning a simple two-person game. Proceedings of the National Academy of Sciences, 99(7):4748–4751, 2002.
73.Shalev-Shwartz, S. Online learning and online convex optimization. Found. Trends Mach. Learn., 4(2):107–194, 2012.
74.Shapley, L. S. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953.
75.Shmyrev, V. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3:505–518, 10 2009. doi: 10.1134/S1990478909040097.
76.Sion, M. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171 – 176, 1958.
77.Southey, F., Bowling, M. H., Larson, B., Piccione, C., Burch, N., Billings, D., and Rayner, D. C. Bayes? bluff: Opponent modelling in poker. In UAI ’05, Proceedings of the 21st Conference in Uncertainty in Artificial Intelligence, pp. 550–558. AUAI Press, 2005.
78.Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pp. 2989–2997, 2015.
79.Vetta, A. Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), pp. 416. IEEE Computer Society, 2002.
80.Vlatakis-Gkaragkounis, E., Flokas, L., Lianeas, T., Mertikopoulos, P., and Piliouras, G. No-regret learning and mixed nash equilibria: They do not mix. In Advances in Neural Information Processing Systems 33 2020l, 2020.
81.von Stengel, B. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220–246, 1996.
82.Wei, C., Lee, C., Zhang, M., and Luo, H. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pp. 4259–4299. PMLR, 2021a.
83.Wei, C., Lee, C., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-point optimization. In 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net, 2021b.
84.Wu, F. and Zhang, L. Proportional response dynamics leads to market equilibrium. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 354–363. ACM, 2007.
85.Zhang, G. and Yu, Y. Convergence of gradient methods on bilinear zero-sum games. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
86.Zhang, L. Proportional response dynamics in the fisher market. Theor. Comput. Sci., 412(24):2691–2698, 2011.
87.Zhou, Z., Mertikopoulos, P., Moustakas, A. L., Bambos, N., and Glynn, P. W. Mirror descent learning in continuous games. In 56th IEEE Annual Conference on Decision and Control, CDC 2017, Melbourne, Australia, December 12-15, 2017, pp. 5776–5783. IEEE, 2017.
88.Zhou, Z., Mertikopoulos, P., Athey, S., Bambos, N., Glynn, P. W., and Ye, Y. Learning in games with lossy feedback. In Advances in Neural Information Processing Systems 2018, pp. 5140–5150, 2018.

Citation

MLA

Anagnostides, I., et al. “On Last-Iterate Convergence Beyond Zero-Sum Games”. International Conference on Machine Learning, vol. 162, 2022, pp. 536–81, https://proceedings.mlr.press/v162/anagnostides22a.html.

APA

Anagnostides, I., Panageas, I., Farina, G., & Sandholm, T. (2022). On Last-Iterate Convergence Beyond Zero-Sum Games. International Conference on Machine Learning, 162, 536–581. https://proceedings.mlr.press/v162/anagnostides22a.html

Chicago

Anagnostides, I., I. Panageas, G. Farina, and T. Sandholm. 2022. “On Last-Iterate Convergence Beyond Zero-Sum Games”. International Conference on Machine Learning 162: 536–81. https://proceedings.mlr.press/v162/anagnostides22a.html.

Harvard

Anagnostides, I. et al. (2022) “On Last-Iterate Convergence Beyond Zero-Sum Games”, International Conference on Machine Learning. PMLR, pp. 536–581. Available at: https://proceedings.mlr.press/v162/anagnostides22a.html.

Vancouver

1. Anagnostides I, Panageas I, Farina G, Sandholm T (2022) On Last-Iterate Convergence Beyond Zero-Sum Games. In: International Conference on Machine Learning. PMLR, pp 536–581

BibTeX

@InProceedings{pmlr-v162-anagnostides22a,
  title = 	 {On Last-Iterate Convergence Beyond Zero-Sum Games},
  author =       {Anagnostides, Ioannis and Panageas, Ioannis and Farina, Gabriele and Sandholm, Tuomas},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {536--581},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/anagnostides22a/anagnostides22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/anagnostides22a.html},
  abstract = 	 {Most existing results about last-iterate convergence of learning dynamics are limited to two-player zero-sum games, and only apply under rigid assumptions about what dynamics the players follow. In this paper we provide new results and techniques that apply to broader families of games and learning dynamics. First, we show that in a class of games that includes constant-sum polymatrix and strategically zero-sum games, the trajectories of dynamics such as optimistic mirror descent (OMD) exhibit a boundedness property, which holds even when players employ different algorithms and prediction mechanisms. This property enables us to obtain $O(1/\sqrt{T})$ rates and optimal $O(1)$ regret bounds. Our analysis also reveals a surprising property: OMD either reaches arbitrarily close to a Nash equilibrium or it outperforms the robust price of anarchy in efficiency. Moreover, for potential games we establish convergence to an $\epsilon$-equilibrium after $O(1/\epsilon^2)$ iterations for mirror descent under a broad class of regularizers, as well as optimal $O(1)$ regret bounds for OMD variants. Our framework also extends to near-potential games, and unifies known analyses for distributed learning in Fisher’s market model. Finally, we analyze the convergence, efficiency, and robustness of optimistic gradient descent (OGD) in general-sum continuous games.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

On Last-Iterate Convergence Beyond Zero-Sum Games

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — RVU bounds imply bounded cumulative movement

Knowl 2 — Game classes with nonnegative total regret

Knowl 3 — OMD reaches an approximate Nash equilibrium in finite time

Knowl 4 — Optimal constant individual regret from bounded movement

Knowl 5 — Heterogeneous mirror descent ascends potential games

Knowl 6 — Optimistic multiplicative weights has optimal regret in potential games

Knowl 7 — Near-potential games retain approximate potential ascent

Knowl 8 — Smooth games yield an equilibrium-or-welfare dichotomy

Knowl 9 — A spectral condition guarantees linear OGD convergence in two-player games

Knowl 10 — OGD converges in a multiplayer star polymatrix game under a spectral condition

Knowl 11 — Convergent OGD can select an arbitrarily inefficient equilibrium

Knowl 12 — Arbitrarily small departures from zero-sum can destabilize OGD

Knowl 13 — Linear Fisher-market dynamics are proportional response

Knowl 14 — Experiments show last-iterate convergence in poker extensive-form games

Knowl 15 — No regular historical-gradient method is stable on every general-sum game

References

Citation

BibTeX

Access the Paper