Counterfactual Regret Minimization

Counterfactual Regret Minimization (CFR) finds good strategies in imperfect information games. We'll focus on zero-sum games.

In rock-paper-scissors the equilibrium is for both players to play uniformly at random. If you play rock more than 13\tfrac13 of the time, I can play more paper and win on average. At the uniform strategy there is nothing to exploit. The goal of CFR is to compute an equilibrium.

# Regret

The regret for action aa is what you would have earned by playing aa minus what you actually earned. Positive regret means aa would have been better; negative regret is the other way around.

Ideally, suppose we score a win as +1+1, a tie as 00 and a loss as −1-1. Then, say you play rock and the opponent plays paper. I got −1-1. Paper would have got 00 and scissors +1+1. So the regrets for this round are

rock: −1−(−1)=0-1 - (-1) = 0
paper: 0−(−1)=10 - (-1) = 1
scissors: +1−(−1)=2+1 - (-1) = 2

Let u(a,st)u(a, s^t) be what action aa would have earned against the opponent's play sts^t in round tt, and u(σt,st)u(\sigma^t, s^t) be what my strategy σt\sigma^t actually earned, the cumulative regret of aa after TT rounds is

RT(a)=∑t=1T[ u(a,st)−u(σt,st) ].\begin{equation} R^T(a) = \sum_{t=1}^{T} \Big[\, u(a, s^t) - u(\sigma^t, s^t) \,\Big]. \end{equation}

# Regret matching

Regret matching plays each action with probability proportional to its positive cumulative regret,

σT+1(a)=RT(a)+∑bRT(b)+,x+=max⁡(x,0),\begin{equation} \sigma^{T+1}(a) = \frac{R^T(a)^+}{\sum_b R^T(b)^+}, \qquad x^+ = \max(x, 0), \end{equation}

and uniformly at random if no regret is positive. It is basically, the natural response to regret which is playing the actions you regret not playing more often. Its cumulative regret grows at most like T\sqrt{T}, so average regret RT(a)/TR^T(a)/T goes to zero like 1/T1/\sqrt{T}.

# Equilibrium

Suppose we let both players use regret matching against each other.

In a two-player zero-sum game, if both players have average regret at most ε\varepsilon, then their average strategies form a 2ε2\varepsilon-Nash equilibrium.

The average strategy is

σˉT=1T∑t=1Tσt\begin{equation} \bar\sigma^T = \frac{1}{T}\sum_{t=1}^T \sigma^t \end{equation}

Low regret implies that no fixed action would have done much better against the opponent's play on average. If that holds for both players, neither average strategy can be exploited by much, which is approximate equilibrium.

# Counterfactual value

In most games players take turns and can't see everything. So it is quite naive to assume that a strategy is a row of a table because there would be exponentially many rows. CFR instead runs a small regret matcher at each information set II, a set of game states hh. CFR runs regret matching separately at every information set. Each matcher needs a payoff for the actions at II, which is the counterfactual value:

vi(σ,I)=∑h∈Iπ−iσ(h)∑z : h⊑zπσ(h,z) ui(z).\begin{equation} v_i(\sigma, I) = \sum_{h \in I} \pi_{-i}^{\sigma}(h) \sum_{z \,:\, h \sqsubseteq z} \pi^\sigma(h, z)\, u_i(z). \end{equation}

πσ(h,z)\pi^\sigma(h, z) is the probability that play goes from hh to zz, and ui(z)u_i(z) is player ii's payoff there. Basically, the inner sum is the expected payoff from hh onward. zz ranges over the end states reachable from hh. The outer sum weights each h∈Ih \in I by π−iσ(h)\pi_{-i}^\sigma(h) the probability that chance and the opponent play to hh, and adds them up. Our own reach probability πiσ(h)\pi_i^\sigma(h) is left out, so viv_i is the value of II as if we had played to reach it. That is what makes it counterfactual, and it lets every information set be treated as its own regret problem, even ones we rarely reach.

# Counterfactual regret

Let σI→a\sigma_{I \to a} be σ\sigma except that player ii always plays aa at II. The counterfactual regret of aa at II is Eq. 1 with payoffs replaced by counterfactual values:
RiT(I,a)=∑t=1T[ vi(σI→at,I)−vi(σt,I) ].\begin{equation} R_i^T(I, a) = \sum_{t=1}^{T} \Big[\, v_i(\sigma^t_{I \to a}, I) - v_i(\sigma^t, I) \,\Big]. \end{equation}

CFR is regret matching on these, separately at every information set:

σT+1(I)(a)=RiT(I,a)+∑bRiT(I,b)+.\begin{equation} \sigma^{T+1}(I)(a) = \frac{R_i^T(I, a)^+}{\sum_b R_i^T(I, b)^+}. \end{equation}

Zinkevich et al. 1 show that the regret of the whole game is at most the sum of these local regrets, so if every information set is no-regret, so is the whole strategy. By the result in the equilibrium section, the average strategy then converges to a Nash equilibrium. As in rock-paper-scissors, it's the average you keep, not the last iterate. At each II the average is weighted by our own reach πiσt(I)\pi_i^{\sigma^t}(I), since iterations where we rarely reached II barely affected how we played.

Here are some practical CFR implementations worth reading:

OpenSpiel
OpenSpiel Deep CFR: the PyTorch version.
Neller and Lanctot's tutorial: more detailed tutorial.

# References

  1. [1]
    M. Zinkevich, M. Johanson, M. Bowling and C. Piccione, Regret Minimization in Games with Incomplete Information, NeurIPS 2007.
← All notes

© 2026 by Divin. Design inspired by Goodfire