acceptodds
Withdrawn from ICLR 2027

Improving Last-Iterate Convergence in Monte Carlo Counterfactual Regret Minimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Counterfactual regret minimization (CFR) and its Monte Carlo sampled variants (MCCFR) are the standard solvers for two-player zero-sum extensive-form games and the engine behind superhuman poker programs. Their guarantees cover the *average* strategy, which is cheap to track offline. A deployment that acts with the current strategy, for instance online adaptation to a changing opponent, has only the *last* iterate to act on. Under MCCFR sampling the last iterate of the regret-matching family settles at a noise floor and improves far more slowly than the average. We introduce reward-transformed MCCFR (RT-MCCFR), a regret matching plus (RM) algorithm whose last iterate lowers this floor and keeps falling from 5M to 40M node visits in our sweeps. A perturbation keeps every reach probability bounded below, an anchor regularization makes each local subproblem strongly concave, and a windowed average of the recent iterates is the output that the regularization pulls toward, at constant memory per information set. On five games under external sampling (ES) and outcome sampling (OS) with 10 seeds, the windowed anchor is below the best baseline under the same window rule in six of ten cells and above it in four, one cell resolved in each direction, and below every baseline last iterate; the raw last iterate is below every RM-family last iterate. Multiplying the budget by eight from an exploration transient lowers the anchor by a factor of 1.6 to 23 where RM moves by at most 30%, and past that budget no anchor change is resolved. On the ES noise axis the floor rises with exponent 0.47 and bootstrap half-width 0.10 in the total sampling variance, consistent with the square-root heuristic of the self-normalized RM step size, and it falls roughly inversely in the anchor strength over the working range. We prove an inverse-square-root last-iterate convergence bound, in squared distance to the regularized fixed point, in a stylized push regime.

Primary area:
reinforcement learning
Keywords:
Monte Carlo Counterfactual Regret Minimization, Last-iterate, regularization, multi-agent reinforcement learnning

Reviews

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

The paper introduces RT-MCCFR+, a reward-transformed variant of RM+ for Monte Carlo counterfactual regret minimization (MCCFR). At each information set, RT-MCCFR+ perturbs the executed strategy by mixing it with a uniform distribution and regularizes the sampled counterfactual value toward a slowly moving anchor. The anchor is a windowed average of recent played strategies and is also the reported output, giving constant memory per information set. This work also establishes last-iterate convergence for a single 2×22\times 2 information set, bounding squared distance to the regularized fixed point at an inverse-square-root rate. Experiments on five extensive-form games under external sampling (ES) and outcome sampling (OS) validate the effectiveness of the proposed perturbation and regularization based MCCFR lagorithm.

Critical strengths

1. A simple and new algorithm for an important problem. Last-iterate convergence for MCCFR variants is a critical problem in solving truly large-scale extensive-form games, like Heads-Up No-Limit poker. Existing theoretical results for MCCFR only guarantee average-iterate convergence, which requires computation of averaged strategy over all iterations. The paper shows that the last-iterate strategy of Monte-Carlo CFR variants can stall at a noise floor, and it proposes a simple, constant-memory modification that can wrap existing RM+ minimizers under the perturbation and regularization framework.

2. An explicit last-iterate convergence rate of proposed MCCFR variant. By utilizing Lyapunov arguments, this paper also provides explicit last-iterate convergence guarantee for the algorithm in 2×22\times 2 matrix games.

3. Broad empirical study. The extensive empirical evaluation includes five games, two samplers, 10 seeds, paired significance tests, matched-window controls, budget sweeps, and noise-injection experiments. The authors also report unfavorable or unresolved cells. This makes the empirical section informative even where the gains are mixed.

Critical weaknesses

1. The theory is too narrow to support the main ``last-iterate convergence'' framing. Theorem 4.1 is proved only for a single 2×22\times 2 information set (i.e. matrix game). It does not cover full extensive-form trees, n≥3n \ge 3 actions. More importantly, it bounds the squared distance to the regularized fixed point x^⋆\hat{x}^\star, not to a Nash equilibrium of original matrix game. Thus the paper does not establish last-iterate convergence to the equilibrium for MCCFR in the original EFGs, instead it just establishes a stylized rate to a simplified perturbed matrix game.

2. The reasonableness of the assumptions in last-iterate convergence result. The last-iterate convergence relies on several assumptions, i.e. M, A-var, A-init, A-push. Are these assumptions reasonable enough to hold in practical EFG/NFG instances? For example, the per-step sampling variance can be lower bounded in regularized and perturbed EFG/NFG? If not uniformly hold in all EFGs, the basic examples of EFG satisfying such assumptions should be added to demonstrate the reasonableness. In my opinion, such assumptions seem truly strong to hold in practice.

3. Unclear explanations for the improvement of the last-iterate convergence of MCCFR. I am not so sure what is the main contribution for the improvement of last-iterate convergence of the proposed MCCFR variant. Is it due to the introduction of perturbation and regularization technique in MCCFR, or is it mainly from the constant-memory storage of recent strategies? If the improvement is mainly from the former, then the novelty of this algorithm seems not new, because it has been identified in [liu et al 2023 iclr] and [Masaka et al., 2025] that regularization can improve the last-iterate convergence of CFR variants.

4. Lack comparisons with bandit-optimization based algorithms in EFG. I know this paper mainly focuses on the last-iterate convergence of RM-type algorithms, but there have existed bandit learning based algorithms with last-iterate convergence guarantee in solving EFGs, like virtual transition probability based OMD. Besides, even the model-free algorithms with only average-iterate convergence also exhibit last-iterate convergence in EFG. More comparisons with these baselines should be added.

Other minor problems:

5. Unprecise statement.

(1) In line 54, "Under MCCFR sampling the last iterates of the regret-matching (RM) family, regret matching plus (RM+) and its predictive variants, settle at a noise floor", here additional citation should be added. In fact, [A3] has demonstrated theoretically that RM+ and its predictive version fails to converge in last-iterate in certain matrix games, let alone their Monte-Carlo sampling variants.

(2) In line 58, "The theory of last-iterate play covers normal-form games under full feedback (Meng et al., 2025b; Zhang et al., 2025) and, in extensive-form games, the full-feedback RTCFR+ of Meng et al. (2025a)." Precisely speaking, Zhang et al., 2025 did not establish the last-iterate convergence for their proposed IREG-PRM algorithm, they only prove average-iterate and best-iterate convergence guarantee. Besides, Meng et al. (2025a) actually only obtain the last-iterate convergence of CFR+ in regularized and perturbed EFGs, not in original unregularized EFGs. Such last-iterate convergence for CFR-type algorithms was first proposed in [liu et al 2023 iclr] where the local regret minimizer is OMD but not RM+.

6. Miss explanations. Line 161, no formal explanations for the strongly concave property. Line 172, Section 5 without reference. Lines 226/231 in the pseudo-code of Algorithm 1, too many semicolons.

References

[A1] Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback. ICML2025

[A2] Learning in two-player zero-sum partially observable Markov games with perfect recall. NIPS 2021.

[A3] Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games. NIPS 2025

Questions for authors

Besides the above weaknesses, I have another question.

  1. I am very curious that whether the last-iterate convergence results can be extended to the general matrix game setting (I know it is hard to generalize to the EFG setting), because Theorem 4.1 only gives results for 2×22\times 2 matrix game. Can you provide any tree-level or n ≥ 3 action extension of Theorem 4.1, even under stronger assumptions? If not, how should practitioners interpret the theory for real EFGs?
Reviewer_dfJTOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper presents a new Monte Carlo CFR variant based on regret-matching+. It uses a reward transformation, regularization, time-windowed "recent past averages" as an "anchor" strategy to inform the MCCFR updates. The new algorithm can be applied to both standard MCCFR sampling methods (outcome sampling - OS, and external sampling - ES).

On a number of games the authors show several results comparing many baselines, including an ablation study to demonstrate the effect of time-windowed average and alternatives.

Critical strengths

RM+ has been hard to get working with the combination of Monte Carlo sampling, which is why not many variants have combined the two. This paper presents the first demonstrable success of combining the two.

The convergence is studied in the last iterate, which is good -- separate averaging is not required (except for the time-windowed anchors).

The idea of using the average or recent-approximation thereof to anchor the strategies makes sense, especially when using it to transform rewards, as it provides a somewhat stable "baseline" for comparison. In fact, equation (2) looks like a control variate in a similar sense as VR-MCCFR (Schmid et. al '19) cited by the authors. Note also that the average strategy has been used to modify the sampling strategy, see Gibson et al. 2012, Efficient Monte Carlo Counterfactual Regret Minimization in Games with Many Player Actions.

In practice, the method seems to work quite well on the tested domains, with a few potential caveats (see questions section).

Critical weaknesses

The theoretical contribution (Theorem 4.1) only applies in a very restricted setting: a matrix game with 2 actions per player, with several other restrictions. And even for this restricted case, the steps required seems quite comple.

Most (almost all-- except matching pennies) of the empirical results are in games that do not satisfy the assumptions required by Theorem 4.1. So there are no guarantees that the method will converge to an equilibrium outside of the very restricted case of a matrix game with 2 actions per player.

The authors are mostly upfront about this in the paper itself, but I found the last line of the abstract misleading (leaning a bit toward over-claiming): "We prove an inverse-square-root last-iterate convergence bound, in squared distance to the regularized fixed point, in a stylized push regime".. where a "stylized push regime" is actually a "matrix game with 2 actions per player that must have bounded per-step sample variance, a fixed point in the interior with nonzero margin, constraints on the best response curvature, and a specific fallback threshold".

Questions for authors

How is it possible that \mu = 1 works so well? Looking at equation (2), an entry in the sampled counterfactual value \hat_{u}_I could vary between a huge range +/- (U / ( \gamma/|A| ) ^ depth), but then you subtract 1 * (x_i - r_i), both x_i and r_i are probabilities, so that difference is bounded to [-1,1]. Sampled counterfactual values could always dominate? Also shouldn’t \mu be different for ES and OS?

In Figure 1, why is the NashConv flat for the first 2*(10^6) touches for both RT-MCCFR+ variants? It is not clear why this method would suddenly only start working after a certain burn-in period. This seems like it can be a concern if RT-MCCFR+ was used in the online setting motivated by the intro (and contrasted to e.g. full-width CFR algorithms)

Why no comparison to standard ES or OS ? I strongly suspect the NashConv graph of standard ES would look very good in Fig 1, possibly better than any line on the graph.. and as mentioned in the early part of the paper, it doesn't cost much to maintain the average strategy online, so there's not much advantage to emphasize the comparison to be only between last iterate approaches only.

Reviewer_urb9OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a new MCCFR variant that aims to make the last-iterate converge faster, by reducing the noise in the strategy from timestep to timestep. The approach builds off of an existing variant with a last-iterate convergence guarantees and then smooths it with a regularization term to keep the current strategy close to a windowed average of recent strategies. The provided noise reduction is shown to have faster convergence in two toy games.

Critical strengths

None

Critical weaknesses

This paper is written by an LLM from abstract to appendix, which makes much of the writing impenetrable with invented jargon, unclear motivations, and extremely dense prose that says far less than the word count suggests. It's basically unpublishable on this alone. Given the effort the authors put into writing this paper, I'm reluctant to spend further time enumerating the issues.

Beyond the poor presentation, there are still other critical weaknesses:

  1. Motivation for last-iterate convergence is not at all clear: if we're interested in adapting to a changing opponent then the average regret guarantees are already sufficient for strong play. Why would I need the last-iterate to converge at all? There may be some motivation around not needing to store a second full copy of the average strategy reducing the overall memory footprint. However, the paper's solution keeps a windowed average, exactly returning this second full-strategy in memory.
  2. The paper is about last-iterate but the results that are emphasized are on the anchor policy, which itself is a running average, not the strategy the agent is playing at the current time step. This is completely misleading.
  3. The proof is over 12 pages long, involves a half of page of assumptions, and all for just proving a regret-bound on the last iterate with 1 information set and 2 actions.
  4. The notation varies throughout the paper (in a true LLM fashion). For example, they introduce regret matching in the usual notation σIt(a)\sigma^t_I(a) as the player's strategy and u^I(a)\hat u_I(a) for the sampled counterfactual value at time tt for information set II. But then ignore this switching to x^I\hat x_I and qIq_I when introducing their method (with barely a node to defining these terms).

I'm sure there's another dozen problems, if I read it more closely.

Questions for authors

None

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

Related papers

Discussion (0)

Sign in to comment.