Exact Averaging And Discounting for Monte Carlo Counterfactual Regret Minimization

Counterfactual regret minimization (CFR) is the standard method for solving twoplayer zero-sum games with imperfect information, and its error bound concerns an average strategy that weights iteration t at an information set by the probability that the player’s own actions lead there. Tabular CFR accumulates that average exactly, whereas outcome-sampling Monte Carlo CFR updates only the information sets on one sampled playthrough per player and iteration, while the average keeps changing at the information sets it skips. The rules in use account for them differently, and which average they return depends on where they are applied. On the player’s own playthrough the opponent does not explore, so an information set can stay unvisited while its weight keeps growing. We show that the missed weight is already recorded in the player’s tables, as the growth of the exact sum at the predecessor’s action leading to the information set. Reading it at each visit, on the way down, and once at the end returns the exact reach-weighted average of the strategies the sampled run produced, for uniform, linear and polynomial weights alike. A prefix-product table replays skipped discount factors at one subtraction. The coefficient distortion of a skipped positive-regret factor is bounded when discounted CFR’s exponent exceeds one, and unbounded below that and for the strategy sum. On nine games from 12 to 524,288 information sets, our implementation of OpenSpiel’s rule returns strategies 1.7 to 9 times as exploitable as the exact average after 107 iterations, a gap that grows with training, while the opponent’s-playthrough rule stays within five per cent and the exact rule costs 0.3–4.5% more time. Both are cheap enough to be defaults for outcome-sampling implementations.