GPU-Accelerated Counterfactual Regret Minimization
counterfactual regret minimization;extensive-form games;graphical processing units;imperfect information games;Nash equilibrium
There are **significant** differences in how GPUs are used in our work versus the works that you brought up.

* We frame the problem of CFR as a series of sparse matrix/vector operations, and the utilization of GPUs for this task is very well studied.
* Reis and Rudolf (not Weng) wrote the CFR implementation **including recursive tree traversal on CUDA**.
* DeepStack's GPU usage is for their **neural network evaluation**. They still perform costly recursive traversal for the lookahead operation (not parallelized). The "Student of Games" and "ReBeL" algorithms also use GPU for their NN, and these particular algorithms are mentioned in our introduction.

They or their connection to GPUs were not mentioned due to space constraints and their (perceived) irrelevance to our approach. With that said, we will mention them in our revision if the reviewer feels strongly about it.

>Space complexity

It's linear w.r.t. the game size.

>accelerate the calculation of exploitability?

Yes, our approach can be used. But, we did not explore it in this work.

We hope this addresses some of your concerns.
Thank You for Your Review!
We would like to address some points that were brought up.

>The open spiel codebase is not an example of a performant CFR implementation, it is meant to be extremely generic.

* Our implementation is **also** designed to be extremely generic, compatible with all discrete games on OpenSpiel plus more.
* Their C++ implementation is **supposed to be** their performant version.
* OpenSpiel is also **widely used** by researchers... a faster library compatible with OpenSpiel's games can be useful.

>The games tested are extremely tiny. [...] It's not clear what a perfect information game is doing there. [...] `tic_tac_toe.py` dark variant of tic-tac-toe.

* These games are **widely used** to test the convergence speed of algorithms in the field of CFR [1].
* CFR can **absolutely** be used to solve perfect information games.
* In our tests, we **only** used `gpugt/games/open_spiel.py`.

>this method becomes more and more wasteful as the depth of the game increases.

We don't quite understand this. Our experiments indicate that our method scales well. Also, note that the growth of the depth is logarithmic w.r.t. the game size.

>Modifying the algorithm seems extremely expensive and cumbersome

Some modifications are trivial, as stressed in the paper. With that said, we acknowledge that in the paper as a limitation.

>not very GPU friendly and a lot of FLOPS are probably wasted

Again, empirical experiments show our method is still quite performant. We acknowledge the lack of further profiling in the paper.

>The paper does not include any exploitability results.

The convergence behavior of CFR is **already very well known** and we **do not propose** any new algorithm or variant. With that said, it can be added to the Appendix if the reviewer feels strongly about it.

>Why [...] CuPy?

Similar API as NumPy which allows us to swap between them to see performance with and without parallelization.

>How long does it take to setup the game tree?

* Our code performs a single game tree traversal, followed by filling in the matrices.
* It takes from 0.015 seconds (Kuhn poker) to 67.951 seconds (tic-tac-toe).
* The times can be added to the Appendix if the reviewer feels strongly about it.

>Were 32 or 64-bit floats used? Were tensor cores enabled?

* 64-bit floats were used.
* Tensor cores were not used.

>reason for making the nature player have infosets

* We found it to be more consistent. 
* It helped us derive the matrix/vector equations.

>it is not the product of average strategies that converges to the set of CCEs, but rather the average product.

Our Equation 8 is identical to Equation 4 in Zinkevich et al [2].

>The introduction should include the CFR theorem

Some CFR papers omit this. But, we can add it in our revision.

>what purpose Figure 1 serves in the paper [..] error bar

We see your point. You are right.

>why is alternating CFR hard to implement?

At the time of writing the paper, it seemed to require updating sparse matrix values mid-way. But, now, we understand that this can be implemented by creating separate masks for each actor during setup.

>This statement is not backed by anything in this paper

* We did not elaborate due to space constraints.
* Tammelin et al. [3] parallelized CFR by chunking the game tree with a trunk and many subtrees. Each subtree and trunk was assigned to a node that traversed the assigned tree.
* Our approach is simply a series of sparse matrix/vector operations, and distributing this is a well-studied problem in systems.

>the number of infosets for liars_dice seems to be wrong

* We considered nature's decision node to form a singleton infoset, hence the 16 infosets for Kuhn poker (instead of 12), 1093 for Leduc poker (instead of 936), et cetera.

We apologize for the long response... there was a lot to cover. We hope we addressed some of your concerns. Thank you for your stylistic suggestions.

[1] H. Xu et al., 2024. Dynamic Discounted Counterfactual Regret Minimization. URL: https://opnreview.net/forum?id=6PbvbLyqT6

[2] M. Zinkevich et al., 2007. Regret Minimization in Games with Incomplete Information. URL: https://poker.cs.ualberta.ca/publications/NIPS07-cfr.pdf

[3] O. Tammelin et al., 2015. Solving Heads-up Limit Texas Hold’em. URL: https://poker.cs.ualberta.ca/publications/2015-ijcai-cfrplus.pdf
Thank You for Your Very Detailed Review!
Yes
No ethics review needed.
N/A
Originality: The paper introduces a creative approach by reformulating Counterfactual Regret Minimization (CFR) as matrix operations suitable for GPU processing. This novel restructuring allows a highly parallelizable version of CFR, which has not been extensively explored in existing CFR literature.

Efficiency in Design: By avoiding recursive tree traversal, the implementation achieves substantial speed gains, especially in larger games, demonstrating an efficient design choice that effectively leverages GPU hardware.

Thorough Empirical Evaluation: The paper evaluates the new approach on a diverse set of games with varying complexity and size, rigorously benchmarking it against established OpenSpiel baselines in both Python and C++. This experimental breadth strengthens the validity of its claims about speedup and scalability.

Significant Potential for Scalability: The approach is well-suited for large-scale games, with experiments showing up to 352.5 times faster performance than OpenSpiel’s Python baseline and 22.2 times faster than its C++ counterpart, especially promising for future work on supercomputing platforms or even more extensive imperfect information games.
The paper presents a GPU-accelerated approach for Counterfactual Regret Minimization (CFR), a class of no-regret learning algorithms widely used in solving large-scale imperfect information games like poker. Traditionally, CFR algorithms rely on recursive tree traversal, which limits their efficiency. This work proposes a restructured CFR algorithm that converts the operations into a series of dense and sparse matrix and vector computations, making it highly parallelizable on GPUs at the cost of increased memory usage.

The study concludes that the proposed approach could serve as a foundational step for highly scalable CFR on supercomputing infrastructures, enabling faster solutions to complex game-theoretic problems.
Originality Limitations: Although innovative, the paper applies GPU parallelization to the vanilla CFR algorithm, which is somewhat limited in novelty given the existence of other CFR variants that incorporate modern enhancements (e.g., CFR+ or discounting techniques). A broader implementation encompassing these would increase the relevance of this work.

Limited Exploration of Advanced CFR Variants: The paper does not explore compatibility with modern CFR variants, such as sampling-based or discounting techniques, which are widely used in state-of-the-art game-solving algorithms. This omission reduces the approach’s applicability in advanced game AI contexts.

High Memory Requirements: The matrix-based reformulation, while speeding up calculations, results in high memory consumption, especially for larger games. This trade-off is not thoroughly analyzed or discussed, particularly regarding potential bottlenecks for memory-constrained systems, which limits practical usability.

Narrow Application Scope: The results indicate that this GPU implementation is unsuitable for small games, where it can actually perform worse than CPU implementations due to overhead. This could reduce its perceived impact and limits its practicality in domains that deal with a wide range of game sizes.
Yes
No ethics review needed.
- What was the inspiration for using CuPy?
- Why are there no exploitability results?
- How long does it take to setup the game tree?
- Were 32 or 64-bit floats used? Were tensor cores enabled?

- 022- The abstract is used in the introduction
- 037- GPU is defined twice
- 062- What is the philosophical reason for making the nature player have infosets? I find this very nonstandard
- 163- While CFR can find approximate coarse correlated equilibrium, the formulation presented in this paper does not. The reason is that it is not the product of average strategies that converges to the set of CCEs, but rather the average product.
- 175- The introduction should include the CFR theorem ($r^{(T)}(i_{+,j}\in\mathbf{I}_{+})$ is bounded by the sum of the local regrets)
- 201- Case in point in that this paper tries to inflate its notation, $l\in[1, D]\cap \mathbf{Z}$ is just weird.
- 292- Hadamard product was not defined. I would argue that it is not a common notation and should be defined explicitly.
- 397- It is not clear what purpose Figure 1 serves in the paper.
- 432- Why is there no error bar on the time measurements?
- 515- I understand that pruning the tree may be expensive (surely a very big downside) but why is alternating CFR hard to implement?
- 523- "Our approach is also much easier (and likely more efficient) to be run on supercomputers compared to previous methods" This statement is not backed by anything in this paper, see Weaknesses.
- 651- the number of infosets for liars_dice seems to be wrong, it should be 24576 not 24583 (or 12288 if we remove infosets with only one action).
This paper is interesting because it tries to solve two problems at the same time:
- APIs like [GraphBLAS](https://graphblas.org/) have successfully represented graph algorithms as a sequence of BLAS-like operations over semirings. This paper tries to do the same for CFR.
- It's not obvious how GPUs, the powerhouse of deep learning, can be used to accelerate game solving (other than calling neural networks). This paper tries to solve this gap.
This paper aims to frame the CFR algorithm as a sequence of matrix operations (Think GraphBlas).
Overall, this paper tries to aim for a best-of-both-worlds approach: low coding effort and high performance. 
Instead, it ends up with an exposition that is somehow less clear than the original CFR paper, benchmarks that don't inspire confidence, and the resulting algorithm seems to be not very flexible and requires major efforts to do the simplest changes like going from simultaneous to alternating variants of CFR.
 
- The open spiel codebase is not an example of a performant CFR implementation, it is meant to be extremely generic. Comparing with more reasonable implementations is necessary (for instance the Cepheus codebase for Leduc, there are other codebases as well).
- The games tested are extremely tiny. The largest game (tic tac toe) takes less than 3 seconds to traverse on a pure Python implementation and is a perfect information game. It's not clear what a perfect information game is doing there. The number of nodes in Appendix A is the number of infosets + terminals (i.e., there is only one node per infoset), and looking at the code, `tic_tac_toe.py` is not a dark variant of tic-tac-toe.
- The updates are batched and masked. Effectively, for each depth $d$, a (sparse) matrix multiply is done but only the output at depth $d$ is stored. As a matter of efficiency, this method becomes more and more wasteful as the depth of the game increases.
- Modifying the algorithm seems extremely expensive and cumbersome. (see  line 515)
- The computations presented here are probably not very GPU friendly and a lot of FLOPS are probably wasted (Yet this has not been analyzed).
- The paper does not include any exploitability results.
Yes
No ethics review needed.
see above
The acceleration seems quite significant as the author claimed.
This paper studies hardware acceleration for counterfactual regret minimization.
Well, it is unclear to me if this paper fits well for ICLR since there is no new algorithm / methodology / theory proposed. It may fit more to ML system venue. The benchmark selected (Game in OpenSpiel) is less known. I will suggest show improvements on more common benchmarks. I have to admit I do not have sufficient GPU hardware background to evaluate this paper.
Yes
No ethics review needed.
* What is the space complexity of the method?
* Can this method be used to accelerate the calculation of exploitability?

Minor Suggestions:

* It will help to improve clearity by adding a symbol table and an example figure.
* It will help to enhance readability by keeping the symbol descriptions consistent with CFR literatures, such as using $I$ for an information set and $h$ for a history node.
* The paper is well-written, and the notations are clearly defined.
* The GPU implementation significantly boosts the speed of the CFR algorithm, and the difference from the OpenSpiel implementation grows as the game size increases.
* The code is open-sourced, making it easy to apply to games in OpenSpiel.
This paper proposes a GPU implementation of the CFR algorithm. It stores the game tree structure in matrices and performs a series of matrix operations to compute reach probabilities, expected payoffs, and other relevant information level by level, thereby avoiding the costly tree traversal process. By leveraging GPU acceleration for these matrix operations, the approach significantly enhances CFR’s speed, albeit at the expense of increased memory usage.
This is not the first approach to implementing CFR on GPUs. For example, the thesis by Reis [1] and the report by Weng [2] also present GPU implementations of CFR. Additionally, DeepStack [3] [4] constructs the look-ahead tree and runs CFR on GPUs. These works and this paper use a similar approach, computing relevant information in CFR level by level and accelerating it with GPUs. However, the paper does not compare or discuss these related works.

[1] Reis J. A gpu implementation of counterfactual regret minimization. Master Thesis, University of Porto, 2015.

[2] Weng L. Counterfactual regret minimization on gpu.
https://cent.felk.cvut.cz/courses/GPU/archives/2020-2021/W/rudolja1/, 2021

[3] Moravčík M, Schmid M, Burch N, et al. Deepstack: Expert-level artificial intelligence in heads-
up no-limit poker. Science, 2017, 356(6337): 508-513.

[4] Schmid M. DeepStack for Leduc Hold'em. https://github.com/lifrordi/DeepStack-Leduc, 2017
Yes
No ethics review needed.
* Is OpenSpiel’s implementation paralleled? I think this can have a lot of differences in the performance. Only comparing with the benchmark implementation can be limited.
* You showed there is a trade-off for memory efficiency and computation time. However I don’t see there are any reasons on this if we store every sparse matrix within the corresponding format. Can you further explain this?
* Leveraging GPUs to improve the computation for game solving is still under-explored and this manuscript has a solid step towards it.
This manuscript discussed about how to leverage GPU’s computation power on sparse matrix multiplication to improve the computation speed for large scale games.
* This is a more engineering-driven paper without lots of scientific contribution.
* I’m not quite sure about where the benefit is from. See the questions.
We implemented CFR as dense and sparse matrix and vector operations, achieving orders of magnitude speedups on GPUs compared to OpenSpiel's baselines.
@inproceedings{
anonymous2024gpuaccelerated,
title={{GPU}-Accelerated Counterfactual Regret Minimization},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=dWsBrgaNzU},
note={under review}
}
Counterfactual regret minimization is a family of algorithms of no-regret learning dynamics capable of solving large-scale imperfect information games. We propose implementing this algorithm as a series of dense and sparse matrix and vector operations, thereby making it highly parallelizable for a graphical processing unit, at a cost of higher memory usage. Our experiments show that our implementation performs up to about 352.5 times faster than OpenSpiel's Python implementation and up to about 22.2 times faster than OpenSpiel's C++ implementation and the speedup becomes more pronounced as the size of the game being solved grows.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
counterfactual regret minimization extensive-form games graphical processing units imperfect information games Nash equilibrium
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/5f56348598a6a038b18738dcb97c1c94becb7c03.pdf
other topics in machine learning (i.e., none of the above)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/5645a2d161d306fa0c8e2efe849629e7ceacbb5f.zip
GPU-Accelerated Counterfactual Regret Minimization
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission