Solving Large Sequential Games with the Excessive Gap Technique
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-ofthe-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 extensiveform games. We present comparisons of several excessive gap technique and CFR variants.
Previous results on zero sum imperfect information games such as poker have mostly used counterfactual regret minimization (CFR) and variants to find approximate equilibria, even though CFR has worse theoretical guarantees than first order methods (FOM).  This paper shows that a specific first order method called the excessive gap technique with aggressive step size (EGT/AS) is competitive with CFR and it's variants.  This means that it performs worse than the best CFR variants, but better than others.  The paper is a somewhat incremental extension of previous work laying out the theory of EGT and the specific distance functions needed.  Previous work also introduced EGT/AS, and showed that it worked on small to medium sized games.  The main contributions of this paper are 1. Showing that EGT/AS works reasonably well on large games, specifically poker endgames arising from Libratus. 2. Some technical and numerical details concerning solving EGT subprograms in numerically stable ways, and a bit of (relatively straightforward) discussion about mapping these computations to GPUs. I would advocate accepting this paper, as demonstrating performance of EGT/AS on interesting games is a useful contribution, and is useful for guiding future research.  The sense I get from this paper is that the space of algorithms spanned by CFR, EGT, and their variants is far from settled, and it seems likely that future work will find better variants that match the best theoretical guarantees with better empirical performance.  That blending isn't this paper, but it's useful to know that EGT/AS is an empirical contender (even if it isn't as good as the best CFR variants for reasonable amounts of convergence).  As a general aside: I am curious if or when when poker algorithms will adopt actual ML techniques.  It's reasonable to include this series of "clever brute force, non-ML" algorithms in NIPS since they are solving a goal clearly within the  scope of NIPS applications, but it's interesting that poker seems to be going the way of chess rather than go and avoi ding primarily ML solutions.  On the subject of reproducibility: the methods presented are clear, so the main reproducibility barrier is having the surrounding machinery for a Libratus-equivalent engine.  This is hard to avoid for this type of scaling paper, so it should not count much against acceptance.  Various notes: 1. The abstract should say "imperfect information" clearly.  It's mathematically implied by not saying "perfect information", but worth being explicit. 2. The first sentence frightens me a little bit (line 21-22).  Hopefully most business and military games are not zero sum. :) 3. Line 99: "and is strongly convex modulus" should be "and has...". 4. Line 108: What norm is ||A||?  From Nesterov it looks like a mixed p-norm operator norm, which no one is going to guess without looking at Nesterov, and I'm confused by the norm would be asymmetrically defined given the symmetric structure of the bilinear program.  Also, what are the a_1, a_2 constants?  Ah, are those the unnecessary linear terms in the bilinear function phi?  Finally, it's bad to introduce phi in line 85, discard it, and then introduce another function named phi in equation (3). 6. Why is the (E)xcessive (G)ap (C)ondition called EGV? 7. It's worth some discussion whether EGT/AS or variants are applicable to the nonzero sum setting, and more generally to games with more than 2 players.  By default I believe the answer is no, since two player zero sum has additionally convexity structure which these algorithms are exploiting heavily.