One-sentence Summary

DeepMind proposes the first loss function for approximate Nash equilibria in normal-form games that admits unbiased Monte Carlo estimation, enabling standard non-convex stochastic optimization techniques such as SGD to compute equilibria with provable guarantees and outperform previous state-of-the-art approaches.

Key Contributions

• Introduces the first loss function for approximate Nash equilibria in normal-form games that admits unbiased Monte Carlo estimation, addressing bias in exploitability and gradient-based losses under sampled play.
• By enabling unbiased gradient estimation, the formulation allows standard non-convex stochastic optimization methods, including bandit and vanilla stochastic gradient descent, to be used for equilibrium computation with provable guarantees.
• Experiments show stochastic gradient descent based on the loss can outperform previous state-of-the-art approaches for approximating Nash equilibria.

Introduction

Nash equilibria describe stable outcomes in multi-agent systems where no player benefits from a unilateral deviation, making them central to economics, machine learning, and behavioral modeling. In general n-player, general-sum games, however, computing or even approximating equilibria is computationally hard, and practitioners face an equilibrium selection problem when multiple equilibria exist. Existing solvers for normal-form games scale poorly because payoff tensors grow exponentially and common equilibrium losses rely on nonlinear best-response or projection operations that prevent unbiased sampled estimation. The authors formulate approximate Nash equilibrium search as a stochastic nonconvex optimization problem with a Lipschitz bounded loss that admits unbiased Monte-Carlo estimation, allowing bandit and SGD methods to be applied at scale. This approach also supports application-specific objectives such as finding equilibria above a welfare threshold or near observed behavior, and they compare stochastic gradient descent against state-of-the-art baselines on large games.

Method

The authors transform Nash equilibrium approximation into a stochastic optimization problem over the joint mixed strategy space of a game. Each player k maintains a strategy $x_k$xk​ in a simplex, and the joint strategy is $\boldsymbol{x} = (x_1,\ldots,x_n)$x=(x1​,…,xn​). For a given joint strategy, player k has an expected payoff $u_k(\boldsymbol{x})$uk​(x), and the corresponding gradient $\nabla^k_{x_k}$∇xk​k​ measures how payoff changes with player k’s action probabilities. Because strategies are constrained to the simplex, the authors focus on the tangent space of the simplex. The projection onto this tangent space is

$$\Pi_{T\Delta}(v) = v - \frac{1}{m}\mathbf{1}(\mathbf{1}^\top v),$$ΠTΔ​(v)=v−m1​1(1⊤v),

where $m$m is the number of actions. This geometric view is central: an interior strategy is a best response if and only if its projected-gradient norm is zero. This stationarity condition motivates a loss function based directly on projected-gradient norms,

$$\mathcal{L}(\boldsymbol{x}) = \sum_k \eta_k \left\|\Pi_{T\Delta}(\nabla^k_{x_k})\right\|^2,$$L(x)=k∑​ηk​​ΠTΔ​(∇xk​k​)​2,

where $\eta_k > 0$ηk​>0 can be interpreted as a weight or a projected gradient ascent step size for player k. The loss vanishes exactly when every player’s projected gradient is zero, which corresponds to an interior Nash equilibrium. Equivalently, the loss measures how much a one-step projected-gradient ascent update would change each player’s strategy. The authors also connect this loss to exploitability, showing that the maximum gain an opponent can obtain from deviating is upper bounded by a scaled projected-gradient norm and therefore by the loss itself.

A key design choice is to make the loss amenable to one step unbiased Monte Carlo estimation. The difficulty is that the loss contains the squared norm of an expected gradient, and the square of an expectation is not equal to the expectation of the square. To overcome this, the authors use two independent unbiased gradient estimators, $\hat{\nabla}^{k(1)}_{x_k}$∇^xk​k(1)​ and $\hat{\nabla}^{k(2)}_{x_k}$∇^xk​k(2)​, and take the dot product of their projected versions. Conceptually, the projected estimator is

$$\hat{g}^{(p)}_k = \hat{\nabla}^{k(p)}_{x_k} - \frac{\mathbf{1}}{m_k} \left(\mathbf{1}^\top \hat{\nabla}^{k(p)}_{x_k}\right) \mathbf{1},$$g^​k(p)​=∇^xk​k(p)​−mk​1​(1⊤∇^xk​k(p)​)1,

and the product $\hat{g}^{(1)}_k \cdot \hat{g}^{(2)}_k$g^​k(1)​⋅g^​k(2)​ gives an unbiased estimate of the squared norm of the projected expected gradient. The gradient estimators can be constructed at different cost and variance tradeoffs. An exact estimator marginalizes player k’s payoff against all other players’ strategies, while cheaper estimators sample opponents’ actions or sample actions for all players. Sampling increases variance but reduces query complexity, making the method suitable for large games.

The basic projected-gradient loss is most natural for fully mixed interior equilibria. Many games, however, have pure or partially mixed equilibria on the boundary of the simplex, where boundary constraints can make projected-gradient analysis less reliable. To handle these cases, the authors introduce entropy regularization. Each player’s utility becomes

$$u_k^\tau(\boldsymbol{x}) = u_k(\boldsymbol{x}) + \tau S(x_k),$$ukτ​(x)=uk​(x)+τS(xk​),

where $S(x_k) = -\sum_l x_{kl}\ln(x_{kl})$S(xk​)=−∑l​xkl​ln(xkl​) is Shannon entropy and $\tau > 0$τ>0 is a temperature parameter. Entropy regularization changes best responses into a softmax form, guaranteeing that all equilibria have positive probability mass and therefore lie in the interior. The corresponding loss is

$$\mathcal{L}^{\tau}(\boldsymbol{x}) = \sum_k \eta_k \left\| \Pi_{T\Delta}(\nabla^{k\tau}_{x_k}) \right\|^2.$$Lτ(x)=k∑​ηk​​ΠTΔ​(∇xk​kτ​)​2.

The entropy gradient depends only on player k’s known strategy, so it can be added deterministically to the sampled gradient estimator while preserving unbiasedness. The entropy-regularized loss also maintains a bound on exploitability in the original unregularized game,

$$\epsilon \leq \tau \log\left(\prod_k m_k\right) + \sqrt{\frac{2n}{\min_k \eta_k}} \sqrt{\mathcal{L}^{\tau}(\boldsymbol{x})}.$$ϵ≤τlog(k∏​mk​)+mink​ηk​2n​​Lτ(x)​.

Thus, by choosing a small temperature $\tau$τ, the method can approximate both interior and boundary Nash equilibria while preserving an interpretable upper bound on exploitability. As shown in the figure below:

The authors then analyze the optimization landscape of the entropy-regularized loss. Although the loss is generally nonconvex, it is bounded and Lipschitz continuous over the relevant interior region, which makes standard nonconvex optimization assumptions applicable. The gradient of $\mathcal{L}^{\tau}$Lτ can be expressed through projected gradient terms and local curvature information of the game, and the Hessian can be decomposed into a Gram matrix term and a term that vanishes at equilibria. Around an equilibrium, positive definiteness in valid simplex directions corresponds to local strong convexity. The authors introduce the notion of a polymatrix-isolated equilibrium, which occurs when the local polymatrix approximation of the game yields a full-rank curvature certificate in the tangent space of the joint simplex. This condition helps distinguish isolated equilibria from degenerate regions where multiple equilibria may be connected.

The landscape analysis also clarifies why optimization can work in practice despite nonconvexity. The loss surface can contain many saddle points, but these are often associated with high exploitability rather than false equilibria. Refer to the figure below:

Building on this formulation, the authors explore two optimization strategies. The first is stochastic gradient descent applied to $\mathcal{L}^{\tau}$Lτ. At each iteration, the algorithm constructs an unbiased sampled estimate of the projected-gradient loss and updates the strategy profile while keeping the strategies on the simplex. SGD does not provide global convergence in general and can become stuck near saddle points, but it benefits from implicit regularization toward flat minima and performs well empirically on several benchmark games. As shown in the figure below:

The second strategy uses bandit-based global optimization to mitigate local minima and saddle points. Instead of following gradients alone, the algorithm systematically explores the joint strategy space by refining a mesh or partition of the strategy simplex and evaluating sampled points using the unbiased loss estimator. This exploration-exploitation process can be interpreted as a stochastic generalization of exclusion methods for Nash equilibrium approximation. Under the assumption that all quantal response equilibria are polymatrix-isolated, the bandit method obtains a high-probability polynomial convergence rate to approximate Nash equilibria. The approximation quality improves as the temperature $\tau$τ decreases, while the constants in the convergence bound increase through the associated Lipschitz behavior of the regularized loss.

Experiment

Experiments evaluate stochastic gradient descent on several game families by comparing it with established scalable equilibrium approximation methods. The results show that SGD is broadly competitive, performing especially well when the game structure supports convergence, such as in modified Shapley games, while challenging saddle point structures like Blotto remain more difficult. Overall, the findings validate SGD as an effective and structure-sensitive optimizer for approximate equilibrium computation.

Prior loss functions for normal-form games are often biased when game payoffs are estimated by sampling play, because their estimators involve random variables inside max operators or simplex projections. The listed obstacles show that exploitability, NashConv-type losses, fully differentiable exploitability, and gradient-based NashConv all require nonlinear expectations that are not straightforward to estimate without bias. The context suggests unbiased estimation is possible by replacing nonlinear projection with a linear tangent-space projection and using independent samples. Exploitability and NashConv losses become biased when a max over sampled payoffs is estimated directly. Fully differentiable exploitability remains difficult under sampling because it also evaluates a max operator with random payoffs. Gradient-based NashConv requires projecting a random gradient step onto the simplex, introducing projection bias. Simplex-constrained methods create sampling ambiguity unless unconstrained coordinates are first projected.

The experiments examine why common game-theoretic losses are often biased when game payoffs are estimated from sampled play. They find that exploitability, NashConv-type objectives, fully differentiable exploitability, and gradient-based NashConv each involve nonlinear expectations or simplex projections that are difficult to estimate without bias. The findings support using linear tangent-space projections with independent samples for unbiased estimation, while showing that simplex-constrained methods require careful handling to avoid sampling ambiguity.