Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
Authors: Hedi Hadiji
Sarah Sachs
Tim van Erven
Wouter M Koolen
Venue: NeurIPS 2023 poster (2023)
Keywords: game theory
minimax optimization
lower bounds
TL;DR: We provide the first lower bound for the first-order query complexity of approximate Nash equilibria, and discuss why this problem is difficult.

Abstract: In the first-order query model for zero-sum $K\times K$ matrix games, players observe the expected pay-offs for all their possible actions under the randomized action played by their opponent. This classical model has received renewed interest after the discovery by Rakhlin and Sridharan that $\epsilon$-approximate Nash equilibria can be computed efficiently from $O(\frac{\ln K}{\epsilon})$ instead of $O(\frac{\ln K}{\epsilon^2})$ queries. Surprisingly, the optimal number of such queries, as a function of both $\epsilon$ and $K$, is not known. We make progress on this question on two fronts. First, we fully characterise the query complexity of learning exact equilibria ($\epsilon=0$), by showing that they require a number of queries that is linear in $K$, which means that it is essentially as hard as querying the whole matrix, which can also be done with $K$ queries. Second, for $\epsilon > 0$, the current query complexity upper bound stands at $O(\min(\frac{\ln(K)}{\epsilon} , K))$. We argue that, unfortunately, obtaining a matching lower bound is not possible with existing techniques: we prove that no lower bound can be derived by constructing hard matrices whose entries take values in a known countable set, because such matrices can be fully identified by a single query. This rules out, for instance, reducing to an optimization problem over the hypercube by encoding it as a binary payoff matrix. We then introduce a new technique for lower bounds, which allows us to obtain lower bounds of order $\tilde\Omega(\log(\frac{1}{K\epsilon})$ for any $\epsilon \leq 1 / (cK^4)$, where $c$ is a constant independent of $K$. We further discuss possible future directions to improve on our techniques in order to close the gap with the upper bounds.

Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
Hedi Hadiji
Sarah Sachs, Tim van Even Korteweg-de Vries Institute for Mathematics University of Amsterdam
Laboratoire des signaux systèmes Univ. Paris-Saclay, CNRS, CenéraleSupélec
Wouter Koolen
Centrum Wiskunde & Informatica and University of Twente
Abstract
In the first-order query model for zero-sum K K matrix games, players observe the expected pay-offs for all their possible actions under the randomized action played by their opponent. This classical model has received renewed interest after the discovery by Rakhlin and Sridharan that e-approximate Nash equilibria can be computed efficiently from OlIn K/e) instead of OIn K/e²) queries. Surprisingly, the optimal number of such queries, as a function of both E and K, is not known. We make progress on this question on fronts. First, we fully characterise the query complexity of learning exact equilibria (s 0), by showing that they require essentially hard
number of queries that linear K, which means that querying the whole matrix, which can also be done with K queries. Second, for 0, the current query complexity upper bound stands at ((min(In(K))) We argue that, unfortunately. obtaining matching lower bound is not possible with existing techniques: we prove that no lower bound can be derived by constructing hard matrices whose entries take values in known countable set, because such matrices can be fully identified by a single query. This rules out, for instance, reducing to optimization problem over the hypercube by encoding payoff matrix. We then introduce a new technique for lower bounds, which allows us to obtaín lower bounds of order {(log(( x )) for any & < 1/(cK*), where e is constant independent of K. We further discuss possible future directions improve on our techniques in order to close the gap with the upper bounds.
K)).
binary
Introduction
Computing the saddle point
min max f(z, v) EE nEy
for convex-concave functions f X' x R of general interest throughout optimization, economics and machine learning. We study the computation of an approximate saddle point (I,, yx). satisfying maxyey (xx v) mingex f(x, v/)) 2a for some given > 0. Starting with an unknown ff from known class F, we consider sequential learning in the first-order feedback model, where the learner gets observe gradients of the objective. Formally, each query (x. y) results in feedback (V.f v), V fz, ((z.v). v)). We are interested in the following question:
How many firtt-orr queries are necessary and sufficient for a sequential learner oulput an approximate saddle point for any f E F?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Characterizing the query complexity of learning saddle points is of theoretical interest for understand- ing the hardness of computing equilibria, and for certifying the optimality of upper bounds.
In this work, we restrict our attention to the special case of zero-sum matrix games, where X' and y inite-dimensional probability simplices and f is bilinear. For this canonical setting, the optimal query complexity is, surprisingly, unresolved. Indeed, computation algorithms are known since (3], up (37,, while lower bounds remain elusive, leaving the optimal query complexity still unknown.
Obtaining lower bounds is not only of fundamental interest in itself, but may also lead to interesting new techniques, since none of the existing proof strategies applicable. New ideas provided here could prove useful to tackle other problems.
1.1 Contributions
We make progress towards characterizing the first-order query complexity of approximate Nash equílibria in finite-action zero-sum games, as function of the number of actions K and approximation level Our contributions are the following:
Lower bounds We provide the first lower bounds on the first-order query complexity for zero-sum matrix games with bounded entries. We show that K/2 queries are necessary compute an exact equilibrium (Theorem 11 in Section and at least (1(lo(11//)) an e-equilibrium if & T (Theorem 17 in Section 4). More than the concrete rates, we believe that the structure of our proof is of particular interest, and might be of use beyond this specific setting.
log(K)) queries are required for
Upper Bounds We show that if the game matrix has entries in a known countable set, then the learner recover the full matrix in one single first-order query (Theorem 4 in Section 3 This result can be interpreted both as an upper bound on the query complexity for matrices on countable entry sets, and as impossibility result, precluding the use of simple predefined sets of matrices as candidate objectives for proving lower bounds. This, together with the lack of rotational invariance of the action sets, sheds light why this setting turns be surprisingly resistant proving lower bounds using well-established techniques.
1.2 Related Work on Lower Bounds: Lower Bounds
Below we review the literature on lower bound techniques for related problems and settings. We find that none of the existing techniques apply to our setting, for three particular reasons. They either:
Build matrices from a set of matrices with entries lying in finite alphabet. In Theorem f we show that, for game matrices with entries in known countable set, single first-order query suffices to infer the exact Nash equilibrium. This shows in particular that any such matrix construction cannot lead to lower bound in the first-order model.
Rely crucially rotational invariance of the action set, which limits the approach to the é2- constrained or unconstrained cases, ruling out the probability simplex.
Assume that the players select actions in the span of the observed gradients. This span assumption is not suited when the action set is not an & ball, in which case the span of the gradients has no natural embedding into the action set; most algorithms leave the span, c.g. exponential weights.
First-order Query Complexity of Minimax Optimization Existing lower bounds 24 33 for minmax optimization are known for finite-dimensional Fuclidean spaces where X y are either Euclidean balls or the whole space. Both these cases benefit from the property that the action sets are invariant under rotation, allowing for a step-by-step reduction to lower dimensional instances, as shown in the seminal work of (29 30 The notable exception of [14] also does cover the case we study: they consider the computational hardness of non-convex non-concave optimisation.
In the unconstrained case with curvature, that is, if F is the set of strongly convex, strongly con- cave functions with marginal condition numbers K2 and Kyy the query complexity is settled to be 43 for lower bounds and [27 and references therein for upper bounds.
(Kv (0g(()))): see 24
For the constrained case, 33 provide lower bounds for bilinear saddle-point problems. They establish query complexity of order Dy/EE), where Dx and Dy are the respective diameters of the
2

---

constraint sets X' and V and Ly measures the Lipschitz regularity of f. However, their techniques rely crucially on rotational invariance and sequentially adapted constraint sets, and they ask the open question of whether similar lower bounds can also be shown for fixed constraint sets.
Other Query Models The query complexity of minimax optimization has also been studied under different feedback models. some game matrix M. (16) study the query complexity of (approximate) Nash equilibria of the game, i... (approximate) saddle points of f. under a query model where the learner chooses single entries of the matrix to observe. They show, among other results, that in order to compute E-equilibrium in x K zero-sum games, the number of entries queried needs to be at least 2 log K) when O11 log K). (2) consider setting in which the learner observes best reponse to their query (p, q). i.e., it E argmin (Manninn(M)eaaa and 1 E argmin - (MTp), In that setting, they show that to compute a / /4-equilibrium,
that we focus on the bilinear case, where f : p. + p q for
least 92( D(VK/ /K/oog//// k)² best-response queries are necessary. Since first-order query brings strictly more information than either a best-response query or an entry query, these lower bounds do not have direct consequences for our query model. Both of these references prove their lower bounds by building hard matrices with entries in a known finite set (c.g., {0, 1)).
Other Lower Bounds in Saddle Point and Equilibria Computation For multiplayer games, strong lower bounds on the computational complexity of exact Nash equilibria have been uncovered: PPAD-hardness for computing the Nash-equilibrium in general game, see [79), or in non-convex- concave zero-sum game [14] Regarding query complexity, (2 21 study the single-entry query complexity for approximate correlated equilibria and Nash equilibria of games with many players. As in other references mentioned, all these bounds are built on matrices with entries a finite set. Due to their intrinsically combinatorial nature, these techniques are less common for numerical algorithms. One of the classical methods for sample complexity lower bounds was introduced by (31] for first-order optimization. It was successfully extended to saddle-point problems (S] and recently also to unconstrained zero-sum games by [24]. However, these techniques rely on the assumption that the next iterate is chosen in the span of the previous oracle information
(ef. Definition 1 in [24 or Assumption 2.1.4 in B1). Moreover, the game constructed by [24] for a Nesterov-style lower bound results in matrices with entries from finite alphabet. For the same reason, no proof technique inspired by lower bounds via Rademacher random variables, as in (32] can ever work.
1.2.1 Other Related Work
Upper Bounds for Finite Action Zero-Sum Games Early on, 3 38 show that under best- response dynamics, the average plays converge to an equilibrium. The connection to regret bounds was established by (17), who deduce (log(() /e2)) query complexity, by means of construction akin to online-to-batch conversion. More recently, [1] [2] obtained the first fast rates of order (c((K)))) through an ingenious learning mechanism. [37] rediscovered the Optimistic Online Mirror Descent algorithm (36), and pioneered optimistic online learning regret bounds; they yield to this the day the fastest rates of ([log(K)/e) and the simplest algorithm. The instance-dependent linear-rate upper bounds of order A(M) In(1/e) by [19 41) are essentially incomparable to the
worst-case (log((K) /E)); they are superior when X(M) K, and vacuous in the typical case X(M) = K (see the discussion below Theorem l.
Our focus is the quality of the inferred saddle point (this optimization perspective is sometimes called pure exploration). Part of the literature regards the queries as actual moves made, and consequently prioritizes other objectives. In particular, many focus on studying uncoupled dynamics, that is, sequences of actions that separate the observations of the individual p and players without allowing communication between the players. Another recent theme of interest is the last-iterate convergence of such dynamics, see e.g., [23].
Upper Bounds for Minmax Optimization The vast majority of the known upper bounds in minimax optimization (and more generally in variational inequality problems), outside of finite-action zero-sum games mentioned above, concern unconstrained settings [ 20 28). The literature on constrained settings is more sparse: 4 recently proved the rate of convergence the projected extra- gradient method [26] 42 adapt interior methods to handle constraints. [18] propose fast algorithm when either the action sets are strongly convex, or the objective is strongly-convex strongly-concave. Recently, non-convex-concaat settings have also attracted attention, see [27] and references therein.
3

---

Upper Bounds for General-Sum Games and Correlated Equilibria uncoupled dynamics do not converge (in any sense) to Nash equilibria. procedures can find correlated and coarse correlated equilibria [5]
For multiplayer games, However, regret-based
In particular, internal regret guarantees for individual players general-sum multiplayer games were recently improved from the generic ( for any sequences of losses, to (11/54/3) in 40), to O(1/e in 6 and to (1oog(1/))/ in 13, 15 (we omit the dependence on the number of actions and players). Polynomial-tine time methods for efficient computation of exact correlated equilibria are designed by
39 35
25
34, using their formulation as solutions to a linear program.
2 Setting and Notation
Given a set of numbers A C R. we denote by MM the set of K x K matrices with entries in A; we mainly consider the bounded-entrics class MM 11,1,,], 1)). ([-111, zero-sum game between minimizing p-player (or row player) and a maximizing q-player (or column player) is represented by a matrix M E MMx (R); we restrict our attention to square K x K games. For any pair of plays (p. 9). the expected loss vector of the p-player (resp. q-player) is Mq R (resp. - -T E IR ). ). The suboptimality gap at (p, q) is
General Notation
A K K
g(M, q) max (MP)), min (Mg). <E[K]
JEKK
The gap ( p. q) is non-negative for any M, and g. The pair of plays (p,q) is said to be e-Nash equilibrium if g (M, p. p. & 2c; Nash equilibria are O-Nash equilibria. Most games we will consider will possess unique Nash equilibrium p, q. and this equilibrium will be fully supported, i.e., all components of and are positive. Fully supported equilibria in finite games are also equalizing strategies, meaning that the loss vectors are then isotropie; in finite zero-sum games, this entails that MTp Mq vl, where v is the game-value. We follow the notation convention to abbreviate min(x, v) = x A v and to hide polylogarithmic terms by fl or Ó.
First-Order Query Model and Objectives The finst-order query model an interaction protocol between a learner and a game matrix, defined as follows. Fix time horizon T e N, and set of candidate matrices M C MM (R). Over the course of T rounds, the learner sequentially picks (queries) pairs of plays (pt, q:) and observes the expected losses (Mq, P.).,, where the matrix M E M is fixed and unknown to the learner.
We examine the number of interactions necessary to compute approximate equilibrium. At the end of the rounds, the learner recommends a pair (p, q) Given a fixed gap level > and set of candidate matrices M, we say strategy achieves query complexity T(e; M) if for any matrix M EMM the strategy outputs a pair p, q such that g(M, p. 4) < 2e when > T(s; M(. (The dependence on M is omitted when clear from context.) We also occasionally refer to the query complexity of recovering the full matrix, which a different task but in the same query model. In this case, the learner recommends full matrix and achieves query complexity T if the matrix guess is correct for any true matrix M E M.
The topic of this paper is the study of the optimal query complexity of finding c-Nash equilibria in the first-order model, for the set of matrices with bounded entries Mx x (M([[111)]
3 Upper Bounds
In this section we collect upper bounds for the first-order query complexity of approximate Nash equilibria. These bounds are either well-established, trivial or exploit in miraculously striking fashion the difference between learning saddle points for matrix games taking entries in a countable (e.g., Q) uncountable (e.g.. [-1, 1111) sets of values.
3.1 Query Complexity over Mx ([-1, Regret and Elementary Strategies
We list some well-known results from the literature and state them in terms of first-order query complexity. The results described here are compiled in Figure We use the notation tham to denote the family (ux) E

---

K
K
log
K
Rakhlin and Sridharan
37
Queries (()
T(=) 0
Ô (log K Theorem 17
1. by
Prop. 3
T(x)
clog K
clog K
Daskalakis et al.
c/ K
log K K
Figure 1: Upper (blue) and lower (red) bounds on the first-order query complexity of computing an e-equilibrium for K x K matrix games with entries in [-1, 1]. See Sections 3 and 4 for details.
O K) Queries from Optimistic Online Learning The current best upper bounds on the query complexity of e-equilibria for zero-sum games are derived from online learning methods. As is well-known [ Chapter 7], if we denote by Pr (resp. (r) the average of Pı:r (resp. (i.r) then
(g(M, ) T max (MTPr); T min (Mār): jE[K]
sE[K]
Σ t=1
(ps Mqp)
T min (M@r): + --i- -MTpp) TT min (-MTpr); iE[K]
iE[K]
(pe, Mq))
Σ min (Mq:):
Σ (9e. -MT
Σ min 1-M pt); KE[K]
EE(K]
This last term is exactly the sum of the regrets suffered by each player their respective losses: the gap of the average plays is smaller than the sum of the average regrets over T rounds. This relationship between regret and gap provides fruitful way to upper bound the query complexity of computing equilibiria. Specifically, [37] observed that if players follow the Optimistic Mirror
Descent strategy then the of the regrets stays smaller than Olog K); see the paragraph following Proposition 6 in the mentioned reference.
Theorem (Consequence of Rakhlin and Sridharan (37 There exists an absolute constant c
such that the first-order query complexity over Mx (1-1, 11 1]) is
T(s) < (c log K
K.
A wide stream of literature leverages the connection between regret and equilibria, and study the dynamics of pairs of learning algorithms, including the two principal flavors of optimistic online algorithms, Optimistic Mirror Descent and Optimistic
thw-Reeularized-Laee
cf. Section 1.2
Insendet Rates of Convergence Many existing bounds show rates of convergence exponential in T', with instance-depender constant?] see, e.g., [19 41
However, we show in Example 18 that for a zero-sum two-player bilinear game, these constants can be large, even on simple game matrices. If the constants are too large, the consequences vacuous, as they might require more than queries to obtain non-trivial (e < 1) equilibria. Although these results give very interesting analysis beyond the worst-case, they are beyond the scope of this work.
query complexity are
More precisely: parameter similar to condition number of the game matrix
5

---

Upper Bounds for Large We conclude this section with two elementary strategies that provide equilibria with large approximation values of ε 3 1/2.
Theorem 2 (Theorem. 3.1 in 10). For any 1/2. the query complexity over Mx((-1,1)) of finding an E-equilibrium is T(e) & 2.
The following proposition is well-known observation (see, e.g.,
[6]) that having the learner select
a pair of uniform plays always gives an approximate equilibrium.
Proposition 3. For any & > 1 - 1/K, the query complexity over Mx((-1,1)) of finding an e-equilibrium is T(e)= O.
3.2 Recovering the Matrix: Upper and Lower Bounds
In this section we show that the first-order query complexity for recovering the full game matrix (a task harder than computing an equilibrium) is between (1)), independent of the number of actions, and @ ( depending on the set of candidate matrices. An important consequence of these results is that several known standard lower bound techniques cannot be applied to provide lower bounds on the easier task of learning equilibria.
Matrix Sets with Countable Alphabet Many existing methods rely on building hard matrices with entries in finite alphabet: we prove this cannot lead to lower bound.
Theorem 4. Let A C R be countable set of at least two numbers. Then the first-order query complexity over Mx(A) of recovering the full matrix is 1.
This result exploits infinite precision in the feedback, and as such does not provide a reasonable algorithm that the players would use should they know that the matrix belongs to MM (A). The intent of this statement is to show that any attempt at a lower bound that builds matrices with entries in fixed countable set (and in particular with integer entries) doomed to fail after one query.
The proof of Theorem 4 does not provide explicit algorithm. However, the learner knows that the entries of the matrix are in a finite set A C Q an explicit strategy can be easily described. In this case, A of the form fa./r,....,44 ",,//'' with ag Z. and N. Consider a base b= max(a1m)- min(aim)) and consider a query with & (b-1, 6-_, ".bb_,..,,bb" b-k) (the choice for irrelevant here). The learner can deduce the full matrix M from the single observation MTp Of course, this strategy has no practical interest as soon as either A or K is moderately large, since it requires arbitrary precision in the outputs.
Remark 5.
Difficulty of Recovering the Matrix Exactly In the first-order query model, the learner receives 2K numbers every round, so in order to fully determine an arbitrary K K matrix one needs at least K2 (2//(2)) K/2 rounds. It turns out that this bound is not tight, and we may need exactly K rounds in the worst case, because of redundancies between the 2K numbers we observe per round:
Theorem 6. The first-order query complexity over MM 1[) of recovering the full matrix is K.
Intuitively, it is overkill to recover the matrix exactly to output an g-Nash equilibrium. In the next section, when & & 1/K useful information to find an e-equilibrium faster than it takes to reveal the whole matrix.
IKK K (in particular when e = 0), we show that first-order queries do not provide
4
A New Lower Bound on the Query Complexity of Approximate Equilibria
We switch perspective, attempting to make the life of any learner hard. For this, we need to think about responding to queries to keep the learner unwitting.
4.1 Overview and Notation
After time steps, queries Pıæ and qua have been made and the outputs provided to the learner are (( and p(P) Let denote the of matrices with entries in [-1, that consistent with the observations after t time steps by
E, {M Mx 1I) Vs E [t], MT P. -e(0) and Mq. (d²) )

---

we sometimes refer to this as the set of candidate matrices after rounds of observations. We omit the dependence on the sequence of queries (ps, 9,) and outputs (e!") _ to reduce clutter, as it will always be clear from the context.
We say a sequence of matrices Mar is adapted the queries pI.T, 91:r, if it gives consistent outputs to the queries, i.c., if for all s < t < T, M, p. = MJPs and M44a = Maqs; in other words, Mir is adapted if M,+1 & for all t.
Instead of defining directly the answers to the queries, we equivalently build a sequence of adapted matrices. Formally, round t + 1, given & and (pt+1.9(+1), we select matrix M,+1 & and output (2 (41 = (+++1
Let us fix some common technical notation that we use in the proofs, to measure distances in matrix space. For a matrix M E MM (R), and for r, E [1, oo]. we denote the operator norm of M by ||,] = suP>ERK; = / Recall that for y. E TR.K we have Ir,, = || where r' E [1, xo] is such that 1/r 1/r' = 1. In particular [|M][1, max(,j((K] [Ma and
lly=T 1, = ||yll |==|| If F is closed convex set subset of R.K. we denote by p the orthogonal projection of x on F.
Common Structure of the Proofs Both proofs of Theorems 11 and 17 follow the same template:
Assume an e-equilibrium is found after 7 first-order queries.
Find necessary condition on this equilibrium formulated as constraints on the observed losses and the sequence of queries. Precisely, we observe that under some initial assumptions on the game matrix, the all-ones vector 1 needs to lie near the span of the outputs observed by the player, regardless of the queries and outputs.
Ensure that this necessary condition cannot be met by any pair of mixed actions (p. q) by building an appropriate adapted sequence of matrices. In our case, we ensure that the span of the losses of the q-player stays far from the all-ones vector 1.
This proof structure is promising way to derive the exact query complexity of (approximate) Nash equilibria. We use it provide the first non-trivial lower bound for this setting.
The next two sections implement this template to prove query complexity lower bounds for exact E = 0 (Theorem M and approximate > 0 (Theorem 17) equílibria. Detailed proof's are in Appendix D While we could have deduced the final lower bound for exact equilibria directly from the approximate equilibria case, we describe the result separately to ease exposition. Indeed, the bound for the exact case contains the main ideas but is technically simpler.
4.2 Proof: Exact Equilibrium Case
Step I: Common Equilibria are in the Span of Past Queries We start by defining an initial set of candidate matrices with some special properties. These properties are used to ensure that the common cquilibrium is fully mixed, and therefore an equalizing strategy for both players.
Definition 7. A set of matrices Bo C Mx ([) satisfies the assumptions A(0) if
For all M E Bg, all equilibria of M are fully mixed, There exists a matrix M E Bo with non-zero value.
By Lemma 20 (App. D any ball centered at (1/2) with small enough radius satisfies A(0), e.g.,
Bo = =Bi-Ih..
LK - = {MM E Mx (R) M 1 - 6
16K Vi.j E [k]]
1
16K2
The following lemma states that after first-order queries, if at least one matrix in Bo is still candidate matrix, then any common equilibrium to all candidate matrices must lie the span of the queries. Since equilibria of matrices in Bn are fully mixed, and are thus equalizing strategies, this further implies that the all-ones vector must lie in the span of the outputs to the queries.
Lemma 8. Let Bo be set of matrices satisfying A(0). Assume in addition that & r Bo + ø and that & n MM(((-1,)) 1)) f Ø. If there exists common Nash equilibrium (p, q) to all matrices in &. then E Span(pia) and q E Span(qıa).
Corollary 9, Under the assumptions of Lemma there exists a value v o 0 such that
v1 Span 1a n SSSaa ()pa)(eP)))
7

---

Step II: Sequential construction Given Corollary to prove a query complexity lower bound, it suffices build the answers to the queries Рı:t and Q1:t a way that ensures that
the vector never belongs to the span of the observations of (say) the g-player, there is least remaining candidate matrix in Bo, i..., & O Bo Ø
For technical reasons (cf. the assumptions of Lemma 8), we also need to make sure that there is enough space left in &c. We do by keeping a candidate matrix Mr E & n Mxx((-1,1) away from the border of the initial set of candidate matrices (i.e., with entries stricly between -1 and 1).
Lemma 10. Fix time horizon T K/2 1. For any sequence of queries Piat, I1. there exists sequence of matrices MpT in (x((-111))) adapted to PıT: 91.T that defines losses { for which, for any + O,
& Span (g)
Conclusion Combining Lemmas & and 10 against any learning strategy, we have built a sequence of outputs for which there is common equilibrium to all remaining candidate matrices after 'I' rounds, as long as T < (K - 3)/2: this proves the following theorem.
, Theorem 11. The first-order query complexity MM ([-1, 1)) of finding Nash equilibrium
T(0) K/2 1
The next section tackles the lower bound for approximate equilibria. Its proof follows the same template for the exact case, although the technical complexity increases.
4.3 Proof: Approximate Equilibria Case
Step I: Common Equilibria Are Close to the Span of Queries In the following, we say probability distribution over [K] is 6-supported if p(t) for all i. We say a pair of distributions (p. q) is --supported both p and are d-supported. We start by defining a quantitative version of Definition for approximate equilibria. In order to retain the property that losses at e-equilibria stay close to an Isotropic vector, we add a requirement on the support of the equilibria.
Definition 12. A set of matrices B&d C. (x((-1,11) satisfies the assumption A(E,8) 8) if
For all M Be,s, all E-equilibria of M are 6-supported, There exists matrix M E Be,s with non-zero value.
For example, by Corollary 21 the || -ball centered at (1/2) and of radius (1/16) satisfies this condition for any I/ (16K3² and 5 & 1/(2K).
The following proposition is a quantitative version of Lemma for approximate equilibria, which show that any common approximate equilibrium to all matrices in E needs to be close to the span of the queries.
Lemma 13. For e, 0, let B s be set of matrices satisfying A(e, 8), cf. Definition 12 Assume that & n Be,5 + 2, and that the relative interior of & contains a ball of radius Tt measured in ||. 1,0 norm. there exits common E-Nash equilibrium (p. 9) sto all matrices in E,, then
2: lp Projspan(pu.d (p)ll < br,
25
and
||q Projspanig...) (4)ll &
dr.
Corollary 14. Under the assumptions of Lemmal 13 there exists a game matrix M E Be,5 such that the value v E IR of M satisfies || Proj Proispan
(9) (v1)ll < (4KKe)(rr.).
Step I: Construction of Matrices We design adapted sequence of matrices that keeps el away from the span of the observed losses.
Lemma 15. Let B be closed ball in 11, -oor of radius & 1/2 contained in Mx 1]). Fix a time horizon T & K/2 - 1. For any sequence of queries (pt, QeTTT, there exists a sequence of matrices MiT B adapted (pt, qt) that defines losses g49). for which, for any
T+1
| - Proj Spant (10) (1)))
( (c1)|l
> u 8KT2
and such that E, contains ball of radius T 7/2 in its relative interior.

---

The proof relies on decomposition of the squared distance of v to the span of observed losses at time t ++ through a Pythagorean identity. relating it to the span at time t. By carefully choosing the new matrix Mz+1 as a function of the query pt-1, 0t+1, we manage to ensure that the squared distance decreases only by a constant factor.
The radius of the ball inside & stays constant at r/2, even though &n gets smaller as t increases. This is made possible by choosing M, very close to M,- (roughly at a distance of r measured in || 1,), effectively ensuring that Mt stays far from the boundary of Mx (x((-1,1))
Remark 16.
Step III: Conclusion We now combine Corollary 14 and Lemma t5 obtain lower bound on the best achievable gap after T rounds, which directly translates to a query complexity lower bound.
Theorem 17. In the first-order query model on MM ([-11,11)))) 1, 1)), for any algorithm the worst-case gap after T & (K - -3)/2 22 time steps is at least
T+1
E 2 211/235/2T)
Therefore, the query complexity of finding e-equiliirium for any = & 1/(e21 is at least (2
T(s)
log (211/2 + log( - (og()o)(2 1)
(K/2-1))
4.4 Potential Improvement and Discussion
There is still a wide disparity between upper and lower bounds on first-order query complexity. The lower bound Theorem 17 is most probably not tight, so let us discuss potential ways to improve it.
We believe the most promising approach for improvement is find different proxy for the gap. Our proof uses the distance to the span of the losses ||o1 - (ro)) 1| for > (2K),, which is convenient because it is a distance, but we need to introduce a strong restriction on the set of candidate matrices B5,5 5 to be able to relate it to the gap, namely the restriction to ball around 1 of radius O(1/K?), In order to make significant progress is therefore essential to enlarge the class of candidate matrices significantly compared to B,, and therefore to modify the proxy for the gap.
5 Discussion: Future Work and Conclusion
We study the first-order query complexity of computing approximate Nash equilibria for two-player zero-sum matrix games. We review upper bounds coming from online learning, and discuss existing lower bounds for related problems including alternative query models. Taking stock, we arrive the surprising state of affairs that for this fundamental problem no lower bounds are known. We then offer some explanation for this current state of affairs: the first-order query model is powerful enough to identify any matrix from a fixed countable set in a single query; this rules out many techniques. We then turn to lower bounds. We design an adaptive adversary that answers incoming learner queries in such a way that the remaining consistent matrices do not share a common Nash equilibrium for as long as possible. Our approach based on quantity serving as a "potential function": namely the distance of the all-ones vector to the span of the observations. We discuss in detail the result, future scope and limits of our proposed technique.
As can be seen in Figure we are still far from matching lower and upper bounds. The most intriguing possibility for resolution would be if it were turn that the upper bounds (i.e. algorithms) are improvable. Current upper bounds come from online learning regret bounds, with algorithms falling in the category of uncoupled dynamics. We would love to know if these algorithm templates are in fact optimal for query complexity.
To cycle back to our motivation of computing saddle points in general, future work could attempt to extend our lower bound technique to different constraint sets, to functions possibly exhibiting curvature, and to instance-dee dependent rates. Another direction would be generalize multi-player games and investigate the query complexity of weaker solution concepts.
Limitations and Broader Impact The main limit of this work is that it only partially resolves the first-order query complexity of approximaae NE in finite games, calling for tighter analysis. Regarding broader impact, results are mainly theoretical and do not entail direct socictal consequences.

---

Acknowledgments and Disclosure of Funding
Sachs and Van Erven were supported by the Netherlands Organization for Scientific Research Part of the research was performed while Hadiji was
(NWO) under grant number VI. the University of Amsterdam. During that time he was supported by the same grant number VI. Vidi. 192.095.
References
[1] Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient-bact based methods for a whole spectrum of differentiable games. In International conference on artificial intelligence and statistics, pages 2863-2873. PMLR, 2020.
[2] Yakov Babichenko. Query complexity approximate Nash equilibria. Journal of the ACM (JACM), 63(4):1-24 2016.
[3] George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13 (1)377, 1951.
[4] Yang Cai, Argyris Oikonomou, and Weigiang Zheng. Tight last-iterate convergence of the extragradient method for constrained monotone variational inequalities. arXiv preprint arXiv:2204.0922 2022.
[5] Nicolo Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[6] Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 18:90999-8,99 2020.
[7] Xi Chen, Xiaotie Deng, and Shang-Hus Teng. Computing Nash equilibria: Approximation and smoothed complexity. Electron. Colloquium Comput. Complex., 2006.
[8] Xi Chen, Xiaotie Deng, and Shang-Hus Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3), may 2009.
[9] Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing Nash equilibrium. SIAM J. Comput., 39: 39:195-259, 02 2009.
[10] Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitrion. A note on approximate Nash equilibria. Theoretical Computer Science,
1581-5588, 2009.
[11] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Proceedings of the tventy-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235-254. SIAM, 2011.
[12] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. Games and Economic Behavior, 92:327-348, 2015.
[13] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, volume 34, pages 27604-27616, 2021.
[14] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. Proceedings of the 53dd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478. 2021.
[15] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wad Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret lcarning dynamics for general convex games. Advances in Neural Information Processing Systems, 35:39076-39089, 2022.
[16] John Fearnley, Martin Gairing, Paul Goldberg, and Rahul Savani. Learning equilibria of games via payoff queries. Journal of Machine Learning Research, 16:1305-1344, 2015.
10

---

[17] Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-)):79-103, 1999.
[18] Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-wolfe algorithms for saddle point problems. In Artificial Intelligence and Statistics, pages 362-371. PMLR, 2017.
[19] Andrew Gilpin, Javier Peña, and Thomas Sandholm. First-order algorithm with (ln(L//)) convergence for e-equilibrium in two-person zero-sum games. In Proceedings of the 23rd National Conference Artificial Intelligence, AAAL08, pages 75-82, 2008.
[20] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems, 2020.
[21] Sergiu Hart and Noam Nisan. The query complexity of correlated equilibria. Games and Economic Behavior, 108:401-410, 2018.
[22] Elad Hazan and Tomer Koren. The computational power of optimization in online learning, In Proceedings of the Roght-Eighth Annual ACM Symposium on Theory of Computing. STOC 16, pages 128-143 2016.
[23] Yu-Guan Hsieh, Kimon Antonakopoulos, and P. Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In Anmual Conference Computational Learning Theory, 2021.
[24] Adam Ibrahim, Waiss Azizian, Gauthier Gidel, and Ioannis Mitliagkas. Linear lower bounds and conditioning of differentiable games. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, volume 119, pages 4583 4593. PMLR, 2020.
[25] Albert Xin Jiang and Kevin Leyton-Brown. Polynomial-time computation of exact correlated equilibrium in compact games. In Proceedings of the 12th ACM conference on Electronic commerce, pages 119-126, 2011.
[26] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[27] Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Annual Conference Computational Learning Theoryy 2020.
[28] Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o( ((1/)) for optimistic gradient and extragradient methods in smooth convex-concut saddle point problems. SIAM Journal Optimization, (0(4):3230-3255 2020.
[29] Arkadi S Nemirovsky. On optimality of Krylov's information when solving linear operator equations. Journal of Complexity, 7(2):121-130, 1991.
[30] Arkadi S Nemirovsky. Information-based complexity of linear operator equations. Journal of Complexity, 8(2):153-175, 1992.
[31] Yurii Nesterov. Introductory lectures on convex optimization a basic course. In Applied Optimization, 2014.
[32] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50 69, 2018. Special Issue on ALT 2015.
[33] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
[34] Christos Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi- player games. Journal of the ACM (JACM), 55(3):1-29, 2008.
[35] Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near- optimal uncoupled online learning via clairvoyant multiplicative weights update, Advances in Neural Information Processing Systems, 15:222558-22699 2022.

---

[36] Leonid Denisovich Popov. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
[37] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[38] Julia Robinson. An iterative method of solving game. Annals mathematics, pages 296-301,
1951.
[39] Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games and Economic Behavior, 59(1):187-208 2007.
[40] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[41] Chen-Yu Yu Wei, Chung-Wa Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate con- vergence in constrained saddle-point optimization. In International Conference on Learning Representations, 2020.
[42] Tong Yang, Michael Jordan, and Tatjana Chavdarova. Solving constrained variational inequal- ities via an interior point method. arXiv preprint arXiv:2206. 10575, 2022.
[43] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1-2)9011-955 2022.
12

---

A Proofs of Lemmas 8 and I0
Proof of Lemma | Since p. p.q is equilibrium least one matrix in Bo B& is fully supported: in particular is an equalizing strategy for any M E & and MT = uM1 for some number UM E IR. Furthermore, the value UM is actually independent of M E & since, UM (M p. qı)
(p, p(P))- Therefore, for any M, M' E &t, we have (M - Tp' = 0. Let us now define p = p - Projspan(pL..) (p), and consider the direction pud E (Mx for some arbitrary non-zero vector Uy orthogonal to Q1..... Qt- Fix some matrix M & ((- 1)); non-empty set by assumption. Then for a E R small enough, the matrix M' = M ope, is still in &,, since M is not on its border (all entries are away from { {-1, 1).. Therefore.
(M M') ((p, - u
implying that |il| 0, i.e. that p E Span(pr:); similar reasoning shows that q E Span(gr:))
Proof of Lemma 10 We build the sequence M incrementally by moving at step t 1 in directions chosen function of the new queries 1++11 and qt-1 ensuring by induction that 1 & (pan( Initialize the sequence at Mn = (1/2) Ix. Now for > 0, let us assume that we have correctly built MI.,, inducing losses such that 1 $ Span(4].) ), and let define Mc+1. (Note that the initialization of the induction is valid with the convention that & {0} = Span(Ø).)
If P1+1 is in the span of P1:t. then set M4+1 = M, and the induction holds, since the span of the losses is left unchanged. Otherwise set M,+1 = M, + fe F' ,here pc+1 = P1+1
and to MJ Pt+1; the existence of such u, is guaranteed since 2t + 2 < K, ensuring that there is least one dimension orthogonal to those 2t + 2 vector. By choosing the norm of un to be small enough, we can make sure that M,+1 E Mx((-1, Then, ( M|+1P++1 MJ P++ + Us and is not in the span of g(9) 11(++41)* such that
Projspan(ol.) (pt+1), and ue is non-zero vector orthogonal to the vectors Q1:t, to e/
Indeed, assume by contradiction that there exists real numbers 01:(++1)
ag ((0) a441
then 0++ >> 0 since by induction a Span (1)))((19)) the equation above, we obtain 0 = (u,, 1) = (ue, ac+1 ((+1)))))))))))))))))))))))))) = me<lllell' leading to a contradiction. Therefore 1 & (pan(? at all times < T.
(1)) Then, taking dot products with u, on both sides of
B Details for Upper bounds
B.1
Iistance-Dependeee Query Complexity
The following example shows that the bounds in 19 can be vacuous for our setting. Since, noted by the authors, Theorem by [41 equivalent to the results in [19] the following example is only with respect to the latter.
Example 18. For this example, we use the notation from [19]. Consider the game matrix M- = IK- Observe that M has unique Nash-equilibrimm, hence, by considering p = π and q 5, it can be seen that 8(M) is at most / - R 1. The bound is defined with respect to the condition number xe(M) V Amax MTM (MTM/5(M) where >maax (M) denotes the largest eigenvalue of M. Hence, for example, s(M) is at least of the order of K, which makes bound of R(M) log e for this specific example vacuous. Note that for other game matrices, the results give valuable insights into guarantees beyond the worst-case.
B.2 Constant Queries for Games from Finite Alphabet
Proof. Let F be the smallest subfield of that contains A, then F is countable and, can be seen vector space over F. Recall that family of real numbers (I1...., Fn)
as
13

---

(each seen as vector over the field F) is linearly independent if for any Ai..... An E F we have A, O.
21 +... + S, = 0 if and only A
We claim that if player, say the g-player, queries an action such that the components (1,... qK form linearly independent family, then they can compute the whole matrix M with just observation.
Indeed, if M, M' E .Mx(A), yield the same output after one query, then for any i E [K]]
(M, - Mi =
Therefore, by the independence of (% [))))))))))))))))))))) this implies that Ma, = Mi for any (i.j). In other words, no two different matrices can give the same output after one query under q-
We are now left to show that there exists a play (gn..... gx) with coordinates forming a linearly independent family. We prove this using the probabilistic method. Consider sequence of random variables (U,,.., Ux) i.i.d. and uniformly distributed over [0. 1]. Then with probability 1, the U; independent over F. Indeed, we can upper bound the probability that they are dependent by union bound and use of the tower rule as
P P E [
s.t.
U E Span F (U,1i
P E Span, (U, + i)]
E [ Span o (U,li * i) (U, 1 # =0
The last equality holds because, for any [K] conditionally on {U, j * i). the span of (U, j & i} is countable set, therefore the probability that U, belongs to that set is null. This concludes the proof.
C First-Order Query Complexity of Recovering the Game Matrix
Proof of Theorem 6 Clearly, we can fully reconstruct M from the queries Pt qr e, for 1 1...., K, where e, denotes the standard basis vector direction L. turns out that this optimal.
To show this, note that each query (p. provides us with constraints
n TTM- a,
Mq= b,
for some loss vectors and These may equivalently be expressed as linear constraints in the Hilbert space of matrices A E R with inner product (A, B) Tr( (T(AAB))
(MT, "TTT) = ai
(i i= I=)
(MT, (MT,qe5) = bj
1j= K).
Among these 2K constraints on M, there is (at least) one redundant constraint, because there always exist numbers ......, ......,,uu Ax and ...... YK,, least one of which is nonzero, such that
K
Σ
Neep Σ 75qe 0.
Specifically, this holds for X; q: and 7 Py. It follows that query (pt, q:) in round will provide at most 2(K - t) + new constraints on top of the queries from rounds 1...., - 1. To see this, note that Pt will have at least one constraint in common with g1...., 4t-1 and qi will have at least one constraint in common with PI..... Pt. so the total number of new constraints is at most 1) / = 2(K 1.
n4 : 2K
We now provide the following scenario in which M cannot be fully determined by strictly less than K queries. In rounds t ,,...,K K 1, the answer to queries (Pt, 9:) is always the two loss vectors p(p) g 1 1, which are compatible with the possibility that M equals 2 $11, i.e. the matrix with all entries equal to 1/2. We will show by induction that the dimension of the null-space (i.c. the
14

---

number of unconstrained dimensions of M) of all constraints up to round t is at least (K - -t². This true for for 1. + 1 it is at least
because the domain of M has K² dimensions, and, whenever true for t. then
(K-13 -K) M+++1
-
Thus, after K - rounds, there remains at least one direction V E R xx in this null space with + 0. This means that the learner cannot distinguish the case M 1 from the case M = 11 + 2 maxi, VV,ll thus
queries are not sufficient to fully determine M.
D Proofs and Technical Results for Section
D.1 Approximate Equilibria
D.1.1 Proofs of Main Results
Proof of Corollary 14, (p.q) is a common e-NE all matrices in & then we have for any game matrix M E &
MT p) E Span (c(3)
and therefore for any v >
|| ||ol-Proispan (ef)) (x1)ll & |1l-- (p--) < | 1 p1 & [|1lMMTp|+V/]]
Now as 8 > 0, any M E Bg,s has unique Nash equilibrium p":"". which is fully supported. "it"t.a
Therefore, the value of A1 is v = pMq" as g"' is a an equalizing strategy. Now, using (I in the proof of Lemma 13 which is valid for any matrix that admits p, q as e-NE,
| - MTpll < &vKl KKlul pl < VKe
8
Proof of Lemma 13 First note that p and q are d-supported, as (p. q) is an e-equilibrium of least one matrix in & n ((s,)). For M E E,, pick any j E arg (MnT)e As (p. g) is an E-equilibrium for M,
K
(1-)())) max (MTp), + q(5)) jE(K)
min (MTp); >
Σ
(MM(M))) > max (MTp)) - =,, _E(K]
JE(K]
and therefore, dividing by q(i*)= > 8,
max (MT p); jE(K]
min (MTp); jE[K]
(I)
q(i*)
8
Hence, as min] (MTp); < Mg: & max (MTp),.
|M (D Mqi
2o $
8.
Since T Mqq pT((P) has the same value for any M E,, we apply this inequality for any pair of matrices M, M E & to deduce that
(M 1 M')
Let us now instantiate this identity with some well-chosen M and M'. Let E RK be vector orthogonal to 91...., 9t. such that ||u]] = (such a exists as long as ......, St do not span the whole of I kg. Next consider M and M' in E, such that
Tt
M M M'
PuT.
1r
Such M and M' guaranteed exist in &, |I
M'Il rz. Then, applying 22) obtain
2c
(I M')
T1
|
rel/pl22
8
|
from which the claim follows. The same reasoning applies to obtain the bound on q.
15

---

Proof of Lemma 75
Denote by II, the projection on the span of the observed losses ( 11 for the
q-player at time step t. We build the sequence (Mr) incrementally by moving at step t+11 in directions chosen function of the new queries P++1 and qt-1-
We initialize the sequence at Mo the center of B. Now for > O, Pe+1 is in the span of Pi:ts then set M1+1 M,, otherwise set
M+1 = M2 + P++1
P
where P++1 = Pt+1 - Projspan(pp.. (p++1), and is non-zero vector orthogonal to the vectors Qua e(g) to 1, and to M, Pt+1; the existence of such u, is guaranteed since the only condition is that it is orthogonal to + K vectors. (Note that ur does not depend on the value v.) We set the norm of in at a later stage of the proof. Then,
to
M,+2Pt+ Pt+1 de.
Then for any v E R. the squared distance from the vector el to the space Span (g) can be decomposed thanks to the Pythagorean equality, the squared distance to the previous span minus the squared norm of the projection on the new orthogonal direction p(1) II, (e
| 11+11 (1 = || [1(v1)12 (01, M7 + U4 II, (M, pu+1 + u))
MM P:+1 + ut 11, (M, p++1 + uz)
DD
Observe that for any vectors a, b, we have (a (a),,, b) (a ll b (b)) = (a. b- II, (b)). as II, is an orthogonal projection on a linear subspace. Using this identity, as well as the orthogonality conditions used to define (precisely, that II, (u,) = O, and that u, is orthogonal to M, P++1 and TI, (M, Pc+1)) )), we obtain after applying Cauchy-Schwand
(u1 [1,1),, P1+1 u,)²
D.
| P.+1 + u4 [M, Pi+ + uz)l
(v1 [1,(v1), M.Ppt1 Pt+1 + un)
| + [IM. pc+1 I1, 1
(r1 (v1),, M7Tp111 (MM.] 2)+
||u + [| P (M, p(+1)l12
|IM, PM IM,
< ||c1 (.1))
[M Pt+1 - [I, 11+ + 1
|| 1
< |1 (11)]
IM ||w.|1?
We also used the fact that projections reduce the norm, and the function + x/(2 + 1) is increasing on (0, +oo) to obtain the final inequality.
Using this bound on D, to lower bound the distance to the span, we obtain
[[ - 11+2) > [|(Ix 11)o113
+ ||ul|//|| p2+1
We are now left to choose the norm of uy; the objective is to make it as big as possible under the constraint that the sequence (Me) stays B. We set the norm of uz to be constant multiple of ||M, Pc+ i.c.
|| = Va petall For small enough, can ensure that the whole sequence (M,) stays in the ball B,
1pet1l Iloo
1 u
|M - Molli.0
10.+1122 1| II 11.00.000
|uoloc =
p
|o+1 1
Ugg ||
Mrpe+1ll
& Vavkt,
1p++1
16

---

where we used || < || ||22||1 & V=I| and M, PL+1 = M. Pt+1 since Mt Et. Therefore by taking, a = (r/2)² (r/2)//KTT>) we ensure that M, E B as B contains a ball of radius centered Mg. Furthermore. this choice ensures that & contains the ball of radius r/2 centered Mt in its relative interior as for any matrix U with norm less than r/2, we have | + U Moll <
||M,; Moll ||U|| & r/2, so M++UC E C MM M 1J).
Plugging back the value of a into 3]. we get
[I 11 lI(Tx 1
I[(TK 11)
1+a
After 7' time steps, this implies that for any > O.
1l4x - 11) > l1(k - Ho)ou
aa (1) = |1111111(
?
T+1
8K72
This is the claimed result.
11.. Proof of Theorem 17 Define Be, - (R, 1ok ). which is ball of radius r 1/(16K3)
Given an algorithm, consider the sequence matrices MiT generated by Lemma 15 applied with B B know in particular that Mr Be,s, B NE # Ø.
Assume now that the algorithm outputs a common E-cquilibrium to all matrices in Er. The as- sumptions of Corollary [14] hold, instantiated with Be, and r; = 1/(32K²). Therefore there exists M E Be,,, with value such that
4vKe
|el Proj (p)n(e (v1)] &
8r,
On the other hand, by Lemma 13 also instantiated with B = Be,s, we know that
22
(T-1)/2
|| - Proj Span (elo) (e1)ll 3 vVK K
8KT2
This implies that
vôr: p2
(T+1)/2
8K72
Finally, since is the value of matrix M Be,s.
U min max pd Mq 2 min max pīg
Kr > 2K 16K² 7 4K'
PEAx AEAK
PEAK yEAR 2
We conclude by replacing the constants by their values, 1/(2K) and rt r/2 1/(32
By Lemma 19 in Appendix D we deduce that for (2E) < 1/ 2 KTb,
log 2 K*t)
T T+12
(32
log( 1ogg211= k1s))
D.1.2 Technical Lemmas
Lemma 19. For any a, b, x > 0, for any & & a/c,
log(a/e)
if a
then x log(b (ogllll)a))))))))) (a/s))
Proof of Lemma 19 Assume
> a (1/(bx))² e- -olog(bx)
then
(e/a)² > e -bs log()z)
thus, applying logarithms to both sides,
b blog(e/a) > -bx log br.
17

---

Reformulate as, since a 3
bæ log bx: > blog(a/s) > 0.
We now apply Lambert's Wo function, which is increasing on its main branch [-1/e, too), and use standard lower bound on Wo to obtain
log bæ > Wo(-blog(e/ > log((blog(e]]) - log loggloolo((e////
thus
br 3
which is the claimed bound.
Lemma 20. Let and real numbers, let M E Mr (R) be matrix such that
Ma sIK| &
[]j[[K]
Then for any e-Nash equilibrium (p,9) of M we have any i,j E [K] 2(a + s)(K - 1)
min(p(1), a()) > K
Proof.
Let (p, 4) denote an e-NE of M. Then
max (MT p)5
min (Mq): & 25.
(4)
]E[K]
iE[K]
Now for any j E [K]. since M is close to sIK,
(MTp); 2 s sp())
thus, using the fact that p is a probability vector,
8
max
(M
MTp),
max p(j)
2
(5)
JE[K]
JE[K]
K
Similarly,
min (Ma); < min ((i) + iE[K]
(6)
EE[K]
Combining the equations
and above, have
min g()) + a t K
K
i.e., after rearranging,
+8)
min ((t) > kE(K]
K
Similarly
max p(J) < max (MTp), JE(K]
1
a
< min q(i) + a a
<
1
+
2(a +)
8 jE[K]
K
8
Therefore
K 1
2(a +
min p(k) > 1 (K- max (()x m(ax) jE(K]
(K - 1)
jE(K]
K
2(xx +
(K
K
Completing the proof.
Corollary 21. For any 1/(16K2), for any game matrix M such that
max
M
2 IK
< 16K2
(.jE[K]
all e-NE (p. q) of M satisfy for all i.j
[K]
min (p(1), 9(1))
> 2K
Corollary 22. For any game matrix M such that
max
MaJ
J < 16K2
all exact Nash equilibria (p, q) are fully supported.
18


Reviews:
[{"review_id": "3CesKFEh6o", "reviewer": "Reviewer_VSPH", "summary": "This paper focuses on the query complexity of learning (approximate) Nash equilibria in zero-sum matrix games. The authors provide lower bounds on the query complexity for exact and approximate equilibria. They also show that if the game matrix has entries in a known countable set, the learner can recover the full matrix in one single first-order query. The paper discusses related work on lower and upper bounds for similar problems. The authors present upper bounds for the query complexity of finding approximate equilibria and introduce two strategies for obtaining equilibria with large approximation values. They also propose a potential improvement to the lower bounds by finding a different proxy for the gap. The paper includes proofs, examples, and explanations to support the theorems and corollaries related to the query complexity of learning game matrices. Overall, the paper contributes to the understanding of the query complexity of learning Nash equilibria in matrix games and provides insights into the lower and upper bounds for this problem.", "questions": "Please refer to weaknesses.", "limitations": "The author has clearly acknowledged the limitations of their work, specifically that it only partially resolves the first-order query complexity of approximate Nash Equilibria in finite games and further analysis is needed for tighter results. In terms of broader impact, the results are mainly theoretical and do not have direct societal consequences.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents original and valuable contributions to the understanding of the query complexity of learning Nash equilibria in matrix games. It introduces new results and insights, providing lower bounds on the query complexity for both exact and approximate equilibria, and proposing a potential improvement to the lower bounds. The quality of the paper is high, with rigorous proofs, clear examples, and a comprehensive discussion of related work. The paper is also well-structured and clearly written, making it accessible to readers. In terms of significance, the paper’s contributions can inform the development of more efficient algorithms for learning Nash equilibria in matrix games, with practical applications in various domains. Overall, the paper is a valuable addition to the existing literature in this field.", "weaknesses": "The paper provides valuable insights into the query complexity of learning Nash equilibria in matrix games. However, the novelty of the results is somewhat limited as they largely build upon existing literature, such as the connection between regret and equilibria.\n\nThe paper partially resolves the first-order query complexity of approximate Nash Equilibria in finite games, but further analysis is needed for tighter results. The paper’s focus is primarily on theoretical analysis and proofs, without experimental evaluation, and the results are mainly theoretical with no direct societal consequences.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer VSPH for the helpful remarks and comments!\n\n**Limited novelty due to heavily building on existing results:**\nWe did our best to thoroughly present the state of the problem and the related literature, and to properly credit the ideas we build upon. This, we believe, highlights the novelty of our techniques.\n\nIn particular, for our main results (Section 4) we develop a new lower bound proof technique that does not build on previously known methods or results. This novel technique yields the first non-trivial lower bound for saddle-point optimization, and might be of interest on its own (which was appreciated by reviewers Wvc4 and nqee). \n\nPlease also note that all our main results, e.g., Theorems 4, 6 and 17,\nare not specific to equilibrium guarantees obtained via regret bounds, and apply in a much more general context. All first-order methods must satisfy the lower bounds. \n\n**Lack of experiments:**\nWe did not find any numerical experiments that would helpfully illustrate the main point of the paper, which is our new lower bound technique. \n"}, {"review_id": "xYVVRcM5QY", "reviewer": "Reviewer_3esb", "summary": "This paper delves into the complexities associated with identifying a mixed Nash equilibrium within the context of a zero-sum game. Specifically, it scrutinizes situations where the algorithm does not directly observe the payoff matrix. Instead, it learns about it by querying its product with either a column vector or row vector. The challenge of computing Nash equilibria in this model has been extensively studied, however, prior to this study, little was known about lower boundaries.\n\nThe study's central findings include a K-2 query lower bound for calculating an exact equilibrium and a lower bound that exceeds the constant when 1/epsilon is super-polynomial in K for calculating an epsilon-approximate equilibrium. The methodology for deriving these lower bounds involves the identification of an adversary capable of answering an arbitrary series of first-order queries. This adversary ensures that the all-ones vector remains considerably distanced from the linear span of query responses for the maximum possible steps, while concurrently guaranteeing that the set of matrices congruent with query responses remains non-empty.\n\nEarly on, the paper also introduces a minor result highlighting the complexities inherent in proving lower boundaries within this model. If provided with a countable set of numbers known to encompass all the entries of the payoff matrix, a single first-order query is sufficient to reconstruct these entries and consequently, identify a mixed equilibrium. Although this result is simple, its proof capitalizes on the assumption that responses to first-order queries comprise vectors of infinite-precision real numbers. While this algorithm lacks practicality (an aspect openly acknowledged in the paper), its existence accentuates the challenge associated with establishing lower bounds in a model that facilitates such powerful queries.", "questions": "This paper leaves me in a state of indecision, and being the more positive reviewer, this doesn't appear to be a promising sign for the paper. The rather tepid scores possibly reflect my collective sentiment towards the main result, which is the lower bound. It appears to be quantitatively modest, and we're uncertain about the significance of obtaining upper/lower bounds in this exact query model that permits the use of \"funny bit tricks\". It's unclear how vital these aspects are in terms of contributing to the field, and this ambiguity might be affecting our overall reception of the paper.\n\nLet me give some recommendations about improving the clarity of your theoretical paper:\n\n1. **Abstract and Introduction**: Ensure that these sections provide a clear and concise overview of the key ideas and contributions of the paper. Avoid using overly technical terms and jargon in these sections, as many readers will try to get an understanding of your work from these parts before diving into the main content. \n\n2. **Theoretical Concepts**: Each theoretical concept, model or algorithm that you introduce should be clearly defined and explained. When introducing a new concept, briefly review its background and the relevant literature. Also, explicitly state the assumptions you are making.\n\n3. **Equations and Theorems**: Always explain the intuition and significance behind every equation or theorem before diving into rigorous mathematical proofs. Make sure to annotate your equations adequately and define all terms and variables used. Whenever possible, accompany your mathematical results with visualizations or intuitive examples.\n\nThis crucially misses in the main part of your results\n\n4. **Results Section**: In the results section, don't just state your results, but also explain their implications. Make sure to clearly relate your results back to the problems and questions you outlined in the introduction. \n\n5. **Language and Flow**: Aim for a clear, concise, and precise language. Avoid long and convoluted sentences. Make sure each section and subsection follows logically from the previous ones, helping to guide the reader through your narrative.\n\n6. **Discussion and Conclusion**: Use these sections to clearly summarize your contributions and their implications. Discuss how your results fit into the bigger picture of your research field. \n\n7. **Appendix**: Put additional details, proofs, and technicalities that are not essential for understanding the main ideas of your paper in the appendix. This way, you can keep the main text more readable without losing any necessary detail.\n\nAdd explanatory paragraphs after theorems\n\n\n\nI strongly believe that the paper is not  submitted in the correct conference venue.", "limitations": "n/a", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "n/a", "weaknesses": "The paper has some discernible weaknesses which impact its overall effectiveness and value. They are listed as follows:\n\n1. Lack of Clarity: The exposition in the paper lacks clarity and coherence which makes it difficult to follow the arguments and understand the results. Better structuring and clear, concise language would greatly improve the readability and accessibility of the paper. \n\n2. Absence of Experiments: There are no empirical evaluations or experiments provided to support the theoretical results. Experimental results are key in illustrating the practical applications and feasibility of the proposed methods. Therefore, including such results is crucial for providing a comprehensive understanding of the paper's contributions.\n\n3. Uncertain Significance of the Results: While the results of the paper are novel, their actual importance and impact on the field are uncertain. The paper would greatly benefit from a discussion explaining the broader implications of the results, their potential applications, and how they advance the current state of knowledge in the field. Without such context, it is hard to assess the true significance of the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank Reviewer 3esb for the remarks and comments!\nWe kindly ask Reviewer 3esb to read the other reviewers' feedback regarding the concerns about the clarity of our paper. In particular, please note that all other reviewers did specifically mention the clarity and soundness of our paper as a strength. However, we are happy to clarify during the discussion phase if the reviewer can point us to any specific detail that was unclear.\n\n**Lack of experiments:**\nAs our paper is theoretical, we believe that experiments should be made only if they bring value by illustrating the points made. We did not find any numerical experiments that would helpfully accompany the main message of the paper, which is our new lower bound technique. \n\n**Significance of the results:** Recent years have witnessed a rising interest in saddle-point optimization, which is at the heart of practically impactful fields (e.g., GANs, Robust Optimization, Market Design). On many aspects, the theory of saddle-point optimization parallels that of minimization. For minimization problems, we have a relatively good theoretical understanding due to (matching) upper and lower bounds (under some assumptions). However, we lack these in the saddle-point case, in particular, little is known about lower bounds. Thus, we have no confirmation that our upper bounds and the corresponding algorithms are optimal. We are making a significant (as e.g. reviewer Wvc4 noted) first step towards a lower bound.  \n\n**General advice on theoretical papers and lack of intuitive explanation in main part:** \nWe thank the reviewer for the comments.\nHowever, please note that we are familiar with this kind of advice and\nthat your recommendations are also up to subjective preferences. In\nparticular, we do not agree that in a rigorous mathematical proof that\nis primarily written for experts, every mathematical equation must be explained. Adding intuition after every mathematical expression might make it accessible for readers who are not familiar with rigorous mathematics, but dilute the focus on the rigorous argument. Therefore, we opt for a compromise: as you can see we added a very intuitive and high-level explanation of our proof structure at the beginning of the theoretical part, but kept the focus of the proof on pure math. Please note that this style was very accessible to all other reviewers. \nHowever, if the reviewer could point us to specific examples which were unclear and not intuitively accessible to the reviewer, we are happy to clarify during the rebuttal phase. \n\n**General advice on theoretical papers and undefined mathematical terms in main part:** Since the reviewer is claiming that there are undefined mathematical terms in our main part, please give more details. Specifically, we kindly ask the reviewer to point out undefined variables and mathematical terms. \n"}, {"review_id": "DmaF9Vg2Sc", "reviewer": "Reviewer_nqee", "summary": "Define the gap of a two player zero sum game with payoff matrix M and mixed strategies p and q as: \ngap(M,p,q):=max_j (M^Tp)_j - min_i(Mq)_i\nAn equilibrium is called \\eps approximate if the gap is at most 2\\eps. An important question is to compute the approximate Nash equilibrium by observing the gradients of the objectives in a sequential manner. Of course the number of observations / queries needs to be optimized. Rakhlin and Sridharan showed that O(\\ln K/\\eps^2) queries suffice for K X K matrix games. The authors here improve their bound to O(\\ln K/\\eps) - which is optimal - for small \\eps (\\eps < 1/K^4). They also show a lower bound that rules out certain algorithms for improving the upper bound to match the lower bound for all \\eps.\n\n", "questions": "- How robust are your techniques/bounds when the observations are noisy? Often we don't have access to precise gradients.", "limitations": "Yes, they have been presented clearly.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Learning the \\eps approximate Nash equilibrium is an interesting and important open problem in its own right, not to mention several applications.\n-  The techniques in the paper are interesting by themselves.", "weaknesses": "- The actual result is fairly technical and may not be of broad interest since the improvement is marginal (only for \\eps < 1/K^4).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer nqee for the helpful remarks and the interesting question!\n\n\n**'the actual result is fairly technical and may not be of broad interest since the improvement is marginal'** We agree with the reviewer that our results are quite technical and do not fully characterize the rates of saddle-point optimization yet. However, our new technique provides the first significant step towards the full picture, and we believe it could be of interest on its own.  \n\n**'How robust are your techniques/bounds when the observations are noisy? Often we don't have access to precise gradients.'**\n\nThe reviewer asks an important and interesting question. We thought about this question before and decided to exclusively focus on the deterministic case with precise feedback for the following reasons: (1) We expect that adding enough noise would significantly alter the nature of the learning problem: statistical lower bounds would force us to cover the matrix repeatedly with queries to ensure concentration. (2) Although we agree with the reviewer that noisy feedback is of high practical relevance, we consider the exact feedback model to be a more appropriate model to study and introduce a new proof technique. We believe that whenever the deterministic problem is well understood, a very interesting next step is to combine our technique with statistical lower bounds to obtain lower bounds in the model the reviewer suggests. \n"}, {"review_id": "QvvMbXbS5J", "reviewer": "Reviewer_EExk", "summary": "This paper studies the query complexity lower bound of first-order methods for finding exact and approximate Nash equilibria in two-player zero-sum games. It is first established that if the matrix entries come from a fixed countable set, one query suffices to reconstruct the full matrix and hence to compute the exact Nash equilibrium. This rules out most existing lower bound constructions as they use rational or otherwise countable matrix entries. A new approach is then used to establish an $\\Omega(K)$ lower bound for finding the exact Nash and $\\tilde{\\Omega}(\\log 1/K\\epsilon)$ lower bound for finding an $\\epsilon$-approximate Nash (for sufficiently small $\\epsilon$), where $K$ is the number of actions.", "questions": "Lines 287 and 322: a common Nash equilibrium for all matrices in $\\varepsilon_t$ may not exist, right? Does the statement here mean that \"suppose that a common Nash equilibrium exist\"?", "limitations": "This work is mainly theoretical and does not entail direct societal consequences", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper studies a fundamental yet perhaps overlooked problem in game theory; as mentioned by the authors, it is indeed surprising that none of the established lower bounds apply to this setting. To the best of my knowledge, the results obtained in this paper are indeed the first non-trivial lower bounds for noiseless first-order methods in two-player zero-sum games.\n- The paper is well-written and offers a good explanation (Theorem 4) why it is non-straightforward to adapt existing constructions to two-player zero-sum games.\n", "weaknesses": "- The current lower bound rate is still quite far from the existing upper bound in terms of the dependence on $\\epsilon$. \n\nTypos:\nLine 16: Although not exactly a typo, the submodular optimization problem is never mentioned in the main text.\nLine 59: \"build build\"\nLine 519: the first term should be $\\lambda_1x_1$ instead. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer EExk for the helpful remarks and kind comments! We will fix the typos!\n\n**The current lower bound rate is still quite far from the existing upper bound** See our answer to 'Reviewer neqq': \nWe agree that our results are quite technical and do not fully\ncharacterize the rates of saddle-point optimization yet. However, our\nnew technique provides the first significant step towards the full\npicture, and we believe it to be of interest. \n\n**Does the statement here mean that ``suppose that a common Nash equilibrium exist\"?** Yes, we are assuming existence here. This does not affect the rest of the paper in any way since we were implicitly using the correct version elsewhere. We thank the reviewer for spotting this and we will rectify the statement in the final version. "}, {"review_id": "l6lYMyRyxl", "reviewer": "Reviewer_Wvc4", "summary": "This paper investigates the first-order query complexity of two-player zero-sum games. More precisely, given a bi-matrix zero-sum game $(A,-A^\\top)$ (with $A \\in \\mathbb{R}^{k\\times k}$) a first-order query is a set of strategies $(x,y)$. The answer to such a query is the set of vectors $(A y, -A^\\top x)$ respectively denoting the payoff vectors of the row (x) and the column (y) agent. The authors try to understand what is the necessary number of first-order queries so as to compute a min-max equilibrium of the respective zero-sum game once the matrix $A$ is unknown. The authors establish that in order to compute an exact min-max equilibrium at least $\\Omega(K)$ first-order queries are needed. The latter result coincides with the first-order complexity of the naive algorithm that first $learns$ the whole matrix $A$ and then computes an exact min-max equilibrium. Then the authors show that in order to compute an $\\epsilon$-approximate min-max equilibrium $\\Omega(\\log(1/\\epsilon K))$ first-order queries are needed. The latter result approximately matches the best-known upper bound ($O(\\frac{\\log K}{\\epsilon})$) obtained by Optimistic MWU.", "questions": "Minor: You may want to include also this references for regret-based algorithms for the computation of CCE in general-sum games.\n\nBeyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update, Piliouras et al. 2022", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think that this is a solid work. The first-order complexity model is very well-motivated since it captures exactly the information exchange model of no-regret dynamics with full information feedback. Thus any lower-bound on the first-order complexity directly implies lower bounds on the convergence rates of such no-regret dynamics. The current state of the art convergence results of such no-regret dynamics is $O( \\frac{\\log K}{\\epsilon})$ that is approximately matched by the provided lower bound.\n\nI also think that the paper introduces some interesting techniques that can be of use so as to completely settle the first-order query complexity for computing min-max equilibrium.\n", "weaknesses": "The only weakness of the paper is the fact that it does not match the current upper bound. That being said I believe that this work is an important first-step.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer Wvc4 for the nice comments and for the reference, we will add it to the final version."}]

Author rebuttal:

Meta-review: The paper addresses a fundamental open question in learning: complexity of learning 2-player zero sum games. It obtains lower bounds in the first-order model. While the specific results obtained are restricted and are far from the current upper bounds, the paper is interesting because it develops a new technique for lower bounds. We expect it to be influential in guiding future works on this subject.
Decision: Accept (poster)