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 imperfect-information games—where players possess private information, such as in Poker—is a fundamental challenge in game theory. In these settings, standard Reinforcement Learning (RL) often struggles because the optimal strategy is inherently tied to the opponent's behavior. Existing state-of-the-art algorithms, such as Counterfactual Regret Minimization (CFR) and Fictitious Play (XFP), converge to an equilibrium only in the "average" policy. This requirement to store and compute an average over all historical policies is memory-intensive and complicates integration with deep neural networks, which are optimized for single-policy updates.
The Exploitability Descent Algorithm
Exploitability Descent (ED) addresses these limitations by directly optimizing the current policy against its "worst-case" opponent. The algorithm operates through a repeated two-step process:
- Compute a Best Response: For the current joint policy, calculate the exact strategy a "worst-case" opponent would use to exploit it.
- Gradient Ascent: Update the current policy using gradient ascent to maximize utility against this specific best-response opponent.
By iteratively "plugging the holes" in the strategy, ED ensures the policy converges asymptotically to a Nash equilibrium in the tabular case. The authors propose two variants: Tabular ED, which uses $L_2$ projections or softmax functions to maintain valid probability distributions, and Neural ED, which utilizes deep neural networks to represent and optimize the policy.
Experimental Setup
The algorithm was evaluated on four classic benchmark games used in the game theory community:
- Kuhn Poker: A simplified 3-card poker game.
- Leduc Poker: A larger poker variant with a 6-card deck and two betting rounds.
- Liar’s Dice (1,1): A bidding game involving hidden dice rolls.
- Goofspiel (4-card): A card-bidding game played with imperfect information (bids are unrevealed).
Results and Discussion
ED demonstrates convergence rates comparable to industry standards like CFR and XFP in tabular settings. A significant breakthrough is the performance of Neural ED; in Leduc Poker and Goofspiel, the neural network version converged more effectively than the tabular version, suggesting that the network successfully learned and generalized the underlying game structure.
Key findings include:
- Current Iterate Convergence: Unlike CFR, the policy held at the end of training is the equilibrium strategy, removing the need for policy averaging.
- Deep Learning Synergy: The gradient-based update rule allows ED to integrate seamlessly with modern deep learning frameworks.
- Efficiency and Stability: Neural ED reached low exploitability in Leduc Poker significantly faster than baselines like Neural Fictitious Self-Play (NFSP) and showed monotonic improvement without the "cycling" common in other self-play methods.
Conclusion
While ED currently relies on a perfect Best Response oracle—which is computationally expensive for massive games—it provides a robust framework for direct policy optimization in adversarial settings. Future work involves replacing the perfect oracle with approximate RL-trained models and utilizing sampling techniques to scale the algorithm to larger, more complex environments.
Summary updated