Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games

Thank you for your positive assessment and helpful suggestions.

W1: The contribution of lower variance builds upon the idea of Gemp et al. (2024), which may slightly decrease the paper's originality.

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.

Specifically, 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.

W2.1: The absence of a lower bound of the variance.

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.

Assume $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

Similarly, assuming $Var[\hat{g}^{\tau,x}\_i(a\_i)] = \sigma$ (defined in Section 4.2), we have

where 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.

We will include this result in the revised version.

W2.2: The norm of the gradient should also be considered.

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.

Q1: Why use $\epsilon=1$.

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.

Q2: Why use a DNN rather than a real vector for strategy representation?

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.

Q3: How were the duality-gap and exact loss evaluated in experiments? Through brute-force computations or other cleverer approaches?

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.

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.

Thanks for your valuable and insightful comments.

Q1: The use of undefined symbols in the Related Work section.

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.

Q2: The definition of the stop-gradient operator.

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.

Let $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,

• Forward pass: $sg$ b $$ returns the value of $b$.
• Backward pass: The gradient is blocked—no gradients are propagated through $b$.

We 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.

References:

1. Grill, Jean-Bastien, et al. "Bootstrap your own latent: a new approach to self-supervised learning." Advances in neural information processing systems (NeurIPS). 2020.
2. Flennerhag, Sebastian, et al. "Meta-Learning with Warped Gradient Descent." International Conference on Learning Representations (ICLR). 2020.
3. Chen, Xinlei, and Kaiming He. "Exploring simple siamese representation learning." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR). 2021.

Q3: How the stop-gradient enables variance reduction？

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.

The 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$,

$\quad \nabla\_{x\_i(a\_i)} \langle sg$ b $, x\_i \rangle$

$= \nabla\_{x\_i(a\_i)} \sum\_{a'\_i \in A\_i} sg$ b $(a'\_i) x\_i(a'\_i)$

$= \sum\_{a'\_i \in A\_i} \nabla\_{x\_i(a\_i)} (sg$ b $(a'\_i) x\_i(a'\_i))$

= \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) )$

$= \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)$

$= sg$ b $(a\_i),$

where 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).

In 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''$).

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.