Counterfactual Regret Minimisation

Heads-up limit Texas hold'em has \(3.19 \times 10^{14}\) points at which a player must decide something without seeing the opponent's cards. In 2015 a strategy for it was computed with an exploitability of 0.986 milli-big-blinds per game, so close to perfect that a human lifetime of play could not show statistically that it is not an exact equilibrium. The computation took 1,579 iterations of CFR+ and 900 core-years (Bowling, Burch, Johanson and Tammelin, 2015, Heads-up limit hold'em poker is solved, Science 347(6218)). Every iteration was a pass of the same local update applied independently at every decision point.

Equilibria as Learning Targets explains why no-regret dynamics reach equilibrium in two-player zero-sum games. This concept is the algorithm that makes no-regret learning feasible in sequential games with hidden information, where the number of pure strategies is exponential in the size of the tree.

Regret, made local

An information set \(I\) groups the game histories a player cannot tell apart, such as every deal in which they hold the same cards and saw the same betting. A strategy \(\sigma_i(I)\) is a distribution over actions at each one. Let \(\pi^{\sigma}_{-i}(I)\) be the probability of reaching \(I\) from chance and the opponents' actions alone, assuming player \(i\) played to get there. That is the "counterfactual" weight: it asks what \(I\) is worth if \(i\) had tried to reach it.

Zinkevich, Johanson, Bowling and Piccione define the cumulative counterfactual regret for not having always played action \(a\) at \(I\),

where \(u_i(\sigma, I)\) is player \(i\)'s expected utility given that \(I\) is reached and \(\sigma|_{I\to a}\) is \(\sigma\) with action \(a\) forced at \(I\) (Zinkevich et al., 2007, Regret Minimization in Games with Incomplete Information, NeurIPS). Their Theorem 3 is the decomposition that makes everything work: a player's overall regret is at most the sum over information sets of the positive part of these local regrets. Minimise each local regret independently and the global regret follows.

Each local problem uses regret matching: play actions in proportion to positive cumulative regret,

and uniformly if no regret is positive. Theorem 4 bounds average overall regret by \(\Delta_{u,i}\,|\mathcal{I}_i|\,\sqrt{|A_i|}/\sqrt{T}\), with \(\Delta_{u,i}\) the range of utilities, \(|\mathcal{I}_i|\) the number of information sets and \(|A_i|\) the largest action count. In a two-player zero-sum game, if both players' average regret is below \(\epsilon\), the average strategy profile is a \(2\epsilon\)-Nash equilibrium. Halving \(\epsilon\) costs four times the iterations.

One update, by hand

At some information set with actions fold, call and raise, suppose cumulative regrets are \((-2, 3, 1)\). Regret matching plays \((0, 0.75, 0.25)\). This iteration, action values are \((-1, 0.5, 2)\), so the current strategy is worth \(0.75(0.5) + 0.25(2) = 0.875\). Instantaneous regrets are \((-1.875, -0.375, 1.125)\); weighted by an opponent-and-chance reach probability of 0.4 they become \((-0.75, -0.15, 0.45)\). Cumulative regrets move to \((-2.75, 2.85, 1.45)\) and the next strategy is about \((0, 0.66, 0.34)\): the raise gained weight because it would have done better.

CFR+ changes one line (Tammelin, 2014, Solving Large Imperfect Information Games Using CFR+, arXiv:1407.5042). Regret-matching+ floors the cumulative regret at zero after every update, so fold would sit at 0 rather than \(-2.75\) and could return the moment it looks good, instead of first repaying a debt. With alternating player updates and weighted averaging, it typically ran an order of magnitude faster than earlier variants.

From solved games to Libratus and Pluribus

Linear CFR weights iteration \(t\)'s regret by \(t\), so the first, near-random iteration's influence decays as \(2/(T(T+1))\) rather than \(1/T\). Brown and Sandholm's discounted family, with \(\alpha = 3/2\), \(\beta = 0\), \(\gamma = 2\), was consistently stronger than CFR+ in their experiments (Brown and Sandholm, 2018, Solving Imperfect-Information Games via Discounted Regret Minimization, arXiv:1809.04040).

Libratus combined a CFR-computed blueprint for an abstracted no-limit game with nested subgame solving during play, and beat four top professionals by 147 mbb/game over 120,000 hands (Brown and Sandholm, 2018, Superhuman AI for heads-up no-limit poker, Science 359, 418-424). Pluribus took the approach to six players. Its blueprint came from Monte Carlo Linear CFR in 8 days on one 64-core server, 12,400 core-hours and under 512 GB of memory, about $144 at the spot prices the authors quoted, and it played on two CPUs, winning 48 mbb/game with a standard error of 25 over 10,000 hands against elite professionals (Brown and Sandholm, 2019, Superhuman AI for multiplayer poker, Science 365, 885-890).

When it breaks

Outside two-player zero-sum there is no equilibrium guarantee. Pluribus's authors state plainly that their algorithms are not guaranteed to converge to a Nash equilibrium outside two-player zero-sum games, and argue that the goal should be beating humans empirically rather than a solution concept. A no-regret average in a six-player game converges at best to a coarse correlated equilibrium, which need not be safe to play.

Theory averages; practice often does not. The guarantee is for the average strategy. The hold'em computation discarded its average strategy after measuring it as more exploitable than the current one, and Tammelin reported that CFR+'s current strategy often converges on its own.

Tables scale with information sets. Tabular CFR stores regrets and average strategies for every action at every information set. No-limit games are too large, so they are abstracted, card buckets and bet sizes merged, and the solution is only an equilibrium of the abstraction. Deep CFR replaces the tables with networks (Brown et al., 2019, Deep Counterfactual Regret Minimization, arXiv:1811.00164), trading exactness for approximation error.

Exploitability is unmeasurable at full scale. Computing an exact best response in full no-limit hold'em is not practical, so strength is established by head-to-head matches with variance reduction, which bound performance against those opponents rather than against the worst case.