Solving Large Sequential Games with the Excessive Gap Technique
arXiv:1810.03063
Abstract
There has been tremendous recent progress on equilibrium-finding algorithms for zero-sum imperfect-information extensive-form games, but there has been a puzzling gap between theory and practice. First-order methods have significantly better theoretical convergence rates than any counterfactual-regret minimization (CFR) variant. Despite this, CFR variants have been favored in practice. Experiments with first-order methods have only been conducted on small- and medium-sized games because those methods are complicated to implement in this setting, and because CFR variants have been enhanced extensively for over a decade they perform well in practice. In this paper we show that a particular first-order method, a state-of-the-art variant of the excessive gap technique---instantiated with the dilated entropy distance function---can efficiently solve large real-world problems competitively with CFR and its variants. We show this on large endgames encountered by the Libratus poker AI, which recently beat top human poker specialist professionals at no-limit Texas hold'em. We show experimental results on our variant of the excessive gap technique as well as a prior version. We introduce a numerically friendly implementation of the smoothed best response computation associated with first-order methods for extensive-form game solving. We present, to our knowledge, the first GPU implementation of a first-order method for extensive-form games. We present comparisons of several excessive gap technique and CFR variants.
Cited by in corpus (7)
- Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
- Unlocking the Potential of Deep Counterfactual Value Networks
- Sparsified Linear Programming for Zero-Sum Equilibrium Finding
- Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall
- Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria
- Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
- Subgame solving without common knowledge