# Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselines

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2018.

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

- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games](https://mlsanity.com/paper/2102.06973/) (2021)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [Solving Large-Scale Extensive-Form Network Security Games via Neural Fictitious Self-Play](https://mlsanity.com/paper/2106.00897/) (2021)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [CFR-MIX: Solving Imperfect Information Extensive-Form Games with Combinatorial Action Space](https://mlsanity.com/paper/2105.08440/) (2021)
- [Hierarchical Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/2305.17327/) (2023)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [Look-ahead Reasoning with a Learned Model in Imperfect Information Games](https://mlsanity.com/paper/2510.05048/) (2025)
- [D2CFR: Minimize Counterfactual Regret with Deep Dueling Neural Network](https://mlsanity.com/paper/2105.12328/) (2021)
- [Deep (Predictive) Discounted Counterfactual Regret Minimization](https://mlsanity.com/paper/2511.08174/) (2025)
- [AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games](https://mlsanity.com/paper/2608.06362/) (2026)
- [Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms](https://mlsanity.com/paper/2112.10890/) (2021)
- [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)
- [Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play](https://mlsanity.com/paper/2309.03084/) (2023)
- [NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2603.06977/) (2026)
- [CFR without Unbiasedness: Deterministic Guarantees for Persistent Public-Chance Schedules](https://mlsanity.com/paper/2608.14761/) (2026)
- [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)
- [SafeAdapt-Poker: Counterfactual Risk Calibration for Budgeted Adaptation under Opponent Shift](https://mlsanity.com/paper/2610.20473/) (2026)

## Abstract (arXiv)

Learning strategies for imperfect information games from samples of interaction is a challenging problem. A common method for this setting, Monte Carlo Counterfactual Regret Minimization (MCCFR), can have slow long-term convergence rates due to high variance. In this paper, we introduce a variance reduction technique (VR-MCCFR) that applies to any sampling variant of MCCFR. Using this technique, per-iteration estimated values and updates are reformulated as a function of sampled values and state-action baselines, similar to their use in policy gradient reinforcement learning. The new formulation allows estimates to be bootstrapped from other estimates within the same episode, propagating the benefits of baselines along the sampled trajectory; the estimates remain unbiased even when bootstrapping from other estimates. Finally, we show that given a perfect baseline, the variance of the value estimates can be reduced to zero. Experimental evaluation shows that VR-MCCFR brings an order of magnitude speedup, while the empirical variance decreases by three orders of magnitude. The decreased variance allows for the first time CFR+ to be used with sampling, increasing the speedup to two orders of magnitude.