pith. sign in

arxiv: 2605.19928 · v1 · pith:WGCY4XRInew · submitted 2026-05-19 · 💻 cs.GT · cs.AI· cs.LG

Real-Time Parallel Counterfactual Regret Minimization

Boning Li , Longbo Huang This is my paper

Pith reviewed 2026-05-20 04:26 UTC · model grok-4.3

classification 💻 cs.GT cs.AIcs.LG
keywords counterfactual regret minimizationparallel CFRreal-time game solvingimperfect information gamesdepth-limited solvingCPU-GPU pipelinepoker strategy computation
0
0 comments X

The pith

Parallel CFR decomposes each iteration into seven stages to run 3.3 times faster on billion-history game trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a parallelization method for Counterfactual Regret Minimization that targets real-time computation of strategies in large imperfect-information games. Each CFR iteration is split into a seven-stage pipeline that supports two forms of parallelism, one across information sets and one across tree nodes, while routing leaf evaluations to a GPU. This setup integrates existing techniques such as pruning and abstraction without changing the core algorithm. A sympathetic reader would care because the number of completed iterations within a fixed decision window directly determines the quality of the resulting strategy.

Core claim

The authors claim that decomposing each counterfactual regret minimization iteration into a pipeline of seven stages, combined with parallelism along the dimensions of information sets and tree nodes and GPU batched inference for leaf values, produces a 3.3 to 3.4 times speedup over single-threaded execution while preserving correctness on depth-limited trees containing more than one billion histories.

What carries the argument

The seven-stage decomposition of each CFR iteration that supports orthogonal parallelism by information set and by tree node inside a heterogeneous CPU-GPU pipeline.

If this is right

  • Hundreds of CFR iterations fit inside a typical real-time decision budget of a few seconds.
  • Stronger postflop strategies become computable on trees with over one billion histories.
  • The same pruning, abstraction, and advanced CFR variants remain usable inside the parallel pipeline.
  • Desktop-class hardware suffices instead of requiring large-scale compute clusters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same stage decomposition could be tested on game trees from domains other than poker to check whether the speedup generalizes.
  • Further increases in tree depth might become practical if the pipeline stages are tuned for additional hardware parallelism.
  • Lower per-iteration latency could allow tighter integration between the solver and an online opponent model that updates during play.

Load-bearing premise

The seven-stage decomposition preserves the original CFR convergence guarantees when the stages run in parallel across information sets and tree nodes.

What would settle it

A side-by-side run that measures final exploitability after the same number of iterations in the parallel version versus the single-threaded version; a clear gap in exploitability would show the decomposition altered the algorithm.

Figures

Figures reproduced from arXiv: 2605.19928 by Boning Li, Longbo Huang.

Figure 1
Figure 1. Figure 1: Pipeline of a single CFR iteration in Parallel CFR. Blue stages execute on CPU with [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Per-iteration CFR pipeline time vs. thread count [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Wall-clock convergence comparison between Parallel CFR and PokerRL on a river sub [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
read the original abstract

Counterfactual Regret Minimization (CFR) is the dominant algorithmic family for solving large imperfect-information games, underpinning breakthroughs such as Libratus and Pluribus in No-Limit Texas Hold'em poker. In real-time game-playing systems, the solver must compute a near-equilibrium strategy within a strict time budget of only a few seconds per decision, and the number of CFR iterations completed in this window directly determines play strength. We present \textbf{Parallel CFR}, the first parallelization framework for real-time depth-limited CFR solving that seamlessly integrates pruning, abstraction, and advanced CFR variants. We decompose each CFR iteration into a pipeline of seven stages and identify two orthogonal dimensions of parallelism: \emph{by information set} and \emph{by tree node}. Leaf node evaluation is offloaded to GPUs via batched neural network inference, creating a heterogeneous CPU--GPU pipeline. Experiments on Heads-Up No-Limit Texas Hold'em demonstrate that Parallel CFR achieves $3.3$--$3.4\times$ speedup over the single-threaded baseline on postflop streets, with per-iteration time of ${\sim}47$--$54$~ms on a depth-limited game tree with over $1$ billion histories. All experiments run on a single desktop-class device (NVIDIA DGX Spark), enabling hundreds of CFR iterations within a typical real-time decision budget without requiring datacenter-scale infrastructure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript presents Parallel CFR, a parallelization framework for real-time depth-limited CFR in imperfect-information games. It decomposes each CFR iteration into a seven-stage pipeline, exploits two dimensions of parallelism (by information set and by tree node), offloads leaf evaluations to GPUs via batched neural-network inference, and integrates pruning and abstraction. On a depth-limited Heads-Up No-Limit Texas Hold'em tree exceeding one billion histories, it reports 3.3–3.4× speedup over a single-threaded baseline with per-iteration times of approximately 47–54 ms on a single desktop-class NVIDIA DGX Spark device.

Significance. If the seven-stage parallel schedule produces mathematically equivalent regrets and counterfactual values to sequential CFR, the work would meaningfully advance practical real-time solving. Demonstrating concrete speedups on a billion-history tree while remaining on consumer hardware would allow substantially more iterations inside typical decision budgets, directly improving strategy quality in systems that rely on CFR.

major comments (2)
  1. [Abstract] Abstract: the assertion that the seven-stage decomposition 'preserves' correctness and integrates pruning/abstraction is not accompanied by a synchronization protocol, dependency graph, or argument showing that parallel traversal by information set and tree node yields regrets equivalent to the serial case. CFR convergence depends on consistent sequential accumulation of regrets and counterfactual values; any reordering or stale reads would be load-bearing for the central claim of preserved convergence guarantees.
  2. [Experiments] Experimental evaluation: the reported 3.3–3.4× speedups and 47–54 ms per-iteration times are given without error bars, multiple independent runs, or plots confirming that exploitability or strategy quality after a fixed number of parallel iterations matches the sequential baseline. This verification is required to substantiate that the observed wall-clock improvement does not trade off solution quality.
minor comments (1)
  1. [Abstract] The abstract would benefit from a short clause stating the precise hardware configuration (cores, memory, GPU model) used for the DGX Spark measurements to allow readers to assess reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive comments. We address each major comment below and describe the revisions we intend to make to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that the seven-stage decomposition 'preserves' correctness and integrates pruning/abstraction is not accompanied by a synchronization protocol, dependency graph, or argument showing that parallel traversal by information set and tree node yields regrets equivalent to the serial case. CFR convergence depends on consistent sequential accumulation of regrets and counterfactual values; any reordering or stale reads would be load-bearing for the central claim of preserved convergence guarantees.

    Authors: We agree that an explicit argument for mathematical equivalence is necessary to support the central claim. The seven-stage pipeline executes stages in fixed sequential order with synchronization barriers between stages; parallelism occurs only within stages along dimensions (information-set updates and tree-node traversals) that do not create data dependencies or stale reads for regret and counterfactual-value accumulation. Pruning and abstraction are applied at stage boundaries that preserve the original ordering. To make this fully rigorous, we will add a new subsection containing the dependency graph, a description of the synchronization protocol, and a short proof sketch establishing that the parallel schedule produces identical per-information-set regrets and counterfactual values to the sequential algorithm. revision: yes

  2. Referee: [Experiments] Experimental evaluation: the reported 3.3–3.4× speedups and 47–54 ms per-iteration times are given without error bars, multiple independent runs, or plots confirming that exploitability or strategy quality after a fixed number of parallel iterations matches the sequential baseline. This verification is required to substantiate that the observed wall-clock improvement does not trade off solution quality.

    Authors: The referee correctly notes that the current experimental section reports point estimates without statistical characterization or direct quality comparison. In the revised manuscript we will add (i) timing results from at least five independent runs with error bars, (ii) variance statistics for per-iteration wall-clock time, and (iii) exploitability curves comparing the parallel and sequential solvers after identical numbers of iterations on the same depth-limited tree. These additions will confirm that the observed speedups do not come at the expense of solution quality. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical speedup measured against baseline

full rationale

The paper describes a seven-stage pipeline decomposition of CFR iterations with parallelism by information set and tree node, plus GPU offload for leaves, and reports measured 3.3–3.4× speedup on a depth-limited Hold'em tree. The preservation of convergence is asserted as a property of the decomposition rather than derived from any equation that reduces to its own inputs, fitted parameters renamed as predictions, or load-bearing self-citations. No quoted step equates a claimed result to a prior fit or self-referential definition; the speedup numbers are externally verifiable by re-running the described single-threaded vs. parallel implementation on the same hardware and game tree.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on standard CFR convergence properties and parallel-computing assumptions rather than new fitted constants or invented entities.

axioms (1)
  • domain assumption CFR iterations can be decomposed into seven independent stages that remain correct when parallelized by information set and by tree node.
    Invoked when the pipeline is introduced as preserving original algorithm behavior.

pith-pipeline@v0.9.0 · 5777 in / 1221 out tokens · 34955 ms · 2026-05-20T04:26:39.638037+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

63 extracted references · 63 canonical work pages · 1 internal anchor

  1. [1]

    Advances in Neural Information Processing Systems 20 (NIPS) , year =

    Regret Minimization in Games with Incomplete Information , author =. Advances in Neural Information Processing Systems 20 (NIPS) , year =

    work page

  2. [2]

    Advances in Neural Information Processing Systems 22 (NIPS) , year =

    Monte Carlo Sampling for Regret Minimization in Extensive Games , author =. Advances in Neural Information Processing Systems 22 (NIPS) , year =

    work page

  3. [3]

    Solving Large Imperfect Information Games Using

    Tammelin, Oskari , journal =. Solving Large Imperfect Information Games Using

    work page

  4. [4]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume =

    Solving Imperfect-Information Games via Discounted Regret Minimization , author =. Proceedings of the AAAI Conference on Artificial Intelligence , volume =

    work page

  5. [5]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume =

    Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent , author =. Proceedings of the AAAI Conference on Artificial Intelligence , volume =

    work page

  6. [6]

    A Competitive

    Gilpin, Andrew and Sandholm, Tuomas , booktitle =. A Competitive

    work page

  7. [7]

    Journal of the ACM , volume =

    Lossless Abstraction of Imperfect Information Games , author =. Journal of the ACM , volume =

    work page

  8. [8]

    Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) , year =

    Evaluating State-Space Abstractions in Extensive-Form Games , author =. Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) , year =

    work page

  9. [9]

    Proceedings of the ACM Conference on Economics and Computation (EC) , year =

    Extensive-Form Game Abstraction with Bounds , author =. Proceedings of the ACM Conference on Economics and Computation (EC) , year =

    work page

  10. [10]

    Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit

    Brown, Noam and Sandholm, Tuomas , booktitle =. Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit

    work page

  11. [11]

    Proceedings of the AAAI Conference on Artificial Intelligence , year =

    Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance in Imperfect-Information Games , author =. Proceedings of the AAAI Conference on Artificial Intelligence , year =

    work page

  12. [12]

    Science , volume =

    Heads-Up Limit Hold'em Poker is Solved , author =. Science , volume =

    work page

  13. [13]

    Superhuman

    Brown, Noam and Sandholm, Tuomas , journal =. Superhuman

    work page

  14. [14]

    Advances in Neural Information Processing Systems 30 (NIPS) , year =

    Safe and Nested Subgame Solving for Imperfect-Information Games , author =. Advances in Neural Information Processing Systems 30 (NIPS) , year =

    work page

  15. [15]

    The Thirteenth International Conference on Learning Representations , year=

    Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games , author=. The Thirteenth International Conference on Learning Representations , year=

    work page

  16. [16]

    Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) , year =

    Approximating Game-Theoretic Optimal Strategies for Full-scale Poker , author =. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) , year =

    work page

  17. [17]

    Econometrica , volume =

    A Simple Adaptive Procedure Leading to Correlated Equilibrium , author =. Econometrica , volume =

    work page

  18. [18]

    Contributions to the Theory of Games , volume =

    A Simplified Two-Person Poker , author =. Contributions to the Theory of Games , volume =

    work page

  19. [19]

    International Conference on Machine Learning , pages=

    Opponent-limited online search for imperfect information games , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    work page 2023

  20. [20]

    The Fourteenth International Conference on Learning Representations , year=

    General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess , author=. The Fourteenth International Conference on Learning Representations , year=

    work page

  21. [21]

    Ai Magazine , volume=

    The state of solving large incomplete-information games, and application to poker , author=. Ai Magazine , volume=

    work page

  22. [22]

    International Conference on Computers and Games , pages=

    Abstraction methods for game theoretic poker , author=. International Conference on Computers and Games , pages=. 2000 , organization=

    work page 2000

  23. [23]

    International conference on machine learning , pages=

    Deep counterfactual regret minimization , author=. International conference on machine learning , pages=. 2019 , organization=

    work page 2019

  24. [24]

    Encyclopedia of biostatistics , volume=

    Spearman rank correlation , author=. Encyclopedia of biostatistics , volume=. 2005 , publisher=

    work page 2005

  25. [25]

    David Arthur and Sergei Vassilvitskii , title =

    work page

  26. [26]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Abstraction for solving large incomplete-information games , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  27. [27]

    Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems , pages=

    Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker , author=. Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems , pages=

    work page

  28. [28]

    Proceedings of the National Conference on Artificial Intelligence , volume=

    Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold'em poker , author=. Proceedings of the National Conference on Artificial Intelligence , volume=. 2007 , organization=

    work page 2007

  29. [29]

    Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2 , pages=

    A heads-up no-limit Texas Hold'em poker player: Discretized betting models and automatically generated equilibrium-finding programs , author=. Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2 , pages=

    work page

  30. [30]

    Proceedings of the 7th ACM conference on Electronic commerce , pages=

    Finding equilibria in large sequential games of imperfect information , author=. Proceedings of the 7th ACM conference on Electronic commerce , pages=

    work page

  31. [31]

    , author=

    A Practical Use of Imperfect Recall. , author=. SARA , year=

    work page

  32. [32]

    Proceedings of the 41st International Conference on Machine Learning , pages=

    RL-CFR: improving action abstraction for imperfect information extensive-form games with reinforcement learning , author=. Proceedings of the 41st International Conference on Machine Learning , pages=

    work page

  33. [33]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Automated action abstraction of imperfect information extensive-form games , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  34. [34]

    Proceedings of the 29th International Coference on International Conference on Machine Learning , pages=

    No-regret learning in extensive-form games with imperfect recall , author=. Proceedings of the 29th International Coference on International Conference on Machine Learning , pages=

    work page

  35. [35]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Using sliding windows to generate action abstractions in extensive-form games , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  36. [36]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Regret transfer and parameter optimization , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  37. [37]

    TurboReBeL: 250\

    Boning Li and Longbo Huang , year=. TurboReBeL: 250\

    work page

  38. [38]

    2015 , publisher=

    Simultaneous abstraction and equilibrium finding in games , author=. 2015 , publisher=

    work page 2015

  39. [39]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    No-Regret Strategy Solving in Imperfect-Information Games via Pre-Trained Embedding , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  40. [40]

    , author=

    Abstraction pathologies in extensive games. , author=. AAMAS (2) , volume=

    work page

  41. [41]

    , author=

    Expectation-Based Versus Potential-Aware Automated Abstraction in Imperfect Information Games: An Experimental Comparison Using Poker. , author=. AAAI , pages=

    work page

  42. [42]

    Science , volume=

    Deepstack: Expert-level artificial intelligence in heads-up no-limit poker , author=. Science , volume=. 2017 , publisher=

    work page 2017

  43. [43]

    Advances in neural information processing systems , volume=

    Depth-limited solving for imperfect-information games , author=. Advances in neural information processing systems , volume=

    work page

  44. [44]

    The Fourteenth International Conference on Learning Representations , year=

    Look-ahead Reasoning with a Learned Model in Imperfect Information Games , author=. The Fourteenth International Conference on Learning Representations , year=

    work page

  45. [45]

    IJCAI , volume=

    Accelerating best response calculation in large extensive games , author=. IJCAI , volume=

    work page

  46. [46]

    Advances in neural information processing systems , volume=

    Regret-based pruning in extensive-form games , author=. Advances in neural information processing systems , volume=

    work page

  47. [47]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Fast payoff matrix sparsification techniques for structured extensive-form games , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  48. [48]

    Advances in neural information processing systems , volume=

    Combining deep reinforcement learning and search for imperfect-information games , author=. Advances in neural information processing systems , volume=

    work page

  49. [49]

    International conference on machine learning , pages=

    Reduced space and faster convergence in imperfect-information games via pruning , author=. International conference on machine learning , pages=. 2017 , organization=

    work page 2017

  50. [50]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Strategy-based warm starting for regret minimization in games , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  51. [51]

    arXiv preprint arXiv:1908.09453 , year=

    OpenSpiel: A framework for reinforcement learning in games , author=. arXiv preprint arXiv:1908.09453 , year=

    work page arXiv 1908

  52. [52]

    arXiv preprint arXiv:2407.20351 , year=

    LiteEFG: An efficient python library for solving extensive-form games , author=. arXiv preprint arXiv:2407.20351 , year=

    work page arXiv

  53. [53]

    Contributions to the Theory of Games , volume=

    Extensive games and the problem of information , author=. Contributions to the Theory of Games , volume=. 1953 , publisher=

    work page 1953

  54. [54]

    The Fourteenth International Conference on Learning Representations , year=

    A Faster Parameter-Free Regret Matching Algorithm , author=. The Fourteenth International Conference on Learning Representations , year=

    work page

  55. [55]

    Science Advances , volume=

    Student of games: A unified learning algorithm for both perfect and imperfect information games , author=. Science Advances , volume=. 2023 , publisher=

    work page 2023

  56. [56]

    From poincar

    Perolat, Julien and Munos, Remi and Lespiau, Jean-Baptiste and Omidshafiei, Shayegan and Rowland, Mark and Ortega, Pedro and Burch, Neil and Anthony, Thomas and Balduzzi, David and De Vylder, Bart and others , booktitle=. From poincar. 2021 , organization=

    work page 2021

  57. [57]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Solving imperfect information games using decomposition , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    work page

  58. [58]

    Effective, Efficient, and General Information Abstraction for Imperfect-Information Extensive-Form Games

    Effective, Efficient, and General Information Abstraction for Imperfect-Information Extensive-Form Games , author=. arXiv preprint arXiv:2605.10900 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  59. [59]

    , author=

    Efficient Nash equilibrium approximation through Monte Carlo counterfactual regret minimization. , author=. Aamas , pages=

    work page

  60. [60]

    2026 , eprint=

    Parallelizing Counterfactual Regret Minimization , author=. 2026 , eprint=

    work page 2026

  61. [61]

    Proceedings of the AAAI conference on artificial intelligence , volume=

    Dynamic thresholding and pruning for regret minimization , author=. Proceedings of the AAAI conference on artificial intelligence , volume=

    work page

  62. [62]

    Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence , pages=

    Minimizing weighted counterfactual regret with optimistic online mirror descent , author=. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence , pages=

    work page

  63. [63]

    Steinberger, Eric , year =

    work page