- Rating
- 4(+1)
- Confidence
- 4(+1)
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
This paper introduces PDRM$^{+}^{+}$ algorithms that includes CFR$^{+}^{+}^{+}$ , and PDCFR$^{+}$ as special cases. It proves last-iterate convergence to the unique equilibrium in perturbed regularized extensive-form games for any step size and initialization, and further establishes constant regret and an approximation of the original game. Experiments validate the discount threshold, the regret plateau, and the strong practical performance of RT-PCFR$^{+}$.
Critical strengths
-
The motivation is clear. While methods such as PCFR+ and DCFR+ are more powerful than CFR+, theoretical guarantees for the RT technique were previously established only for CFR+. This work bridges that gap.
-
The experimental results are strong and comprehensive. The paper provides a detailed comparison of the proposed method against various state-of-the-art existing approaches across a range of different games, demonstrating that RT-PCFR+ holds a clear advantage in terms of convergence performance at the last iterate.
-
The paper makes a substantial theoretical contribution by bridging the theoretical gap regarding the last-iterate convergence of various CFR variants in RT technique.
-
The paper is written clearly and is relatively easy to follow.
Critical weaknesses
-
Restrictive assumptions in the constant-discount result. Proposition 1 requires both invertibility of the projected Jacobian and an additional condition excluding directions that leave the opponent’s regret unchanged. These assumptions restrict the result’s applicability, and the manuscript does not establish whether they are necessary or already implied by positive regularization.
-
Incomplete justification for the unperturbed matrix-game experiments. Theorem 1 assumes , whereas the normal-form experiments omit perturbation, with Appendix C stating that “ plays no role in normal-form games”. This statement does not establish that the convergence theorem remains valid at ; an explicit extension is needed to connect these experiments to the fixed-game theory.
-
The text contains several assertions that lack sufficient evidence. For instance, the claim that “the published RTCFR+ configuration is optimal” (lines 370–371) is not supported by the sweep results presented. Furthermore, the statement that “discounting provides no benefit” (lines 420–421) contradicts the data in Table 1. For example, in the games of Goofspiel(5) and Liar’s Dice(5,6), RT-DCFR+ performs better than RTCFR+. These claims require a more precise interpretation, one that accounts for specific methods and game types.
Questions for authors
-
Can you add a discussion about apply the RT-PCFR+ method to larger scale games and attempt to combine it with techniques such as CFR AI-infra techniques [1, 2], abstraction [3, 4, 5], pruning [6] , depth-limited solving [7, 8], etc?
-
Why does RT-PCFR+ perform worse than RTCFR+ in three of all games?
-
How does the wall-clock computational overhead of RT-PCFR+ compare to that of RT-CFR+?
[1] Real-Time Parallel Counterfactual Regret Minimization
[2] GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay
[3] RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning
[4] Effective, Efficient, and General Information Abstraction for Imperfect-Information Extensive-Form Games
[5] Abstraction Agent
[6] Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games
[7] Depth-Limited Solving for Imperfect-Information Games
[8] Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
5 comments
W3. The text contains several assertions that lack sufficient evidence.
(a) "the published RTCFR+ configuration is optimal". We apologize that our wording was easy to misread; we did not intend this claim. The submission states the opposite on page 7, lines 367-368 ("they are tuned for no variant: on Leduc, for instance, γ_0 = 10^-2 improves RTCFR+ by five orders of magnitude") and in the appendix, page 18, lines 940-945 ("The published values ... are not optimal for RTCFR+ ... it is not a tuned comparison"). Our reading of the sweep is the same as the reviewer's: the published configuration is not optimal, and we keep it for all four variants so that Table 1 is directly comparable to Meng et al. (2025). In the revision, that paragraph says this explicitly (page 8, lines 417-419).
(b) "discounting provides no benefit". In the submitted text, page 8, lines 420-422 state: "Discounting has mixed effects: without prediction it beats RTCFR+ on eight of the nine games (Goofspiel(5) by 29x) and loses on Leduc; with prediction it helps only on Liar's Dice(5,6)", which aligns with the reviewer's observation. Following the reviewer's helpful suggestion, we revised page 9, lines 477-480 to report the exact breakdown per method and per game. Without prediction (RT-DCFR+ vs RTCFR+), discounting is better on six games (Goofspiel(4), Goofspiel(5), Liar's Dice(5), Liar's Dice(6), Battleship(2x2), Battleship(2x3)), both are at the roundoff floor on Kuhn and Liar's Dice(4), and it is worse on Leduc. With prediction (RT-PDCFR+ vs RT-PCFR+), discounting is better on Liar's Dice(5) and Liar's Dice(6), both are at the floor on Goofspiel(4) and Liar's Dice(4), and it is worse on the remaining five.
Q1. Can you add a discussion about apply the RT-PCFR+ method to larger scale games and attempt to combine it with techniques such as CFR AI-infra techniques [1, 2], abstraction [3, 4, 5], pruning [6] , depth-limited solving [7, 8], etc?
New experiments. Following the reviewer's suggestion, we evaluated RT-PCFR+ on two games beyond Table 1 under alternating and simultaneous updates: Goofspiel(6) (about 34k information sets) and Liar's Dice with 2 dice of 4 sides (about 393k information sets, roughly five times Battleship(2x3), the largest game in the submission). The results are in the table below and in the revised paper at Table 12 on page 24; discussion on page 23, lines 1235-1241. Conclusion: the pattern of the nine benchmark games carries over; RT-PCFR+ is the best RT variant on Goofspiel(6), and on the Liar's Dice game RT-CFR+ leads under alternation while RT-PCFR+ leads under simultaneous updates. In detail, on Goofspiel(6), after 20,000 iterations RT-PCFR+ ends at 6.75e-06, the best of the four RT variants (RT-CFR+: 2.55e-05). On the Liar's Dice game, after 5,000 iterations under alternating updates RT-CFR+ ends at 5.87e-05 and RT-PCFR+ at 3.91e-03; under simultaneous updates the order reverses (see Q2).
Goofspiel(6), 20,000 iterations; rows without a tag use alternating updates.
| algorithm | final expl. | iterations to 1e-3 |
|---|---|---|
| RT-CFR+ | 2.55e-05 | 4400 |
| RT-PCFR+ | 6.75e-06 | 2400 |
| RT-DCFR+ | 1.40e-05 | 3800 |
| RT-PDCFR+ | 6.85e-05 | 2600 |
| RT-CFR+ (simultaneous) | 2.43e-01 | -- |
| RT-PCFR+ (simultaneous) | 7.80e-03 | -- |
| RT-DCFR+ (simultaneous) | 3.22e-01 | -- |
| RT-PDCFR+ (simultaneous) | 7.69e-03 | -- |
Liar's Dice (2 dice, 4 sides), 5,000 iterations; rows without a tag use alternating updates.
| algorithm | final expl. | iterations to 1e-3 |
|---|---|---|
| RT-CFR+ | 5.87e-05 | 2350 |
| RT-PCFR+ | 3.91e-03 | -- |
| RT-DCFR+ | 2.70e-04 | 2750 |
| RT-PDCFR+ | 2.05e-02 | -- |
| RT-CFR+ (simultaneous) | 1.94e-02 | -- |
| RT-PCFR+ (simultaneous) | 1.13e-03 | 4800 |
| RT-DCFR+ (simultaneous) | 2.08e-02 | -- |
| RT-PDCFR+ (simultaneous) | 7.65e-04 | 3350 |
On combining RT-PCFR+ with these techniques, we added a discussion that cites all of [1]-[8] (page 3, lines 130-138). PDRM+ changes only the local regret update at each information set, and the RT protocol only adds a local regularization term to the utilities, so the tree traversal is untouched. Consequently, parallel and GPU traversal [1, 2] applies unchanged, and with a per-iteration cost ratio of 0.98x to 1.06x (Q3) their speedups carry over. For abstraction [3, 4, 5], an abstract game is itself an extensive-form game, so our guarantees hold for it verbatim. For depth-limited solving and search [7, 8], a last-iterate method returns one strategy without averaging, which is convenient when subgames are re-solved online. Finally, for pruning [6], how pruning interacts with the perturbation γ is an open question that we now state.
Q2. Why does RT-PCFR+ perform worse than RTCFR+ in three of all games?
Thank you for this question. This behavior is an effect of alternating updates, not of prediction itself. Table 1 uses alternating updates (the practical default), whereas our theory covers simultaneous updates.
New experiments. Following the reviewer's question, we ran simultaneous-update controls on the two larger games and collected the comparison under both update orders on Leduc and Liar's Dice(5,6) in a new table, including a 3x3 grid of (μ, T_u); the results are in the revised paper at Table 8 on page 22, discussed on page 21, line 1133 to page 22, line 1139, and Table 12 on page 24. Conclusion: the lead of RTCFR+ is tied to alternating updates, not to prediction; under simultaneous updates the order reverses on all three games and on the larger Liar's Dice game. In detail, under simultaneous updates RTCFR+ vs RT-PCFR+ gives 2.46e-01 vs 4.85e-02 on Leduc, 5.36e-02 vs 6.00e-06 on Liar's Dice(5), and 2.47e-02 vs 7.55e-04 on Liar's Dice(6). Over a 3x3 grid of (μ, T_u) under simultaneous updates, RT-PCFR+ is ahead on 9 of 9 settings on Leduc, 6 of 9 on Liar's Dice(5), and 5 of 9 on Liar's Dice(6). On Liar's Dice with 2 dice of 4 sides (the largest game we could run), the same reversal appears: alternating gives 5.87e-05 (RTCFR+) vs 3.91e-03 (RT-PCFR+), while simultaneous gives 1.94e-02 (RTCFR+) vs 1.13e-03 (RT-PCFR+); see the table under Q1.
We believe the reason is that alternation already supplies a form of lookahead to the non-predictive update (the second player responds to the first player's fresh strategy), and on these games it helps RM+ more than prediction does. Figure 1 shows the same in the fixed game, where under alternating updates RM+ often locks onto the equilibrium exactly. We state this in the main text (page 9, lines 472-477) and do not claim that RT-PCFR+ dominates under alternation.
Q3. How does the wall-clock computational overhead of RT-PCFR+ compare to that of RT-CFR+?
New experiment. Following the reviewer's question, we measured the time per iteration for all four RT variants on all nine games, in a single serial process without exploitability evaluation, median of 3 runs. The results are in the table below and in the revised paper at Table 13 on page 24; discussion on page 24, lines 1262-1265. Conclusion: RT-PCFR+ costs between 0.98x and 1.06x of RT-CFR+ per iteration. Prediction adds one vector addition per information set, whereas the tree traversal that dominates the cost is identical. The overhead shrinks with game size: 1.05x on Kuhn, 1.00x on Liar's Dice(6), and 0.98x on Battleship(2x3), the largest game in Table 1. For completeness, the discounted variants cost at most 1.26x (RT-PDCFR+ on Battleship(2x2)).
Milliseconds per iteration (ratio to RT-CFR+ in parentheses).
| game | RT-CFR+ ms/iter | RT-PCFR+ ms/iter | RT-DCFR+ ms/iter | RT-PDCFR+ ms/iter |
|---|---|---|---|---|
| Kuhn | 0.014 (1.00x) | 0.015 (1.05x) | 0.016 (1.13x) | 0.017 (1.19x) |
| Leduc | 1.845 (1.00x) | 1.920 (1.04x) | 2.020 (1.09x) | 2.092 (1.13x) |
| Goofspiel(4) | 0.224 (1.00x) | 0.234 (1.05x) | 0.251 (1.12x) | 0.262 (1.17x) |
| Liar's Dice(4) | 1.737 (1.00x) | 1.798 (1.03x) | 1.913 (1.10x) | 2.001 (1.15x) |
| Goofspiel(5) | 7.058 (1.00x) | 7.342 (1.04x) | 7.909 (1.12x) | 8.395 (1.19x) |
| Battleship(2x2) | 6.858 (1.00x) | 7.294 (1.06x) | 8.146 (1.19x) | 8.614 (1.26x) |
| Liar's Dice(5) | 26.191 (1.00x) | 26.487 (1.01x) | 27.629 (1.05x) | 28.309 (1.08x) |
| Liar's Dice(6) | 212.935 (1.00x) | 213.226 (1.00x) | 219.353 (1.03x) | 221.621 (1.04x) |
| Battleship(2x3) | 569.736 (1.00x) | 557.325 (0.98x) | 604.589 (1.06x) | 609.713 (1.07x) |
We thank you again for your support and constructive suggestions, which improved the paper. We are glad to discuss anything further.
We thank you for your positive, encouraging evaluation, and for recognizing our clear writing, clear motivation in closing the gap where reward-transformation guarantees existed only for CFR+, substantial theoretical contribution, and strong, comprehensive experiments. Below, we answer each weakness and question.
We thank the reviewer for raising this point: asking whether the condition follows from positive regularization is the right question, and the answer is yes. We now prove that invertibility of the tangent-space map ΠJ holds for every μ>0 (Lemma 3, page 18, lines 928-949), so the revised Proposition 1 (page 6, lines 317-321) carries no nondegeneracy assumption. Specifically, if ΠJδ=0, then the regularized payoff operator M=[μI, A; −Aᵀ, μI] (blocks) satisfies ⟨y, My⟩=0 for the rescaled direction y, and since the cross terms cancel by the zero-sum structure, ⟨y, My⟩=μ‖y‖², so y=0.
We also wish to clarify that in the submitted version, Proposition 1 (page 6, lines 296-300) assumed only that ΠJ is invertible; there was no second condition on the opponent's regret, and Appendix B (page 16, lines 815-816) stated "No condition on the cross blocks is needed". We apologize if our wording there suggested an extra requirement. With Lemma 3, page 18, lines 928-949 in place, what remains in Proposition 1 is scope, not assumption: a normal-form game, a fully mixed equilibrium, and p=0.
We apologize that the extension was easy to miss: it appears in the appendix, and the main text cites it only in passing (page 8, line 427 of the submission: "γ = 0 (Remark 2)"). The explicit extension requested is provided in Remark 2 (page 15, lines 756-761 of the submission), which states that for a normal-form game (H=1), Theorems 1 and 2 hold with γ=0. Remark 2 goes through each place where γ enters the proof: inequality (L-E) holds with constant 1 because sequence-form and behavioral strategies coincide; the factor ζ_I=1-α_I equals 1; inequality (L-D) holds directly, with the explicit constant C_1 given there; and uniqueness of the equilibrium follows from μ>0 alone. We could not find the phrase "plays no role" in the manuscript and believe the intended passage is this remark. In the revision, the normal-form paragraph of Section 6 states the extension explicitly and points to Remark 2 (page 9, line 485 to page 10, line 514; Remark 2 itself is on page 17, lines 868-873).
New experiment. Following the reviewer's suggestion, we reran the normal-form table with γ>0 (γ_0=10^-3, halved every T_u iterations, as in the extensive-form protocol). The results are in the table below and in the revised paper at Table 14 on page 24; discussion on page 24, lines 1280-1284. Conclusion: the results are unchanged; every fraction moves by at most 0.01, and RT-PCFR+ still reaches the roundoff floor on the Cai et al. game.
Simultaneous updates, μ = 1e-2, 20,000 iterations.