Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Authors: Linjian Meng
Wubing Chen
Wenbin Li
Tianpei Yang
Youzhi Zhang
Yang Gao
Venue: ICML 2025 spotlightposter (2025)
Keywords: Stochastic Optimization
Nash Equilibrium
Normal-Form Games
Primary area: theory->game_theory
TL;DR: We propose a novel surrogate unbiased loss function for learning a Nash equilibrium in normal-form games via stochastic optimization techniques from machine learning.

Abstract: Nash equilibrium (NE) plays an important role in game theory. How to efficiently compute an NE in NFGs is challenging due to its complexity and non-convex optimization property. Machine Learning (ML), the cornerstone of modern artificial intelligence, has demonstrated remarkable empirical performance across various applications including non-convex optimization. To leverage non-convex stochastic optimization techniques from ML for approximating an NE, various loss functions have been proposed. Among these, only one loss function is unbiased, allowing for unbiased estimation under the sampled play. Unfortunately, this loss function suffers from high variance, which degrades the convergence rate. To improve the convergence rate by mitigating the high variance associated with the existing unbiased loss function, we propose a novel surrogate loss function named Nash Advantage Loss (NAL). NAL is theoretically proved unbiased and exhibits significantly lower variance than the existing unbiased loss function. Experimental results demonstrate that the algorithm minimizing NAL achieves a significantly faster empirical convergence rates compared to other algorithms, while also reducing the variance of estimated loss value by several orders of magnitude.

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Linjian Meng'
Wubing Chen Wenbin Li"
Tianpei Yang'
Youzhi Zhang? Yang Gao
Abstract
equilibrium (NE), where no player gains by unilaterally de- viating from it. However, computing an NE often involves a complex, non-convex optimization problem. Theoretically, computing an NE known to be PPAD-complete and thus computationally intractable (Daskalakis et al., 2009).
Nash equilibrium (NE) plays an important role in game theory. How to efficiently compute an NE NFGs is challenging due to its complex- ity and non-convex optimization property. Ma- chine Learning (ML), the cornerstone of modern artificial intelligence, has demonstrated remark- able empirical performance across various appli- cations including non-convex optimization. To leverage non-convex stochastic optimization tech- niques from ML for approximating an NE, various loss functions have been proposed. Among these, only one loss function is unbiased, allowing for unbiased estimation under the sampled play. Un- fortunately, this loss function suffers from high variance, which degrades the convergence rate. To improve the convergence rate by mitigating the high variance associated with the existing un- biased loss function, we propose a novel surro- gate loss function named Nash Advantage Loss (NAL). NAL is theoretically proved unbiased and exhibits significantly lower variance than the exist- ing unbiased loss function. Experimental results demonstrate that the algorithm minimizing NAL achieves a significantly faster empirical conver- gence rates compared to other algorithms, while also reducing the variance of estimated loss value by several orders of magnitude.
Machine Learning (ML) (Mitchell Mitchell, 1997) is a predominant technology in contemporary artificial intelli- gence, demonstrating remarkable performance in diverse real-world applications including non-convex optimization problems such as image and speech recognition (Deng et al., 2014), natural language processing (Achiam et al., 2023), autonomous vehicles (Bojarski al., 2016), and financial modeling (Heaton et al., 2017). Since NE computation known to be non-convex optimization problem (Gemp et al., 2024), leveraging ML for NE computation presents promising research direction. However, the application of ML to NE computation remains largely unexplored.
A significant challenge in applying ML to compute an NE is designing an appropriate loss function. Specifically, for an n-player, m-action, general-sum normal-form game (NFG), storing the payoff matrix requires nm" entries. As and n increase, the storage complexity 0(mm") grows expo- nentially, making it computationally prohibitive to load the entire payoff matrix into memory for large-scale NFGs. Thus, sampling a portion of the payoff matrix becomes nec- essary, iee., minimizing the expectation of random variable using non-convex stochastic optimization techniques in ML. However, most existing loss functions (Nikaidô & Isoda, 1955; Shoham & Leyton-Brown 2008; Raghunathan et al., 2019; Gemp et al., 2022; Duan et al., 2023) introduce bias under the sampled play, which can be seen as the stochastic optimization setting in MI, making it infeasible to compute an NE under this setting. To address this bias, Gemp et al. (2024) propose a loss function that can be unbiasedly esti- mated under the stochastic optimization setting. However, it suffers from high variance, as its value is estimated via the inner product of two independent and identically distributed random variables, whose variance is the square of that of estimating an individual random variable, thus significantly degrading the convergence rate.
1. Introduction
Game theory is a powerful tool for modeling multi-agent in- teractions. A common goal in addressing games is the Nash
'National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China "Centre for Artificial Intelli- gence and Robotics, Hong Kong Institute of Science & Innovation, Chinese Academy of Sciences. Correspondence to: Tianpei Yang <tianpei. @aonn@@nju.ddc www..cu.u........... Youzhi Zhang <youzhi, zhang @ cair- cas.org.hk>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
To improve the convergence rate by mitigating the high vari- ance associated with the existing unbiased loss function,

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
propose a novel surrogate loss function called Nash Advan- tage Loss (NAL). Our key insight is: finding way to obtain an unbiased estimate of the first-order gradient to eliminate the need for calculating the inner product that introduces
matrix grows exponentially. Although many works (Gok- tas et al., 2022; Marris et al., 2022; Liu et al., 2024) have investigated computing an NE via optimization techniques of ML, they did not consider whether loss functions would incur bias under the sampled play, which can be interpreted as the stochastic optimization setting in ML. Actually, most existing loss functions (Nikaidō & Isoda, 1955; Shoham & Leyton-Brown, Brown, 2008; Raghunathan et al., 2019; Gemp et al., 2022; Duan al., 2023) will incur bias under the sampled play. Specifically, these functions are biased under the sampled play due to either (i) the presence of a random variable as the argument of a complex, nonlinear function, or (ii) the unclear sampling methods (Gemp et al., 2024). For instance, duality gap-based loss functions (Nikaidō & Isoda, 1955; Shoham & Leyton-Brown, 2008; Duan et al.. 2023; Gemp et al., 2022) incur bias through a max operator. Additionally, Gradient- Nash Iteration (NI) (Raghu- nathan et al., 2019) is biased due to a projection operator that projects a random variable onto the simplex, which involves a max operator (Chen & Ye, 2011). Moreover, unconstrained optimization methods (Shoham & Leyton- Brown, 2008) that penalize deviation from the simplex lose the ability to sample from strategies when any iterate is no longer within the simplex. To mitigate the bias under the stochastic optimization setting, Gemp et al. (2024) propose loss function that allows unbiased estimation under this setting. However, it suffers from high variance.
high variance. Specifically, previous works have overlooked the fact that commonly used non-convex stochastic optimiza- tion techniques in ML (Robbins & Monro, 1951; Bottou, 2010; Kingma& & Ba, 2014) require only unbiased estimates of the first-order gradient, not the loss function itself. Con- sequently, NAL ensures that obtaining an unbiased estimate of its first-order gradient does not require computing the inner product of the two random variables, avoiding the high variance associated with such computations. In addition, we demonstrate that the first-order gradient of NAL can ap- proximate that of a variant of the loss function proposed by Gemp al. (2024) under certain conditions. This implies that when applying commonly used non-convex stochastic optimization techniques in MI., minimizing NAL approxi- mates the process of minimizing the loss function proposed by Gemp et al. (2024), while mitigating the high variance caused by the inner product of two estimated variables.
We conduct an empirical evaluation of the convergence rates and the variances of the estimated values of the loss func- tions on eight NFGs from OpenSpiel (Lanctot et al., 2019) and GAMUT (Nudelman et al., 2004). Our results reveal that the algorithm minimizing NAL substantially outper- forms algorithms that minimize existing unbiased or biased loss functions in terms of the convergence rate. Addition- ally, our algorithm exhibits significantly lower variance in the estimated values of its loss function than the algorithm minimizing the existing unbiased loss function. Particularly, compared to the existing unbiased loss function, the vari- ance in estimating the value of NAL is typically reduced by two orders of magnitude. In some games, this variance reduction can even reach six orders of magnitude. Further- more, we analyze the discrepancies between estimated and true values for different loss functions. Our findings indicate that the difference between the estimated and true values for our loss function is usually two orders of magnitude smaller compared to that of other tested loss functions.
Our approach is different from algorithms that replicate tabular methods, i.e., those that use deep neural networks (DNNs) (LeCun et al., 2015; Goodfellow, 2016) to approx- imate variables in tabular algorithms without modifying the update rules, such NFSP (Heinrich & Silver, 2016), PSRO (Lanctot et al., 2017), and Deep CFR (Brown et al., 2019). These algorithms employ non-convex stochastic op- timization techniques to train a DNN for approximating variables in tabular algorithms, rather than directly comput- ing an NE. More details can be found in Appendix B.
In addition, while our algorithm bears resemblance to exist- ing simultaneous gradient descent algorithms (Sokota et al., 2023) under a certain specific setting, this setting is not sup- ported by our algorithm (Appendix C). Specifically, even when an NE is learned, existing simultaneous gradient de- scent algorithms may continue to operate and deviate from this NE rather than halt their progress, while our algorithm cease once the NE is reached. This distinction is clearly demonstrated in our experimental results, which show that under the same set of conditions, our algorithm successfully converges to the NE, while the traditional simultaneous gradient descent algorithms fail to do so. Moreover, we establish a connection between NAL and the loss function in Gemp et al. (2024), which does not hold for any existing simultaneous gradient descent algorithm. Additional details can be found in Appendix C.
2. Related Work
Our research aligns with studies that conceptualize the prob- lem of computing an NE in NFGs as a non-convex optimiza- tion problem and address it through non-convex stochastic optimization techniques in ML due to their remarkable em- pirical performance in solving such problems (Chen et al., 2019; Zou et al., 2019). Specifically, we focus on studies that reduce NE computation to minimize a loss function via non-convex stochastic optimization techniques in ML.
Sampling is critical for solving large-scale NFGs since the action size increases lincarly while the shape of the payoff
2

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
3. Preliminaries
-Va, uz(x) + 7 log a, and F. = Eoue F. (a:)/ As the utility func- tion uf ()) of each player is concave over X,, Va,, df E Ai, Va,"/ (a:)(a;) = uz (x)((a) if and only is an NE of the regularization game. In other words, (x) = O if and only if is NE of the regularization game. By gradually decreasing the sequence of NEs of the regular- ization games converges to an NE of the original game. The advantage of this function is that this function can be unbias- edly estimated given two independent unbiased estimations of FT
where F = - -Va; (e
Normal-form games (NFGs) are fundamental games in game theory (Osborne et al., 2004), which consists of play- ers N 2..,,..., n). an action set A, for each player and a utility function u; for each player i. Each player i E N simultaneously chooses an action u; E A, and re- ceives a utility u,(a,, a-1) E [0, LJ, where -i denotes all players except player i. The strategy of player i is rep- resented by I; E X; and the strategy profile is denoted as æ = { E X: | á E M}. where X; is a (IAi) - 1)- dimensional simplex. The strategy space of all players is represented by X' X.evx;; Moreover, the inte- rior of X is denoted as X². Precisely, for each æ E X², a, (a;) > 0, Vi E N and E A,, The utility of player i, given that all players follow the strategy profile æ E X, (y(a)), [az)), where aj E A denotes player j is component of the joint action a.
To improve the readability, we include table of notations and definitions, as shown in Appendix A.
4. Our Method
is u, x-.) = EaEx.gN uy (a(a)
To the best of our knowledge. Gemp et al. (2024) propose the only unbiased loss function that enables unbiased estima- tion when computing an NE by using non-convex stochastic optimization techniques of MI. However, this loss function often exhibits high variance, resulting in significant insta- bility that degrades the convergence rate. To address the high variance, we propose a novel surrogate loss function, termed the Nash Advantage Loss (NAL).
Nash equilibrium (NE) describes a rational behavior where no player can benefit by unilaterally deviating from the equilibrium. As analyzed in Facchinei (2003), if the utility function of each player i is concave over X' an NE x is such that (V., u4: (z)))) x; 2;) < 0, Vi E N' and x E X. This concavity condition is satisfied in NFGs since the utility function of each player is linear over X, We denote the set of NE by X'. If the utility function of each player is concave over X,, a well-known metric to measure the distance from the strategy profile æ to NE is the duality gap: dg(x)) = ESeN max Ex (Va, 2, (x)x), 2z zz). If and only if dg(ær) = O, x E X If dg(x) = 8. then x is a 6-NE. 2 denotes interior NE that Vx= E x x (a.)) > 0, Vi E N, 0; E A.. The duality gap is the upper bound of exploitability; exp(x)) = EieN u,(2%, x.)) u,,,,, x) S dg(x:)/Wi as uz(-) is linear over X-
4.1. Overview of NAL
Our key insight is: finding a way to obtain an unbiased estimate of the first-order gradient to eliminate the need for calculating the inner product, which introduces high vari- ance. In particular, the insight comes from fact overlooked in previous works that commonly used non-convex stochas- tic optimization techniques of ML (Robbins & Monro, 1951; Bottou, 2010; Kingma & Ba, 2014) require only unbiased estimates of the first-order gradient.
Existing unbiased loss function. To our knowledge, the only known unbiased loss function for approximating an NE is proposed by Gemp et al. (2024). The key insight of this loss function is that gradients of all actions, w.r.t. an interior strategy profile x E X; are equal if and only if X when the utility function of each player i is concave over X, Formally, for any x X and Va,, df E Ai, Væ, (a,) if a E x when the utility function w; (x) of each player i is concave over X; (Gemp et al., 2024). To ensure that the interior NE always exists, they add an entropy - log x; to each player's 's utility function, where F > 0 is constant. From their analysis, the addition of entropy guarantees that all equilibria of the regularization game with utility function ur (x=) ux(x) rœ." log x; are interior. Formally, given a strategy profile x E X, their loss function is defined as follows:
Lemma 4.1. For any vector b E Rd and any y in a (d (d-11 1)- dimensional simplex, the equation b- (b, y) 1 = 0 holds if and only if all coordinates of b are all equal to each other.
Specifically, NAL aims to ensure that (i) its first-order gradi- ent can be estimated without bias by using single random variable to reduce the variance, and (ii) its first-order gradi- ent with respect to E X equals 0 if and only if x E X to ensure that the algorithm stops once an NE is learned. To achieve these, we build on the key insight from the loss function in Gemp et al.
N, Ve, (a() if and only
where for any æ E X E N, and a, df E A,, Va, (a.) = V (x) if and only if x E x="0_and recognize that Va, un (x) can be estimated without bias using single random variable (e.g., via importance sampling). Then, inspired by Lemma 4.1, we define NAL's first-order gradient as the difference between the gradient of the utility function of the game and the inner product of the utility function's ''s gradient with any arbitrary given strategy क. This difference is the advantage
(z) =
T
F T
(1)
iEN
3

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
of each action's gradient for making the gradients of actions more uniform. Formally, the first-order gradient can be
of AL is used for non-convex stochastic optimiza- tion techniques in ML to update the strategy profile. Further details the unbiased estimation process are in Section 4.3.
(-Va,u;()) + (Va, (x()) 1 i E EM.
Relationship between duality gap in the regularization game and NAL. As analyzed in Gemp et al. (2024), Va,, aj E A,, V æ, uz (a)) = Va, 25 (a)( holds if and only if a: is an NE of the regularization game with the utility function u, (a)). Then, from Lemma 4.1, we have that V, AL (a)) = if and only if a is an NE of the reg- ularization game with the utility function uē (a). A formal relationship between the duality gap of strategy profile in the regularization game and the gradient of NAL is in Theorem 4.2. The proof of Theorem 4.2 depends on the properties of the tangent residual (Cai et al., 2022).
As Vo X,, E N and o of E A,, V (a)
V., (a() if and only if x X", from Lemma 4.1, we have that Vx X,, [-Va, (x)) + (Væ, (,(x), #;)1 i E M1 = 0 if and only if x E X In addition, to ensure that the interior NE always exists, as done in Gemp et al. (2024), we add an entropy -r log x; to each player's utility, where T > 0 is a constant. As we mentioned above, Gemp et al. (2024) show that the additional entropy guar- antees that all NE of the regularization game, with utility function u5 (x) (x) T log T, are interior.
Now, we provide the formal definition of NAL. Given a strategy profile x E X, N.N is defined as
Theorem 4.2 (Proof is in Appendix E.2). The duality gap of a strategy profile x in the regularization game with the utility function u² (a:) = us uz(x)) - T log æ.; is bounded as:
(z) = Σ (sg[F (F 11)1)
iEN
dg (2) = Σ max ( ug (x), - -xa)
iEN xx
& can be any strategy pro- where å = [ ...... .....
file in X' (notably, Vi E .N. 2; * 0 and must in X.), FT. = - u. (z) = Ve,u, (x) + T log x; is defined in Eq. (1), and sg[-] is the stop-gradient operator that im- plies the term in this operator is not involved in gradient backpropagation, i.e., for any variable b E IRd, sg(b] = b while [b] = 0 (see details in Appendix D). There- fore, in Eq. (2), æ; participates in gradient backpropagation, whereas sg[ [F -FF 1.)1] do not. Consequentially, we obtain Vz, AL = sg (F. 1.. As a in NAL can be any strategy, not just æ,, we are free to employ any sampling strategy to estimate Vz, Ar ( to
<CollVafxAL(
where Co is game-dependent constant.
For the exploitability in the regularization game, we have expx (x) of (æ;, -))\/A] S dg (x)/IM1 since the fumction u. (zx) is linear and -r log x; is concave over X,, respectively, as well as for any concave function f(-) with any u, v in its domain, the inequality f'uu) - [(v) S (VS(v), u v)
Ese uī (x) x)
holds.
further reduce the variance.
Relationship between duality gap in the original game and NAL. NAL ensures that a zero point of the first-order gradient of NAL corresponds to NE of the regularization game rather than the original game. To find an NE of the original game, we establish a precise relationship between the duality gap in the original game and NAL, as shown in Theorem 4.3. This relationship allows us to approximate an NE of the original game by minimizing NAL. Specifically, by progressively decreasing the value of т, we guarantee that the sequence of NEs of the regularization games, charac- terized by the utility function u, (x) u, (xxx)= - -x log xi converges to the set of the NE of the original game.
While other loss functions do not include the soppggradient operator in their definitions, in practice, these loss functions must employ the stop-gradient operator when solving real- world games. This is because Vz, (z)) in FT cannot feasibly participate in gradient backpropagation. Enabling F to participate in backpropagation would require iter- ating over all action pairs for every two players, as done in Gemp et al. (2022) and Gemp et al. (2024), which is practi- cally infeasible in real-world games. More details about the implementation of other loss functions are in Appendix G.
Unbiased estimation of NAL. Assume we can obtain an unbiased estimate of FT which can be achieved through importance sampling. as described in Section 4.3, Since F is estimated without bias and क; is given, we have that (FT. ,.)) remains unbiased. By using the unbiased esti- mates of F and (F ...). we can obtain an unbiased estimate of Va. (AZA( Then, with the unbiased esti- mate of Va, CT (z) and knowledge of x; an unbiased estimate of At (a:) is obtained. This unbiased estimate
Theorem 4.3 (Proof is in Appendix E.4). The duality gap of a sirategy profile x: in the original game is bounded as:
dg(z) TC + C2 (m)]l2,
where C1 and C2 are game-dependent constants.
From the analysis above, we observe that NAL learns the global minimum of the loss function proposed by Gemp
4

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
et al. (2024), without requiring the inner product between the two estimated variables that introduces high variance (Section 4.2). Therefore, NAL can be viewed as a surrogate for the loss function in Gemp et al. (2024), which is why we refer to NAL as a surrogate loss function. Furthermore, as demonstrated in Appendix and H. under specific con- ditions, the first-order gradient of NAL approximates that of a variant of the loss function proposed by Gemp et al. (2024), while mitigating high variance. It implies that min- imizing NAL approximates the process of minimizing the loss function proposed by Gemp et al. (2024)
Algorithm 1 Learning an NE via Minimizing NAL
1: Input: An optimizer OPT. the exploration ratio c, the uni- form strategy profile x:" = [x:" j E EM, the initial parameter 0, the learning rate 1), the regularization scalar т, the number of total iterations T, the number of instances S sampled at per iteration, the frequency T., of updating 1j and r. the weight on updating 1/. the weight /3 on updating r, simulator G that returns player i's payoff given a joint action.
2: for each & E [1, 2.... , do
.T]
3: Initialize buffer M, < (. ViE
4:
v, + 0, vi E EW
5:
for each 8 E [1, 2, , do
6:
a, a; Vi E
7:
a x+ a
4.2. Analysis of Variances of NAL and Existing Unbiased Loss Function
8:
a, ~ (1 =)=² + ea... vi ViEN
9:
ps t (1 - c)æe (al) + caf Vi N
10:
Ts df a-i) + logaf Vi E N // To
We now analyze the variance in the estimated values of NAL and the unbiased loss function defined in Eq. (7). We demonstrate that when the variance in estimating the value of NAL is O(a), that of the unbiased loss function defined in Eq. (7) may be ( where > 0 is a constant.
estimate p. (d))
11:
Mi.append((;, de, Ti, pil), ViEN
12:
V; +- v2 +
13:
end for
14:
() t 0
0s + " Vi E NWW To estimate (F. "
15:
.t,)
Firstly, assume that the components of the vector FT (FT.", . at each a; E Ai are estimated independently, with the variance for each estimation being less than a. Specifically, let the estimation of F.T (F.".", , at ac- tion a; E .A, be denoted as (,,"(aa) Under this assumption, 9, TT (a'), where 1 denotes that the two
16:
for each i E N do
17:
for each 1 at af.
pf]
E
M. do
m eat II To estimate F
18:
g
(F
.x:)1
19:
()) t- (0) + (sg19/). af
we have 9, (a²
20:
end for
random variables are independent, and Varlg, - (a:)] = o for all ag d, A, By the definition of variance, the vari-
21:
end for
22:
&- OPT uppatetd (2 AL (0))
ance of (x) is
23: if 1% = 0 then
24:
+ on, T + Br
Var(CNvAL [z)] = Σ
(a.))
25:
end if
26:
end for
iEN a:EA;
27:
Return
Σ
(a:)
iEN a:EAA
where the last inequality follows from Appendix F. Thus, the variance in estimating (x) is a minge |AAi] times larger than for NAL. Then, the variance in estimating (a) is expected to be substantially higher than that of NAL.
IIWoo,
where the second equality is from that for a random variable Y with constant e, Var e² Var and the inequality follows from the fact that Exres, (a:))) <1.
4.3. Minimizing NAL under the sampled play
For the unbiased loss function defined in Eq. (7), we make similar assumptions. Specifically, let the two esti- mates of (a:) F. be g. (ax) and andg. x..2 (a.), assume that each g, " is sampled independently Vi E N, a; E A,, j E (1, and the variances for
We now detail our algorithm that Iearns an NE by mini- mizing NAL. The pseudocode is in Algorithm 1. Specifi- cally, consider an approximation function II(.) parameter- ized by 0, where the resulting strategy profile is denoted as ω II(0). Our goal is to minimize the following loss function L AL))(() (0) through a two-step process: sampling and updating.
each estimation are less than a. Formally, Vi E W,
a, of E Ar, j.j' E (1, g," (a:) L g, p.. (a/) and Var g 7.0.. (a,)) = a. Then, the variances of the estimation for this loss function are
(0)
Σ [sg[FT EN
(FTT" ..)1)
Varl (x))
Σ Σ
Varlg, 1.g...1(... (a.)g, =..))
VEN:EA::
miig|A.1
Sampling. The sampling process is outlined from lines 3 to 13 in Algorithm 1. At each iteration t, we begin by ini- tializing the buffer M, = O and the random variable it for
2////o iE MEA.
min (o.) (a.)))
(a.))l2min] Ail, TEN
5

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
each player i (lines 3 and of Algorithm 1). The random variable 02 is used to estimate the value of -(FT a .;)). Next, for each player i, S instances are sampled. In each instance, an action O; is selected for each player i according to the strategy profile xd (line 6 of Algorithm 1), resulting in the action profile a [a: i E M (line 7 of Algo- rithm 1). Each a_; = la, J E N.j & i] serves as the environmental dynamic for player i, enabling the estima- tion of Ar. (0). Subsequently, based on the exploration parameter e, the uniform strategy profile x" (x = 1/ and the current strategy profile x², an alternative action af is sampled for each player according to the strategy a; = (1 - ))ae + ex. (line of Algorithm 1). The explo- ration parameter and the uniform strategy x" ensure that the probability of selecting any action within the strategy à; is not too small, which guarantees the variance of estimat- ing via importance sampling is not too large. The probability of selecting action af through ē; is denoted by pi (line 9 of Algorithm 1). The unbiased estimation of F (af) is then computed as r; f- (i. d/, a-1) + T log x (af); Vi E N (line 10 of Algorithm 1), where 9 represents the simula- tor returning player i's payoff for the joint action [ab, a-:). Specifically,
and all other coordinates are O. It is straightforward to
verify that Elg;] = F. (F 2.)1. Formally,
1 Us
Eigi] -Bawit:
Dt enq
(5)
F.T.a0 (a.) - (F.
(ii Ea?
P!
where the second equality is from E[ri]] = F. F.Tee
x (a;) (Eq.
(3)), B(es] = (PT.") ..a)) (Eq. (4)), and (r3 ui) 1 pf (as P is given and not sampled, which can be seen constant). As the rightest side of Eq. (5) a standard impor- tance sampling process, it follows from the properties of importance sampling that
F 0 (a²) (F.T. ar)) ea?
[E(g = =Begas:
-Fr (F 80
1.
The estimator AZ (0) is updated via (0) <-
x.) (line 19 of Algorithm 1). Since Elg;] = F (F 2.)1 and x. is known, it follows that 1/ [ = (O). Therefore, Ai pro- vides an unbiased estimate of AI, The estimator (l) is then passed to the optimizer OPT for updat- ing 0 (line 22 of Algorithm 1). If 1%T, u = 0 (line 23 of Algorithm 1), the parameters 7) and T are updated as + (0) and T + BT, where 0 < ax B < 1 (line 24 of Algorithm 1). These adjustments ensure that an NE of the regularization game approaches an NE of the original game, Specifically, as shown in Theorem 4.3, decreasing r brings the NE of the regularization game, defined by the utility function uz (z) = u(xx) πω. log a., closer to that of the original game. Furthermore, reducing 1) stabilizes the algorithm as we find that without a corresponding reduction in v), decreasing T could destabilize the learning process.
B(rd] = ((, d/, a)) 7 log 2r (a/)) -E G(i, di, a a))] + T log 0 (a/)
(3)
-F 2 (a!) + r log x (a!) = F. (af).
where the third line follows from the fact that a_; is sampled according to x²_- Finally, the tuple ( a/s ris pi] is stored in the buffer M; (line 11 of Algorithm 1), and Us is updated as 02 + v2 + r; (line 12 of Algorithm 1).
Updating. The updating procedure is outlined from lines 14 to 25 in Algorithm 1. We first initialize the estimator for AL (0) as AL (0) <- 0 and normalize vs by setting u + S (lines 14 and 15 of Algorithm 1). The expectation E E[us] corresponds to (FT.0" tt).. Formally,
We do not provide the convergence for our algorithm as this convergence depends on the stochastic optimization technique used, which is not the focus of this work. Theoret- ically learning the zero point of the first-order gradient via non-convex stochastic optimization techniques is an urgent problem to be solved. Solving this problem falls under the research direction of optimization rather than game theory.
9
Elv,] = E
E
F
(at)
S
S
(4)
Eag
E
F7 (at)
= =(F.
where of and r come from the s-th tuple [i, az, rg. pt] stored in buffer Mi, the second equality is from E[r[]]
5. Experiments
Configurations. We compare algorithm with algo- rithms that minimize the loss function in Gemp et al. (2024), ADI (Gemp et al., 2022), or NashApr (Duan et al., 2023), re- spectively. Our loss function and the loss function in Gemp et al. (2024) are unbiased loss functions, while others are biased loss functions. The implementation details of the
pr (at) (Eq, (3)), and the third equality is from that of
is sampled via e; Additionally, we use the tuples in M;
(line 17 of Algorithm 1) to estimate F (F 1 e through the computation g + x eaz (line 18 of Algo- rithm 1), where eag is a vector whose the coordinate ot is
6

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
0.4
Kuhn Poker
Goofspiel
0.8
Bletto
Liar's Dice
0.6
duality
0.2
0.4
0.4
0.2
0.2
0.2-
0.0
0.0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
0.6
Bertrand Oligopoly
2.5
Guess
1.0
Majorily Voting
1.25
2.0
0.8
1.00
1.5
0.6
0.75
0.2
1.0
0.4
0.50
0.5
0.2
0.25
0.0
0.
0.0
5000
7500
10000
5080
7500
10000
2500
5000
7500
10000
2500
5000
7500
Iterations
Iterations
iterations
iterations
Ours
Gemp et al., 2024
ADI
NashApr
Figure 1. Empirical convergence rates of tested algorithms when the optimizer is Adam. The top row shows the following scenarios from left to right: 2 players with 64 actions, 2 players with 384 actions, 4 players with 66 actions, and 2 players with 2304 actions. The bottom row displays, from left to right: 4 players with 50 actions, 4 players with 50 actions, 5 players with 30 actions, and 11 players with 5 actions. The shaded regions represent one standard deviation of the results, calculated across four different random seeds.
compared loss functions are in Appendix G. Notably, the implementation of all tested loss functions includes the stop- gradient operator. We conduct experiments eight NFGs from OpenSpiel (Lanctot et al., 2019) and GAMUT (Nudel- man et al., 2004), specifically Kuhn Poker. Goofspiel, Blotto, Liars Dice, Bertrand Oligopoly, Guess Two Thirds Ave, Minimum Effort, and Majority Voting. The former four games are sourced from OpenSpiel, while other games are implemented by GAMUT. The payoff matrix components of each game are normalized to a range between 0 and 1. All experiments are performed on a machine equipped with four RTX 3060 GPUs and 376 GB of memory.
tested algorithms, c is fixed at 1, T 10,000, and S at 10 across all games (unless otherwise stated). We perform an extensive hyperparameter search, varying the learning rate r E {0.0001, 0.00001), regularization scalar E {0.1, 1). update frequency Ta E {200, 500, 1000}, and momentum coefficients or, B E {0.9, 0.5). The selected hyperparame- ters are listed in Appendix I.
Results on convergence rates and variances. We run each algorithm four times with different random seeds. The results, including convergence rates and variances, are pre- sented in Figures and 2, respectively. Our algorithm achieves the fastest empirical convergence rate and the low- est variance. Specifically, we find that, in Goofspiel and Minimum Effort, the algorithm minimizing the existing un- biased loss function in Gemp et al. (2024) fails to converge to an NE. In contrast, the algorithm minimizing NAL able converge an NE. Additionally, algorithms based biased loss functions occasionally fail to converge. For example, the algorithm minimizing ADI does not converge in Blotto, and the algorithm minimizing NashApr fails in Liars Dice. In addition, the variance in estimating NAL decreases by at least two orders of magnitude for all tested games compared to using the existing unbiased loss func- tion, and in Liars Dice, this variance reduction reaches up to six orders of magnitude. We also find a strong correla- tion between variance and convergence performance. In Bertrand Oligopoly, where the algorithm minimizing the ex- isting unbiased loss function in Gemp et al. (2024) performs closest to ours, it is the only case where this algorithm's ''s variance in estimating the value of the loss function lower than that of our algorithm. However, due the extremely
We use a DNN parameterized by 0 to represent strategy profiles due to the strong expressive power of DNNs, as did in previous works (Goktas et al., 2022; Marris et al., 2022: Liu al., 2024) (see discussions in Appendix B). The network used in this paper is a three-layer MLP, with 1024 neurons in both the input and hidden layers, and IV| heads in the output layer, each corresponding to the action space of a player. For all games, the input is a 1024-dimensional vector with all coordinates set to 1. ReLU activation is used in the hidden layers (Krizhevsky et al., 2012), and Softmax activation is applied in the output layer (Dempster al., 1977) (unless otherwise stated), ensuring the output remains within the simplex. Neural networks and optimizers (stochastic optimization techniques) are implemented using Py TyToch (Paszke et al., 2019), with Adam (Kingma & Ba, 2014) as the optimizer (unless otherwise stated), due to its widespread use in training modern neural networks, includ- ing GANs (Goodfellow al., 2014), BERT (Devlin, 2018), GPT (Brown, 2020), and VIT (Dosovitskiy, 2020). For all
7

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Goofspiel
10
Larr's Dice
10
1010
10
veriance
10a
10a
107
10-
10a
10'
10.
10a
10a
10a
10-3
10
10-1
10-2
25000
5000
75.00
10000
2500
2500
5000
75.00
10000
2500
5000
7500
10000
Bortrand gopply
Guess Two Thirds Ave
Minimum Fffort
Majority Vating
100
10a
101
10
10
10a
10-1
veriance
10-1
10
10-3
10-3
10-9
10
10-6
10-4
10-2
10-1
2500
5000 Iterations
75000
10000
5000
2500
5000
75:00
10000
2500
5000
7500
10000
Iterations
Ite rotions
Iterations
Ours
Gomp at al., 2024
ADI
NashApr
Figure 2. Variances observed in estimating the value of loss functions used by different algorithms when the optimizer is Adam.
high variance early on, this algorithm's convergence rate re- mains slower than ours, Although the algorithm minimizing NAL does not appear to converge to an exact NE in Kuhn Poker and Liars Dice, this is primarily due to the value of S being insufficiently large. As shown in Appendix J, when S is increased, our algorithms can also converge to a more and more accurate NE in both Kuhn Poker and Liars Dice.
mizer are in Appendix J. Consistent with the results using Adam, our algorithm exhibits the fastest convergence rates, lowest variance, and smallest difference.
Results on sampling times and convergence rates with different sampling methods. We also present experimental results for algorithms that employ the sampling method from (Gemp et al., 2022) and Gemp et al. (2024), as described in Appendix J. Specifically, we compare sampling times between the method in (Gemp et al., 2022) and Gemp et al. (2024) with the method Algorithm 1, and evaluate the convergence rates of algorithms employing the sampling method used in (Gemp et al., 2022) and Gemp et al. (2024) as well as the sampling method in Algorithm 1, respectively. Experimental results show that both the sampling method in Algorithm 1 and our loss function, NAL, significantly enhance the convergence rate.
Results on differences between estimated and true loss values. To determine whether NAL is an unbiased loss function, we compare the differences between the estimated and true loss values across the various algorithms, as shown in Figure 3. Empirical results confirm that NAL behaves as an unbiased loss function, exhibiting significantly smaller differences between true and estimated values compared to other loss functions. More precisely, the difference between the estimated and true values for NAL is usually two orders of magnitude smaller compared to that of other tested loss functions. As the difference between the true value and the estimated value of NAL is considerably smaller than that of other loss functions, we present a more detailed graph highlighting this difference for NAL in Appendix J. In addition, the estimated value of NAL is also in Appendix J.
Results on convergence rates with different neural net- work structures. Additionally, evaluate the perfor- mance of different algorithms under various network ar- chitectures. Specifically, we replace Softmax with Sparse- max (Martins & Astudillo, 2016). The experimental results are shown in Appendix J. We observe that our algorithm still exhibits the fastest convergence rate. fact, the con- vergence rate of our algorithm remains largely unchanged. In contrast, the convergence rates of the other algorithms experience significant degradation.
Results on convergence rates, variances, and differences with different optimizers. We further assess the robustness of our loss function with different optimizers by evaluating performance using other famous optimizers, such as RM- Sprop (Bottou, 2010) and SGD (Robbins & Monro, 1951), with the parameter fine tuned in the scenario where Adam is used. Key metrics, such as convergence rate, the variance of estimating the value loss function, and the difference between the estimated value and true value of loss functions, analyzed. The results on convergence rates, variances, and differences when using RMSprop SGD as the opti-
Results on convergence rates of NAL with or without the term (F .b:)) 1. Moreover, we investigate the impact of the term (F , in NAL. Our results show that this term not only reduces the variance but also ensures that the algorithm minimizing NAL converges to an NE. In the absence of this term, the algorithm may fail to learn NE, Further details are provided in Appendix J.
8

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Forn Games
10a
Gootspial
10
10
Uarks Dice
10r
101
10a
104
10a
difference
109
104
100
10
10a
0
-10
10:
-10
-10-
-10
-10-
10P
10a
10t
102
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
10
Bartrand Oligopely
10
Ave
10
10'
Majority Vating
109
109
100
109
difference
10
-10-1
10-1_-
-10-
-10-1
-10P
-10*-
-10P
-10
2500
5000 Berations
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
0
2500 5000
7500
10000
Iterations
Iteratins
Iterations
Gemp 2024
ADI
NashAgr
Figure 3. Difference between the true value and the estimated value of loss functions when the optimizer is Adam. Since the difference between the true value and the estimated value of our loss function NAL is considerably smaller than that other loss functions, we present more detailed graph highlighting this difference for NAL in Appendix J.
Results on convergence rates of NAL with different val- ues ef To strengthen the robustness of our results, also include experiments with various c values (0, 0.1, 0.5, and 0.9), as shown in Appendix J. Across all tested e values, our algorithm consistently outperforms the baselines, further validating that the variance reduction achieved by our loss function leads to an accelerated convergence rate.
Acknowledgements
This work is supported in part by the National Natural Science Foundation of China under Grant 62192783, the Jiangsu Science and Technology Major Project BG2024031, the Fundamental Research Funds for the Central Univer- sities (14380128), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the InnoHK funding.
Results convergence rates when the strategy is repre- sented using real vector. As mentioned in Appendix B, we employ a DNN due to its capability to approximate arbitrary non-linear functions, enabling the discovery of complex equilibrium strategies that simpler representations may overlook. In contrast, a real vector lacks this expres- sive power. The results, where the strategy is represented using real vector, are shown in Appendix J. All algorithms exhibit varying degrees of performance degradation, yet our algorithm still outperforms the others.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
6. Conclusions
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S.,
We introduce a novel surrogate loss function for using non- convex stochastic optimization techniques of ML com- pute NE, named NAL. It can be estimated without bias and will incur an significantly lower variance than the exist- ing unbiased loss function. Experimental results show that the algorithm minimizing NAL significantly outperforms other tested algorithms. Our approach offers a promising new direction for computing an NE, with the potential to address the challenges posed by large-scale games. One direction of our future works is to extend approach to solve imperfect information extensive-foo form games.
Anadkat, S., al. GPT-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Bojarski, M., Del Testa, D., Dworakowski, D., Firner, B., Flepp, B., Goyal, P., Jackel, L. D., Monfort, M., Muller, U., Zhang, J., et al. End to end learning for self-driving 2016.
cars. arXiv preprint vrrivv1664..75
Bottou, L. Large-scale machine learning with stochastic gradient descent. In Proceedings of the 19th International Conference on Computational Statistics, pp. 177-186. Springer, 2010.
Brown, N., Lerer, A., Gross, S., and Sandholm, Deep
9

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
counterfactual regret minimization. In Proceedings of the 36th International Conference on Machine Learning, pp. 793-802, 2019.
Gemp, I., Savani, R., Lanctor, M., Bachrach, Y., Anthony, T., Everett, R., Tacchetti, A., Eccles, 'T,, and Kramár, J. Sample-based approximation of Nash in large many- player games via gradient descent. In Proceedings of the 2 International Conference on Autonomous Agents and Multiagent Systems, pp. 507-515, 2022.
Brown. T. B. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Cai, Y., Oikonomou, A., and Zheng, W. Finite-time last- iterate convergence for learning in multi-player games. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems, volume 35, pp. 33904- 33919, 2022.
Gemp, I., Marris, L.,, and Piliouras, G. Approximating Nash equilibria in normal-fone formm games via stochastic optimiza- tion. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Goktas, D., Parkes, D. C.,, Gemp, I., Marris, L., Piliouras, G., Elie, R., Lever, G., and Tacchetti, A. Generative ad- versarial equilibrium solvers. In Proceedings of the 12th International Conference on Learning Representations, 2022.
Chen, X. and He, K. Exploring simple siamese represen- tation learning. In Proceedings of the IEEE/CVF con- ference computer vision and pattern recognition, pp- 15750-15758, 2021.
Chen, X., Hong, M., Liu, S., and Sun, R. On the conver- gence of a class of Adam-type algorithms for non-convex optimization. In Proceedings of 7th International Confer- ence on Learning Representations, 2019.
Goodfellow, I. Deep learning, 2016.
Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A. C., and Bengio, Y. Generative adversarial nets. In Proceedings of the 24th Annual Conference on Neural Information Processing Systems, pp. 2672-2627222 2014.
Chen, Y. and Ye, X. Projection onto a simplex. arXiv preprint ar Xrvi: 101.6081, 2011.
Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. The complexity of computing Nash equilibrium. Com- munications of the ACM, 52(2):89 19.9999772229 2009.
Grill, J.-B., Strub, F., Altché, F., Tallec, C., Richemond, P. H., Buchatskaya, E.,, Doersch, C., Pires, B. A., Guo, Z. D., Azar, M. G., et al. Bootstrap your own latent a new approach to self-supervised learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pp. 21271-21184, 2020.
Dempster, P., Laird, N. M., and Rubin, D. B. Maxi- mum likelihood from incomplete data via the em algo- rithm. Journal of the Royal Statistical Society: Series B (methodological), 39(1):1-22, 1977.
Heaton, J. B., Polson, N. G., and Witte, J. H. Deep learning for finance: Deep portfolios. Applied Stochastic Models in Business and Industry, 33(1):3-12, 2017.
Deng. L., Yu, D., al. Deep Learning: methods and appli- cations. Foundations and Trends@ in Signal Processing, 7(3-4):197-387, 2014.
Heinrich, J. and Silver, D. Deep reinforcement learning from self-play in imperfect-informateee games. arXiv preprint arXiv:1603.011
Devlin, J. Bert: Pre-training of deep bidirectional trans- formers for language understanding. arXiv preprint arXiv:1810.04805, 2018
2016.
Hornik, K. Approximation capabilities of multilayer feed- forward networks. Neural networks, 4(2):251-257, 1991.
Dosovitskiy, A. An image is worth 16x16 words: Trans- formers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988 2014.
Duan, Z., Huang, W., Zhang, D., Du, Y., Wang, J., Yang, Y., and Deng, X. Is Nash equilibrium approximator learn- able? In Proceedings of the 22nd International Confer- ence on Autonomous Agents and Multiagent Systems, pp. 233- 241, 2023.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. In Proceedings of the 25th International Conference on Neu- ral Information Processing Systems, volume 25, 2012.
Facchinei, F. Finite- dimeessdimniii variational inequalities and complementarity problems. 2003.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls. K., Pérolat, J., Silver, D., and Graepel, T. A uni- fied game-theoretic approach to multiagent reinforcement learning. In Proceedings of the 3 Annual Conference on Neural Information Processing Systems, pp. 4193- 4206, 2017.
Flennerhag, S., Rusu, A. A., Pascanu, R., Visin, F,, Yin, H., and Hadsell, R. Meta-learning with warped gradient de- scent. In Proceedings of the 8th International Conference on Learning Representations, 2020.
10

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., et al. Openspiel: A framework for reinforcement learning in games, 2019.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z.., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. In Proceedings of the 32nd Inter- national Conference on Neural Information Processing Systems, volume 32, 2019.
Langley, P. Crafting papers on machine learning. In Proceed- ings of the 17th International Conference on Machine Learning, pp. 1207-1216, 2000.
Raghunathan, A., Cherian, A., and Jha, D. Game theoretic optimization via gradient-based nikaido-isoda function. In Proceedings of the 36th International Conference on Machine Learning, pp. 5291-5300. PMLR, 2019.
LeCun, Y. Bengio, Y., and Hinton, Deep learning. Na- fure, 521(75533 2015.
Liu, S., Marris, L., Piliouras, G., Gemp, L., and Heess, N. Nfgtransformer: Equivariant representation learning for normal-fone games. In Proceedings of the 12th Interna- tional Conference on Learning Representations, 2024.
Robbins, H. and Monro. S. A stochastic approximation method. The annals of mathematical statistics, pp. 400- 407, 1951.
Shoham, Y. and Leyton-Browy K. Multiagent systems: Al- gorithmic, game-theoretic, and logical foundations. Cam- bridge University Press, 2008.
Marris, L., Gemp, I., Anthony, T., Tacchetti, A., Liu, S., and Tuyls, Turbocharging solution concepts: Solving nes, ces and cces with neural equilibrium solvers. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems, 2022.
Sokota, S., D'Orazio, R., Kolter, Z., Loizou, N., Lanctot, M., Mitliagka,, Brown, N., and Kroer, C. A uni- fied approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In Proceed- ings of the 12th International Conference on Learning Representations, 2023.
Martins, A. and Astudillo, R. From softmax to sparsemax: A sparse model of attention and multi-label classification. In Proceedings of the 33rd International conference on machine learning. pp- 1614-1623. PMLR, 2016.
Wu, Y., Sun, Z.,, Yuan, H., Ji, K., Yang, Y., and Gu, Q. Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675. 2024.
Mescheder, L., Geiger, A., and Nowozin, Which training methods for gans do actually converge? In Proceedings of the 35th International conference machine learning, pp. 14900. PMLR, 2018
Ye, C., Xiong. W., Zhang, Y.. Jiang, N., and Zhang, Online iterative reinforcement learning from human feed- back with general preference model. arXiv preprint arXiv:2402.07314 2024.
Milionis, J., Papadimitriou, C., Piliouras, G., and Spendlove, K. An impossibility theorem in game dynamics. Pro- ceedings of the National Academy of Sciences, 120(41): e2305349120, 2023.
Yongacoglu, B., Arslan, G., Pavel, L., and Yuksel, S. Paths equilibrium in games. In Proceedings of the 38th Annual Conference Neural Information Processing Systems, 2024.
Mitchell, T. M. and Mitchell, T. M. Machine learning, volume 1. McGraw-hill New York, 1997.
Zou, F., Shen, L., Jie, Z., Zhang, W., and Liu, W. A sufficient condition for convergences of Adam and Rmsprop. In Proceedings of the IEEE/CVF Conference computer vision and pattern recognition, pp. 11127-11135, 2019.
Munos, R., Valko, M., Calandriello, D., Azar, M. G., Row- land, M., Guo, Z. D., Tang, Y., Geist, M., Mesnard, T., Michi, A., et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00888 2023.
Nikaidō, H. and Isoda, K. Note on non-cooperative convex games. 1955.
Nudelman, E., Wortman, J., Shoham, Y., and Leyton-Brown, K. Run the gamut: A comprehensive approach evalu- ating game-theoretic algorithms. In Proceedings of the 3rd International Conference on Autonomous Agents and Multiagent Systems, volume 4, pp. 880-887, 2004.
Osborn,, M. J. et al. An introduction to game theory, vol- ume 3. Oxford university press New York, 2004.

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fove Formml-Form Games
A. Table of Notations and Definitions
Table Table of Notations and Definitions
Notation/Definitton
Section
Description
N
3
the set of players the index of the player all players except player the action set of player an action of player i, e.g., E A,
i
3
-1
3
A;
3
3
3
the actions selected by the players except player the utility received by player player select a,. while other players select a_
ui(a;, aa:)
3
x;
3
the strategy of player
X;
3
the of the strategies of player a (lAi) 1)-dimensional simplex
3
{ær X; Ni; the strategy profile
X
3
XieN' the strategy space of all players
x
3
the interior of X, e.g. : for each æ X2, (a.) > 0, E N and a; E A;
EaexieNA: (a) ILE (gz)) where aj A, denotes player j's component of the joint action a; the utility received by player i,
u2 xi)
3
given that all players follow the strategy profile E X
Va, (x:)
3
the first-order gradient ";(x:) w.r.t. æ;
x
3
the set of NEs in the game with the utility function u(xx)
the set of interior NEs in the game with the utility function (x) such that Var" 200 ax (a:) >> O, Vi E N, as E A,
3
EiEN max (Va, U4 (x) x². x;)): the duality gap in the game with the utility function (x; well-known metric measure the distance
dg(æ))
3
from the strategy profile to NE;
if and only if dg(x) 0, x E X" if dg = 8, then is 5-NE
Emxx u. (at x-) (2, .c.))
exp(#:
3
the exploitability in the game with the utility function u((x), well-known metric measure the distance from the strategy profile to NE
u, (a:) the utility function of the regularization game defined in Gemp et al. (2024)
T log a;;
(x)
3
Continued next page
12

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Notation/Deffmition
Section
Description
3
my uzf (2:), which also be represented by -V
Vn, (2((r) log s;
Da,ea; (?:)(a))
F
3
EiEN the loss function proposed by Gemp al. (2024)
P
12:
(2))
3
the stop-gradiens operator such that
sgl:]
for any variable R sg [b] while bosg(b] = 0 E Rdxd
Eie F (F. 2, æ.),
(x)
where a = [&o $1, ... w1 can be any strategy profile in X;
NAL, unbiased loss function proposed by us
sg F (F.".. "F.."".t .2,)1}; the first-order gradient of L (x) w.r.t. Z;
V2, (x)
4
[sg[F]T* (FT 1,, E EM:
V Vo vaL(vA(())
4
the first-order gradient of (z) w.r.t
Eier m (Va, u. (x) x/ 2z); the duality gap in the game with the utility function uf (a)
(g"
4
(mxx(max u/ (ar a w)- (0); am).))))))) :))
exp" (x:)
W
the exploitability in the game with the utility function uf (a:)
this notation represents that two random variables are independent, e.g., for random variables b and c, L implies that b and are independent
4
Var[-]
4
the variance
9, -0 (a:)
the estimation of FT (F... ax) at action aj A; in NAL 4
the j-th estimation of FTT _ F. action a; E A; in the loss function proposed by Gemp al. (2024), where {1,2)
g. an (a:)
4
in Section 4.2, we assume that Varlg," (a,)) = 0 and Var (g, ... (a.) = a, vi E E j E (1,2). and a; E A,
o
the strategy profile represented by an approximation
0
4
function II(-) parameterized by 0
L (F... ... the NAL related to the parameter 0
(.)
(0)
OPT
4
the optimizer in Algorithm
e
4
the exploration ratio in Algorithm
x
4
the uniform strategy of player
4
M]: the uniform strategy profile
1)
4
the learning rate in Algorithm ] the number of total iterations in Algorithm
T
4
Continued on next page
13

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Notation/Deffnition
Section
Description
S
4
the number of instances sampled per iteration in Algorithm
Tu
4
the frequency of updating 7) and in Algorithm the weight on updating in Algorithm 1, e.g. 1/ CUT) the weight on updating in Algorithm 1, egg., T BT
4
8
4
the simulator in Algorithm that returns player i's payoff given joint action
g
4
M2
the buffer in Algorithm
1
4
the current iteration in Algorithm
a
4
[a: e M]; the joint action in Algorithm
sampled from (1 c)xf + car used in Algorithm for estimating F. (F
d;
4
(1 (1-c) =) (a() + (a));
4
used in Algorithm for estimating FT
(F
x.,11
- d/. a-:) + T log x (d();
4
used in Algorithm for estimating F.
(Fr
x
U/3
4
used in Algorithm for estimating Fr.
(F
xx,11
AL)
4
the estimation of AL in Algorithm
rf.
the s-th tuple stored buffer M, in Algorithm
enf where Eag is a vector whose the coordinate af is and all other coordinates are 0; used in Algorithm for estimating F. F (E. a
g
4
minze.Nx(ar) V_u(x) + =112,
where (x {u E R
x (v, x'' x)) S 0, Va X
is the normal cone of a.
and V (
V mu [z();; Vz,, 21 (x)); :.::..... ; V W (x)];
tan (x)
E
the tangent residual in the game with the utility function (z),
a new metric to measure the distance from the strategy profile x to NE;
if and only if tan (x) = 0, x X':
used for proving Theorem 4.2
minzeNx((s) || V..u" "0"""" (æ) + 2 2|22
pl (x:
the tangent residual the game with the utility function uj (x);; used for proving Theorem 4.2
two independent variables.
y()) ((2)
used for deriving the variance of the product of two independent variables
Y
the expectations of (1) and (2)
i
0
25-1
G
the (2s 1)-th tuple stored in buffer M, in Algorithm
24-1
24
.Pi
Continued on next page
14

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Notation/Definition
Section
Description
(1, ,r? r? , p??1
G
the 2s-th tuple stored in buffer M; in Algorithm
(0)
G
EVEN || | + t log xr
sgl Fr""
Flog x
the implementation of the loss of Gemp et al. (2024) used in our paper
EIEN Eesl (sgl F. 1125-11 1l + T log x
sg
Fw 1,2s
Flog
x
sg
Fxoe + log x sgl
Fue 1
Flog x
1,20
(0)
G
where F 1,20-1 log c m 1.2s
= r
log a
c well as
2 (eag1) is vector in which the coordinate dg
2s
(a
24 is
and all other coordinates are O; the estimation of 2 (0)
EEEN m (sgl FF + log xx. a' x. the implementation of the loss of Gemp et (2022) used our paper
(0)
G
EiEN max Ni (sgl ( where F.. -o- well Caf is vector in which the coordinate ag is and all other coordinates are 0: the estimation of LADI
log x x x Pf Cot F Σ==1 ==1 F
(0)
maxieN maxai (sgl F. 1, x;);;
NaahhApr
G
the implementation of the loss of Duan et al. (2023) used in our paper
m max x, (sgl F.
x
x
where F 1. - log Coj. F0
-
F
1.6
G
well eaf is vector in which the coordinate of is and all other coordinates are O: the estimation of LNachApr (0)
Eien [|sg[E? -sg[-sge Fg TT, where Tæ; = E.EA, mi
Tσ. 12.
(x:) H
LAI 1;
variant of the loss of Gemp et al. (2024) that is used for deriving the relationship between NAL. and the loss of Gemp et al. (2024)
(2 FTT.0
(F... .x!") ..)) (ræ;, rx.)) (roz, rx;));
(T)))
H
used for deriving the relationship
between NAL and the loss of Gemp et al. (2024)
B. Discussion on Learning Nash equilibria via the Combination of Deep Neural Networks with Non-Convex (Stochastic) Optimization Techniques
Deep neural networks (DNNs) have been widely applied to solve complex optimization and decision- decision-making problems across diverse domains, owing to their expressive power. This enables them to capture intricate patterns and relationships that are challenging model using traditional methods. DNNs can approximate arbitrary non-linear functions (Hornik, 1991), making them particularly suitable for representing strategic decision-makin making processes in game theory. Furthermore, the ability of DNNs to learn directly from raw data data-without requiring handcrafted batures-alloww them to uncover complex equilibrium strategies that might otherwise be overlooked (Brown et al., 2019; Goktas et al., 2022; Marris et al., 2022: Liu et al., 2024).
variety of methods combining DNNs with non-conver (stochastic) optimization techniques has been developed to compute an NE, where strategy profiles are represented by DNNs and the equilibrium directly learned by minimizing loss
15

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
function through non-convex (stochastic) optimization techniques (Goktas et al., 2022: Marris et al., 2022: Liu al., 2024). To the best of our knowledge, the first work computing NE via the combination of DNNs with non-convex (stochastic) optimization techniques was proposed by Duan et al. (2023), demonstrating the feasibility of combining DNNs with non-convex optimization techniques for computing an NE. Following this, Marris et al. (2022), Goktas et al. (2022), and Liu et al. (2024) conducted extensive research on network architectures tailored for computing an NE through this combination. However, these architectures are not suitable for solving real-world games, as they assume that the payoff' matrix can be fully loaded into memory as input to the network. In contrast, real-world games often feature payoff matrices too large to fit into memory, necessitating solutions based on sampling subset of the matrix, referred as sampled play, which can be seen as the stochastic optimization setting in MI.
In the context of stochastic optimization, designing appropriate loss functions specifically tailored for equilibrium computa- tion remains a significant challenge. Many existing loss functions rely on sampling to estimate gradients or payoff', which can introduce considerable biases (Duan et al., 2023; Gemp et al., 2022) or lead to high variance (Gemp et al., 2024), thereby making training unstable. This limitation highlights the need for further research in developing unbiased, low-variance loss functions that better align with the requirements of equilibrium computation. Nonetheless, the intersection of DNNs, non-convex (stochastic) optimization techniques, and game theory presents promising avenue for addressing complex. world problems, ranging from economic markets to strategic decision- making in games.
C. Relationship between Our Algorithm and Simultaneous Gradient Descent Algorithms
Our algorithm is similar to existing simultaneous gradient descent algorithms, specifically to its improved version, magnetic mirror descent (Sokota et al., 2023), if we set a; = 0. However, as mentioned in Section 4, the property of NAL does not hold when क; = 0 (we also highlight around Eq. (2) that &; + 0 in NAL).
Firstly, we cannot relate the zero-point of the first-order gradient of existing simultaneous gradient descent algorithms (NAL with o; = 0) to NE (Theorem 4.2 and 4.3). Specifically, when é; 0 and applying commonly used non-convex stochastic optimization techniques in ML, we cannot guarantee that the algorithm will stop updating upon reaching NE, This is because, even if æ is an NE of the regularization game, existing simultaneous gradient descent algorithms only ensure that its first-order gradient sg( Fg (F 2 0)1] = sg(F, is the same across all actions (as shown in the analysis in Section 4), but does not guarantee that this gradient is O. Unfortunately, the algorithm that employs commonly used non-convex stochastic optimization techniques in ML, will only stop updating when the first-order gradient of the loss function is O. In other words, even if an NE is learned by existing simultaneous gradient descent algorithms, the updates may not stop, and existing simultaneous gradient descent algorithms will eventually deviate from this NE. In contrast, NAL ensures that its first-order gradient sg|F,* (FT 1 = 0 if and only if x: is an NE of the regularization game (as shown in the analysis in Section 4), which enables the algorithm employing commonly used non-convex stochastic optimization techniques in ML to stop updating once an NE is learned.
Secondly, no connection can be established between existing simultaneous gradient descent algorithms and the loss function proposed by Gemp al. (2024). However, as shown in Theorem H.1, the first-order gradient of NAL approximates variant of the first-order gradient of the loss function introduced by Gemp al. (2024). This suggests that, if we can establish theoretical convergence for the loss function proposed by Gemp et al. (2024) when using commonly applied non-convex stochastic optimization techniques to minimize this loss function, we may also be able to establish similar convergence results for NAL under these techniques. However, this does not hold for existing simultaneous gradient descent algorithms.
Regarding the theoretical convergence of existing simultancous gradient descent algorithms, these algorithms are primarily used in training GANs (Goodfellow et al., 2014; Mescheder et al., 2018), which typically involve two-player zero-sum games, as opposed to multi-player general-sum games that we consider. Notably, while research (Milionis et al., 2023) suggests that there may be games where dynamics do not converge to NE, their theory does not account for randomness. As the authors state: "our impossibility results do not apply to stochastic dynamics e.g., discrete-time dynamics in which (p()) is distribution of possible next points" (where (((x) is the notation in Milionis et al. (2023)). Yongacoglu et al. (2024) demonstrate that the presence of randomness can enable convergence to an NE, noting that "we note that our possibility result does not contradict the impossibility results of [22, 2] or [38]. In particular, the functions { need not be (and usually will not be) continuous, violating the regularity conditions of [22] and [38]" (where {ff is the notation in Yongacoglu et al. (2024), and [38] refers to (Milionis et al., 2023)). Our algorithm incorporates randomness. Studying the theoretical convergence of our algorithm will be the future work.
16

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Thirdly, the experimental results in Figure 20 and Figure 21 further highlight the distinct nature of NAL and existing simultaneous gradient descent algorithms, their performance diverges significantly. Specifically, minor modification the neural network nachitecture-namell,, replacing the activation function in the final layer-causes existing simultaneous gradient descent algorithms to fail to converge, whereas NAL's convergence rate remains unaffected by this structural change.
D. More Details of Stop-Gradient Operator
Let b IR be variable. The stop-gradient operator is defined as sg [b] = b IR with Vbsg(b] 0 R=*" This implies that sg[b] [b] passes the value of unchanged in the forward pass, but blocks its gradient during backpropagation. Intuitively, sg[-] can be regarded constant during differentiation. In summary,
Forward pass. sg[b] returns the value of b.
Backward pass. The gradient is blocked-no gradients are propagated through
In fact, this operator has already been widely adopted in previous works (Grill et al., 2020; Flennerhag et al., 2020; Chen & He, 2021). We are inspired by the use of this operator in previous works and adopt in our work accordingly.
E. Missing Proofs in Section
E.1. Proof of Lemma 4.1
Proof. Let (b1, b2....... ..... ......, ba) Rd and y (311 V2....,, Va) be vector in the standard simplex, i.e. y: 0 and Σk=1 Uk 1.
The inner product (b, y) is defined as
(b, y) =
byckk.
Am
We will now prove the lemma in parts: sufficiency and necessity.
Sufficiency:
Assume that all coordinates of b are equal, i.c., b1 = b2 =...= = by = C, where is some constant. In this case, we have
(b. y) =
buyk
cyk
yk = c.c 1
k=1 k=1
k=1
Thus,
(b. y) = (c, c, cc) cc= (0,0,...,0)
which implies that b (b. y) Hence, the sufficiency holds.
Necessity:
Now, assume that (b, y 0. We need to show that this implies that all coordinates of are equal. From the equation (b. y) = O, we have
b (b, 1,
where = (1, 1,......, 1) is the vector of all ones. This implics that
by (b, y) for all k = 1,2, In other words, all by are equal to (b, y), meaning b = by Since both sufficiency and necessity have been proven, the lemma is true.
by. Thus, the necessity holds.
17

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
E.2. Proof of Theorem 4.2
Proof. We prove Theorem 4.2 via the tangent residual (Cai et al., 2022). Therefore, before we start the proof, first introduce the tangent residual. Formally, for any game, whose utility function u(-) of each player is concave over X yx E X, its tangent residual is
ton (a) = min Vwu(x) + =212. =ENx(#)
where Nx(x) fo E R (0, a) S 0, Va' X3 is the normal cone of æ, and Va)(z) (V no (a:); V Va, (z)): Van-, -an-1"n-11 1 (x)]] If p (a)) O, then, by Lemma E. is an NE. Additionally, if is NE, then Vau(a) E (x(x),, since (Vau(z))
x) 0, Va' X when is NE. Therefore,
lan [()) vau(a))l2 = 0 if and only if a is an NE.
Lemma E.1 (Proof is in Appendix E.3). For any game, whose utility function of each player is concave over X; it holds that
dg(æ:) S v 2// (x)
From the definition of ,F)",,)),, Var x' X, we have
Σ (F 1, Φ - xi) Σ iEN
(F (2i) (F? ...) 0,
iE.N
where the first equality comes from (1,z)) (1. x.i) = since of and are in the simplex. Therefore,
[-(F,"" ( ( ; 1; ::;; FT 1 is in the normal cone of æ Then, from the definition of the tangent residual.
tan.7 (x)))(())) =
min || V (xx + 2112
=x\x(a>)
with (a)) the normal cone of a and
Ve, (x) F.
we have that
Lam,7 (x) S V (2))12-
In addition, from Lemma 1. we obtain that
dg'(x) I 22 N0. (()) S V2/Ni aa
It completes the proof.
E.3. Proof of Lemma E.1
Proof. Let æ arg max Vvx, ui (x(x), x/ xx)) for the definition of the duality gap and normal cone, vz e (x) we have
dg(x) Σ V -
iEN
< Σ
V (x), xa) + (2. x¹)
(6)
iEN
(- V=u(x) # x¹)
- || - V<u(z) + =1|2||æ x 112
where the second lines comes from the fact that, Vz E (x (z) and a:" Xx x ==>) 2 0 holds. As Eq. (6) holds for
all E (x),,, we can get
dg(x) < || x'112
min || V ( + +1|12
=x)x(()
which implies
dg(x)) S 2m
where the right-hand side comes from max,", xx 1|=0" x²1 5 v EiEN maxay, arex, || - x²
V VieN2= W2.. completes the proof.
18

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore -erall-Form Games
E.4. Proof of Theorem 4.3
Proof. Beginning with the definition of the duality gap, we find
dg(#)
Σ max (Va, (n,);(r)), ai)
VEN EX
iN mi EX, Va,u;(1)) log( + 7 log( a/ xi;)
max
max Vv (x) log( x² xz) + Σ
max (T log(2;)); x -(,-),) xx,
IEN ExE,
iEN
dg" (z) +
max (T loog(a;))))))))))))(())) xt)) + Σ (T log(az)) -2:))
iNN EfER:
IEN
2| An
(T Folo((z;)) (zi), -x;)
VEN
V +
log( (::)).
BEN
where the second inequality follows from the definition of the duality gap and NE, and the third inequality comes from (o;) < 0, v0 S x; < 1. It completes the proof.
F. Variance of Estimating via Two Independent and Identically Distributed Random Variables
Let two independent samples from two corresponding identically distributed random variables be y and (() Due the definition of (()) and ((2), we have ( E Y. Assume Var[Y<W) = and VarlY a. Now, we aim to analyze the variance Var( From the definition of (arl we have
(2) IB[ ())((())))(((( (EE (L( (
For the term E3,, from the definition of VarlY (1) we get
Varly - (E(Y(11)² E((y(W)}] -2 =a (1)() = o
Similarly, we have (2) = 2 Combining the above equities, we have
(arlY (o + (x = =0 208
G. Implementation Details of Compared Loss Functions
The loss function proposed by Gemp et al. (2024). As shown in Algorithm 1, we do not employ the sampling method used in Gemp et al. (2022) and Gemp et al. (2024) due to the high per-sample sampling complexity of their sampling method. Formally, the per-sample sampling complexity of their estimating method is ((IA7]AA,1)) while that of our estimating method as shown in Algorithm is ((WV). In Appendix J, we provide a comparison of the sampling time between our sampling method and the sampling method used in Gemp et al. (2022) and Gemp et al. (2024), under the same number of sampled instances In our sampling method, the estimated variable of F?" (i.e., Vn, (x(x)) cannot participate in gradient backpropagation, and only the variable x!! participates in gradient backpropagation. In other words, we minimize the following loss function
(0)
Σ || iEN
F 6 + 7 log x.
sg F + rlog x 1-
The only distinction between (0)
(0) and (0) in Eq. (1) (or (x(x)) is the omission of the gradient backpropagation path for agl FFe" and sgl [.*"). For the definition of the stop- gradient operator in Appendix D, the stop-gradient operator
19

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
only affects the gradient computation. Specifically, the stop-gradient operator treats term constant, preventing it from participating in the gradient backpropagation, but does not alter the value of the term. Based on the analysis in Section 3, for
all x² E X, x is an NE of the regularization game with utility function u (x²) = u; uz(x)) ) - - log a and only C (ax = Since the stop-gradient operator does not alter the value, it follows that for all æ E X, x is an NE of the
regularization game with the utility function in (a=²) uu(xx)) Tæ. log æ² if and only if (z 0.
As done in Gemp et al. (2024), we use the following loss function to estimate the value of (0) via the (2s 1)-th and (2s)-th tuples ((i, a0f=_1, ,r/=-1 Pt =1²==1] and [i, at² r2a , stored in M,:
(0) = Σ
(ag( F 1,25-11 + log oi sg 11 - Tlog x. .g ( + 7 log o. sg F. - -log x.);
iEN
log P:
log pi 6a2
F1,2-11
2
2,24
Pi
p
where eq" (eap+) is vector in which the coordinate d
2x-1 (a. is 1 and all other coordinates are 0. From the analysis in Gemp al. (2024), E 1,2- F EEFE Fi and [E(2 (0).
E[
ADI (Gemp al., 2022). Since the variable F. cannot participate in gradient backpropagation via our sampling method, we defined this loss function
C ( = Σ [sg
F log x. x' =x?).
X.
iEN
We use the following loss function to estimate the value of (0) via the tuples [ ri (s E [1, 2, ... ST) stored in Mj;
F
r² - T log
Cat
1,
p
8=1
(0) = Σ max (sg x
pr + log x. x' xx)
x²))
EEN
NashApr (Duan et al., 2023). Since the variable F. cannot participate in gradient backpropagation via our sampling method, we defined this loss function as
NaahhApr ( = max max ( 1. a.²)
cEN' xiX;
We use the following loss function to estimate the value of LNashApr via the tuples ai p/.pil (s E [L, 2, ... $) stored in M₁:
F
r.
T
log
Frce
Aash (0) max max 1,
1. x
1.8
easy
VENV 2
H. Minimizing NAL Approximates the Process of Minimizing the Loss Function in Gemp et al. (2024)
We now show that when using commonly used non-convex stochastic optimization techniques in ML, minimizing NAL approximates the process of minimizing the loss function in Gemp et al. (2024), while mitigating the high variance caused by the inner product of two estimated variables.
As mentioned in Appendix G, for the loss function in Gemp et al. (2024), it is difficult to backpropagate the gradient of the term Vn, (x) in FT when solving real-world games. Therefore, practice, we have to use the following loss function as surrogate function for the loss in Gemp et al. (2024):
(T(2)=
Σ IEN
[sg] F!")
8g F + T log Ø; - Glog x;
2
2
(7)
20

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore -eraal-Formm Games where F.= -Va, -Va,u, (x)) Then, consider the following variant of (ar):
())z)
Σ SEN
[|
sgl [ Tæ; T2;
Compared to (2)),, (2x). the key difference is that (x) replaces the gradient backpropagation paths involving log æ with those involving 2;.- The reason for this modification is that the gradient of log æ; is 1/x,, which may become very large some cases, leading to instability (as shown in Figure 18). This modification ensures that global minimum of (x)) an NE of regularization game with the utiliiy function dī (z). Formally, since Va, 2ī (a) F; ræz = Va, (x) 7 log 2; T2; is concave over x. from the analysis in Gemp et al. (2024), we have that F; + ræ; = F TW,, Vi E N if and only if is an NE of the regularization game with the utility function á. (z:). Then, consider the following loss function
(T(x)=
Σ icN
(2r(sg[FT
".T"","")1]. + (Ta,,TT))) (TIi, rI,))
Theorem H.1 (Proof is in Appendix H.1). The fusttorder gradients of (xx) and (x) are identical.
surprised to find that the first-order gradient of (x) is the same as the first-order gradient of LT (x)) It is evident that non-convex stochastic optimization techniques commonly used in ML require only first-order gradients as input, minimizing (x) is equivalent to minimizing CT (x). Moreover, (T(x) (z) does not involve the inner product of two estimated variables that leads to high variance compared to (z²).
As shown in Theorem H.I,
is evident that AL AL (x) approximates (a²), as the difference between them is merely the term (Tæ;, T (rā,, rza). Therefore, we have that when employing commonly used non-convex stochastic optimization methods in ML, minimizing NAL approximates the process of minimizing ()(xr)
(az) while reducing high variance. In our experiments (Figure 18), the algorithm minimizing CT(x)) significantly outperforms the algorithm minimizing (x) (in fact, we compare the algorithm minimizing (a) with the one minimizing L (ae)/TT, as the first-order gradients of (z and (2)))/2 are on the same scale as the first-order gradient of NAL. This ensures consistent comparison framework). This highlights the substantial impact of variance on convergence, as the performance of both algorithms would be consistent when using commonly used non-convex stochastic techniques without sampling. However, under the sampled play, the algorithm minimizing CT (x) surpasses the one minimizing CJ by significant margin. Furthermore, the algorithm minimizing NAL also achieves considerably better performance compared the one minimizing CJ (zz), further emphasizing the critical role of variance in convergence, given that NAL is merely an approximation of (xx). For detailed results, refer Appendix J.
We employ NAL instead of C3 (a:) in our paper because the computation of L7 (a)) involves (ræ;, ra.) (TT,, rT;) When the action size of the game is large, the entire x; is unknown, and only the value x;(a;) on the sampled action E Ai is available. For instance, in games used for preference alignment in large language models (Munos et al., 2023; Wu et al., 2024; Ye et al., 2024), where actions consist of all possible natural language sentences, is evident that æ; cannot fully known. Note that for the computation of [s (FF . xxi) 1]. 2x)), due to the importance sampling, sg(F," -(F x;]]]] zero except for the sampled actions, thus the entire æ; is not required. Our experimental results, as depicted in Figure 18, demonstrate that the algorithm minimizing NAL exhibits nearly identical performance to the one minimizing (z)) We
hypothesize that this is primarily because the gradient V., ((TR;, TT;) (TTI, Txx)) 27 27 (see derivation in Eq. (11), (12), and (13)) is relatively small compared to the value of sg(F, - (F; 1., due to the entropy term in
sg [ TT (F ,,""",""" 1]. See details in Appendix
H.I. Proof of Theorem H.1
Proof. Now, we prove that the first-order gradients of the following two loss functions are identical:
(x)) = Σ
|| [T - sgl F...0 + TT;; -rxx
IEN
(8)
[T(x) = Σ
(2T (sg[F] (FT 11, + (TI,, TxO)) (TI,, Tx:))
VEN
21

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Expanding the first line in Eq. (8) (CT())) (æ)),
have
|sg[ FT Tæ; sgl Fi T
(sg(E) T sg F. T
sg F. "1 Tx,, sg(F. F.
T2E +
sg F
T
sg
F?
Lemma H.2. (Proof is in Appendix H.2) yb, c R,, we have
(b, (b,c) =b,
where b Σ--1bb b() and Σj-1eh1 c(5)
By substinuting Lemma H.2 into Eq. (9) with b c sg [?
73 have
(ag[F] + ra,, sg FTT") rat))
sg PT
+ T 89 F.
+ Tmm)
+ sg F. F...
T 8gl F + T.D.
= (ag[E) "I Tw,, sgl F. + r - sg F
+ T sg
+ T
+ sg F
TJt sg F + न.b.
= (sg[F) + ræ;, sgl F. + r
5g ( + T sg FT
+ T
-ssg[ sg F ") ((s "], Twt) (T rw:)
[ sg [F
2(sg] F.Taa. -3x) (T T..).
(10)
Combining Eq. (8), (9). and (10), we get
4 (x) [sg[FT"" [.sg(F" 2(gg ")rrs) (T:) FF
1. F...... F7
2(
EEN
Now, we present the first-order gradient of (x) with respect to (a,).. Formally, we have
(o(e)
Σ [sgl (.9g())))) +(sg(
(rmy, (x [. (.ggF
2(sg ( (7 "))))))))))))))))))))))))))))( (rāj,
JEN
-Va(tan
(2(sg] F.
F T2.) (1,),
-Vs,(,))(s5111 VV. (T. V (2.10.)((s))) F. I.ra.)) V (a
Eoles sg F (u)) Eoees, xs (af)
-2rs (a))
Ail
Arl
-Vilee))A EdtEA, (a)) Eo EA, (i(
Ai
Ail
=2rsg(F""<011) (a:)) (1aaa)220 2T EntEA, sg1 [F (a)))
EoteE, (ai)
27
A
(II)
where the last line comes from
Va.(e.) Acl7? Lo 2z((a)) Ea,eA, xc(af))
7² Σ Σ (=(a)eer(a")
-Vai(as)
A.l AAi
AA
a'EA,
72
V Var(e,)
Σ
20. (ax(a)aaaaaa))
(12)
A.
afEA,aa
72
Eates xi((!)
Σ
2x.(
Σ
2x,(a))
=27"
|..|
A.
22

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Table 2. The hyperparameters of the algorithm that learns NE via minimizing NAT..
T
To
8
Kuhn Poker
0.0001
0.1
200
0.9
0,9
Goofspiel
0.0001
0.1
200
0.9
0,5
Blotto
0.0001
0.1
500
0.9
0.5
Liar's Dice
0.0001
0.1
500
0.9
0.5
Bertrand Oligopoly
0.0001
0.1
200
0,9
0.5
Guess Two Thirds Ave
0.0001
0.1
1000
0.9
0.5
Minimum Effort
0.0001
0.1
200
0.9
0.5
Majority Voting
0.0001
0.1
200
0.9
0.5
Therefore, from Eq. (1I), we get
V (x) -2rsg F7101+ + 22-=x; FF F.7
-222
(13)
=2rsg F. a F. 27 27
For [](x) = (2 (F. 1). + (T TT:)) (T ra;)). obviously, we have
Vz. =2rsg FT (FT xx 1| + V ( (TZ,, Ta;) - rai))
(14)
=2r8gl PTT F
2T 27 272x0
where the last line comes from the derivation of the first-order gradients of (TZ,, rx;) and (rZz, Tzi) Eq. (11). By combining Eq. (13) and (14), we complete the proof.
H.2. Proof of Lemma H.2
Proof. From the definition of (b, c). (b, c) and (b, c), we have
(b, E b(i),
d 1, E2=10 c(i)
1) d Σ
bi)
Σ
-
c('
b(j)
5'=1
y=1
Σ Σ b(j)
1
(b,c)
7
b(j)
Σ
cl'),
d
3'1
(b, = (b.
E
1) d
1
Σ
b(J) Σ
clj')
='1
Therefore, we have (.. (b, c) = (b.c). which finishes the proof.
I. The Hyperparameters Used in Experiments
The selected hyperparameters for algorithms that minimize NAL, the loss function in Gemp al. (2024), ADI, and NashApr, shown in Table 2, Table 3, Table 4, and Table 5, respectively (unless otherwise stated).
J. A dditional Experimental Results
Results on differences between true and estimated values for NAL. Firstly, as previously mentioned, the difference between true and estimated values for NAL is significantly smaller than other loss functions. To illustrate this difference more clearly, we present detailed graph specifically for NAL, shown in Figure
23

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Table The hyperparameters of the algorithm that learns NE via minimizing the loss function proposed by Gemp al. (2024).
7
Tu
a
Kuhn Poker
0.00001
1
500
0.9
0.5
Goofspiel
0,00001
0.1
200
0.9
0,5
Blotto
0.00001
0.1
500
0.9
0.5
Liar's Dice
0.00001
0.1
500
0.9
0.5
Bertrand Oligopoly
0.00001
0.1
200
0.9
0.5
Guess Two Thirds Ave
0.00001
0.1
500
0.9
0.9
Minimum Effort
0.00001
0.1
200
0.9
0.9
Majority Voting
0.00001
0.1
1000
0.9
0.5
Table 4. The hyperparameters of the algorithm that learns
NE via minimizing ADL
T
Tu
/
Kuhn Poker
0.00001
1
500
0.9
0.5
Goofspiel
0.0001
0.1
200
0.9
0,5
Blotto
0.00001
0.1
500
0.9
0.5
Liar's Dice
0.0001
0.1
500
0.9
0.5
Bertrand Oligopoly
0.00001
0.1
200
0.9
0.5
Guess Two Thirds Ave
0.0001
0.1
1000
0.9
0.5
Minimum Effort
0.00001
0.1
200
0.9
0.5
Majority Voting
0.00001
0.1
200
0.9
0.5
Table 5. The hyperparameters of the algorithm that learns NE via minimizing NashApr.
Kuhn Poker
0.0001
Goofspiel
0.00001
Blotto
0.0001
Liar's Dice
0.0001
Bertrand Oligopoly
0.00001
Guess Two Thirds Ave
0.0001
Minimum Effort
0.0001
Majority Voting
0.0001
Results on the value of NAL. We also present the value curves of NAL during the training process. Adam employed as the optimizer. The parameter remains constant throughout the training because, as observed, continuously shrinking r (as suggested Algorithm 1) renders it excessively small, diminishing its impact. The experimental results are shown in Figure Note that the absence of biased estimates in Goofspiel is an artifact of the logarithmic scaling of the y-axis, leading visual distortion. In most cases, we observe that the values of NAL converge to zero, which aligns with NE of the regularization game. However, it is important to emphasize that since NE in NAL is only the point of the first-order gradient, the values of NAL may either exceed or fall below zero.
Results on convergence rates with different optimizers. The convergence results for RMSprop and SGD are shown in Figures and 7, respectively. RMSprop shows minimal variation empirical convergence compared to Adam, likely due to their similarities. In contrast, other algorithms except ours, experience significant performance degradation with SGD, This is likely due the considerable difference between SGD and momentum-bars based optimizers like Adam and RMSprop.
24

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Results on convergence rates of algorithm minimizing NashApr when the optimizer is SGD with larger learning rates in terms of epochs. We observe that the convergence performance of NashApr is poor when the optimizer is SGD. Therefore, we also present the results when the loss function is NashApr, the optimizer is SGD, and the learning rate is increased by a factor of 10 and 100, respectively, compared to the learning rate of NashApr shown in Appendix I. The experimental results are illustrated in Figure 8 and Figure 9, corresponding to learning rates 10 and 100 times higher, respectively, while keeping the learning rates for algorithms using other loss functions unchanged. We observe that algorithms using NashApr as the loss function still perform poorly.
Results on variances and differences between true and estimated values with different optimizers. Now, we present the results of the variance in estimating the value of loss functions and the difference between the true and estimated values when RMSprop and SGD are used as optimizers. The variances in estimating the value of loss functions under RMSprop and SGD are shown in Figures 10 and 11, respectively. Similar to the case when Adam is used as the optimizer, our algorithm demonstrates the lowest variance. Additionally, the differences between the true and estimated loss values under RMSprop and SGD are presented in Figures 12 and 13, respectively. Again, consistent with the results using Adam, our algorithm exhibits the smallest difference.
Results on convergence rates with different numbers of sampled instances. Then, we investigate the empirical convergence rates of our algorithm and the algorithm minimizing the loss function proposed by Gemp et al. (2024) with varying numbers of sampled instances S per iteration, using Adam as the optimizer. We focus on these two algorithms since they both minimize unbiased loss functions. The results are presented in Figure 14. We observe that as S innreeses, our algorithm converges to a more and more accurate NE. In contrast, the algorithm minimizing the loss function proposed by Gemp et al. (2024) learns a more and more accurate NE in Liar's Dice, but fails to learn a more accurate NE in Kuhn Poker. These results demonstrate that finding an NE is easier by using our algorithm due to the lower variance.
Results on sampling times with different sampling methods. We also provide a comparison of the sampling time between our sampling method in Algorithm I with the sampling method used in Gemp et al. (2022) and Gemp et al. (2024), under the same number of sampled instances S. We conduct our tests on Liar's Dice because it has the largest number of actions for each player among the eight games evaluated in the experiments. The results are shown in Figure 15. We observe that the sampling time of the methods employed by Gemp et al. (2022) and Gemp et al. (2024) are at least 10,000 times greater than that of our sampling method. Specifically, when S = 10, which corresponds to the configuration used in our experiments (Section 5), our sampling method achieves a sampling time of approximately 0.004 seconds, while the methods from Gemp al. (2022) and Gemp et al. (2024) require about 1590 seconds.
Results on convergence rates with different sampling methods in terms of time. Now, we compare the convergence rates of algorithms employing different sampling methods in terms of time. We focus on algorithms that minimize NAL or the loss function proposed by Gemp et al. (2024), the only known unbiased loss functions. We conduct experiments on Liar's Dice, which has the largest number of actions (2306) among all tested games. For the algorithms employing the sampling method outlined in Algorithm 1, we set = 100 to learn a sufficiently accurate approximation of NE, while maintaining all other parameters as described in Section 5. For the algorithms that adopt the sampling method utilized in Gemp et al. (2022) and Gemp et al. (2024), We reduce T and T. in Section 5 by factor of 100 since the sampling time associated with the method in Gemp et al. (2022) and Gemp et al. (2024) is excessively large. In addition, we employ two different settings of the value of S, e.g., S = 2 and S = 100. All other settings remain unchanged from Section 5. Notably, when employing the loss function from Gemp al. (2024), F also contributes to the gradient backpropagation, consistent with the settings in the original paper by Gemp al. (2024). The experimental results are presented in Figure 16. We observe that both algorithms minimizing NAL exhibit faster convergence rate than minimizing the loss function proposed by Gemp et al. (2024). More importantly, we find that the wall times of the algorithms utilizing the sampling methods from Gemp et al. (2022) and Gemp et al. (2024) are significantly greater than those of the algorithms employing the sampling method in Algorithm 1. This suggests that, when addressing real-world games, the sampling method in Algorithm is more advantageous, as the action space in real-world scenarios vastly exceeds the 2306 actions present in Liar's Dice.
Results on convergence rates of algorithms employing the sampling method used in Gemp et al. (2022) and Gemp et al. (2024) in terms of epochs. We compare the convergence rates of the algorithms when they employ the sampling method presented in Gemp et al. (2022) and Gemp et al. (2024) across all games, measured in terms of epochs. It is important to note that when using the sampling method from Gemp et al. (2022) and Gemp et al. (2024), the runtime of the algorithms is primarily determined by the sampling time. Therefore, the runtime difference between algorithms with the same number of epochs is negligible, which implies that analyzing the convergence rates in terms of epochs sufficient to
25

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
reflect the convergence rates in terms of runtime. As shown in Figure 16, we focus on algorithms that minimize NAL and the loss function proposed by Gemp et al. (2024). We reduce T and Tu, in Section 5 by a factor of 100, and set 5 to 2 instead of 10, as the sampling time associated with the methods in Gemp et al. (2022) and Gemp et al. (2024) is excessively large. All other settings remain unchanged from Section 5. The experimental results are presented in Figure 17. In alignment with the findings in Section 5, we observe that the algorithm minimizing NAL exhibits a significantly superior convergence rate compared to the algorithm minimizing the loss function proposed by Gemp et al. (2024). More critically, in numerous games, the latter algorithm fails to learn sufficiently accurate NE. Conversely, the algorithm minimizing NAL successfully learns an accurate NE in nearly all games, characterized by exploitability upproaching zero.
Results on convergence rates of C (x) and L (z:). As shown in Appendix H. it is clear that (i) the first-order gradient of ( (a variant of the loss function in Gemp et al. (2024)) is identical to that of (x)) and (ii) NAL is approximation of 2T (22) We evaluate the convergence rates of algorithms minimizing 2 or 2T (x))/2T. Note that the term 2r from that NAL is an approximation of 2 (x)) (2x)2T. For convenience, throughout the rest of this paper, we refer to algorithms minimizing CT (a) (CI (z)) as those minimizing ( (2) respectively. For both algorithms, we use the parameters that minimize NAL.. The experimental results are shown in Figure 18. The algorithm minimizing 4 (x) significantly outperforms the algorithm minimizing C (z). Since the first-order gradients of (2) and 2 (x) are identical, in scenarios where the entire payoff matrix is known (i.e., no sampling required), the performance of both algorithms should be consistent when using standard non-convex stochastic methods, such as SGD. However, as shown in Figure 18, under the sampled play, the algorithm minimizing (xx) significantly outperforms the one minimizing C)(2)) (zz), highlighting the substantial impact of variance on convergence. The results also show that the algorithm minimizing NAL outperforms the one minimizing (x) by a large margin, further demonstrating the strong influence of variance on convergence, as NAL is merely an approximation of 2 (az). Furthermore, the performance of the algorithms minimizing NAL or 2 (a:) is nearly identical across all games. We hypothesize that this phenomenon arises primarily because the term Va, ((T22) TW;,)
(r35, ) 27 27 is relatively small in magnitude compared to the term sgl F7 (F,T ar() 1] due the influence of the entropy term embedded within sgl F (F." ...
Results on convergence rates with different neural network structures. As mentioned in the main text, we evaluate the performance of different algorithms across various network architectures. Specifically, we replace the Softmax function with Sparsemax (Martins& & Astudillo, 2016). The experimental results are presented in Figure 19. Our algorithm demonstrates the fastest convergence rate. Its convergence behavior remains stable, while the convergence rates of the other algorithms experience sigmificant degradation. In particular, the algorithm minimizing the loss function in Gemp et al. (2024) exhibits output instability, often producing NaN values in numerous games, which also explains why the exploitability curve of the algorithm is incomplete in many games. This instability is likely due to excessively high variance. Moreover, the algorithms minimizing ADI or NashApr fail to converge in all games.
Results on convergence rates of NAL with or without (F.T",, ...)1. As mentioned in the main text, we analyze the convergence behavior of NAL when (F. .;)1 1 is omitted. The case where NAL does not include (F . 1 can also be interpreted as Φ;- In this scenario, NE no longer zero point of the first-order gradient of NAL, as the gradient FT - (F, _ does not vanish at NE. Consequently, parameter updates induce a shift in strategy. We evaluate the performance across various values of S (S- 2, 10, 100, oo), where S ac corresponds to the case without sampling. That is. for S = oc, the variance introduced by sampling is zero. The experimental results are presented in Figure 20 and Figure 21, corresponding to Softmax and Sparsemax activation functions, respectively, in the final network layer. Note that the minimum value of 5 is 2. For 5 = 1, it is impossible to estimate FT (F, a 2;)1 using Algorithm 1, as the estimated value of F: - (F.** 2 in this case will always be 0 (since r 2/- = 0).
We observe that when the activation function is Softmax and S = Do, using NAL with é; = as the loss function performs equivalently to the standard NAL. This equivalence arises because the Softmax function normalizes outputs (i.e.. for any z > 0, it produces z >/sum(2), constrained within the simplex), leading identical parameter updates under FTT - [F .2.)) 1 and FT However, when S < oo, using NAL. with क; = 0 introduces higher variance compared to the standard NAL, resulting in degraded performance. This is further evidenced by the increasing performance gap between using FT - (F .t)1 1 and FT as S decreases. For Sparsemax activation, the standard NAL significantly outperforms NAL with é; = O. Notably, we do not observe convergence for NAL with ă; = 0 under Sparsemax. This observation suggests that the convergence of NAL with é; = O when using the Softmax activation is likely consequence of the identical parameter updates induced by FT (F..
2 ..) 1 and F
26

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Forn Games
Goofspiel
Dice
10
10-1
10
10
10
10
10
10
difference
10-1_-
-10-
10"1
-10-
-10-
-104
-00-
-10-
-10-1
-10
-10-2
-10-1
100
10
100
109
2500
5000
7500
10000
2500
7500
10000
2500
5000
7500
10000
2500
7500
10000
10a
Bartrand Oligopaly
10a
10a
10a
Vating
10-1
10-1
10-1
10-1
10-2
difference
10a
10-1
10-2.
10-._
10
-10-
10-2
10
10-2
-10-1
10-1
10-
2500
5000 Berations
7500
10000
2500
5000 Iterations
7500
10000
2500
5000 Beeations
75000
10000
2500
5000
7500
10000
Iterations
Figure 4. Difference between the true value and the estimated value of NAL when the optimizer is Adam.
100
Kuhn Poker
100
Goofsplel
100
Biotto
100
Uar's Dice
duallyy gep
10-2
10
10-2
10
0
-10
10
-10
10
-10-1
-10"
100
100
110
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
5000
7500
10000
100
Bertrand Oligopaly
100
Guess Two Thirds Ave
109
Minimum Effort
10a
Majonby Voting
duality gap
10-2
10-7
10-2
10-2
-10
-10
-10-1
10-1
10-1
-100
-109
-10"
-10
10000
10000
10000
10000
estimated loss
true loss
Figure 5. Value of NAL during the training. The optimizer is Adam. The parameter T 0.1 (from the hyperparameters Table remains constant. Note that the absence of biased estimates in Goofspiel is an artifact of the logarithmic scaling of the y-axis, leading to visual distortion.
Results on convergence rates of NAL with different values To enhance the robustness of our results, we conduct experiments with various values (0, 0.1, 0.5, and 0.9), as illustrated in Figure 22. Our algorithm consistently surpasses the performance of baselines at all tested values. This consistency further confirms that the variance reduction facilitated by our loss function contributes to an accelerated convergence rate.
Results on convergence rates when the strategy is represented using a real vector. As highlighted in Appendix B, we utilize a DNN due to its ability to approximate arbitrary non non-linear functions. This capability allows for the identification of complex equilibrium strategies that simpler representations, such as real vectors, may fail to capture. In Figure 23, the results are displayed with the strategy represented by a real vector. Although all algorithms show varying levels of performance degradation, algorithm consistently outperforms the others.
27

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore Formal-Form Games
Gontsplel
0.3
0.6
0.6
0.6
0.4
duellyy
0.4
0.1
0.2
0.0
0.0
0.0
0.0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
0.6
Bertrond Oligopaly
2.5
Guess Two Thirds Ave
Minimum Effort
1.5
Majority Voting
2.0
0.44
1.5
0.75
1.0
cualit
1.0
0.50
0.2
0.5
0.0
0.00
2500
5000 Iterations
7500
10000
0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000 iterations
7500
10000
Iterations
Iterations
ADI
Figure 6. Empirical convergence rates of tested algorithms when the optimizer is RMSprop.
Uar's
0.3
0.6
0.6
0.0
0.4
duality
0.4
0.2
0.0
0.0
0.0
0.0
2500
7500
10000
2500
10000
2500
5000
10000
2500
5000
7500
10000
Bertrand Oligopely
2.5
Guess Two Thirds Ave
Minimum Effort
Majority Voting
2.0
0.8
1.00
Quality 80
3..4
1.5
0.6
0.75
1.0
0.4
0.50
0.2
0.2
0.25
0.0
0.0
0.0
0.00
7500
5000 Iterations
7500
10000
0
2500
5000 Iterations
7500
10000
2500
5000
7580
10000
2500
5000
7500
10000
Iterations
Iterations
ADI
Figure 7. Empirical convergence rates of tested algorithms when the optimizer is SGD.
28

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore Formal-Form Games
Gootsplel
Uar's
0.6
0.3
0.6
0.4
duellyy
0.4
0.1
0.2
0.0
0.0
0.0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
0.0
Bertrond Dligopaly
2.5
Guess Two Thirds Ave
Minimum Effort
Majority Voting.
1.25
2.0
0.8
1.00
0.44
1.5
0.6
quallty
0.75
0.2
1.0
0.4
0.50
0.2
0.25
0.0
0.0
0.00
2500
5000 Iterations
7500
10000
0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
Iterations
Iterations
iterations
ADI
Figure 8. Empirical convergence rates of tested algorithms when the optimizer is SGD with 10 times larger learning rate for NashApr.
Var's
0.3
0.6
0.6
0.0
0.4
duality
0.4
0.1
0.2
0.0
0.0
0.0
0.0
2500
7500
10000
2500
10000
2500
5000
10000
2500
5000
7500
10000
Bertrand Oligopely
2.5
Guess Two Thirds Ave
Minimum Effort
2.0
Majority Voting
2.0
80.
0.44
1.5
1.0
Quality
1.0
1.0
0.2
0.5
0.0
0.0
0.0
0.0
2500
5000 Iterations
7500
10000
0
2500
5000
7500
10000
2500
5000
7580
10000
2500
5000
7500
10000
Iterations
Iterations
Iterations
ADI
Figure 9. Empirical convergence rates of tested algorithms when the optimizer is SGD with 100 times larger learning rate for NashApr.
29

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore Formal-Form Games
Kuhn Poker
Gootsple el
Blotto
Lars Dice
10a
10"
1022
10
10a
10a
variance
10a
107
10*
10a
10a
10a
10-2
10-1
10-2
10-1
10
2500
5000
75.00
10000
2500
5000
7500
10000
2500
5000
75000
10000
2500
5000
7500
10000
Bertrand Oll gopoly
Guess Two Thirds Ave
Minimum Effort
Majority Voting
10a
vallecce
10a
10
10
10
10-9
10
10-2
10
10-1
10-
10
10
10-7
2500
5000 Iterations
7500
10000
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
Iterations
ite Merations
iterations
Ours
Cemp al., 2024
+ ADI
NashApr
Figure 10. Variances observed in estimating the value of loss functions used by different algorithms when the optimizer is RMSprop.
Kuhn Poker
10a
Goofsplel el
10"
Blotto
Liar's Dice
10a
10:0
10a
valience
10a
10a
10a
10a
107
10-2
10a
10-2
2500
7500
10000
2500
5000
10000
2500
5000
7500
10000
Bertrand Oll gapoly
10a
Guess Tero Thirds Ave
Minimum Effort
Majority Voting
10a
10a
10a
varience
10
10-2
10-3
10-1
10-4
10-1
2500
5000
7500
10000
2500
5000 Iterations
7500
10000
2500
5000 Ite rations
7500
10000
2500
5000
7500
10000
Iterations
Iterations
Ours
- Gemp al., 2024
- ADI
NashApr
Figure 11. Variances observed in estimating the value of loss functions used by different algorithms when the optimizer is SGD.
30

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
10"
201
-200
-127
3500
5300
7520
10320
2500
5200
7520
10300
3500
5000
7530
10000
2000
5000
30000
122
200
-100
5300
2500
$200
2500
5000
2500
5000
1.2
Goorate
Lar's Dloa
100
30
10
20
20
10-1
10300
$200
5000
7500
19200
Beronrd popppyy
0ve5s No Thiis Awo
Mapert 90019
10
30-
30-1
-00-1
2300 5000
7500
10920
2000 5000
7540
(03000
2300
50001 (laratarm
15/00
20500
22:00
5000
1590
20000
1/8
Figure Difference between the true value and the estimated value of loss functions when the optimizer is RMSprop.
540 Mer
SWASER
10
222
20-
202
201
-200
-167
2300
5000
7500
10910
2000
5000
1560
19300
2300
5000
1530
19500
2300
5000
1550
20000
122
102
1.2
10P
2700
5300
2500
5200
35.00
2500
5000
NaxtAge
-2--
-20-1
-00
-129
2500
5300
1520
10320
2500
5200
7550
10300
3500
5050
7520
10300
200
2500
5400
7030
10200
Bettadd DECeeeY
Two ThiTT
-20-
-30-1
-20--
-20-
-00-
-20
300
-127
-107
3500
5000
3520
16356
2000
5200
7720
10310"
35000
5000
7750
10500
2000
5200
7030
10400
Figure 13. Difference between the true value and the estimated value of loss functions when the optimizer is SGD.
31

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Forae Games
S-10
Kuhn Paker 1=000
0.4
5-500
Kuhn
0.3
0.3
0.3
0.3
dualiy gap
0.1
0.1
0.1
0.1
0.0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
Liar's Dice $=10
Var's Dice S=100
Liar's Dice S=500
Lar's S=1000
0.6
0.6
0uallt 940
0.4
0.4
0.4
0.4
0.2
0.0
2500
5000 iterations
7500
10000
2500
5000 iterationn
7500
10000
2500
5000
7500
10000
2500
5000 iterations
7500
10000
Reeations
Figure 14. Empirical convergence rates of our algorithm, well the algorithm proposed by Gemp et al. (2024), with varying numbers of sampled instances at per iteration, are evaluated when the optimier is Adam.
10a
sampling time (seconds)
10a
10
S
ours
Gemp et al.
Figure 15. Comparison of the sampling times of sampling method, shown Algorithm with the sampling method used in Gemp et al. (2022) and Gemp et al. (2024) for various values the number of the sampled instance in Liar's Dice. We conduct our tests on Liar's Dice because has the largest number of actions for each player among the eight games evaluated in the experiments. For cach we run four seeds and report the average sampling times.
32

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore Formll-Form Games
06
9.6
0.3
0.0
20000
time
Alortthim
camplinng
Figure 16. Empirical convergence rates of the algorithms utilizing various sampling methods in Liar's Dice. The x-axis represents the wall time. For algorithms that employ the sampling method outlined in Algorithm I, the parameter S is set 100 ensure the learning of a sufficiently accurate NE. For algorithms that employ the sampling method used in Gemp et al. (2022) and Gemp et al. (2024), we (2022) and Gemp
reduce T and Tu in Section by factor 100, as the sampling method used in Gemp excessively higher sampling times for each instance than that of the sampling method in Algorithm 1. which is used in Section 5. The remaining hyperparameters for each algorithms remain consistent with those used in Section graph on the right a scaled version of the one on the left.
(2024) results
Dice
0.3
0.6
0.6
duality
0.2
0.4
0.4
0.4
0.1
0.2
0.2
0.0
0.0
0.0
0.0
100
Oligopoly
1.0
Minimum
1.0
Majority Vettng
0.8
0.8
Quality 330
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
100
100
25
100
25
100
Iterations
Iterations
Iterations
Iterations
Ours with the sampling method of Gemp et al.
Gemp et al., 2024 with the sampiing method of Gemp et al.
Figure Empirical convergence rates of the algorithms that employ the sampling method used Gemp al. (2022) Gemp (2024). We reduce the 7 and T., in Section by a factor of 100, and set S as 2 rather than 10 in Section 5, The remaining hyperparameters remain consistent with those used Section
33

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore Formal-Form Games
0.4
Kuhn Poker
Gootsplel
0.8
Blotto
Dar's Dice
0.6
0.6
Qualty
0.2
0.4
0.4
0.2
0.2
0.0
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
0.6
Bertrand Oliyopely
2.5
Guess Two Thirds
Minimum Effort
Majority Voting
2.0
0.8
1.00
quality 68
1.5
0.6
0.75
1.0
0.4
0.50
0.5
0.25
0.0
0.00
2500
5000 Iterations
7500
10000
2500
7500
10000
2500
5000
7500
10000
Iterations
Gemp al.,
4(xx
Figure 18. Empirical convergence rates the algorithms that minimize (x) or (ar) when the optimizer Adam, All hyperparameters remain consistent with those used in Section 5.
0.4
Kuhn Poker
Goofspiel
0.8
lettt
Lar's Dice
0.8
0.6
dualey
0.2
0.4
0.4
0.2
0.2
0.0
7500
5000
7500
10000
2500
5000
7500
10000
2500
5000
7500
10000
7500
5000
7500
10000
Bertrand Oligopoly
2.5
Guess Two Thirds
Minimum Effort
Majority Voting
2.0
1.5
0.75
duality
0.50
0.5
0.5
0.25
0.00
2500
5000 Iterations
7500
10000
5000 Iterations
75000
- Ours
Gemp al., 2024
ADI
NashApr
Figure Empirical convergence rates algorithms the Softmax function replaced by Sparsemax. All hyperparameters remain consistent with those used in Section 5, The incompleteness of the exploitability curve of the algorithm is incomplete is due to that network will output NaN value.
34

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
Foln Pole
Hune
Lay's Skee
0.8
5.4
04
0.2
6.2
0.2
0.8
1000 Necrhy V2700
Danrand pepoodty
Gueet No Thins Art
U4a mrm Offert
0.6
2.0
1.00
3.5
3.50
2.2
0.5
3.00
Kzr stors
Kctatoos
2.4
Kahn Polor
Gootgile
Lia's Clce
2.3
040
2.2
0.4
2.2
5200
3000
Berond Rionnnly
Guees km Thard
011tY 012
1..4
2.0
1.50
3.75
2.2
0.4
3.30
0.3
3.25
3.0
3.50
herttins
beratirs
3.4
Kshn Polee
Coolype
Holts
Lar's Dlee
0.6
0.6
0.000 010
0.2
5.4
0.2
0.2
0.2
Berraed Dionedly
Guees Bun Thirtt Apt
Mi mwm Emter
Msarhy Ve7t
1.00
3.4
3.75
0.4
0.5
3.2
3.20
2500
3200
10300
2200
1002
30020
20:0
2007
8-2
2.4
Kchn Rooer
Cootegle
Slttts
Ubite 2804
0.6
010
3.2
5.4
0.2
0.2
1000
bu Blech
sffeet
2:0
3.75
0.4
3.50
2.2
0.5
3.00
2500
2300
Tor Torelurs
Estalboss
Figure 20. Empirical convergence rates of the algorithms that minimize NAL and NAL with é; 0. respectively, when the optimizer Adam. The notation S oc denotes the scenario where sampling not used.
35

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
faln Pole
Lay's Skee
9.2
5.4
0.4
0.2
0.2
0.2
0.8
5200 Danrand plpontty
2500
1000 Hearhy V2100
Guees No Thirss Art
Vmmuum tffert
3.25
0.0
2:0
3.00
1.0
0.2
0.5
3.25
6.5
3.00
12r Terelorr
Ketatoos
2.4
Kahn Poler
Gootgils:
Skitt
0.3
2.2
2.2
0.2
5200
1502
1000
Becond coenlyy
Guees ko Thrmk Axt
March
2.0
03127 015
0.66
3.75
1.0
3.50
0.2
0.3
3.00
5.0
herttins
3.4
Klln Poler
Coutppi
Hrits
La'ss Dee
0.6
0.2
5.4
0:2
0.2
0.2
0.2
Berrad Dlenetly
2.5
Gueet Bo Thrm Apt
U/ mwm Eiter
Msarhy Ve
1.20
018
1.0
1.30
0.5
3.20
5.0
2505
3200
1502
10300
2310
1002
30020
2310
1007
10500
2050
2007
3.4
Kchn Rooe
Cootegle
Settt
Ubite 28e
3.7
0,6
010
0.3
0.4
5.4
2.2
0.2
2500
1000
0.2
Blech
sffeet
Maxt
2:0
3.5
1.0
6.0
0.4
0.5
6.2
0.0
5.0
2500
2310
30020
2300
2010
Tor Torelurs
Estatbon
Figure 21. Empirical convergence rates of the algorithms that minimize NAL and NAL with é; 0. respectively, when the optimizer Adam and the activation function of the final layer Sparsemax. The notation S denotes the scenario where sampling is not used.
36

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
coodager
6.6
0:2
6.4
3.7
0.2
3.2
Bertand pipuadyy
2.3
Oucss bo lirnh
Permun Eflent
1:25
1.20
0.44
0.6
3.75
6.4
3.50
0.5
3.25
0.0
3.00
2502
5200
1502
10000
2300
5002
10020
2310
2002
13000
2010
5000
10000
Outz
2034
NostAp'
2.4
Eoto Note
Gooteiie
0.5
HUtT
Uirs Okte
0.5
5.6
5.2
0.4
3.5
0:2
0.0
6.0
2300
20000
2200
2002
2003
2320
2000
Bonrand Digonaly
235
Thim
Utmmum Effert
2.3
1.25
1.20
210
1.00
3.75
0.5
3.25
3.25
3.50
3.00
2502
3200
1502
30300
5002
20020
2310
2002
12000
2310
2000
Out>
Ap
0.4
Edtn
Cootatee
0.8
C.C
0.4
0.4
3.2
0.2
2300
2200
2002
2007
2020
3000
2.5
Tlinb
Pemmun Eilent
1.25
Mocr
2.2
1.20
2.4
0.6
3.75
1.2
6.4
3.50
05
3.25
0.0
3.20
2502
5200
7502
10000
2500
1002
10030
2550
1003
13000
2510
5000
be
Our
Nastip
2.4
In Nal
Goolyee
0.6
Huze
Lar's (iz
2.5
0.5
0.0
6.6
0.2
2.2
0.2
0.0
2502
1502
20000
2200
2003
2210
2003
2320
3000
0.5
Decmadd Bigooshy
2.5
Thinss
Eifert
2.3
1.00
210
2.4
3.75
3.50
05
0.2
3.25
5.0
3.00
5200
7502
30320
2300
2002
20020
2210
2003
13000
2310
2000
10500
OLts
Gato 2534
NaxtAp
Figure 22, Empirical convergence rates of the algorithms that minimize NAL with various e values. From top to bottom, e takes values of (..1, 0.5, and 0.9.
37

---

Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Fore -orall-Form Games
Lirs
0.6
0.1
0.0
0.0
Mintrum Effort
2.0
0.4
1.00
1.00
0.75
0.75
0.22
0.50
0.50
0.0
0.9
Itorations
Iterattons
Itarationc
Ours
Gemp et al, 2026
+ ADI
NachApp
Figure 23. Empirical convergence rates of tested algorithms when the strategy is represented by real vector rather than DNN.
38


Reviews:
[{"review_id": "HUuUqEvzMH", "reviewer": "Reviewer_f3FW", "summary": "This paper addresses the challenge of efficiently computing Nash equilibria (NE) in normal-form games (NFGs) via non-convex optimization. Prior work, notably by Gemp et al. (2024), proposed an unbiased loss function for this purpose but encountered high variance, which hindered convergence. To overcome this, the authors introduce a novel surrogate loss function - the Nash Advantage Loss (NAL) - which remains unbiased and exhibits significantly lower variance. Empirical results indicate that minimizing NAL yields much faster convergence rates than existing methods. Extensive experiments conducted on eight different NFGs validate the efficacy of the proposed approach, including comparisons across various optimizers and network structures.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your recognition of our work. In response to your suggestion regarding readability, we have added a table of notations and definitions, as presented in Table 1 of https://anonymous.4open.science/api/repo/ICML-2025-ID-10862-Rebuttal/file/notation-table.pdf.", "claims_and_evidence": "Yes (see the strengths discussion below).", "methods_and_evaluation_criteria": "Yes (see the strengths discussion below).", "theoretical_claims": "Although I did not check the details of the proofs (given my limited familiarity with this literature), the technical statements appear well-founded.", "experimental_designs_or_analyses": "Yes (see the strengths discussion below).", "relation_to_broader_scientific_literature": "The paper proposes a novel loss function to efficiently compute NE in NFGs.", "essential_references_not_discussed": "--", "other_strengths_and_weaknesses": "Strengths:\n- The introduction of the Nash Advantage Loss (NAL) is a notable contribution. Its key properties - being unbiased and having reduced variance - directly address the limitations of previous approaches, thereby enhancing the efficiency of NE computation.\n- The theoretical sections are presented rigorously. Although I did not check the details of the proofs (given my limited familiarity with this literature), the technical statements appear well-founded. \n- The paper provides a systematic empirical evaluation of the proposed method against multiple baselines. The experiments not only compare convergence rates and variance of the loss estimates but also explore different optimizers and network structures, consistently demonstrating better performance of the proposed approach.  \n\nWeaknesses:\n- The technical sections are dense, and navigating through the various notations and definitions can be challenging. Including a comprehensive table of notations and definitions in the appendix would greatly aid readers.", "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": "q9k0iAQi2d", "reviewer": "Reviewer_NE5j", "summary": "The authors tackle the problem of NE computation in general-sum multiplayer NFGs, which is known to be a computational hard problem. They build on the work of Gemp et al. (2024) to come up with a novel approach involving a surrogate loss function they call Nash Advantage Loss. They show that NAL is unbiased and that its variance is lower compared to other surrogate loss functions. They provide empirical evidence to support these claims.\n\nPost-rebuttal\nWhile the authors' response was helpful, I do think that it would be valuable to see the exposition regarding the stop-gradient incorporated into the paper, in particular, a precise mathematical definition. While the references are helpful, given that it is a key notion in the paper, it should be defined at the beginning of the paper before the approach is explained in more detail. I will maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your valuable and insightful comments.\n\n**Q1: The use of undefined symbols in the Related Work section.**  \n\n**A:** We fully agree with your observation. The use of undefined symbols compromises the internal consistency of the paper. We will revise our paper to ensure that all symbols are properly introduced and clearly defined before they are used.\n\n---\n\n**Q2: The definition of the stop-gradient operator.**\n\n**A:** We apologize for the confusion, the description of the stop-gradient operator in our paper (lines 175–178 and 767–770) is too brief. Below, we now provide a more detailed introduction to the stop-gradient operator.\n\nLet $b \\in \\mathbb{R}^n$ be a variable. The stop-gradient operator is defined as $sg\\[b\\] = b \\in \\mathbb{R}^n$ with $\\nabla\\_b sg\\[b\\] = 0 \\in \\mathbb{R}^{n \\times n}$. This implies that $sg\\[b\\]$ passes the value of $b$ unchanged in the forward pass, but blocks its gradient during backpropagation. Intuitively, $sg[\\cdot]$ can be regarded as a constant during differentiation. In summary,\n\n- **Forward pass:** $sg\\[b\\]$ returns the value of $b$.\n- **Backward pass:** The gradient is blocked—no gradients are propagated through $b$.\n\nWe will provide a detailed definition of the stop-gradient operator in a future revision. In fact, this operator has already been widely adopted in previous works [1,2,3]. We are inspired by the use of this operator in previous works and adopt it in our work accordingly.\n\nReferences:\n\n1. Grill, Jean-Bastien, et al. \"Bootstrap your own latent: a new approach to self-supervised learning.\" *Advances in neural information processing systems* (NeurIPS). 2020.\n2. Flennerhag, Sebastian, et al. \"Meta-Learning with Warped Gradient Descent.\" *International Conference on Learning Representations* (ICLR). 2020.\n3. Chen, Xinlei, and Kaiming He. \"Exploring simple siamese representation learning.\" *Proceedings of the IEEE/CVF conference on computer vision and pattern recognition* (CVPR). 2021.\n\n---\n\n**Q3: How the stop-gradient enables variance reduction？**  \n\n**A:** Your observation is highly perceptive. The stop-gradient operator is crucial for variance reduction in our stochastic optimization framework. Specifically, it ensures that the variance of our NAL is determined solely by a single estimated variable. In contrast, the loss proposed by Gemp et al. (2024) involves the inner product of two independently estimated variables, leading to significantly higher variance. A more detailed explanation is provided below.\n\nThe core idea behind our NAL is that the stochastic optimization techniques in ML rely solely on unbiased estimates of the first-order gradient, rather than the loss function itself. Leveraging this, we define NAL using the stop-gradient operator as $\\langle sg\\[b\\], x\\_i \\rangle$, where the backpropagated gradient is simply $sg\\[b\\]$. Here, $b$ is an estimate of the first-order gradient, defined as ${F}^{\\tau, x}\\_i - \\langle {F}^{\\tau, x}\\_i , \\hat{x}\\_i \\rangle \\mathbf{1}$, with $\\hat{x}\\_i$ being any strategy. Formally, for each $a\\_i \\in A\\_i$,\n\n$ \\quad   \\nabla\\_{x\\_i(a\\_i)} \\langle sg\\[b\\], x\\_i \\rangle $\n\n$= \\nabla\\_{x\\_i(a\\_i)} \\sum\\_{a'\\_i \\in A\\_i} sg\\[b\\](a'\\_i) x\\_i(a'\\_i) $\n\n$= \\sum\\_{a'\\_i \\in A\\_i} \\nabla\\_{x\\_i(a\\_i)} (sg\\[b\\](a'\\_i) x\\_i(a'\\_i)) $\n\n$= \\sum\\_{a'\\_i \\in A\\_i} \\left( \\nabla\\_{x\\_i(a\\_i)} sg\\[b\\](a'\\_i) \\right) x\\_i(a'\\_i) + sg\\[b\\](a'\\_i) \\nabla\\_{x\\_i(a\\_i)} x\\_i(a'\\_i) ) $\n\n$= \\sum\\_{a'\\_i \\in A\\_i} ( \\nabla\\_b sg\\[b\\](a'\\_i) \\nabla\\_{x\\_i(a\\_i)} b ) x\\_i(a'\\_i) + sg\\[b\\](a\\_i) $\n\n$= sg\\[b\\](a\\_i),$\n\n\nwhere the last equality follows from $\\nabla\\_b sg\\[b\\] = 0 \\in \\mathbb{R}^{n \\times n}$ (considering $sg\\[b\\]$ as a constant during the differentiation process makes this process clearer and more understandable).\n\nIn contrast, Gemp et al. (2024) define a loss based on the inner product $\\langle b', b'' \\rangle$, where $b'$ and $b''$ are independent estimates of ${F}^{\\tau, x}\\_i - \\overline{{F}^{\\tau, x}\\_i}$. Notably, ${F}^{\\tau, x}\\_i - \\overline{{F}^{\\tau, x}\\_i}$ and ${F}^{\\tau, x}\\_i - \\langle {F}^{\\tau, x}\\_i , \\hat{x}\\_i \\rangle \\mathbf{1}$ is equivalent when $\\hat{x}\\_i$ is set to the uniform strategy, which is the setup used in our experiments. As analyzed in Section 4.2, the variance of our NAL estimate scales **linearly** with the variance of $b$, while the variance of Gemp et al.’s loss scales **quadratically** with the variance of $b'$ (and $b''$).", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the proofs, although, it was unclear to me what the formal definition of the stop-gradient operator is; since the paper is about the novel loss function, and the analysis of the loss function hinges on the stop-gradient operator, it seems as though more exposition should be allocated to the stop-gradient operator.", "experimental_designs_or_analyses": "Yes, the experimental design is sound.", "relation_to_broader_scientific_literature": "The authors have done a good job of contextualizing their work with respect to the broader literature, particular in appendices A and B.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I have already commented on my confusion regarding the stop-gradient operator. The empirical results seem to suggest that the method is successful at reducing variance.", "other_comments_or_suggestions": "1. In the Related Work section, it is a bit odd to refer to $\\hat{\\mathbf{x}}_i$ when you have not introduced any notation yet; it just leads to more confusion for the reader (especially, when you say your \"algorithm does not support $\\hat{\\mathbf{x}}_i = 0$\"; these statements would be more appropriately placed after notation has been introduced by your paper, and in the Related Work section, it would make sense to keep things more high-level without introducing notation.", "questions_for_authors": "1. Can the authors explain how the stop-gradient enables variance reduction in their stochastic optimization framework?", "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": "80hGWyFQZq", "reviewer": "Reviewer_wd5S", "summary": "This paper studies computing Nash equilibria (NE) in normal-form games using non-convex stochastic optimization techniques from machine learning. The existing unbiased loss function for approximating NE has high variance, which degrades the convergence rate. To address this, the authors propose a novel surrogate loss function named Nash Advantage Loss (NAL). NAL is theoretically proven to be unbiased and has a significantly lower variance than the existing unbiased loss function. Experimental results on eight normal-form games show that the algorithm minimizing NAL converges much faster and has a lower variance in estimated loss values compared to other algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We sincerely appreciate your time and thoughtful review of our manuscript. Your positive feedback are truly encouraging our work. This paper focuses on leveraging the stochastic optimization techniques in ML to approximate NE of normal-form games. We propose a novel surrogate loss function, which has a significantly lower variance than the existing unbiased loss function. This reduction in variance accelerates the convergence rate for approximating NE. We hope our work can inspire more researchers in the community to engage with this emerging line of leveraging the stochastic optimization techniques in ML for NE computation.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "As far as I checked, the proofs are correct.", "experimental_designs_or_analyses": "The experimental design and analysis sound.", "relation_to_broader_scientific_literature": "Approximating NE of normal-form games is a well-studied area. The main contribution of this paper is a novel surrogate loss function, which is theoretically proven to be unbiased and has a significantly lower variance than the existing unbiased loss function. As the author pointed out, this result show that the variance of the loss function may be one of the key issues influence the convergence rate for approximating NE.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "jcm4IKnCCi", "reviewer": "Reviewer_9MEJ", "summary": "This paper proposes NAL, a loss function that is unbiased and has lower variance compared with the only unbiased loss function proposed in Gemp et al. (2024). The paper conducts theoretical and empirical justifications to show that NAL theoretically and empirically exhibits lower variance and thus accelerates convergence.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your positive assessment and helpful suggestions.\n\n**W1: The contribution of lower variance builds upon the idea of Gemp et al. (2024), which may slightly decrease the paper's originality.**\n\n**A:** Both our work and Gemp et al. (2024) explore leveraging the stochastic optimization techniques in ML for NE computation. However, our work is motivated by a distinct problem compared to Gemp et al. (2024). Gemp et al. (2024) resolve whether NE can be learned via these techniques in ML, while we address how efficiently NE can be learned through these techniques. \n\nSpecifically, Gemp et al. (2024) mainly focus on removing bias introduced by previous loss functions, which could hinder convergence to NE when employing the stochastic optimization techniques in ML. In contrast, our work tackles the high variance issue within the loss function proposed by Gemp et al. (2024), as excessive variance can significantly slow down convergence when learning NE via the stochastic optimization techniques in ML. As you kindly pointed out, \"the observation of the unnecessary large variance in the loss function proposed by Gemp et al. (2024) is insightful,\" we are the first to identify this high-variance issue and to propose a solution to it.\n\n---\n\n**W2.1: The absence of a lower bound of the variance.**\n\n**A**: Now, we present that the variance in estimating ${L}^{\\tau}\\_{G}(x)$ is at least $\\sigma \\min\\_{i \\in N}|A\\_i|$ times greater than that of NAL.\n\nAssume $Var[\\bar{g}^{\\tau,x,j}\\_i(a\\_i)] = \\sigma$ (defined in Section 4.2, and $j \\in \\{ 1, 2\\}$). Applying the derivations in Appendix D (where every \"$\\leq$\" can be replaced with \"$=$\") to Section 4.2, for the loss in Gemp et al. (2024), we have\n$$\nVar[L^{\\tau}\\_{G}(x)] = \\sum\\_{i \\in N} \\sum\\_{a\\_i \\in A\\_i} Var[\\bar{g}^{\\tau,x,1}\\_i(a\\_i)\\bar{g}^{\\tau,x,2}\\_i(a\\_i)] \\geq \\sum\\_{i \\in N} \\sum\\_{a\\_i \\in A\\_i} \\sigma^2 \\geq \\sigma^2 |N|\\min\\_{i \\in N}|A\\_i|.\n$$\nSimilarly, assuming $Var[\\hat{g}^{\\tau,x}\\_i(a\\_i)] = \\sigma$ (defined in Section 4.2), we have\n$$\nVar[L^{\\tau}\\_{NAL}(x)] = \n   \\sum\\_{i \\in N} \\sum\\_{a\\_i \\in A\\_i} (x\\_i(a\\_i))^2 Var[\\hat{g}^{\\tau,x}\\_i(a\\_i)] = \\sum\\_{i \\in N} \\sum\\_{a\\_i \\in A\\_i} (x\\_i(a\\_i))^2 \\sigma \\leq \\sigma|N|,\n$$\nwhere the last inequality comes from that $\\sum\\_{a\\_i \\in A\\_i} (x\\_i(a\\_i))^2 \\leq 1$. Clearly, the variance in estimating ${L}^{\\tau}\\_{G}(x)$ is at least $\\sigma \\min\\_{i \\in N}|A\\_i|$ times greater than that of NAL, since intuitively, $\\sigma$ increases with the size of the game and can grow significantly larger than 1. \n\nWe will include this result in the revised version.\n\n---\n\n**W2.2: The norm of the gradient should also be considered.**\n\n**A**: We sincerely appreciate your insightful suggestion. It is an important aspect that was not considered in our paper. However, since studying the norm of the gradient involves substantial theoretical and empirical investigation, and this paper primarily focuses on variance reduction, we leave a thorough exploration of the gradient norm to future work. Thank you for your thoughtful feedback and for helping to inform the direction of our ongoing research.\n\n---\n\n**Q1: Why use $\\epsilon=1$.**\n\n**A:** The reason is that $F^{\\tau, x}_i - \\overline{F^{\\tau, x}_i}$ (used in Gemp et al. (2024)) and $F^{\\tau, x}_i - \\langle F^{\\tau, x}_i , \\hat{x}_i \\rangle \\mathbf{1}$ (used in NAL) is only equivalent when $\\epsilon=1$ in Algorithm 1. This choice ensures a fair comparison between NAL and the loss in Gemp et al. (2024), as it mitigates the influence of the selection of $\\hat{x}\\_i$. To strengthen the robustness of our results, we include experiments with various $\\epsilon$ values ($0$, $0.1$, $0.5$, and $0.9$), as shown in Figures 1–4 of https://anonymous.4open.science/api/repo/ICML-2025-ID-10862-Rebuttal/file/additional-experimental-results.pdf. Across all tested $\\epsilon$ values, our algorithm consistently outperforms the others.\n\n---\n\n**Q2: Why use a DNN rather than a real vector for strategy representation?**\n\n**A:**  We employ a DNN due to its capability to approximate arbitrary non-linear functions, enabling the discovery of complex equilibrium strategies that simpler representations may overlook (see Appendix A for a detailed discussion on the advantages of DNNs). In contrast, a real vector lacks this expressive power. The results, where the strategy is represented using a real vector, are shown in Figure 5 of https://anonymous.4open.science/api/repo/ICML-2025-ID-10862-Rebuttal/file/additional-experimental-results.pdf. All algorithms exhibit varying degrees of performance degradation, yet our algorithm still outperforms the others.\n\n---\n\n**Q3: How were the duality-gap and exact loss evaluated in experiments? Through brute-force computations or other cleverer approaches?**\n\n**A:** Unfortunately, we rely on brute-force computation. This computation is used solely to assess the performance of the tested algorithms and are not involved in these algorithms' convergence process.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "All proofs seem to be correct.", "experimental_designs_or_analyses": "Yes. The experiments in Section 5 well demonstrates the advantages of NAL compared with existing loss functions.", "relation_to_broader_scientific_literature": "The paper builds on the literature of equilibrium computation in normal-form games. Gemp et al., (2022) and Duan et al., (2023) propose biased loss functions, and Gemp et al. (2024) proposes an unbiased loss function with large variance. This paper contributes to the literature by proposing an unbiased loss function with lower variance. Besides, this paper also contributes to the general machine learning literature where unbiased estimators are key components for convergence of many first-order algorithms.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:  \nS1: The presentation is easy-to-follow and well-written.  \nS2: The observation of the unnecessary large variance in the loss function proposed by Gemp et al. (2024) is insightful.  \nS3: Both theoretical and empirical results about NAL are strong.  \n\nWeaknesses:  \nW1: The contribution of lower variance builds upon the idea of Gemp et al. (2024), which may slightly decrease the paper's originality.  \nW2: The theoretical justification of variance difference between NAL and loss in Gemp et al. (2024) is not rigorous, mainly for following reasons: 1) The expression derived between LHS of line 243-248 is an upper bound of the variance. Actually, to show the variance of Gemp et al. (2024) suffers from a $\\sigma \\max |\\mathcal{A}_i|$ scaling, there should be an example demonstrating the $\\Omega(|\\mathcal{N}|\\sigma^2 \\max |\\mathcal{A}_i|)$ lower bound, or show that the inequality between LHS of line 255-line 256 is tight in some sense. 2) The lower variance of the gradient is not the only evidence for faster convergence. The norm of the gradient should also be taken into consideration. For example, if you scale the NAL loss with a factor $\\sigma \\max |\\mathcal{A}_i|$, then there seems to be no variance advantages for NAL.", "other_comments_or_suggestions": "Comments:  \nC1: It seems that between RHS of line 380-383, the statement should be reverse (alternate Blotto and Liars Dice).  \nC2: I found the game size configurations in the caption of Figure 1. I think it should better appear in the main text, since the large game description is one of the motivation to estimate the loss.", "questions_for_authors": "Questions:  \nQ1: In RHS of line 327, the authors mentioned that $\\epsilon = 1$ in experiments. It means that $\\hat{x}_i$ in NAL is always chosen to be the uniform strategy. Can authors provide more intuitions behind this practice?  \nQ2: In RHS of line 308-316, the authors use a DNN with constant input to represent a strategy. Why do not the authors choose to represent the strategy with real vectors directly? (with post-processed softmax activation)  \nQ3: How were the duality-gap and exact loss evaluated in experiments? Through brute-force computations or other cleverer approaches? It seems that the game size is not small and directly computing the duality gap and loss functions require costly computations.", "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:

Meta-review: All reviewers unanimously agree that this paper makes nice contribution to the fundamental problem of approximating NE in normal-form games by proposing a new surrogate loss that leads to lower variance. The theoretical findings are backed up with extensive experiments on real data.  This is a clear accept.
Decision: Accept (spotlight poster)