Invariant Last-Iterate Convergence for Optimistic Counterfactual Regret Minimization in Solving Perturbed Extensive Form Games

Counterfactual regret minimization (CFR) represents a family of online algorithms to effectively learn the (approximate) Nash Equilibrium (NE) of imperfect-information extensive-form games (EFGs). Among them, the optimistic/predictive CFR methods, which incorporates the optimism technique from online optimization to accelerate approximation to NE, often achieve superior theoretical and practical performance. However, relatively little is known about the last-iterate convergence of optimistic CFR variants. In this work, we take a step forward and provide asymptotic last-iterate convergence guarantees for two classical optimistic CFR methods (PCFR${}^{+}$ and PDCFR${}^{+}$) in solving perturbed EFGs. Specifically, we first provide last-iterate convergence for PCFR${}^{+}$ in solving perturbed regularized EFGs. Such a result holds for any step size and any initialization at each decision node, and hence is referred to as invariant last-iterate convergence for perturbed EFGs. Based on the invariance property, we develop a tighter average-regret bound than the previous one for PCFR${}^{+}$ in solving EFGs. Then, we extend our analysis to the PDCFR${}^{+}$ algorithm that discounts regrets from earlier iterations. The invariant last-iterate convergence still holds for any non-decreasing bounded sequence of discounting factors and any strategy initialization. Furthermore, we reveal that the last-iterate strategy of the above two optimistic CFR algorithms forms an approximation of the NE of original EFG. The approximation error approaches zero by setting small perturbation/regularization coefficients and enforcing the last-iterate strategy to be close to the unique NE of the perturbed regularized EFG. Experiments show that our proposed methods outperform the latest method in most medium-size EFGs, and yield comparable performance to discounted CFR in large-scale Poker games.