Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent

Edward Lockhart, Marc Lanctot, Julien Pérolat, Jean-Baptiste Lespiau, Dustin Morrill, Finbarr Timbers, Karl Tuyls

Abstract

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.

Introduction

Finding Nash equilibria in two-player zero-sum games with imperfect information, such as Poker, is a fundamental challenge in artificial intelligence. Traditional state-of-the-art methods like Counterfactual Regret Minimization (CFR) and Fictitious Play (XFP) have a significant limitation: they only guarantee convergence to an equilibrium in the average of the policies generated over time. To implement the resulting strategy, one must store and average every policy from every iteration, creating a massive memory bottleneck. Furthermore, this requirement makes it difficult to integrate deep learning effectively, as neural networks are optimized for improving a single current policy rather than maintaining a running average of millions of past states.

Exploitability Descent (ED) addresses this by directly optimizing the current policy to be less exploitable. This approach ensures that the policy being trained is the one that converges to the equilibrium, making it naturally compatible with deep neural networks and significantly more memory-efficient.

The Exploitability Descent Algorithm

The core idea of Exploitability Descent is to iteratively "plug the holes" in a player's strategy that a perfect opponent would exploit. The algorithm operates in a simple two-step loop for each player:

  1. Compute a Best Response: Given the current joint policy, calculate the "worst-case" opponent strategy—the strategy that maximizes the opponent's utility against the current player.
  2. Policy Gradient Update: Perform a gradient ascent step on the player's policy to increase their utility specifically against that best-response opponent.
The Exploitability Descent algorithm pseudocode.

By repeatedly updating the policy to perform better against its own worst-case exploiter, the strategy is pushed toward unexploitability. The authors provide mathematical proofs that for tabular policies, this process converges asymptotically to a Nash equilibrium.

Experimental Results

The algorithm was evaluated on four benchmark games: Kuhn Poker, Leduc Poker, Liar’s Dice (1,1), and Goofspiel (4d). The researchers compared two versions of the algorithm—Tabular ED (using standard probability tables) and Neural ED (using deep neural networks for function approximation)—against industry standards like CFR and XFP.

Exploitability vs. iterations for four benchmark games, comparing Neural Net ED, Tabular ED, CFR, and XFP.

Key Findings

  • Competitive Convergence: In tabular settings, ED's convergence rate is comparable to CFR and XFP across all tested games.
  • Generalization via Neural Networks: A standout result is that Neural ED outperformed its tabular counterpart in Leduc Poker and Goofspiel. In Goofspiel, Neural ED reached an exploitability level several orders of magnitude lower than the tabular version within the same number of iterations. This suggests that the neural network successfully learned underlying structural patterns in the game, allowing it to generalize across states rather than learning each state in isolation.
  • Efficiency: Unlike methods like Neural Fictitious Self-Play (NFSP), ED does not require a massive replay buffer to store past experiences, making it a leaner alternative for deep reinforcement learning in adversarial settings.

Conclusion and Future Work

Exploitability Descent represents a significant step forward by providing a policy gradient method where the "last" policy converges to a Nash equilibrium. This property makes it uniquely suited for large-scale applications using deep learning.

However, the current implementation requires a "Best Response Oracle," which is computationally expensive for massive games like No-Limit Texas Hold'em. Future research will focus on using approximate best responses derived from reinforcement learning and sampling trajectories rather than full game-tree traversals. This evolution would allow ED to scale to the world's most complex strategic environments.

Summary updated

Abstract

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.
BibTeX
@inproceedings{lockhart2019computing,
  author = {Edward Lockhart and Marc Lanctot and Julien Pérolat and Jean-Baptiste Lespiau and Dustin Morrill and Finbarr Timbers and Karl Tuyls},
  title = {{Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=qFPgU9QJW2O},
}
Figure