Faster Game Solving via Initial Regret Reduction

Counterfactual regret minimization (CFR) is the leading framework for solving two-player zero-sum imperfect-information games and underlies recent superhuman poker AI. A remaining source of inefficiency in CFR and CFR+ is uniform initialization: because every action is explored equally at the start, clearly suboptimal actions depress the average counterfactual value and inflate the initial positive regrets of the remaining actions, forcing many iterations to separate the viable actions that matter in equilibrium. Discounted variants such as DCFR and PDCFR+ mitigate this effect only indirectly by decaying accumulated regrets over many iterations. We propose initial regret reduction (IRR), a one-time reduction that rescales the first positive accumulated regret by a factor of at most one, preserves its direction, and leaves every later update unchanged. The factor comes from computing the regret of that round as if it had been played with a mixture of the uniform strategy and the next strategy induced by the first positive regret. We prove that the single reduction never enlarges the first positive regret, and that IRR-RM+ and IRR-PRM+ preserve the $O(1/\sqrt{T})$ no-regret rate. Combined with PCFR+, IRR-PCFR+ attains the lowest average-iterate exploitability among the compared algorithms on benchmark imperfect-information games other than the heads-up no-limit Texas hold'em subgames, where DCFR remains superior.