acceptodds
Under review as a conference paper at ICLR 2027

Faster Game Solving via Initial Regret Reduction

11 views

Abstract

Counterfactual regret minimization (CFR) is the leading framework for solving two-player zero-sum imperfect-information games and underlies recent superhuman poker AI. A remaining source of inefficiency in CFR and CFR+ is uniform initialization: because every action is explored equally at the start, clearly suboptimal actions depress the average counterfactual value and inflate the initial positive regrets of the remaining actions, forcing many iterations to separate the viable actions that matter in equilibrium. Discounted variants such as DCFR and PDCFR+ mitigate this effect only indirectly by decaying accumulated regrets over many iterations. We propose initial regret reduction (IRR), a one-time reduction that rescales the first positive accumulated regret by a factor of at most one, preserves its direction, and leaves every later update unchanged. The factor comes from computing the regret of that round as if it had been played with a mixture of the uniform strategy and the next strategy induced by the first positive regret. We prove that the single reduction never enlarges the first positive regret, and that IRR-RM+ and IRR-PRM+ preserve the no-regret rate. Combined with PCFR+, IRR-PCFR+ attains the lowest average-iterate exploitability among the compared algorithms on benchmark imperfect-information games other than the heads-up no-limit Texas hold'em subgames, where DCFR remains superior.

Primary area:
reinforcement learning
Keywords:
CFR, imperfect-information games, regret minimization, regret matching, equilibrium computation, online learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_DZRPOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies how uniform initialization can create excessively large initial positive regrets in CFR-based algorithms. Initial Regret Reduction rescales the regret vector and corresponding prediction term once, when positive regret first appears at an information set, and then resumes standard updates. The paper establishes an O(T−1/2)O(T^{-1/2}) average-regret rate and an interpretation as a one-time OMD step-size adjustment. Experiments cover 16 games, reporting favorable average-strategy results on non-HUNL benchmarks while acknowledging stronger DCFR performance on HUNL.

Critical strengths
  1. The modification is simple and addresses a clearly illustrated mechanism. The motivating examples show how initial regret magnitudes can delay differentiation among effective actions. Applying the intervention once per information set preserves the regret vector's direction and avoids substantial recurring overhead.

  2. The theoretical treatment and evaluation acknowledge important distinctions. The proofs explicitly account for the scaled regret and prediction terms. The experiments report both average-strategy and last-iterate behavior and include settings where the proposed method is not strongest.

Critical weaknesses
  1. The presentation makes the central mechanism unnecessarily difficult to understand. The reader must connect several layers of notation covering regret matching, predictive updates, averaging, and the OMD interpretation. The paper does not provide a sufficiently clear, unified explanation of how these components relate to the one-time intervention. Figure 1 illustrates motivating examples and Figure 2 presents results, but neither provides a mechanism diagram connecting the original regret vector, the interpolation baseline, the scale factor, and the subsequent update. Despite the numerical examples, this substantially increases the effort required to assess the method as a whole.

  2. The main average-strategy comparison does not isolate the contribution of IRR. The paper explicitly uses γ=2\gamma=2 for PCFR+ and γ=9\gamma=9 for IRR-PCFR+. Although the averaging exponent does not affect the last iterate, it directly changes the average strategy used in the principal comparison. Consequently, the reported improvement combines the intervention with a different averaging scheme. The last-iterate results provide complementary evidence but do not resolve this attribution problem.

  3. The benefit of the specific adaptive scaling rule remains insufficiently established. The theoretical guarantees apply to general one-time scaling factors s∈(0,1]s\in(0,1], rather than depending on the particular norm ratio in Equation (3). For a two-action information set with initial regret (a,−a)(a,-a), the proposed rule reduces to the fixed coefficient s=1−λs=1-\lambda. Without a fixed-scaling baseline, the experiments do not establish whether the adaptive construction contributes beyond the simpler intervention of shrinking the initial regrets.

  4. Parameter selection and evaluation on the same benchmarks limit the robustness of the empirical conclusions. The authors disclose that λ\lambda and γ\gamma were selected through benchmark sweeps and then frozen. However, the submission provides neither sensitivity results nor evaluation on games excluded from parameter selection. Several competing methods retain their original configurations. The evidence therefore does not adequately distinguish a robust algorithmic improvement from an advantage associated with the selected configuration.

Questions for authors

See weaknesses.

1 comment

Thank you for the careful reading and constructive feedback. We ran all requested ablations across the 16-game suite (matched γ and fixed versus adaptive one-time scaling) and added the analyses and full trajectory curves in Appendix D of the revised PDF (pages 22 to 27: text on pages 22 to 24; Figure 3 on page 25 for matched γ and Figure 4 on page 26 for fixed versus adaptive scaling).

W1 (Presentation and mechanism diagram). We appreciate the feedback on readability. Because Eq. (3) is an empirical heuristic rather than a principled derivation, we chose not to add a mechanism diagram that would make it look more theoretical than it is, and instead added the empirical scaling ablation in Appendix D.2 (page 23) and Figure 4 (page 26).

W2 (Matched γ). We re-ran all 16 games × {IRR-PCFR+, PCFR+, PDCFR+} × γ ∈ {2, 5, 9} (144 runs; full trajectory curves in Figure 3, page 25, discussed in Appendix D.1, page 23). Because curves eventually stop decreasing, fluctuate near the bottom of the axis, or hit floating-point zero, we count both terminals at or below 1e-13 as a tie (Appendix D, page 22); all reported wins are by at least 10×, so none of the counts depend on this cutoff. At matched γ = 9 against PCFR+, IRR-PCFR+ wins 6 games (from 10.6× on SmallMatrix (1) to 1.8e13× on SmallMatrix (4)), ties 8, and loses the two HUNL subgames (1.44× and 1.56×). Against PDCFR+ at γ = 9, it wins 3 (up to 5.8e6×), ties 10, and loses 3 (Liar's dice (5) 8.6×, Subgame (3) 3.4×, Subgame (4) 2.4×). The large Kuhn gap under unmatched exponents disappears once γ is matched. Also, PDCFR+ is not monotone in γ: at γ = 9 it finishes 7.5e4× worse than PCFR+ on Goofspiel-imp (5).

W3 (Fixed scaling vs adaptive rule). Your two-action reduction to ≈1/2 holds, and the data match your observation on near-symmetric games (matrix games and HUNL), where fixed and adaptive scaling behave similarly or s = 1 is slightly better. Adaptivity helps when initial regret scales differ widely across actions. We tested fixed one-time scales s ∈ {1, 0.5, 0.1, 1e-3, 1e-5} (s = 1 is PCFR+; full trajectory curves in Figure 4, page 26, discussed in Appendix D.2, page 23). Every fixed constant fails by 5 to 13 orders of magnitude on at least one game (s = 1 and 0.5 on SmallMatrix (4); s = 0.1 and 1e-3 on Goofspiel (5); s = 1e-5 on Liar's dice (5)), while the adaptive rule stays within 3.9× of the per-game best constant on all 16 games and beats all five constants on Goofspiel (4) and Goofspiel-imp (5).

W4 (Parameter sweep and benchmark protocol). We swept λ ∈ {0.1, 0.3, 0.5, 0.7, 0.9, 0.99, 0.999, 0.9999, 0.99999} and γ ∈ {2, 5, 9} across all 16 games, minimizing terminal average-strategy exploitability. Competitors are evaluated both under their published defaults (main text) and at matched γ ∈ {2, 5, 9} across all 16 games (Appendix D.1, page 23; Figure 3, page 25).

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

This paper proposes Initial Regret Reduction (IRR), a simple modification of the SOTA method predictive counterfactual regret minimization (PCFR+) algorithm, that aims to accelerate convergence by mitigating the uniform-initialization bias. The key idea is to rescale the instantaneous regret at the first positive-regret round at each information set by a factor s∈(0,1]s\in(0,1], computed by evaluating the regret against a mixture of the uniform strategy and the strategy induced by the original positive regret. Then, the algorithm returns to the standard update rule of PCFR+ without further modifications. On the theoretical side, the authors prove that the scaling factor never exceeds one and establish that the modified local regret minimizers retain O(T)O(\sqrt{T}) regret bounds, hence preserving the corresponding O(1/T)O(1/\sqrt{T}) average-strategy convergence guarantee. The experimental on matrix-derived examples and benchmark imperfect-information games validate the improvements of IRR-PCFR+ over existing CFR variants.

Critical strengths

1. A simple and practically motivated modification of CFR algorithms. The paper identifies a plausible source of inefficiency in CFR-type algorithms: the first positive regret vector can have a large scale caused by highly suboptimal actions under the initial uniform strategy. The proposed one-time rescaling directly targets this issue while preserving the direction of the positive regret vector. Unlike repeated discounting, IRR modifies only one update per information set, making the method conceptually simple and potentially inexpensive to incorporate into existing implementations of local regret matching-type minimizer.

2. Theoretical preservation of no-regret guarantees.

The authors establish that IRR-RM+ and IRR-PRM+ retain O(T)O(\sqrt{T}) regret bounds. The resulting average-strategy convergence guarantee O(1/T)O(1/\sqrt{T}) is therefore preserved.

3. Broad empirical evaluation.

The experiments cover several structured matrix game examples and extensive-form game benchmarks, and report substantial improvements on many of them. The inclusion of last-iterate convergence results and the explicit identification of HUNL subgames as a setting where DCFR remains superior also make the empirical evaluation more informative than a uniformly positive performance claim would be.

Critical weaknesses

1. The theoretical results do not explain or guarantee faster convergence. The motivation of the proposed IRR-PCFR+ is to speed the average-iterate convergence of CFR-type algorithms, but the theoretical guarantee still remains the same suboptimal rate O(1/T)O(1/\sqrt{T}) as traditional CFR variants like CFR+ and PCFR+. Given that two recent works [A1-A2] have proposed new regret matching type algorthms with optimal/fast average-iterate convergence rate O(1/T)O(1/T) while retaining strong empirical performance in both matrix games and EFG benchmarks, the (theoretical) novelty of this work is truly limited.

2. The proof techniques are almost the same as in previous works. The implementation of the proposed IRR-PRM+ differs from that of PRM+ only in one line (i.e. the initial regret correction step). Therefore, the cumulative regret of IRR-PRM+ admits the same order of PRM+ (although PRM+ in Farina et al. 2021 requires the uniform distribution initialization, generalizing its regret bound for arbitrary initialization is feasible and not that technical, e.g. see the related work [A3]). Besides, as far as i can tell, the whole proofs (especially theorems 2-3) mainly build on the existing theoretical results of several celebrated CFR variants (like CFR in nips2027, CFR+ in IJCAI2015, and PCFR+ in AAAI2021), and actually most of them is unnecessary to be exhibited once again. So it is hard for me to distinguish the original part of the theoretical analysis for IRR-PCFR+.

3. The empirical verification of the IRR mechanism is not that convinced. As all CFR variants use weighted-average strategy in empirical evaluation, the proposed IRR-PCFR+ should use the same weight γ\gamma as that in PCFR+ to show its advantages. However, in table 1, IRR-PCFR+ uses γ=9\gamma =9 while PCFR+ uses γ=2\gamma=2.

4. Unclear motivation of the construction of scaling factor. It is not hard to conceive of an idea to use a rescaling factor to mitigate the large regret, but i am not clear why this work uses the mixture of current strategy and next strategy to construct the scale factor in Eq.3. Is there any theoretical explanation for such construction?

5. The proposed IRR-PCFR+ loses the parameter-free and scale-invariant property of PCFR+ algorithm, due to the introduction of the hyperparameter λ\lambda, whereas the two recent works [A1-A2] admits such desirable properties and fast 1/T1/T average-regret guarantee.

Minor Problems.

6. Table 1 does not give the formulation of predicted accumulated regret.

7. Lack of comparisons with other theoretical related works. In section 5, you should not just list several theorems without any discussion of their advantages/comparisons with other related works. For example, it is well-known from Farina 21's work that PRM+ can be considered as the implementation of optimistic mirror descent on non-negative orthants, then what insight does Theorem 4 give besides the equivalent OME formulation?

8. The description of experimental results is rush and too short.

Overall, the IRR mechanism is interesting, but the current manuscript is too rush and far below the acceptance bar of a top AI conference.

References

[A1] A Faster Parameter-Free Regret Matching Algorithm. ICLR2026.

[A2] Scale-invariant regret matching and online learning with optimal convergence: Bridging theory and practice in zero-sum games. EC 2026.

[A3] Refined Last-Iterate Convergence Analysis with Optimism in Solving Extensive-Form Games. 2026.

Questions for authors

Besides the main weakness, i have other two questions:

  1. How sensitive is IRR-PCFR+ to the interpolation parameter (\lambda)? The experiments use (\lambda=0.99999). Could the authors report an ablation study over a meaningful range of (\lambda) values, including the resulting distribution of reduction factors (s)?

  2. How much of the improvement comes from IRR itself rather than the averaging exponent? Since IRR-PCFR+ uses (\gamma=9), whereas PCFR+ uses (\gamma=2), could the authors include comparisons with matched averaging exponents and, ideally, compare IRR-PCFR+ against PCFR+ under independently tuned averaging schedules?

1 comment

Thank you for the thorough review and helpful suggestions. We ran all requested follow-up experiments across the 16-game suite (matched γ, fixed versus adaptive scaling, and comparisons against [A1] and [A2]) and added the analyses and full trajectory curves in Appendix D of the revised PDF (pages 22 to 27: text on pages 22 to 24; Figure 3 on page 25 for matched γ, Figure 4 on page 26 for fixed versus adaptive scaling, and Figure 5 on page 27 for [A1] and [A2]).

W1 ([A1] and [A2]). Agreed on the theoretical rate: our theory is not meant to claim a novel or faster asymptotic rate, and primarily verifies that the one-time scaling does not break the host algorithm's convergence guarantee. In CFR-based game solving, asymptotic rate guarantees and finite-time empirical performance frequently diverge. To test this directly, we implemented [A2] (IREG-PRM+ and IR-PRM+) and ran all 16 games (Table R1; full trajectory curves in Figure 5, page 27, discussed in Appendix D.3, page 24). Although [A2] carries a stronger O(1/T) theoretical bound, neither [A2] variant outperforms IRR-PCFR+ on the 14 matrix and sequential games, where the stronger baseline trails by 5 or more orders of magnitude on sequential games. On HUNL, IREG-PRM+ [A2] is the best rate-optimal baseline and DCFR is best overall, consistent with the dominated-action share (8.7% and 14.3% on Subgame (3) and (4), the lowest among the sequential games). We also attempted to implement [A1] (MI-SPRM+); however, [A1] specifies pseudocode only for normal-form games and has no open-source implementation. Because our extensive-form adaptation plateaued between 1e-2 and 1e0 across games and could not be verified as faithful to [A1]'s setup, we omitted [A1] from Figure 5 and Table R1 rather than report an unverified baseline.

GameIRR-PCFR+PCFR+IREG-PRM+ [A2]IR-PRM+ [A2]
Liar's dice (5)2.5e-128.8e-61.8e-62.2e-6
Goofspiel (5)1.2e-155.8e-61.8e-96.6e-8
Battleship (3)1.2e-147.4e-127.6e-95.3e-9
Leduc poker6.0e-142.9e-132.2e-85.8e-9
Kuhn poker1.8e-151.3e-151.6e-103.2e-10
SmallMatrix (1)2.5e-92.7e-82.5e-83.4e-8
HUNL Subgame (3)2.3e-51.6e-55.2e-69.7e-6
HUNL Subgame (4)1.2e-57.9e-66.5e-62.1e-5

Table R1: Terminal average-strategy exploitability (γ = 9 for the first two columns) at the paper budgets.

W2 and Minors 6-8. On W2, agreed that the base regret analysis follows prior PRM+ bounds; the new technical pieces are the non-expansion of the scaled pair (Theorem 1) and the exact one-time OMD step-size equivalence on top of Farina et al. (2021) (Theorem 4). On Minor 6, Table 1 (page 2) explicitly gives the predicted accumulated regret formula for all predictive variants. On Minor 7, Section 5.2 (pages 6 to 7) states the specific insight beyond Farina et al. (2021): IRR corresponds to modifying the OMD step size η_τ = s on the single reduction round τ while keeping η_t = 1 otherwise and leaving the forcing action unchanged, like learning rate warmup.

W3 and Q2 (Matched γ). We re-ran all 16 games × {IRR-PCFR+, PCFR+, PDCFR+} × γ ∈ {2, 5, 9} (144 runs; full trajectory curves in Figure 3, page 25, discussed in Appendix D.1, page 23). Because curves eventually stop decreasing, fluctuate near the bottom of the axis, or hit floating-point zero, we count both terminals at or below 1e-13 as a tie (Appendix D, page 22); all reported wins are by at least 10×, so none of the counts depend on this cutoff. At matched γ = 9 against PCFR+, IRR-PCFR+ wins 6 games (from 10.6× on SmallMatrix (1) to 1.8e13× on SmallMatrix (4)), ties 8, and loses the two HUNL subgames (1.44× and 1.56×). Against PDCFR+ at γ = 9, it wins 3 (up to 5.8e6×), ties 10, and loses 3 (Liar's dice (5) 8.6×, Subgame (3) 3.4×, Subgame (4) 2.4×). The large Kuhn gap under unmatched exponents disappears once γ is matched. Also, PDCFR+ is not monotone in γ: at γ = 9 it finishes 7.5e4× worse than PCFR+ on Goofspiel-imp (5).

W4 (Eq. 3). To be honest, the mixture in Eq. (3) is an empirical heuristic rather than a first-principles derivation. It is supported by Theorem 1 (s ≤ 1 always), Theorem 4 (an exact OMD step-size reading once s is chosen), and the fixed-scaling ablation in Appendix D.2 (page 23) and Figure 4 (page 26) showing that every fixed constant fails by 5 to 13 orders of magnitude on some game while adaptive IRR stays within 3.9× of the per-game best constant everywhere.

W5 and Q1 (Sensitivity to λ and distribution of s). IRR adds one parameter λ and is scale-invariant only up to the (1−λ) floor. We swept λ ∈ {0.1, 0.3, 0.5, 0.7, 0.9, 0.99, 0.999, 0.9999, 0.99999} and γ ∈ {2, 5, 9} across all 17 games, minimizing terminal average-strategy exploitability. Across 122,038 realized factors s, the median equals the 1−λ = 0.00001, with p75 = 0.011 and p90 = 0.098.

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

The paper proposes initial regret reduction (IRR), a one-time rescaling of the first positive regret vector at each information set. The scaling factor is obtained by re-evaluating the current loss vector against an interpolation between the uniform strategy and the next regret-matching strategy. The paper proves that the factor does not exceed one and that the modified local regret minimizers retain no-regret guarantees. It evaluates IRR-PCFR+ using average- and last-iterate exploitability on matrix games, sequential benchmarks, and two HUNL subgames.

Critical strengths
  1. The method is simple and is motivated by a concrete initialization effect in regret matching: large early regrets can obscure small payoff differences between viable actions.

  2. The paper provides a useful local analysis, including the non-expansion of the first positive regret and an OMD interpretation.

  3. The evaluation reports both average and last iterates and includes negative HUNL results rather than only favorable diagnostic games.

Critical weaknesses
  1. The main average-iterate comparison does not isolate IRR. IRR-PCFR+, PCFR+, and PDCFR+ use averaging exponents 9, 2, and 5, respectively. Since larger exponents put more weight on recent iterates, the reported average-strategy gains cannot be uniquely attributed to IRR.

  2. The theory preserves no-regret convergence but does not establish a better finite-time guarantee than the unmodified algorithm. The HUNL results also suggest that the method is not uniformly robust, but the paper does not identify whether the degradation comes from IRR, PCFR+, or parameter selection.

  3. The sweep that selected lambda = 0.99999 and gamma = 9 is not described sufficiently to assess tuning bias or sensitivity.

Questions for authors
  1. What are the results of an IRR on/off comparison with the same averaging exponent, including both HUNL subgames? Does the comparison with PDCFR+ persist when PDCFR+ is also allowed gamma = 9?

  2. What parameter grid, selection objective, and tuning budget were used?

  3. Can the authors compare IRR with a simple fixed one-time regret scaling and explain the HUNL failure cases?

1 comment

Thank you for the constructive review and detailed questions. We ran all requested follow-up experiments across the 16-game suite (matched averaging exponents and fixed one-time scaling) and added the analyses and full trajectory curves in Appendix D of the revised PDF (pages 22 to 27: text on pages 22 to 24; Figure 3 on page 25 for matched γ and Figure 4 on page 26 for fixed versus adaptive scaling).

W1 and Q1 (Matched γ). We re-ran all 16 games × {IRR-PCFR+, PCFR+, PDCFR+} × γ ∈ {2, 5, 9} (144 runs; full trajectory curves in Figure 3, page 25, discussed in Appendix D.1, page 23). Because curves eventually stop decreasing, fluctuate near the bottom of the axis, or hit floating-point zero, we count both terminals at or below 1e-13 as a tie; all reported wins are by at least 10×, so none of the counts depend on this cutoff. At matched γ = 9 against PCFR+, IRR-PCFR+ wins 6 games (from 10.6× on SmallMatrix (1) to 1.8e13× on SmallMatrix (4)), ties 8, and loses the two HUNL subgames (1.44× and 1.56×). Against PDCFR+ at γ = 9, it wins 3 (up to 5.8e6×), ties 10, and loses 3 (Liar's dice (5) 8.6×, Subgame (3) 3.4×, Subgame (4) 2.4×). A noteworthy phenomenon is that PDCFR+ is not monotone in γ: at γ = 9 it finishes 7.5e4× worse than PCFR+ on Goofspiel-imp (5).

W3 and Q2 (Parameter sweep). We swept λ ∈ {0.1, 0.3, 0.5, 0.7, 0.9, 0.99, 0.999, 0.9999, 0.99999} and γ ∈ {2, 5, 9} across all 16 games (Table 2's 16 games), minimizing terminal average-strategy exploitability.

W2 and Q3 (Rate, fixed scaling, and HUNL). Agreed on the asymptotic rate: IRR keeps the host bound by design and targets finite-time constant-factor speedup rather than a better asymptotic rate. For fixed scaling, we tested s ∈ {1, 0.5, 0.1, 1e-3, 1e-5} (s = 1 is PCFR+; full trajectory curves in Figure 4, page 26, discussed in Appendix D.2, page 23). Every fixed constant fails by 5 to 13 orders of magnitude on at least one game (s = 1 and 0.5 on SmallMatrix (4); s = 0.1 and 1e-3 on Goofspiel (5); s = 1e-5 on Liar's dice (5)), while the adaptive rule stays within 3.9× of the per-game best constant on all 16 games and beats all five constants on Goofspiel (4) and Goofspiel-imp (5).

On HUNL, at matched γ = 9 IRR trails PCFR+ by 1.44× on Subgame (3) and 1.56× on Subgame (4). Across our 12 sequential (extensive-form) games, Subgame (3) and Subgame (4) have the lowest dominated-action shares: Subgame (3) 0.0870 < Subgame (4) 0.1429 < Goofspiel-imp (5) 0.1537 < Goofspiel (5) 0.2008 < Goofspiel-imp (4) 0.2184 < Goofspiel (4) 0.2378 < Battleship (2) 0.2945 < Battleship (3) 0.3473 < Liar's dice (4) 0.3652 < Liar's dice (5) 0.3849 < Leduc poker 0.3988 < Kuhn poker 0.4167 (plus Battleship_22_ship12_3 at 0.2073; among the matrix games, SmallMatrix (1) and SmallMatrix (2) have 0.0000, SmallMatrix (3) has 0.1667, and SmallMatrix (4) has 0.4000). Because these two HUNL subgames have the fewest dominated actions among the sequential games, the one-time scaling hits active strategic regret rather than initialization error; across the 17-game dominance census, the Spearman rank correlation between dominated-action share and IRR gain is −0.43 (−0.41 under the matched γ = 9 terminals of Figure 3).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.