Technical Summary: Parallelizing Counterfactual Regret Minimization

Problem Statement

While parallelization has been a cornerstone of artificial intelligence, drastically reducing training times for large models, its application to computational game solving remains relatively unexplored. Despite landmark successes in solving large imperfect-information games (e.g., Cepheus, Libratus, Pluribus) relying on some form of parallelism, the specific mechanics of parallelizing Counterfactual Regret Minimization (CFR) algorithms have not been generalized. Existing attempts, such as those by Reis and Rudolf, often suffer from reproducibility issues, require complex control flow per thread, or result in suboptimal quadratic work complexity. Furthermore, previous domain-specific approaches (e.g., in Cepheus) lack generality. The authors identify a need for a generalized, domain-independent framework that can accelerate CFR and its tabular variants without sacrificing the algorithmic properties that make them effective.

Methodology

The authors propose a generalized parallelization framework that reframes the sequence-form version of CFR as a series of linear algebra operations. This transformation allows the application of standard, highly optimized techniques for parallelizing linear algebra (specifically on GPUs) to game solving.

Core Technical Approach

1. Reframing CFR as Linear Algebra:
   The paper converts the tree traversal steps inherent in CFR (top-down for strategy updates, bottom-up for utility observation) into matrix-vector operations. This is achieved using logic matrices (matrices with entries in $\{0, 1\}$) to reconcile different data representations:

   • Sequence vs. Node Representation: Logic matrix $A \in \mathbb{R}^{P \times \Sigma}$ converts between per-node vectors ($\mathbb{R}^P$) and per-sequence vectors ($\mathbb{R}^\Sigma$).
   • Behavioral Representation: Logic matrix $B$ handles the conversion to the behavioral representation ($\mathbb{R}^{\Sigma^+}$), which excludes the empty sequence.
   • Action Aggregation: Logic matrix $C$ aggregates values across available actions at decision points, enabling L1-normalization and expectation calculations via matrix multiplication.

2. Parallelized Tree Traversal:
   Instead of recursive tree traversal, the algorithm decomposes the Tree-Form Sequential Decision Process (TFSDP) into level structures. Adjacency matrices $L^{(d)}$ represent edges at each depth $d$.

   • Top-down traversal (for strategy propagation) is performed by sequentially applying $L^{(1)}, L^{(2)}, \dots, L^{(k)}$.
   • Bottom-up traversal (for utility accumulation) is performed by applying these matrices in reverse order.
   • These operations are implemented using Compressed Sparse Row (CSR) sparse matrix-vector multiplication, which is highly efficient on parallel hardware.

3. Algorithmic Adaptation:
   The framework is designed to be modular. The core parallelized operations (NEXTSTRATEGY and OBSERVEUTILITY) are defined, and specific CFR variants are implemented by appending simple operations to these core functions:

   • CFR+: Adds a flooring operation to regrets.
   • Discounted CFR (DCFR): Applies time-dependent scaling factors to positive and negative regrets.
   • Predictive CFR (PCFR): Incorporates a prediction vector for instantaneous regrets.

Key Contributions

• Generalized Framework: The paper presents a domain-independent framework that treats CFR as linear algebra, making it applicable to any tabular CFR variant (CFR, CFR+, DCFR, PCFR, PCFR+).
• Theoretical Analysis: Using the work-depth model, the authors prove that the parallelized algorithm maintains the same total work complexity ($W = \Theta(|P|)$) as the sequential sequence-form CFR, ensuring no efficiency loss in the absence of parallelism. The depth is shown to be $D = \Theta(k \log B)$, where $k$ is the tree height and $B$ is the branching factor.
• Open-Source Implementation: Unlike previous GPU attempts, this work provides an open-source implementation compatible with the OpenSpiel library, facilitating reproducibility and integration.
• Scalability: The approach effectively splits the game at every depth rather than just at subgame boundaries, potentially yielding higher parallelism than previous architectures like Cepheus.

Experimental Results

The authors evaluated their GPU-accelerated implementation against Google DeepMind's OpenSpiel implementations (Python and C++) running on CPUs across seven benchmark games of varying sizes (from Kuhn poker with 58 nodes to Large Battleship with $5.2 \times 10^7$ nodes).

• Small Games: For small games (e.g., Kuhn poker, Leduc poker), the GPU overhead results in a slowdown compared to CPU implementations.
• Large Games: As game size increases, the parallelized implementation significantly outperforms the CPU baselines.
  • For Small Battleship, the speedup is approximately $2.1 \times 10^2$ times faster than OpenSpiel's C++ implementation.
  • For Medium Battleship, the speedup reaches $1.2 \times 10^3$.
  • For Large Battleship, the speedup is $4.1 \times 10^3$.
  • Overall, the GPU implementation is up to 18,889 times faster than OpenSpiel's Python implementation and 3,413 times faster than its C++ implementation.
• Convergence: The experiments demonstrate that the parallelized implementation achieves the same exploitability reduction over wall-clock time, but in a fraction of the time, with the speedup becoming more pronounced as the game size grows.

Significance and Claims

The paper claims that while this parallelization technique does not necessarily increase the size of the game that can be solved (in terms of memory capacity), it dramatically reduces the time required to find an optimal solution.

• Research Acceleration: The primary value proposition is enabling researchers to test hypotheses, new CFR variants, and hyperparameter regimes with much faster turnaround times.
• Repetitive Settings: The framework is particularly useful for games played in repeated settings (e.g., poker with varying stack sizes) where individual game trees are similar, allowing for rapid re-solving.
• Compatibility: The authors emphasize that their method retains full compatibility with OpenSpiel, allowing it to be used as a drop-in accelerator for existing game-theoretic research without requiring a rewrite of game definitions.
• Modesty: The authors explicitly state that their contribution is not mutually exclusive with previous architectures (like Cepheus's subgame splitting); rather, their technique can be augmented with such architectures for further parallelism. They also acknowledge that while they compare GPU to CPU, the results highlight the potential of parallelism even in regular use cases, though they do not claim to solve games that were previously unsolvable due to memory constraints.