Dominated Actions Slow Down Counterfactual Regret Minimization

Counterfactual regret minimization (CFR) is the leading framework for solving imperfect-information games and underlies superhuman poker AI. Its fastest variants, CFR+, predictive CFR+ (PCFR+) and the discounted PDCFR+, all start every information set from the uniform strategy, and that start carries a cost. At the first iteration the baseline against which regrets are measured is the unweighted mean of the counterfactual action values, so dominated actions pull it down and every non-dominated action receives the same additive offset in its first regret. The offset is uninformative, since pairwise differences are unchanged. Regret matching+ keeps it in the cumulative regret until later updates outweigh it, so those iterations are spent separating good actions whose order the offset does not change. We propose cold-start regret attenuation (CSRA), which multiplies the first non-zero regret of each information set by a constant c ∈ (0, 1] at the moment it appears and leaves every later update verbatim. The first strategy update is unchanged, the reduction costs one additive constant in the regret bound, and a single reduction preserves the convergence rate of any base algorithm whose analysis is sequence-agnostic. CSRA is the limiting case of PDCFR+, and truncating PDCFR+’s discount after its first iteration leaves its convergence within the variation across perturbed starts. Appending k dominated actions to every decision node of a controlled experiment multiplies the iterations PCFR+ needs at k = 32 by 5.40, pushes CFR+ past the budget, and changes those of CSRA by at most a factor of 1.27. On the standard benchmarks, evaluated with perturbation ensembles because the iteration at which a single run reaches a given exploitability is not reproducible on the games with large offsets, CSRA-PCFR+ matches PDCFR+ without a discount schedule. On the two games with the largest offsets, Battleship and Small Matrix, it reaches a given exploitability 2.43 to 9.38 times faster than PCFR+ and up to 3.12 times faster than PDCFR+, and it also accelerates PDCFR+ and APCFR+. A statistic computed from the first iteration alone, the common lower bound on the first regret, separates the games where the offset is large. The uniform start of CFR is not free, and CSRA removes its cost with a single multiplication at the first regret.