acceptodds
Under review as a conference paper at ICLR 2027

Invariant Last-Iterate Convergence for Optimistic Counterfactual Regret Minimization in Solving Perturbed Extensive Form Games

Abstract

Counterfactual regret minimization (CFR) represents a family of online algorithms to effectively learn the (approximate) Nash Equilibrium (NE) of imperfect-information extensive-form games (EFGs). Among them, the optimistic/predictive CFR methods, which incorporates the optimism technique from online optimization to accelerate approximation to NE, often achieve superior theoretical and practical performance. However, relatively little is known about the last-iterate convergence of optimistic CFR variants. In this work, we take a step forward and provide asymptotic last-iterate convergence guarantees for two classical optimistic CFR methods (PCFR and PDCFR) in solving perturbed EFGs. Specifically, we first provide last-iterate convergence for PCFR in solving perturbed regularized EFGs. Such a result holds for any step size and any initialization at each decision node, and hence is referred to as invariant last-iterate convergence for perturbed EFGs. Based on the invariance property, we develop a tighter average-regret bound than the previous one for PCFR in solving EFGs. Then, we extend our analysis to the PDCFR algorithm that discounts regrets from earlier iterations. The invariant last-iterate convergence still holds for any non-decreasing bounded sequence of discounting factors and any strategy initialization. Furthermore, we reveal that the last-iterate strategy of the above two optimistic CFR algorithms forms an approximation of the NE of original EFG. The approximation error approaches zero by setting small perturbation/regularization coefficients and enforcing the last-iterate strategy to be close to the unique NE of the perturbed regularized EFG. Experiments show that our proposed methods outperform the latest method in most medium-size EFGs, and yield comparable performance to discounted CFR in large-scale Poker games.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
last-iterate convergence, counterfactual regret minimization, perturbation, extensive-form game

Reviews

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

This paper proves asymptotic last-iterate convergence for PCFR+ and PDCFR+ in two-player zero-sum regularized perturbed EFGs.

Critical strengths
  • The paper is easy to read.
  • The paper makes a good comparison with related work.
Critical weaknesses

The setting considered in this paper (regularized and perturbed two-player zero-sum EFG) is the same as Reg-CFR. This paper extends the results of Reg-CFR to PCFR+/PDCFR+. However, this is not surprising since the paper's results rely on regularization + perturbation as Reg-CFR.

Questions for authors

Is it possible to extend the result to non-regularized and non-perturbed EFGs? I would raise my score if either of these two is proven.

  • A counterexample about last-iterate convergence of PCFR+/PDCFR+ in non-regularized and non-perturbed EFGs.
  • A last-iterate convergence guarantee for PCFR+/PDCFR+ in non-regularized and non-perturbed EFGs.
Reviewer_nneMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the performance of predictive counterfactual regret minimization (PCFR+) and a discounted version (PDCFR+) on solving two-player zero-sum perturbed and regularized extensive-form games (EFGs). The main theoretical results include the asymptotic last-iterate convergence to the unique NE of the perturbed and regularized games (that holds for any initializations, learning rates, and discount factors), as well as regret bounds that slightly improve over some prior work. In addition, the paper also shows that as the perturbation and regularization level goes to zero, the duality gap of the algorithm's last iterate (in terms of the original game) goes to zero as well. Finally, the paper empirically verifies the effectiveness of the studied algorithms on solving medium to large scale EFGs.

Critical strengths
  • The paper provides theoretical justifications for some of the most practically effective algorithms for solving EFGs, which is always good to have.

  • The convergence results for the original games (instead of only the perturbed and regularized ones) are also good to have.

  • The paper is overall very well written.

Critical weaknesses

The reasons that I cannot give a higher rating at this point are as follows:

  1. Overall I feel that the results are very much "expected". Despite all those technical novelties claimed in Appendix C, I am not sure how many of them are real and significant innovations, especially when compared to Meng et al. 2025a.

  2. The last-iterate convergence is only asymptotic without a concrete rate. Given the vast literature in this line of work (some of which do provide concrete convergence rates, such as Cai et al. 2025), I feel that it is not unreasonable to ask for more at this point.

  3. The paper emphasizes that the convergence/regret results hold for all initializations and learning rates, but I am not sure why that is really important. It seems to me that from both a practical and a theoretical viewpoint, setting the initialization to 0 is the best choice (in which case the choice of η\eta also becomes irrelevant since the algorithm is invariant to it). So do we really care about other choices of initializations? Note that once we set the initialization to 0, the claimed regret bound improvement (Remark 4.1) also disappears.

  4. Related to the last comment on regret bound improvement over Farina et al. 2021, there are several works in the literature that obtain even faster rates (i.e. sub T\sqrt{T} rate), as also acknowledged in Table 1. This further diminishes the importance of the regret bound results of this work.

  5. Proposition 5.3: I don't understand how the result can be correct since the bound is independent of γ\gamma. Just consider the case where ν=μ=0\nu=\mu=0, then the statement becomes "an NE of any perturbed EFG is an NE of the original EFG", which is clearly wrong. I wanted to check what goes wrong in the proof, but I gave up after seeing some clear errors; for example, the definition of duality gap in L1718 is clearly wrong (this might just be a typo instead of the key reason for the aforementioned issue, but I thought it would be easier for the authors to figure this out.)

  6. The 2nd bound of Theorem 5.1 is not explicit enough, since it is unclear how small the term Gapγk(...)\text{Gap}_{\gamma_k}(...) is. It seems to me that it can be further bounded by ∥x^Tk+1−x^∗,γk,μk∥+μk\|\hat{x}^{T_k+1}-\hat{x}^{*,\gamma_k, \mu_k}\|+\mu_k (order-wise). Overall, I think the conclusion in L414 that says the error is O(...+min⁡{μk,γk})O(...+\min\{\mu_k, \gamma_k\}) is clearly wrong. In particular, the min should be a sum instead.

Below are some minor issues (I don't know where else I should put this):

  1. L111 and L145: the notation P is used for two different things

  2. L253: The statement that Meng et al. 2025a is a special case of Theorem 4.1 seems problematic. While PCFR+ with a general predictor for the first step of the update is certainly a more general algorithm than CFR+, the PCFR+ presented in (5) and analyzed in Theorem 4.1 already hardwires the predictor with −m^it(I)-\hat{m}_i^t(I), so it no longer covers CFR+ as a special case. Things could still be correct even with a general predictor, but this is just not what is currently proven in Theorem 4.1.

  3. Pseudocode of ALG1: Lines 6 and 7 are problematic since the updates of θ^It+1\hat{\theta}_I^{t+1} should be performed after Line 9 (as it depends on σ^it+1\hat{\sigma}_i^{t+1}).

Questions for authors

I would like to hear the authors' response on Weaknesses 3, 5, and 6 I pointed out earlier.

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

The paper studies PCFR+ and PDCFR+ within the reward-transformation framework for perturbed, regularized extensive-form games. It proves asymptotic last-iterate convergence for a fixed transformed game, derives average-regret bounds, and relates transformed-game solutions to approximate equilibria of the original game. Algorithm 1 combines these solvers with phase-wise reference-strategy updates and decreasing perturbation and regularization parameters, yielding RTPCFR+ and RTPDCFR+.

Critical strengths
  1. Last-iterate convergence for optimistic CFR variants is an important problem, and extending the analysis from RTCFR+ to predictive and discounted updates is potentially useful.

  2. The paper states the assumptions for the fixed-game convergence results and carefully distinguishes convergence to a perturbed regularized equilibrium from approximation of the original game.

  3. The comparisons with RTCFR+ and Reg-CFR are relevant, and the appendices explain the intended proof innovations and tuned settings.

Critical weaknesses
  1. The algorithmic ingredients are largely established: reward transformation, perturbation, regularization, RTCFR+, PCFR+, and PDCFR+. The paper should make the non-routine theoretical increment relative to RTCFR+ much clearer.

  2. The fixed-game theorems do not by themselves give an explicit convergence guarantee for the changing-reference outer loop with finite phase lengths. The original-game gap bound contains an inner-solver error, but the required phase-length or stopping-residual condition is not stated as an end-to-end iteration guarantee.

  3. Theorem 5.1 is described as a convergence rate, but it is primarily an approximation-error bound rather than an explicit total-iteration or computation bound. The experimental comparisons also need matched RT schedules to isolate the source of improvements.

Questions for authors
  1. Relative to RTCFR+, which theorem is the principal nontrivial extension, and which proof step is essential for prediction or discounting?

  2. Is there an end-to-end guarantee for Algorithm 1 with the stated geometric schedules and finite phase lengths?

  3. Can the authors compare RTCFR+, RTPCFR+, and RTPDCFR+ under the same perturbation, regularization, and reference-update schedules?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.