PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Counterfactual Regret Minimization

Noam Brown, Adam Lerer, Sam Gross, Tuomas Sandholm

arXiv:1811.00164v3cs.AIcs.GTcs.LG

TL;DR

Large imperfect-information games are difficult to solve because tabular CFR often depends on manually designed abstractions, while common deep RL methods lack suitable equilibrium guarantees. Deep CFR uses deep neural networks to approximate CFR directly in the full game, and the paper reports strong poker performance, including competitiveness with domain-specific abstractions and superiority to NFSP. The authors identify scalability of sampling and high payoff variance as important boundaries for extending the method.

  • Problem

    Large imperfect-information games commonly require abstractions that demand domain knowledge and may provide only coarse approximations, while popular deep RL methods do not generally converge to good equilibria in such games.

  • Method

    Deep CFR uses deep neural networks and external-sampling MCCFR to approximate tabular CFR on the full, unabstracted game.

  • Results

    Deep CFR achieves strong performance in large poker games, outperforms NFSP, and is competitive with domain-specific tabular abstraction techniques.

  • Takeaways & Limitations

    Deep CFR provides a theoretically principled non-tabular CFR approach that succeeds in large games without relying on advanced domain knowledge.

  • Takeaways & Limitations

    Extending Deep CFR to larger games likely requires more scalable sampling strategies and methods to reduce the high variance of sampled payoffs.

Abstract

from arXiv · show

Counterfactual Regret Minimization (CFR) is the leading framework for solving large imperfect-information games. It converges to an equilibrium by iteratively traversing the game tree. In order to deal with extremely large games, abstraction is typically applied before running CFR. The abstracted game is solved with tabular CFR, and its solution is mapped back to the full game. This process can be problematic because aspects of abstraction are often manual and domain specific, abstraction algorithms may miss important strategic nuances of the game, and there is a chicken-and-egg problem because determining a good abstraction requires knowledge of the equilibrium of the game. This paper introduces Deep Counterfactual Regret Minimization, a form of CFR that obviates the need for abstraction by instead using deep neural networks to approximate the behavior of CFR in the full game. We show that Deep CFR is principled and achieves strong performance in large poker games. This is the first non-tabular variant of CFR to be successful in large games.

1. Introduction

Imperfect-information games require approximate equilibria, but solving them with CFR becomes difficult at large scale. Deep CFR replaces manually constructed abstractions with neural function approximation while retaining CFR’s equilibrium-oriented framework.

  • Imperfect-information games involve strategic interactions under partial information, including negotiations, auctions, and cybersecurity interactions.
  • CFR is an iterative algorithm that converges to a Nash equilibrium in two-player zero-sum games.
  • Abstraction simplifies extremely large games by grouping similar states, but constructing effective abstractions requires extensive domain knowledge and may yield only coarse equilibrium approximations.
  • Deep reinforcement learning uses neural networks to handle large state spaces with relatively little game-specific domain knowledge, but popular RL algorithms lack convergence guarantees in imperfect-information games.
  • Deep CFR approximates tabular CFR on the full, unabstracted game using deep neural networks, with theoretical and empirical evaluation in poker.

2. Notation and Background

CFR minimizes counterfactual regret across information sets and uses average strategies to approach equilibrium in two-player zero-sum games. Monte Carlo variants reduce traversal costs by sampling portions of the game tree, with external sampling used here for its simplicity and performance.

  • An information set groups game-tree nodes that a player cannot distinguish, and the player must use the same strategy across those nodes.
  • CFR applies regret minimization separately at each information set, typically using regret matching to choose actions in proportion to positive regret.
  • In two-player zero-sum games, both players’ average strategies form a 2ϵ-Nash equilibrium, making CFR an anytime algorithm for finding approximate equilibria.
  • Vanilla CFR requires full game-tree traversals, whereas MCCFR samples only part of the tree and tracks sampled regrets.
  • External-sampling MCCFR traverses the tree for one player at a time, explores all traverser actions, and samples one action at other information sets and chance nodes.
  • External-sampling MCCFR probabilistically converges to an equilibrium.

3. Related Work

Related work combines regret minimization with faster solvers, fictitious play, regression features, or deep learning, but differs in convergence properties, scalability, or feature construction. Deep CFR is positioned as a multi-agent, function-approximated CFR approach for large games.

  • Although first-order methods have better theoretical convergence rates, practical CFR variants are faster and more robust to error when combined with function approximation.
  • NFSP combines deep function approximation with fictitious play for heads-up limit Texas hold’em, but fictitious play converges more slowly in practice than CFR.
  • Prior deep-learning approaches often estimate subgame values while retaining tabular CFR inside subgames, unlike Deep CFR’s intended multi-agent setting.
  • Regression CFR approximates tabular regrets with regression trees and hand-crafted information-set features rather than learned features.
  • Double Neural CFR also combines deep learning with CFR, but its authors consider only small games and its theoretical soundness is questioned in the cited discussion.

4. Description of the Deep Counterfactual Regret Minimization Algorithm

Deep CFR approximates CFR by learning regret-related values from sampled traversals rather than storing regrets at every information set. It combines external-sampling MCCFR, neural value and policy models, replay memories, and a convergence guarantee tied to approximation error.

  • Deep CFR generalizes across similar information sets with neural networks instead of calculating and accumulating regrets at each information set.
  • Each iteration uses K external-sampling MCCFR traversals, with a neural value network producing action values used by regret matching.
  • Sampled instantaneous regrets are added to a value memory using reservoir sampling when capacity is exceeded.
  • External sampling gives sampled instantaneous regrets that are unbiased estimators of the advantage.
  • The value network is retrained from scratch using mean squared error between predicted advantages and stored instantaneous-regret samples.
  • A separate policy network approximates the average strategy, which is the strategy that converges to a Nash equilibrium.
  • With sufficiently large memory buffers, Deep CFR’s average regret is bounded by a constant proportional to the square root of function approximation error.
  • Deep CFR has no convergence bound under linear weighting because Monte Carlo Linear CFR’s convergence rate has not been established.

5. Experimental Setup

The experiments evaluate Deep CFR in large poker games using neural networks, external-sampling traversal, memory-based training, and Linear CFR. The setup compares it with NFSP and poker-specific abstraction methods while examining convergence-related design choices.

  • Game Domains: FHP contains over 10^12 nodes and over 10^9 infosets, whereas the network has 98,948 parameters; HULH contains over 10^17 nodes and over 10^14 infosets.FHP ends after the second betting round, while HULH continues through four betting rounds.
  • Baselines: Deep CFR is compared with NFSP and state-of-the-art poker abstraction techniques in both games.NFSP provides a domain-independent function-approximation baseline, while the abstraction methods are designed specifically for poker.
  • Network Architecture: The network receives infosets containing cards and bet history and produces action advantages for the value network or probability logits for the average-strategy network.The architecture uses separate card and bet branches before combining their features in fully connected layers.
  • Traversal and Memories: Deep CFR uses external-sampling traversal to collect data for advantage and strategy memories during each CFR iteration.The traverser evaluates every available action, while opponent actions are sampled from the predicted strategy; resulting advantages and probabilities are stored in separate memories.
  • Training: Training the value model from scratch at each iteration rather than reusing previous weights leads to better convergence.The implementation uses reservoir-sampled memories and trains neural networks with stochastic gradient descent and Adam updates.
  • Linear CFR: Linear CFR weights iteration t by t, using weighted error minimization for neural-network training.The method uses LCFR because it is faster than vanilla CFR and tolerates approximation error well; experiments report faster convergence, not better asymptotic performance.

6. Experimental Results

Deep CFR achieves competitive exploitability and head-to-head performance in large poker games while avoiding domain-specific abstraction, though neural computation introduces time and training trade-offs.

  • FHP comparisons: Deep CFR reaches exploitability similar to a 3.6 million-cluster abstraction while converging substantially faster.The comparison measures performance in FHP.
  • NFSP comparison: 37 mbb/g exploitability for Deep CFR compares with 47 mbb/g for NFSP, while Deep CFR is more sample efficient.Both methods spend most wall-clock time performing SGD steps, reducing Deep CFR’s wall-clock advantage relative to its sample-efficiency advantage.
  • Sensitivity analyses: Reducing traversals per iteration slows convergence but preserves final exploitability, whereas reducing SGD updates affects asymptotic exploitability.Increasing model size decreases final exploitability up to a certain size in FHP.
  • Ablations: Retraining from scratch and reservoir sampling are important: fine-tuning raises final exploitability by about 50%, while sliding-window memories stop converging when full.Using the highest-regret action when all regrets are negative also improves final exploitability relative to uniform play.
  • HULH comparison: Deep CFR loses to a 3.3 · 10^8-bucket abstraction by only −11 ± 2 mbb/g and beats NFSP by 43 ± 2 mbb/g in HULH.The comparison uses head-to-head expected value against converged CFR equilibria.
  • FHP comparisons: 2–3 orders of magnitude fewer samples let Deep CFR converge than a lossless abstraction, while remaining competitive with the 3.6 million-cluster abstraction.

7. Conclusions

Deep CFR combines CFR with deep neural-network function approximation to find approximate equilibria in large imperfect-information games without advanced domain knowledge. It achieves strong performance in large poker games, while scalability remains tied to sampling and variance challenges.

  • Deep CFR combines CFR with deep neural-network function approximation to find approximate equilibria in large imperfect-information games.
  • Deep CFR achieves strong performance in large poker games relative to domain-specific abstraction techniques without relying on advanced domain knowledge.
  • Deep CFR and other neural methods target games whose state or action spaces are too large for tabular methods or where abstraction is not straightforward.
  • Extending Deep CFR to larger games will likely require more scalable sampling strategies and methods to reduce high variance in sampled payoffs.
  • Heads-up limit Texas hold’em has two players, alternating positions, and bounded betting actions across four betting rounds.
  • Flop Hold’em Poker is identical to heads-up limit Texas hold’em except that it has only the first two betting rounds.

B. Proofs of Theorems

The proofs review external-sampling MCCFR by formalizing sampled terminal histories, reach probabilities, and regret estimators. The central result is that sampled values and regrets are unbiased, supporting regret bounds under the sampling scheme.

  • MCCFR samples a block of terminal histories on each iteration and considers only histories within that block.
  • External sampling defines reach probabilities using the probability of playing from an infoset to a terminal node under the strategy profile.
  • The probability of sampling terminal history z is the sum of the probabilities of blocks containing z.
  • The sampled value is an unbiased estimator of the true value, so sampled instantaneous regrets estimate the corresponding true regrets without systematic bias.
  • The proof introduces B_p as infoset sets grouped by distinct action sequences and M_p as the sum of their sizes.
  • The convergence analysis applies a general high-probability regret bound under sampling conditions, with external sampling permitting δ = 1.

B.3. K-external sampling

K-external sampling performs multiple external-sampling traversals per iteration and retains a convergence bound similar to standard external sampling. Increasing K can accelerate convergence, although the iteration order remains unchanged.

  • K-external sampling performs K external-sampling traversals per iteration and shares a similar convergence bound with standard external sampling.
  • The K-external-sampling analysis models T iterations as T × K rounds of external sampling.
  • The strategy is unconstrained at infosets with zero positive cumulative regret, which matters because value-network training only uses visited infosets.
  • The theorem establishes a high-probability bound on total regret after T iterations of K-external sampling.
  • The proof transfers the standard external-sampling argument because K-external sampling differs in the choice of σ_T and satisfies the required bound.
  • K-external sampling converges faster as K increases up to a point, but requires the same order of iterations as standard external sampling.

B.4. Proof of Theorem 1

The proof derives a regret bound for sampled regrets by relating traversal frequencies and approximation errors to the total regret expression. It then connects the resulting bound to MSE-based value-network analysis under an assumption that memories remain unfilled.

  • Regret-bound derivation: Rescaling action strategies by a positive infoset-dependent factor preserves the strategy, allowing canceling factors to be inserted into the bound.This manipulation supports the transition from sampled regret terms to expressions involving traversal probabilities.
  • Regret-bound derivation: The proof represents sampled regrets using traversal indicators and the fraction of iterations in which each infoset is visited.The sampled regret is stored when an infoset is traversed; otherwise it is zero.
  • Regret-bound derivation: The resulting expression retains the first term from Theorem 3 and adds a second term for approximation error.The proof identifies approximation error as the additional contribution to the bound.
  • MSE analysis: The analysis decomposes average MSE into bias and variance, with the mean minimizing MSE and achieving loss equal to Var(x).These lemmas are used to analyze the model that minimizes the memory loss.
  • Memory assumption: The memory analysis assumes all sampled regrets are retained, which holds when K · |I_p| · T is smaller than the value-memory capacity.The proof does not use the full-memory case in this assumption.

B.5. Proof of Corollary 1

The corollary’s proof begins with a finite-horizon scaling choice, while the supplied passages emphasize that the full-memory case is not formally analyzed. The authors instead give an empirical intuition for reservoir sampling.

  • Proof setup: The proof sets the scaling parameter ρ to T^-1/4.
  • Memory limitation: The analysis does not formally handle cases where memories become full.The authors expect reservoir sampling to retain an unbiased sample and report that it performs well empirically, unlike a sliding window in Figure 4.

C. Network Architecture

The network architecture embeds cards and betting features in separate branches, combines them through a shared trunk, and outputs action values through a linear action head.

  • Implementation: The implementation uses a default hidden dimension of 256 for the DeepCFRModel.
  • Input branches: The card branch embeds rank, suit, and card identity, while masking nonexistent cards before summing card representations.The architecture supports hole, board, and optional turn and river card groups.
  • Combined trunk: The card and betting representations are concatenated and passed through three residual-style fully connected layers.Each combined layer applies a linear transformation, ReLU, and skip addition.
  • Output: The trunk representation is normalized before a linear action head produces one output for each action.
  • Input branches: The betting branch clamps bet sizes, records whether bets occurred, and processes the resulting features through two linear layers with ReLU activations.
Loading 1811.00164v3…