Regret-Based Pruning in Extensive-Form Games
Counterfactual Regret Minimization (CFR) is a leading algorithm for finding a Nash equilibrium in large zero-sum imperfect-information games. CFR is an iterative algorithm that repeatedly traverses the game tree, updating regrets at each information set. We introduce an improvement to CFR that prunes any path of play in the tree, and its descendants, that has negative regret. It revisits that sequence at the earliest subsequent CFR iteration where the regret could have become positive, had that path been explored on every iteration. The new algorithm maintains CFR's convergence guarantees while making iterations significantly faster-even if previously known pruning techniques are used in the comparison. This improvement carries over to CFR+, a recent variant of CFR. Experiments show an order of magnitude speed improvement, and the relative speed improvement increases with the size of the game.
The paper describes a new way to prune parts of the game trees in counterfactual regret minimization. This is achieved by properties of regret-matching and by mixing best responses with CFR inspired by CFR-BR. The end result is by doing some extra book-keeping, much of the CFR tree pass can be omitted and then retroactively adapted at a later point when relevant.Regret-based pruning saves significant computation in terms of nodes touched per iteration and the savings seems to grow as a function of the game. The pruning technique is tied to CFR, but the authors also show improvements in CFR+.I have some questions to help clarify some points:Best response strategies normally prescribe an action (or distribution) for each one of a player's information sets, so the partial best responses in Section 3 are a not clear.Q1. Are these best responses to a well-defined subgame of Player 2? If so, how is the subgame defined?Q2. Assuming "no" to Q1, then the best responses under the zero-reach information sets are in fact just subsets of a full best response strategy. Can you explain why it's possible to directly re-use the CFR-BR theory in this case, where the strategy used from T_0 to T_0 + m is a combined (partial CFR strategy) and (partial best response)? This seems to assume that the games are decomposable.Q3. Can you give some kind of indication as to the raw computation time trade-off? How much overhead does the best response computation take? In the graphs, does "nodes touched" also somehow include the extra time taken for the best response calculations?---- Added after the review + discussion: The most efficient implementation of partial pruning for CFR can be found in code pointed to by "Limit Texas Hold'em is Solved" paper, reference [1]. Using this implementation, each iteration updates regrets for player i and updates the average strategy for player 3-i, alternating the players. This allows partial pruning when just one of the reaches (pi_{-i}) = 0. If accepted for publication, the authors should rephrase or soften their claim in the intro that CFR requires both reaches to 0 to apply partial pruning because, as admitted by the authors in their response, the validity of this claim is implementation-dependent. Specifically, the claim is not true for this most efficient implementation of Vanilla CFR, and thus this claim as written could mislead readers.Also, while it is not entirely clear, the benefit of RBP could be significantly affected if the authors had used this most efficient version of Vanilla CFR to compare to. Any future works/publication should either use this most efficient implementation as a baseline for comparison, or compare against both implementations, since the motivational arguments used in the intro do not hold for this implementation.