Beyond KL Divergence: General Payoff Perturbations in Extensive-Form Games

Payoff perturbation is a useful principle for last-iterate convergence in games, but existing analyzes of behavioral-form Follow-the-Regularized-Leader (FTRL) in extensive-form games have focused mainly on a KL reward transformation. We use a strongly convex potential to construct Bregman-based payoff adjustments at each history–action pair relative to a anchoring strategy profile, and show that these adjustments make a global Lyapunov function decrease. Under explicit regularity assumptions, this yields last-iterate convergence of continuous-time perturbed FTRL (PFTRL) to a stationary point of the modified game when the anchoring strategy profile is held fixed. We instantiate the framework with KL and reverse-KL perturbations and derive a specialized perturbation and convergence result for two-player zero-sum games. Building on anchoring strategy updates from prior work, we also analyze an idealized outer iteration that solves each modified game exactly before updating the anchoring strategy profile; this result does not cover the finite-inner-loop discrete-time implementation. Experiments on two-player zero-sum benchmarks show that discrete-time PFTRL substantially reduces last-iterate exploitability, while perturbed CFR+ variants remain the strongest solver-level baselines in most settings.