GPU-Accelerated Counterfactual Regret Minimization

Authors: Juho Kim
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: counterfactual regret minimization, extensive-form games, graphical processing units, imperfect information games, Nash equilibrium

Abstract:
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 401.2 times faster than OpenSpiel's Python implementation and, on an expanded set of games, up to about 203.6 times faster than OpenSpiel's C++ implementation and the speedup becomes more pronounced as the size of the game being solved grows.

Decision: reject
Reviewer scores: 5, 3, 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1729975765695

thread_type:
official_review

<thread_object>
creator: reviewer_hul5

<content>
summary:
This manuscript discussed about how to leverage GPU’s computation power on sparse matrix multiplication to improve the computation speed for large scale games.

strengths:
* Leveraging GPUs to improve the computation for game solving is still under-explored and this manuscript has a solid step towards it.

weaknesses:
* 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.

questions:
* 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730120247457

thread_type:
official_review

<thread_object>
creator: reviewer_vhx6

<content>
summary:
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.

strengths:
* 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.

weaknesses:
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

questions:
* 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730670606534

thread_type:
official_review

<thread_object>
creator: reviewer_ex7u

<content>
summary:
This paper studies hardware acceleration for counterfactual regret minimization.

strengths:
The acceleration seems quite significant as the author claimed.

weaknesses:
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.

questions:
see above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681796501

thread_type:
official_review

<thread_object>
creator: reviewer_dyt9

<content>
summary:
This paper aims to frame the CFR algorithm as a sequence of matrix operations (Think GraphBlas).

strengths:
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.

weaknesses:
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.

questions:
- 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).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730697263563

thread_type:
official_review

<thread_object>
creator: reviewer_zsia

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1731922453695

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common Responses and Changes in our Revision

comment:
We would like to thank all the reviewers for their reviews and take this opportunity to give generalized comments and summarize the revisions we made to our manuscript.

We are happy that most reviewers agree that the degree of GPU acceleration in our work is "substantial"/"significant"/"solid" (Reviewers zSia, eX7u, Vhx6, and hUL5). Even Reviewer dyt9 who took an issue with our benchmark (more on this later) at least found our paper "interesting". New experimental results (at the request of Reviewer dyt9) for games orders of magnitudes larger than the ones previously tested show an even greater speedup of up to 114.2 times faster than OpenSpiel's baselines.

Reviewers hUL5 and eX7u expressed sentiment that the "engineering-driven"/"system"s nature of our contribution does not fit well for ICLR. We would like to point out that ICLR has published numerous systems papers before and "infrastructure, software libraries, hardware, etc." is one of the relevant subject areas explicitly mentioned by ICLR.

Reviewer Vhx6 brought up that GPUs have been leveraged before for CFR [1-2] or CFR-inspired algorithms like DeepStack [3]. In our new revision and the discussion chain, we argue how our transformation of CFR into linear algebra operations (for GPU usage) greatly differs from the works the reviewer cited. Note that works by Reis and Rudolf the reviewer emphasizes are not peer-reviewed and/or self-published.

Reviewers dyt9 and eX7u questioned if the use of OpenSpiel's games and baselines for benchmarks was sufficient. We argue that it is, as selections of its games (that we also test on) have been used by a wide variety of past CFR/imperfect-information game AI papers [4-5], and our solution is designed to be as generic as OpenSpiel's. In general, there is a lack of good benchmarks for CFR performance. Our new revision contains experimental results from games of sizes orders of magnitudes larger (at the request of Reviewer dyt9 who felt the games were not large enough).

Reviewer dyt9 pointed out the lack of exploitability results. We argued that the reviewer is conflating the general expectations in CFR papers with what is relevant to our specific contribution. With that said, we calculated exploitabilities (as sanity tests) and added the log-log plots in our latest revision (Appendix A). During the process, we found a bug in our code and formulation when it came to average strategy calculation which we fixed in the new revision (and supplementary).

We also incorporated several stylistic suggestions and answers to reviewers' questions. Again, we would like to thank the reviewers for pointing them out. Overall, we believe our paper has been significantly strengthened following this review process.

With that aside, we provided detailed responses to all of the reviewers' concerns and questions. We hope to have addressed them adequately.

[1] Reis J. A gpu implementation of counterfactual regret minimization. Master Thesis, University of Porto, 2015. URL: https://repositorio-aberto.up.pt/handle/10216/83517

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

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

[4] Perolat J, et al. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. International Conference on Machine Learning, 2021.

[5] McAleer S., et al. ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret. The Eleventh International Conference on Learning Representations, 2023. URL: https://web.mit.edu/~gfarina/www/2023/escher_iclr23/2206.04122.pdf
</content>
</thread_object>

</thread>
<thread>
creation date:
1732687705360

thread_type:
official_comment

<thread_object>
creator: area_chair_i3jj

<content>
comment:
Dear all,

First of all, thanks to everyone for engaging in a polite discussion about the merits of the paper.

I have noticed there have been many messages exchanged, so I thought it would be productive to try to summarize the most contested points and focus the discussion further for the next few days before the (extended) author discussion closes.

First, though, let me get a few things out of the way:
- to Reviewers hUL5 and eX7u: I agree with the authors that engineering work does fit under the umbrella of welcomed contributions at ICLR
- I agree with the authors that (in my experience) "there is a lack of good benchmarks for CFR performance."
- I agree with the authors that "authors may be excused for not knowing about papers not published in peer-reviewed conference proceedings or journals" as per reviewing guidelines.

Overall, it seems that one of the main points of disagreement between Reviewer dyt9 and the authors is about whether comparison against OpenSpiel is meaningful. As the reviewers pointed out, OpenSpiel is one de-facto standard for entry-level game-solving primitives and a well-established library. On the other hand, I think that Reviewer dyt9 has a point that comparing a sophisticated GPU implementation against OpenSpiel's "vanilla" Python implementation is apples-to-oranges and not necessarily informative. I agree with Reviewer dyt9 that the implementations of CFR that ended up used in breakthrough results were much more tuned than the Python implementation of OpenSpiel. That being said, most of those implementations are not publicly available (or not general purpose), and the authors' contribution could help people today. So, it seems that the major point of disagreement is not about whether the author's contribution is welcome (it is!), but rather whether the evaluation of said contribution is thorough and convincing. In this regard, the following points have been brought up:
- The games used in the benchmarks might be too small. The authors seem to have added at least one game to address this.
- Exploitability plots were missing. This was a good suggestion by Reviewer dyt9, which helped the authors catch a minor bug.
- OpenSpiel might be spending the majority of time constructing internal bookkeeping that's not directly correlated with running CFR iterations.
- The authors' implementation is not yet capable of implementing alternating CFR.
- Certain low-hanging benchmarks have been left out (such as turning on tensor cores, or ablating the choice of floating point format).
- Reviewers Vhx6 and hU5 seemed to believe the technical novelty is insufficient. However, some of the references they brought up seem to refer to unpublished work with no publicly available code, so I think it is unfair to hold it against the authors. 

As things stand, from my point of view, the main merit of the authors' contribution is that it would provide the community with an open-source implementation of CFR that is significantly faster than the default Python one in OpenSpiel, while retaining compatibility with OpenSpiel games. That being said, I think that the reviewers have brought up several important points. For example, the inability to solve Liar's Dice with two dice and four faces each seems a bit of a letdown, given that the game is not that large. In addition, I agree that certain ablations might make evaluating this ML systems paper more thorough. 

If I may add on top of the reviewers, one point I did not fully understand about the implementation (but I might have completely missed) is whether CFR is implemented as an algorithm on the game tree, or on each player's sequence-form polytope. The latter can be significantly smaller, and the benefit is important in games such as poker that admit fast gradient and best-response computation (in time proportional to the number of information sets as opposed to nodes in the game tree; e.g., Johanson et al. 2011). Implementations based on the sequence form are, in my experience, significantly faster and easier to parallelize.

That being said, I want to thank again both the authors and the reviewers for their vigorous engagement in this paper. While not all parties might be in agreement on all the points, it is clear that significant effort has been put into the lengthy back-and-forth discussion.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Before going into details, I want to thank again the reviewers and the authors for engaging so actively on this paper. 

My position on this paper was summarized in detail in my post during the response period. To restate the crux of it, from my point of view, the main merit of the authors' contribution is that it would provide the community with an open-source implementation of CFR that is significantly faster than the default Python one in OpenSpiel, while retaining compatibility with OpenSpiel games. Furthermore, I think that the authors have addressed many of the points that the reviewers brought up.

After the end of the response period, I contacted Reviewer dyt9 to try to understand better their position, and we had an in-depth conversation. Overall, I think I made progress in convincing them that the community would find the contribution useful. However, they still seemed not enthusiastic about the paper. From my understanding, their point of view is that nobody that really needs to squeeze performance out of a game solver would use or compare against OpenSpiel's implementations. And on top, they were not in love with the graph-based approach used in this paper to implement CFR, and thought that a level-based approach would do better. Finally, they didn't love the fact that alternation was not supported.

Overall, while I like the paper, for me to override five reviewers and push this paper through seems extreme. The review panel included knowledgeable people on extensive-form games, and I know that Reviewer dyt9 has hands-on experience with implementing GPU-accelerated first-order optimization solvers. 

As a concrete suggestion for future iterations, I would recommend implementing alternation, both as a way to dismiss concerns that the approach used in the paper is too restrictive, and also since alternation usually performs well in extensive-form games. It might also help to discuss different design that have been considered and why they were discarded; such a discussion could also help future implementations by other groups as well.