# Stable-Predictive Optimistic Counterfactual Regret Minimization

arXiv: https://arxiv.org/abs/1902.04982 · HTML: https://mlsanity.com/paper/1902.04982/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2019.

## Built on by (most cited first, 21 of 21)

- [Suspicion-Agent: Playing Imperfect Information Games with Theory of Mind Aware GPT-4](https://mlsanity.com/paper/2309.17277/) (2023)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Anytime PSRO for Two-Player Zero-Sum Games](https://mlsanity.com/paper/2201.07700/) (2022)
- [Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent](https://mlsanity.com/paper/2110.04961/) (2021)
- [Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent](https://mlsanity.com/paper/2404.13891/) (2024)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [Optimistic and Adaptive Lagrangian Hedging](https://mlsanity.com/paper/2101.09603/) (2021)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [Constant Individual Regret in General Games](https://mlsanity.com/paper/2608.31166/) (2026)
- [On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games](https://mlsanity.com/paper/2410.23398/) (2024)
- [On the Power of Perturbation under Sampling in Solving Extensive-Form Games](https://mlsanity.com/paper/2501.16600/) (2025)
- [DecisionHoldem: Safe Depth-Limited Solving With Diverse Opponents for Imperfect-Information Games](https://mlsanity.com/paper/2201.11580/) (2022)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games: Corrections](https://mlsanity.com/paper/2205.12031/) (2022)
- [Reciprocal Learning](https://mlsanity.com/paper/2408.06257/) (2024)
- [GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay](https://mlsanity.com/paper/2609.11923/) (2026)

## Abstract (arXiv)

The CFR framework has been a powerful tool for solving large-scale extensive-form games in practice. However, the theoretical rate at which past CFR-based algorithms converge to the Nash equilibrium is on the order of O(T-1/2), where T is the number of iterations. In contrast, first-order methods can be used to achieve a O(T-1) dependence on iterations, yet these methods have been less successful in practice. In this work we present the first CFR variant that breaks the square-root dependence on iterations. By combining and extending recent advances on predictive and stable regret minimizers for the matrix-game setting we show that it is possible to leverage "optimistic" regret minimizers to achieve a O(T-3/4) convergence rate within CFR. This is achieved by introducing a new notion of stable-predictivity, and by setting the stability of each counterfactual regret minimizer relative to its location in the decision tree. Experiments show that this method is faster than the original CFR algorithm, although not as fast as newer variants, in spite of their worst-case O(T-1/2) dependence on iterations.