Last-Iterate Convergence in Adaptive Regret Minimization for Approximate Extensive-Form Perfect Equilibrium

Hang Ren, Xiaozhen Sun, Tenghao Ma, Jiajia Zhang, Xuan WangFrontiers in Artificial Intelligence and Applications 2025 · DOI · OpenAlexGitHub resource

Abstract

This paper introduces RTCFR, a novel algorithm that achieves "last-iterate" convergence for finding refined Nash Equilibria in complex, sequential games. By combining reward transformation with a new adaptive perturbation strategy (the ISNE metric), the authors provide a way to compute strategies that are robust even when opponents make mistakes, significantly outperforming current state-of-the-art methods in both speed and accuracy.

Introduction: The Problem with Nash Equilibrium

In game theory, the Nash Equilibrium (NE) is the gold standard for "optimal" play. However, NE has a major flaw in Extensive-Form Games (EFGs)—games like Poker where players move sequentially and have hidden information. NE assumes everyone plays perfectly. If a player makes a "mistake" and ends up in a part of the game tree that shouldn't be reached under perfect play, the NE strategy often fails to provide a robust response, leading to suboptimal behavior.

To fix this, researchers use Extensive-Form Perfect Equilibrium (EFPE). EFPE assumes every player has a tiny chance of making a "tremble" (a mistake), forcing the strategy to be optimal everywhere in the game tree. The challenge lies in computing EFPE efficiently; existing algorithms are often memory-intensive and slow, struggling with the trade-off between convergence speed and accuracy.

Methods: RTCFR and Adaptive Perturbation

The authors propose two major innovations to solve these hurdles:

  1. RTCFR (Reward Transformation Counterfactual Regret Minimization): Standard CFR algorithms converge on average. By adding a "Reward Transformation" (a form of regularization), the authors force the algorithm to achieve last-iterate convergence. This means the current strategy is the best one, which is much more compatible with modern deep learning architectures.
  2. Adaptive Perturbation via ISNE: Instead of picking a fixed mistake probability ($\epsilon$), the authors developed the Information Set Nash Equilibrium (ISNE) metric to measure "local" stability. The algorithm starts with a large $\epsilon$ to explore the game tree quickly and then dynamically shrinks it as the strategy stabilizes, eventually converging to a high-precision EFPE.
  3. Basis Mapping: To handle the math of "forced mistakes," they map the original game's strategy space into a "perturbed" space using non-standard basis matrices, ensuring that every action maintains a minimum probability $\epsilon$.
Standard vs. perturbed strategy spaces.

Experimental Evaluation

The researchers evaluated their approach on several standard benchmark games:

  • Kuhn Poker and Leduc Poker (3 and 5 ranks): Testing complexity and betting rounds.
  • Goofspiel (3 and 4 ranks): A card-bidding game testing psychological play.
  • Liar’s Dice (5 and 6 ranks): A large-scale bluffing game serving as a stress test for scalability.

Key Results

RTCFR+ (the adaptive version) consistently achieved lower exploitability than state-of-the-art algorithms like CFR+, EGT, and RegOMWU. A key insight was that focusing on Information Set Regret allows the algorithm to detect when specific parts of the game tree have "settled," enabling local reductions in perturbation for higher efficiency.

Convergence performance across multiple benchmark games.

In games like Liar's Dice (6), RTCFR+ converged to a near-perfect equilibrium in just 20 iterations, whereas traditional methods required significantly more computational effort. The adaptive perturbation successfully reached an ISNE regret level below $10^{-10}$ in several benchmarks, indicating an extremely high-quality approximation of the "perfect" equilibrium.

Conclusion and Future Work

RTCFR proves that last-iterate convergence is a viable path for scaling refined equilibrium computation. While the method introduces new hyperparameters like the RT weight ($\mu$), it observed much faster $O(1/T)$ performance in practice than the theoretical $O(1/\sqrt{T})$ rate. The next logical step is integrating RTCFR with Deep Reinforcement Learning to handle games with state spaces far too large for tabular methods.

Summary updated

Abstract

The Nash Equilibrium (NE) assumes rational play in imperfect-information Extensive-Form Games (EFGs) but fails to ensure optimal strategies for off-equilibrium branches of the game tree, potentially leading to suboptimal outcomes in practical settings. To address this, the Extensive-Form Perfect Equilibrium (EFPE), a refinement of NE, introduces controlled perturbations to model potential player errors. However, existing EFPE-finding algorithms, which typically rely on average strategy convergence and fixed perturbations, face significant limitations: computing average strategies incurs high computational costs and approximation errors, while fixed perturbations create a trade-off between NE approximation accuracy and the convergence rate of NE refinements. To tackle these challenges, we propose an efficient adaptive regret minimization algorithm for computing approximate EFPE, achieving last-iterate convergence in two-player zero-sum EFGs. Our approach introduces Reward Transformation Counterfactual Regret Minimization (RTCFR) to solve perturbed games and defines a novel metric, the Information Set Nash Equilibrium (ISNE), to dynamically adjust perturbations. Theoretical analysis confirms convergence to EFPE, and experimental results demonstrate that our method significantly outperforms state-of-the-art algorithms in both NE and EFPE-finding tasks.
BibTeX
@inproceedings{ren2025last,
  author = {Hang Ren and Xiaozhen Sun and Tenghao Ma and Jiajia Zhang and Xuan Wang},
  title = {{Last-Iterate Convergence in Adaptive Regret Minimization for Approximate Extensive-Form Perfect Equilibrium}},
  booktitle = {Frontiers in Artificial Intelligence and Applications},
  year = {2025},
  doi = {10.3233/faia251374},
}

Loading related content...

Figure