Parameter-Free Last-Iterate Convergence of Optimistic and Discounted Counterfactual Regret Minimization

Counterfactual regret minimization (CFR) with regret matching${}^{+}$ local minimizers is the standard way to solve two-player zero-sum games in extensive form (EFGs), but only its average strategy is guaranteed to converge. The reward-transformation framework restores them by solving a sequence of auxiliary games in which every action keeps probability at least $\gamma$ and a quadratic penalty $\mu$ pulls toward a reference strategy; RTCFR${}^{+}$ showed that plain CFR${}^{+}$ converges in the last iterate on every such fixed game for any step size and any initialization. The variants that are actually used, namely predictive CFR${}^{+}$ and the discounted variants DCFR${}^{+}$ and PDCFR${}^{+}$, had no such guarantee. We study one family of local minimizers, predictive discounted regret matching${}^{+}$, that contains all of them. We show that the strategy sequence of any member depends on the step size and the initialization only through their ratio, and use this invariance to prove that in every perturbed regularized EFG the last iterate converges to the unique equilibrium for any step size and any initialization, provided the total discount ${\sum }_t(1-d_t)$ is finite. The DCFR schedule satisfies the condition exactly when its exponent exceeds one, and without prediction a constant discount cannot converge on nondegenerate matrix games unless it hits the equilibrium in finite time. Every instance has constant regret in the perturbed regularized game, hence an $O(1/T)$ average-iterate rate there, and the last iterate is an $O(\mu +\gamma )$-equilibrium of the original game. Experiments confirm the summability condition and the constant-discount obstruction, show the regret plateau the constant-regret bound predicts, and show that optimism turns the slow last-iterate convergence of regret matching${}^{+}$ into fast convergence: with the published RTCFR${}^{+}$ hyperparameters, RT-PCFR${}^{+}$ ends below $10^{-15}$ on most benchmark EFGs and converges on a matrix game where both plain PCFR${}^{+}$ and RTCFR${}^{+}$ fail. Parameter-freeness is the property the reward-transformation framework needs, and it survives both optimism and discounting: within each perturbed regularized game the practical variants have the same guarantee as CFR${}^{+}$, with no retuning of step size or initialization.