- 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 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 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 information set (i.e. matrix game). It does not cover full extensive-form trees, actions. More importantly, it bounds the squared distance to the regularized fixed point , 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.
- 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 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?