Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization
Authors: Ian Gemp
Luke Marris
Georgios Piliouras
Venue: ICLR 2024 oral (2024)
Keywords: game theory
stochastic optimization
nash equilbrium
normal-form game
x-armed bandits
Primary area: general machine learning (i.e., none of the above)
TL;DR: We propose the first stochastic NE loss for normal-form games.

Abstract: We propose the first loss function for approximate Nash equilibria of normal-form games that is amenable to unbiased Monte Carlo estimation. This construction allows us to deploy standard non-convex stochastic optimization techniques for approximating Nash equilibria, resulting in novel algorithms  with provable guarantees. We complement our theoretical analysis with experiments demonstrating that stochastic gradient descent can outperform previous state-of-the-art approaches.

Published as a conference paper at ICLR 2024
APPROXIMATING NASH EQUILIBRIA IN NORMAL- FORM GAMES VIA STOCHASTIC OPTIMIZATION
Ian Gemp
Luke Marris
Georgios Piliouras DeepMind London, UK gp 1 1ggoogee.ccomm
DeepMind London, UK imgemp@google.com
DeepMind
London, UK
ma rr isrissee sesisssgooll..ooooooooooo com
ABSTRACT
We propose the first loss function for approximate Nash equilibria of normal-fome games that is amenable to unbiased Monte Carlo estimation. This construction allows us to deploy standard non-convex stochastic optimization techniques for approximating Nash equilibria, resulting novel algorithms with provable guaran- tees. We complement our theoretical analysis with experiments demonstrating that stochastic gradient descent can outperform previous state-of-the-art approaches.
INTRODUCTION
Nash equilibrium (NE) famously encodes stable behavioral outcomes in multi-agent systems and is arguably the most influential solution concept in game theory. Formally speaking, if n players independently choose n, possibly mixed, strategies (rgg, for h É [n]) and their joint strategy (a: II zz) constitutes a Nash equilibrium, then no player has any incentive to unilaterally deviate from their strategy. This concept has sparked extensive research in various fields, ranging from economics (Milgrom and Weber, 1982) to machine learning (Goodfellow et al., 2014), and has even inspired behavioral theory generalizations such as quantal response equilibria (QREs) which allow for more realistic models of boundedly rational agents (McKelvey and Palfrey 1995).
Unfortunately, when considering Nash equilibria beyond the 2-player, zero-sum scenario, two significant challenges arise. First, it becomes unclear how independent players would collectively identify Nash equilibrium when multiple equilibria are possible, giving rise to the equilibrium selection problem (Harsanyi et al., 1988). Secondly, even approximating single Nash equilibrium is known to be computationally intractable and specifically PPAD-complete (Daskalakis et al. 2009).
Combining both problems together, e.g., testing for the existence of equilibria with welfare greater than some fixed threshold is NP-hard, and is in fact even hard to approximate (Austrin et al. 2011).
From machine learning practitioner's perspective, such computational complexity results hardly give pause for thought as collectively we have become all too familiar with the unreasonable effectiveness of heuristics in cireumventing such obstacles. Famously, non-convex optimization is NP-hard, even if the goal is to compute local minimizer (Murty and Kabadi 1985), however, stochastic gradient descent (SGD) and variants succeed in training billion parameter models (Brown al. (020)).
Unfortunately, computational techniques for Nash equilibrium have so far not achieved anywhere near the same level of success. In contrast, most modern NE solvers for n-player, m-action, general-sum, normal-form games (NFGs) are practically restricted to a handful of players and/or actions per player except special cases, e.g., symmetric (Wiedenbeck and Brinkman 2023) or mean-fiell games (Pérolat et al. 2022). For example, when running the suite of all 7 applicable methods from the hallmark gambit t library (McKelvey et al. 20T6) on a 4-player Blotto game, we find only brute-force pure-NE enumeration is able return any NE within a hour time limit. Scaling solvers to large games is difficult partially due to the fact that an NFG is represented by a tensor with an exponential um" entries; even reading this description into memory the point, any computational technique that presumes exact computation of the expectation this tensor sampled according similarly does not have any hope of scaling beyond small instances.
be computationally prohibitive. More to
This inefficiency arguably lies at the core of the differential success between machine learning (ML) optimization and equilibrium computation. For example, numerous techniques exist that reduce the

---

Published as a conference paper at ICLR 2024
problem of Nash computation to the minimization of the expectation of random variable (Section 3 Unfortunately, unlike the source of randomness in ML applications where batch learning suffices to produce unbiased estimators, these techniques do not extend easily to game theory which incorporates non-linear functions such as maximum and best-response. This raises our motivating goal:
Can we solve for Nash equilibria via unbiased stochastic optimization?
Our results. Following in the successful steps of the interplay between ML and stochastic optimiza- tion, we reformulate the approximation of Nash equilibria in a normal-form game as a stochastic non-convex optimization problem admitting unbiased Monte- Carlo estimation. This enables the use of powerful solvers and advances in parallel computing to efficiently enumerate Nash equilibria for n-player, general-sum games. Furthermore, this re-casting allows practitioners to incorporate other desirable objectives into the problem such as "find an approximate Nash equilibrium with welfare above w" or "find an approximate Nash equilibrium nearest the current observed joint strategy" resolving the equilibrium selection problem in an effectively ad-hoc and application tailored manner. Concretely, we make the following contributions by producing:
A loss L (a: 1) whose global minima well approximate Nash equilibria in normal form games, 2) admits unbiased Monte-Carlo estimation, and 3) is Lipschitz and bounded.
Efficient randomized algorithms for approximating Nash equilibria in a novel class of games. The algorithms emerge by employing the family of X'armed bandit approaches to L (x) and connecting their global stochastic optimization guarantees to global approximate Nash guarantees.
An empirical comparison of SGD against offte-of-the-ar baselines for approximating NEs in large games. In some games, vanilla SGD actually improves upon previous sfate-of-the-art, in others, SGD is slowed by saddle points, a familiar challenge in deep learning (Dauphin et al. 2014).
Overall, this perspective showcases a promising new route approximating equilibria scale in practice. We conclude the paper with discussion for future work.
2 PRELIMINARIES
In an n-player, normal-form game, each player k E {I,..., = [n]] has a strategy set As {ak1..... agme consisting of my pure strategies. These strategies can be naturally indexed, so we redefine A = [am] as an abuse of notation. Each player & also has utility function, UK A = Il Ar + [o, 1]. (equiv. "payoff tensor") that maps joint actions to payoffs in the unit-interval. We denote the average cardinality of the players' action sets by m n Ex my and maximum by m = max; my. Player k may play a mixed strategy by sampling from a distribution over their pure strategies. Let player k's mixed strategy be represented by a vector ve E my -1 where A m is the (ma - 1ols-11-dimenn -1ddiemnsso probability simplex embedded in Rm Each function un is then extended to this domain so that uy (x) = EaEA Uy (a) II, Ja, where æ = (æ1,..... xn) and aj E A, denotes player j's component of the joint action a A. For convenience, let = denote all components of belonging to players other than player k.
The joint strategy æ E II A ma-11 -1 is a Nash equilibrium and only if, for all k: E [r]]. us (E x x=.) S us (x) for all 2 E A -1 i... no player has any incentive to unilaterally deviate from æ. Nash is typically relaxed with c-Nash, our focus: uk(=,, -xk) I (xx + for all 2 E A
As an abuse of notation, let the atomic action ag = eg also denote the my-dimensional "one- hot" vector with all zeros aside from a 1 at index ax; its use should be clear from the context. We also introduce Vt. as player k's utility gradient. And for convenience, denote by Hğ = Ex- [u (ak, a, x=]]]] the bimatrix game approximation (Janovskaja, 1968) between players and 7 with all other players marginalized out; x denotes all strategies belonging to players other than k and 1 and us (a a,, x xa) separates out I's strategy 2; from the rest of the players k- Similarly, denote by kly = E,_ [ug di (tty) the 3-player tensor approximation to the game. Note player k's utility can now be written succinetly as ug(a,, x- zz V x 11/- = T Taayen for any l where we use Einstein notation for tensor arithmetic. For convenience, define diag(z) as the function that places a vector & on the diagonal of a square matrix, and di aig3 = Rdd Rdxdxd 3-tensor of shape (d, d, d) where d (g) z1-
2

---

Published as a conference paper at ICLR 2024
Loss Exploitabilty (e) Nikaido-Isoda (NI) Fully-Dift. Exp
Function
Obstacle
max; (x(
max of r.v.
Dx (x( Ex EaveA, [max (0, Up (9,(au) (ak, 1 un (2))2
max of r.v.
max of r.v.
Gradient-based NI
NI w/ BR aBRR ITA Ih V. uu (ar)
Al of r.v. sampling from TA E m
Unconstrained
Loss + Simplex Deviation Penalty
Table 1: Previous loss functions for NFGs and their obstacles to unbiased estimation. Note that 6g (a) = max, (.) - contains max operator (see equivalent definition in equation (I).
Following convention from differential geometry, let T.M be the tangent space of manifold M v. For the interior of the d-action simplex Ad-1 the tangent space is the same at every point, so we drop the v subscript, i.c., T We denote the projection of a vector E Fd onto this tangent space as I (z) )= [T ] and call a (V& ib, projected- -orrtedd-r.diet..... We drop d - 1 when the dimensionality is clear from the context. Finally, let (S) denote discrete uniform distribution over elements from set S.
RELATED WORK
Representing the problem of computing Nash equilibrium optimization problem is not new. A variety of loss functions and pseudo-distance functions have been proposed. Most of them measure some function of how much each player can exploit the joint strategy by unilaterally deviating:
def
U. (BRA, x =1) ux (ax) where BR E arg max un (=)x.)).
(1)
As argued in the introduction, we believe it is important to be able to subsample payoff tensors of normal-form games in order to scale to large instances. As Nash equilibria can consist of mixed strategies, it is advantageous to be able to sample from an equilibrium estimate its exploitability 6, However none of these losses is amenable to unbiased estimation under sampled play. Each of the functions currently explored in the literature is biased under sampled play either because 1) a random variable appears as the argument of a complex, nonlinear (non- moon-oolynomint function or because 2) how to sample play is unclear. Exploitability, Nikaido-Isoda (NI) (Nikaidō and Isoda 1955) (also known by Na shConv (Lanctot et al., 2017) and ADI (Gemp et al., 2022)), as well as fully-differentiable options (Shoham and Leyton-Brown Brown 2008 p. 106, Eqn 4.31) introduce bias when a max over payoff's is estimated using samples from x. Gradient-based NI (Raghunathan jt al. 2019) requires projecting the result of a gradient- ascentt step onto the simplex; for the same reason as the max, this projection is prohibitive because it is nonlinear operation which introduces bias. Lastly, unconstrained optimization approaches (Shoham and Leyton-
2008 p. 106) that instead penalize deviation from the simplex lose the ability to sample from strategies when each iterate x no longer a distribution (i.e., 2y & A m1). Table summarizes these complications.
NASH EQUILIBRIUM AS STOCHASTIC OPTIMIZATION
We will now develop our proposed loss function which is amenable to unbiased estimation. Sub- sections 4.1 4.4 providee a warm-up in which we assume an interior (fully-mixed) Nash equilibrium exists. Subsection 4.5 then shows how to relax that assumption allowing us to approximate partially mixed equilibria as well (including pure equilibria). Our key technical insight is to pay special attention to the geometry the simplex. To our knowledge, prior works have failed to recognize the role of the tangent space TA. Proofs are in the appendix.
4.1 STATIONARITY ON THE SIMPLEX INTERIOR
Lemma Assuming player k's utility, us (Ik, x -Kk)., is concave in its own strategy 2s. a strategy in the interior of the simplex a best response BRg if and only if it has zero projected-gradien norm.
Not to be confused with the nonlinear (biased) projected gradient operator (Hazan
2017
3

---

Published as a conference paper at ICLR 2024
In NFGs, each player's utility is linear in 24. thereby satisfying the concavity condition of Lemma
4.2 SIRECTED-GRADIENT NORM AS A LOSS
An equivalent description of a Nash equilibrium is a joint strategy a where every player's strategy is best response to the equilibrium (i.e., Iyk BR2 that (x(x) 0). Lemma states that any interior best response has zero
gradient norm, which inspires the following loss function
[(x=)= Σ T Il1
where each 7k > O represents a scalar weight, or equivalently, a step size to be explained next. Proposition[[] | The loss L is equivalent to NashConv, but where player k's best response is approx- imated by single step of projected gradient ascent with step size T].: aBR; I₁ + m.llra V
This connection was already pointed out in prior work for unconstrained problems (Gemp et al. 2022 Raghunathan et al. 2019), but this result is the first for strategies constrained to the simplex.
4.3 CONNECTION TO TRUE EXPLOITABILITY
In general, we can bound exploitability in terms of the projected -raeteee-ggdienttt norm as long as each player's utility is concave (this result extends to subgradients of non-smooth functions). Lemma 2 The amount player can gain by exploiting a joint strategy a is upper bounded by quantity proportional to the norm of the projected-gradtts
(xxx) S V2|ITTT (V )..
This bound is not tight on the boundary of the simplex, which can be seen clearly by considering Tи to be part of pure strategy equilibrium, In that case, this analysis assumes 2& can be improved upon by a coojected-gradiens ascent step (via the equivalence pointed out Proposition|] TT. However, that is false because the probability of pure strategy cannot be increased beyond 1. We mention this to provide further intuition for why our "warm-up" loss L(x) is only valid for interior equilibria.
Note that [ sy III S | because a is a projection. Therefore, this improves the naive bounds on exploitability and distance best responses given using the "raw" gradient V
Lemma The exploitability of a joint strategy æ, is upper bounded by a function of L(x):
2n
cs
((x)) f(C).
(4)
min& Mp
4.4 UNBIASED ESTIMATION
As discussed in Section primary obstacle unbiased estimation of C(x) is the presence of complex, nonlinear functions of random variables, with the projection of point onto the simplex being one such example (see AI in TT. However, IT the projection onto the tangent space of the simplex, is linear! This is the insight that allows us to design an unbiased estimator (Lemma 5)
Our proposed loss requires computing the squared norm of the expected value of the projected- gradient under the players' mixed strategies, i.e., the 1-th entry of player k's gradient equals V agg Eg_ Be_teaL x (axt, a.).. By analogy, consider a random variable Y. In general, [E[Y]² & [E[ This means that we cannot just sample projected- -erateden-nr and then compute their average norm to estimate our loss. However, consider taking two independent samples from two corresponding identically distributed, independent random variables (1) and (2). Then (3) = [)/()////
E| (1) (2) by properties of expected value over products of independent random variables. This is a common technique to construct unbiased estimates of expectations over polynomial functions of
random variables. Proceeding in this way, define kk)) as a random, unbiased gradient estimate (see
Table 2). Let v be independent and distributed identically to kk))) Then Lemma shows
C(x)
E
mh (())
1
(2)) (Q S2
-1 (1 (1)
(5)
projected gradient
projected pmojectel-graliemt gradient 2
4

---

Published as a conference paper at ICLR 2024
Exact
Sample Others
Sample All
o2 Estimator of V M() V k())
[ux x x+) [0,1]
jux (akt, a-k ~ x= [0,
my4k ( ~ a-k ~
Bounds
[0, me!
(k(p) Query Cost
I Rmml
my
C Bounds
+ 1/4
Σx mame
= Σ 7mm
+ 7mm 2n
L. Query Cost
15 1= my
2mm
Table 2: Examples and Properties of Unbiased Estimators of Loss and Player Gradients (V
k(p) zz
where kp))) is an unbiased estimator of player k's gradient. This estimator can be constructed in several ways. The most expensive, an exact estimator, is constructed by marginalizing player k's payoff tensor over other players' strategies. However, a cheaper estimate can be obtained the expense of higher variance by approximating this marginalization with Monte Carlo (MC) estimate of the expectation. Specifically, we sample a single action for each the remaining players, we can construct unbiased estimate of player k's gradient by considering the payoff of each of its actions against the sampled background strategy. Lastly, we can consider constructing an estimate of player k's gradient by sampling only single action from player i to represent their entire gradient. Each of these approaches outlined in Table Saaeeaalooe along with the query complexity (Babichenko) 2016) of computing the estimator and bounds on the values it can take (Lemma
We can extend Lemma to one that holds under T samples with probability ô by applying, for example, a Hoeffding bound: S (((()) + 0( In(1/5)) where é is an MC estimate of L.
4.5 INTERIOR EQUILIBRIA
We discussed earlier that L(x) captures interior equilibria. But some games may only have partially mixed equilibria, i.c., equilibria that lie the boundary of the simplex. We show how to circumvent this shortcoming by considering quantal response equilibria (QREs), specifically, logit equilibria. By adding an entropy bonus to each player's utility, we can
guarantee all equilibria are interior,
still obtain unbiased estimates of our loss,
maintain upper bound on the exploitability of any approximate Nash equilibrium in the original game (i.c., the game without an entropy bonus).
Define (x) = (x) + +S(xx)) where Shannon entropy S(zx) = -; zsz (n(zx)) is L-strongly concave with respect to the 1-norm (Beck and Teboulle 2003). It known that Nash equilibria of regulay-re games satisfy the conditions for logit equilibria (Leonardos et al. 2021), which are solutions the fixed point equation Ią so f tmx( , v my The softmax should make clear to the reader that all probabilities have positive mass at positive temperature.
Recall that in order to construct an unbiased estimate our loss, we simply needed to construct unbiased estimates of player gradients. The introduction of the entropy term to player k's utility is special in that it depends entirely on known quantities, i.e., the player's own mixed strategy. We can directly and deterministically compute dS dze -7 (In((+() 1) and add this to our estimator of
dS kp)), ( kp) + dzz""
Consider our loss function refined from with changes in blue:
L (T
Σ Tk I (VA))
(6)
As mentioned above, the utilities with entropy bonuses still concave, therefore, a similar bound to Lemma@]applnn applies. We use this to prove the QRE counterpart to Lemma 3 where EQRE is the exploitability of approximate equilibrium in game with entropy bonuses.
5

---

Published as a conference paper at ICLR 2024
Cef/CTweh Feid
E6 SAT CO02E
<4 et 100cog
CEC with Leb
reG 10
Fayer Neteewee
62 24
Pruthwerec
Age Postboare
Poyer PnitSnonn
In 2
oth 35xign
ath 1000l3
In ath 325xa0
Seanr 158xto
Figure I: Effect of Sampled Play on Biased Loss. The first row displays the expectation of the
upper bound guaranteed by our proposed loss L with Te = for all k. The second row displays the expectation of NashConv under sampled play, i.e., Σ E where EN - [max,, ui (a) Ea-zz fu [a)]. To be consistent, we subtract the offset r log(m²) from f+(C") ) per Lemma 13 which relates the exploitability at positive temperature to that at zero temperature. The resulting loss surface clearly shows NashConv fails to recognize any interior Nash equilibrium due to its inherent bias.
Lemma The entropy regularized exploitability, EQRE, of a joint strategy æ, is upper bounded as:
2n ming V/k
(x) daf f(CT).
EQRE S
Lastly, establish connection between quantal response equilibria and Nash equilibria that allows us to approximate Nash equilibria in the original game via minimizing our modified loss L (xr)
Lemma 13 (LT Scores Nash Equilibria). Let (x) be our proposed entropy regularized loss function and be an approximate QRE. Then it holds that
6 7og (II [ms) + k
2n ming UK
(L)(x) (CT)
This upper bound is plotted as heatmap for familiar Chicken game in the top row of Figure First, notice how pure equilibria are not visible as minima for zero temperature. but appear for slightly warmer temperatures. Secondly, notice that NashConv the bottom row is unable to capture the interior Nash equilibrium because of its high bias under sampled play. In contrast, our proposed loss L is guaranteed to capture all equilibria at low temperature T.
ANALYSIS
In the preceding section we established loss function that upper bounds the exploitability of an approximate equilibrium. In addition, the zeros of this loss function have a one-to-one correspondence with quantal response equilibria (which approximate Nash equilibria low temperature).
Here, we derive properties that suggest it is "easy" to optimize. While this function is generally non-convex and may suffer from proliferation of saddle points (Figure 2 is Lipschitz continuous (over the relevant subset of the interior) and bounded. These are two commonly made assumptions in the literature on non-convex optimization, which we leverage in Section 6 In addition, we can derive its gradient, its Hessian, and characterize its behavior around global minima.
Lemma 14
The gradient of L (x)) with respect to player I's strutegy x is
V 22
LT
Σ nu B
(9)
where Bu --
[T-
1111 |d a and B
11
H for t1.
ma
ma

---

Published as a conference paper at ICLR 2024
504 10 (2T 31P 501
T21 W0 12- WeT
30. 18 120 157
150 10: 7E0 TVV
12- 301
Figure 2: Analysis of Loss Landscape. We reapply the analysis of (Dauphin et al. 2014), originally designed to understand the success of SGD in deep learning, to "slices" of several popular extensive form games. To construct slice (or meta-game), and then consider the corresponding n-player, G-action normal-form game at r = 0.1 (with payoff's normalized [0, 1l). The index of critical point &e (V=L² (are) 0) indicates the fraction of negative eigenvalues in the Hessian of L at Te; = 0 indicates local minimum, 1 a maximum, else a saddle point. We see positive correlation between exploitability (y-axis), projected -grddient norm (æ-axis), and (color) indicating a lower prevalence of local minima at high exploitability.
randomly sample 6 deterministic policies
Lemma 16 The Hessian of L (x)) can be wrilten
Hess(L = 2 B THlaa (V')]
(10)
where Bud = BRs. [V) = [m In (.. a (V2T), and we augment T (the 3-player approximation to the game, ligh) so that Tu = rdiag3
At an NE, the latter term disappears because II (V 0 for all & (Lemma If X' was R then we could simply check if B is full-rank to determine if Hess > 0, i.e. if L is locally strongly- convex. However, X' is simplex product, and we only care about curvature in directions toward which we can update our strategy profile æ. Toward that end, define M to be the n(m + 1) nm matrix that stacks B on top of repeated identity matrix that encodes orthogonality to the simplex:
T (
VTllTa (11
VillTa (H
UmllTa T -T -T (
M(x)
(11)
1
where 1lra(2 E Raxb) = 1La - [.1,1]] subtracts the mean from each column of a and 1. is shorthand for diag (21 M(x)
for a nonzero vector 2 E Ran this implies there exists a that orthogonal to the ones vectors of each simplex (i.e., is a valid equilibrium update direction) and 2) achieves zero curvature in the direction z, i.c.. 2 (B) B) 2 (Hfes)) O, and Hess is not positive definite. Conversely, if M (æ) is of rank nmn for quantal response equilibrium æ, then the Hessian of L at in the tangent space of the simplex product (A' = II Xx)) is positive definite. polymatrix because we only require information of the
In this case, we call x polymatrix-isolater local polymatrix approximation of the game (i.e., the H matrices) to construct M and isolated because it implies xc is not connected to any other equilibria.
Definition (Polymatrix-Isolae
Equilibrium). Nash equilibrium x" is polymatrix -ssoaate iff is isolated according to its local polymatrix game uppreximation.
By analyzing the rank of M, we can confirm that many classical matrix games including Rock- Paper-Scce Scies--s,ssor,,,, Chicken, Matching Pennies, and Shapley's game all induce strongly convex L at zero temperature (i.e., they have unique mixed Nash equilibria). contrast, game like Prisoner's Dilemma has a unique pure strategy that will not be captured by our loss at zero temperature.
6 ALGORITHM
We have formally transformed the approximation of Nash equilibria NFGs into a stochastic optimization problem. To knowledge, this is the first such formulation that allows one-shot
7

---

Published as a conference paper at ICLR 2024
Snapleys (8 0.51
GANUT Cowa la mamm))
Bootoo (1Dc, 3r, 400
Blatto DI0; 3p1
0.20
FILL ia =11
[s=1]
0.15
10711
10
KoRgeth 110)
100
0.10
10
10 14
0.0
2.5
5.0
7:5
10.0
0.0
2.5
5.0
7.5
10.0
0.0
0.5
2.5
5.0
7.5
10.0
0.00
0.0
2.1
5.0
7.5
30.0
(Thousands)
Iteratione (Thousaa051
Rerattons (mnoosardds
Ieeratinns (Thoussndss
Figure 3: Comparison of SGD on _==0 against baselines on four games evaluated in (Gemp et al. 2022). The number of samples used to estimate each update iteration (i.e., minibatch size) is indicated by s. From left to right: 2-player, 3-action, nonsymmetrie; 6-player, 5-action, nonsymmetric; 4-player, 66-action, symmetric; 3-player, 286-action, symmetric. SGD struggles at saddle points in Blotto.
unbiased Monte-Carlo estimation which is critical to introduce the use of powerful algorithms capable of solving high dimensional optimization problems. We explore two off- srethhe-sheff approaches.
6.1 STOCHASTIC GRADIENT DESCENT
Stochastic gradient descent is the workhorse of nigh-dimensional stochastic optimization. It is
guaranteed to converge stationary points (Cutkosky al.] 2023), however, it may converge to local, rather than global minima. It also enjoys implicit gradient regularization (Barrett and Dherin 2020), seeking "flat" minima and performs approximate Bayesian inference (Mandt al. (017). Despite the lack of global convergence guarantee, we find it performs well empirically in games previously examined by the literature: modified Shapley's (Ostrovski and van Strien 2014). GAMUT
D7 (Nudelman et al. 2004). Blotto (Arad and Rubinstein 2012). Figure 3 shows SGD is competitive with scalable techniques to approximating NEs: FTRL (Shaley-Shwarc and Singer 2006 Shalev
Shwartz et al. 2012), Regret Matching (Hart and Mas-Colell 2000), ADIDAS/ QUSSQQQRRRRRR QREaatt (Gemp et al. 2022). Shapley's s game induces a strongly convex L (see Section 5) leading to SGD's strong
performance. Blotto reaches low, but nonzero 6, demonstrating the challenges of saddle points.
6.2 HIGH PROBABILITY, GLOBAL POLYNOMIAL CONVERGENCE RATES VIA BANDITS
We explore one other algorithmic approach to non-convex optimization based on minimizing regret, which enjoys finite time global convergence rates. X'-armed bandits (Bubeck et al., 2011) system- atically explore the space of solutions by refining a mesh over the joint strategy space, trading off exploration versus exploitation of promising regions. Several approaches exist (Bartlett et al. 2019 Valko et al. 2013) with open source implementations, e.g., (Li et al.) 2023). Applying Xrammed bandits to our _ can be thought of as a stochastic generalization of the exclusion method and other bandit approaches for Nash equilibria (Berg and Sandholm 2017: Zhou et al. 2017).
Equipped with these techniques, we establish high probability polynomial-time global convergence rate to Nash equilibria in n-player, general-sum games given all QRES(T) are polymatrix-isolated The quality of this approximation improves as > 0, at the same time increasing the constant on the convergence rate via the Lipschitz constant / L defined below. For clarity, assume users provide a temperature in the form 7 In(I/p) with p - (0, 1) which ensures all equilibria have probability Lower p corresponds with lower temperature.
mass greater than _.__ for all actions (Lemma
Theorem (BLiN PAC Rate). Assume т7s 17 2/L. T mttp and a previously pulled arm is returned uniformly at random (i.e., t ~ U(T))) Then any w > 0
In
e S w (n(ppp)
log mx) + 2(1 + (1e 13 2nd
(12)
T
with probability (1 w 10=)=(11- -2 where m max; my, 2| S c
[I((m))
2
[In(1/p)
(Corollary D. i- In la(1/p)
+ plm(1/p) (p
+
m
+ nm) (Corollary 2 the zooming dimension d2 nm,
and the zooming constant C. 1 (1 ( -x)) nm (Corollary 30
The convergence rate for BLiN (Feng et al. 2022) depends on bounds on the exploitability in terms of the loss (Lemma [3]. bounds on estimates of the loss (Corollary D. Lipschitz bounds the
8

---

Published as a conference paper at ICLR 2024
7-Player, Symmetric, 2-Action Game
Strategy
10
Symmetric joint joint J
True Exploitability (E)
10-1
Exploitability
Upper Bound = f(c)
10-3
Upper Bound
E f 0.01)
10
1.14
1.60
0.62
0.56
Bandit Samples
0.69
10-7
0.0
0.2
0.6
0.8
1.0
Probability of Selecting Action of
Figure 4: based (BLiN) Nash solver applied to an artificial 7-player, symmetric, 2-action game. We search for symmetric equilibrium, which is represented succinetly as the probability of selecting action 1. The plot shows the true exploitability of all symmetric strategies in black and indicates there exist potentially 5 NEs (the dips in the curve). Upper bounds on our unregularized loss L capture of these equilibria, missing only the pure NE on the right. By considering our regularized loss, L", we are able to capture this pure NE (see zoomed inset). The bandit algorithm selects strategies evaluate, using 10 Monte-Carle samples for each evaluation (arm pull) of L These samples are displayed as vertical bars above with the height of the vertical bar representing additional arm pulls. The best arms throughout search are denoted by green circles (darker indicates later in the search). The boxed numbers near equilibria display the welfare of the strategy profile.
infinity norm of the gradient (Corollary 2 and the number of distinct strategies (nm Σx m&). zooming-dimension
This result further depends on the optrinatt or zooming dimension d₂ and zooming constant C2 which quantify the number of near optimal states. particular, we assume L(s(=) locally (g-oc)-strongl)) convex with respect to 11> about each global optimum within a ball of radius
Tyy Here, [0. 1]"(m-1) + 11, A m. is any function that maps from the unit hypercube to product of simplices; we analyze two such maps in Appendix B.I Next, we present an additional convergence rate result using an alternative X'bandit approach, StoSOO (Valko et al. (013)..
Theorem 5 (StoSOO Rate). Corollary of Valko et al. (2013) implies that with probability (1
w- (1 8) for any w > 0, uniformly randomly drawn arm (i.e., t ~ U(TT) achieves
6 S W
1
log (II mx) + Vnl.
loga (Tk/8)
2 2logs(e) + Eab de TT/K
(13)
(n(1/p)
where d= nmm 1). E = (2 22/d), & (1+2(+)) k T log, (T) 33 b is the branching factor
d/2
for partitioning cells, and the near-optimality constant C 1 2
bad
(Lemma 36
5r
Here we assume [(s(2) is locally (a-2)-stronlly convex with respect to || ||e about each global optimum within a ball of radius Ty- Theorem implies (T--1/1) global convergence rate (Proposition) Z) however this is achieved only after exponential number of burn-in iterations.
7 CONCLUSION
In this work, we proposed a stochastic loss for approximate Nash equilibria in normal-form games. An unbiased loss estimator of Nash equilibria is the "key" to the stochastic optimization "door" which holds a wealth of research innovations uncovered over several decades. Thus, it allows the development of new algorithmic techniques for computing equilibria. We consider bandit and vanilla SGD methods in this work, but these are only two of the many options now at our disposal (e.g. adaptive methods (Antonakopoulos et al. 2022), Gaussian processes (Calandriello et al., 2022). evolutionary algorithms (Hansen et al. 2003). etc.). Such approaches as well as generalizations of these techniques to extensive-form, imperfect-informatt information games are promising directions for future work. Similarly how deep learning research first balked at and then marched to train neural networks via NP- hard non-convex optimization, we hope computational game theory can march ahead to make useful equilibrium predictions of large multiplayer systems.

---

Published as a conference paper at ICLR 2024
REFERENCES
K. Antonakopoulos, P. Mertikopoulos, G. Piliouras, and X. Wang. AdaGrad avoids saddle points, In International Conference on Machine Learning, pages 731-771. PMLR, 2022.
A. Arad and A. Rubinstein. Multi-dimensional iterative reasoning in action: The case of the Colonel Blotto game. Journal of Economic Behavior & Organization, 84(2)571-5855 2012.
Austrin, M. Braverman, and E. Chlamtáë. Inapproximability of NP-complete variants of Nash equilibrium. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 13-25. Springer, 2011.
Y. Babichenko. Query complexity of approximate Nash equilibria. Journal of the ACM (JACM), 63 (4):36:1-36:24 2016.
D. Barrett and B. Dherin. Implicit gradient regularization. In International Conference Learning Representations, 2020.
P. L. Bartlett, V. Gabillon, and M. Valko. A simple parameter-free and adaptive approach to optimization under minimal local smoothness assumption. In Algorithmic Learning Theory, pages 886. PMLR, 2019.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):667-1755 2003.
K. Berg and T. Sandholm. Exclusion method for finding Nash equilibrium in multiplayer games, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
P. Boyd and Vandenberghe. Convex optimization. Cambridge university press, 2004.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam,
G. Sastry, A. Askell, al. Language models are few-shot learners, Advances in neural information processing systems, 33: 1877-1901, 2020.
S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvári. X'armed bandits. Journal of Machine Learning Research, 12(5), 2011.
D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco. Scaling Gaussian process optimization by evaluating a few unique candidates multiple times. International Conference on Machine Learning, pages 2523-2541. PMLR, 2022.
A. Cutkosky, Mehta, and F. Orabona. Optimal, stochastic, non-smooth, non-convex optimization through online-to-none -onncco-v- conversion. In Proceedings of the 40th International Conference Machine Learning, ICML'23. JMLR.org, 2023.
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium, Communications of the ACM, 52(2):89-97,2000 2009.
Y. N. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio. Identifying and attacking the saddle point problem high-dimensional non-convex optimization. Advances in Neural Information Processing Systems, 27, 2014.
A. Deligkas, Fearnley, A. Hollender, and T. Melissourgos. Pure-cireuit: Strong inapproximability for PPAD. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 159-170. IEEE, 2022.
Y. Feng, Z. Huang, and T. Wang. Lipschitz bandits with batched feedback. Advances in Neural Information Processing Systems, 35:19836-19848 2022.
B. Gao and L. Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv: /004::/770000000 2017.
10

---

Published as a conference paper at ICLR 2024
1. Gemp, R. Savani, M. Lanctot, Y. Bachrach, T. Anthony, R. Everett, A. Tacchetti, T. Eccles, and Kramár. Sample-base based approximation of Nash in large many-player games via gradient descent. In Proceedings of the 21st International Conference Autonomous Agents and Multiagent Systems, pages 507-515, 2022.
B. Ghojogh, A. Ghodsi, F. Karray, and M. Crowley. KKT conditions, first-order and second-order optimization, and distributed optimization: tutorial and survey. arXiv preprint arXiv:2110.01858, 2021.
I. Goodfellow, J. Touget-Abadie, M. Mirza, B. Xu, D. Warde-Farley. S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 27, 2014.
N. Hansen, S. D. Müller, and P. Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary computation, 11(1): 1-18, 2003.
J. C. Harsanyi, R. Selten, et general theory of equilibrium selection in games. MIT Press Books, 1, 1988.
S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econo- metrica, 68(5):1127-1155) 2000.
E. Hazan, Singh, and C. Zhang. Efficient regret minimization non-convex games. In Interna- tional Conference on Machine Learning, pages 1433-1441. PMLR, 2017.
E. Janovskaja. Equilibrium points in polymatrix games. Lithuanian Mathematical Journal, 8(2): 381-384, 1968.
M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and T. Graepel. unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, pages
2017.
M. Lanctot, E. Lockhart, J.-B. Lespiau, V. Zambaldi, S. Upadhyay, J. Pérolat, S. Srinivasan, F. Tim- bers, K. Tuyls, S. Omidshafiei, D. Hennes, D. Morrill, Muller, Ewalds, R. Faulkner, Kramár, B. D. Vylder, B. Sacta, J. Bradbury, D. Ding, S. Borgeaud, M. Lai, J. Schrittwieser, T. Anthony, E. Hughes, Danihelka, and Ryan-Davis. OpenSpiel: A framework for reinforcement learning in games. CoRR, abs//108.0944 094553, 2019. URL htL.ttt:///axxi..orr/aa/////////
09453
S. Leonardos, G. Piliouras, and K. Spendlove. Exploration-exploitation in multi-agent competition: convergence with bounded rationality. Advances in Neural Information Processing Systems, 34: 26318-26331, 2021.
W. Li, H. Li, Honorio, and Q. Song. Pyxab a python library for X'armed bandit and online blackbox optimization algorithms, 2023.
04 04030
C. K. Ling, F. Fang, and J. 7. Kolter. What game are we playing? end-to-end learning in normal and extensive form games. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 396-402, 2018.
J. Mairal. Optimization with first-order surrogate functions. In International Conference on Machine Learning, pages 783-791. PMLR, 2013.
S. Mandt, M. D. Hoffman, and D. M. Blei. Stochastic gradient descent as approximate Bayesian inference. Journal of Machine Learning Research, 18:1-35, 2017.
L. Marris, Gemp, and G. Piliouras. Equilibrium-invartee invariann embedding, metric space, and fundamental set of 2x2 normal-form games. arXiv preprint 3304022330009977,. 2023.
R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1),6-3,, 1995.
R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory, version 16.0.1, 2016.
11

---

Published as a conference paper at ICLR 2024
D. Milec, J. Černý, V. Lisý, and B. An. Complexity and algorithms for exploiting quantal opponents in large two-player games. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6): 5575-5583, 2021.
R. Milgrom and R. J. Weber. theory of auctions and competitive bidding. Econometrica: Journal of the Econometric Society, pages 1089-1122 1982.
K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Technical report, 1985.
H. Nikaid6 and K. Isoda. Note on non-cooperative convex games. Pacific Journal of Mathematics, (1):807815, 1955.
E. Nudelman, J. Wortman, Y. Shoham, and K. Leyton-Brown. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In AAMAS, volume 4, pages 880-887, 2004.
G. Ostrovski and S. van Strien. Payoff performance of fictitious play. Journal of Dynamics and Games, 1(4):621-636 2014.
Pérolat, S. Perrin, R. Elie, M. Laurière, G. Piliouras, M. Geist, K. Tuyls, and O. Pietquin. Scaling mean field games by online mirror descent. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 2022.
T. Popoviciu, Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica, (129-145):20, 1935.
A. Raghunathan, Cherian, and D. Jha. Game theoretic optimization via gradient-based Nikaido- Isoda function. In International Conference on Machine Learning, pages 5291-5300, PMLR, 2019.
Shalev-Shwarz and Y. Singer. Convex repeated games and Fenchel duality. Advances in Neural Information Processing Systems, 19, 2006.
S. Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012.
Y. Shoham and K. Leyton- Broww. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008
M. Valko, A. Carpentier, and R. Munos. Stochastic simultaneous optimistic optimization. In International Conference Machine Learning, pages 19-27. PMLR, 2013.
B. Wiedenbeck and F. Brinkman. Data structures for deviation payoffs. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, 2023.
Y. Zhou, J. Li, and J. Zhu. Identify the Nash equilibrium in static games with random payoffs. In International Conference Machine Learning, pages 4160-4169. PMLR, 2017.
12

---

Published as a conference paper at ICLR 2024
APPENDIX: APPROXIMATING NASH EQUILIBRIA IN NORMAL-FORM GAMES VIA STOCHASTIC OPTIMIZATION
Loss with its Properties and Derivatives
14
A.I Loss: Connection to Exploitability, Unbiased Estimation, and Upper Bounds
14
A.2
QREs Approximate NEs Low Temperature
19
Gradient of Loss
A.4
Bound on Gradient Lipschitz Property
22
Hessian of Loss
23
Global Convergence Guarantees
26
B.
Maps from Hypercube to Simplex Product
26
B.2
Near Optimality & Zooming ................................
29
B.3
D-BLiN
32
B.4
Bounded Diameters and Well-shaped Cells
................................
37
B.5
Stochastic Simultaneous Optimistic Optimization
39
B.6
Regret to PAC Bounds
41
B.7
Complexity of Polymatrix Games
43
Experimental Setup and Details
45
GAMBIT
45
Loss Visualization and Rank Test
45
Saddle Point Analysis
47
4
SGD Classical Games
47
BLiN on Artificial Game
13

---

Published as a conference paper at ICLR 2024
A LOsS WITH ITS PROPERTIES AND DERIVATIVES
In this section, we construct our loss function and derive many of its properties and derivatives (c.g., gradient and hessian) useful for analyzing and executing optimization algorithms.
A.1 LOSS: CONNECTION TO EXPLOITABILITY, UNBIASED ESTIMATION, AND UPPER BOUNDS
A.1.1 KKT CONDITIONS IMPLY FIXED POINT SUFFICIENCY
Consider the following constrained optimization problem:
max f(x) #ER"
(14a)
s.t. Di (x))) - 0 Vi
(14b)
(x Vj
(14c)
where f' is concave and Si and hy represent inequality and equality constraints respectively. If g: and hú are affine functions, then any maximizer x² of f must satisfy the following necessary and sufficient KKT conditions (Ghojogh et al. 2021 Boyd and Vandenberghe 2004):
Stationarity: 0 0f(x*) E, (x0 E, (x)g((x")
Primal feasibility: hz(²") ) = for all j and gi S for all
Dual feasibility; 14 2 0 for all
Complementary slackness: (*gr(x=") = for all
Lemma 1. Assuming player k's utility, uk [ is concave in its own strategy 2k, strategy in the interior of the simplex is a best response BR if and only if it has zero projected-gradier norm:
BRk E (inlA ( Farg max (2 ug x.))
(BRg E inlA) (I V+ BR IlI 0).
Proof. Consider the problem of formally computing EK (z) maXeeintA (=(2, us (zk. T-A)::
max un (2, xx - un (x xt
(15a)
s.t. 2/ < Vk
(15b)
2/ 0.
(15c)
Note that the objective is linear (concave) in and the constraints affine, therefore the KKT conditions are necessary and sufficient for optimality. Recall that we assume that the solution 2 lies in the interior of the simplex, i.e., = for each k. Also, let e be onehot vector, i.e., zeros vector except with a 1 at index k. Mapping the KKT conditions onto this problem yields the following:
Stationarity: 0 E Oug(2" x- X1 + En PACk
Primal feasibility: Σ 2 = 1 for all k
Dual feasibility: n4 2 0 for all l:
Complementary slackness: = 0 for all k.
For any point z* intA, primal fcasibility will be satisfied. Given assumption that at > 0. by complementary slackness and dual feasibility, each f4 must be identically zero. This implies
Not to be confused with the nonlinear (i.e., introduces bias) projected gradient operator introduced in Hazan
2017
14

---

Published as a conference paper at ICLR 2024
the stationarity condition can be simplified to 0 Oug(2* x=k)) + A1. Rearranging terms (and repurposing A) we find that for any z", there exists a such that
A1 E Oup(2" (xxx)=
(16)
Equivalently, ( x at E inlA. Any vector proportional to the ones vector has zero projeteedgradicn norm, completing the claim: [
__111 11 [(A1) A(1
ma
ma 1) 0.
ma
A.1.2 NORM OF PROJECTED-GRADIENT AND EQUIVALENCE TO NEG EXPLOITABILITY WITH APPROXIMATE BEST RESPONSES
Proposition 1. The loss C is equivalent to NashConv, but where player k's best response is approx- imated by single step of mnjjectddgradicen ascent with step size Ti: aBRk Ik + m.llTa (Val)
Proof. Define an approximate best response as the result of player adjusting their strategy via wrojected-gradient ascent step, i.e,, aBR₁ I + m.l (V+, for player k.
In normal form game, player k's utility at this new strategy
( x xx)) = (V z (xx + mh T (V us (a)) + (V an (
(17)
Therefore, the amount player gains by playing aBR is
εx = uu (aBRRR x F- (x)
(18a)
Tik (V ok
IIA (V.. 1x
(18b)
1/K
(V ma
(1 vv ITA((V)))
(18c)
Th IIT
11
(18d)
where the third equality follows from the fact that the projected- -raettedtggrdeet.. II (Vh, v, ), is orthogonal to the ones vector.
A.1.3 CONNECTION TO TRUE EXPLOITABILITY
Lemma 2. The amount player gain by deviating is upper bounded by quantity proportional to the norm of the rrnjected-grudieer
en (x( S @2|IIITT(VE I..
(19)
Proof. Let = be any point on the simplex. Then by concavity of un with respect to z,
Ug (2, x xx) - (x) I (V (z xx)
(20a)
1-1=0
= (v+)) T( xx) (1
(( - IDk
(20b)
m&
= -IITA (v ) T)
(z- TR
(20c)
(1)
S (V
(Cauchy-Schwarc
(20d)
Continuing, we can prove a bound on in terms of the projected-gradient loss:
Lemma 3. The exploitability, c, of a joint strategy x. is upper bounded as a function of our proposed loss:
2n.
((x).
(21)
min+ me
15

---

Published as a conference paper at ICLR 2024
Proof.
max max us (2, ux(2))
(22a)
max un (z, - un (x)
(22b)
2 IIT V 112
(Lemma 2
(22c)
[ITT (V 1|2
(22d)
< 2m
ITA 21)),l.......
|
(22e)
V2n
IITA (V
(22f)
/2n
Th TI (V VIB
(22g)
2n
(22h)
ming ?e
2n
f(xx).
(22i)
ming 4e
Lemma 4. The entropy regularized exploitability, EQRE, of joint strategy x, is upper bounded function of our proposed loss:
2n
EQRE
L7 (xx)
(23)
ming 7Jk
Proof. Recall that uf (Ik, xb) is also concave with respect to dy. Then
EQRE max max us (z, x. (x(
(24a)
max u (z, - (x)
(24b)
V2 [I 1ll
(Lemma 2
(24c)
v2
(24d)
S 2m
12,
(24e)
22n
(24f)
2n
Σ
mi |ITA
(24g)
Tikk
2n
me Tellllya 1B
(24h)
ming Me
2n
(x))
(24i)
mink 7p
n
16

---

Published as a conference paper at ICLR 2024
A.1.4 UNBIASED ESTIMATION
Lemma 5. An unbiased estimate of [(x) can be obtained by drawing two samples (pure strategies) from each players' mixed strategy and observing payoffs.
Proof. Define in
random, unbiased gradient estimate (see Table 2. Let V
be independent
and distributed identically to (((1) Then,
E mote Σ Th
(V
( mx
(V
(
(25a)
m
zL
projected gradientt 1
projected gradient
Σ A. (+)()) 1 (1 (
(
(
1
(1
)
(25b)
mk
= Σ M.Eaaaa (( (1 ( )1)] (3) (
T
(
(25c)
mk
22
Σ VV
1 (I 1))
_ -1 [ )1
(25d)
mk
mk
Σn (
(25e)
L(x)
(25f)
where the first equality follows from linearity of expectation, the second from independence of random variables, and the third from Egin> |
V my i.e., v((r) is an unbiased estimator of
player k's gradient. Therefore, equation (2a comprises an unbiased estimate of C(x) proving the claim.
Lemma 6. The loss formed as the sum of the squared norms of the projected-gradients, LT, can be decomposed into three terms as follows:
(x)
Σ
na Big Bag + 2 Σ
Ex Bxq + Σ
Ex
Ex
(26)
k
R
(A)
(B)
(C)
where q is any player other than k:
Proof. Let ST = - Ei Thi In(xx) so that 0st
= -T(((x))) + 1). Note that Ir (8S")
Bag
=
-rllra(n((x))) L (xx = Σ (Il ViTT
(V
II
(27a)
OST
0ST
Σ Em To +
11 J[I me
11
[11
+
(27b)
Σ Mh [ [ TT
11
|2 kny 12. +
[T
11
H
(27c)
m4
01
m&
kq
OST [T
OST
+ 0ok
11 T 12
(27d)
Dirk
mo.t
T B B + 2 Σ
mh ER Bkq +
Σ
The ET Ex
(27c)
I
b:
(4)
(B)
(C)
where Bkg
1 me
11 1 and Eg
85
T
1 11 In(x)))
mg
mc
17

---

Published as a conference paper at ICLR 2024
A.1.5 BOUND ON Loss
By Proposition T. Equation 18d
can also rewrite this loss weighted sum of 2-norms, m.
((z) = Σx 7k V Hxll2 where
V
E [0, 1] for brevity. This will allow us to
more easily analyze our loss.
Lemma 7. Assume payoffs are bounded in [0, 1), then setting Th S nmk
or The S nm
or Σx T/
ensures 0 S (xx) I 1 for all a E X.
Proof.
S [(x)
Σ Me VE 1E - -xxl2
(28a)
Σ MIETE m
(V ma1 - )2
(28b)
Σ mame V (
(28c)
m
(28d)
A
$ (max mk)
Σ mp)
(28c)
&
(max 7k )mm 1 1
(28f)
4
(max TT&
(28g)
Yum
where the first inequality follows from Popoviciu's inequality (Popoviciu) 1935): the variance of bounded random variable X is upper bounded by [ar[X]=
[maxx- mimx)
Next, establish the following useful lemmas. Lemma 8. The matrix I
ma 11 is a projection matrix and therefore idempotent. It is also symmetric, which implies it is its own square root.
Proof.
2
[
11
11
1(1
T
1)1
(29a)
17
m&
m
2
1
=I
11
11
(29b)
m
m
1
11
(29c)
m
Lemma 9. The product All 11m 1TB for any integer p O has entries whose absolute value is bounded by n (Amax (mmi)(mmax - Bmin) where Aminy Amax, Bming Bmax represent the minima and maxima of the matrices respectively.
Proof. The matrix [] 11-41 -11 [[]] is idempotent (Lemma
rewrite the product for any p as
A[1 11
[[
11 J.
(30)
m
The matrix [ 111]] has the property that removes the mean from every row of a matrix when right multiplied against it, i.c., All - 111" removes the means from the rows of A. Similarly, left multiplying it removes the means from the columns. Let Á and / represent these mean-centered
18

---

Published as a conference paper at ICLR 2024
results respectively. recognized as
The absolute value of the ijth entry in the resulting product can then be
Σ An Bkg
E( 1 Σ Ask BBs
1 Σ Bey)
(31a)
mm Corr(Ar, B) JA, ØB.gl
(31b)
I mo ...."
(31c)
By Popoviciu's inequality (Popoviciu 1935), know the variance of bounded random variable
X is upper bounded by Var | S 1 [maxx- minx)² )²² Hence its standard deviation is bounded by
Std[X] S (maxx - minx). Plugging these bounds for A and B into equation (31c) completes the claim.
Lemma 10. Assume payoffss are bounded in [0, 1), then
(x)) | - 1 (max ) In
+ 1)²
(32)
Tmin
for any such that z
2 miaa Ak, L.
Proof. First note that for payoffs in [0, 1]. the entries
1Ta (v = ll (v.. - ((n(#x) + 1)) = LITA(VV - - (m(x))
(33)
are bounded within [0, r ln( ) 11 with a range of r In( 1))+1
+1. Then starting from the definition
of L and applying Lemma we find
|C (x)
Th | (V
(34a)
morrer (T In
+ 1)²
(34b)
Tmin
(T In
+ 1)
mmx mp)
Σ m&
(34c)
4
Imin
4 k
(max nh aumi(Tll
+ 1)²
(34d)
Emin
A.2 QRES APPROXIMATE NES AT Low TEMPERATURE
Lemma 11. Setting ln(pp)) with p E (0,1) and payoffs in [0, ensures that any QRE contains probabilities greater than max, me
Proof. Let m max; my and V be player k's gradient. Recall that a QRE(T), specifically a logit nu
equilibrium, satisfies the fixed point equation ve softmax( for any action in a QRE strategy profile, x, is lower bounded as
for all k. Then the probability
Iki 2 min min {IKI} 2
min min min {2/23
(35a)
æ' wo is QRE
min min min [softmax Vig
}]
(35b)
(35c)
(m-
1)e e0
Emin
(35d)
where equation (35c follows from minimizing the numerator and maximizing the denominator the softmax formula subject to the payoff constraints.
19

---

Published as a conference paper at ICLR 2024
Rearranging terms, we find
1)
(36)
m
Jmmin
In
1 Amia
1)
m
Let p E (0, 1) such that Tinn
P,
then
max, 12
m
(37a)
In
1)
m
Emin
(37b)
In
m 1)
m
p
1
(37c)
In
n m--p1 1 m--17 P
(37d)
In
This implies if we set = In(1/n(()))) -1, then we are guaranteed that all QREs contain probabilities
greater than Tmin max, ma.
Corollary 1. Assume payoff' are bounded in [0. 1] and r In(1/p) then
1
In(m") 2
(a:))
(max me nnm
(1(p/)) +2)
(38)
Proof. Starting with Lemma
10 and applying Lemma
we find
|C (x)
S
(max nı )nm (T In
+ 1)²
(39a)
4
l:
Ømin
1
m
+ +1) )² p
(max )re
In
(39b)
4
In(1/p)
1
In(1/p) (In(m") + 1n(1/p))) + +1)
(max My )rm
(39c)
4
In(m²)
2
(max 7h nm
In(1/p) + +2)
(39d)
I &
Lemma 12 (Low Temperature Approximate QREs are Approximate Nash Equilibria). Let V be player k's entropy regularized gradient and x be an approximate QRE. Then it holds that
(BRR x.)) un (x) S 7 rlg(mm)) v2|lTrr (VAr) IIl--
(40)
Proof. Beginning with the definition of exploitability, we find
Ug (BRs, x - ux (x) = (ux (BR xt + S((B))) - -S((Be))
(41a)
(2) + + 7((x))
2i (BRR, I (x( - (S((x)) S((B+)
(41b)
< max uj -
x 2z) ux (x) + max
S(z')
(41c)
EE
V2IlLITA (V K +7
S(2') -E
max
(41d)
W V2 (V + rlg(m))
(41e)
where the second equality follows from the definition of player k e's entropy regularized utility uf. the first inequality from nonnegativity of entropy S, the second inequality from concavity of uh with respect to its first argument (Lemma 2). and the last from the maximum possible value of Shannon entropy over distributions my actions.
20

---

Published as a conference paper at ICLR 2024
Lemma 13 (L" Scores Nash Equilibria), Let (x) be proposed entropy regularized loss function and a be an approximate QRE. Then it holds that
S T Flo
(II mmm)
2n
(x).
(42)
ming 1Jk
Proof. Beginning with the definition of exploitability and applying Lemma 12 we find
c max Us (BRR, x x=)) ux.22)
(recall each E 2 0)
(43a)
(BRR, uu (2)
(43b)
$
Σ
T (log(mm)
+ 22 II
(43c)
k
Σ
log(m))
+
Σ v2 IITA
kT
(43d)
S log II
mk
+
2n
(x)
(43e)
ming TJk
where the last inequality follows from the same steps established the relationship between ((x:) and c.
24c
24
outlined in Lemma
which
A.3 GRADIENT OF LOss
Lemma 14. The gradient of (x)) with respect to player I's strategy xı is
V ((x) = Σ
mi BELTATA (
(44)
k
where Bu = =T(1 11 Jdiag(( 4 and BRI = =11- [1- -1--1,111 11
H H for k # I.
mi
m.
Proof.
Recall from Lemma that the loss can be decomposed as (x)x) = (A) + (B) + (C).
Then
De, Da,[(A)] = Dz, Σ Th B Bxg =2
BB BRIT
(45)
light
where a # k and Bkg 11 11 [ does not depend on zg.
me
Also, letting Bu = -- [[[-
1 [diag()
mi
Dz, [B][ = 1 Σ Thk In(xx) Bky
(46a)
-2 In Day (n(m))) T Biggol + Σ
De,DDnn [I((x)) BRAal]
(46b)
--2r(mdiag] 1
Biqry +
Σ
mr Br In(xx)]
(46c)
21
ligh
--27 (n (1--111 Jdiaagaa(() (1)
(
Σ kgl
mh Bi In(2x)
(46d)
my
= =2/m - Σ
ni Bu In(zx)]
(46c)
21

---

Published as a conference paper at ICLR 2024
And
D2,[(C]] = Dzy Σ 7hE In(x)) -
[I
11 T In(xx))
(47a)
m&
2T- Indiag( _ [T
[I((z))
(47b)
21
my
27m (1
11 ]dlag( ())) ITra(-rin(a)
(47c)
my
2m (ra(-r(a1)))
(47d)
Putting these together, we find
V ((x) 2 Σ
mh - In(xx))) + 2m 2m [ITTA (V') + 1l (+=a(=in((zi)
(48a)
2m ITT (VRTT + Σ
mh BR (V
(48b)
= -2 - The II
(48c)
A.3.1 UNBIASED ESTIMATION
In order to construct an unbiased estimate for each BRG, we will need form an independent unbiased estimate of H Recall that H is simply the expected bimatrix game between players & and I when all other players sample their actions according their current strategies.
A.4 BOUND ON GRADIENT/ / LIPSCHITZ PROPERTY
Lemma 15, Assume payoffs are upper bounded by 1, then the infinity norm of the grudient is bounded
VnL (x) S 1 (max m1) (T)
(11 (ommmLLa
+ 1) [Tm* (11-1) -1) + nm
(49)
2
Emin
Fmin
Proof.
Recall from Lemma that the gradient of C(x) with respect player I's strategy o; is
V F(x) = 2 Σ BiILI (VAr) a
(50)
k
where Bu =-r 1 |diag( 1 and Bug 1
11 H for k #
mi
me
As noted before the derivation of Lemma 10 for payoffs in [0, 1]. the entries in vkr 7 7 In(2x) are bounded within [0, 7 In(
21
24
with a range 7 In(
1. Similarly, the entries in with range of 7( Fanin 1).
2min
-ddi ag 2 bounded within
Fmin
22

---

Published as a conference paper at ICLR 2024
The infinity norm of the gradient can then be bounded as [m (x))lox
maxx V mz L(xx)]loo
(51a)
max 2 Σ mhs
(51b)
h mh max
2
(51c)
( +) +
-1)
ma (T (r In
2 n.
(r
In
+
1)
2
Amiu
Fmin
Emin
(51d)
= 2 In Timin
+ 1) m-
- 1) + Σ
ToTTER
(51e)
Vrmin
lighl
(max nh) (T
1
1)
Tmm--
-1)
Σ
mb
(51f)
2 k
Pmin
(max mhe (T In
+1) rm"
+
-1)
1) + mm
(51g)
Timin
Emin
where the second inequality follows from Lemma 9
Corollary 2. If T is set according to Lemmal 11 as T = In(1/p))* and payoff's are in [0, 11. then the infinity norm of the gradient bounded as
In(mm) [n(1/p) +
m m2
2T (T) S 2/ (max mh)
+ nm = (max mx) pln(1/p)
(52)
&
where m max; my and L is defined implicitly for convenience in other derivations.
Proof. Starting with Lemma 15 and applying Lemma 11 (i.e., r T= =l((p/p)- and Timin
P with
payoffs in [0, 1] and where m
max; my), we find
1
1
V (x) $
(max mp ( In
1) rm"
1) + mm
(53a)
2
Tmin
Tmin
1 (max ms)
In(mm /v)
m
+
-1) + nm
(53b)
2
In(1/p)
In
p
1 (max
In(m²) In(1/p) +
m
+ mm
(53c)
2
pl1(1/p)
As p -> 0+, the norm of the gradient blows up because the gradient of Shannon entropy blows up for small probabilities. As p + 1, the norm of the gradient blows up because we require infinite temperature guarantee all QREs are nearly uniform; recall 7 the regularization coefficient on the entropy bonus terms which means our modified utilities blow up for large T.
A.5 HESSIAN OF LOSS
We will now derive the Hessian of our loss. This will useful in establishing properties about global minima that enable the application of tailored minimization algorithms. Let [=[) denote the differential operator applied to (possibly multivalued) function f with respect to z. For example, Dxr, [M = Dr,, [T,,TT The where T is player k's payoff tensor according to the three-way approximation between players hi, 1, and y to the game at at.
Lemma 16. The Hessian of L (x:) can be written
Hess( = 2B B (
(54)
where Bu = VT (V)) = Im (V!T), In T (era(Vi (VH)), and we augment T (the 3- 3-player tensor approximation to the game, T so that Thp = T rdiag3( 1.) and otherwise 0.
23

---

Published as a conference paper at ICLR 2024
Proof. Recall the gradient of our proposed loss:
Vx, [(x) = Σ
mh BI (V
(55)
k
where By --[--
11 adi and Byr =
11 for fl.
mi Consider the following Jacobians, which will play an auxiliary role in our derivation of the Hessian:
m.
1 17
Di[Ba] = r|1 11
[diag3
(56a)
D,[Bu]
(56b)
Di[Bu] O
(56c)
Dy[Bul = [1
11 J
(56d)
mhk
D& 1TTA (VH)) |
11
T 1Dx Kr
(56c)
[
11 T
V 1
In(x)]
(56f)
m&
[[
11 I1 rdiag
(56g)
m&
2
Bss
(56h)
Dj IIT (V
[I
11 [
(56i)
m
[I
11 11 zz - F In(xx))
(56j)
m&
||
11 [
(56k)
Bgg-
(561)
We can derive the diagonal blocks of the Hessian as
Du[[(x)] = D. n; C(x)
(57a)
= 22, 1
The Billlras
(57b)
= =2(m Di Bij T V 1r]
Σ
nh Dj
(57c)
ktl
= 2 n [Di[Br]] 11
IIT
(57d)
+ Σ m [DtBar Hra ( + B D I
(57e)
= 2 n /diag3 ) 1 11 Ir ( + BiT Bul + Σ
nh BLB
(571)
my
= 2 rmdiag [
o UTa (V!)) + Σ m BBb
(57g)
24

---

Published as a conference paper at ICLR 2024
and the off-diagonal blocks as DiglC(0)] = D, x1 [(x)]
(58a)
2D E The I [
(58b)
L IIs + Σ n,Da (Bellra
(58c)
2 ml [M Ir
Byj Dg 11 [
(58d)
Σ ?k [D, BRi]
" ( + B Dg
(58e)
lepfl
2 m Bi Big +
Σ
mk [T (iihl
Ira V + BBg Bkgg]
(58f)
m&
lighl
Σ mh
Bkg
Bkg
Ne Tigh ITA VKTT
(58g)
kift
Therefore, the Hessian can be written concisely as
2 B + TIITT(V"))
(59)
where BR = BRs. (V) = [n (V!1) V.........
...., 7n ITlTT (V?)), and we augment T (the 3-player tensor approximation to the game, Tygx) so that Tis = rdiag3 (+) and otherwise 0.
25

---

Published as a conference paper at ICLR 2024
B GLOBAL CONVERGENCE GUARANTEES
In this section, we analyze the application of optimization techniques such as bandit algorithms and gradient descent our loss function.
B.1 MAPS FROM HYPERCUBE TO SIMPLEX PRODUCT
In this subsection, we derive properties map s from the untthhypereube the simplex product. This map is necessary to adapt our proposed loss L to the commonly assumed setting in the X-armed bandit literature (Bubeck et al., 2011) where the feasible set is hypercube. We derive relevant properties of two such maps: the softmax and mapping that interprets dimensions of the hypercube as angles on a unit-sphere that are then f--normalized.
Lemma 17. Let [(x) = -f(s(x)). Then (1V/ [I0T666))
Proof.
[V = (V(())))TTT((()))))) [1066)))
(60)
L
Lemma 18. The oc-norm of the Jucobian-transper of transformation s(x) applied elementwise product space is bounded by the 3c-norm of the Jacobian-transpos of a single transformation from that product space, i.e., [}](s 1ox0 I maX [|](s(z;)) 1o for any i.
Proof. Let E X IT== Xr 2 IT Z, and S X 2 [[<(11) ).: (xx)) where denotes column-wise stacking, H; E X. Also, X. = Xj and Z; = 2, all and j. Then the
Jacobian of S(x)
[s(Z1))
O... J(s(zz))
0
0
0
J(S()))
(61)
0
0 J(s(x.))
0
The co-norm of this matrix is the max 1-norm of any row. This matrix is diagonal, therefore, the co-norm of each elementwise Jacobian-transpost represents the max 1-norm the rows spanned by its block. Given that the domains, ranges, and transformations for all blocks are the same, their oc-norms are also the same. The max co over the blocks is then equal to the co-norm of any individual J(s Jss(x)))
B.1.1 HESSIAN OF BANDIT REWARD FUNCTION
Lemma 19. Let s(x) be function that maps the unit hypercube to the simplex product (mixed strategy space). Then the objective function f(x) = -[(((T)) The Hessian f(x) at an optimum
x" direction A Ax T T H=(x))D(x))] Ar where He the Hessian of and Ds(x) the Jacobian of s(x).
Proof.
amm"
Az) = Ax
d,((s(z) (2h, Ar
(62a)
+ Ar
Hc(x) ([(()(()))(()())
AT
Ax A Hc(x)) Ar.
(62b)
26

---

Published as a conference paper at ICLR 2024
Lemma 20. Let s(z) =
A be injective function, Lee, + = s(x) # s(y).
Also let J = (s)))) be the Jacobian of with respect to I and Ar be a nonzero vector in the tangent space of X. Then
JA + O.
(63)
Proof. Recall that the ijth entry of the Jacobian represents das so that the ith entry of JAx is D2j
[Ar]: = Σ Fz.
0s; Arj ds;-
(64)
Assume JAr = 0. This would imply change in r E X results in no change in (ds 0). contradicting the fact that s injective. Therefore, we must conclude the claim that JAr + 0.
Lemma 21. Let J [s(())) be the Jacobian of any composition of transformations 81 $1
where 5 (z) = / Σ3 Zglb. Then JAz lies in the tangent space of the simplex.
Proof. We aim to show JAx 0 for any Az and z. By chain rule, the Jacobian of is = [(s) = I== J(s)). Therefore, T JAr = 1 T= Az. Consider the first product:
((z)) =0 0
(65)
by Lemma 24
Therefore 1 JAr = 1
J())) O OT ( J())) 0.
This implies J Aa is orthogonal to 1 for any E X' and Ar, therefore J aa lies in the tangent space of the simplex for any X' and Az.
B.1.2 SOFTMAX MAP
Let [0, 1,4-1 Ad Fd be the softmax function. See (Gao and Pavel 2017 for analysis of many of its properties and in the context of game theory. Note that s maps a (d - 1) dimensional variable to d dimensional distribution. This can be practically handled by always appending a 0 to the (d - 1) di-mmennsoonal input prior to applying the standard softmax. We perform our analysis below in terms of the standard softmax, x, but note the norms derive apply to our modified (invertible) softmax.
Standard:
s(x)
21
(66)
Modified:
s(x) 1 ンラ
e
.1]
(67)
Lemma 22. Let be the Jacobian of the softmax operator. Then || S and ||J 1000 S 2.
Proof. Let S; represent the ith entry of S softmax(2) for any R.. Then the 1-norm of row i is upper bounded as
D,S: S: S₁)
(68a)
- Σ DyS.1 = Σ [S( - 5,)
(68b)
$ Σ So + +1SSS
(68c)
S, Σ S,S,
(68d)
S, S Σs,
(68e)
22,
(68f)
< 2 Vi.
(68g)
27

---

Published as a conference paper at ICLR 2024
Also, the 1-norm of column is upper bounded similarly
(69a)
Σ 1 Σ |S - S2)
(69b)
Σ Soy [S,8,]
(69c)
+ + Σ S.S,
(69d)
S + S Σ S.
(69c)
2S}
(69f)
Vj.
(69g)
The oc-norm of a matrix is the maximum 1-norm of any row. Therefore, ||J and || are both upper bounded by 2.
Corollary 3. Let J be the Jacobian of the softmax operator. Then ||]||2 - and ||JT 1|2 S 2.
Proof. The Gershgorin circle theorem states that every eigenvalue of J lies within one of the discs centered the diagonal of J with radius equal to the 1-norm of the row (excluding the diagonal term). The Jacobian of the softmax operator contains only nonnegative diagonal terms, therefore, the 1-norm of any entire row also represents the maximum magnitude of any eigenvalue allowed by any Gershgorin disc. In addition. // is symmetric and therefore, the magnitude of its eigenvalues are equivalent to its singular values. Therefore by Lemma 22
|| 22 2.
B.1.3 SPHERICAL MAP
For spherical coordinates, let s(x) n(((c(x))) where c(x) = T/ 7/2x, ((b) maps angles to the unit sphere, and n22) [z// Σg 2yls-
Definition 2. Define l(bb) as the transformation the unit-sphere using spherical coordinates:
4 (xb) = cos(1/1)
(70a)
12(()) = sin(V)) ) cos(1²2)
(70b)
la(v) sin(v)) sin(v2) cos(1bs)
(70c)
=
(70d)
1m-1 (v) = sin(w)) sin(V22 ... cos(e'm))
(70e)
(m)) sin(v11 sin(U22 sin(vm-11)
(70f)
Lemma 23. Let J be the Jacobian of the transformation to the unit-sphere using spherical coordinates,
i.e. z 1(1b where ||z]| and 4/2 E [0, 7 represents an angle for each i. Then |]]|e= S vm.
2
Proof.
The Jacobian of the transformation is
sin cos( w/n cos(
0 sin(v' sin((
0
J(()
cos(vi)) ) sin (122) cos (10mm cos()/1) sin(122) ... sin (1/m-1)
sin (1n sin (an(vim- sin Sin (1) sin(v)) ... sinn (mm-2) cos( 3' 1)
(71)
28

---

Published as a conference paper at ICLR 2024
and it square is
cos (1h) ) 1
) 22
J(O)
cos( e/1) ) sin (d2)) 2 cos (0mmm))))))
sin( )² ... sin sin((mm-2) 2) 2
cos( ) sin( (22 sin (0m(2mm-) 11)
sin(ti)) sin(v'm 2) )²t tm
(72)
where
pim 1 if m. else
(73a)
t = dim cos (v:-1) (1 6mm) ) (vn) S 1.
(73b)
To compute the Frobenius norm, will need the sum of the squares of all entries. We will consider the sum of each row individually using the following auxiliary variable Ri,s where Σ, J = R and apply a recursive inequality.
(74a)
Ricket
cos² (thke)
II 1=k
sin swnn(w))) coss(1bb)) + 4 II sin (wh)
(74b)
k-=k
= (1bk)
II
sin"(v2))
coss(('s))
(74c)
1=k+1
i-1
+ +sin?()bk)
Σ cos² cos?(1bxr) (thwr
II
sin?(wh) (1b)(1)))
(74d)
W=+++1
i-1
+ +sin?(
II
(1/2
(74e)
1=++1
< cos² (1bx(
(74f)
i-1
+ sin (win)
Σ cos² (1bbr)
II 1=t+1//
sin? cos (16) +
II sin sin(())) (74g)
k' k==++1
1=k+1
= =cos² (vix) + sin? s Ric+11
(74h)
Note then that R $ = Ra < 1. We know RA,; =t < 1, therefore, R²,1 S 1 by applying
the inequality recursively. Finally, E, J3 R S 1 implies the claim || = >; R S m. O
Lemma 24. Let be the Jacobian of n()) = 2/7 where 7 Ex 2k- Then 1 T OT.
Proof. The ijth entry of the Jacobian of nn(2 is
[n) = 7 ( (-24 + 2).
(75)
Therefore [1T = E, J(n),) 3/2 (-Z Z) 0 where is a point on the unit-sphere in the
positive orthant.
B.2 NEAR OPTIMALITY & ZOOMING DIMENSION
In this subsection, we derive bounds on the near-optimality dimension and zooming dimension of the associated bandit optimization problems use to derive global convergence guarantees to Nash equilibria. This is written in terms of maximizing a function rather than minimizing a loss to better
match the bandit literature (Bubeck et al. 2011 Valko et al. 2013 Feng al. 2022
29

---

Published as a conference paper at ICLR 2024
Assumption 1. Locally around each interior x² E X,, -f(x) is lower bounded by -f(x")
0-1|2 x= [1 other words, for all f(x) 2 f(x²) TT:
f(x") 2 0- --==11=>"p - 20
(76)
where we have left the precise norm unspecified for generality. Let E(xr 0+11x - x² 101aat.
Definition 3. X. dal ExE Ex* E x s.l. [(x) 2 [(x)) -c]
Definition 4. Xlower del for E Exx E x s.t. f(z") 0-1|z -----x111 x=1loni 2 f(x*) -c}
Corollary 4. X, Xlooer
Proof. By Assumption 1 - x"I|an 2 fz)). Therefore, any X' that satisfies the requirement for an element of Xe. f(x) 2 f(x*) c, will also satisfy the requirement for an element of X Plower
L
Definition 5 (i--ear Optimality Dimension). The vh-near optimality dimension is the smallest d' >> O such that there exists >> such that for any O, the maximum number of disjoint t-balls of radius th and center X. is less than Ce-d'
Definition (Zooming Dimension). The zooming dimension the smallest d, > such that there exists C₂ > O such that for any the maximum number of disjoint t-balls radius 2 and center in M16r is less than Cur-ds, -ss
Corollary 5 (Zooming Dimension from ve-na Optimality Dimension). The zooming dimension of f E [0, 1]" + [-1, 1] under E(z,y) 0+ |x yl (ooo is d2 d( 0tgOns
(21=0 with constant
C. 16-6 C with th 32 (t) is needed to compute C.).
Proof. Mapping the definition of vl-near optimality onto zooming dimension, we find a/e = r/2 and = 16r. Then infer vi 1/32; this is used to compute C' (see Theorem 1. Rewriting the bound from ne-a optimality in terms of r, we find
N. Ni S C(16r) C16-d Crr-da
(77)
where Niør denotes the number of f-balls of radius r/2 with center in Xiar, d, = d', C2 C16-d' Cl,-d, Therefore, this translation only effects the constant C., not the zooming dimension.
=
Lemma 25 (Nesn & Cesyt- The maximum number of disjoint l-balls with radius the and afor. and
center in Xegy Nes is upper bounded by Cesye-" where Cesn | (oo d' d( (h1=0ia)) Oio
Proof. The number of disjoint 8-balls of radius the and center in X can be upper bounded as follows.
Rewrite
X Xlower by rearranging terms
Plower {ir X' X s.t. || x 2011 11 ( 1/ams
re)
(78)
and recall that from Corollary that X. plower, Furthermore, an e-ball of radius the implies
(xx,v) 0 1 S thc || vl1 $ the
1/0 def
(-
rt-
(79)
30

---

Published as a conference paper at ICLR 2024
The number of disjoint b-blls that can pack into set Xe, Negn, is upper bounded by the ratio of the volumes of the two sets:
Vol(X.)
Nesa
(80a)
Vol(Be)
V Vol(X)ouer)
(80b)
Vol(Be)
|Sar
(80c)
Sart
d/ani
|280
(80d)
d/Oto
de 0+
1/2le 1) 1h
1/010 d é d(1/am-1/o1d
(80e)
1/ani
|x*1(
d/ain d(
Chi-Mte) alo
(80f)
v0
Cesnne
(80g)
d/aio
where Cesn 1
d'
d( ( ),
| is the number of distinct global
optima, and Sa is the volume constant for d-sphere under the given norm -|.
Recall, these results apply when f(x) 2 fx=)) i.e., when e S 17. Otherwise, we can upper bound the number of (-balls by considering the entire set X' which has volume 1, First, we will bound the constant associated with the volume of a d-sphere.
Lemma 26 (Nezn I Cezy). The maximum number of disjoint l-balls with radius the and center
d/0n. and Sa is the volume
in Xezw Nezv is upper bounded by Cezn where Cezg -ST constant for d-sphere under a given norm.
0+ 17
Proof. We can upper bound the number of ê-balls needed pack the entire space by considering the smallest possible radius thy..
Vol(X'
Nez
(8la)
(ol(
(81b)
Sarg
1
(81c)
d/ato
smn Sa
d/ato
ST
(++)
(81d)
vbm
C.zn
(81e)
where T1 was defined in equation
79
Theorem The v-near optimality dimension of f x E [0, + [-1,1] under is d' d( (15- with constant
C - max {1,5a'
(ri
oto
"As (ato ato
a+
d/ain
(82)
where Sa is the volume constant for d-sphere under the same
31

---

Published as a conference paper at ICLR 2024
1/ons
Proof. First, let us define inp
as in equation (78) which implies r7 o_rqu Then
apply Lemmas 25 (Nesn I C. Cesnne and 26 (Nezn S Cezn) which bound the number of E-balls required to pack X, when E less than and greater than 1j respectively:
Cesn = |1A7
0+
d/aio
(83)
aio/oni
100
d' d( Ohi (lo
(84)
and
Cezn -S 0+
d/ato
(85a)
=1x"1-1S_
d/ani d/010 0_
1 20 2lo//on
0+
d/ato
(85b)
|
d/oio o
d/an d/an+
(85c)
|
1
T
don' doni/aw d/aio o
dfans Cesn
(85d)
the -
The Mia) olo
||
Tq
ato σ_
Cesn
(85e)
(
(shi
|
TT
Cesn
(85f)
where Sa is the volume constant for a d-sphere under the given norm. ST has been upper bounded for the 2-norm in Lemma 35 For the oo-norm, SJ = 2 2-d, We have written C.zn in terms Cesn to clarify which is larger.
Therefore.
C max
ahi 1, 1,128-1-SS 152((1n0
(n, 1io
(ahi-ato) Pla
Cesn
(86a)
ahe 1io
(apemata "i
d/mio
max 111
rm
(86b)
Intuitively, if the radius for which the polynomial bounds hold (ry) is large and the minimum curvature constant o_ is also large, then the bound Cesn, holds for large deviations from optimality The number of rp-radius (-balls required to cover the remaining space, Cezy. will be comparatively small.
B.3 D-BLIN
The regret bound for Doubling BLiN (Feng al. 2022) was originally proved assuming a standard normal distribution, however, the authors state their proof can be easily adapted to any sub-Gaussian distribution, which includes bounded random variables. This matches our setting with bounded payoffs, so repeat their analysis here for that setting.
In what follows, in an effort to match notation in (Feng et al., 2022). let p(x) = (s)x)))) denote the expected reward for evaluating E [0, 11" (((z) is unbiased estimate of μ(x)). Here,
[0, 1)) - II, m is any function that maps from the unit hypercube to product of simplices; we analyze two such maps in Appendix B.I Also let Am denote the collection of hypercubes to be investigated during the mth batch of arm pulls, C' E Am denote a hypercube partition in X' nm indicates the number of times each cube in Am is played in batch m, and Broop denote the last batch.
Definition 7 (Global Arm Accuracy). E daf {lu(e) - Pm((C)) S Tm +
VOL
In Rm
1A 5 m
Bstop - 1, VC E Am, Vo cC.
32

---

Published as a conference paper at ICLR 2024
Define: 1m C2 7 rm
Im Vos I
Definition 8 (Elimination Rule). Eliminate E Am im pm 2 2(1 + va/e2) 2( + val I
where Pmm del maXCEAm Pm (C).
Lemma 27. Pr[E] 2r(8)21- 2T -11
Proof. Let (C) = 1 Ei= yc,, be the unbiased estimate of u(r E C*) using nm samples. Assume each yC,, E (a, with = b- and inC) inequality gives
1 Ei lCC.+ Applying a Hoeffding
Pr Pr[1a(C) - B[(()) 2 Va
In Tlm
S 2e
20, luT/C²
(87a)
= T) ) -201/62
(87b)
=27 202/2/ YC.
(87c)
By Lipschitzness of μ we also have
[B[A(C)] - u(z) S rm Ve C.
(88)
Then consider
sup =CC
[u(x) AiC))| sup
(u(x) E[((C)) + A(O)
(89a)
=EC
sup
(m(())) E[A(C)) [[([C M(I))
(89b)
aEC
sup (m(x)) E[A(C)]I (BA(() (C)
(89c)
=EC
In
+ Tm
(89d)
7mm
with probability 1 -2,-20 The first inequality follows by triangle inequality and the second follows from equation (88) and considering the complement of equation (87c.
The complement of this result occurs with probability
I
Pr sup [p(x) p(C)) 2 Pm + V c1 ZEC
< 2c,/2
(90)
7mm
At least arm is played in each cube C' E Am for 1 S S Bstop 1, therefore, [Aml < T must be true given the exit condition the algorithm. In addition, assume Bstop & T (Bstop will be defined such that this is true). Then a union bound over all T events gives
hT VCI
Pr 3m E [1, Bstop
11, C' Am s.t. sup (u(x) ((C) Tm sec
(91a)
7mm
Batap= 11
In
Σ
Σ
Pr sup (m(x) - ((C)) 2 I'
(91b)
Nmm
m=1
CEAm
Botop-1 Σ
2T 2T-20 20/02
(91c)
m=1
CE
< 27 2c1//2 T2
(91d)
Taking the complement of this event and noting that supzec (m(x) - MCC) S mm +
va LT
[p(x) jACC < Ym + v
I Vx E C' gives the desired result.
33

---

Published as a conference paper at ICLR 2024
Lemma 28 (Optimal Arm Survives). Under event E, the optimal arm x² arg max (xz) is nor eliminated after the first Bstop batches.
Proof. Let O denote the cube containing x² in Am- Under event &, for any cube C' Am and I E C, the following relation shows that O avoids the elimination rule in round m:
In T
(- pu(x)) + mm + Vai In
i(C)- i((m)) < (u(x)) + Tm + +V
(92a)
Amm
1mm
ln
(u(x) [u(x)))
+2r m + 2/ nmm
(92h)
50
In T
T
S 2
C2
+ 2
G1
(92c)
1mm
R'm
In T
= 2( + Vo2)
(92d)
where the first inequality follows from applying Lemma 27 to upper bound ((C) and A(C; indi- vidually.
The remaining steps use the optimality of x", the definition of r's and the elimination rule.
Lemma 29, Under event E. for any S m S Batop, any C E Am and any x E C, Ar satisfies
D S 4(1 CC1/c2)rm
(93)
Proof. For m 1, recall that I' is the side length of a cube C' E Am. therefore, A₂ S Tm-1
S
4(1 + V /////22) r holds directly from the Lipschitzness of μr.
Am be the cube containing x=. From Lemma this cube has not been eliminated under event E. For any cube C E Am and x E C, it is clear that & is also in the parent of C, denoted Cpar (x E C C Opar). Then for any x E C, it holds that
For m 1, let - E
IT
Ag = p(x*) - -u(I)= S (mm-1(Cmm-)) + -m-- +
(94a)
7m-1
(- Amm-1(Cparr + +m-1 +
In
7m
ln
- = (pm-1 - (C + 2(vc21 + vo2)
(94b)
Rm-11
In
S (pmax pm (C + +2(VV (V2))
(94c)
nm=-1
IT
In
< 22(V0 + )02)
+ 2(( + +(2)
(94d)
7m-11
7m-1
ln
=4(Vc1 + Vo2)
(94e)
1mm-1
4(11 + (a//2))mm
(94f)
where we have applied Lemma 27 similarly as in Lemma 28 and also used the definition of I'm
The last two inequalities use the fact that 1C
S paaer and Cpar was not eliminated. L
Theorem 2 (BLiN Regret Rate). With probability exceeding 1 2 2/e1/0 -1) the T T-step total regret R(T) of BLiN with Doubling Edge-length Sequence (D-BLiN) Feng et al. (2022) satisfies
R(T) S 8(1+ (22)) a d+t1
(95)
where de is the zooming dimension of the problem instance. In addition, D-BLiN only needs more than B log 2(T) ((CTT))oooo0 ((m(TT) + 2 rounds of communications achieve this regret rate.
d.+2
34

---

Published as a conference paper at ICLR 2024
Proof. Since mm implics that every cube C' Am is a subset of S(8(1 + rm) Thus from the definition of zooming dimension (Corollary) with appropriate condition), we have
mm-1 2m for the Doubling Edge-length Sequence, Lemma 29
Am S Nrm Carme
(96)
Fix any positive number B. Also by Lemma 29 we know that any arm played after batch B incurs regret bounded by 8(1 + / /e// /1/e2)rB since the cubes played after batch B have edge length no larger than rg. Then the total regret that occurs after batch is bounded by 8(1 + /2 (where I is an upper bound on the number of arms).
Thus the regret can be bounded as
R(T) S
Σ m=1 CEAm i=1
Dec, + 811 + V
(97)
where the first term bounds the regret in the first batches of D-BLiN, and the second term bounds the regret after the first B batches. If the algorithm stops at batch < B. we define A. for any B < m < B and inequality equation (97 still holds.
By Lemma we have Arc, & 8(1+ v for all C E Am- We can thus bound equation (97
by
B
R(T)= S
Σ
Aml nm 8(1 va/e2)r + +8 Vale22rBT
(98a)
B
Nrm nm 8(1+ (a//22m + +811 TTT
(98b)
m
B
In
Nrm
C2
8(1 Va/22)) +8 Va/e2)rl
(98c)
r2
m=1
B
T
Σ
N
80 va/e2) + 8(1 Va
(98d)
I'
where equation 98bb uses equation (66, and equation 98ch uses equality nm = 0 72 Tm = 2 mm
IT
Since
and Nr... < Crr-d < C22 2 mm 1)d, we have
B R(T) < Σ m=1
In
C. 2(m-1)d
80,(1 vai/2) + 881 2- B+1T
(99a)
2-m+1
= 8(1 Va/oz)
C2 I
2 (m- 2mmm1)(d++1) + --
(99b)
35

---

Published as a conference paper at ICLR 2024
Continuing find
B C2 IT R(T) s 8(1 Val/o2)
Σ
(m--))(d+t)) + B+11
+2-B+11 (T]
(100a)
m==
=8(1 + 8(1+ V2/02)
C2 hT
(2 m- 22 2-B+IT
(100b)
B
8(1+ 222)2
hT C2C, InT
12 mh + 2- +2-B++1 B+IT]
(100c)
BBd +1)
-11 + 2- Bttg]
8(1 22/02)
C2C ln
via geometric series
(100d)
2d,+1
2B(d++1)
$ 8(1 + /2
C2C, lT
+2 B+1T T|
(100c)
2d.t1
2B(d,+1)
s 8(1+ + 21)
C2C, In
+2 -2-B+IT
(100f)
2dst1
-((1 + 212))
20 2 (B-1) In + 2 (8-
(100g)
log, - d.
This incquality holds for any positive B. By choosing 8 1
we have
R(T) s 8(1 + 022)
C02C.
T
2
T
In T
Tas
(101a)
88(1 + (22))
2cyC, (4
(d=-1)
IT
+ T
( In 1
(101b)
(d++t)
= =811 c/2/2)
202C,
In T [لل
+1 dd
In (d
(101c)
(d==1)
=811+ Va/22) (2cc 1)7 ds In TW.
(101d)
Corollary 6 (BLiN Regret Rate Refined), Setting 01 = 2c² and C2 = 2 10,
2/3 simplifies Theo-
rem 2 such that
R(T) s 8(1 + (432 ta. In T
(102)
with probability 1 -7
2/3
then Val/22 of 1C=
1/3
(AeC:) 1/3
Proof.
If set e₁ 2c² and C2 2
T0.
202C2.
Lemma 30. The zooming dimension and zooming constant under the l(x, y) = ||0 - ylloo norm are
dg 2 niTt
(103)
nm
C, |
(104)
where a-c0 =||Hess(-f((())1 is an upper bound on the infinity norm of the inverse Hessian matrix of the function every equilibrium.
Proof. Recall from Theorem that d: d( Cth -aie with constant C₂ = 16-d' d' C where defined
below. In addition, BLiN assumes E(x, y) = I ylloo. Matching to Assumption I 0. Gio = 1. Under the infinity norm, the volume constant S2 2d
we see that
We will define the other constants with respect to properties of the Hessian of f(x about each equilibrium, specifcclll the infinity norm of the inverse Hessian that a-oc- This means
36

---

Published as a conference paper at ICLR 2024
will bound the function locally with quadratic, i.e., ats 2. Lastly, recall from Corollary that vp = 32 and the dimension of our search space (the product space player mixed strategies) is d nm 1) S nm for simplicity.
Plugging this information into Theorem
we find
1 d2 = d'
mm
(105)
2
and
C max
11,12*1115;
(1)
2to
chi-aio
d
0+
d/aio
(106a)
1o
max
{1,1209 1226
-0000000
d
32
(106b)
1/2
max
11,12-11 (2 -00
32
(106c)
1/2
-00
hard
12201-1 (2-20
-d
32
-00
1/2
(106d)
-00
hard
12"1--1
16
nm
(106e)
where hard indicates we are assuming Ty and a-c0 are small enough to dominate the other operand of the max.
Finally, converting the near optimality constant to a zooming constant, we find
16
C. = 16 de
X
(107a)
72000
-1801112
4
(107b)
000
B.4 BOUNDED DIAMETERS AND WELL-SHAPED CELLS
We assume the feasible set is unit-hypereube of dimensionality d where cells are evenly split along the longest edge to give new partitions and Th represents the center of each cell.
There exists decreasing sequence w(h) 0, such that for any depth h 2 0 and for any cell Xr.s of depth h, we have supzer'. (( x) S wh)).. Moreover, there exists 2 O, any cell Xn, contains an f-ball of radius vw(h) centered at Th,1-
such that for any depth
((x,y)
7
f(x, v) || v|
dm/2 b
b b-a/d
d d/a226 2n
((x,8) 3) = ||x
bb
b-a/d
b b-2a 20
Table 3: Bounding Constants: sup supaex,. (x)hi, S w(h) cg.h
B.4.1 L2-NORM
Lemma 31 (Lg-Norm Bounding Ball). Let {(x,8) || - -111.. Then supaexh, {(zh,,,) S w²(h) cg where
dbb a/2 and 7 b-a/d
37

---

Published as a conference paper at ICLR 2024
Proof.
d w(0) = 1 (1/2)3) a/2 = =(4)a/2
(108a)
==1
w(1) [1/b 102)) + Σ
(1/2)870012 (1/4)))1/4) + +d - ()(144))o/2
(108b)
i=2
1 1+ 1/b² )a12
(108c)
d
w(d) = 12
(1/b. 1/2))//2 = 4. 12
a0/2
(108d)
t=1
w(h) = (r(1/b) (1/2)² Σ (1/6)
(108e)
(1/2) + (d (d- a/2
(108f)
[0/68)(144(44<(( 1 ))] 1] a/2
(108g)
< [11/8))(144)d 9/2
(108h)
< [01/8)//6-11444dd a/2
(108i)
(1163))//(12/4444) a/2
(108))
db2 0/2 (1/b)**
(
(108k)
= Ca
(1081)
where q,r divmoo(h, d) = q 2 h/d 1, 1, = =(4t²) ( and 7 = (1/b)a/d = b-a/d
Lemma 32 (Lg-Norm Inner Ball). Let f(x, v) || --1BB- Any cell Xn,s contains an E-ball of radius (w) where v= = (dbb))-a/2
Proof. Any cell My,s contains an 8-ball of radius equal to its shortest axis:
Tmin = [11/4)11/B) [B//4)(1//8))////]))))
(109a)
> [1/4)
(109b)
R..4 a/2 (1/b)*h
(109c)
w(h) (1)1 )a/2
(109d)
B.4.2 -NORM
Lemma 33 -Norm Bounding Ball). Let f(x, v) = || - -vlo- Then sup (xn,)r)) S (h)(h) = =h where e = (b)) and 7 b-a/d
Proof. Any cell Xh.s is contained by an E-ball of radius equal to its longest axis:
Tmax = [CL/4)
(110a)
s [(1/A)(1/83//4-1]]0
(110b)
a/2 (1/6) nh
(110c)
=cg/
(110d)
38

---

Published as a conference paper at ICLR 2024
where e ( // / and 7 (1/0)a/d=1)) b-a/d.
Lemma 34 (o Norm Inner Ball), Let ((2,)) =|1x -oll. Any cell &n, contains an l-ball of radius 20 (h) where v= b-2a.
Proof. Any cell 2 contains 8-ball of radius equal to its shortest axis:
[(/4))11/B3))))|]]) a/2
Tmin
(11la)
2 (1/4A((/63)4/444))g))
(111b)
=
a/2 (1/b)
(111c)
B. .4
w(hh) 1 0/2 00/2
)
(11ld)
B.5 STOCHASTIC SIMULTANEOUS OPTIMISTIC OPTIMIZATION
StoSOO is flexible in its choice of metric and partitioning structure. In StoSOO, may choose ((z, y) = || y112-
Lemma 35. The volume of a d-sphere with radius and d even is given by Sar where S I d/2
2
d
2
Proof. First, recall Stirling's bounds the factorial: /2mn( ( e 12n4I < n! < 22 " This will be useful for bounding the Gamma function: I'(d) (d 1)! for even d.
Given d even, we start with the exact formula for Sa:
T(d/2+1)
S
(112a)
7d/2
(d/2)!
(112b)
24/2
(d/2) 2/22d/22 rad//a)
(112c)
Td/2
1/2221/2
2d/d22 edt
(112d)
md/2
12
(112c)
d/2
d
d/2
S /2rd
(112f)
2Tee
Lemma 36. The near optimality dimension and constant under the ((x,)) = ||x - -yl norm are
= 0
(113)
= 1--1111 2mmm
VATEL
mm//2
(114)
3vr3o-2
where 0-2 is lower bound the singular value of the Hessian matrix of the function at every equilibrium and v is defined in Table for the corresponding E(x, bbll.
Proof. Recall from Theorem that d' = d( (Dhi-Ola) ) with constant C' defined below. In addition, 01o0hi
will analyze StoSOO with the choice f(r, y) || v112- Matching Assumption 1
39

---

Published as a conference paper at ICLR 2024
4/2
that 0+
and oio 2. Under the 2-norm, the volume constant S S /2rd
d 2
(see
Lemma 35
We will bound the function locally with a quadratic, ie., Ohya = 2. Lastly, from Valko et al.
2013
Corollary 1), vi - with y . defined in Table 3 and the dimension of our search space (the product space of player mixed strategies) is d = n(m 1) I nm for simplicity.
Plugging this information into Theorem
we find d' 0 and
C' = max
1,120'11s ST (1)
abe oio
The (ie)
-d
o+
djato
(115a)
max
1, 1, S 11
d
d/2
(115b)
V0
hord
d/2
(115c)
12
hord S 1 2
d
d/2
3
d/2
(115d)
2Te
ur
0-
hard
b²d
d/2
12 2
(115e)
5r -2
hard [x -1
|x 1111/22nn
n2 mm2 2
mm/22
(115f)
5
where hard indicates we are assuming I',, the radius of the ball under which the local polynomial bounds are accurate, is small enough to dominate the other operand of the max.
Theorem (StoSOO Regret Rate). Corollary 1 of Valko et al. (013)) implies that with probability 1- 8, the regret, R₁, of StoSOO after t pulls is upper bounded as
logo (tk/8)
(2 + b2/d)
V
=1b2(1+2/00 de Va/k
(116)
2 [l)g,e))k
where 11m b is the branching and k is the maximun number of evaluations per node.
faatiingnfaatooo factor for partitioning cells, C is the near-optimality constant,
Proof. Plugging the constants c, 7, and v defined in Table for the 2-norm into Corollary 1 of Valko al. 2013). we find with probability 6:
R₂ $ (2+ 1/7)c + cy to 2
(117a)
(2+ 1/7))
log(Uk/0)
+ + Vefk-2
(117b)
2k
log(th/0)
(2+ /
db²(b (0-(b-2//) 22d Vi/k-2
(117c)
2k
4
(2+ + /
(tk/))
1
21+ (b (6-2/d) a viTk
(117d)
logg(e))
(2+ )
logg, (1k/8)
212(1-2/00 ao Vifk
(117c)
loog (E)k 4
Proposition 2. Assume the same conditions as Theorem 3 and let k = flogg(t) where p 2 3. Then the StoSOO (Algorithm of Valko al. (2013)) bound requires i 002 pulls before exhibiting (T-11/2) decay in regret.
40

---

Published as a conference paper at ICLR 2024
Proof. We know from the given definition of & that vt/k (t)r/2 We will analyze the second
term in the regret formula of Corollary 3 Note that the second term, b- de vefk (bVl/K)- de
(b"0,, y-
(blog,(t) (o). 2//2 ) -c
21/2
Jogy (0)60-22222//2 de
To
achieve a 1-112 convergence rate (or better), we need & 2 b( For convenience, we report the entire simplification of the bound below:
R₂ (2 /
logo (1k/8)
logs (e)k + db 2bb(1+2/003 to V1/k
(118a)
(12/(6 logo (12 /6 log, (()))) (1) 2log((e)
1 =112(1+210) (0 4
(2 +2+ 1
2c
(118b)
logo (t2 /0) logo (t/8)²
+ 1 -db2(1-210)
(1)a 22/2
S 52+ 1
(118c)
2 2logs
loga (1/5)0t1
1os 21/2 + 2b2(1+2/144
(2 1
(118d)
2log((e)
(2 + 12/4)
logo (4/8)(0+1)/2
+ (1)
21)2(1+2/d))
(118e)
(e)
Vt
(2 12/4)
(1) log, (8) (0))(222)22
t0 21/2
(1-211)
(118f)
/ (e)
B.6 REGRET TO PAC BOUNDS
Lemma 37. [Loss Regret to Exploitability Regret] Assume exploitability joint strategy is upper bounded by ((T(x) where f is a concave function and L is a loss function. Let æ; be a joint strategy randomly drawn from the set of predictions made by online learning algorithm A over T steps. Then the expected exploitability of a is bounded by the average regret of A:
Edlel S R(T)).
(119)
Proof.
E, [e]] = (.(f(((x))) & ((E,((())))
= f( Σ ((a))) E
-
s(
(120)
where the inequality follows from Jensen's 's inequality.
Theorem 4 (BLiN PAC Rate). Assume 17 = 1j 2/ as defined in Lemma 2 t
lm(1pp) so that all
equilibria place at least P. mass on each strategy, and a previously pulled arm is returned uniformly al random (i.e., (T)).. Thenffor any w 0,
6 w ( [lo (II
In mg + 2(1 (333 2n 202x22) +2)
(121)
T
with probability (1 -- 2) where m max; Mi, and
S nm 1.
In(m") ) In(l/p) + is an
upper bound the range of E (Corollary 11 i [In(m")
[i((1/)) +2)
m
+ mm
(Corollary
2 the
p pln(1/p)
nm (Corollary 301
zooming dimension d= = 1 nu,, and the zooming constant C- = | P70-
41

---

Published as a conference paper at ICLR 2024
Proof. Assume 7/2 1 = 7 defined in Lemma so that 2 is 1-Lipschitz with respect || |lac-
Also assume previously pulled arm is returned uniformly at random. Starting with Lemma 13 and applying Corollary 6 we find
E(er] S T log II mz +
T Σ (T(z)
(122a)
mink 77k
< 1n(1/p)
log II mi + nLv 8(1 (462)1/8797 (as In T
(122b)
log II mp
+2(1+ (4c2 /222nni
In
2((2+
(122c)
ln(1/p)
T
with probability - 27 where m = max my, and c <
min
In(m" In(1pp) +2)
is an upper bound on
the range of sampled values from L (see Corollary
Markov's s inequality then allows us to bound the pointwise exploitability of any arm returned by the algorithm as
T T
4 5 w In(1/p)
log II mg) + + + (482)
V 2n
(123)
with probability (1 w--)(( 2) for any w
Theorem 5 (StoSOO PAC Rate), Corollary of Valko et al. (2013) implies that with probability (1 (1-w" w1-w-116 (1- 8) for any w > 0, a uniformly randomly drawn arm (i.e., ~ U(TT)) achieves
6 S ln(1/p) log
mh
+ mL
Ei
loga (Tk(o)
2 2oo (e)k
+ Eab do vTykk
(124)
where d = nmm-1) & = (2+22/4), E2 abb k = 7 (lgg b is the branching factor for partitioning cells, and the near-optimality constant C | 2
(T)
d/2
2md
(Lemma 361.
br
Proof. Assume π7 17= = 2 as defined in Lemma Also assume previously pulled arm is returned uniformly at random. Starting with Lemma 13 and applying Theorem and Lemma 37 we find
E[e] S + log [[ mk +
2n
(x(
(125a)
min& Mh V
loga (Tkk0)
log II mz) + ní VnEEe
+ Egb - de VT/k
(125b)
ln(p/)
2 log (e)k
with probability 1 where m maxę My, = nmm- - 1), & = (2 + 22/d), E2 4 (12+2/4
T Tlog, (T) 3 is the branching factor for partitioning cells, and the near-optimality constant x C 1=12- d 3
d/2
62d2
(Lemma 36
Markov's 's inequality then allows us to bound the pointwise exploitability of any arm returned by the algorithm as
(Tk/o) log, (e)k fab do VT/KK
6 S In(1/p)
log II mk
Vnl, E1
(126)
with probability (1 -1) 5) for any 0.
42

---

Published as a conference paper at ICLR 2024
B.7 COMPLEXITY OF POLYMATRIX GAMES
Lemma 38. For polymatrix game defined by the set of bimatrix games with payoff matrix Pii for every player k and 1 + k. the rank of the matrix M (x) defined in equation 11) can be equivalently studied by replacing all instances of H with Pi--
Proof. Consider the polymatrix game given by the set of matrices P for every l and 1 + k. The polymatrix game can be equivalently written in normal form, albeit. less concisely. Note that the polymatrix approximation, H as we have defined it (see Section Preliminaries) of this normal- form representation between players and with all other players" strategies marginalized out related to the true underlying bimatrix game between them as follows:
H [ax, ai] = Ex -kl [uu (ax, at, x x-)] Vax, az
(127a)
= 0 (Paar= +
E Pkjzzs)
Vag. ai
(127b)
jRik
=0 .gk phaa + og
Σ
Phames
Vak: d4
(127c)
(E(N.)
where Phi is player k's payoff matrix for the bimatrix game between players k and / in a polymatrix game and pk does not depend on player I's strategy.
This implies that H is equal to Ph up constant offset of the rows, i.c.,
H PH + Cs
(128)
where Cs is matrix with constant rows.
Consider the matrix (xx which contains H blocks. Recall that the bottom rows of (xx) contain rows of I's matching each column of H& blocks. Consider multiplying the ith row of I's (which contains O's on all columns not the Ith block) by vTklI- block containing /T
1 1 JC& and subtracting it from the ma
ma 1, H
1 11 m7
1 I
C&)
(129)
mc
my 1, still remains matrix with constant rows (the preconditioner effec- tively subtracts a constant matrix from Cj). This multiplying and subtracting a row from another an elementary operation on the matrix. meaning does not change its row rank. Therefore, for a polymatrix game, we can reason about the positive definiteness of the Hessian at equilibria by examining the matrix ((x) with all H swapped for Pk: ss
Note that TTLl 1
11
Interestingly, at zero temperature (where QRE Nash), M is constant for polymatrix game, so the rank of this matrix can be computed just once to extract information about all possible interior equilibria in the game. Furthermore, the Hessian is positive semi-definite over the entire joint strategy space, implying the loss function is convex (see Figure (left) for empirical support). This indicates, by convex optimization theory, 1) all mixed Nash equilibria in polymatrix games form convex set (i.c.. they are connected) and 2) assuming mixed equilibria exist, they can be computed simply by stochastic gradient descent on C. If A is rank-nm,, then this interior equilibrium is unique.
Complexity Approximation of Nash equilibria in polymatrix games is known to be PPAD- hard (Deligkas al., 2022). In contrast, if we restrict our class of polymatrix games to those with at least one interior Nash equilibrium, our analysis proves we can find an approximate Nash equilibrium in deterministic, polynomial time (Corollary(7) (7). This follows directly from the fact that L convex, our decision set X I X is convex, and convex optimization theory admits polynomial time approximation algorithms (e.g., gradient descent). We consider the assumption of the existence of interior Nash equilibrium to be relatively mild" so this positive complexity result is surprising.
shows 2-player, 2-action polymatrix games with interior Nash equilibria make up non-trivial 1/4 of the space of possible 2 2 games.
Marris al. 2023
43

---

Published as a conference paper at ICLR 2024
Also, note that the Hessian of the loss Nash equilibria is encoded entirely by the polymatrix approximation at the equilibrium. Therefore, approximating the Hessian C about the equilibrium (which amounts observing near-equllibrum behavior (Ling et al. 2018)) allows one recover this polymatrix approximation (up to constant offsets of the columns which equilibria are invariant to (Marris al. 2023)).
Corollary (Approximating Nash Equilibria of Polymatrix Games with Interior Equilibria). Con- sider the class of pelymatrix games with interior Nash equilibria. This class of games admits a fully polynomial time deterministic approximation scheme (FPTAS).
Proof. Lemma relates the approximation of Nash equilibria to the minimization of the loss function [(x)). By Lemma [ this loss function attains minimum value of zero if and only if Nash equilibrium. For polymatrix games, the Hessian of this loss function is everywhere finite and positive definite (Lemma[T6) T6), therefore, this loss function is convex. The decision set for this minimization problem is the product space of simplices, therefore it is also convex. Given that only consider polymatrix games with interior Nash equilibria, we know that our loss function attains global minimum within this set. By convex optimization theory, this function minimized in a polynomial number of steps by. for example, (projected) gradient descent (Boyd and Vandenberghe 2004). Gradient descent requires computing the gradient of the loss function each step. From Lemma 14 we see that computing the gradient (at zero temperature) simply requires reading the polymatrix description of the game (i.e., each bi-matrix game H between players), which is clearly polynomial in the size of the input (the polymatrix description). The remaining computational steps of gradient descent (e.g., projection onto simplices) are polynomial as well. In conclusion, gradient descent approximates a Nash equilibrium in polynomial number of steps (logarithmic if strongly-convex (Mairal 2013)), each of which costs polynomial time, therefore the entire scheme is polynomial.
be approximately
44

---

Published as a conference paper at ICLR 2024
C EXPERIMENTAL SETUP AND DETAILS
Here we provide further details on the experiments.
C.I GAMBIT
The seven methods from the gambit (McKelvey et al., 2016) library that tested on the 3- player and 4-player Blotto games are listed below (with runtimes). Only gambit-enumpo -ewpitteeumpoolo ly and -embitee are able return any NE for 3-player Blotto within hour time limit (and only pure equilibria). And only gambit -emuitte returns any NE for the 4-player game.
gambit-enumpol [73 see 3-player, timeout 4-player]
gambit-enumpure [72 sec 3-player, 45 sec 4- 4-player]
gambit-gnm
gambit- -ipa
gambit-logh
gambit-simpdiv
C.2 Loss VISUALIZATION AND RANK TEST
Figure 3 and claims made in Section 5 analyze several classical matrix games. We report the payoff matrices in standard row-player column-player payoff form below. All games are then shifted and scaled payoff' lie in [0, 1] (i.e., first by subtracting the minimum and then scaling by the max).
RPS:
0/0
-111
1/-1
1/-1
0/0
-1/1
(130)
-1/1
1/ 1/-1 0/0
Chicken:
0/0
1111
(131)
1/-1 -3/ -3
Matching Pennies:
1/ 1/-1 -1/1
(132)
-1/1 1/-1
Modified-Shape -hapleey:
1/ - 0.5
0/1
0.5/0
0.5/0
1/-0.5 0.5
0/1
(133)
0/1
0.5/0
1/-0.3 0.5
Prisoner's Dilemma:
-1/ -
-3/0
(134)
10--3 -3
-2/
45

---

Published as a conference paper at ICLR 2024
C.2.1 Loss ON FAMILIAR GAMES
We visualize our proposed loss L on two classic 2-player, general-sum games: Chicken, payoff matrix (31), and the Prisoner's Dilemma, payoft matrix (I34). Each plot in Figure 5 visualizes the loss at various strategy profiles in probability-space; each strategy profile is represented by each player's probability of playing action of 2 (top row / first column of payoff matrix). Temperature varied across the plots. Figure repeets this same visualization but in logit-space to better show the equilibria closest to the boundaries.
ref/cT/vhh
c.f 2T 3222-100
Rayer Nowewee
Payer Nndewwen
Maye Trokshere
Rayer Pesewend
Rayer Pralwaoee
Figure 5: Upper Bound (+(CT) Heatmap Visualization. The first row examines the loss
landscape for the classic anti-coordination game Chicken (Nash equilibria: (0, 1), (1,0), (2/3, 1/3))
while the second row examines the Prisoner's dilemma (Unique Nash equilibrium: (0, 0)). For improved visibility, we subtract the offset (m²² from (2") per Lemma 13) which relates the exploitability at positive temperature to that zero temperature. Temperature increases for each plot moving to the right. For high temperatures, interior (fully-mixed) strategies are incentivized while for lower temperatures, nearly pure strategies can achieve minimum exploitability. For zero temperature, pure strategy equilibria (e.g., defect-defect) are not captured by the loss illustrated by bottom-left Prisoner's Dilemma plot with a constant loss surface.
reficia 1030
exdieh 6111 125x100
eedict a
Mayr [uyiteeest
Noe Lagibadd
Mayer Buyilayleeee
LapisCopenttll
(Coppetts
Lughttapperss
LagisCeenennt
Figure 6: [Figure 5 Repeated in Logit-Space (In( (2,)) Rather than Sabbability-Spacee (p)) Upper Bound (e S (r( Heatmap Visualization. The first row examines the loss landscape for the classic anti-coordination game of Chicken (Nash equilibria: (0, 1), (1, 0), (2/3, 1/a)) while the second row examines the Prisoner's dilemma (Unique Nash cquilibrium: (0, 0)). Temperature increases for each plot moving to the right. For improved visibility, subtract the offset log(m²) from f. (CT) per Lemma 13 which relates the exploitability at positive temperature to that at zero temperature. For high temperatures, interior (fully-mixed) strategies are incentivized while for lower temperatures, nearly pure strategies can achieve minimum exploitability. For zero temperature, pure strategy equilibria (e.g., defect-defect) are not captured by the loss as illustrated by the bottom-left Prisoner's Dilemma plot with a constant loss surface.
46

---

Published as a conference paper at ICLR 2024
C.3 SADDLE POINT ANALYSIS
To generate Figure 2 we follow procedure similar to the study of MNIST in (Dauphin et al. 2014) (Section 3 of Supp.). Their recommended procedure searches for critical points in two ways. The first repeats randomized, iterative optimization process 20 times. They then sample one these 20 trials at random, select a random point along the descent trajectory, and search for a critical point (using Newton's 's method) nearby. They repeat this sampling process 100 times. The second approach randomly selects a feasible point in the decision set and searches for critical point nearby (again using Newton's 's method). They also perform this 100 times.
Our protocol differs from theirs slightly in a few respects. One, we use SGD, rather than the saddle- free Newton algorithm to trace out an initial descent trajectory. Two, do not add noise strategies along the descent trajectory prior to looking for critical points. Thirdly, we minimize gradient norm rather than use Newton's method to look for critical points. Lastly, we use different experimental hyperparameters. We run SGD for 1000 iterations rather than 20 epochs and rerun SGD 100 times rather than 20. We sample 1000 points for each of the two approaches for finding critical points.
C.4 SGD CLASSICAL GAMES
The games examined in Figure were all taken from (Gemp al. 2022). Each is available via open source implementations in OpenSpiel (Lanctot et al, 2019 or GAMUT (Nudelman et al. 2004).
We compare against several other baselines, replicating the experiments in (Gemp al. 2022). RM indicates regret-matching and FTRL indicates bollow-the-regularizee
These are, arguably, the
two most popular scalable stochastic algorithms for approximating Nash equilibria. " "QREsaoo is stochastic algorithm developed in (Gemp et al. 2022).
For each of the experiments, we sweep over learning rates in log-space from 10-3 3 102 in increments of 1. We also consider whether to run SGD with the projected- -ogjecee-gradient and whether to constrain iterates to the simplex via Euclidean projection or entropic mirror descent (Beck and Teboulle 2003). We then presented the results of the best performing hyperparameters. This was the same approach taken in Geep et al. 2022).
Saddle Points in Blotto
To confirm the existence of saddle points, we computed the Hessian of oo), deflated the matrix by removing from its eigenvectors all directions
[( for SGD orthogonal to the simplex, and then computed its top-(nm n) eigenvalues. We do this because there always exists a n--imensional nullspace of the Hessian at zero temperature that lies outside the tangent space of the simplex, and only care about curvature within the tangent space. Specificaly, at an equilibrium æ, if we compute z Hess( (C)= where 2 is formed as a linear combination of the [0....,.., _T, F.,] then each block B& is identically zero at an equilibrium: Bus = VTLl / - 11 H R = VTh IT (Vk 22 = 0. By Lemma 16 this implies there is zero curvature of the loss in the direction 2: (Csss()== 0.
vectors {|01, 0, 0 O
C.5 BLIN ON ARTIFICIAL GAME
To construct the 7-player, 2-action, symmetric, artifical game in Figure we used the following coefficients (discovered by -nd--ord-error):
00.09906873
0.23116037
0.62743528
0
0.19813746
0
0.33022909
0
0.03302291
0.62743528
(135)
The first row indicates the payoffs received when player plays action and the background population plays any of the possible joint actions (number of combinations with replacement). For example, the first column indicates the payoff when all background players play action 0. The second column indicates all background players play action 0 except for one which plays action 1. and so on. The last column indicates all background players play action These 2n scalars uniquely define the payoffs of a symmetric game.
47

---

Published as a conference paper at ICLR 2024
Given that this game only has two actions, represent mixed strategy by a single scalar p [0, 1], ie., the probability of the first action. Furthermore, this game is symmetric and we seek symmetric equilibrium,
represent a full Nash equilibrium by this single scalar p. This reduces our search space from 7 x 2 = 14 variables to variable (and obviates any need for a map from the unit hypercube to the simplex- see Lemma 22
48


Reviews:
[{"review_id": "KHqgsxIR9E", "reviewer": "Reviewer_MRwi", "summary": "The paper provides a loss function for computation of approximate Nash equilibria in general-sum multiplayer matrix games for which unbiased estimators can be constructed. This allows the exploitation of stochastic optimization algorithms for computation of Nash equilibria in general matrix games. They provide numerical evidence that this approach is competitive with existing approaches.", "questions": "1. There is a typo in the definition of the projected-gradient (it should be $\\Pi_{T\\delta^{d-1}}(z) = z - \\frac{1}{d} \\mathbf{1}^\\top z \\mathbf{1}$)\n2. In Section 6, it is confusing to introduce SGD first and then the bandit algorithm and then immediately have a subsection discussing the bandit algorithm, especially since it is stated that \"in the next section, we find it performs well empirically in games previously examined by the literature.\" Perhaps it makes sense to include the SGD experiments before any discussion of the bandit approach.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is generally well-written.\n2. The formulation of the loss function which allows for unbiased sampling is a solid novel technical contribution. As the authors note, this is a step towards enabling computation of Nash equilibria in large-scale settings (in spite of theoretical hardness results), which is quite important for operationalizing game theory in the real world. \n3. The paper provides numerical evidence supporting that the loss function is \"easy\" to optimize in many benchmark games of interest, and that it is competitive with other SOTA approaches.", "weaknesses": "1. The empirical section (6.2) could use some additional explanation/discussion. The baselines that are compared against should be explicitly stated in the body text (and cited appropriately) instead of just stating that they are the baselines used in Gemp et al. 2022's simulations.\n2. The flow of Section 6 generally could be improved (one suggestion is provided below).", "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": "IZU5tQs6LN", "reviewer": "Reviewer_rSdL", "summary": "The paper proposes a new loss function for approximating Nash equilibria in normal-form games. The key idea is that the loss function can be unbiasedly estimated through Monte Carlo sampling of the joint strategies. This allows the use of stochastic optimization, eliminating the need to read all the payoffs, which would be exponential with respect to the number of players.\n\nThe loss function upper-bounds the exploitability of an approximate equilibrium. The authors prove this both theoretically and empirically. This approach enables the scaling of equilibrium computation to larger games than previously thought feasible. Experiments are conducted on games with up to 286 actions.\n\nTwo algorithms are explored: vanilla SGD and a bandit-based method. The bandit algorithm comes with theoretical guarantees regarding exploitability.", "questions": "1. How well does the approach scale to larger real-world games with structures like symmetry? Are techniques such as grouping actions necessary?\n2. Have the authors attempted more advanced optimization methods like Momentum SGD or Adam to address saddle points?\n3. What heuristics could be employed to guide equilibrium selection when multiple equilibria exist?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a new loss function for approximating Nash equilibria in normal-form games that is amenable to unbiased Monte Carlo estimation. This allows for the use of powerful sample-based stochastic optimization techniques, eliminating the need to read all the payoffs.\n2. The loss function upper-bounds the exploitability of an approximate equilibrium. The authors provide theoretical proofs and present empirical results.\n3. The proposed approach enables the scaling of equilibrium-finding techniques to larger games than was previously possible. The paper presents experiments on games with up to 286 actions.\n4. Two algorithms are analyzed: vanilla SGD and a bandit-based method. The bandit approach offers theoretical guarantees, such as a high probability bound on exploitability.", "weaknesses": "1. The loss function only captures fully mixed equilibria. The authors address this by considering quantal-response equilibrium. As a result, a zero loss can only serve as an approximation to a Nash equilibrium.\n2. There is limited empirical evaluation on real-world games. Most experiments involve small synthetic games from previous research. It's possible that more complex games may expose certain limitations.\n3. SGD encounters issues with saddle points in certain games, which is a common challenge in non-convex optimization.", "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": "PdhsmmpBCH", "reviewer": "Reviewer_Lp7D", "summary": "This paper investigates the problem of solving a Nash equilibrium (NE) inside a normal-form general-sum game (NFG). Unlike previous works, the authors propose a new kind of loss that serves as an upper bound for $\\epsilon$ (coefficient of $\\epsilon$-Nash). More importantly, the authors show that an unbiased gradient of the loss can be obtained using the symmetrization technique. As a result, the problem of NE can be treated as a stochastic optimization problem, such that some famous algorithms like SGD and BLiN can exploited. Moreover, the authors also consider the case when the NE is not inside the simplex but on its boundary. And they show that this issue can be also handled by optimizing on a refined game with additional bonuses. Finally, empirical studies validate the effectiveness of the proposed method.", "questions": "I do not have any questions, as the presentation of this work is quite clear and intuitive, along with some illustrations to help readers understand it well.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I have not read the papers about how to solve an NE efficiently before. However, this paper is quite clear in this presentation, such that I have now obtained a whole picture of this problem. The problem setup is clearly introduced. The solution is illuminated step by step, which is clear and intuitive. It is worth mentioning that the authors give several illustration figures (e.g., Figures 1 and 2) to help the readers understand the paper better, which is very good. The experiments are also sufficient and complete. Moreover, this work offers the community a new and principled way of solving NEs efficiently, and many more stochastic optimization algorithms can be leveraged in this field.", "weaknesses": "I do not see major weaknesses in this work, though I am not an expert in this field.", "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 (oral)