Learning Nash Equilibria in Normal-Form Games via Approximating Stationary Points

Q14: Why does it make sense to overparameterize a strategy (e.g., 2-action game) with a neural network and then run gradient descent on the network parameters?

A: The scale of the game is determined not only by the number of actions but also by the number of players. For an n-player, m-action, general-sum normal-form game, storing the payoff matrix requires $nm^n$ entries.

As described in the caption of Figure 1 in our original submission, the game settings for Kuhn Poker, Goofspiel, Blotto, Liar's Dice, Bertrand Oligopoly, Guess Two-Thirds Average, Minimum Effort, and Majority Voting are as follows: 2 players with 64 actions, 2 players with 384 actions, 4 players with 66 actions, 2 players with 2304 actions, 4 players with 50 actions, 4 players with 50 actions, 5 players with 30 actions, and 11 players with 5 actions, respectively. The corresponding sizes of the payoff matrices are 8,192 for Kuhn Poker, 294,912 for Goofspiel, 75,898,944 for Blotto, 10,616,832 for Liar's Dice, 25,000,000 for Bertrand Oligopoly, 25,000,000 for Guess Two-Thirds Average, 121,500,000 for Minimum Effort, and 537,109,375 for Majority Voting.

Notably, Majority Voting has the smallest action size and the largest payoff matrix size.

The reason for using a deep neural network is its expressive power, allowing it to capture highly complex patterns and relationships that are difficult to model with traditional methods. Neural networks, especially deep architectures, can approximate arbitrary non-linear functions, making them well-suited for representing the strategic decision-making process in game theory. The ability of deep learning models to learn from raw data—without the need for handcrafted features—enables them to uncover intricate equilibrium strategies that might otherwise be overlooked. We use such a neural network demonstrate the power of DL for approximating the NE. Intuitively, a larger neural network is required to better learn the NE in larger games.

Additional References

[1] Yongacoglu, Bora, et al. "Paths to Equilibrium in Games." The Thirty-eighth Annual Conference on Neural Information Processing Systems.

[2] Grill, Jean-Bastien, et al. "Bootstrap your own latent-a new approach to self-supervised learning." Advances in neural information processing systems 33 (2020): 21271-21284.

[3] Chen, Xinlei, and Kaiming He. "Exploring simple siamese representation learning." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021.

Q9: The dot notation is unideal given it’s widely accepted to mean time derivative, $\dot{x}=dx/dt$. Prior work uses sg[⋅] for the "stop grad" operator which is clearer and more explicit. I would suggest writing equation (3) as $\mathcal{L}^{\tau}\_{NAL}({x}) = \sum\_{i \in \mathcal{N}} \langle sg[{F}^{\tau, {x}}_i- \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}], {x}_i \rangle,$ with the explicit sg[⋅] operator. In equation (6), please state the distribution that the expectation is taken w.r.t., i.e., $E\_{s \sim p_i(s)}$. Theorem 4.2 defines the utility function ${x}_i \log{{x}_i}$. The second term is currently interpreted as a vector. It is missing a sum or a transpose, i.e., it should be ${x}_i^{\mathrm{T}} \log{{x}_i}$.

A: Thank you for your suggestion. We have revised the manuscript accordingly.

Q10: Lemma 4.1 is interesting. Can you derive the y∈Δ that minimizes variance of the norm of b−⟨b,y⟩1?

A: We apologize if we misunderstood your concern. We assume you are referring to the variance caused by sampling. If this is the case, the minimum variance for any given function is always 0.

Q11:Why, in lines 8 & 9 of Algorithm 1, do you suggest sampling actions from a strategy that interpolates between uniform and the current strategy? Can you provide any analysis that motivates this decision? Note it appears you set ϵ=1 in all experiments anyways, and this is precisely the setting that Gemp et al. 2024 already provided analysis for in their Table 2.

A: It is the $\epsilon$-greedy exploration strategy, which is commonly used in game theory, reinforcement learning, and online learning. It is designed to balance the trade-off between exploration (testing new actions to discover their potential rewards) and exploitation (selecting actions that are already known to provide high rewards).

The estimation method shown in the last column of Table 2 in Gemp et al. (2024) is the importance sampling method, where the uniform strategy is used as the sampling strategy. The importance sampling method allows any strategy within the interior of the simplex to be used as the sampling strategy. However, it is important to note that in their algorithm implementation, Gemp et al. (2024) adopt the estimation method from Gemp et al. (2022) in order to incorporate ${F}^{\tau, {x}}_i$ into the gradient backpropagation.

Q12:How does your algorithm behave if you set $\hat{x}_i=0$? How does it behave if you set $\hat{x}_i=1/|A_i|$?

A: Firstly, $\hat{x}_i=0$ is infeasible because Lemma 4.1 requires $\hat{x}_i$ to lie within the simplex. Secondly, in our experiments, we set $\epsilon=1$, which results in $\hat{x}_i=1/|A_i|$ under this condition (line 328-329).

Q13: DL is used as a primary motivation for the paper yet it is not discussed until the experiment section.

A: Thank you for your suggestion. We have added a section in the Appendix (Appendix A) discussing learning NE via DL (highlighted in red).

Furthermore, in Section 2, we discuss the loss functions that can be utilized for learning NE via DL. In Section 4, we highlight that the key idea of our algorithm is inspired by the observation that "optimizers (Robbins & Monro, 1951; Bottou, 2010; Kingma & Ba, 2014) commonly used in DL require only unbiased estimates of the first-order gradient." Finally, the problem we aim to address is, in fact, the unbiased estimation issue in DL-based stochastic optimization. All these aspects are closely related to DL.

We thank the reviewer's comments, this helps us a lot to improve the paper.

Q1: DL has been applied to NE in prior work (GAES [1], NES [2], NFGTransformer [3]).

A: Using DL is not our contribution. Our innovation lies in proposing a novel loss function for learning the NE via DL with an unbiased estimate.

Additionally, the loss functions in the works [1] and [3] you referenced both include the max operator. According to the analysis in (Gemp et al., 2024), the inclusion of the max operator generally leads to biased estimates under sampled play. Regarding work [2], based on Eq. (9) of [2], the final output strategy involves an exponential operation. Even if we obtain an unbiased estimate of $A_p$ (as defined in [2]), we cannot obtain an unbiased estimate of the strategy itself. In other words, work [2] also encounters biased estimation issues under sampled play. In conclusion, these works you mentioned all suffer from the biased estimation issues under sampled play. In contrary, our work proposes an efficient way to learn the NE with an unbiased estimate.

Q2: A loss function is generally accepted to be a function whose value captures some measure of sub-optimality and whose global minimum expresses a desired solution. This is not the case with $L\_{NAL}^τ$. While $L\_{NAL}^τ=0$ at a Nash equilibrium of the entropy regularized game, LNALτ may be less than 0 for some other strategy profiles. This would suggest there exist profiles that are “closer” to a Nash equilibrium than actual equilibria, which is counter-intuitive. One can confirm this phenomenon with a simple example; consider the game where the row player’s payoff matrix is [0011] and the column player’s is the transpose. If you plot $L\_{NAL}^τ$ for $τ=0.2$ and $x_i=1/|A_i|=[1/2,1/2]$ while varying each player’s mixed strategy $x_r=[p,1−p]$ and $x_c=[p,1−p]$, you will see the loss is negative for a range of strategies. For this reason, please plot the actual loss function in experiments. I do not doubt the empirical results of Figure 3 that show the difference between the true expected loss and its estimated value; that is expected. But I would not be surprised if a plot of the true expected loss shows negative values at times.

A: You are absolutely correct that this phenomenon that the value of NAL may be negative exists, as a stationary point may indeed be a saddle point. However, this is precisely one of our key ideas: by approximating stationary points instead of pursuing the global minimum, we aim to reduce the difficulty of learning NE while using our loss function.

Regarding your suggestion to "plot the actual loss function in experiments," we have addressed this in our revision (Appendix E, Figure 17, highlighted in red). The value of NAL can indeed be either greater than or less than 0.

Thank you very much for your review. Here are our replies to your concern.

Q1: While the experimental results are promising and show a significant reduction in variance compared to Gemp et al. (2024), I find the optimization process of the approach to be unusual and lacking theoretical insights. The proposed loss function $L\_{NAL}^τ(x)$ is provided in Equation (2), but its gradient does not match the expression $F_i^{τ,x}−⟨F_i^{τ,x},\hat{x}_i⟩1$ in Equation (3). The authors derive the gradient by stopping the backpropagation of gradients in $F^{\tau,x}_i$. While such an operation can be easily implemented, it lacks mathematical justification. The expression in Equation (3) is not necessarily the direction that maximizes the rate of increase for the proposed loss. Therefore, I do not believe that optimizing the loss using this incorrect gradient is theoretically sound. When discussing Gemp et al. (2024), the authors state that "learning an NE through this loss function requires finding a global minimum in a non-convex optimization problem, which is widely acknowledged as significantly challenging." However, I did not find that the paper addresses this challenge. We still need to locate a global minimum for $L\_{NAL}^τ(x)$.

A:

• We are indeed searching for the stationary point of the NAL. In the definition of NAL (Eq. (2)), we utilize the stop-gradient operator, a widely used technology in DL (Grill et al., 2020;Chen et al., 2021), which implies that the term inside this operator does not participate in gradient backpropagation. Following Reviewer RHJo's suggestion, we have updated Equation (2) to $\mathcal{L}^{\tau}\_{NAL}({x}) = \sum\_{i \in \mathcal{N}} \langle sg[{F}^{\tau, {x}}_i - \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}], {x}_i \rangle$ for better clarity (the changes are highlighted in red), where $sg[\cdot]$ denotes the stop-gradient operator. Since $sg[{F}^{\tau, {x}}_i - \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}]$ is excluded from gradient backpropagation, it can be treated as a constant. Consequently, the gradient of NAL is as presented in Eq. (3).

• By applying the stop-gradient operator, we effectively transform the problem of estimating the value of the loss function into the task of estimating its gradient, thereby mitigating the high variance issue observed in (Gemp et al., 2024). When Eq. (3) equals zero, the gradient of NAL is also zero, indicating that the point is a stationary point of NAL. Therefore, we are leanring a stationar point of NAL rather than a global minimum.

• The stationary points of NAL are specific to the inclusion of the stop-gradient operator, a feature absent in the definitions of existing loss functions. In this regard, we acknowledge that it cannot be claimed that learning the stationary points of NAL is easier than finding the global minimum of other loss functions. Therefore, we have removed the previous claims that "this approach improves the tractability by solving stationary points" (highlighted in red) and addressing the challenging "learning an NE through this loss function requires finding a global minimum in a non-convex optimization" you mentioned. We also revise our statement about tractability, e.g., “inspired by the fact that learning a stationary point is simpler than a global minimum since a global minimum is necessarily a stationary point while a stationary point is not always a global minimum, we ensure that an NE is a stationary point of NAL to improve the computational efficiency“. In other words, we do not claim that learning NE via minimizing NAL is simpler than other loss function in the revisied version.

• However, it is worth emphasizing that while other loss functions do not include the stop-gradient operator in their definitions, in practice, these loss functions must employ the stop-gradient operator when solving real-world games. This is because $F^{\tau,x}_i$ cannot feasibly participate in gradient backpropagation. Enabling $F^{\tau,x}_i$ to participate in backpropagation would require iterating over all action pairs for every two players, as done in (Gemp et al., 2024) and (Gemp et al., 2022), which is practically infeasible in real-world games. Our results in Figure 12 and Figure 13 further validate this (Note that the algorithm "Gemp et al., 2024 with the sampling method of Gemp et al." in Figure 13 is identical to the original algorithm design presented in (Gemp et al., 2024)). In fact, as detailed in Appendix D, all the loss functions used in all our experiments (Section 5 Experiments) incorporate the stop-gradient operator.

We hope that these comments have addressed the reviewer’s concern.

Q1: It seems unfair to compare the variance of NAL with the variance of loss in (Gemp et al., 2024). It is because the gradient of NAL seems to have square root order magnitudes compared with the gradient of loss in (Gemp et al., 2024).

A: 1) For the calculation of the variance of our loss function values and the loss function values in (Gemp et al., 2024), both the estimated and true values need to be computed. Unfortunately, the loss function in (Gemp et al., 2024) must include a squared term, otherwise, their loss cannot be estimated unbiasedly. Moreover, it is infeasible to compute the variance by taking the square root of the estimated value of loss in (Gemp et al., 2024) after the estimated value was computed because the estimated value may be negative, making the square root operation impossible. 2) Furthermore, directly taking the square root of the variance of the loss in (Gemp et al., 2024) is incorrect. This operation does not yield the variance of the loss in (Gemp et al., 2024) without the square. (We present a comparison of the variance of NAL with the square root of the variance of the loss function from Gemp et al. (2024) in Figure 18. We observe that the variance of NAL is, in most cases, significantly smaller than the square root of the variance of the loss function presented in Gemp et al. (2024). )

Q2: It also seems inappropriate to say this method solves the stationary point of NAL. It is essentially defining a "gradient" in equation (3) for back propagation, which is not the full gradient of the NAL function. The goal is equivalent to finding the zero point of equation(3). Therefore, the claim that this approach improves the tractability by solving stationary point instead of global minimum is questionable.

A:

• We are indeed searching for the stationary point of the NAL. In the definition of NAL (Eq. (2)), we utilize the stop-gradient operator, a widely used technology in DL (Grill et al., 2020;Chen et al., 2021), which implies that the term inside this operator does not participate in gradient backpropagation. Following Reviewer RHJo's suggestion, we have updated Equation (2) to $\mathcal{L}^{\tau}\_{NAL}({x}) = \sum\_{i \in \mathcal{N}} \langle sg[{F}^{\tau, {x}}_i - \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}], {x}_i \rangle$ for better clarity (the changes are highlighted in red), where $sg[\cdot]$ denotes the stop-gradient operator. Since $sg[{F}^{\tau, {x}}_i - \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}]$ is excluded from gradient backpropagation, it can be treated as a constant. Consequently, the gradient of NAL is as presented in Eq. (3). By applying the stop-gradient operator, we effectively transform the problem of estimating the value of the loss function into the task of estimating its gradient, thereby mitigating the high variance issue observed in (Gemp et al., 2024). When Eq. (3) equals zero, the gradient of NAL is also zero, indicating that the point is a stationary point of NAL.
• The stationary points of NAL are specific to the inclusion of the stop-gradient operator, a feature absent in the definitions of existing loss functions. In this regard, we acknowledge that it cannot be claimed that learning the stationary points of NAL is easier than finding the global minimum of other loss functions. Therefore, we have removed the previous claim that "this approach improves the tractability by solving stationary points" (highlighted in red). We also revise our statement about tractability, e.g., “inspired by the fact that learning a stationary point is simpler than a global minimum since a global minimum is necessarily a stationary point while a stationary point is not always a global minimum, we ensure that an NE is a stationary point of NAL to improve the computational efficiency“. In other words, we do not claim that learning NE via minimizing NAL is simpler than other loss function in the revisied version.
• However, it is worth emphasizing that while other loss functions do not include the stop-gradient operator in their definitions, in practice, these loss functions must employ the stop-gradient operator when solving real-world games. This is because $F^{\tau,x}_i$ cannot feasibly participate in gradient backpropagation. Enabling $F^{\tau,x}_i$ to participate in backpropagation would require iterating over all action pairs for every two players, as done in (Gemp et al., 2024) and (Gemp et al., 2022), which is practically infeasible in real-world games. Our results in Figure 12 and Figure 13 further validate this (Note that the algorithm "Gemp et al., 2024 with the sampling method of Gemp et al." in Figure 13 is identical to the original algorithm design presented in (Gemp et al., 2024)). In fact, as detailed in Appendix D, all the loss functions used in our all experiments incorporate the stop-gradient operator.

Q2: The input, parametrization and usage of NNs should be expanded further.

A: The network architecture is described in detail in Section 5 Experiments: “The network, parameterized by ${\theta}$ and responsible for representing strategy profiles, is structured as a three-layer MLP. Both the input and hidden layers consist of 1024 neurons, while the output layer has $|\mathcal{N}|$ heads, where each head’s dimension corresponds to the action space of its respective player. The hidden layers utilize the ReLU activation function (Krizhevsky et al., 2012), and the output layer applies the Softmax activation function (Dempster et al., 1977), ensuring that the output resides within the simplex."

Therefore, in the experiment, the neural network's input is a constant 1024-dimensional vector rather than a representation of the game itself. However, any input is feasible, and this setup is used in our paper primarily for demonstration purposes. For example, in solving real-world games, the input could be a natural language description of the game. Specifically, the natural language description can be processed by an Large Language Model (LLM), and the output from the embedding layer of the LLM can then be used as the input to the network that solves for the NE.

The reason for using a deep neural network is its expressive power, allowing it to capture highly complex patterns and relationships that are difficult to model with traditional methods. Neural networks, especially deep architectures, can approximate arbitrary non-linear functions, making them well-suited for representing the strategic decision-making process in game theory. The ability of deep learning models to learn from raw data—without the need for handcrafted features—enables them to uncover intricate equilibrium strategies that might otherwise be overlooked. We use such a neural network demonstrate the power of DL for approximating the NE (we provide a detailed discussion on learning NE via DL in Appendix A).

Q3: The paper lacks sufficient comparison/discussion to related prior work. E.g. [2-4]

A: The loss functions in the works [2] and [4] you referenced both include the max operator. According to the analysis in (Gemp et al., 2024), the inclusion of the max operator generally leads to biased estimates under sampled play. Regarding work [3], based on Eq. (9) of [3], the final output strategy involves an exponential operation. Even if we obtain an unbiased estimate of $A_p$ (as defined in [3]), we cannot obtain an unbiased estimate of the strategy itself. In other words, work [3] also encounters biased estimation issues under sampled play. In conclusion, these works you mentioned all suffer from the biased estimation issues under sampled play. In contrary, our work proposes an efficient way to learn the NE with an unbiased estimate.

In addition, these works investigate network architectures tailored for learning NE through DL. However, these architectures are unsuitable for solving real-world games, as they assume that the payoff matrix can be fully loaded into memory as input to the network. In real-world games, the payoff matrix is often too large to fit into memory, necessitating solutions based on sampling a subset of the matrix, referred to as sampled play. In this paper, we consider "sampled play". We are unable to compare with these works because they focus on the scenario where the payoff matrix can be loaded into memory, whereas our work considers the sampled play.

Q4: Is Equation 3 the gradient of some precise loss function? If not, why is it appropriate to consider your approach as finding stationary points?

A: Please see our responses to Q1.

Additional References

[1] Yongacoglu, Bora, et al. "Paths to Equilibrium in Games." The Thirty-eighth Annual Conference on Neural Information Processing Systems.

[2] Grill, Jean-Bastien, et al. "Bootstrap your own latent-a new approach to self-supervised learning." Advances in neural information processing systems 33 (2020): 21271-21284.

[3] Chen, Xinlei, and Kaiming He. "Exploring simple siamese representation learning." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021.

We thank the reviewer for the insightful and useful feedback, please see the following for our response.

Q1: The use of stop-gradients in going from the loss function defined in Equation 2 to Equation 3 does not feel perfectly theoretically justified. For example, it is not clear whether there exists a function whose gradient is exactly Equation 3? But if that is not the case, then it is not clear whether the proposed technique is akin to finding local optima of non-convex landscape or more like the more complex problem of finding zeros of more arbitrary vector field. For the second case, there exist impossibility results [1] that show that local learning rules although clearly sufficient for solving the first problem do not suffice to solve the second one. In any case, I believe that these connections need to be ironed out and expanded more formally.

A:

• Firstly, [1] does not investigate the "problem of finding zeros of more arbitrary vector fields." Instead, [1] studies whether there exist continuous update dynamics that converge to the NE. However, the conclusions in [1] do not apply to situations involving randomness, as stated in [1]: "Finally, we note that our impossibility results do not apply to stochastic dynamics—e.g., discrete-time dynamics in which $\varphi(x)$ is a distribution of possible next points". Our algorithm involves randomness. In addition, Yongacoglu et al. (2024) demonstrate that dynamic convergence to a NE exists when $\varphi(x)$ is discontinuous.

• Secondly, we apologize for the fact that without employing the stop-gradient operator, the function may not exist. However, we are indeed searching for the stationary point of the NAL. In the definition of NAL (Eq. (2)), we utilize the stop-gradient operator, a widely used technology in DL (Grill et al., 2020;Chen et al., 2021), which implies that the term inside this operator does not participate in gradient backpropagation. Following Reviewer RHJo's suggestion, we have updated Equation (2) to $\mathcal{L}^{\tau}\_{NAL}({x}) = \sum\_{i \in \mathcal{N}} \langle sg[{F}^{\tau, {x}}_i - \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}], {x}_i \rangle$ for better clarity (the changes are highlighted in red), where $sg[\cdot]$ denotes the stop-gradient operator. Since $sg[{F}^{\tau, {x}}_i - \langle {F}^{\tau, {x}}_i, \hat{{x}}_i \rangle {1}]$ is excluded from gradient backpropagation, it can be treated as a constant. Consequently, the gradient of NAL is as presented in Eq. (3). By applying the stop-gradient operator, we effectively transform the problem of estimating the value of the loss function into the task of estimating its gradient, thereby mitigating the high variance issue observed in (Gemp et al., 2024). When Eq. (3) equals zero, the gradient of NAL is also zero, indicating that the point is a stationary point of NAL.

• Thirdly, since the stationary points of NAL are specific to the inclusion of the stop-gradient operator, a feature absent in the definitions of existing loss functions, we acknowledge that it cannot be claimed that learning the stationary points of NAL is easier than finding the global minimum of other loss functions. Therefore, we have removed the previous claim that "this approach improves the tractability by solving stationary points" (highlighted in red). We also revise our statement about tractability, e.g., “inspired by the fact that learning a stationary point is simpler than a global minimum since a global minimum is necessarily a stationary point while a stationary point is not always a global minimum, we ensure that an NE is a stationary point of NAL to improve the computational efficiency“. In other words, we do not claim that learning NE via minimizing NAL is simpler than other loss function in the revisied version.

• Lastly, it is worth emphasizing that while other loss functions do not include the stop-gradient operator in their definitions, in practice, these loss functions must employ the stop-gradient operator when solving real-world games. This is because $F^{\tau,x}_i$ cannot feasibly participate in gradient backpropagation. Enabling $F^{\tau,x}_i$ to participate in backpropagation would require iterating over all action pairs for every two players, as done in (Gemp et al., 2024) and (Gemp et al., 2022), which is practically infeasible in real-world games. Our results in Figure 12 and Figure 13 further validate this (Note that the algorithm "Gemp et al., 2024 with the sampling method of Gemp et al." in Figure 13 is identical to the original algorithm design presented in (Gemp et al., 2024)). In fact, as detailed in Appendix D, all the loss functions used in our all experiments incorporate the stop-gradient operator.