Equilibrium-finding via exploitability descent with learned best-response functions
Authors: Carlos Martin
Tuomas Sandholm
Venue: Submitted to ICLR 2023 (2023)
Keywords: equilibrium finding
game solving
best-response function
computational game theory

Abstract: There has been great progress on equilibrium-finding research over the last 20 years. Most of that work has focused on games with finite, discrete action spaces. However, many games involving space, time, money, etc. have continuous action spaces. We study the problem of computing approximate Nash equilibria of games with continuous strategy sets. The main measure of closeness to Nash equilibrium is exploitability, which measures how much players can benefit from unilaterally changing their strategy. We propose a new method that minimizes an approximation of  exploitability with respect to the strategy profile. This approximation is computed using learned best-response functions, which take the current strategy profile as input and return learned best responses. The strategy profile and best-response functions are trained simultaneously, with the former trying to minimize exploitability while the latter try to maximize it. We evaluate our method on various continuous games, showing that it outperforms prior methods.

Under review as a conference paper at ICLR 2023
EQUILIBRIUM FINDING VIA EXPLOITABILITY DESCENT WITH LEARNED BEST-RESPONSE FUNCTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
There has been great progress on equilibrium finding research over the last 20 years. Most of that work has focused on games with finite, discrete action spaces. However, many games involving space, time, money, etc. have continuous ac- tion spaces. We study the problem of computing approximate Nash equilibria of games with continuous strategy sets. The main measure of closeness to Nash equilibrium is exploitability, which measures how much players can benefit from unilaterally changing their strategy. We propose new method that minimizes an approximation of exploitability with respect to the strategy profile. This approxi- mation is computed using learned bext-response functions, which take the current strategy profile input and return learned best responses. The strategy profile and best-response functions are trained simultancously. with the former trying to min- imize exploitability while the latter try to maximize it. We evaluate our method on various continuous games, showing that it outperforms prior methods.
INTRODUCTION
Most work concerning equilibrium computation has focused on games with finite, discrete action spaces. However, many games involving space, time, money, etc. have continuous action spaces. Examples include continuous resource allocation games (Ganzfried 2021). security games in con-
tinuous spaces (Kamra et al., 2017 2018 2019), network games (Ghosh Kundu 2019). military simulations and wargames (Marchesi et al. 2020), and video games (Berner et al., [0199 Vinyals
jet al. 2019). Moreover, even if the action space is discrete, it can fine-grained enough treat continuous for the purpose of computational efficiency [Brel (9388; Chen & Ankenman (006);
Ganzfried & Sandholm (2010b).
The first question that arises in the multiagent setting is what game-theoretic solution concept and performance metric should be used. For the former, we use the standard solution concept of a Nash equilibrium: that is, strategy profile for which each strategy is best response to the remaining players' strategies. The main measure of closeness to Nash equilibrium is exploitability, which measures how much players benefit from unilaterally changing their strategy. Typically, we seek Nash equilibria, that is, strategy profiles for which the exploitability is zero. As some previous works in the literature have done, we can try search for Nash equilibria by performing gradient descent on exploitability, since it is non-negative and its zero set is precisely the set of Nash equilibria. However, evaluating exploitability requires computing best responses the current strategy profile, which is itself a nontrivial problem in complex games.
We propose a new method that minimizes an approximation of the exploitability with respect to the strategy profile. This approximation is computed using learned bext-response, functions, which take the current strategy profile as input and return learned best responses. The strategy profile and best-response functions are trained simultancously, with the former trying minimize exploitability while the latter try to maximize it.
We start by introducing some background needed to formulate the problem, including the definition of strategic-form games, strategies, equílibria, and exploitability. Next, we describe some prior methods in the literature and related research. We then describe various games that we use as benchmarks and discuss our experimental results. Finally, we present our conclusion and suggest directions for future research.

---

Under review as a conference paper at ICLR 2023
2 BACKGROUND
Games and equilibria A strategic-form game is a tuple (T,X, u) where I is a set of players, X; a strategy set for player i, and u: 11, + IR! is utility function. A strategy profile I E 11; X; maps each player to a strategy for that player. A game is zero-sum if and only if 3: u(x); = 0 for all strategy profiles æ. Z-; denotes æ excluding player i's strategy. Player i's best-response utility b(z); = sup.: u( z=3); is the highest utility they can attain given the other players' strategies. Their utiliiy gap 6(z); = b(x); u(x;;; is the highest utility they can gain from unilaterally changing their strategy. x is an E-equilibrium iff sup; 6(z); S E. A O-equilibrium is called a Nash equilibrium. In Nash equilibrium, each player's strategy is a best response to the other players' strategies, that is, u(z); 2 u( x=;); j for all E I and x; E X;.
Infinite games For some games, the X, might be infinite. The following theorems apply to such games: If for all i, X, is nonempty and compact, and u(z); is continuous in z, a mixed strategy Nash equilibrium exists Gllicksberg. 1952). If for all i, X; is nonempty, compact, and convex, and u(x);; is continuous in æ and quasi-concave in Zg, a pure strategy Nash equilibrium exists (Fudenberg & Tirole 1999, p. 34). Other results include the existence of a mixed strategy Nash equilibrium for games with discontinuous utilities under some mild semicontinuity conditions the utility functions (Dasgupta & Maskin 1986). and the uniqueness a pure Nash equilibrium for continuous games under diagonal strict concavity assumptions (Rosen 1965).
Nikaido-Isoda function
Nikaido & Isoda (1555) introduced the Nikaido-Isoda (NI) function
6(2. y) (u(ys 2 x-i): u(z); It is also sometimes called the Ky Fan function (Flām & An-
tipin 1996 Fläm & Ruszczynski 2008 Hou et al. (0188). Several papers have proposed algorithms
that use this function to find Nash equilibria, including Berridge
Incrrding Berrrdge & Krawezyk (1970); Uryasev & Rubinstein (1994); Krawezyk& & Uryasev (2000); Krawczyk (2005)); Flām & Ruszczyński (2008);
Gürkan & Pang (2009): von Heusinger & Kanzow (2009a b); Qu & Zhaoo (2013): Hou et al. (018);
Raghunathan et al. (2019); Tsaknakis & Hong (2021).
Exploitability Let (xx) = sup, (xx, v). Then (bx)) 2 0. Furthermore, (xx = 0 if and
only if x. is Nash equilibrium. t/ commonly known the exploitability or Nash conver- gence metric (NashConv) in the literature (Lanctot et al. 2017: Lockhart et al. 2019 Walton & Lisy| 2021 Timbers al. 2022). It adds up the utility gaps d(z); sup,, y, u(yh. of each player, and thus serves as measure of closeness to Nash equilibrium In two-play wwo-player zero-sum game, the exploitability reduces the so-called "duality gap" (Grnarova et al., 2021) (x) = sup,; u(z1,, #2)1 inf u(x1,,z))1. 22)11
u u(z)
There several algorithms in the literature for continuous games. Mescheder et al. (017) introduced consensus optimization (CO) to improve the convergence properties of GANs. Unfortunately. CO can sometimes converge to undesirable points even in simple potential games. Balduzzi et al. (2018) introduced symplectic gradient adjustment (SGA) to address some of the shortcomings of CO.
Algorithms
Foerster et al.] (2018) introduced learning with opponent -eparinn-learnnng awareness (LOOAA), a method in which each agent shapes the anticipated learning of the other agents in the environment. The LOLA learning rule includes term that accounts for the impact of one agent's policy on the anticipated parameter update of the other agents. They show that LOLA leads cooperation with high social welfare, while independent policy gradients, a standard multiagent RL approach, does not. The policy gradient finding is consistent with prior work, such as (Sandholm & Crites (1996). Letcher et al. (2018) introduced sluble opponent shaping (SOS), which interpolates between LOLA and different but similar learning method called LookAhead (Zhang & Lesser 2010p.
Schaefer & Anandkumar (2019) introduced competitive gradient descent (CGD), natural gener- alization of gradient descent to the two-player setting where the update is given by the Nash equi- librium of regularized bilinear local approximation of the underlying game. It avoids oscillatory and divergent behaviors seen in alternating gradient descent. The convergence and stability prop- erties of their method are robust strong interactions between the players, without adapting the stepsize, which is not the case with previous methods. Ma et al. (202I) generalized CGD to more than two players by using local approximation given by a multilinear polymatrix game that can
2

---

Under review as a conference paper at ICLR 2023
be solved using linear algebraic methods. They call this method polymatrix competitive gradient descent (PCGD).
To describe these and other methods in the literature formally, use the following notation. Let { = diag Vu be the simultaneous gradient; each component & = V,u; is the gradient of a player's utility with respect to their strategy. It is vector field the strategy profile space. It need not be conservative (the gradient some potential), which is the primary source of difficulties in apply- ing standard gradient-based optimization methods, since trajectories can cycle around fixed points rather than converge to them. Let H = VE. Then naive learning (NL) (also known as simul- taneous gradient ascent), extragradient (EG) (Korpelevich) I optimism (OP) (Popov 1980, Daskalakis et al., 2018)) consensus optimization (CO) (Mescheder et al.) 2017), sympletic gradient adjustment (SGA) (Balduzzi et. 2018), lookahead (L.A) (Zhang Lesser] [esser]20100, symmetric looka- head (SLA) [Letcher] 2018), learning with opponent- opponent-lerningg awareness (LOLA) (Foerster et al.)
2018), gradient- based Nikaido-Isoda (GNI) (Raghunathan al. 2019), and polymatrix competitive are, respectively:
gradient descent (PCGD) (Ma et al. 202 l
İNI. = {
(1)
ĐG El
(2)
OP = _ + -5
(3)
cco = (I - -- E -
(4)
SSGA (I - -
LA = (I + HHo
(6)
SSLA = (1 + +
LOLA = LA - 7 diag H. Vu Vu
(8)
ÆGNI = V VO(x, x +E)
(9)
TPGG = (T -HHH
(10)
where 7 0 is hyperparameter, Ehy is & evaluated at y rather than x, HT is the transpose of H, Ha = 2 TT) is the antisymmetric part of H, and H. is the off- off-diagonal part of H (replacing its diagonal with zeroes). GNI replaces the supremum in vi with the local approximation y = x + + SLA is a linearized version of EG (Enrich) 2019 Lemma 1.35). LA is the series expansion of PCGD to first order in (Willi et al. 2022 Proposition 4.4), since (I - -M) = I + + + 2 + for sufficiently small y. Exact PCGD requires solving linear system of equations, which makes each iteration costly (Ma et al. [02TT] p. 10). The actual optimization is done by discretizing each ODE in time. For example, with NI., we have the iteration scheme x4+1 = 24 + n/: for some small learning rate 7) > O. With OP, we have Fi+1 = + n); + 755 E-11
)
These algorithms have been analyzed in various works, including Balduzzi al. (2018); Letcher et al. (2018) 2019); Mertikopoulos & Zhou (2019); Grnarova
[ et al. (2019); Mazumdar et al. (2019); Hsich et al. [202 Willi al. (2022). Additional related research can be found in the appendix.
OUR METHOD
Before introducing our method, we motivate it by considering the perspective of a single player in a two-player game, with the aim of recommending a "good strategy" for that player.
Single-player perspective Let X, Y be sets and u XxY - R be differentiable function. Sup- pose want solve the following optimization problem: max, min, u(æ; vy). This corresponds to finding minimally-exploitbble strategy for Player in zero-sum game with payoff function u. To solve this problem, we could try to apply simultaneous gradient ascent:
Φ = V (z.
i v-ux, v)
(11)
Unfortunately, this approach can easily fail even in simple games. For example, consider the simple bilinear game that has X, Y C R and u(z y) = ry. should converge to 0, but instead oscillates around it indefinitely. In fact, x and jointly trace a circle around the origin. The essence this cycling problem is that Player 2 has to "relearn" good response to Player every time the lattr's
3

---

Under review as a conference paper at ICLR 2023
strategy switches sign. This is a general problem for games: small changes in other players' strate- gies may cause big changes in a player's 's best response. Thus players have to essentially "releam" how to respond to the other players' strategies every time such discontinuous changes occur.
Best-response functions To address this, we can reformulate the problem as maximizing u(x;, b(x))) with respect x, where b: X - Y is a function that satisfies b(x) E arg miny u(z, y)- Since b is a fully-fledged function, it can map different strategies for Player to different strategies for Player 2. Thus can immediately adapt to Player I's strategy and avoid the cycling problem. To find x and such a b simultaneously, we can perform simultaneous gradient ascent:
(12) This time, we use the functional derivative Vo. Again, since is a fully-fledged function, Player I's changing behavior poses no fundamental hindrance to it learning good responses, and "saving" them for later use if Player I's behavior changes. It could even learn the true best-response function and stop there, leaving Player 1 to face a simple standard optimization problem.
A = +V b()) b= - -vu(a, b(x:)
If X is infinite and Y is nontrivial, X + Y is mnfnite-dimmnsional. To represent and optimize in practice, we need finite-dimensional parameterization of (a subset of) this function space. We use neural networks for this, letting be the function defined by a neural network with given set of parameters, and optimize these parameters.
X itself may be a function space. For example, Player I's strategy may be policy that takes observations as input and outputs actions accordingly. In that case, b acts as a higher-order function that takes a function (Player I's strategy) as input and returns a new function (a strategy for Player 2). In practice, it can simply take the parameters of Player I's policy as input.
Approach for n-player games We can try to search for Nash equilibria by performing gradient descent on the exploitability function v since it is non-negative and its zero set is precisely the set of Nash equilibria. However, computing the supremum for i expensive and/or intractable in the gen- eral case, since it requires computing best responses to the current strategy profile, itself nontrivial problem. Inspired by our approach for the 2-player setting, we reformulate & as ((x)) = o(zz b(z)) where b is a best-response function such that b(ar); arg max u(z;, x-)) In practice, model best-response functions with neural networks, which have finite miite-dimensional parameterization, and train them simultaneously with æ. Thus our scheme is:
i = V2o(æ,
b b= Voo(a, (x))
(13)
That is, the best responses try to increase the exploitability while the strategies try to decrease it. More precisely, if b is parameterized by finite-dimensional parameter vector 0, then our scheme is:
ズ = vv bo())) 0= + Vod(z, bz()))
(14)
We call our method exploitability descent with learned best-response funcctioos
4 EXPERIMENTS
In our experiments, we use affine best-response functions of the form (x = Ax + b where b) 0. We initialize that ba the identity function. Unless otherwise specified, we use learning rate of 10-2 and 10-1 1, For the algorithms that use 7, lower values of y slowed their convergence rate, bringing it closer to that of NL. Higher values y accelerated convergence on some but not all games. Hyperparameter comparisons can be found in the appendix.
Some of these benchmarks are based on normal-form or extensive-form games with finite action sets, and thus finite-dimensional continuous mixed strategies. While there are algorithms for such games that might have better performance (such as counterfactual regret minimization (Zinkevich) et al. 2007) and its variants), these do not readily generalize to general continuous-action games. Thus we are interested in comparing only to those algorithms which, like ours, do generalize to continuous-action games, namely those described in the previous section.
We parameterize mixed strategies on a finite action set (e.g., at a particular information set inside actions. Then use parameter
an extensive-form game) follows. Suppose there x e R and define the action probabilities as coftmax(appendd) 0)). When x is 1-dimensional, this equívalent to applying the logistic sigmoid function.
4

---

Under review as a conference paper at ICLR 2023
Sign game
This game has players, X, [-100, 100], and
2:3441 < 71
u(z); =
(15)
L1 = n1
This is an n-player generalization of the simple bilinear zero-sum game u(zz = y)2 zy. The latter is an important example because it captures the cycling behavior of simultaneous learning dynamics when training GANs (Mescheder et al.) 2018 Zhang & Yu 2020 This game has an equilibrium the origin.
The performance of each algorithm is illustrated in Figure 2a (for players) and Figure 2b (for players). The trajectories of each player's parameter for the 2-player case are shown in Figure Ta NL. slowly spirals away from the equilibrium. All algorithms from OP to LA (inclusive) overlap exactly and slowly spiral into the equilibrium. LOLA also spirals into the equilibrium, but faster. Our e
algorithm shoots straight for the equilibrium, overshoots it a bit, and bounces back along the same line, getting closer and closer to the equilibrium with each oscillation. converges significantly faster than the other algorithms.
Antisymmetric game This game has 4 players. X; |- 100, 100), and u(x); x; Σ, 3y sign(j - i). It appears in Balduzzi et (2018 Appendix D). The performance of each algorithm on this game is illustrated in Figure 2c On this game, LOLA and our algorithm converge significantly faster than the rest, with the former converging slightly faster.
Pennies game This is the strategic-fomm version of a normal-form game with n players, action sets A; = (H,T), and payoff function
u(a); = fla a++1] - F a1]
i
(16)
i i= n
where [:] denotes the Iverson bracket, which is 1 if its argument is true and 0 otherwise. This is generalization of the classic matching pennies game to n players (Jordan 1993 Leslic & Collins
2003). Each player but the last tries to match the next player, and the last player tries to wnmatch the
first. Like the 2-player version, it has a unique mixed strategy equilibrium where each player mixes uniformly between heads and tails. The payoff matrix for n 2 is shown in Table la
Interestingly.Doraar (1993) shows that the 3-player game's 's Nash equilibrium is locally unstable in a strong sense: for any >> and for almost all initial empirical distributions that are within Euclidean distance & of the equilibrium, discrete-time fictitious play does not converge to the equilibrium. Instead, it enters limit eycle asymptotically t
We can construct a strategic-fort game whose strategy sets are the mixed strategies of this normal- form game, and whose payoffss are the expected payoff's of the normal-form game under such mixed strategies. We use a softmax parameterization of the strategies, as described in the beginning of this section. The game then has a unique equilibrium at the origin.
The performance of each algorithm is illustrated in Figure 2d (for 2 players) and Figure 2 (for players). The trajectories of each player's parameter for the 2-player case are shown in Figure Tb NL slowly spirals away from the equilibrium. All algorithms from SLA to CO (inclusive) overlap almost exactly and slowly spiral into the equilibrium. LOLA also spirals into the equilibrium, but slightly faster. Our algorithm shoots straight for the equilibrium, overshoots it, and bounces back, getting closer and closer to the equilibrium with each oscillation. It converges significantly faster.
Rock paper seissors game This is the strategic-form version of the classic rock paper scissors game, 2-player normal-form game whose payoff matrix is shown in Table 1b The equilibrium lies at the origin. The performance of each algorithm is illustrated in Figure 2F The trajectories of each player's 's action probabilities (a point on the 2-simplex) are illustrated in Figure 4a in the appendix. Our algorithm converges faster than the rest, with LOLA attaining the next-best performance.
Shapley game This is the strategic-form version of the Shapley game, a normal-fonme game whose payoff matrix is shown in Table Tcl It was introduced by (Shapley 1964 p. 26) and is well-known
5

---

Under review as a conference paper at ICLR 2023
example of a game for which fictitious play does not converge. Instead, fictitious play cycles through the cells with I's in them, with vvrr-nncrassing lengths of play in each of these cells.
The performance of each algorithm is illustrated in Figure 2g The trajectories of cach player's 's action probabilities are illustrated in FigureAblin the appendix. The difference in performance between our algorithm and the others is especially stark in this game. All other algorithms seem to diverge from the equilibrium quite rapidly, whereas ours converges rapidly toward it.
Glicksberg- Gross game This is the strategic form version of 2-player continuous-action normal-form game with action sets A, = [0, 1] and payoff function
u(I, 3) = --(,, u)2 (1 + x1 + y)(1 xy)
(17)
(1 + zy)²
This is a 2-player zero-sum game on the unit square. was studied by Glicksberg & Gross (1953), who showed that it has unique mixed strategy Nash equilibrium with the probability density func- tion f(x) xvズ(1+x] for both players. As the authors comment, this shows that rational games do not share with polynomial games the property of always having step function solutions.
For this game, we model players' strategies as beta distributions that are parameterized as follows: Each player's strategy is pair of real numbers. These passed through a softplus function to make them positive, and the results are used as the concentration parameters. Due to the variance of our stochastic estimator for the game's utility function, each algorithm. Ours attains a lower exploitability than the other algorithms and appears have lower variance. Figure Balin in the appendix illustrates the probability density functions of each player after training.
use a learning rate of 10- Figure
2h illustrates the performance
Circle game This is the strategic-form version of an n-player continuous-action normal-form game with action sets A, = [-T, n, 1) and payoff function
((41) u(a) [d(an,
(18)
= n
where d(x, y) is the Euclidean distance between the points at angles v and y on the unit circle. Each player chases the next, but the last avoids the first. This a generalization of the 2-player zero-sum distance game on the unit circle. Like the 2-player version, it has a mixed strategy equilibrium where each player mixes uniformly on the unit circle.
We let player strategies be von Mises distributions (of which the circular uniform distribution is a special case) that are parameterized as follows: Let n; E TR22 be Player i's parameter. Then arctan2(x:)) E [-m, TT is the angular position parameter and ||=;||| E [0, oc) is the angular scale parameter, where arctan2 yields the angle of its input (in radians). Due to the variance of stochastic estimator for the game's utility function, and Figure 2ijlllustete the performance of each algorithm for 2 players and 3 players, respectively. Our algorithm attains lower exploitability and variance than the rest. Figure 3b in the appendix illustrates the probability density functions of each player after training.
learning rate of 10-4. Figure 2i
Kuhn poker This is a famous simplified version of poker introduced by Kuhn 1950) as a model inffrecctiooooottionnn games that can be analyzed theoretically. A 3-player
of zero-sum two-player variant was introduced by |Szafron et al. (2013), who stated that it was one of the largest three-player games to be solved analytically to date.
As described the beginning of this section, each player's strategy stores the logits for softmax parameterization of action distribution at cach information set. 2-player Kuhn poker has 6 in- formation sets per player with 2 actions each, yielding 6 x (2 - 1) = 6 parameters per player and
6 x 2 12 parameters in total. 3-player Kuhn poker has 16 information sets per player with 2 actions each, yielding 16 x (2 (2-12 1) = 16 parameters per player and 16 x 33 = 48 parameters in total. The utility function for each player is the expected payoff of the resulting strategy profile.
In this experiment, we also test low-rank affine best-response functions of the form (x(x) = (I + UV)x + b where < is rank, V E RRrx U Rox and (U, V,b) 0. This reduces the

---

Under review as a conference paper at ICLR 2023
H
1.0
0.0
R
0,0
- 1,
1,
4.-1
H
1,0
0,
0.0
0,
P
1,
0,0
-1,1
0,1
1,0
0.1
0.0
1,0
1
0,0
(a) Pennies game (2 players).
(c) Shapley game.
(b) Rock paper scissors game.
Table Normal-form games.
EG
0.6
0.75
QP
CO
SGA
0.50
SLA
GNI
0.25
LA
parameter?
0.00
ED
0.0
NL
OP
-02
CO
-0.50
SGA
GNI
-0.75
LA
LOLA
-1.00
-1.00
-0.75
-0.50
-0.25 0.00
0.25
0.50
0.75
1.00
-0.6
-0.4
-0.2
0.0
0.2
0.4
0.6
parameter
parameter
(a) Sign game (2 players).
(b) Pennies game (2 players).
Figure I: Trajectories of each player's parameter.
number of parameters of the linear map from n² to 2nr and its computational complexity from O(n²) multiplications and additions to (nr)) multiplications and additions
Figures 2K and [ illustrate the performance of each algorithm on the 2-player and 3-player game, respectively, with ? 1. Our algorithm significantly outperforms the rest and attains lower ex- ploitability. The low-rank versions are suffixed with the rank number. Interestingly, some of them match the performance of the full-rank version, a reduced computation cost.
5 CONCLUSIONS AND FUTURE RESEARCH
We studied the problem of computing approximate Nash equilibria of games with continuous strat- egy sets. Many settings involving space, time, money, and other resources are naturally modeled continuous games. The main measure of closeness to Nash equilibrium is exploitability, which measures how much players can benefit from unilaterally changing their strategy. We proposed a new method that minimizes approximation of the exploitability with respect to the strategy pro- file. This approximation is computed using learned best-response functions, which take the current strategy profile input and return learned best responses. The strategy profile and best-response functions are trained simultancously, with the former trying to minimize exploitability and the latter trying to maximize it. We evaluated our method in various continuous games, showing that out- performs prior methods. We now discuss some possible extensions of our method to more general settings and directions for future research.
'To handle very large strategy vectors very large games, one could also use sparse matrices or hierar- chical matrices (Börm et al. 2003 Grasedyck & Hackbusch [2003] Bebendorf] (2088 Hackbusch] 20015) The latter rely on local low-rank approximations and are closely related to the fast multipole method (Greengard & Rokhlin 1987 Greengard] 1987 White & Head-Gordon 1994), which is widely used in computational science speed up calculations.

---

Under review as a conference paper at ICLR 2023
13
LOLA
LA
1074
10-h
60.4
22A
10
LO1A
2000
.003
6202
8000
10000
2000
2000
9033
10000
2000
4000
2003
2003
10000
(a) Sign game (2 players).
(b) Sign game players).
(c) Antisymmetric game.
10
101
23
20-
30
30"
BOLA
IDLA
20000
50003
30000
20000
30303
100000
(d) Pennies game (2 players).
(c) Pennies game (3 players).
(f) Rock paper scissors game.
137
10"7
10
LOLA
504
stice
166
(g) Shapley game.
(h) Glicksherg- Gross game.
(i) Circle game (2 players).
20
10"
H01-
LOLA
0.20
0.25
0.50
0.75
2.00
2.25
2.75
2
0.0
0.5
0.4
Steg
.209
(j) Circle game (3 players).
(k) Kuhn poker (2 players).
Kuhn poker (3 players).
Figure 2: Exploitabilities.
8

---

Under review as a conference paper at ICLR 2023
Deep generative models In some games, simple parametric distributions (including mixture mod- els) may not be flexible enough to represent equilibrium strategies well. Instead, one can use deep generative models. One example is generative network, which transforms input noise from some fixed latent distribution (such as a multivariate Gaussian) and yields a new output distribution. This is used in GANs. Since the action space distribution is longer a simple parametric distribution, we cannot feed those parameters into the best-response function. Instead, we can feed the generative network's weights, since they implicitly define the distribution. If the generative network is com- plex, it might be difficult for the best-response function to "make sense of" the weights it receives as input. In that case, we can take a more black-box approach: We do not care about the internals of the generative network (its intrinsic behavior), only the distribution it produces (its extrinsic behav- ior) on the action space. Instead of feeding the parameters of the generative network, we can feed batch of samples from the generative network, letting the best-response function "analyze" said batch in some fashion. If the batch size is large enough, the best-response function could identify the features of the distribution that are relevant to recommending a good best response. We describe a few approaches for "aaaalzing" the distribution from batches of samples.
Packing Lin et al. (2020) proposed way handle the mode collapse problem for GANs called packing. It modifies the discriminator to make decisions based on multiple samples from the same class, either real or artificially generated. The authors use analysis tools from binary hypothesis test- ing, particularly the seminal result of Blackwell] (1953), to prove fundamental connection between packing and mode collapse. Specifically, they show that if the discriminator is allowed to see sam- ples from the m-th order product distributions pm and Q" instead of the usual target distribution P and generator distribution Q, then the corresponding loss when training the generator naturally penalizes generator distributions with strong mode collapse. Based on these insights, they propose PacGAN, which passes m "packed" or concatenated samples to the discriminator that are jointly classified either real or artificially generated.
Generalized moments An alternative approach is to use a generalized version of the method of momenty from statistics. We let bx(x) 9o (Eazz so(a)) where Se II. A, + R" and 9e: : R" + II,X, are trainable neural networks. Ordinary moments can be recovered with ap- propriate functions. For example, the first and second moments F[X] and F[X*] are sufficient to recover the concentration parameters of beta distribution from its variates X. To estimate such generalized moments, we can replace the expectation with an average 1 aj are independent samples of action profiles from the strategy profile.
[ ΣjEJ fo(a,), where the
Multi-state games The above can be readily generalized to perfect-informationn games where all players receive a common observation that is correlated with the payoffs given their actions. In that case, the best-response function can feed the observation through the strategy networks they take as input and analyze the resulting action distributions.
The case of cuperfect-informatie have access to the other players' observations, which their action distributions depend on. In that case, we have at least two options. On the one hand, the best-response functions could take the strategy networks' parameters as input (the intrinsic approach), since these implicitly define all of their behavior. On the other hand, they could analyze the strategies purely through their output behavior (the extrinsic approach). In that case, they would have to learn to query such networks with hypothetical observations, given their own observation.
games is more complex. In that case, best responses do not
When designing the (parameterized) best-response function, one could also exploit the special struc- ture of the extensive-form game by performing some form of local game tree analysis of the strategy profile in, say, the neighborhood of an information set. See Timbers et al. (2022) for application of this in the extensive-form setting that computes approximate best responses.
REFERENCES
Lukáš Adam, Rostislav Horčík, Tomás Kasl, and Tomáš Kroupa. Double oracle algorithm for com- puting equilibria in continuous games. AAAI Conference on Artificial Intelligence (AAAI), 35: 5070-5077, 2021.

---

Under review as a conference paper at ICLR 2023
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. In International Conference on Machine Learning (ICML), volume 80, pp. 354-363, 2018.
Mario Bebendorf. Hierarchical matrices. Springer, 2008.
Ulrich Berger. Brown's 's original fictitious play. Journal of Economic T'heory, 135:572-578, 2007.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 1912.06600, 2019.
Steffan Berridge and Jacek B. Krawezyk. Relexation algorithms in finding Nash equilibria. Victoria University of Wellington, 1970.
Martin Bichler, Maximilian Fichtl, Stefan Heidekrüger, Nils Kohring, and Paul Sutterer. Learning equilibria in symmetric auction games using artificial neural networks. Nature Machine Intelli- gence, 3:687-695, 2021.
David Blackwell. Equivalent comparisons of experiments. The Annals of Mathematical Statistics, 24:265-272 272, 1953.
Émile Borel. Truité du calcul des probubilités et ses applicatioons volume IV of Applications aux jeux des hazard. Gauthier- Villars, Paris, 1938.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPP programs, 2018.
George W. Brown. Iterative solutions of games by fictitious play. In Tjalling C. Koopmans (ed.), Activity Analysis of Production and Allocation, pp. 374-376. John Wiley Sons, 1951.
Steffen Börm, Lars Grasedyck, and Wolfgang Hackbusch. Introduction to hierarchical matrices with applications. Engineering Analysis with Boundary Elements, 27:405 422, 2003.
Bill Chen and Jerrod Ankenman. The Mathematics of Poker. ConJelCo, 2006.
Partha Dasgupta and Eric Maskin. The existence of equilibrium in discontinuous economic games. Review of Economic Studies, 53:1-26, 1986.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference Learning Representations (ICLR), 2018.
Carles Domingo Enrich. Games machine learning: differentiable n-player games and structured planning. B.S. thesis, Universitat Politècnica de Catalunya, 2019.
Maximilian Fichtl, Matthias Oberlechner, and Martin Bichler. Computing Bayes Nash equilibrium strategies in auction games via simultaneous online dual averaging. 2022. arXiv:2208.0200
Tanner Fiez, Chi Jin, Praneeth Netrapalli, and Lillian Ratifff. Minimax optimization with smooth algorithmic adversaries. In International Conference on Learning Representations (ICLR), 2022.
Sjur Didrik Flåm and Anatoly S. Antipin. Equilibrium programming using proximal-lic like algorithms. Mathematical Programming, 78:29-41, 1996.
Sjur Didrik Flåm and Andrzej Ruszczyíski. Finding normalized equilibrium in convex-concave games. International Game Theory Review, 10:37-51, 2008.
Jakob Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In Autonomous Agents and Multi-Agent Systems, pp. 122-130, 2018.
Drew Fudenberg and Jean Tirole. Game theory. MIT Press, Cambridge, MA, 1991. ISBN 0-262- 06141-4.
10

---

Under review as a conference paper at ICLR 2023
Sam Ganzfried. Algorithm for computing approximate Nash equilibrium in continuous games with application to continuous Blotto. Games, 12:47, 2021.
Sam Ganzfried and Tuomas Sandholm. Computing equilibria by incorporating qualitative models. In International Conference on Autonomous Agents and Mulli-Agent Systems (AAMAS), 2010a.
Sam Ganzfried and Tuomas Sandholm. Computing equilibria by incorporating qualitative models. Technical report, Carnegie Mellon University. 2010b.
lan Gemp, Rahul Savani, Mare Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, An- drea Tacchetti, Tom Eccles, and János Kramár. Sample-based approximation of Nash in large many-player games via gradient descent. In Autonomous Agents and Mulli-Agent Systems, pp. 507-515, 2022.
Papiya Ghosh and Rajendra P. Kundu. Best-shot network games with continuous action space. Research Economics, 73:225-234, 2019.
Irving Leonard Glicksberg. A further generalization the Kakutani fixed point theorem, with application to Nash equilibrium points. Proceedings of the American Mathematical Society, 3(1): 170-174, 1952.
Irving Leonard Glicksberg and Oliver Alfred Gross. Notes on games over the square. In Harold William Kuhn and Albert William Tucker (eds.), Contributions to the Theory of Games (AM-28), Volume II, pp. 173-182. Princeton University Press, 1953.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Conference on Neural Information Processing Systems (NeurIPS), volume 27, 2014.
Lars Grasedyck and Wolfgang Hackbusch. Construction and arithmetics of H-matrices. Computing, 70:295-334, 2003.
Leslie Greengard and Vladimir Rokhlin. A fast algorithm for particle simulations. Journal of computational physics, 73:325-348, 1987.
Leslie Frederick Greengard. The rapid evaluation potential in particle systems. PhD thesis, Yale University, 1987.
Paulina Grnarova, Kfir Y. Levy, Aurelien Lucchi, Nathanael Perraudin, Ian Goodfellow, Thomas Hofmann, and Andreas Krause. A domain agnostic measure for monitoring and evaluating GANs. In Conference on Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Paulina Grnarova, Yannic Kilcher, Kfir Y. Levy, Aurelien Lucchi, and Thomas Hofmann. Generative minimization networks: training GANs without competition, 2021. arXiv:2103.12685.
Gül Gürkan and Jong-Shi Pang. Approximations of Nash equilibria. Mathematical Programming, 117:223-253, 2009.
Wolfgang Hackbusch. Hierarchical matrices: algorithms and analysis. Springer Publishing Com- pany, Incorporated, 1st edition, 2015.
Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International Conference on Machine Learning (ICML), volume 37, pp. 805-813, 2015.
Jian Hou, Kong-Chuan Wen, and Qing Chang. An unconstrained optimization reformulation for the Nash game. Journal of Interdisciplinary Mathematics, 21:1303-1307, 2018.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: convergence to spurious non-critical sets. In International Conference on Machine Learning (ICML), volume 139, pp. 4337-4348, 2021.
James S. Jordan. Three problems in learning mixed-steer -ixed-strategy Nash equilibria. Games and Economic Behavior, 5:368-386 1993.
11

---

Under review as a conference paper at ICLR 2023
Nitin Kamra, Fei Fang, Debarun Kar, Yan Liu, and Milind Tambe. Handling continuous space security games with neural networks. In Proceedings of the International Joint Conference on Artificial Intelligence (ICCAI), 2017.
Nitin Kamra, Umang Gupta, Fei Fang, Yan Liu, and Milind Tambe. Policy learning for continuous space security games using neural networks. AAAI Conference Artificial Intelligence (AAAT), 32, 2018.
Nitin Kamra, Umang Gupta, Kai Wang, Fei Fang, Yan Liu, and Milind Tambe. Deepfp for finding Nash equilibrium continuous action spaces. In Decision and Game Theory for Security. pp. 238-258, 2019.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika Matematicheskie Metody, 12:747-756, 1976.
Jacek B. Krawczyk. Coupled constraint Nash equilibria in environmental games. Resource and Energy Economics, 27:157-181, 2005.
Jacek B. Krawezyk and Stanislav Uryasev. Relaxation algorithms to find Nash equilibria with eco- nomic applications. Environmental Modeling & Assessment, 5:63-73, 2000.
Tomá' Kroupa and Tomáš Votroubek. Multiple oracle algorithm for general-sum continuous games, 2021. arXiv:2109.04111
Harold William Kuhn. simplified two-person poker. Harold William Kuhn and Albert William Tucker (eds.), Contributions to the Theory of Games, volume I of Anmals of Mathematics Studies, 24, pp. 97-103. Princeton University Press, Princeton, New Jersey, 1950.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pero- lat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforce- ment learning. In Conference Neural Information Processing Systems (NeurIPS), volume 30, 2017.
David S. Leslie and Edmund J. Collins. Convergent multiple-timescales reinforcement learning algorithms in normal form games. The Annals of Applied Probability, 13:1231-1251 2003.
Alistair Letcher. Stability and exploitation in differentiable games. PhD thesis, Master's thesis, University of Oxford. Accessed: 2020-06-23, 2018.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable opponent shaping in differentiable games, 2018. urXiv:1811.0844
Alistair Letcher, David Balduzzi, Sébastien Racanière, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. Differentiable game mechanics. Journal of Machine Learning Research, 20: 3032-3071, 2019.
Zun Li and Michael P. Wellman. Eyolution strategies for approximate solution of Bayesian games. AAAI Conference Artificial Intelligence (AAAI), 35:5531-5540, 2021.
Zinan Lin, Ashish Khetan, Giulia Fanti, and Sewoong Oh. PacGAN: the power of two samples in generative adversarial networks. IEEE Journal on Selected Areas in Information Theory, 1: 324-335, 2020.
Viliam Lisý and Michael Bowling. Eqilibrium approximation quality of current no-limit poker bots. In AAAI Computer Poker Workshop, 2017.
Edward Lockhart, Marc Lanctot, Julien Pérolat, Jean-Baptiss Lespiau, Dustin Morrill, Finbarr Tim- bers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by ploitability descent. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). pp. 464-470, 2019.
Jeffrey Ma, Alistair Letcher, Florian Schäfer, Yuanyuan Shi, and Anima Anandkumar, Polymatrix competitive gradient descent, 2021. arXiv:211 111:2111.0880 1.08565.
12

---

Under review as a conference paper at ICLR 2023
Alberto Marchesi, Francesco Trovö, and Nicola Gatti. Learning probably approximately correct maximin strategies in simulation-baii games with infinite strategy spaces. In Autonomous Agents and Muett-Agent Systems, pp. 834 842, 2020.
Eric Mazumdar, Lillian J. Ratliff, and S. Shankar Sastry. On gradee learning in continuous games. SIAM Journal on Mathematics of Data Science, 2: 2:103-131, 2020.
Eric V. Mazumdar, Michael I. Jordan, and S. Shankar Sastry. On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games, 2019. arXiv: 1991.00838..
H. Brendan McMahan, Geoffrey J. Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In International Conference on Machine Learning (ICML), pp. 536-543, 2003.
Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173:465-500 -57, 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics GANs. In Conference 2017.
on Neural Information Processing Systems (NeurIPS), pp-
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. Which training methods for GANs do actually converge? In International Conference on Machine Learning (ICML), 2018.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks, 2016. 1rXiv:1611.02163
Hukukane Nikaido and Kazuo Isoda. Note non-cooperative convex games. Pacific Journal of Mathematics, 5:807 815, 1955.
Julien Perolat, Bart Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elic, Sarah H. Cen, Zhe Wang. Audrunas Gruslys, Alcksandra Malysheva, Mina Khan, Sherjil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eccles, Mark Rowland, Mare Lanctot, Jean-Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalie Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of Stratego with model-free multiagent reinforcement learning, 2022. arXiv:2206. 15552286...78.....
Leonid Denisovich Popov. A modification of the Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
method for search of saddle points.
Rong-Jun Qin, Fan-Ming Luo, Hong Qian, and Yang Yu. Unified policy optimization for continuous- action reinforcement learning in non-stationary tasks and games, 2022. CKKi:2200800945
Biao Qu and Jing Zhao. Methods for solving generalized Nash equilibrium. Journal of Applied Mathematics, 2013:762165, 2013.
Arvind Raghunathan, Anoop Cherian, and Devesh Jha. Game theoretic optimization via gradient- based Wikaido-Isode function. In International Conference on Machine Learning (ICML), vol- 97, pp. 5291-5300, 2019.
J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica, 33:520-534, 1965.
Tuomas W. Sandholm and Robert H. Crites. Multiagent reinforcement learning in the iterated pris- oner's dilemma. Biosystems, 37:147-166, 1996.
Florian Schaefer and Anima Anandkumar. Competitive gradient descent. In Conference on Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Lloyd S. Shapley. Some topics in two-persor games. In M. Drescher, L. S. Shapley, and A. W. Tucker (eds.), Advances in Game Theory. Princeton University Press, 1964.
Duane Szafron, Richard Gibson, and Nathan Sturtevant. A parameterized family of equilibrium profiles for three-player Kuhn poker. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 247-254, 2013.
13

---

Under review as a conference paper at ICLR 2023
Finbarr Timbers, Nolan Bard, Edward Lockhart, Mare Lanctot, Martin Schmid, Neil Burch, Julian Schrittwieser, Thomas Hubert, and Michael Bowling. Approximate exploitability: learning a best response. In Proceedings of the International Joint Conference on Artificial Intelligence (ICCAI), pp. 3487-3493, 2022.
Ioannis Tsaknakis and Mingyi Hong. Finding first-order Nash equilibria of zero-sum games with the regularized Nikaido-Isode function. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130, pp. 1189-1197, 2021.
Stanislav Uryasev and Reuven Y. Rubinstein. On relaxation algorithms in computation of noncoop- erative equilibria. IEEE Transactions on Automatic Control, 39: 263--1267, 1994.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350-354 2019.
Anna von Heusinger and Christian Kanzow. Optimization reformulations of the generalized Nash equilibrium problem using Mikaido-Isoda-yye functions. Computational Optimization and Ap- plications, 43:353-377, 2009a.
Anna von Heusinger and Christian Kanzow. Relaxation methods for generalized Nash equilibrium problems with inexact line search. Journal of Optimization Theory and Applications, 143:159- 183, 2009b.
Michael Walton and Viliam Lisy. Multi-agent reinforcement learning in OpenSpiel: a reproduction report, 2021. arXiv:2103.0018%
Christopher A. White and Martin Head-Gordon. Derivation and efficient implementation of the fast multipole method. The Journal of Chemical Physics, 101(8):6593-660) 1994.
Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber. Natural evolution strategies. In 2008 IEEE Congress Evolutionary Computation (IEEE World Congress Computational Intelligence), pp. 3381-3387, 2008
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research, 15:949-980. 2014.
Timon Willi, Alistair Hp Letcher, Johannes Treutlein, and Jakob Foerster. COLA: consistent
learning with opponent-learning awareness. In International Conference on Machine Learning (ICML). volume 162, pp. 33804-23833 2022.
Chongjie Zhang and Victor Lesser. Aueti- learning with policy prediction. In AAAI Conference on Artificial Intelligence (AAAI), volume 2, pp. 927-934, 2010.
Guojun Zhang and Yaoliang Yu. Convergence of gradient methods on bilinear zero-sum games. In International Conference on Learning Representations, 2020.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Conference on Neural Information Processing Systems (NeurIPS), 2007.
A ADDITIONAL RELATED RESEARCH
McMahan et al. (2003) introduced the double oracle algorithm for normal-form games and proved its convergence, Adam et al. (202T) extended it to two-player zero-sum continuous games. Kroupa & Votroubek (2021) extended it to n-player continuous games. Their algorithm maintains finite strategy sets for each player and iteratively extends them with best responses to an equilibrium of the induced finite sub-game. This "converges fast when the dimension of strategy spaces is small, and the generated subgames are not large." For example, in the two-player zero-sum case: computed by selecting the best point of uniform discretization for the
"The best responses dieenimnnnional problems and by using a mixed-ine -ixed-integer linear programming reformulation for the Colonel Blotto games."
14

---

Under review as a conference paper at ICLR 2023
Ganzfried (202
introduced an algorithm for approximating equilibria in continuous games called "redundant fictitious play" and applied it to a continuous Colonel Blotto game. Kamra et al. (2019) presented DeepFP, an approximate extension of fictitious play (Brown 1951 Berger 2007) to con- tinuous action spaces. Theyy demonstrate stable convergence to equilibrium on several classic games and large forest security domain. DeepFP represents players' approximate best responses via gen- erative neural networks, which are highly expressive implicit density approximators. The authors state that, because implicit density models cannot be trained directly, they employ game-model network that is differentiable approximation of the players' payoffs given their actions, and train these networks end-to-end in a model- learning regime. This allows working in the absence of gradients for players.
Li & Wellman (202)) extended the double oracle approach to n-plaaer general-sum continuous Bayesian games. They represent agents as neural networks and optimize them using natural evolu- tion strategies (NES) (Wierstra al.) 2008 2014). For pure equilibrium computation, they formulate the problem as a bi-level optimization and employ NES to implement both inner-loop best-response optimization and outer-loop regret minimization. Bichler et al. (20T)) presented a learning method that represents strategies as neural networks and applies simultaneous gradient dynamics to provably learn local equilibria. Fichtl et al. (2022) compute distributional strategies on a discretized version of the game via online convex optimization, specifically simultaneous online dual averaging (SODA), and show that the equilibrium of the discretized game approximates an equilibrium in the continuous game.
In generative adversarial network (GAN) (Goodfellow et al. 2014). a generator learns to generate fake data while discriminator learns to distinguish it from real data. Metz et al. (2016) introduced a method to stabilize GANs by defining the generator objective with respect to an unrolled opti- mization of the discriminator. They show how this technique solves the common problem of mode collapse, stabilizes training of GANs with complex recurrent generators, and increases diversity and coverage of the data distribution by the generator. [Grarova et al. (2019) proposed using an ap- proximation of the game-theoretic duality gap as a performance measure for GANs. Grnarova et al. 2021 proposed using this measure as the objective, proving some convergence guarantees.
Lockhart et al. (2019) presented exploitability descent, which computes approximate equilibria in two-player zero-sum extensive-form games by direct strategy optimization against worst-case op- ponents. They prove that the exploitability of player's 's strategy converges asymptotically to zero. Hence, when both players employ this optimization, the strategy profile converges to an equilib- rium. Unlike extensive-form fictitious play (Heinrich al., 2015) and counterfactual regret mini- mization (Zinkevich et al. 2007), their convergence pertains to the strategies being optimized rather than the time-average strategies. Timbers al.) (2022) introduced approximate exploitability, which uses an approximate best response computed through search and reinforcement learning. This is a generalization of local best response, a domain-specifff evaluation metric used in poker (Lisý & Bowling 2017)
Fiez et al. (022) consider minimax optimization min, max, f(x, y) in the context of two-player zero-sum games, where the min min-player (controlling x) tries to minimize ff assuming the max-player (controlling y) then tries to maximize it. In their framework, the min-player plays against smooth algorithms deployed by the max-player (instead of full maximization, which is generally Na-hard). Their algorithm is guaranteed to make monotonic progress, avoiding limit cycles or diverging be- havior, and finds an appropriate "stationary point" in a polynomial number of iterations. This work has important differences to ours. First, our work tackles multi-player general-sum games, a more general class of games than two-player zero-sum games. Second, their work does not use learned best-response functions, but instead runs a multi-step optimization procedure for the opponent on every iteration, with the opponent parameters re-initialized from scratch. This can be expensive for complex games, which may require many iterations to learn a good opponent strategy. It also does not reuse information from previous iterations to recommend good response. Our learned best- response functions can retain information from previous iterations and do not require a potentially expensive optimization procedure on each iteration.
Gemp et al. (022) proposed an approach called average deviation incentive descent with adaptive sampling that iteratively improves an approximation a Nash equilibrium through joint play by tracing a homotopy that defines continuum of equilibria for the game regularized with decaying
15

---

Under review as a conference paper at ICLR 2023
levels of entropy. To encourage iterates to remain near this path, they minimize average deviation incentive via stochastic gradient descent.
Ganzfried & Sandholm (2000a b) presented procedure for solving large imperfect information games by solving an infinite approximation of the original game and mapping the equilibrium to strategy profile in the original game. Counterintuitively, it is often the case that the infinite ap- proximation can solved much more easily than the finite game. The algorithm exploits some qualitative model of equilibrium structure as an additional input in order find an equilibrium in continuous games.
Mazumdar al. (2019) proposed local symplectic surgery, two-timescale procedure for finding local Nash equilibria in two-player zero-sum games. They showed that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due the existence of non-Nash stationary points. By taking advantage of the differential structure of the game, they construct an algorithm for which the local Nash equilibria are the only attracting fixed points. |Mazunaar al. (2020) analyze the limiting behavior of competitive gradient-based learning algorithms using dynamical systems theory. They characterize a non-negligible subset of the local Nash equilibria that will be avoided if each agent employs gradient-based learning algorithm.
Mertikopoulos & ( examines the convergence of no-regret learning in games with contin- action sets, focusing learning via "dual averaging", widely used class of no-regret learning schemes where players take small steps along their individual payoff gradients and then "mirror" the output back to their action sets. They introduce the notion of variational stability, and show that stable equilibria are locally attracting with high probability whereas globally stable equilibria are globally attracting with probability
Willi et al. (202)) show that the original formulation of the LOLA method (and follow-up work) is inconsistent in that it models other agents naive learners rather than LOLA agents. In previous work, this inconsistency was suggested as a cause of LOLA's failure to preserve stable fixed points (SFPs). They formalize consistency and show that higher-order LOLA (HOLA) solves LOLA's in- consistency problem if it converges. They also proposed a new method called consistent LOLA (COLA), which learns update functions that are consistent under mutual opponent shaping. It quires no more than second-order derivatives and learns consistent update functions even when HOLA fails to converge.
Perolat et al. (2022) introduce DeepNash, an autonomous agent capable of learning to play the imperfect information game Stratego from scratch, up to a human expert level. DeepNash uses game-theoretic, model-free deep reinforcement learning method, without search, that learns to master Stratego via self-play. The Regularised Nash Dynamics (R-NaD) algorithm, a key component of DeepNash, converges to approximate Nash equilibrium, instead of "cycling" around it, by directly modifying the underlying multiagent learning dynamics. Qin et al. (2022) proposed a no- regret style reinforcement learning algorithm PORL for continuous action tasks, proving that it has a last-iterate convergence guarantée.
B ADDITIONAL FIGURES
In this section, we present some additional figures. Figure illustrates Billusraass the probability density func- tions of each player after training in the Glicksberg- Gross game and the circle game with players. The black dashed line indicates the analytic equilibrium. Figure T illustrates the trajectories of each player's s action probabilities in the rock paper scissors game and the Shapley game. Since there are actions, the action probabilities are points on 2-simplex. The remaining figures compare different values of the hyperparameters and (the learning rate). They yielded qualitatively similar results.
C CODE SAMPLE
Listing shows example implementation of method in the Python programming language using Google JAX (Bradbury et al., 2018). We used Python version 3.7 and JAX version 0.3.24 for our experiments.
16

---

Under review as a conference paper at ICLR 2023
0.175
player
0.150
0.125
0.100
density
density
0.075
0.050
2-
0.025
player
1
0.000
0.0
0.2
0.4
0.6
0.8
1.0
-3
-2
2
action
(a) Glicksberg-Grre Gross game.
(b) Circle game (3 players).
Figure 3: Probability density functions after training.
LOLA
LOLA
(a) Rock paper scissors game.
CO
SGA
SGA
SLA
SLA
GNI
GNI
LA
LOLA
LOLA
ED
(b) Shapley game.
Figure Trajectories of each player's action probabilities. Left: Player 1. Right: Player
17

---

Under review as a conference paper at ICLR 2023
2074
20"1
3.0
Figure 5: Glicksberg Gross game with 7 = 0.1, 1, 10 (left to right).
10
30-F
0.20
0.25
0.50
1.00
1.25
3.75
2.00
0.00
0.33
0.52
0.75
1.00
1.55
2.00
0.00
0.25
0.50
Figure 2-player circle game with 7 = 0.1, 1, 10 (left to right).
10t
Py
CGA
1.00
0:00
0.23
0.50
1.50
1.25
1n6.
Figure 3-player circle game with 7 0.1, 10 (left to right).
10"
20
SGA
2011
JOLA
G61
10
20
202
1044
103
0.0
Figure 2-player Kuhn poker with 7 = 0.1, 10 (left to right).
18

---

Under review as a conference paper at ICLR 2023
10
10"
147
Figure 9: Glicksberg Gross game with = 10 10 2. x 10 4 (left to right).
20
18-1
0:08
0.23
0.30
1.50
1.5
155
Ind
Figure 10: 2-player circle game with 1j = 5 x 10 9,10-1,2 10 (left to right).
10P
GNI
100
Figure 11: 3-player circle game with 17 = 5 x 10-5 5, 2,104, 2 x
(left to right).
28-1
10
PM
5CA
20
20.4
202
22:4
10.2
10
1D3
28-11
100
Figure 2-player Kuhn poker with 7 = 10-3 10-2, x 10-2 (left to right).
19

---

Under review as a conference paper at ICLR 2023
Listing Example implementation of our method.
from jax import grad, tree_map
from jax lax import fori_loop
from jax. flatten_util import ravel_pytree
def restace(1st, index, value): return 1st[:index] [value] lst[index 1:]
def nikaido_isoda(u x, y):
return sum(
u(replace(x, i, yi))[i]
for i, yi in enumerate(y)
) (x))
def best_response__nnx w):
x_ x_vector, unravel ravel_pytree(x) ravel into flat vector A,
y_vector = A @ x_vector return unravel (y_vecoo)) # unravel from flat vector
def run(u, X, W, n: int, Ir: float):
...
utility function
strategy profile
best-response function parameters
n: number of steps
Ir: learning rate
The strategy profile should be list of pytrees. The utility function should take strategy profile input and return sequence of the same length containing each player's utility.
def objective w):
y bees__response_fit fx,, w) # best responses
return nikaido_isoda(Ce x, y)
def ustet, state):
x, state dx, goad(objective, [0, 1]) (x, w)
x_new mae_mbaap x, dx: x dx 1r, x, dx)
w_new tram_mapplambda w, dw: w dw * 1r, w, dw)
return x_new, w_new
x_ x_final, w_final fori_ n, update, (x, w))
return x_final
20

---

Under review as a conference paper at ICLR 2023
137
137
ED-eaact 16-33
10"0
60 exact jeid
ED 2e-4 Ie-5
50A
30
SLA
S04
5SA
CD
CD
EDetact:a-d3
10
LOKA
ED-ton
ED4
ID1A
2000
+093
6002
B00C
10000
2000
4000
2033
9002
10000
2000
4000
5000
3003
10000
stp
Sign game players).
(b) Sign game players).
(c) Antisymmetric game.
10'
m
13-3
10-1
ouist:c
SLA
10-0ott-3e-13
expiitaily
SCA
70
10
1D
10"
10-
10-mact:2--22
10 1n-31
S-A
IOLA
20000
30202
(d) Pennies game (2 players).
(c) Pennies game (3 players).
(f) Rock paper scissors game.
137
ED eocc te touccillt
10-7-
ID-cartie-dd S0react ds
Roweartlee 1e:44
12-4
CO
Hil-caat te
S.X
LOLA
02
CD
(D 16:3
20
OP
38-1
6D
10
lod
166
(g) Shapley game.
(h) Kuhn poker (2 players).
ii) Kuhn poker (3 players).
Figure 13: Exploitabilities.
D COMPARISON TO EXACT EXPLOITABILITY DESCENT
In many situations, we do not have access to exact best responses. Computing them can be inefficient intractable in complex games. Our method does not require them, and thus avoids that bottleneck. If we do have access to exact best-response oracles, we can try performing gradient descent on the exact exploitability function (x:) sup, pfI,, y), as in Lockhart et al. (2019). (Because of the supremum, & may not be differentiable even if is.)
Figure 13 compares our method (labeled ED-fun) exact exploitability descent (labeled ED-exact:1) where 77 a learning rate) on some games where we have access to the exact exploitability function (more precisely, its subgradients). On some of those games, ED-exact decreases quickly at first, but stops at a higher exploitability than ED-fun. This is likely because the exact exploitability function sup, (xx, y) may fail to be differentiable when the approximate exploitability function o(x, (x)) is. In that case, subgradient methods might be useful.
21


Reviews:
[{"review_id": "ncO085tqhI", "reviewer": "Reviewer_5nGD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work proposes a new dynamical system (continuous dynamics) where the players follow  a gradient ascent style dynamics per player but in order to adapt fast to their opponents, each player assumes that all the other players follow their best-response in its own strategy. At the same time, best-response would evolve as a functional with a gradient descent dynamical system.\nThe strategy profile and best-response functions are trained simultaneously, with the former trying to minimize exploitability while the latter try to maximize it. They evaluate our method on various continuous games, showing that it outperforms prior methods.", "summary_of_the_review": "In this work, the authors propose a new method for equilibrium finding based on the idea of learned best-response functions.\n", "strength_and_weaknesses": "In my humble opinion, this work is very incremental for the current venue. Since I want to give always the right of uncertainty, I will be really happy to read the answer of the authors in my objections.\n\nFirst of all, the continuous dynamics may hide certainly the actual complexity of the problem since it could run in exponential time. Secondly, I don't understand how much easy is to compute the best-response at every round when I have multiple players ( I refer to the case where strategies belong to some convex sets, like simplex). It is not clear, if best-response for the case of multiple players correspond to the product of constrained sets (Nash equilibrium style) or in general optimization framework (Coarse Correlated Best Response style). Thirdly, how we are sure that the BR functional is continuous, smooth differentiable ? \nHow much easy is to compute such a Best-response for a given strategy? If we use an Poly TM to compute it, why this is differentiable?\n\nAdditionally, I don't understand the intuition about the descent in the functional. Can you explain me where the concept of 'exploitability' is hidden in this setting?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "V_Khfffaom", "reviewer": "Reviewer_KfZH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem computing NE for continous games. It equipes exploitability descent with learned best-response functions to provide better convergence (in empirical). Plenty of experiments are conducted to show its better performance than previous works.", "summary_of_the_review": "The paper proposed a new algorithm to computing NE for continous games, which combines previous approaches properly. Plenty of experiments support its performance. Thus I am tend to accept it.", "strength_and_weaknesses": "Strength:\n1. The iead of introducing learned best-response function is interesting. It is not surprising that replacing the observed opponents' strategy by the learned opponents' best-response will lead to better performance. On the other hand, it seems to be a simpler and more general way (like a blackbox) to doing lookahead than previous approaches by modeling opponents.\n2. Plenty of experiments are conducted to evaluate the proposed algorithms. The solved games in this paper covers many common classes.\n\nWeaknesses:\n1. There is no theoretical guarantee on convergence or approximation bound.\n2. The \"exploitability\" itself may be too simple. Anyway, there should be a comparison with simply exploitability-descent (Lockhart et al. (2019)). Some intuition is that it is the \"learned best-response\" part make more contributions. Thus, it would also be better if an approach like GNI + learned best response is further compared.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NGa_H8rRij", "reviewer": "Reviewer_WPMd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a new method to compute approximate Nash equilibria of games with continuous strategy sets. Specifically, the new method minimizes an approximation of exploitability with respect to the strategy profile using learned best-response functions. ", "summary_of_the_review": "Considering the paper's strong assumptions and their justifications (more details in Weaknesses), I would not recommend it for publication in its present form.\n\nI have read the authors' response and would like to keep the same score.", "strength_and_weaknesses": "Strength:\n1. The authors did a thorough literature review on Nash equilibrium for continuous games and also compared the proposed method with these existing ones.\n2. The authors experimented with the proposed method on variant games from a naive sign game to Kuhn poker.\n\nWeaknesses:\n1. The authors assume that there exists an explicit fully-fledged function mapping different strategies for Player 1 to different strategies for Player 2. This is a very strong assumption and not well justified. In the experiment, the authors used a linear form best-response function which is an even stronger assumption. What if there are multiplier players and there are interactions among multiple players? Will the linearity still hold?\n2. The learning rate is fixed at 0.01 for all experiments except for Glicksberg–Gross game 10-4. It will be helpful to have some ablation study w.r.t. this hyperparameter if it needs to be carefully set. The same issue for the hyperparameter gamma. It is worth exploring how these two hyperparameters affect the convergence jointly.\n3. The authors claimed that 'If X is infinite and Y is nontrivial, X → Y is infinite-dimensional' and proposed neural networks to model the function b. This is an important use case but it seems that the authors did not offer any experimental results on it.\n4. In Fig. 1(a), it is not clear how the parameters of OP, SGA, CO, EG, and GNI evolve. It will help visualize the results to use different marks for different methods. The same issue for Figure 2.\n5. In Fig. 2(l), why ED(4) with rank 4 is better than the full-rank affine best response function? It is worth doing more ablation study w.r.t. the low rank when decomposing matrix A into I+UV.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AzrE5Qj1Yu", "reviewer": "Reviewer_u8oJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors study the problem of finding Nash equilibria in continuous games. Their key observation is that one of the reasons why algorithms for computing Nash equilibria fail is that players spend a lot of iterations re-learning the best response to a strategy of the other players. This happens even if the same strategies are repeated multiple times during the game.\n\nThe authors propose that players should learn the parameters of a best response function that learns to best respond to the other players. This function can be parametrized as affine functions or neural networks in the most general setting. Experimental results show that across a variety of games, the proposed approach can outperform prior work.", "summary_of_the_review": "In summary, I am willing to increase my score if the authors elaborate about the uniqueness/novelty of their approach or at least highlight some lessons learned from their experiments. As it is though, I am currently leaning towards rejection.\n\nAfter the responses of the authors, I have increased my score to a 6.", "strength_and_weaknesses": "Regarding strengths, the paper is clearly written with the notation, motivation and the intuition of the approach being very clearly and thoroughly introduced. To the best of my knowledge, this is the first work to propose the learned best responses framework in its full generality where the learned best response function can be arbitrarily parametrized in terms of $\\theta$.\n\nRegarding weaknesses, the concept of learned best responses is not entirely new. For example, [1] proposes an instance of the learned best response framework where the adversary learns a weighted average of fixed smooth functions of the opponent's strategy. The individual algorithms may run GD on an objective for a fixed initialization for a fixed number of epochs. But in principle, any smooth function can be used. Even in this limited setting, one does not need to worry about cycling when using gradient ascent descent. \n\nGiven that learned best responses are not entirely new, I would suggest to the authors to highlight how/when the generality of their framework is useful or lessons learned about these problems from their experiments.   \n\n\n\n[1] Tanner Fiez∗, Lillian J. Ratliff, Chi Jin, Praneeth Netrapalli, MINIMAX OPTIMIZATION WITH SMOOTH ALGORITHMIC ADVERSARIES, ICLR 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject