Research map / Optimization / Nonconvex and smooth optimization

Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization

ICLR 2024 · Optimization › Nonconvex and smooth optimization · approach: Equilibrium learning in zero-sum games · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a loss for approximate Nash equilibria in normal-form games whose squared projected-gradient form admits unbiased Monte Carlo estimation, enabling SGD and bandit (BLiN/StoSOO) solvers with convergence guarantees.

Problem

Computing approximate Nash equilibria in large n-player normal-form games is intractable for existing solvers, and existing equilibrium losses (exploitability, NashConv, NI) are biased under sampled play, so stochastic optimization cannot be applied directly.

Approach

Replace the max-based exploitability with a squared norm of the tangent-space projected gradient, whose expectation can be unbiasedly estimated by taking two independent samples of the gradient (product of independent estimates); entropy regularization (logit QRE) ensures interior equilibria so the loss captures pure equilibria at low temperature.

Key results

• SGD on the entropy-regularized loss is competitive with or improves on FTRL, Regret Matching and ADIDAS in several games (e.g., Shapley's game, where the loss is strongly convex at zero temperature).
• In the 4-player Blotto game, SGD is slowed by saddle points and reaches low but nonzero exploitability.
• BLiN bandit search gives a high-probability global rate of order T^{-1/(2(d_z+2))} with zooming dimension d_z = n·m̄/2; StoSOO gives an Õ(T^{-1/4}) rate after exponential burn-in.

Measured effects reported in the paper

Surprising findings

• Vanilla SGD outperforms previous state-of-the-art solvers in some games despite no global convergence guarantee.
• NashConv is unable to capture the interior Nash equilibrium in Chicken because of high bias under sampled play.

Limitations

• Loss is non-convex and has saddle points (e.g., Blotto), so SGD may stall at nonzero exploitability.
• Global convergence guarantees for bandit methods require an exponential number of burn-in iterations for StoSOO.
• Warm-up loss only valid for interior equilibria; pure equilibria require entropy regularization and a temperature choice.

Experimental setup

Datasets: modified Shapley's game GAMUT D7 Blotto game Chicken game

Benchmarks: modified Shapley's game GAMUT D7 Blotto

Metrics: exploitability welfare

Baselines: FTRL Regret Matching ADIDAS/yQRE^auto NashConv Exploitability

Builds on: NashConv quantal response equilibrium StoSOO BLiN ADIDAS

Closest papers by meaning

• Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games (ICML 2025 · similarity 0.92)
• Competitive Gradient Descent (NeurIPS 2019 · similarity 0.90)
• On the convergence of policy gradient methods to Nash equilibria in general stochastic games (NeurIPS 2022 · similarity 0.89)
• Smooth Fictitious Play in Stochastic Games with Perturbed Payoffs and Unknown Transitions (NeurIPS 2022 · similarity 0.89)
• On the Approximation of Nash Equilibria in Sparse Win-Lose Games (AAAI 2018 · similarity 0.89)
• Robust PAC Learning of Concurrent Stochastic Games (NeurIPS 2026 · similarity 0.87)