Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games
Authors: Ioannis Anagnostides
Gabriele Farina
Ioannis Panageas
Tuomas Sandholm
Venue: NeurIPS 2022 Accept (2022)
Keywords: Uncoupled learning dynamics
optimistic mirror descent
correlated equilibrium
Nash equilibrium

Abstract: We show that, for any sufficiently small fixed $\epsilon > 0$, when both players in a general-sum two-player (bimatrix) game employ optimistic mirror descent (OMD) with smooth regularization, learning rate $\eta = O(\epsilon^2)$ and $T = \Omega(poly(1/\epsilon))$ repetitions, either the dynamics reach an $\epsilon$-approximate Nash equilibrium (NE), or the average correlated distribution of play is an $\Omega(poly(\epsilon))$-strong coarse correlated equilibrium (CCE): any possible unilateral deviation does not only leave the player worse, but will decrease its utility by $\Omega(poly(\epsilon))$. As an immediate consequence, when the iterates of OMD are bounded away from being Nash equilibria in a bimatrix game, we guarantee convergence to an \emph{exact} CCE after only $O(1)$ iterations. Our results reveal that uncoupled no-regret learning algorithms can converge to CCE in general-sum games remarkably faster than to NE in, for example, zero-sum games. To establish this, we show that when OMD does not reach arbitrarily close to a NE, the (cumulative) regret of both players is not only negative, but decays linearly with time. Given that regret is the canonical measure of performance in online learning, our results suggest that cycling behavior of no-regret learning algorithms in games can be justified in terms of efficiency.

Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games
Ioannis Anagnostides Carnegie Mellon University
Gabriele Farina Carnegie Mellon University Pittsburgh, PA 15213 gfarina@cs. cmu. edu
loannis Panageas University of California Irvine
Pittsburgh, PA 15213
Irvine, CA 92697
ianagnosecs cmu edu
ipanagea@ics.uci.com edu
Tuomas Sandholm Carnegie Mellon University Strategy Robot, Inc. Optimized Markets, Inc. Strategic Machine, Inc. Pittsburgh, PA 15213 sandholn@cs. cmu. edu
Abstract
We show that, for any sufficiently small fixed e >> O, when both players in general- sum two-player (bimatrix) game employ optimistic mirror descent (OMD) with smooth regularization, learning rate = = and T ((lpoly(1/c) repetitions, either the dynamies reach an c-approximate Nash equilibrium (NE), or the average correlated distribution of play is an (ppoy(()))
coarse correlated equilib- rium (CCE): any possible unilateral deviation does not only leave the player worse, but will decrease its utility by (epoy(e)). As an immediate consequence, when the iterates OMD are bounded away from being Nash equilibria in a bimatrix game, guarantee convergence to exact CCE after only (1) iterations. Our results reveal that uncoupled no-regret learning algorithms can converge to CCE general-sum games remarkably faster than to NE in, for example, zero-sum games. To establish this, we show that when OMD does not reach arbitrarily close to a NE, the (cumulative) regret of both players is not only negative, but decays linearly with time. Given that regret is the canonical measure of performance in online learning, our results suggest that cycling behavior of no-regret learning algorithms in games can be justified in terms of efficiency.
Introduction
The last few years have seen a tremendous amount of progress in computational game solving, witnessed over series of breakthrough results on benchmark applications in AI (Bowling al.
2015 Brown and Sandholm 2017 Moravčík et al. 2017 Silver et al. 2016 Vinyals et al. 2019] Most of these advances rely on algorithms for approximating a Nash equilibrium (NE) Nash 1950 in two-player zero-sum games. Indeed, in that regime it is by now well- underssosd how to compute NE scale. However, many real-worid interactions are zero-sum, but instead have general- sum utilities, and often more than two players. In such settings, Nash equilibria suffer from several drawbacks. First, finding even an approximate NE is computationally intractable (Daskalakis et 2008 Etessami and Yannakakis] 2007 [Cen et 2009 Rubinstein 2016]- subject to well-believed complexity-therrete assumptions. Furthermore, even if we were to reach one, NE outcomes can be dramatically more inefficient in terms of the social welfare compared to other more permissive equilibrium concepts [Moulin and Vial 1978 Finally, NE suffer from equilibrium selection issues:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

there can be multitude of equilibria, and an equilibrium strategy may perform poorly against the "wrong" equilibrium strategies (Harsanyi et al. 1988 Harsanyi 1995 Matsui and Matsuyama [995].
thereby necessitating some form of communication between the players.
A competing notion of rationality is Aumann's concept of correlated equilibrium (CE) [Aumann 1974]. generalizing Nash's original concept. Unlike NE, a correlated equilibrium can be computed exactly polynomial time [Papadimitriou and Roughgarden 2008 Jiang and Seyyton-Browy 2015).
Further, CE can arise from simple uncoupled learning dynamics, overcoming the often unreason- able assumption that players have perfect knowledge over the game's 's utilities. As such, correlated equilibria constitute a much more plausible outcome under independent agents with bounded ratio- nality. Indeed, it is folklore that when all players in a general game employ a no-regret learning algorithm (Hart and Mas- Colesl 2000], the average correlated distribution of play converges to coarse correlated equilibrium (CCE) a further relaxation of CE [Moulin and Vial 1978.
Now as it happens, there are specific classes of games, such as strictly competitive games Adler et al. 2009 or constant-sum polymatrix games (Daskalakis and Papadimitriou [009a] Cai and Daskalakis 2011 Cai et al. 20166) for which CCE "collapse" to NE. In fact, although computing Nash equilirria in such games is amenable to linear programming [Adler 2013). the state of the art algorithms are based on uncoupled learning procedures, for reasons mostly relating to scalability. Nevertheless, such algorithms require ((poly(1/e)) iterations reach an e-approximate Nash equilibrium [Daskalakis] et al. 2011]. meaning that the convergence is slow. particularly in the high precision regime- both in theory and in practice. Furthermore, prior literature treats convergence to NE in, for example, zero-sum games analogously to convergence to CCE in general-sum games. While this unifying an artifact of the no-regret framework may seem compelling at first glance, is unclear whether CCE share similar convergence properties to NE. Indeed, as we have alluded to, those equilibrium concepts are fundamentally different (in general games).
tratment-wwhih.
Our primary contribution is to challenge this traditional framework, establishing that convergence to CCE can be remarkably faster than the convergence NE; this fundamental difference is showcased in Figure I In fact, we show that the only obstacle for converging exactly after only O(1) iterations to CCE in general-sum two-player games reaching arbitrarily close to a NE. Our results also
reveal an intriguing complementarity: the farther the dynamics are from NE, the faster the guarantee of convergence to CCE.
Zero-Sum Game
General- Summ Game
100
Couzsit currelated eqg gap
Nash equilitrian goa
10
10-1
10
10-2
10
10-3
20
60
100
Iteration
Iteration
Figure 1: Convergence of uncoupled no-regret dynamics to NE in a zero-sum game (left image) versus convergenee to CCE in general-sum game (right image); further details are provided in Section 4.1
1.1 Our Contributions
We study uncoupled no-regret learning dynamics the fundamental class of two-player general-sum games (a. bimutrix gumes). Specifically, we focus on optimistic mirror descent (OMD) (Chiang al. 2012 |akhlin and Sridharan] 2013a], a variant of the standard miror descent method which incorporates a prediction into the optimization step. Before we state our main result, let us introduce strong CCE, a refinement of CCE for which any unilateral deviation from a player is not only worse, but decreases its utility by additive 2 0 (see Definition 2.4 for formal description). In particular, we clarify that any strong CCE is (trivially) an exact CCE. We are now ready to state our main theorem!
For simplicity in the exposition of our results, we use the 0(-) and 22()) notation in the main body to suppress parameters that depend on the underlying game; precise statements given in Appendix[A]

---

Theorem 1.1 (Abridged; Full Version in Corollary A.2 Fix any sufficiently small e > 0. and suppose that both players in bimatrix game employ OMD with learning rate 1 = O(e²) and smooth regularizer for T = (pplly (1/c)) repetitions. Then,
Either the dynamics reach an E-approximate Nash equilibrium;
* Or, otherwise, the average correlated distribution of play is an ((poly(c))-stron) CCE.
Here, the convergence to Nash equilibrium is implied in a last-iterate sense (and not typical time-average): i.e., there exists time t E [T] for which the dynamics reach an e-approximate Nash equilibrium. Of course, in light of well-established impossibility results, OMD certainly not going to reach an e-approximate NE for a sufficiently small constant e >> O [Rubinstein [016] 20 every bimatrix game. As a result, an immediate interesting implication of Theorem 1.1 is that, by setting to be sufficiently small, OMI) either yields the best known polynomial-time approximation for Nash equilibria in bimatrix games, or, otherwise, O(1) iterations suffice to obtain strong CCE. is intriguing that the farther the dynamics are from yielding Nash equilibrium, the stronger the CCE predicted by Theorem 1.1 Indeed, the only impediment for reaching a strong CCE after only O())
iterations lies in reaching very close to Nash equilibrium? P
To establish Theorem 1.1 we prove that when the iterates of OMD are bounded away from being Nash equilibria, the regret of both players is not only negative, but decreases linearty over time (Theorem 3.4): see Figure 3 for an illustration. In this way, our approach represents a substantial departure from prior work which endeavored to characterize no-regret learning dynamics from unifying standpoint for all possible games. Furthermore, besides the folklore connection of regret with CCE (which allows us to establish Theorem[[.]] regret is the canonical measure of performance in online learning. Hence, our results can be construed as follows: when the dynamics do not reach a Nash equilibrium, we obtain remarkably stronger performance guarantees. This seems to suggest that cycling behavior in games may not be a bug, but a feature 3
From a technical standpoint, a central ingredient in our proof is remarkable property discovered in prior works--coine as the RVU bound (Syrgkanis et al., 2015 Rakhlin and Sridharan 2013a] Specifically, our argument crucially leverages the rather enigmatic negative term in the RVU bound (Proposition 2. which was treated as a "cancellation factor" in prior works. This allows us to establish (conditionally) linear decay for the regrets in Theorem 3.4 To this end, an important component of our proof is to connect the path lengths of the two players in Lemma (33 through a potential-type argument; notably, such properties break in arbitrary games with more than two players (see Remark 3.7.. (We give a detailed sketch of our proof of Theorem I.I in Section 3)
Importantly, our techniques apply under arbitrary convex and compact strategy spaces, thereby allowing for direct extension to, for example, normal-form coarse correlated equilibria in extensive- form games (EFGs) [Moulin and Vial 1978). Another compelling aspect of our result is that both players employ constant learning rate. feature which has been extensively motivated in prior works (e.g., see [Bailey and Piliouras| 2019 Piliouras et al.) 2021 Golowich et al. (200aa). )) Besides the improved performance guarantees observed in practice under time-invarian learning rate, arguably induces a more natural behavior from an economic standpoint. Finally, we corroborate our theoretical findings through experiments on standard benchmark extensive-fore games in Section 4.2
1.2
Related Work
Nash Equilibria in Bimatrix Games Bimatrix games is one of the most fundamental and well- studied classes of games. In a celebrated series of works, it was shown that computing a NE in bimatrix games does not admit fully polynomial-time approximation scheme (FPTAS), unless every problem in PPAD [Papadimitriou 1994] can be solved in polynomial time CCen et al. 2009 Daskalakis et al.
2 Closeness to NE is always implied in terms of the best response gap, not the distance to the set of NE. "To explain this point further, it is important to connect last-iterate convergence with NE. Namely, if all players employ no-regret learning algorithms and the dynamics converge pointwise, then it is easy to see that the limit point has to be NE. On the other hand, correlated equilibrium concepts are, by definition, incompatible with last-iterate convergence behavior. In light of this, there are games for which stability can be at odds with efficiency since NE can be dramatically more inefficient that correlation schemes [Moulin and Vial 1978). We also refer to our example in Section 4 where this phenomenon becomes clear; cff., see Kleinberg et al. 2011
least under uncoupled dynamics. Indeed, correlation inherently requires cycling
3

---

2009]. In light of this intractability result, there has been substantial amount of attention in deriving polynomial-time approximation algorithms for NE in bimatrix games [Daskalakis et al. 2006a] 2007
Bosse et al., 2010, Tsaknakis and Spirakis, 2008 Kontogiannis and Spirakis 20 Daskalakis and Papadimitriou 2009b] Deligkas et al. [022a bj. fact, even computing suffciently small constant
approximation essentially requires quasi- quasi-polynomial time [ubinstein 2016 Kothari and Mehta 2018], subject to the exponential-be
hypothesis for PPAD Babichenko et al. 2016]. matching the [0003] It is also worth stressing that, in terms of computing Nash
seminal QPTAS of Lipton et al.
equilibria, there is a polynomial lime reduction from any game with a succinct representation to a bimatrix game [Daskalakis et al.
2006b]; this illustrates the generality of bimatrix games.
Near-Optimal Regret in Games In a pioneering work by Daskalakis et al. [2011 was shown that there exist uncoupled no-regret learning dynamics such that when employed by both players in a zero-sum game, the cumulative regret incurred by each player is bounded by (log T), substantially improving over the (!(TT) lower bound under adversarial utilities. Thereafter, there has been considerable amount of effort in simplifying and extending the previous results along several
lines [Rakhlin and Sridharan 2013a| (Syrkkanis et al. 2015 Chen and Peng 2020 Foster et al. 2016
Wei and Luo 2018 Farina et al. [2199|] Daskalakis and Golowich 2022 Daskalakis al. 102
Piliouras et al. 2021]. This line of work was culminated in a recent result due to Daskalakis et al.
[202]], establishing ((polylog(T)) individual regret when all players employ an optimistic variant of multiplicative weights update in general games, nearly-matching the lower bound in [Daskalakis et al., 2011]. Nevertheless, the optimality here is only existential: there exist games- in fact, zero-sum- for which the guarantee in DDaskalakis et al. [022]] is essentially unimprovable. But we argue that this is not a good enough justification for considering the problem of no-regret learning in games settled. As we show in this paper, substantially more refined guarantees are possible beyond zero-sum games.
Last-Iterate Convergence A folklore phenomenon in the theory of learning in games is that broad familics of no-regret algorithms exhibit cyclic or even chaotic behavior [Sato et al. [200 Sandholm
2010, Mertikoooulos et al. 2018 Andrade et al., |021 Cheung and Piliouras] 20200] Cheung and
Tao 2021]. even in oiwdiimnniional zero-sum games. A compelling approach to ameliorate this problem was proposed by Daskalakis et al. 2018). , showing that an optimistic variant of gradient
descent guarantees last-iterate convergence in unconstrained bilinear (zero-sum) games. Thereafter, there has been a tremendous amount of interest in strengthening and extending their result in different regimes; for a highly incomplete list, we refer to [Daskalakis and Panageas, 2019 2018,) Wei et al.
2021a Golowich et al. 2020a b Hsiih al., 2021 Zhou al. [2077] Lin al. 2020 Mertikopoulos et al.
2019 Liang and Stokes 2019 Zhang and Yu 2020 Mokhtari et al.] 2020, Daskalakis et al.
2020 Wei al. [202 Anagnostides and Panageas [022]] and references therein. The precursor of
our main result is the recent paper of
Anagnostides et al. [2022a] that obtained similar results but for the sum of the players' regrets, which does not have implications in terms of convergence CCE.
2 Preliminaries
Notation and Conventions We lct = (1,2....} be the set of natural numbers. The (discrete) time index is represented exclusively via the variable t. We also use the shorthand notation [p] == (1,2....,P)) We let ||-|| || be a norm on Rd, for some d E N. and I|-II= be the dual norm of ||-||: namely, || = [ 1 (t4, v). For a (nonempty) convex and compact set X' C IRd, we denote by 2xx == max ||= - T the diameter of X' with respect to | to lighten the notation, the underlying norm will be implicit in our notation. Moreover, we let ||-X|| == maxxex ||az|| For a matrix A we let ||A|] llop be its operator norm: ||lp == sup [u||s] |Aul... We point out that || * 0 when
A f O. Finally, for a finite nonempty set A, we let (A4) {= RR/ ECEA æ(a)= = } be the probability simplex over A, where æ(aa) is the coordinate of æ corresponding to E A.
2.1 Online Learning and Regret
Let X be a nonempty, convex and compact subset of IRd, for some d E N. In the online learning framework the learner commits strategy (+)) X' every iteration t N. Then, the learner receives as feedback from the environment a (linear) utility function u(t) X' 3 + (æ,, u (0). with r (t) E Rdd that the utility received at time t is given by (x((), u ())). Based on that feedback, the

---

learer may adapt its next strategy. The framework is online in the sense that no information about minimize the cumulative
future utilities available. The canonical objective in this framework external regret (or simply regre(), defined for a time horizon T E N as follows.
}
Reg"
max ar EX
Σ (o u u
E(x0)) (t u )
That is, the performance is measured in terms of the optimal fixed strategy in hindsight.
2.2
Optimistic Regret Minimization
To leverage the additional structure in more benign environments, several predictive algorithms have been recently introduced (Hazan and Kale 2011 Chiang et al. 2012 2013 Rakhlin and Sridharan
2013b|a Syrgkanis et al., 2013] Farina et al. [002]] this paper we employ a predictive variant of
MD, known as optimistic mirror descent [Chiang et al. 2012 Rakhlin and Sridharan 2013a].
Optimistic Mirror Descent Let R be 1-strongly convex continuously differentiable regularizer (or distance generating function (DGF)) with respect to norm on H. We say that R. is G-smooth, with G > 0, if for any x, 3 E X,
VR(x)) - VR(T)]l S
(2)
For example, the Euclidean regularizer R(x) == 1/2 || [2. which is 1-strongly convex with respect
to the Euclidean norm || |12. trivially satisfies the smoothness condition of 2 with G 1; we recall that || ||| is self-dual. Moreover, we let (x (z: the Bregman divergence induced by R [Rockafellar parameterized by (dynamic) prediction vector m
3 = R(x) R(ã) (VR()). x I be
1970 Optimistic mirror descent (OMD is
E Rd for every time E N, and learning
rate 1j > 0, so that its update rule takes the following form for E N:
(1) == arg max EE
(z,, m0)
1 Dx || (11-1))
1)
(OMD)
2(0) arg max SEX
(i, (0)) - - Dx [e (((-1)) 17
Further, (0)) = arg mingex R for convenience, we also let x (()) = (0), We will refer to ax(") _,1) .... as the secondary sequence of OMD, while (0) (1) .... is the primary sequence. We also let Q2= == max Dx (x (0)) denote the R-diameter of X. As usual, we consider the "one-recency bias" prediction mechanism SSrgkanii et al. 2015), wherein (! = (t-1) for t E N. (To make ()) well-defined in games, each player initially receives the utility corresponding to the players' strategies at t = 0; this is only made for convenience in the analysis.)
An important special case of (OMD) arises under the Euclidean regularizer R(x) = = in which case we refer to the dynamics as optimistic gradient descent (OGD):
a:
IIx (z](t-1) + 11mm
(OGD)
a 11x
(t-1-) + +ru m
Here, (xx(-) stands for the Euclidean projection to the set X.
A fundamental property crystallized in [Syrgkanis et al.) 2015). building on (Rakhlin and Sridharan 2013a], the regret bounded by variation utilities (RVU). For our purposes, we will employ
refinement of the RVU bound for OMD, which follows from (Rakhlin and Sridharan 2013a Lemma I
the Full Version]-thi can be extracted en route to the proof of (Syrgkanis et al. 2015 18).
Theorem
Proposition 2.1 (Rakhlin and Sridharan 2013a Syrgkanis et al. learning rate 1) > 0 can be bounded as
2015 The regret of (MD with
Reg T <
aR El u 7
-1
-1a(0)))0))
20) ||x(()
( 1112)11(2)
4n
'To avoid any confusion, point out that OMD sometimes stands for online mirror descent in the literature.
5

---

For convenience, we will use shorthand notation for the second-order path length:
Dx
[|x(t)) 1011 [|x(()) - - -0(-11113)
(3)
2.3 No-Regret Learning and Coarse Correlated Equilibria
folklore connection ensures that when all players in a general game employ no-regret learning algorithm, the average correlated distribution play converges to a coarse correlated equilibrium (CCE) [Aumann 1974 Moulin and Vial 1978). Formally, let us first introduce the notion of a CCE in general normal-form games (NFGs). To this end, we consider set of p players [p]. with each player
having of available actions A,, The utility of player E [p] is function u; X :=1 A indicating the utility received by player under the action profile
B a aaaa R
Definition 2.2 (Approximate Coarse Correlated Equilibrium). A distribution over the set X [= A, is an e-approximate coarse correlated equilibrium, with 2 0, if for any player i E [p] and any unilateral deviation of E A.,, E Eary [u:[o', a-;)l S Bar [a,(a)] +
We now ready state the fundamental theorem connecting no-regret learning with CCE; for completeness, we include the short proof in Appendix [A]
Theorem 2.3 (Folklore). Suppose that every player E [p] employs a no-regret learning algorithm with regret Reg. up to time T E N. Moreover, let y1()) a/ @ ... & xt be the correlated distribution of play at time E [T]. and j == Ei= (1))) be the average correlated distribution of play up to time T. Then,
1 max Reg. :E[p]
Earp (us a-:) Ba-a [u:(a))
T
We also introduce a refinement CCE which we refer to as strong CCE:
Definition 2.4 (Strong Coarse Correlated Equilibrium). probability distribution μ over the set X-= A is an e-strong course correlated equilibrium, with 2 O, if for any player i [y] and any unilateral deviation af E Ai,,
Earp [u:[a', a-;)l S Ban [u,(a)] c. -c
In a strong CCE any deviation from the mediator's recommendation is not only worse, but can decrease the player's utility by a significant amount. In that sense, a strong CCE can be a much more self-enforcing equilibrium outcome, and, as such, arguably more likely to occur. A strong CCE (Definition 2.4 can be thought of as standard CCE (Definition 2.2) but with a "negative approximation". We include discussion and an illustration of strong CCE in Section 4.1
2.4 Bimatrix Games
bimatrix game involves two players. Each player has set of strategies X' C R and C Rm respectively. The (expected) payoffs of each player under strategies (x. y) E X' x y is given by the bilinear forms x Ay and x: By, respectively. Here, A, Raxm are the payoff matrices of the game As example, the special case where X' A(Ax) and y A(Ay) corresponds to normal-fone games, but our current formulation captures extensive-form games as well. By convention, will refer to the two players as player X and player y respectively. Furthermore, the underlying bimatrix game will be referred to as (A,B) without specifying the strategy sets.
Definition 2.5 (Approximate Nash Equilibrium). A pair of strategies (x", y²) E X' x y is an e-approximate Nash equilibrium of (A,B), B), for 0, if for any (x. y) E X y
T "Ty"" (x*) Ay" +6;
(4)
(x') T By S (x*) By" +
To make Definition 2.5 meaningful, some normalization has to be imposed on the utilities. Here, we will assume that max |Ayl|- < and max [B æl|- < 1.
We assume that A * 0 and B o 0. In the contrary Theorem 1.1 follows trivially.

---

3
Main Result
In this section we sketch the main ingredients required for the proof of Theorem 1.1
all the proofs
are deferred to Appendix AA] Moreover, a detailed version of Theorem 1.1 for normal games under Euclidean regularization is given in Corollary [A.2] In the sequel, we assume that players X and y' employ regularizers Rxx and Ry, respectively, so that the regret of each player enjoys an RVU bound with respect to the same pair of dual norms (Il ll. Il -I=). The first step cast the refined RVU bound of Proposition 2. for bimatrix games.
Corollary 3.1. Suppose that both players employ
OMD) with learning rate > 0. Then,
Regx S
ARR + 7/1 A
2 op
T
11
(t)
1/²
1
T
(Ia2.0) - 1/00 + || - 5: 10(-
1
4n
:=1
Regy= T
1
SRy + n1
B1ppp
Σ
T
(0)
111-11112
1 (I18(0) - -/100122 + (1y - g(t g((-
T
1
4m
The next critical step consists of showing that approximate fixed points of (OMD) under smooth ingularization-in the sense of (2) correspond to approximate Nash equilibria (recall Definition 2.5 of the underlying bimatrix game, as we formalize below.
Proposition 3.2 (Approximate Fixed Points of OMD). Consider a bimatrix game (), and suppose that both players employ (OMD) with learning rale 17 > O and G-smooth regularizer, Then, ||
ff(( ((-1) || [5(00 - x1 S en and ( - ( (0(()) y y(t) || S en, the pair (x:10) ())
a (2eG max fyy + apprrxxpo Nash equilibrium of (A,
Indeed, we show that when the iterates of (OMD) do not change by much (relatively to the learning rate), each player approximately best responding to the observed utility. The following ingredient is where we rely on the two-player aspect of the game. On a high level, we show that when the strategies of one of the players change fast over time, the other player ought to be "moving" rapidly as well.
Lemma 3.3. Suppose that both players in a bimatrix game (A, B) employ (MD) with learning
rate n) > 0. Then, for any T E N.
T
T
11 -y y11111
(1a250) - 111-11 1|5(0) -a----- x0011))
2
2nyl | A
| olop
op
(t) x (((1))]
(1 - -0(1-1)12 + +10000 y0)
2
2
27 B
B|Oop
olpp
The intuition is that as long as one player is "moving" substantially faster than the other player, its utility will be monotonically increasing as the (repeated) game progresses. But this cannot occur for too long-by a potential argument-since the utility of each player is bounded. We are now ready to state the main technical theorem.
Theorem 3.4 (Linear Decay of Regret; Full Version in Theorem I.I. Suppose that both players in a bimatrix game (A,B) employ (OMD) with smooth regularizer, learning rate n O(e²) and
T = =2 (ي) ). for sufficiently small fixed > 0. Then, if the dynamics do not reach an O(e)-
approximate NE, then
Reg., Regz)= < (EE)))..
By virtue of Theorem 2.3 and Proposition 3.2 Theorem 3.4 immediately implies Theorem 1.1 An
illustration of the linear decay of regret in a bimatrix game can be seen in Figure 3
Before we sketch
the proof of Theorem 3.4 let us point out the following useful lemma.
Lemma 3.5 (Stability of OMD). Suppose that both players employ (MD) with learning rate > 0.
Then, for any & N,
(t) (t-1)) || 1 31%
(t) (t) - ( || < 3TJ.
7

---

Sketch Proof of Theorem 3.4 When the iterates of (OM)) are M2()) from being a Nash equilibrium,
Proposition 3.2 implies that ΣT. y TT) where we used the notation of 3 Now suppose
DT. Then, using Corollary 3.1 we get that Regx = -)((E))) For the regret of player y that X 2 yy.
we first use Lemma
3.3 to obtain that by () Finally, using Corollary 3.1 and Lemma 3.5
we can conclude that Regy- V SRy - (((((//)))) -
While the dichotomy of Theorem 1.1 is based on whether only a single iterate is an e-approximate Nash equilibrium, our techniques also directly give analogous guarantees dependening on whether most say 99%-of of the iterates are e-approximate Nash equilibria, as we formalize in Corollary A.3
Remark 3.6 Eettensive-Fori Games). Theorem has direct implications for normal-form coarse
correlated equilibria (NFCCE) [Moulin and Vial 1978 in extensive- form games using the sequence-
form strategy representation [Romanovskii 1962 von Stengel| 1996. Koller al., [996].
Remark 3.7 (Multiplayer Games). Theorem does not extend to arbitrary games with p 2 3. To see this, consider a 3-player game for which the utility of player 3 does not depend on the strategies of the other players. Then, the regret of player will strictly positive-as long as the initialization differs from the optimal strategy. So, even if the dynamics are far from Nash equilibria, the CCE gap will always be strictly positive. At a superficial level, this issue occurs in games where the strategic interactions form, in some sense, multiple "connected components". Nevertheless, characterizing the multiplayer games for which Theorem holds an interesting question for the future.
Experiments
In this section we provide experiments supporting our theoretical findings. We start by analyzing the CCE and the behavior of (OGD) in simple bimatrix NFG in Section 4.1 while in Section 4.2 experiment with several benchmark games used in the EFG-solving literature.
4.1 An Illustrative Example
First, we study the 3 bimatrix normal-fore game (A, B), where
0
0
0
A
1
1
0
B =
0
0
(5)
0
0
1
0 0
can be shown that this bimatrix game has unique Nash equilibrium (a", yx) such that
and y" (1.244 [Avis et al. 2010). Moreover, (x", yy" secures xx (3 (3:3: 1.
social welfare SW(x", yy) other hand, it is easy to see that there exists an exact CCE μ* such that SW()") = 1. In fact, this social welfare optimal even without any incentive-coppabbilly constraints. Furthermore, using a lin- ear programming solver, we find that the strongest CCE (in the sense of Def- inition 2.4 has parameter of roughly 0.2083. The entire landscape of CCE as- sociated with the bimatrix game (5) is illustrated in Figure 2 The blue region corresponds to strong CCE, under which both players obtain a high utility. On the other hand, configurations for which one of the players receives low utility are not incentive compatible.
(x Ay + (x*) By 1/ ++ 0.5833. On the
104
63
666
60
Figure 2: The maximum incentive comppaiiic parameter of CCE which guarantees a given pair of utilitics.
Next, we focus on the behavior of the (MD)) dynamics. We let both players employ Fuclidean regularization and learning rate r) == 0.1. The convergence to CCE of the induced
(OGD) dynamics is illustrated in Figure 3 In particular, after T 1000 iterations the average
8

---

correlated distribution of play fi reads (with precision up to 4 decimal places)
1..4
0.1778
0.0048
j Rd
0.0029
0.1614
0.1607
[0.1642
0.0075
0.1613]
This correlated distribution secures a social welfare of (W) 0.4793 + 0.5027 0.9819. Thus, f is near-optimal in terms of the obtained social welfare. As such, it substantially outperforms the efficiency of the Nash equilibrium (xx,, yy". Moreover, we see that μ is (approximately) 0.1525- strong CCE. Indeed, for player X' the maximum possible utility attainable from a unilateral deviation roughly 0.32688, compared to 0.4793 obtained under fi; for player the maximum utility from unilateral deviation is roughly 0.3420, compared to 0.5027. It is worth noting that (OGD) does not converge to the strongest possible CCE of the game, even under different random initializations. The results described here are robust to different initializations alltt under the definition of (OGD) each player should start from the uniform distribution.
Finally, let us elaborate on Figure I The left image illustrates the Nash gap of the average strategies of (OGD) (with 17 0.1) in the zero-sum game (A, A),, while the right image shows the CCE gap of the average correlated distribution of play in the bimatrix game (A, B), as given in (5)
Plaer X
0.500
0.10
Playrr y
0-
0.05
Utitty of Plaper
0.450
-10
Blghht
0.425
0.00
-20
0.400
00.0
0.575
-30
0.350
00.10
-00
0.525
50
100
150
200
250
0.3
0.4
Iteration
Utility Player
Figure 3: The convergence of (OG)) dynamics to CCE in the bimatrix game (A, B) introduced in ( On the left image we plot the regret of each player under different random initializations; we recall that the maximum average regret is tantamount the CCE gap. We that after about 60 iterations both players experience negative regret-impllyng exact convergence to CCE. Furthermore, their regret decays linearly over time; this translates to convergence to strong CCE, as illustrated in the right image. More precisely, the color of each point (in the right image) corresponds to the CCE gap at the given iterate. Even when the initialization is "clase" to the Nash equilibrium (represented by "*"), the dynamics manage to avoid it in search of more efficient outcomes. In fact, the limit CCE of the dynamics yields near-optimal social welfare.
4.2 Benchmark Games
Next, illustrate the convergence of (OMD) on several benchmark bimatrix EFGs; namely: (i) Sheriff' [arina et al. 2019b): (ii) Liar's Dice [Lisý et al. 2015); (iii) Battleship [Farina et al. (019b]; ;
and (iv) Goofspiel [Ross] 1971). A detailed description of the game instances we used for our
experiments is included in Appendix B
We instantiated (OMD) with Euclidean regularization. After very mild tuning process, we chose for all games a (time- invarianti learning rate of 17 = (2 max ||2 [BIl2)) here, || 1l2 stands for the spectral norm of the corresponding matrix. For all games the initialization is chosen so that 2(0) arg minge Rx ( and g( arg mingexx (ÿ)) with the sole exception of Battleship for which that initialization is (virtually) already a Nash equilibrium. In light of this, for Battleship we initialized the dynamics in some arbitrary deterministic strategies; we stress that the conclusions derived here are robust to different initializations. Our results are summarized in Figure
From these benchmark games, only Liar's Dice is constant-sum in fact, zero-sum. Hence, as expected, the NE gap of the (OGD) dynamics essentially converges to O. Perhaps surprisingly, the same appears to hold for both Sheriff and Battleship. On the other hand, the dynamics exhibit a remarkably different behavior in Goofspiel. Indeed, although initially the dynamies appear to gradually converge to Nash equilibrium, after about 600 iterations the NE gap of the last iterate

---

Liar's Dice
Sheriff
NE Gap
10p
NE. Gap
10-3
10"2
10"1
100
200
300
400
500
500
1000 Iterationn
1500
2000
Dernaion
Battleship
Goofipiil
NE Gop
10
10--
10-1
10-1
Gap
10
OCE Gap
500
1000
1500
2000
3000
20000
3000
4000
5000
Irenation
Iterattion
Figure The NE gap of the last iterate and the CCE gap of the average correlated distribution of play under (GD) in different benchmark games.
rapidly increases. Afterwards, the CCE gap starts to decay remarkably fast, eventually leading to a strong CCE. Specifically, after = 5000 iterations the average correlated distribution of play (roughly) a 0.0637-strong CCE. These results are consistent with the predictions of Theorem I.1
5
Discussion
Our primary contribution was to establish a new characterization for the convergence properties of OMD an uncoupled no-regret learning algorithm-wlae employed by both players in general- sum game: OMD either reaches arbitrarily close to a Nash equilibrium, or, otherwise, both players experience (2(T")) regret. Our results open several interesting avenues for future research:
Can we extend Theorem from coarse correlated equilibria to correlated equilibria? At the very least, such an extension would be particularly challenging since all the known no- internal-regrer algorithms used for converging to correlated equilibria involve the stationary distribution of a Markov chain. While the recent reduction in [Anagnostides al. 2022b may seem useful, their technique only applies for (OMD) under entropic regularization. In contrast, our current argument crucially relies on the smoothness of the regularizer.
For which classes of multiplayer games would Theorem I.] hold? As we pointed out in Remark 3.7 while Theorem I.I does not extend arbitrary multiplayer games, still interesting to give sufficient conditions under which our results would carry over.
Can we characterize the bimatrix games for which (OM)) exhibits last-iterate convergence? It should be noted that recent results seem to suggest that such a characterization may be too hard to obtain in general [Andrade et al.) 2021].
Finally, can we improve Theorem 1.] terms of the dependence on and n7? For example, it would be interesting to extend Theorem [.I under learning rate that does not depend on e. Some form coupling the spirit of alternation (Tammelin et al. 2015) could useful in that direction.
Acknowledgements
We are grateful to anonymous NeurIPS reviewers for many helpful comments. Ioannis Panageas is supported by start-up grant. Part of this work was done while loannis Panageas was visiting the Simons Institute for the Theory of Computing. Tuomas Sandholm is supported by the National Science Foundation under grants 195-190 and CCF-1733556.
10

---

References
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Hcads-up limit hold em poker is solved. Science, 347(6218), January 2015.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, Dec. 2017.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, May 2017.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panneershelvam,, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-354 2019.
John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48-49, 1950.
Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing Nash equilibrium. SIAM Jourmal on Compuring. 2008
Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points (extended abstract). In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 1 113-123, 2007.
Xi Chen, Xiaotie Deng, and Shang- -hang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56:3):14:1-14:: 2009.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 258-265. IEEE Computer Society, 2016.
Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3):201-221, 1978.
John C Harsanyi, Reinhard Selten, et al. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
John C. Harsanyi. new theory of equilibrium selection for games with complete information. Games and Economic Behavior, 8(1):91-122, 1995.
Akihiko Matsui and Kiminori Matsuyama. An approach to equilibrium selection. Journal of Economic Theory, 65(2)4415-434, 1995.
Robert Aumann. Subjectivity and correlation randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.
Christos H. Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. J. ACM, 55(3):14:1 2008
Albert Xin Jiang and Kevin Leyton-Brown. Polynomial-time computation of exact correlated equilibrium in compact games. Games Econ. Behav., 91:347-359, 2015.
Sergiu Hart and Andreu MaleCll simple adaptive procedure leading to correlated equilibrium. Econometrica, 68: 1 1150- 2000.
Iln Adler, Constantinos Daskalakis, and Christos H. Papadimitriou. A note on strictly competitive games. In Internet and Network Economics, 5th International Workshop, WINE 2009, volume 5929 of Lecture Notes in Computer Science, pages 471 4714 Springer, 2009.

---

Constantinos Daskalakis and Christos H. Papadimitriou. On network generalization of the minmax theorem. In Automata, Languages and Programuning. 36th Internatilonal Colloquium, ICALP 2009, volume 5556 of Lecture Notes in Computer Science, pages 423-434. Springer, 2009a.
Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 217-234, SIAM, 2011.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum polyma- trix games: generalization of minmax. Mathematics of Operations Research, 41 41(():648-66 655, 2016.
Ilan Adler. The equivalence of linear programs and zero-sum games. Int. J. Game Theory, 42(1): 165-177, 2013.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6-1, 2012.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013a.
Robert D. Kleinberg, Katrina Ligett, Georgios Piliouras, and Éva Tardos. Beyond the nash equilibrium barrier. In Bernard Chazelle, editor, Innovations in Computer Science ICS 2011, pages 125-140. Tsinghua University Press, 2011.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 2989-2999 2015.
James P. Bailey and Georgios Piliouras. Fast and furious learning in zero-sum games: Vanishing regret with non-vanishing step sizes. Advances in Neural Information Processing Systems 32, pages 12977-12987, 2019.
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint arXiv:2111. 2021.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In Advances in Neural Information Processing Systems 2020, 2020a.
Christos Papadimitriou.. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):498-533 1994.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1), 2009.
Constantinos Daskalakis, Aranyak Mehta, and Christos H. Papadimitriou. A note on approximate nash equilibria. In Internet and Network Economics, Second International Workshop. WINE 2006, volume 4286 of Lecture Notes in Computer Science, pages 297-306. Springer, 2006a.
Constantinos Daskalakis, Aranyak Mehta, and Christos H. Papadimitriou. Progress in approximate nash equilibria. In Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), pages 355-358. ACM, 2007.
Hartwig Bosse, Jaroslaw Byrka, and Evangelos Markakis. New algorithms for approximate nash equilibria in bimatrix games. Theoretical Computer Science, 11131):164-173, 2010.
Haralampos Tsaknakis and Paul Spirakis. Optimization Approach for Approximate Nash Equilibria, Internet Mathematics, 5(4):365 382, 2008
12

---

Spyros C Kontogiannis and Paul G Spirakis. Well supported approximate equilibria in bimatrix games. Algorithmica, 57(4):653-665 2010.
Constantinos Daskalakis and Christos H. Papadimitriou. On oblivious ptas's ' for nash equilibrium. In Proceedings of the s1 Annual ACM Symposium on Theory Computing, STOC 2009, pages 75-84. ACM, 2009b.
Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A polynomial-ime algorithm for 1/3-approimmate nash equilibria in bimatrix games. In 30th Annual European Symposium Algorithms, ESA 2022, volume 244 of LIPlcs, pages 41:1-41::4 Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2022a.
Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. A polynomial-timg algorithm for 1/2-well-supported nash equilibria in bimatrix games. CoRR, 0atp22077.7007 2022b.
Pravesh Kothari and Ruta Mehta. Sum-of-squares meets nash: Optimal lower bounds for finding any equilibrium. Electron. Colloquium Comput. Complex., page 126, 2018.
Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 1-9, ACM, 2016.
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, page 36-41. Association for Computing Machinery, 2003.
Constantinos
Daskalakis, Alex Fabrikant, and Christos H. Papadimitriou. The game world is flat: The complexity of nash equilibria in succinet games. In Automata, Languages and Programming. 33rd International Colloquium, ICALP 2006, volume 4051 of Lecture Notes in Computer Science, pages 313-524. Springer, 2006b.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness of fast convergence. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 29, 2016.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1263-1291, PMLR, 2018.
Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. International Conference on Machine Learning (ICML), 2019a.
Constantinos Daskalakis and Noah Golowich. Fast rates for nonparametric online learning: from realizability to learning in games. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pages 846-859, ACM, 2022.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 77604-27616, 2021.
Yuzuru Sato, Eizo Akiyama, and J. Doyne Farmer. Chaos in learning a simple two-person game. Proceedings of the National Academy of Sciences, 99(7):4748 4751, 2002.
William H. Sandholm. Population Games and Evolutionary Dynamics. MIT Press, 2010.
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2703-2717 SIAM, 2018
13

---

Gabriel P. Andrade, Rafael M. Frongillo, and Georgios Piliouras. Learning in matrix games can be arbitrarily complex. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 159-185. PMLR, 2021.
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, 2020.
Yun Kuen Cheung and Yixin Tao. Chaos of learning beyond zero-sum and coordination via game decompositions. In 9th International Conference on Learning Representations, ICLR 2021. OpenReview.net, 2021.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with op- timism. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net, 2018.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, volume 124 of LIPlcs, pages 27:1-27:18. Schloss Dagstuhl Leibniz--Zentrum für Informatik, 2019.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In NeurlPS 20/8, pages 9256-9266 2018.
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. 2021a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman E. Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-coneawe saddle point problems. In Conference Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 1758-1784. PMLR, 2020b.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence nash equilibrium. In Conference on Leurning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2388-2422, PMLR, 2021.
Zhengyuan Zhou, Panayotis Mertikopoulos, Aris L. Moustakas, Nicholas Bambos, and Peter W. Glynn. Mirror descent learning in continuous games. 56th IEEE Anmual Conference on Decision and Control, CDC 2017, Melbourne, Australia, December 12-15, 2017, pages 5776-5783. IEEE, 2017.
Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael I. Jordan. 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, pages 6161 61711. PMLR, 2020.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR 2019. Open- Review.net, 2019.
Tengyuan Liang and James Stokes. 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, pages 907-915. PMLR, 2019.
Guojun Zhang and Yaoliang Yu. 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.
14

---

Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. A unified analysis of extra aaira-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, pages 1497-1507. PMLR, 2020.
Constantinos Daskalakis, Dylan J. Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 20201, 2020.
Chen-Y Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in unfiite-horizzn competitive markov games. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 4259-42999 PMLR, 2021b.
Ioannis Anagnostides and Ioannis Panageas. Frequency-Dowe Domaiin Representation of Wrrst-Order Methods: A Simple and Robust Frumework of Analysis, pages 131-160. 2021.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 536-581. PMLR, 2022a.
Elad Hazan and Satyen Kale. Better algorithms for benign bandits. J. Mach. Learn. Res., 12: 1287-1311, 2011.
Chao-Kai Chiang, Chia-Jung Lee, and Chi-Jen Lu. Beating bandits in gradually evolving worlds. In COLT 2013 The 26th Annual Conference on Learning Theory, volume 30 of JMLR Workshop and Conference Proceedings, pages 210-227. JMLR.org, 2013.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, 2013..
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
R. Tyrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
I. Romanovskii. Reduction of a game with complete memory to matrix game. Soviet Mathematics, 3, 1962.
Bernhard von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-246, 1996.
Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2), 1996.
David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard von Stengel. Enumeration of nash equilibria for two-player games. Economic Theory, 42(11:9 37, 2010.
Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation extensive-form games: Saddle-point formulation and benchmarks. In Conference Neural Information Process- ing Systems (NeurIPS), 2019b.
Viliam Lisý, Mare Lanctot, and Michael Bowling, Online Monte Carlo counterfactual regret min-
imization for search in imperfect information games. In Autonomous Agents and Multi-Agent Systems, pages 27-36, 2015.
Sheldon M Ross. Goofspiel-thh the game of pure strategy. Journal of Applied Probability, 8(3): 621-625, 1971.
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022, pages 736-749. ACM, 2022b.
15

---

Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit Texas hold' em. Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015.
Francisco Facchinei and Jong-Shi Pang. Finile-dimensional variational inequalities and complemen- tarity problems. Springer, 2003.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "mgyudeuJ8Tq", "reviewer": "Reviewer_6PC8", "summary": "This paper proves a new phenomenon about the Optimistic Mirror Descent (OMD) algorithm in two-player general-sum matrix games (bimatrix games): The iterates either converge to an approximate Nash Equilibrium (NE), or converge to a Strong Coarse Correlated Equilibrium (CCE). This result links and improves over two existing understandings: (1) Convergence to NE is unlikely to be generally achievable by any efficient algorithm due to its PPAD-hardness; (2) Convergence to approximate CCE is achievable by any no-regret algorithm, but it is unclear whether such CCE is a strong CCE (in the present paper’s sense).", "questions": "Please find some of my questions in the “weaknesses” part.\n\nAdditional questions:\n\nHow is Lemma 3.3 different from standard RVU bound (e.g. Proposition 2.1 & Corollary 3.1)? Skimming over the proof, it seems not a corollary of the RVU bound, but the proof steps are quite similar to that of RVU. Could the authors provide more intuition on this Lemma?\n\nLast sentence in abstract, “our results suggest that cycling behavior of no-regret learning algorithms in games can be justified in terms of efficiency”--- is a bit unclear to me what it means? Does “efficiency” mean convergence to Strong CCE? Or better social welfare? Same goes with the statement on Line 54-55. Perhaps the authors could expand or modify these statements to clarify. \n", "limitations": "/", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe main message of this paper is conceptually quite interesting and new. Most existing works consider learning NE in two-player zero-sum games and CCE in multi-player general-sum games as parallel goals, as they can both be achieved by no-regret learning. On the other hand, learning NE in general-sum games is likely computationally challenging due to its PPAD hardness, and thus very sparsely studied in the context of no-regret learning (which mostly consider computationally efficient algorithms). \n\nThis paper essentially proves that, for the OMD algorithm and *two-player* general-sum games, if NE is not achieved, then convergence to CCE is stronger than standard bounds—you actually converge to $O(-\\epsilon)$-CCE (what’s called the “strong CCE” in the paper) rather than $O(\\epsilon)$-CCE. At a high level this seems to say something about the “optimization landscape” of bimatrix games, like it is perhaps more benign than the worst-case hardness / convergence results suggests. \n\nTechnically, it appears that the result follows by playing with the fundamental RVU property (and its proof) of OMD algorithms and making several smart observations. In particular, the proof (for the Reg_X part) follows by the observation that if NE is not achieved, then OMD iterates must move substantially (Proposition 3.2), which makes the negative term in the RVU dominate the positive term if learning rate is small enough, hence a *negative* regret and convergence to strong CCE. This argument appears new and may be applied in future work. It also gives me an impression that the RVU property may have other fruitful consequences yet to be discovered, despite its already powerful consequences for large bodies of work in this area. \n\nIt is also good to see the numerical experiments, in particular the fact that convergence to both NE and strong CCE are possible in general-sum games (so that the “either-or” statement in the theorem is unlikely to be improved, at least for this algorithm).\n\n\nWeaknesses:\n\nThe result has a feeling of being slightly preliminary and not very complete. One caveat is the perhaps restrictive set of assumptions: global smoothness of regularizer, two-player games, and very small learning rate. In particular I am a bit bothered by the small learning rate, which is $O(\\epsilon^2)$ compared with the standard $\\Theta(1)$ learning rate for OMD type algorithms. This also makes convergence to NE/Strong CCE slower than standard $1/\\epsilon^2$ time. I understand it is necessary in the current proof, but I wonder have the authors thought about larger learning rates (as mentioned in Appendix B)? Or alternatively, infinitesimally small learning rate like in gradient flow?\n\nAlso, the assumption of global smoothness of the regularizer rules out the very standard example of entropic regularizer on the probability simplex (whose smoothness grows to $\\infty$ as we approach the boundary) for normal-form games, as mentioned in the open questions section in Appendix B. In numerical experiments, the authors consider L2 regularizers which are indeed globally smooth (thus satisfying the conditions of the theorem) but less standard. \n\nSection 4.1 needs a bit more polishing. Some important quantities are not well-defined (e.g. what is “incentive-compatibility parameter?) Apart from that, Figure 2 is also a bit confusing (e.g. what are the policies used to plot Figure 2? Since policies have much more degrees of freedom than 2). Some of the numerical details in the text also does not seem too important and may be moved to the Appendix. I do like Figure 3 which shows very clearly the negative regret and the improvement in social welfare. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MQNquEsr47C", "reviewer": "Reviewer_Vmdx", "summary": "Precisely as per the title, the paper shows that optimistic mirror descent (OMD) either converges to epsilon-approximate Nash equilibria, or the average emprical distribution of correlated play converges to an approximate-\"strong-coarse correlated equilibrium (eps-SCC). Here an epsilon-strong-coarse correlated equilibrium is parameterized by epsilon, which dictates the extent to which players see a decrease in utility from unilaterally deviating from the correlated distribution of play (where deviations are such that a player uses a single fixed strategy rather than following the correlated distribution's signals). An interesting consequence of the result lies in the fact that for constant epsilon, an eps-SCC is in fact an exact coarse correlated equilibrium, hence if the dynamic has not reached an eps-approximate, it must forcibly give rise to an exact coarse correlated equilibrium. Finally, the authors provide an in-depth analysis/visualization of the performance of OMW on a specific 3x3 game instance, as well as general performance on several game benchmarks", "questions": "In the experimental section you mention the possibility of different initializations for OGD. Are there games where different intializations to the same game can give rise to either of the guarantees of your result (eps-Nash or eps-strong CCE)? \n\nSupposing that players do not have access to the representation of the game and infer utilities from potentially noisy oracles, are results robust to such a setting? \n", "limitations": "The main limitation that came to mind was the applicability of methods to games with more than 2 players, but this was adequately adressed in the paper as a potential thread of future research. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n-The paper is very clear and results are well-motivated. A large part of the clarity stems from the fact that results are simple to state with interesting consequences. Furthermore, the overall intuition behind main proofs is well-explained in spite of technique details being in the appendix. Furthermore, the results will be of interest to the general community at Neurips.\n\nWeaknesses:\n-The paper could have had more exposition regarding the setting where players do not have access to the full representation of the bimatrix game but rather infer knowledge of the game through oracles.\n-A minor point really, but it would be interesting to map the trajectory of play for the game instance in Section 4, especially for different intializations as mentioned at the end of 4.1. This would be especially useful to visualize for the main Lemmas of section 3.\n\nMinor point:\nIn the appendix you mention that the state of the art for approximate eps-Nash being the Tsaknakis and Spirakis 0.3393 + delta result. Recently there has been a paper Deligkas et al. (https://arxiv.org/pdf/2204.11525.pdf) which improves this to 1/3 + delta\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "55Bf-MuKmqr", "reviewer": "Reviewer_Yw3X", "summary": "This paper studied the dynamic behaviour of Optimistic Mirror Descent beyond two-player zero-sum games and consider two-player general sum games (bimatrix games). It shows that the dynamic either visits an $\\epsilon$-NE or achieve a strong coarse correlated equilibria. \nIn order to prove that, the authors observe the correlation in behaviour of two players 's strategies (Lemma 3.3 in Appendix) along with the existing regret bound of OMD (Proposition 2.1).", "questions": "I have a few questions to better understand the paper.\n\n1. I am wondering whether the existence of a strong CCE is guaranteed in every bimatrix game?\n2. In experiments, do the authors observe chaos behaviour of OMD? (e.g., the dynamic keeps approaching and moving away from a NE repeatedly)? \n\n", "limitations": "there is no negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I really like the result of strong CCE and negative regret bound for both players (theorem 3.4) as they are new and fundamentally better compared to previous results. However, the condition in which the paper needs to achieve these results is hard to interpret. That is, the dynamic needs not to visit an $\\epsilon$-Nash Equilibrium in the whole $T$ rounds. Hypothetically, OMD can have a chaotic behaviour while still visiting an $\\epsilon$-Nash Equilibrium. This type of chaotic behaviour is known for many no-regret algorithms. Thus, the result of visiting $\\epsilon$-Nash Equilibrium is less exciting and provides little information. Besides, visiting $\\epsilon$-Nash Equilibrium and last round convergence are two very different, thus Theorem 1 does not imply the existing last round convergence result of OMD in zero-sum games. \n\nThe paper will be much stronger if the results in Theorem 1 can implement last-round convergence to NE (not visiting) or strong CCE. A relevant result in zero-sum games about $\\epsilon$-NE leading to last round convergence can be found in \"Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept