# ApproxED: Approximate exploitability descent via learned best responses

arXiv: https://arxiv.org/abs/2301.08830 · HTML: https://mlsanity.com/paper/2301.08830/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 71 of its 144 references that are in the map.
- First posted on arXiv 20 Jan 2023.

## Builds on (most cited first, 30 of 71)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Review on Generative Adversarial Networks: Algorithms, Theory, and Applications](https://mlsanity.com/paper/2001.06937/) (2020)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [PacGAN: The power of two samples in generative adversarial networks](https://mlsanity.com/paper/1712.04086/) (2017)
- [An Introduction to Deep Generative Modeling](https://mlsanity.com/paper/2103.05180/) (2021)
- [A Survey on Generative Adversarial Networks: Variants, Applications, and Training](https://mlsanity.com/paper/2006.05132/) (2020)
- [FedGAN: Federated Generative Adversarial Networks for Distributed Data](https://mlsanity.com/paper/2006.07228/) (2020)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Gradients are Not All You Need](https://mlsanity.com/paper/2111.05803/) (2021)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Stochastic Hyperparameter Optimization through Hypernetworks](https://mlsanity.com/paper/1802.09419/) (2018)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Generative Multi-Adversarial Networks](https://mlsanity.com/paper/1611.01673/) (2016)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Multi-Agent Diverse Generative Adversarial Networks](https://mlsanity.com/paper/1704.02906/) (2017)

## Built on by (most cited first, 1 of 1)

- [DiffNash: Finding Nash Equilibrium in High-Dimensional Continuous Action Spaces with Diffusion Policies](https://mlsanity.com/paper/2610.15932/) (2026)

## Abstract (arXiv)

There has been substantial progress on finding game-theoretic equilibria. Most of that work has focused on games with finite, discrete action spaces. However, many games involving space, time, money, and other fine-grained quantities have continuous action spaces (or are best modeled as having such). We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. The standard measure of closeness to Nash equilibrium is exploitability, which measures how much players can benefit from unilaterally changing their strategy. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile. The first method uses a learned best-response function, which takes the current strategy profile as input and outputs candidate best responses for each player. The strategy profile and best-response functions are trained simultaneously, with the former trying to minimize exploitability while the latter tries to maximize it. The second method maintains an ensemble of candidate best responses for each player. In each iteration, the best-performing elements of each ensemble are used to update the current strategy profile. The strategy profile and ensembles are simultaneously trained to minimize and maximize the approximate exploitability, respectively. We evaluate our methods on various continuous games and GAN training, showing that they outperform prior methods.