Adaptive Local Perturbation Counterfactual Regret Minimization

Imperfect-information games can admit Nash equilibria whose behavior at low- probability or unreachable information sets is strategically implausible. We in- troduce ALP-CFR, a counterfactual-regret-minimization framework that uses information-set-level local perturbations and adapts their magnitude from cumu- lative reach information. Under-reached descendants generate protection requests that propagate toward ancestors, allowing the method to allocate larger local per- turbations where downstream behavior receives too little effective reach. This pa- per develops the framework, its full-tree regret analysis, and the conditions needed for a sampling-based extension. We establish the scope of the claims carefully: the results concern perturbed-game regret, vanishing local perturbations, and sam- pling estimators under explicit assumptions; they do not, in general, establish convergence to an extensive-form perfect equilibrium (EFPE). Experiments on imperfect-information benchmark games will evaluate the effect of the protection mechanism on Nash and information-set regret metrics.