Learning Nash Equilibria in Rank-1 Games
Authors: Nikolas Patris
Ioannis Panageas
Venue: ICLR 2024 poster (2024)
Keywords: learning in games
rank games
Nash equilibria
Minty
optimistic gradient
Primary area: learning theory

Abstract: Learning Nash equilibria (NE) in games has garnered significant attention, particularly in the context of training Generative Adversarial Networks (GANs) and multi-agent Reinforcement Learning. The current state-of-the-art in efficiently learning games focuses on landscapes that meet the (weak) Minty property or games characterized by a unique function, often referred to as potential games. A significant challenge in this domain is that computing Nash equilibria is a computationally intractable task [Daskalakis et al. 2009]. 

In this paper we focus on bimatrix games (A,B) called rank-1. These are games in which the sum of the payoff matrices A+B is a rank 1 matrix; note that standard zero-sum games are rank 0. We show that optimistic gradient descent/ascent converges to an \epsilon-approximate NE after 1/\epsilon^2 log(1/\epsilon) iterates in rank-1 games. We achieve this by leveraging structural results about the NE landscape of rank-1 games Adsul et al. 2021. Notably, our approach bypasses the fact that these games do not satisfy the MVI property.

Published as a conference paper at ICLR 2024
LEARNING NASH EQUILIBRIA IN RANK- GAMES
Nikolas Patris University of California, Irvine Archimedes Research Unit npatris@ue edu
Joannis Panageas University of California, Irvine ipanagea www.uii......................... edu
ABSTRACT
Learning Nash equilibria (NE) in games has garnered significant attention, particularly in the context of training Generative Adversarial Networks (GANs) and multi-agent Rein- forcement Learning. The current state-of- totte-of-thearrt in efficiently learning NE in games focuses on landscapes that meet the (weak) minty property or games characterized by a unique function, often referred to potential games. A significant challenge in this domain is that computing Nash equilibria is a computationally intractable task Daskalakis et al. (2009).
In this paper we focus on bimatrix games (A, B) called rank- 1. These are games in which the sum of the payoff matrices A + B rank matrix; note that standard zero-sum games are rank-0. We show that a modification of optimistic mirror descent converges to an e-approximate NE after O (2z log( ()) iterates in rank-1 games. We achieve this by leveraging structural results about the NE landscape of rank-1 games Adsul et al. (2021). gases/Adsul Notably, our approach bypasses the fact that these games do not satisfy the MVI property.
INTRODUCTION
Learning in games has its origins in Blackwell's influential work the approachability theorem (Blackwell 1956] Abernethy et al.] 2011). which paved the way for the development of various learning algorithms with convergence guarantees different game theoretic solution concepts, including coarse correlated equilibrium (CCE) and Nash equilibrium (NE). For instance, a well-known result in this context is that if both players in a zero-sum game employ no-regret learning algorithm, the empirical averages of their strategies will converge to a NE. However, the typical guarantees provided by online learning frameworks do not shed light on how the system stabilizes toward Nash equilibrium when the underlying two-player game is neither zero-sum nor potential game (Anagnostides et al., 20226). In such cases, one can only argue that the empirical averages converge CCE if both players employ no-regret learning algorithm. This raises the following fundamental question:
For which classes of two-player games, beyond zero-sum and potential games, can we design online learning algorithms that guarantee convergence to Nash equilibrium?
The work in Kannan & Theobald (2010) introduced hierarchy of bimatrix games denoted as (A, B), where the rank of A + B is k. These referred to as rank-k bimatrix games. Notably, this class encompasses zero-sum games when & is zero. Intriguingly, it has been demonstrated that even for the case of A = 1, the set of Nash equilibria can comprise potentially large number of disconnected components and lacks convexity. Furthermore, has been proven that for 2 3, computing an exact Nash equilibria in rank k bimatrix games is PPAD-hie problem Mehta (2018). In other words, it is highly unlikely that a polynomial-time algorithm exists for computing Nash equílibria in such games. On the contrary, rank-1 games have been shown to have polynomial-time algorithms based on linear programming formulations Adsul al. 2021 2011). while the
complexity of rank-2 games remains an open question.

---

Published as a conference paper at ICLR 2024
Our contributions and Technical Overview In this paper, we focus on rank- 1 games. First we establish that there exist rank-1 1 games that do not satisfy the so-called Minty criterion and as a result optimistic mirror descent Rakhlin & Sridharan (013) and extra gradient algorithms Korpelevich (1976) fail to converge to a Nash equilibrium.
On a positive note, we introduce a decentralized learning algorithm that converges to an e-approximate Nash equilibrium O (+z log (2) iterations, as proven Theorem 3.7 Both agents in the game utilize an optimistic mirror descent algorithm in parametrized zero-sum game that evolves over time. The key to our technical analysis lies in how we adapt the underlying parameter, ensuring that when the algorithm terminates, an approximate Nash equilibrium in the parametrized zero-sum game coincides with approximate Nash equilibrium in the rank-1 game. To provide more context, consider a rank-1 I bimatrix game represented (A, B). We can assume that B - ab for some vectors and b. It turns out that a Nash equilibrium (x, y) of the rank-l game B) is also a Nash equilibrium of the parametrized zero-sum game (A 1Ab A + 1XbT) for an appropriate choice of the parameter A, where 1 the all-ones vector. The primary technical challenge is formulating a suitable optimization problem to ensure that a Nash equilibrium the parameterized translates
Nash equilibrium the rank-1 game, as shown in Lemma 3.4
Our proposed algorithm is based on optimistic mirror descent applied to the parameterized bilinear function x: (A 1bb yy with an additional regularization term (æ: T a - 2)². Depending on the sign of the difference (x: x). À is updated appropriately. To prove our claims, we leverage the structural insights of the
Nash equilibrium landscape Adsul et al. (2021) and exploit the stationarity properties of the x-parameterized (strongly) concave-convex function fx y) x' (A-1 y -/x'' a-))². Furthermore, in Appendix C we provide experimental evaluation supporting our theoretical findings.
2 PRELIMINARIES
2.1 NOTATION AND DEFINITIONS
Notation Let R be the set of real numbers, and [n] be the set {1, n.. We define An as the probability simplex, which is the of n-dimensional probability vectors, i... A, == (x E R" x, 2 E. x; = 1}. We use e; to denote the i-th elementary vector, and to refer to the i-th coordinate of we use D;. The superscripts are used to indicate the timestep at which a vector referring to.
Normal-form Games of payoff matrices E mm and B "x where and m are the respective pure strategies (actions) of the row and the column player. After the players choose their action, we denote (e,, e,) the joint action profile for i E [m]] and j E [m]] Then, their respective payoffs are Aij e, Ae; for the row player and B, == e; Be, for the column player. Player are also allowed to randomize. A mixed strategy for the row (resp. column) player is a probability distribution æ E An (resp. y E Am) over the n rows (resp. m columns). In this case, the expected utility of the row, column player is expressed as x Ay and x By respectively, where (x, y) E An x Am denotes the joint mixed strategy profile.
We primarily focus on two-player normal-form bimatrix game. We are given pair
Definition 2.1 (e-approximate Nash Equilibrium). A strategy profile (x",y") y") E An x Am is called an e-approximate Nash equilibrium (NE) if and only if
(x') Ay
x T Ayy
Vi E An and
(xy) Vy E A..
In words, an approximate Nash equilibrium is a strategy profile in which no player can improve their payoff significantly (more than by unilaterally changing their strategy, but the strategy profile may not necessarily satisfy the definition of an exact (e = 0) Nash equilibrium.
2

---

Published as a conference paper at ICLR 2024
Remark 2.2. We highlight two special cases of an e-approximate Nash equilibrium. Firstly, when is equal to zero, is referred to as an exact Nash equilibrium. Secondly, when the support of strategies, supp ax) = {i my > 0), is of size 1, it is called pure Nash equilibrium.
2.2 RANK-1 GAMES
this work, we consider bimatrix games (A, B) of fixed rank, and particularly of rank This hicrarchy within two-player games initially introduced by Kannan & Theobald (2010) in attempt to offer more detailed characterization of games that (may) admit simple polynomial-une time algorithms based on the rank of the matrix (A B). In related model, Lipton et al. (003) investigated games where both payoff matrices are of fixed rank k, and they proposed a simple (quasi) polynomial monomil--timee algorithm for constructing e-approximate NE. This seemingly similar model, however, has a significant drawback; even zero-sum games, which have polynomial-time algorithms, entirely belong to this class. Motivated by this observation, Kannan & Theobald (2010) proposed that (A + B) should have fixed rank instead.
Definition 2.3 (Games of fixed rank). The rank of bimatrix game (A, B) is the rank of matrix A + B.
Remark 2.4. It is apparent that zero-sum games (A, -A) are rank-O games as A + (-A) = 0. Additionally, rank-1 games satisfy A + B ab
Assumption 2.5. As Nash equilibria remain invariant under the transformations of shifting and scaling of the payoff matrices, we assume that the elements of and b are confined within the interval [-1, 1]. This assumption simplifies our calculations without impacting any of our results.
The following lemma presents alternative method for describing bimatrix game of fixed rank
Lemma 2.6 (Lemma Adsul et al. 2021)). ). An (n x m) bimatrix game (A, of positive rank r can be written (A, C + ab" for suitable R" Rm, and a game (A, C) of rank
The following lemma, though simple, holds significant importance as it establishes that for bimatrix game of fixed rank r, the of its Nash equilibria equivalent the intersection of the of equilibria of parameterized game of rank
and a hyperplane.
Lemma 2.7 (Lemma 6 Adsul et al. (202)). Let A, C. RR x E An, y E Am, IR", E R. À
R. The following are equivalent:
(a) (x. y) is an equilibrium of (A, C + Cbbb)).
(b) (x. y) is an equilibrium of (A, C + 1XbT) and x a T
X
(c) (x. y) is an equilibrium of (A 1Xb C 1>bT) and x. a X.
Sketch Proof. The equivalence of (b) holds because the players get in both games the same expected payoffs for their pure strategies. The games in and [c)are are strategically equivalent.
While it may not be immediately evident how this rank reduction can practically applied, the true significance of Lemma 2.7 becomes fully apparent in the context of rank-1 games.
Corollary 2.8. Let (A be a bimatrix game of rank I, i.e. + = abT. Then, the following are equivalent.
(a) (x. y) is an equilibrium of (A, - A Aabb Tb
(b) (a. y) is an equilibrium of (A 1 - - -11 and x: Ta A.
The proof follows trivially from the equivalence of (a) and (a)and (c) in Lemma 2.7
3

---

Published as a conference paper at ICLR 2024
Parameterized zero-sum games Corollary 2.8 establishes a connection between rank-1 games and pa- rameterized zero-sum games. While this link initially appears compelling, remains uncertain whether an algorithm can compute, or more importantly learn, Nash equilibrium (æ,, y) satisfying a: a À at the same time. The primary challenge arises from the fact that optimal strategies vary as the parameter changes. It is well-known, however, that zero-sum games be efficiently solved using various methods, including LP-based techniques Adler (2013); von Stengel 2023) and no-regret algorithms Freund & Schapire (1999); ;
Daskalakis et al. (201 Syrgkanis et al. (2015): Chen & Peng (2020). Therefore, as long as there is easy way of updating X, the parameterized sero-sum game serves as an intermediary to solve the rank-1 game.
An initial attempt was made in Adsul et al. (20TT) where they demonstrated that the set of fully-labeled points, which captures all Nash equilibria of the game, of specific best-response polytopes contains only a path that exhibits monotonicity with respect X. Additionally, they introduced an algorithm that employs binary search on the parameter to compute an exact Nash equílibrium for the rank-l game. However, a limitation of this method is its inability handle non-degenerate games. In their subsequent work Adsul et al. (202T). while retaining their structural insights and building on Adler & Monteiro (1992), they refined their approach. They proposed polynomial- time algorithm, similar in spirit the one in Adsul et al. (201T). compute a Nash equilibrium for any rank-1 game.
Definition 2.9. Let / be the set of the Nash equilibria of the parameterized sum game defined as follows.
===((A, y) ERX R RM
(x,y) is NE of (A LAbT, A - -
(I)
The following key lemma, essential for the algorithm in Adsul et al. 2021). shows that the set W exhibits monotonicity with respect to X.
Lemma 2.10 (Lemma 17 Adsul et al. (2021)). Let À A L. An and y. y E Am so that for N in
(), A. 9) E,W, A AS a (Λ, EN, x2 TT
Then x X for some (Λ, v. y) E N with X E [A
This property serves as the invariant maintained by the algorithm outlined in Adsul et al. (202T). The algorithm essentially employs a binary search with respect to the parameter x. In brief, at each iteration, considers the midpoint, either return a Nash equilibrium of the zero-sum game (A 1 A + 1 for which x a \ or indicate that none of the Nash equilibrium strategies satisfy this equation. Importantly, in the latter case, and due the monotonic nature with respect the parameter, the sign of the difference (x T a A) should be maintained. Therefore, depending on it, either or X is updated accordingly. For instance, case then À = >; otherwise, it sets À A According to Lemma 2.10 this step safe as there exists Nash equilibrium (ar, y) such that x: À and À E [A, A). In Lemma 3.5 extend this property to the case of an approximate Nash equilibrium by leveraging the convexity of Nash equilibria in zero-sum games.
(A + /2, and, based on value, it solves series of linear programs. These
æ Ta
2.3 BASIC BACKGROUND ON MIN-MAX OPTIMIZATION
After establishing the link between rank-1 games and zero-sum games, demonstrated in Corollary 2.8 this section presents a brief background on min-max optimization. A more compact and thorough presentation is deferred to Appendix B
We have intentionally omitted certain technical details of this step that do not impact the core aspects of the algorithm.
4

---

Published as a conference paper at ICLR 2024
A Nash equilibrium in zero-sum games represents solution to saddle point problem which in its general form (not only for bilinear functions) is
min max f(x,,)) TE yEY'
where X are convex and compact subsets of an Euclidean n-dimensional (m-dimensional resp.) space, and is continuously differentiable function, i.e. smooth function.
Remark 2.11. It is widely recognized that two zero-sum games constitute special case where the function f(x. 3) = x Ay is convex (linear) with respect to æ and concave (linear) with respect to y. Then, the celebrated minimax theorem v. Neumann 1928) asserts that min max (x, y) max min veV fæ, y)
#EY yEy
However, in practical scenarios, such as those in Generative Adversarial Networks (GANs) Daskalakis et al. (2017), the function f does not meet the necessary convex-concave property, and so most optimization techniques for (2) do not to apply. As a result, a significant amount of research has focused instead on different notions of local min-max solutions Daskalakis & Panageas 2018b); ; JJn et al. (2020). The result in Daskalakis et al. (202I), however, establishes that for general smooth objectives, the computation of even approximate first-order locally optimal min-max solutions is intractable. In light of this intractability result, research has shifted its focus to investigate structural properties that circumvent this barrier, enabling the efficient computation of a solution. This will usually involve imposing some (mild or not) assumptions on the objective function. An example of such assumption is the existence of solution to MVI as presented below.
Nash Gap The goal is find point (æ= y²) E X y that is close to the set of Nash equilibria. The notion of closeness is implied in terms of the best response gap, not the distance to the set NE and is defined with respect to the (Nash) gap as
Gap(æ", vy) = max f(x", .y) min f(z, y²),
(Gap)
wex
which is always non-negative and zero if and only if (x", ,y") is NE.
Variational inequalities We introduce the set Z X x y and the operator F' associated with the function
defined as F(z) F()))
V=)(z.)) It is readily verified that saddle point problem (2) can (...(
be framed as a variational inequality problem; this unifying treatment enables the application of various techniques and results drawn from the vast literature of variational inequalitiss,Faccchnee & Pang (2003).
Given the compact convex set 2 and an operator F, the Stampacchia Variational Inequality problem consists in finding z E 2 such that:
(F(z"), z²) 2 for all Z
(SVI)
In this case, x" is referred to the strong solution to variational inequality problem corresponding to F. From a game-thoee theoretic standpoint, x* corresponds to a Nash equilibrium of the underlying game. As the existence of Nash equilibrium is always guaranteed exist Nash Jr (950)), exists a solution to (VII.
safely assume that there
Most of the existing literature on variational inequality problems Facchinei & Pang (003) has focused the monotone case, i.e. I is convex concave. In this context, it is widely acknowledged that every solution to SVI) is also a solution to the Minty Variational Inequality problem (MVI.
(F(z), x x²)
for all e Z
(MVI)
TThis notion of closeness is commonly referred to in the literature as weak, while the closeness in terms of the distance to a Nash Equilibrium is known as the strong notion Etessami & Yannakakis (2010).
5

---

Published as a conference paper at ICLR 2024
In settings beyond the monotone case, all that can be said is that the set of solutions for (VI is a subset of the set of solutions for (SVI). An important (Minty) criterion that ensures tractability the existence of solution to (MVT). In Mertikopoulos et al. (2018), they introduced the concept of coherence (refer to Definition 2.1), which holds true if every saddle point of f [2). and in turn to (VVI), is a solution to (MVT) and vice versa. In Mertikopoulos et al. (2018); Song et al. (2020); Zhou al. (2020) (and references therein) it has been established that if the Minty criterion is satisfied (e.g. bilinear problems, guasi-convex-comee objectives) then extra gradient Korpelevich (1976) do converge to solution of saddle point problem. In recent works, such as Diakonikolas et al. (2021); Pethick et (2022), less stringent criterion, namely the weak Minty criterion, has been explored, and convergence solution of (2) was also ensured. Nevertheless, as we will demonstrate shortly in the Section 3.1 even relatively simple rank-1 1 games fail to satisfy the (weak) Minty criterion.
3 EFFICIENTLY LEARNING NASH EQUILIBRIA IN RANK-1 GAMES
this section, we sketch our main findings concerning the learning of Nash equilibria in rank-1 games; all the proofs are deferred to Appendix A We start by presenting two illustrative examples that highlight the inherent challenges of these games. Despite their apparent simplicity, conventional first-order methods fail to converge to a Nash equilibrium. In Section [3.2] we introduce an efficient algorithm for learning NE, that uses and extends the structural properties detailed in Section 2.2
3.1 TECHNICAL CHALLENGES
The rank-reduction method presented in Corollary 2.8 transforms a rank-1 game (A, B) into a parameterized zero-sum game (A 1 X A 1bb ). A question that arises is whether the of approximate Nash equilibria of the zero-sum game is properly included in the approximate Nash equilibria of the rank-1 game. Although in the case of an exact NE, we readily verify that it does not hold, the former remains unelear for approximate NE. In other words, can solving the zero-sum game alone provide a solution for the rank-1 1 game?
The following example provides a negative answer to this question, even when we have complete knowledge of a correct value X -ie., corresponding to a Nash equilibrium (x* 3²) of the rank- I game where (x*) a X
Example 3.1 (Full Version in Example A.I. Let A - 1λb = [1_ -. This game has an exact NE of the form (x*, y²) = ((1, 0), (R, - n)) for any E [o, 1]. Additionally, (æt 3) = (()) $), (t. f)) is an
2 Saapproximate Nash equilibrium of the zero-sum game (A 1Ab - + 1Ab
ÿ = a: T (A - 1AbT) yn and T (A 1\b
2 1 1-c 1- =1 11- 2
1
We choose a = [1 2] and b = [2 1]
and so x+ a a=
1 1
2 1
3 2 2-6
-1 -1] 1+E
A 1 - e 1 1
+
2
1
= 3-6
and B =
We confirm that (ã. 9) ((} 1) (2, b)) no longer qualifies as an 5 5aapproximate Nash Equilibrium for the original rank-1 1 game as the Nash equilibrium condition (inequality) for the column player does not hold.
As described in Section 2.3 there are additional structural properties that enables convergence to a solution even if the game is no longer monotone. As such, our next goal is investigate whether the Minty criterion MVI is satisfied rank-1 games. Unfortunately, but importantly for the scope of this work, it fails to hold.
6

---

Published as a conference paper at ICLR 2024
Algorithm 1: Rank-1 Game Solver
Algorithm 2: OMWU(2, y,
Input: æ (0) 1/n E An; (0)) 1/m E Am
Input: (x(0), ())) An Am, XE [0. 1]
Output: (a.y) y) NE of rank-1 (A,B)
Output: (æ; y) such that Gap(æ; y) S
1 for k =1,.... I..... K do
(0) =0
gx
2 (x y())==
(0) =0
OMWU(x!!-1) 2y (*-111, (((11))
gy
3 for i 1,2...., F...,,Too do
if (xx(), (h)) is NE of (A, B) then
(v=(((ar(() y)"))
L return (x((), yy(()) (k)
g (t) vzfi( (1)"))
gy
else
m: expl xx 20 (1) -x (1-1))
((+1)
((k) = (k-11) zt sgn (k) a 11)
(1) expl ax x nx 1)
/* update according to sign */
(++1)
v expl by 2gr -/ gr 17)
y)
Σ Mj
(1) exp( my 2g o..
7
return (x(T), y y(T))
Example 3.2 (Full Version in Example A.2
(x" y²) be NE of the bimatrix rank-1 game B (A, - + ab" We show that there exists a game such that the Minty variational inequality
Let z"
MVD not satisfied.
x
Ay -B
(MVI)
(F(z), - 2*) 4
where F(z)
We examine solutions 2" = ,y" that correspond to the Nash equilibrium of the selected game.
T xx" y y" -x x;, Ay) (y B xx)
(F(z), x - z²) = - B
Let A [b]] and B [11 === This game has the two pure equilibria (æ1, yn) ((1, 0), 0)) and (x2, 822 = ((0, 1). (0, 1)). and the mixed equilibrium (æz, ya) = ((), ( ))) However, none of these equilibria satisfy the Minty criterion.
3.2 MAIN RESULTS
this section, we introduce our method, and sketch the main ingredients required for the proof of Theorem 3.7 To facilitate the presentation, break it down into three main steps. The first step consists of showing that only specific approximate Nash equilibria of the parameterized zero-sum correspond to approximate Nash equilibria of the underlying rank-1 game. Then, formulate suitable min-max optimization problem whose stationary points are extendable unddr conditions- to NE. Finally, we present an efficient algorithm for solving the optimization problem.
The following lemma relies on the correspondence established in Corollary 2.8 Although this appears to be applicable solely exact Nash equilibria, demonstrate that by relaxing both conditions, it also extends approximate Nash equilibria.
Lemma 3.3. Let (xc y) be an e-approximate Nash equilibrium of the zero sum game with payoff (A 1 A and in Al Then (x. y) an (3p)-aappo Nash equilibrium of the rank-1 game (A, A LAb
7

---

Published as a conference paper at ICLR 2024
A study of Lemma] 3.3 eadd us to the following observation: to compute an approximate Nash equilibrium of the rank-1 game, we should seek NE of the parameterized zero-sum game which simultaneously minimizes the distance (æ:
X). By virtue of this observation, we formulate the following min-max optimization problem; its full proof deferred to Appendix
a 1)2. f is concave with respect to a and convex (linear) with respect to y. Moreover, assume that the corresponding zero-sum game has c-approximate Nash equilibrium (x* y²) with lx= a >l S Then, any c-approximate stationary point (ic y) of f must satisfy the following.
Lemma 3.4. Consider the function fx(2. y) TT ( 1xb y -
a
1. 2 T - V5c.
2. (a. 3) must be an (6 (C)-NE of the zero-sum game (A 1Ab - + 1AbT).
Sketch Proof. Given that (z, 3) is an e-approximate stationary point of f. it satisfies the following variational inequalities (VI).
(I (V>/a(0, D). w' x) = (AA LAbT) ÿ ύ- (===aa-- a) - ②) Seva's E An
(2) (Vy/aa, - ((A 1 i. y 0) Vy' Am
First, the fact that f(: is concave function for any y. which implies that it satisfies the inequality [x ÿ) S ( ÿ) + / ÿ), x' .). Therefore, when setting x' x and from VI (1) and the fact xx" A S we obtain the following.
x (A 1xb J (A LXb 1Xb
{ x
2) 2c
Furthermore, /2 -) is linear,for any x, which implies that it satisfies the equality (a y fā D) + VV D), 7) for any y' Am- Therefore, when setting y' y² and from VI (2) we obtain the following.
(A - (A-11 y 2 x (A 1x6 ) -
The last two inequalities follow from the approximate NE definition of (x* y²), with representing the maximizer and y representing the minimizer.
e (A 16b y 2 ē. (A 1x6 3 -
xx
A
1X6 y" < x (A 11b ÿ +
By combining the above four inequalities, we prove the first claim: | a X| S V5c. The second claim- (i. ÿ) is a Nash Equilibrium (NE) of the parameterized cero-sum-followe from the VI VI (2) alongside the inequalities
showed.
So far, we have verified that any stationary point (ā., ÿ) of fA constitutes a Nash equilibrium for the rank-1 game under the condition that NE does exists for that particular In other words, Lemma 3.4 holds true only in the case where the parameter attains the correct value X+iie., corresponding to Nash equilibrium (x*, yy) of the rank-1 game where (x*) T a = X* This raises the question how we can determine the correct value of X. Hopefully, the following simple but important lemma answers this question.
Lemma 3.5 (Approximate Nash equilibria maintain sign). Let (ă. ④) and (x* y be c-approximate Nash equilibria of the parameterized zero-sum game (A 1 - + 1Xb ), so that x a >> > and x² a < X. Then, there exists (7. y) that is e-approximate NE with कं' a = A.
8

---

Published as a conference paper at ICLR 2024
The lemma above answers our question in the following way: whenever a stationary point (z",y") of fx(:.) fails to an e-approximate Nash equilibria for the zero-sum and |a a X| be less than or equal to e, this necessarily means that there does not exist any NE that satisfies that equation for that particular X; otherwise, any stationary point of fa would suffice. More importantly, it implies that æ a - À must maintain its sign for any e-approximate Nash equilibrium in the zero-sum game for that particular A. In other words, if there were a pair of Nash equilibria where (x a X) has opposite signs, then according to Lemma 3.5 it would guarantee the existence of third solution where this difference equals zero
In similar spirit to Lemma 2.10 Lemma 3.5 serves as an invariant in our approach. Algorithm [ performs binary search to parameter A. At each iteration, it employs Algorithm 2 to obtain an e-approximate stationary point of f'x This solution either constitutes a Nash equilibrium of the rank-1 game (A, B) or indicates that no Nash equilibrium exists for that particular À and the specified precision In the latter case, the sign of the difference (æ a >) determines the next value of X. For instance, if x a - X < -e, then À is updated as A zz otherwise, if x
+e, then is set as X
In the final part, we introduce an efficient method for obtaining an e-approximate stationary point of fx for a specific A. Leveraging the structure of fx. we utilize an Optimistic Multiplicative Weights Update (OMWU), as detailed in Daskalakis & Panageas (2018)). This method offers two key advantages: it does not require a projection step, which can be computationally expensive, and achieves faster convergence rates by incorporating optimism. A more comprehensive presentation of optimistic methods is deferred to Appendix B (.6 provides us with a specific number of iterations required.
Lemma 3.6. Let (x()), y be initialized as uniform vectors (1/n, 1 1/m). Suppose that both players employ OMWU for T Ω2 (Inntham) with learning rates nyx "yy
16v2 max || and fixed x. Then,
Algorithm 2 returns a pair of strategies
(T) (TT)
that guarantees the following.
Gap ,
max fx (I. WEAn
min fa
TT( Se.
yEAm
Also, it holds that (T( ) is an E-approximate stationary point of fx-
We are now prepared to present the main technical theorem that integrates all the components established thus far into a concise statement
Theorem 3.7 (Main Result). Let (A,B) be a rank-1 1 game. Suppose that both players employ OMWU for T = Ω (log +og m)) log(t)) Then, Algorithm returns pair of strategies (x",y") that constitutes an 18e-approximate Nash equilibrium of the runk-1 game.
22
4 CONCLUSION
In this work, we examined the structural properties, as well as challenges, of rank-1 games, an important class the generalizes over the well-understood zero-sum games. We introduced a decentralized learning procedure that provable converges to a Nash equilibrium of the game. Nevertheless, number of important questions remain open. Proving a matching lower bound will certify the optimality of our solution. However, given that our approach hinges the idea of reducing a rank-1 game into zero-sum game and then optimizing carefully crafted minmax problem, we presume that, unless an entirely different methodology or accelerated methods are considered, solution remains optimal. Furthermore, fundamental question is whether approach, or one similar to it, can be extended further for rank-2 games.
9

---

Published as a conference paper at ICLR 2024
5 ACKNOWLEDGEMENTS
We are grateful to anonymous reviewers at ICLR for valuable feedback. loannis Panageas would like to acknowledge startup grant from UCI and UCI ICS Research Award. Part of this work was conducted while Nikolas and loannis were visiting Archimedes Research Unit. This work has been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.
REFERENCES
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In 21st Annual Conference on Learning Theory, COLT 2008, 2008.
Jacob D. Abernethy, Peter L.. Bartlett, and Elad Hazan. 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. JMgR.org, 2011.
Ilan Adler. The equivalence of linear programs and zero-sum games. International Journal of Game Theory, 12:165-177, 2013.
Ilan Adler and Renato DC Monteiro. A geometric view of parametric linear programming. Algorithmica, 8: 161-176, 1992.
Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni. Rank-1 bimatrix games: a homeomorphism and polynomial time algorithm. In Proceedings of the forty- annual ACM symposium on Theory of computing, pp. 195-204 204, 2011.
Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, and Bernhard Von Stengel. Fast algorithms for rank-1 1 bimatrix games. Operations Research, 69(2):613-63 2021.
Ioannis Anagnostides, Gabriele Farina, Joannis Panageas, and Tuomas Sandholm. Optimistic mirror descent either converges to nash or to strong coarse correlated equilibria in bimatrix games. Advances in Neural Information Processing Systems, 35: 16439-16454, 2022a.
loannis Anagnostides, loannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 536-581. PMLR, 2022b. URL https::/o... /ttpcsee/prccceeee ngs ml prwpsprsssss.... v1 62 www.aaannnssssoooooooomo des22a. html
David Blackwell. An analog the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6 (1):1 8, 1956.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 13:1 1990--1999, 2020.
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, pp. 6-I. Workshop and Conference Proceedings, 2012.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint 1807:v1807.04222 2018a.
10

---

Published as a conference paper at ICLR 2024
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems, 31, 2018b.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadinitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero- sum games. In Proceedings of the twenty-second annual ACM-SIAN symposium on Discrete Algorithms, pp. 234-254. SIAM, 2011.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv: 171.0017 2017.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan. Efficient methods for structured -onnonccee min-max optimization. In Arindam Banerjee and Kenji Fukumizu (eds.). The 24th International Conference Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pp. 2746-2754, PMLR, 2021. URL http::/prott http://prrcceddings mmlr wtw..prees/vvv000 hitp:///ii.aaooooslla...aaaa html
Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Journal Computing, 39())2531-2597, 2010.
Francisco Facchinei and Jong-Shi Pang. Finite-dimensionll variational inequalities and complementarity problems. Springer, 2003.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, (9(1-2):79-10) 1999.
Elad Hazan and Satyen Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine learning, 10:165-00 1888 2010.
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What is local optimality in nonconvex-nonconcee minimax optimization? 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. 4880 4889. PMLR, 2020. URL
ngg wwt.ssm.r.pppm httpp////......///////////////// www.w/ii///niee... 11t000e.2222eee1mmmmm1mmmmm
Ravi Kannan and Thorsten Theobald. Games of fixed rank: A hierarchy of bimatrix games. Economic Theory, 42:157-173, 2010.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12: 747-756, 1976.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2/06.01999 2021.
Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, pp. 46-41, 2003.
Ruta Mehta. Constant rank two-player games ppad-hard. SIAM Journal Computing, 47(5): 1853:1888888888 2018. doi: 10.11337/
11

---

Published as a conference paper at ICLR 2024
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint orXiv:/807.0220 2018.
John F Nash Jr. Equilibrium points in n-person games. Proceedings the national academy of sciences, 36 (1):48-49) 4,448-9,,10 1950.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. In Wiley-Interscience, 1983.
Francesco Orabona. modern introduction online learning. arXiv preprint 1rx 2019.
Francesco Orabona. Saddle-Point Optimization With Optimism, November 2022. URL https:// optomimismm
parameterfree. com. http:///////aaaeeeoooooooo-ooppp
[Online; accessed 15. Mar. 2024].
Thomas Pethick, Puya Latafat, Panos Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cy- cles: Global convergence for constrained noncomvex-nomconcave minimax problems. In International Conference on Learning Representations, 2022. URL https:://ppenrevieet net/Forumiid-2
vhkAMARK
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
Shai Shalev-Shwartz. Thesis submitted for the degree of "Doctor of Philosophy". PhD thesis, Thesis submitted for the degree of doctor philosophy, 2007.
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171 - 176, 1958.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Advances Neural Information Processing Systems, 33: 14303-14314, 2020.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
J v. Neumann. Zur theorie der gesellschaftsspiele. Mahheaatscche annalen, 100(1):295-322 1928.
Bernhard von Stengel. Zero-sum games and linear programming duality. Mathematics of Operations Research, 2023.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 30 (1):687-716, 2020.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 TWO-EXAMPLES OF SECTION 3.
Example A.1. In this example, we demonstrate that approximate Nash equilibrium of the zero-sum game (A _AbT,- - + ) does not constitute an approximate Nash Equilibrium of the rank- game, even when we know a correct value of X.
Let A- TAb [i-e [- This game has exact NE of the form (x*,y") (1, (1., -0) for any 4 E [0, 11. Additionally, (#, ù) ((2 2) (2 2)) an 2 a-apprxximae Nash equilibrium of the zero-sum game (A - 1Ab - 1
x= T (A 1Ab ) yn and t (A- (A-1Xb)) 3
1 -
= 2
We now choose a as follows.
2] and b [2 1]
Thus, setting X = (= x a) the rank-1 game is defined
2 1
3
2 2-c
-1 1+c
-=
A
+
and B
1 1
2
1
-
We confirm that (æ: (G) original rank-l game as the condition for the column player does not hold.
()) (
longer qualifies & a-approximate Nash equilibrium for the
C (
Bÿ x
0
2
Specifically, this example highlights that irrespective of our knowledge of X, approximate NE of the zero-sum game that does not satisfy x a X, cannot be a Nash Equilibrium in the original rank-1 1 game.
Example A.2. Let x² (x" yy) be a NE of the bimatrix rank-1 game (A, B) (A, A introduce the operator F.
A ab Tb We
F(z) (
x:
Ay 2
i.c. the gradient operator with respect to the underlying rank game. We note that as both players aim maximize their payoff, the considered gradients come with negative sign.
As described in Section 2.3 recent literature line investigates structural properties of games that enable learning procedure to converge to a Nash equilibrium, beyond the case of a monotone operator F. An example of compelling criterion that guarantees convergence the existence of solution to the Minty variational inequality (MVI) problem Mertikopoulos et al. (2018) or the weak MVI problem Diakonikolas et al. (202)) this example, we show that there exists a game such that neither of those criterion does not hold.
[
(MVI) (F(z), x²) 2 for all
y
(weak MVD) (F(z),z x*) > 2 F(2)11B for all
T where p E 0,
1
4L
13

---

Published as a conference paper at ICLR 2024
The parameter L is the Lipschitz constant of the operator F with respect to the & norm: [| T 2/112. Now, as the set of solutions the (weak) MVI is subset to the solutions set (5VI). we only have to examine x" (a", ,y") that correspond to the Nash equilibrium of the following game.
122 S
2 0
xc xz" y y¹
x = Ay, -B
= - (x x Ayy ly - y--"" x)
A To calculate the Lipschitz constant, we can simply find the spectral norm of the block matrix C n (1,00, (1, and (æ22 y/2 ((0, 1), (0, 1)), and the mixed equilibrium (æ3, 3/s) (( )) ( })). It is important note that when setting = (x, y) to another NE, the inequality must necessarily be less than or equal to zero (S), as the constituent terms (without the minus sign) greater than equal to zero (2) by the definition of NE.
that is, = [2 2.288. This game has the two pure equilibria (x1 y1
(x* v²) ( y1) and (ae, y) (x22, y2).
(x2 Iτ, Ay2) =1-1 1|
11>0 0
(xx .y") = (ax2, y2) and (ax, (x11 y1).
-11 1
(x) x2, Avi)
-1]
=1>0 0
(x',y") = (1:3, Us) and (ar, v) (x11 91).
1 0
3
(x1 - D3, Ag1)
3
4
> 0
Repeating the procedure for the second term ( y" BTx). get that (F(z2), zअ 21) -2, (, 21 x2) -4, (F(z)), 23) -9/4. Furthermore, it is relative straightforward to verify that [[ 6, [[F(())) 12 = [(a(2)) 1. We readily conclude that neither the Minty or weak Minty criterion is satisfied.
A.2 PROOF OF LEMMA 3.3
Lemma A.3 (Proof of Lemma 3.3)
Let (xc, y) be an e-approximate Nash equilibrium of the zero sum game S Then (x. y) is (appoopmxo Nash equilibrium of the
with payoff' (A 1AbT) and x
rank-1 game (A, - A 1X6
Proof. From the definition of the Nash equilibrium for the row player, it holds that
14

---

Published as a conference paper at ICLR 2024
x T (A- (A-1Ab") y 2 xT (A- 12b for every x' An
Since any E An satisfies x: 1 1, it follows that a: (AbT) (ar (arT1)(2bT) (AbT).
Ay 22 x Ay Ay-c - for every x' E A.
(3)
Thus, Equation (3) satisfies the Nash equilibrium condition of row player for the rank-1 game (A, a )) hence they play approximate best response. Similarly, the Nash equilibrium condition for the column player yields the following.
x (A 11--1 S x T (A - 11bT) y +e x Ay S Ay' Xb
>bb(4 (y 3)) tc
Ay S x Ay' + +(-x² a + b 4)+c
x Ay < x Ay' Tbb T (y 3) + eb (y - yy--))- +c
x: (A - ab
S x (A ab)) y + +3c
(4)
The last inequality follows from application the
inequality and the triangle inequality:
(b. y y²) $ ||b||=o|ly - -y'l1 S max [by| (Ily)l 11 (I1) 2. Equations (3) and (4) prove that (æ: y)
satisfy the NE conditions of the game (A, A )b Thus, (æx y) is an (3e)-apprxximate NE.
A.3 PROOF LEMMA 3.4
Lemma A.4 (Proof of Lemma 3.4). Consider the function fx(x, T (A- y- X)2.
If is concave with respect to x and convex (linear) with respect to y. Moreover, assume that the corresponding zero-sum game has c-approximate Nash equilibrium (x",y" with xx" a -| s Then, any c-approximate stationary point (x. ÿ) of f must satisfy the following.
1. Ta V5e.
2. (#. Ū) must be an (6 (C)-NE of the zero-sum game (A 1\bT, - + 1AbT).
Proef. Given that (Ø, 9) is an e-approximate stationary point of S. it satisfies the following variational inequalities (VI).
(I (V.fa(E, 9) x' - =) ((A 1XbT) 8 (x 2)a,'' x' a) <cva' E An
(2 (VyA(a, U). y 9) =((A 18--1. 10- ã. y. 5) 2 - Vy A
First, we leverage the fact that f(-g) concave function for any y, which implies that it satisfies the inequality fa(æ', ū) < (ā 5) (V. fi(:, ū), T). Therefore, when setting x' xx and from (I) and the fact xx= Al
obtain the following.
T (A a
( a X) S (A 1AbT)
ú ( +
'In its general form, the Cauchy-Schwarr Schwarz incquality states (a, 6) < ||a||||b|.. where ||: is any norm and ||+||. its dual.
15

---

Published as a conference paper at ICLR 2024
6²
ax' (A - 11-11b-) ÿ
S a (A 1AbT)
y 2 a X) 2
+
2
T x) 2
x" T (A- 1\b S क T
(A 1b6
+ 2e
(5)
-) is for any æ, which implies that satisfies the equality fx @ 3/ (Vyf( (σ, 8), V ÿ for any y' E Am. Therefore, when setting y' = y" and from VI (2) following.
Furthermore, fx fx(x,.
we obtain the
1 x T (A-10) 1Ab- y¹
2 2 2) 2 T (A - 1xb
1
1
x a - x) -
2
a (A-11 n" 2 E (A 1Ab ) ÿ -
(6)
The last two inequalities follow from the approximate NE definition of (a* y*), with representing the maximizer and representing the minimizer.
e² (A 1Ab ) y² 2 2 (A (A-1>b]] y²
(7)
xx' (A 12b 3² S x² (A 12b ÿ +
(8)
We now have combine appropriately the above four inequalities prove the claim.
(A 6\T
1 S (A 1X6T) y te
S x (A - 1 y" + 2c
S xx' T (A 1Xb ÿ + 3e
1
à -- 2) 2
< T (A 1X6
5
5e
2
T (A-1Xb7) 0 क (A 1 1
1
Ø >)
+ 5e
2
a - v5c
The fact that (w, 5) constitutes Nash Equilibrium (NE) of the parameterized zero-sum arises from the VI (2 in conjunction with the inequality we have just established.
(2)
((A - 11A-) x. y 10-))) 0) - ā 1)bT) " JUSS क (A 1Xb 3 +
V1(1)
((A 1bb
1 4 2) a, x) S
TT (A 1A6
1) 1 2 TT (A 1\bT) 1 (5 a) x' -5) -
a (A 1X6
1 2 x T (A 1)b ÿ - 2 2 55 -
(9)
a T (A 1xb 2 x (A 1\b 9 6vE
Equation follows again from the Cauchy-Schwarz inequality along with the fact that lo: T a - >l S V5c.
Therefore, conclude that (Ø, i) is an (6ve))-app approxxmaae NE of the zero-sum game (A 1 LAb )
16

---

Published as a conference paper at ICLR 2024
A.4 PROOF OF LEMMA 3.5
Lemma A.5 (Proof of Lemma 3.5 Let (æ, () and (x",y") be e-approximate Nash equilibria of the parameterized zero-sum game (A 1 - + 1\bT), that ă a > X and x' T a < X. Then, there
exists (T. T that is e-approximate NE with E a= -
Proof. It is well-established fact that the set of (approximate) Nash equilibria (NE) in a zero-sum game forms a convex set. In other words, any convex combination μa ÿ) + 11--11111000 -1)(a,,, yy", where μ [0, 1, also constitutes NE. Consequently, consider combination denoted æ, with the property that æ X. As explained earlier, this corresponding convex combination qualifies as an c-NE.
A.5 PROOF OF MAIN RESULT
Theorem A.6 (Proof of Theorem 3.7 Let (A,B) be rank- game. Suppose that both players employ
OMWU for T Ω (log n log mi) log(t)) Then, Algorithm returns pair of strategies (a*, .y") that
constitutes an 18e-approximate Nash equilibrium of the rank-1 game.
Proof. For a specific X, we consider two cases. First, assuming that À is correct, meaning that there exists an appa-xppr Nash equilibrium for the rank-1 game, if we run Algorithm for T O [log [log m)
iterations, we obtain a pair (ă, y) that is an aappproxie point of fa. By combining Lemma 3.4 and Lemma 3.3 this pair constitutes a 18c-approximate Nash equilibrium of the rank-1 game.
Conversely, if the value of incorrect, must updated. Considering the sign the difference (x: T A), the parameter is updated according the rule in Algorithm [ binary search steps, we conclude the aforementioned complexity.
Since Algorithm needs most K log (
B MIN-MAX OPTIMIZATION
B.1 BASIC BACKGROUND
In this section, we provide a concise overview of how online learning, particularly regret minimization, can be employed solve saddle point problem. Most of the results described here can be referenced in Orabonal (2019). We examine the general saddle point problem, as defined in Section 2.3
Definition B.1 (Saddle point problem). Let X C R" and X C m and f XXXX + R. A point (x+ y²) E x Y is saddle-point of in X Y if
f(x" ,)) S f(=,"'"'"
V²) Va X
We first describe the scenario where is a convex-concave function, meaning that f(. is convex for any y E Y, and (ax is concave for any æ E X. In this case, the minimax theorem v. Neumann (9228) Sion (1958) states that:
Theorem B.2 (Minimax theorem v. Neumann (928); Sion 1958)). Let X and Y be compact, convex subsets R and Rm respectively. Let f x Y R continuous, convex-concave function. Then, we have that
min max f(x, y) mEX DEY
max min fx, y)
DEY xeX
17

---

Published as a conference paper at ICLR 2024
Online Learning The saddle point problem can be reformulated as a regret minimization problem as follows. We focus on the first player, whose goal is to minimize the function f(x) = maXyey f(e, y), and Player 2, whose objective is to maximize the function f(y) mingex f(x, y).
Then the standard suboptimality gap, that describes the improvent of Player over time, is
f(x:) = max [(x(1)) min =EX
(xx(") min max f(z y) yEY
(Gapx)
xxX yEY
Similarly, for Player 2, the corresponding measure would be:
max yeX
f(x f f(y
max min f(x, y) yEY #EX
min f(x (0))
(Gapy)
=
By adding these two measures and combining them with Sion's 's minimax theorem, we obtain the suboptimality (Nash) gap.
max f(x y) min max f(x y) +max min f(z y) -min f(x, (0) = mmax f(x WEY
yy- --mmnnn- f(x, (t) (Gap)
wEX wEY
wEY ØEX
weX
WEY
xEX
Regret We describe the process from the perspective of Player 1. an online learning framework, the learner chooses a strategy (+) X every round t [T'. Then, the learner receives linear loss function ex (z). Based on the feedback received thus far, they update their strategy for the next round. The standard objective is to minimize the cumulative external regret, defined as follows.
Regret x (x) = Σ 2 (z)
Σ P
where & E [2'] is the time horizon. In other words, performance is evaluated based on the optimal fixed strategy in hindsight. To provide further precision, it's worth noting that regret typically defined with respect to the strategy xe that maximizes Regretx (?') (az). (x:). Nevertheless, for the sake of clarity in our explanation, we will retain the previously stated definition.
Optimistic Regret Minimization Indeed, it is widely acknowledged that a wide range of online learning algorithms, including www.w-The-Regaaizeeeeee and Mirror Descent Nemirovskij Yudin (1983), can guarantee O(VT) regret under any sequence of
(FTRL) Abermethy al. (2008); Hazaan & Kale (2010)
bounded utilities. However, when dealing with more predictable utilities, one can achieve even stronger convergence guarantees, In recent years, several studies have explored this direction Chiang et al. (2012):
Rakhlin & Sridharan (2013); Syrgkanis et al. (2015). In our work, we focus on the optimistic mirror descent algorithm, as detailed in Rakhlin & Sridharan (0033)
Optimistic Mirror Descent
Suppose now that each player employs optimistic mirror descent. The feedback that Player receives each round set to g(t) (gX) ar) where gx = v ()), while Player
2 receives (1)) (g(") y) where gf¹) --V - (v,f(x (t)) As usual, we consider the "one-recency bias" prediction Syrgkamis et al. (2015). wherein (()) (t-11)
Assumption B.3. Assume that f X x Y + R is smooth in an open interval containing its domain, in the sense that for any x, xx' E X and any y, yy E Y, we have the following.
Waf(x, y) - Vz.f ,v)lx,, S Lxx]|æ - xxl] ||x
V (x, - V f I'),,,,+ S Lxylly - y ||y
| Vyff(z (x, y) Vyf(a 4) Iv,, S LxY - x x
18

---

Published as a conference paper at ICLR 2024
Algorithm 3: Solving Saddle Point Problem with Optimistic OMD Orabona (022)
1 Require: Ax > 0, Xy > O, 2 E X, y1
2 9x 0. 0y
(0)
(0) 0
3 for 1, , do
(t) (=((a())) (*)
9x
gy = vzf(x!)) (())
5
(+++1) 1)++1) E arg min (2g (t) (t-1)
9X x) + Ax Box (x; x!1)
6
y (++1) arg min yey (2g (t)
9y . xy Buy (y: (t))
(1-1)
return T (T)
x (1) y T Σ y()
8
[V,f(z, v)
-y'lly Vyf(a, llr S Lyy 1 y'lly
where Va and Vy denote the gradients with respect to and y respectively. We denote by xIIIIx,,II-I)xx and (II-Ilx, II-I));, the pair of dual norms in X and Y.
The following theorem, originally proven in Rakhlin & Sridharan (2013), has been cited from Orabona (2022).
Theorem B.4. Orabona (022) Let f X X Y + R a convex-concave function satisfying the Assump-
tion B.3
For a fixed a > O, lel Ax 2 2/x + Lxv/a) and Xy 2 2//( + /o). Let R be 1-strongly convex w.r.t. 11-I1x and thy Y IR be 1-strongly conver w.r.t. ll-lly. Assume
x X
arg max WEY f f(x(1') y) and arg min f(x (()) are non-empty. Then, we have
Box (2)1) + Bör (2)
llay B..
max f(x (T) yEY
y min f(z, y (T)
x
Ax
Ay
T
where (T)
x
y T
(t)
Lemma B.5 (Lemma 16 Shalev-Shward (007)). v(x) = Σ x; In w. is 1-strongly convex with respect to x; 2 0,
1=1
the La norm over the simplex An == {x E R
| = 1}.
B.2 PROOF OF LEMMA
In the proof of the lemma, we consider the function fx = - 11b yy - 3x æ is the maximizer and y is the minimizer in our context, and we define = A, and Y = Am Due to this, select the negative entropy the regularizer for both X and Y, that is, rix (æ) Σ 2is1 at, In a4 According to Lemma B.5 this choice ensures that the regularizer is 1-strongly convex concerning the L norm, satisfying some of the conditions outlined Theorem B.4
X)2 where
Next, we examine whether Assumption B.3 are satisfied. Instead of deriving each constant individually, we utilize Proposition B.6 The Hessian matrix of fa is a block matrix composed of four blocks, H
an T A 0 Therefore, we can readily bound each constant Lxx, Lxv, LyY by 4 max{[I [|a||2].
Proposition B.6 (Claim C.2 Leonardos et al. (2021) ). Consider a symmetric block matrix C with n x n. matrices so that [[C 2a & L. Then, it holds that [C]|| nT.. In other words, if all block matrices have spectral norm at most L, then C has spectral norm at most nL.
19

---

Published as a conference paper at ICLR 2024
Regarding the initial Bregman divergences B (x())=1))) and Bøy y it's worth noting that when xx(1) and y0 are initialized to the uniform distribution, they are both upper-bounded by In n and Inm, respectively:
m
Box (u:z)
Σ u, in u, + Inn and B (w; y)
Σ
u n
In m S Inm m
j=1
Lastly, we will bound the dual norm of the gradients vector. For the sake of completeness, we will present the upper bound for 11,,..
11gx
(1) Ixx, = 119 11 S II(A 12b )all + a -/lla
max (A 12b ).y) + a/lo I (Amax + + iE|n]
1gg ||,,- = 1198 a0 S II(A 12b ) x0 I (Amux +
Lemma B.7 (Proof of Lemma 3.6p. Let (x("), y0!) be initialized uniform vectors (L/n, 1/m). Sup- pose that both players employ OMWU for T S (lan+lam) with learning rates T)X T/y (o(T)y'')) that guarantees
max2 2 and fixed X. Then, Algorithm returns a pair of strategies the following.
Gap (T(T),(()) (T
max fx WEA
(Z. min fx (T) Sc.
yEAm..
Also, it holds that (eTT)g(T) is an e-approximate stationary point of fx-
Proof. As mentioned previously, all the assumptions and required conditions of Theorem
B.4 have been
satisfied. By setting 1, Ax xy 16,2 max{||A]p I|2, [|a|l)), bounding ||g
(1)
X
1
1)
by
(A (Amax= - 4) and T 2 O ((nntlnmm, we obtain the following results from Theorem
B.4
max fa (") min fx y ()) Se mE
yE
The fact that (I("), - is an e-stationary point can be deduced from the definition of the Nash Gap, the nen-negativity of both terms, and the definition of a convex-cone convev-concave function for fx-
C EXPERIMENTS
In this section, we provide experimental evaluation supporting our theoretical finding. Here we restrict to a single example, while also provide aanonymous repository containing multiple rank-1 games of multiple sizes
0.10
0.50
0.50
-0.00
-0.307
0.600
0.30
0.00
-0.10
-0.30
0.10
-0.20
0.80
1.00
A
0.10
-0.20
-0.30
0.00
-0.30
a
0.80
b
0.50
-0.30
0.20
-0.10
-0.20
0.00
0.00
0.60
-0.40
-0.20
-0.30
0.40
-0.30
0.10
0.10
20

---

Published as a conference paper at ICLR 2024
Strategies
Y Strategies
Nash Gap
0.10
0.8
0.08
0.6
0.4
0.06
0.4
0.04
0.2
0.02
0.0
0.0
0.00
20000 40000 60000 80000100000
20000 40000 60000 80000100000
20000 40000 60000 80000100000
X Trajectory
Trajectory
0.8
0.8
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
Figure 1: In Figure la we observe how the strategies of the players evolve over time when they employ vanilla OGA, alongside with the Nash gap defined in (Gap). In Figure plot the respective trajectories the simplex signifying that OGA enter limit cycle.
We constructed random 6 x 6 game defined by the matrix A, and the vectors a, b. Then, the payoff matrix of the second player derived usual: -A ab Our solution delineated Section 3.2 is compared against (vanilla) optimistic variant of mirror descent. More specifically, our tests were performed with (optimistc) gradient ascent (OGA) instead of multiplicative weights to avoid any numerical imprecision that might arise due to exponentiation.
Figure D we (experimentally) verify that OGA enters limit cycle, whereas our solution Figure 2 reaches a Nash equilibrium. While this game may not have natural interpretation initially, given their random construction, worth noting that constructing random games where OGA provably enters limit cycle rather challenging. This difficulty is further explained by the recent work Anagnostides al. (2022a).
21

---

Published as a conference paper at ICLR 2024
Learning Rank-1 Games
Strategies
Strategies
Nash Gap
0.8
0.08
0.6
0.4
0.06
0.4
0.04
0.02
0.0
0.0
0.00
50000
100000
150000
50000
100000
150000
50000
100000
150000
X Trajectory
Trajectory
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 2: In Figure 2a we observe how the strategics of the players evolve over time when they employ Algorithm alongside with the Nash gap-as defined in (Gap). In Figure 2b we plot the respective trajectories on the simplex as well.
22


Reviews:
[{"review_id": "D1gbjIMUVa", "reviewer": "Reviewer_cjaZ", "summary": "The paper focuses on learning (approximate) Nash Equilibria of rank-1 bimatrix game, which can comprise a potentially large number of disconnected components, and may lack convexity in general.\nThe rank-1 bimatrix games, which have been shown by Adsul et al., 2021  to have polynomial-time algorithms, are especially interesting, as k>=3 are PPAD-hard, and the complexity of k=2 games are left as an open question.\n\nThe authors build upon the reparameterization approach of Adsul et al., 2021, which establishes a link between rank-1 games and parameterized zero-sum games. \n\n- In Section 3.1, the authors illustrates that naively solving an approximate NE of parameterized zero-sum games does not necessarily results in the approximate NE of the original rank-1 games.\n- In Section 3.2, the authors sequentially connects the approximate NE of rank-1 games to (constrained) approximate NE of parameterized zero-sum games, and (constrained) approximate NE of the parameterized zero-sum-games to the approximate stationary points of an energy function.\n- Finally, the authors propose an algorithm that combines binary search and OMWU that provably learns the approximate NE of the rank-1 game.", "questions": "# Technical Novelty\nI would appreciate if the authors could clarify the the main technical novelties of this work over Adsul et al., 2021 that could contribute (either directly or indirectly) to the future work in this field (differential games, robust optimization, multi-agent RL, etc).", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "- The related works are well-studied and well-presented\n- Theoretical claims are well-backed with easy-to-follow proofs", "weaknesses": "# Technical Novelty \nIt seems most of the technical heavy-lifting (the reparameterization approach, Lemma 3.3, and the usage of binary search) builds upon  Adsul et al., 2021, and lacks original technical contribution & viewpoint that could be useful for the other researchers in the future. \n\n# Broader Context\nI think it would better if the authors could put their theoretical results in a broader context of current literature, and explain why this rank-1 game is an important subclass of differential games.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "0nX7YCVWBk", "reviewer": "Reviewer_TKWX", "summary": "The authors study the problem of finding Nash equilibria for bimatrix rank-1 games. They propose a novel decentralized algorithm for finding approximate Nash equilibria of rank-1 games. Their approach works by reducing the problem to a sequence of parametric zero sum games where the parameter changes for each step of the sequence. Approximately solving the zero sum game and then adapting the game parameter repeatedly leads to an approximate Nash equilibrium for the original game. This decomposition allows the authors to bypass the fact that the original game does not satisfy the Minty variational inequality.", "questions": "I think some more explanation about how we computed the bound on K would help. I guess I am missing the argument about why we only need to know $\\lambda$ up to $O(\\epsilon)$ accuracy or at least some similar argument for the binary search termination.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To the best of my knowledge, this work is the first to propose gradient based decentralized algorithms for approximate Nash equilibria of rank one games. Even though the general solution framework is the same as in Adsul et al. 2021, as they both reduce the problem to a sequence of parametric zero sum games, the way each zero sum game is tackled in this work is different and novel. Handling the additional constraint to the zero sum game was non-trivial. In addition, showcasing new  decentralized learning algorithms for games that go beyond the MVI property may be of independent interest.", "weaknesses": "The algorithm proposed is decentralized in a somewhat limited sense. For example, the two players need to coordinate to solve the same parametric game zero sum in each iteration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "KtplKWa3oe", "reviewer": "Reviewer_r4eu", "summary": "This paper studies the problem of learning Nash equilibrium in two-player rank-1 games, which does not satisfies the Minty condition. The main contribution of the paper is an efficient algorithm for learning Nash equilibrium in two-player zero-sum games. The main technical insights that enables the result are structural results of rank-1 games. Specifically, it is shown that the set of Nash equilibria of a rank-1 game is equivalent to the set of Nash equilibria of a two-player zero-sum game (with additional constraints, so can be seen as a saddle-point problem). The proposed algorithm is double-loop in the sense that the inner loop runs OWMU on the parameterized zero-sum, finds an approximate Nash equilibrium and the outer loop updates the parameter.", "questions": "1. Does rank-1 games satisfy the weak Minty condition?\n2. Can the authors comment more on Algorithm 1? Is it possible to get a single-loop and decentralized algorithm?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "This paper is fairly well-written and easy-to-follow. I really appreciate the authors for providing very detailed high-level iades and proofs for every technical results, which makes the paper very clear.", "weaknesses": "Several concerns about the technical contributions.\n\n1. There is no lower bound results and it is not know if the provided convergence rate is optimal. \n2. The authors show that there exists a rank-1 game that does not satisfies the Minty condition, so previous results on efficient convergence does not apply directly to rank-1 games. However, recent results have shown efficient convergence under a weaker condition than the Minty condition, called *weak Minty* [1, 2, 3].  [1] proposed the notion of weak MVI, while [2,3] generalized the notion to the constrained setting.\n3. I am not sure whether Algorithm 1 is a decentralized algorithm since it is a double-loop algorithm and requires some coordination between the two players. Thus Algorithm 1 is more like an algorithm that computes the Nash equilibrium, not a decentralized learning dynmics that converges to Nash equilibrium\n\n[1] Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization, Diakonikolas et al., AISTATS 2021\n\n[2] Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems, Pethick et al., ICLR 2022\n\n[3] Accelerated Single-Call Methods for Constrained Min-Max Optimization, Cai and Zheng, ICLR 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "rKrfqXnA7u", "reviewer": "Reviewer_LH17", "summary": "The authors consider the problem of approximating the Nash equilibrium (NE) of a rank-one two-player game where the sum of the payoff matrices is of rank one. They prove that a modification of the optimistic mirror descent converges, used to learn a NE in zeros-sum (rank-0) games, to an \\epsilon-approximate NE after O(1/\\epsilon^2\\log(1/\\epsilon)) iterations. They achieves this by leveraging a reduction of rank-1 games to rank-0 games building on the results by Adsul et al. (2021).", "questions": "#General comments:\n\n- Do you have a concrete/practical example of a rank-one game?\n\n- It would be interesting to provide some preliminary experiments on some toy games to compare the proposed algorithm to vanilla OMWU.\n\n- The intuition at the end of Section 1 is not very clear in particular about the fundamental connections between rank-one and rank-zero games.\n\n- It would be clearer to introduce  definitions on the equivalence of games since many technical points rely on jumping from on formulation to another.\n\n- How do your algorithm compare with the one of Adsul et al. (2021) in terms of rates, complexity; since both algorithms seem to solve the same problems with similar techniques.\n\n- What can we say about rank-two games?\n\n#Specific comments:\n\n- P1, introduction: it is not clear what is the MVI property. And \"games, We\".\n\n- P2, top: It is still not clear what is the Minty property. Maybe you can compare the rate you obtain with the rate one can obtain in a rank-0 game. Is \\lambda a real parameter or also a vector? Do we really have that extra gradient and optimistic mirror descent fails to converge if the Minty property is not verified or we can just say we cannot provide any guaranties in this case?\n\n- P3, Lemma 2.6:  what do you mean exactly by a game \"can be written\" in a certain form ?\n\n- P3, end: \"In the what follows\"\n\n- P5, end of Section 2.3.1: It is still not clear what is the Minty criterion.  The link between (MVI) and (VI) and when it is possible to solve (VI) with extra-gradient of optimistic mirror descent is also not clear, e.g. what do you mean by \"the Minty variational inequality is satisfied'. You also talk at some point about saddle point in the context of VI. Maybe you could specialized the results for saddle point without introducing the setting of variationnal inequalities.\n\n- P7, Algorithm 1: How do you initialize \\lambda?\n\n- P9, before Lemma 3.6: How do you initialize  \\lambda, and maybe you should precise in\nwhich interval \\lambda lies.\n\n- P13, before (8): Can you detail the second inequality. I think  you should work with the difference \\lambda-xa and upper bound this difference after applying Cauchy-Schwartz inequality.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think the proposed algorithm and associated analysis is a natural and valuable contribution. The proofs seem correct and are easy to read as far as I checked.", "weaknesses": "The general presentation could be improved, see specific and general comments. The literature review could also be improved in particular it is not clear what is the exact contribution of this work   in comparison to the one by Adsul et al. (2021).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)