acceptodds
Under review as a conference paper at ICLR 2027

Parameter-Free Last-Iterate Convergence of Optimistic and Discounted Counterfactual Regret Minimization

Abstract

Counterfactual regret minimization (CFR) with regret matching local minimizers is the standard way to solve two-player zero-sum games in extensive form (EFGs), but only its average strategy is guaranteed to converge. The reward-transformation framework restores them by solving a sequence of auxiliary games in which every action keeps probability at least and a quadratic penalty pulls toward a reference strategy; RTCFR showed that plain CFR converges in the last iterate on every such fixed game for any step size and any initialization. The variants that are actually used, namely predictive CFR and the discounted variants DCFR and PDCFR, had no such guarantee. We study one family of local minimizers, predictive discounted regret matching, that contains all of them. We show that the strategy sequence of any member depends on the step size and the initialization only through their ratio, and use this invariance to prove that in every perturbed regularized EFG the last iterate converges to the unique equilibrium for any step size and any initialization, provided the total discount is finite. The DCFR schedule satisfies the condition exactly when its exponent exceeds one, and without prediction a constant discount cannot converge on nondegenerate matrix games unless it hits the equilibrium in finite time. Every instance has constant regret in the perturbed regularized game, hence an average-iterate rate there, and the last iterate is an -equilibrium of the original game. Experiments confirm the summability condition and the constant-discount obstruction, show the regret plateau the constant-regret bound predicts, and show that optimism turns the slow last-iterate convergence of regret matching into fast convergence: with the published RTCFR hyperparameters, RT-PCFR ends below on most benchmark EFGs and converges on a matrix game where both plain PCFR and RTCFR fail. Parameter-freeness is the property the reward-transformation framework needs, and it survives both optimism and discounting: within each perturbed regularized game the practical variants have the same guarantee as CFR, with no retuning of step size or initialization.

Primary area:
reinforcement learning
Keywords:
Imperfect Information Games, Counterfactual Regret Minimization, last-iterate convergence

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_BUTBOpenReview ↗
Rating
4(+1)
Confidence
4(+1)
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper introduces PDRM$^{+},aunifiedfamilyofpredictivediscountedregretmatching, a unified family of predictive discounted regret matching^{+}$ algorithms that includes CFR$^{+},PCFR, PCFR^{+},DCFR, DCFR^{+}$ , 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 O(μ+γ)O(\mu+\gamma) approximation of the original game. Experiments validate the discount threshold, the regret plateau, and the strong practical performance of RT-PCFR$^{+}$.

Critical strengths
  1. 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.

  2. 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.

  3. The paper makes a substantial theoretical contribution by bridging the theoretical gap regarding the last-iterate convergence of various CFR variants in RT technique.

  4. The paper is written clearly and is relatively easy to follow.

Critical weaknesses
  1. 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.

  2. Incomplete justification for the unperturbed matrix-game experiments. Theorem 1 assumes γ>0\gamma>0, whereas the normal-form experiments omit perturbation, with Appendix C stating that “γ\gamma plays no role in normal-form games”. This statement does not establish that the convergence theorem remains valid at γ=0\gamma=0; an explicit extension is needed to connect these experiments to the fixed-game theory.

  3. 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
  1. 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?

  2. Why does RT-PCFR+ perform worse than RTCFR+ in three of all games?

  3. 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

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.


W1. 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.

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.

W2. Incomplete justification for the unperturbed matrix-game experiments. Theorem 1 assumes γ>0\gamma >0, 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 γ=0\gamma=0; an explicit extension is needed to connect these experiments to the fixed-game theory.

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.

perturbationquantityRT-CFR+RT-PCFR+RT-PDCFR+
γ = 0Cai game, final expl.3.04e-016.88e-152.59e-02
γ = 0random 3x3, fraction ≤ 1e-60.340.990.89
γ = 0random 4x4, fraction ≤ 1e-60.130.950.89
γ_0 = 1e-3, halved every T_uCai game, final expl.2.30e-014.94e-151.14e-02
γ_0 = 1e-3, halved every T_urandom 3x3, fraction ≤ 1e-60.340.990.90
γ_0 = 1e-3, halved every T_urandom 4x4, fraction ≤ 1e-60.130.950.90

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.

algorithmfinal expl.iterations to 1e-3
RT-CFR+2.55e-054400
RT-PCFR+6.75e-062400
RT-DCFR+1.40e-053800
RT-PDCFR+6.85e-052600
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.

algorithmfinal expl.iterations to 1e-3
RT-CFR+5.87e-052350
RT-PCFR+3.91e-03--
RT-DCFR+2.70e-042750
RT-PDCFR+2.05e-02--
RT-CFR+ (simultaneous)1.94e-02--
RT-PCFR+ (simultaneous)1.13e-034800
RT-DCFR+ (simultaneous)2.08e-02--
RT-PDCFR+ (simultaneous)7.65e-043350

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).

gameRT-CFR+ ms/iterRT-PCFR+ ms/iterRT-DCFR+ ms/iterRT-PDCFR+ ms/iter
Kuhn0.014 (1.00x)0.015 (1.05x)0.016 (1.13x)0.017 (1.19x)
Leduc1.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.

Reviewer_DAC2OpenReview ↗
Rating
4
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper aims to show that various CFR+ methods converge in the last-iterate to Nash equilibrium in 2P0S games under reward transformation (RT) (perturbing and regularizing games).

Under the RT framework, recent work (Meng, et al. (2025a)) recently proved that CFR+ has last-iterate convergence. However, the variants PCFR+, DCFR+, PDCFR+ had no such guarantees. This paper proves last-iterate convergence there (under some weak assumptions).

I did not check the math.

Critical strengths

This paper clearly resolves an open problem: the last-iterate convergence of these methods using perturbed regularized EFGs.

Critical weaknesses

None that I can see.

Questions for authors

N/A

1 comment

We thank you for your positive evaluation and for stating our contribution with such clarity, particularly in recognizing that the paper clearly resolves an open problem.

Our general response lists the revisions to the paper, including a new lemma that removes the assumption of Proposition 1, the experiments other reviewers asked for, and a readability pass, and we are happy to answer any question you may have.

Reviewer_BbvBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper discusses the effect of discounting and optimism on convergence of regret matching plus CFR in regularized and perturbed games. The authors show scale invariance for initialization of the algorithm’s parameters. Main result is constant regret and last-iterate convergence in perturbed regularized game under mild assumptions on discounting. The experiments compare optimistic and discounting variants in both average- and last-iterate case on standard sequential games and few matrix games, with convergence following the theory up to machine precision.

Critical strengths

The last-iterate convergence of discounted regret minimizers fills the gap in the reward transformation framework research, as it is one of the widely used regret minimizers for solving sequential games with CFR-style algorithms. Scale invariance is beneficial for implementation and running the algorithms.

Critical weaknesses

Some experiments tables and plots are badly composed or are not appropriate: Figure 1 Kuhn Poker plot abruptly stops at 20k iterations; Table 1 compares L2-regularized RT-CFR+ with entropy-regularized DOMD, Reg-CFR, and MMD, though all of the methods support euclidean regularization.

Questions for authors

Original Discounted CFR uses regret matching that discounts positive and negative cumulative regrets separately. Do you think it will converge last-iterate in perturbed regularized games?

2 comments

We thank you for your positive evaluation. We appreciate your noting that last-iterate convergence of discounted regret minimizers fills a gap in reward-transformation research, and that scale invariance is useful for implementing and running the algorithms.


Weakness: Some experiments tables and plots are badly composed or are not appropriate: Figure 1 Kuhn Poker plot abruptly stops at 20k iterations; Table 1 compares L2-regularized RT-CFR+ with entropy-regularized DOMD, Reg-CFR, and MMD, though all of the methods support euclidean regularization.

(Figure 1) New run. The Kuhn runs had been logged for 20,000 iterations only, whereas the other games ran for 50,000. Following the reviewer's comment, we reran Kuhn for 50,000 iterations and regenerated the figure; it is in the revised paper at Figure 1 on page 7. Conclusion: all panels now share the same horizon, and under simultaneous updates all four instances agree with the reference to within 1e-14 at 50,000 iterations.

(Table 1) New experiment. This is a fair point. Following the reviewer's comment, we ran Reg-CFR, DOMD, and MMD with the Euclidean regularizer, at LiteEFG defaults and tuned over the same grid as the entropy versions, on all nine games. The results are in the table below and in the revised paper at Table 11 on page 23; discussion on page 22, lines 1179-1186. Conclusion: the Euclidean baselines are stronger than the entropy versions and reach the roundoff floor on four games after per-game tuning; RT-PCFR+ remains ahead of the best tuned baseline on four games; and tuned Euclidean DOMD is ahead of RT-PCFR+ on Liar's Dice(6). In detail, with per-game tuning, Euclidean DOMD reaches the roundoff floor on Kuhn, Goofspiel(4), and Liar's Dice(4), and Euclidean MMD reaches 2.94e-15 on Battleship(2x2); RT-PCFR+ is at the floor on the same four games. RT-PCFR+ remains ahead of the best baseline on four games: Goofspiel(5) (2.58e-16 vs 1.16e-03), Battleship(2x3) (below 1e-15 vs 1.65e-03), Leduc (1.20e-06 vs 6.60e-04), and Liar's Dice(5) (2.86e-05 vs 8.27e-05). On Liar's Dice(6), tuned Euclidean DOMD (2.77e-04) is ahead of RT-PCFR+ (6.24e-03) and level with RTCFR+ (2.81e-04). The baselines need a different step size on each game (the best Euclidean DOMD step ranges from 0.1 to 2), whereas every RT variant uses one untuned configuration. We replaced the sentence claiming that tuned baselines stay above RT-PCFR+ on every game with this account (page 8, lines 424-431).

Final last-iterate exploitability after 20,000 iterations (ent = entropy, Euc = Euclidean; tuned = best over the grid, per game).

gameReg-CFR ent defaultReg-CFR ent tunedReg-CFR Euc defaultReg-CFR Euc tunedDOMD ent defaultDOMD ent tunedDOMD Euc defaultDOMD Euc tunedMMD ent defaultMMD ent tunedMMD Euc defaultMMD Euc tunedRT-PCFR+RT-CFR+
Kuhn2.07e-013.35e-049.72e-023.33e-049.81e-026.81e-101.69e-041.25e-161.44e-027.18e-035.70e-035.62e-035.55e-173.26e-15
Leduc4.09e+007.83e-023.59e+003.07e-031.06e+006.85e-027.67e-026.60e-043.75e-023.75e-022.65e-012.42e-011.20e-062.09e-08
Goofspiel(4)4.62e-012.76e-035.69e-022.50e-033.24e-052.35e-091.67e-151.08e-165.25e-025.08e-022.02e-021.05e-024.08e-173.06e-09
Goofspiel(5)1.59e+002.62e-033.03e-012.12e-031.70e-011.16e-031.49e-021.49e-021.13e-011.13e-013.56e-023.56e-022.58e-163.47e-05
Liar's Dice(4)1.29e+002.62e-031.30e+002.11e-033.58e-025.65e-093.79e-036.94e-175.33e-023.14e-033.90e-033.90e-038.33e-172.08e-16
Liar's Dice(5)1.54e+001.45e-021.53e+002.64e-032.71e-014.01e-048.89e-038.27e-054.88e-028.38e-031.20e-021.20e-022.86e-057.52e-07
Liar's Dice(6)1.75e+001.04e-011.60e+003.26e-033.18e-012.96e-023.27e-022.77e-046.23e-022.39e-021.41e-021.06e-026.24e-032.81e-04
Battleship(2x2)4.58e-015.33e-042.15e-014.42e-042.92e-081.27e-094.25e-144.25e-141.56e-061.31e-091.16e-132.94e-158.88e-162.41e-03
Battleship(2x3)5.01e-017.43e-034.95e-011.65e-039.34e-022.45e-024.59e-024.59e-022.52e-028.18e-037.36e-036.53e-03-1.85e-154.15e-03

Question: Original Discounted CFR uses regret matching that discounts positive and negative cumulative regrets separately. Do you think it will converge last-iterate in perturbed regularized games?

Thank you for this natural question; we ran experiments to test it. Our proof does not cover original DCFR. Theorem 1 relies on a comparator that shrinks together with the iterate, which needs one discount factor applied to the whole regret vector in the nonnegative cone. Original DCFR keeps negative cumulative regrets and scales the positive and negative parts by different factors, so the iterate is not a uniform rescaling and that step fails.

New experiment A. Following the reviewer's question, we implemented original DCFR with negative-part exponent β in {0, 0.5, 1, 1.5, 2}, where β=0 is the constant 1/2 of Brown & Sandholm, and ran it in the fixed perturbed regularized game under simultaneous updates (the regime of Theorem 1); the results are in the table below and in the revised paper at Table 15 on page 25 and Table 16 on page 25; discussion on page 25, lines 1296-1308. Conclusion: its final iterate reaches the reference on Kuhn and Goofspiel(4) for every β, which is consistent with last-iterate convergence in that regime, but we have no proof. In detail, on the two games where the reference is resolved at this horizon, it ends its final iterate reaches the reference on the two games where the reference is resolved at this horizon: within 2.6e-14 on Kuhn and within 3.55e-11 on Goofspiel(4), for every β. On Goofspiel(4) with β=0 this happens late in the run. The evidence is therefore consistent with last-iterate convergence in that regime, but we have no proof.

Original DCFR in the fixed perturbed regularized game (γ = μ = 1e-2), simultaneous updates: distance to the reference after 50,000 iterations.

gameβ = 0β = 0.5β = 1β = 1.5β = 2
Kuhn7.38e-152.59e-143.26e-152.97e-151.74e-15
Goofspiel(4)3.55e-114.58e-159.10e-151.68e-117.68e-15

New experiment B. We ran original DCFR (β=0), without and with prediction, in the RT protocol of Table 1 on eight games; the results are in the table below and in the revised paper at Table 15 on page 25 and Table 16 on page 25; discussion on page 25, lines 1296-1308. Conclusion: our single-discount form is the safer choice; with prediction it ends clearly lower on six games and level on two, and without prediction neither form dominates. In detail, in the RT protocol of Table 1 (alternating, 20,000 iterations, 8 games), without prediction our single-discount RT-DCFR+ ends lower than original DCFR (β=0) on four games, both are at the roundoff floor on two, and original DCFR ends lower on two; RT-DCFR+ reaches 1e-6 on six games and original DCFR on five. With prediction, our RT-PDCFR+ ends clearly lower than the original form on six games (Leduc, Goofspiel(4), Goofspiel(5), Liar's Dice(4), Liar's Dice(5), Liar's Dice(6)), while the two are level, within 2%, on Kuhn and Battleship(2x2). Raising β above 1, which makes the total negative discount finite, does not change the picture. We added this as an open problem (page 25, lines 1296-1303).

RT protocol of Table 1 (alternating, 20,000 iterations): final exploitability / iterations to 1e-6 (-- = not reached).

gameRT-DCFR+ (ours)original DCFR, β = 0RT-PDCFR+ (ours)original DCFR + prediction, β = 0
Kuhn2.44e-15 / 46002.03e-15 / 45002.37e-04 / --2.40e-04 / --
Leduc4.21e-05 / 133001.66e-05 / 120002.26e-04 / --3.24e-04 / --
Goofspiel(4)1.55e-15 / 40005.55e-06 / 190003.34e-16 / 17002.14e-04 / --
Goofspiel(5)1.19e-06 / 169006.14e-05 / --1.96e-03 / --4.15e-03 / --
Liar's Dice(4)1.73e-16 / 7002.50e-16 / 6006.94e-17 / 9001.90e-05 / 800
Liar's Dice(5)4.17e-07 / 100004.84e-16 / 18003.08e-06 / --3.60e-04 / --
Liar's Dice(6)1.57e-04 / --6.99e-04 / --4.85e-04 / --7.15e-04 / --
Battleship(2x2)9.47e-04 / --1.12e-03 / --1.60e-03 / --1.62e-03 / --

We thank you again for your support and for the comments that improved our paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the three reviewers for their time and their constructive comments. We uploaded a revised PDF with every change marked in blue.

Summary of changes

Theory

  • Proposition 1 no longer carries a nondegeneracy assumption (Reviewer BUTB, W1). Lemma 3, page 18, lines 928-949 proves that the tangent-space map ΠJ is invertible for every μ>0, and the revised proposition is on page 6, lines 317-321. The abstract, introduction and conclusion now state its scope precisely: a perturbed regularized matrix game whose equilibrium lies strictly above the perturbation floor (page 1, lines 27-28).
  • Normal-form games with γ=0 (Reviewer BUTB, W2). The normal-form paragraph of Section 6 now states that Theorems 1 and 2 hold with γ=0 when H=1 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 experiments

  • Euclidean-regularized baselines (Reviewer BbvB, W1). Reg-CFR, DOMD and MMD with the Euclidean regularizer, default and tuned, on all nine games (Table 11 on page 23; discussion on page 22, lines 1179-1186); the comparison paragraph of Section 6 is rewritten accordingly (page 8, lines 424-431).
  • Figure 1, Kuhn panel (Reviewer BbvB, W1). Rerun for 50,000 iterations, so all panels share one horizon (Figure 1 on page 7).
  • Original DCFR with separate positive and negative discounting (Reviewer BbvB, Q1). Fixed perturbed regularized game and RT protocol, negative-part exponent β in {0, 0.5, 1, 1.5, 2} (Table 15 on page 25 and Table 16 on page 25; discussion on page 25, lines 1296-1308); stated as an open problem (page 25, lines 1296-1303).
  • Larger games (Reviewer BUTB, Q1). Goofspiel(6) and Liar's Dice with 2 dice of 4 sides, about 393k information sets (Table 12 on page 24; discussion on page 23, lines 1235-1241).
  • Simultaneous-update controls (Reviewer BUTB, Q2). The comparison of RT-PCFR+ and RTCFR+ under simultaneous updates on Leduc, Liar's Dice(5,6) and the two larger games, and over a 3x3 grid of (μ, T_u) (Table 8 on page 22, discussed on page 21, line 1133 to page 22, line 1139, and Table 12 on page 24).
  • Wall-clock cost per iteration (Reviewer BUTB, Q3). All four RT variants on the nine games (Table 13 on page 24; discussion on page 24, lines 1262-1265).
  • Normal-form table with γ>0 (Reviewer BUTB, W2). The perturbed protocol gives the same conclusions as γ=0 (Table 14 on page 24; discussion on page 24, lines 1280-1284).

Wording and presentation

  • Protocol is untuned (Reviewer BUTB, W3). The paragraph on the RT protocol states up front that the published RTCFR+ settings are not optimal and are kept for comparability (page 8, lines 417-419).
  • Effect of discounting, per method and per game (Reviewer BUTB, W3; page 9, lines 477-480).
  • Discussion of larger-scale use (Reviewer BUTB, Q1). A paragraph on combining the method with parallel and GPU CFR, abstraction, pruning, and depth-limited solving, citing the eight references the reviewer listed (page 3, lines 130-138).
  • Readability. We reworded Sections 1, 4, 5, 6, and the appendices: shorter sentences and captions, every symbol defined at first use, fewer cross-references, and experimental paragraphs opening with their conclusions. Theorem statements and proofs are unchanged apart from the changes to Proposition 1 listed above. Three appendix paragraphs that listed numbers are now tables (Table 5 on page 20, Table 6 on page 21 and Table 7 on page 21), Figure 4 moved from the appendix to Section 6, and we removed former Appendix D's source-code listing since the code is in the supplementary package.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.