What Does the Average Strategy of Monte Carlo CFR Actually Average?

Counterfactual regret minimization solves two-player zero-sum games with hidden information. Its guarantee holds for the exact average, which weights each iteration at an information set by the player's own reach probability. However, outcome-sampling solvers update an information set only when a sampled traversal visits it. The original sampling algorithm adds all iterations since the previous visit at the current weight; OpenSpiel adds only the current iteration divided by its sampling probability. We follow OpenSpiel's default sampling: one traversal per player, where only the traversing player explores at a fixed rate. On three of four games, both rules are on average ten to just over fifty percent more exploitable than the exact average after a hundred thousand iterations. After ten million, both are on average two to eight times as exploitable. Since the opponent never explores on the player's traversal, an information set can stay unreached while its weight grows. Adding on the opponent's traversal instead leaves OpenSpiel's rule on average at most two percent worse than the exact average. We prove that an information set's weight between visits is the growth of the exact average's sum at the player's preceding decision, for the action leading there. Reading that growth on the player's traversal at every visit and at the end returns the exact average for at most five percent more training time in our implementation.