# Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2019.

## Built on by (most cited first, 30 of 31)

- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Deep Latent Competition: Learning to Race Using Visual Control Policies in Latent Space](https://mlsanity.com/paper/2102.09812/) (2021)
- [Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2102.08903/) (2021)
- [Towards Multi-Agent Reinforcement Learning driven Over-The-Counter Market Simulations](https://mlsanity.com/paper/2210.07184/) (2022)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [A Game-Theoretic Approach to Multi-Agent Trust Region Optimization](https://mlsanity.com/paper/2106.06828/) (2021)
- [Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL](https://mlsanity.com/paper/2305.17342/) (2023)
- [Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning](https://mlsanity.com/paper/2302.00797/) (2023)
- [Population-aware Online Mirror Descent for Mean-Field Games by Deep Reinforcement Learning](https://mlsanity.com/paper/2403.03552/) (2024)
- [Optimizing αμ](https://mlsanity.com/paper/2101.12639/) (2021)
- [Is Nash Equilibrium Approximator Learnable?](https://mlsanity.com/paper/2108.07472/) (2021)
- [Population-aware Online Mirror Descent for Mean-Field Games with Common Noise by Deep Reinforcement Learning](https://mlsanity.com/paper/2509.03030/) (2025)
- [Learning to Be Cautious](https://mlsanity.com/paper/2110.15907/) (2021)
- [Multi-agent Reinforcement Learning in OpenSpiel: A Reproduction Report](https://mlsanity.com/paper/2103.00187/) (2021)
- [Developing, Evaluating and Scaling Learning Agents in Multi-Agent Environments](https://mlsanity.com/paper/2209.10958/) (2022)
- [Are Equivariant Equilibrium Approximators Beneficial?](https://mlsanity.com/paper/2301.11481/) (2023)
- [Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks](https://mlsanity.com/paper/2211.15936/) (2022)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Composing Efficient, Robust Tests for Policy Selection](https://mlsanity.com/paper/2306.07372/) (2023)
- [On the Power of Perturbation under Sampling in Solving Extensive-Form Games](https://mlsanity.com/paper/2501.16600/) (2025)
- [Deep (Predictive) Discounted Counterfactual Regret Minimization](https://mlsanity.com/paper/2511.08174/) (2025)
- [How Much Due Diligence Before You Bid? Learning in Intractable Takeover Auctions](https://mlsanity.com/paper/2606.29457/) (2026)
- [Safe Multi-agent Learning via Trapping Regions](https://mlsanity.com/paper/2302.13844/) (2023)
- [Meta-Learning in Self-Play Regret Minimization](https://mlsanity.com/paper/2504.18917/) (2025)
- [Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation](https://mlsanity.com/paper/2509.13653/) (2025)
- [Beyond Game Theory Optimal: Profit-Maximizing Poker Agents for No-Limit Holdem](https://mlsanity.com/paper/2509.23747/) (2025)
- [Safe Equilibrium Policy Optimization for Strategic Agent Policies](https://mlsanity.com/paper/2605.30854/) (2026)
- [Enhancing Decision-Making with Large Language Models through Multi-Agent Fictitious Play](https://mlsanity.com/paper/2606.19308/) (2026)

## Abstract (arXiv)

In this paper, we present exploitability descent, a new algorithm to compute approximate equilibria in two-player zero-sum extensive-form games with imperfect information, by direct policy optimization against worst-case opponents. We prove that when following this optimization, the exploitability of a player's strategy converges asymptotically to zero, and hence when both players employ this optimization, the joint policies converge to a Nash equilibrium. Unlike fictitious play (XFP) and counterfactual regret minimization (CFR), our convergence result pertains to the policies being optimized rather than the average policies. Our experiments demonstrate convergence rates comparable to XFP and CFR in four benchmark games in the tabular case. Using function approximation, we find that our algorithm outperforms the tabular version in two of the games, which, to the best of our knowledge, is the first such result in imperfect information games among this class of algorithms.