Research map / Optimization / Nonconvex and smooth optimization
Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games
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 Nash Advantage Loss (NAL), an unbiased surrogate loss for computing Nash equilibria in normal-form games via stochastic gradient optimization, with much lower estimator variance than the prior unbiased loss of Gemp et al. (2024).
Problem
Computing Nash equilibria in large normal-form games with non-convex stochastic optimization requires a loss that can be unbiasedly estimated from sampled plays, but the only known unbiased loss has high variance that slows convergence.
Approach
Defines the loss so that only an unbiased estimate of the first-order gradient is needed: the gradient is the utility gradient minus its inner product with a fixed reference strategy, avoiding the product of two independent estimates that inflates variance. Its zero set matches regularized-game NE, and decreasing the entropy weight tau yields NE of the original game.
Key results
- NAL reaches the fastest empirical convergence to Nash equilibrium across eight NFGs, while the Gemp et al. (2024) unbiased loss fails to converge in Goofspiel and Minimum Effort.
- The variance of the NAL loss estimate is at least two orders of magnitude lower than the Gemp et al. (2024) unbiased loss in all tested games, and up to six orders of magnitude lower in Liar's Dice.
- The estimated-minus-true loss difference for NAL is usually about two orders of magnitude smaller than for the other tested loss functions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Nash Advantage Loss (NAL) instead of the tested existing unbiased or biased loss functions | NE optimization algorithm · Eight NFGs: Kuhn Poker, Goofspiel, Blotto, Liars Dice, Bertrand Oligopoly, Guess Two Thirds Ave, Minimum Effort, Majority Voting | duality gap | Helped |
| Use NAL instead of the existing unbiased loss function | NE optimization algorithm · All eight tested NFGs | variance of estimated loss: at least two orders of magnitude | Helped |
| Use NAL instead of the existing unbiased loss function | NE optimization algorithm · Liars Dice | variance of estimated loss: up to six orders of magnitude | Helped |
| Use NAL instead of the other tested loss functions | NE optimization algorithm · Eight tested NFGs | difference between estimated and true loss: two orders of magnitude | Helped |
| Use the existing unbiased loss function instead of NAL | NE optimization algorithm · Goofspiel and Minimum Effort | duality gap | Hurt |
| Use ADI instead of NAL | NE optimization algorithm · Blotto | duality gap | Hurt |
| Use NashApr instead of NAL | NE optimization algorithm · Liars Dice | duality gap | Hurt |
| Increase the number of sampled instances per iteration (ablation) | NAL algorithm · Kuhn Poker and Liars Dice | duality gap | Helped |
| Use RMSprop or SGD instead of Adam (ablation) | NAL algorithm · Tested NFGs | duality gap | No clear effect |
| Replace Softmax with Sparsemax (ablation) | NAL algorithm · Tested NFGs | duality gap | No clear effect |
| Replace Softmax with Sparsemax (ablation) | Baseline algorithms · Tested NFGs | duality gap | Hurt |
| Remove the term ⟨Fτ, xᵢ, x̂ᵢ⟩1 from NAL (ablation) | NAL algorithm · Tested NFGs | duality gap | Hurt |
Surprising findings
- The Gemp et al. (2024) unbiased loss fails to converge in Goofspiel and Minimum Effort, and the biased ADI loss fails in Blotto.
- In Bertrand Oligopoly, the Gemp et al. loss had lower variance than NAL, yet converged more slowly, which the authors attribute to high early variance.
Limitations
- No convergence guarantee for the optimization itself; convergence depends on the stochastic optimizer used.
- Kuhn Poker and Liar's Dice do not reach an exact NE at the chosen sample size S, which the authors attribute to small S.
- Evaluated only on normal-form games; extension to imperfect-information extensive-form games is left for future work.
Experimental setup
Datasets: Kuhn Poker Goofspiel Blotto Liar's Dice Bertrand Oligopoly Guess Two Thirds Ave Minimum Effort Majority Voting
Benchmarks: Kuhn Poker Goofspiel Blotto Liar's Dice Bertrand Oligopoly Guess Two Thirds Ave Minimum Effort Majority Voting
Metrics: duality gap variance of loss estimate difference between estimated and true loss
Baselines: Gemp et al. 2024 loss ADI NashApr Simultaneous gradient descent
Builds on: Gemp et al. 2024 unbiased loss Adam tangent residual
Closest papers by meaning
- Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization (ICLR 2024 · similarity 0.92)
- Towards convergence to Nash equilibria in two-team zero-sum games (ICLR 2023 · similarity 0.89)
- Learning Deviation Payoffs in Simulation-Based Games (AAAI 2019 · similarity 0.88)
- Competitive Gradient Descent (NeurIPS 2019 · similarity 0.88)
- Exploiting hidden structures in non-convex games for convergence to Nash equilibrium (NeurIPS 2023 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.