Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation

Hang Ren, Yulin Wu, Shuhan Qi, Jiajia Zhang, Xiaozhen Sun, Tianzi Ma, Xuan Wang

Introduction

In computational game theory, the primary objective is often to identify a Nash Equilibrium—a strategy profile where no player can benefit by unilaterally changing their strategy. For decades, Regret Minimization algorithms, such as Counterfactual Regret Minimization (CFR), have served as the standard for solving large-scale games. However, these methods typically only guarantee average-iterate convergence, meaning the average of all strategies played over time converges to the equilibrium. This requirement necessitates storing and computing cumulative averages, which is memory-intensive and can introduce significant errors in massive games.

The Challenge of Last-Iterate Convergence

Researchers have long sought last-iterate convergence, where the final strategy produced by the algorithm is itself an equilibrium. While Reward Transformation (RT) was recently introduced to achieve this by adding regularization terms, it suffers from extreme sensitivity to parameter tuning. Manual selection of these "magic numbers" is often impractical, leading to either slow convergence or instability if the parameters are not perfectly calibrated to the specific game.

Methodology: The Adaptive RT Framework

To address these limitations, the authors propose an Adaptive Reward Transformation (RT) framework. This framework replaces static parameters with three dynamic components designed to automate and accelerate convergence.

Adaptive Reference Strategy

Instead of updating the "target" or reference strategy at fixed intervals, the algorithm monitors the exploitability of the current strategy. If the current strategy demonstrates a significant improvement over the previous reference, the reference point is updated immediately. This ensures that the regularization remains relevant to the current state of the solver throughout the training process.

The training process segmented into successive convex-concave programming (SCCP) steps with adaptive reference updates.

Adaptive Weighting ($\mu$)

The strength of the reward transformation is adjusted dynamically. When the solver is far from the equilibrium, the weight is adjusted to encourage exploration; as it nears the solution, the weight is increased to accelerate convergence toward the exact equilibrium. This avoids the "Assumption 1" trap of previous methods, which required finding an exact saddle point at every step.

Adaptive Regret Weighting

Drawing inspiration from "Discounted CFR," the framework assigns higher weights to recent regrets. By "forgetting" the noisy, sub-optimal strategies from the early stages of training, the algorithm prevents the last iterate from being anchored to initial random moves, allowing for a cleaner path to the equilibrium.

Extension to Extensive-Form Games (EFGs)

The authors extended this framework to EFGs—sequential games with hidden information—using a laminar regret decomposition. This ensures mathematical stability across complex game trees, allowing the adaptive benefits to scale beyond simple matrix games to complex environments like Poker.

Experimental Evaluation

The framework was tested across a variety of benchmarks to demonstrate its versatility:

  • Normal-Form Games: Randomly generated $10 \times 10$ matrix games.
  • Kuhn and Leduc Poker: Standard benchmarks for sequential decision-making under uncertainty.
  • Goofspiel and Liar’s Dice: Games involving complex strategy, bidding, and bluffing.

Key Results and Insights

The adaptive framework demonstrates several critical advantages over existing state-of-the-art methods:

  • Linear Convergence: Unlike the $O(1/\sqrt{T})$ rate of standard CFR, the adaptive method achieves linear convergence, reaching high precision much faster as iterations increase.
  • High Precision: In matrix games, the method achieved exploitability levels as low as $10^{-16}$, effectively reaching a perfect Nash Equilibrium where other last-iterate methods like Optimistic Multiplicative Weight Update (OMWU) often plateaued or oscillated.
  • Robustness: The "Exploit," "Keep," and "Explore" phases allow the algorithm to handle diverse game complexities without the need for extensive manual hyperparameter tuning by a human expert.

Conclusion and Future Directions

The Adaptive RT framework represents a significant step toward making game-theoretic solvers more efficient and autonomous. By enabling robust last-iterate convergence, it reduces memory overhead and improves precision in complex sequential games. Future research will focus on extending these techniques to "bandit feedback" scenarios—where players only observe the outcomes of their own actions—and integrating these adaptive mechanisms into Deep Reinforcement Learning for massive, real-world applications.

Summary updated

Abstract

Regret minimization is a powerful method for finding Nash equilibria in Normal-Form Games (NFGs) and Extensive-Form Games (EFGs), but it typically guarantees convergence only for the average strategy. However, computing the average strategy requires significant computational resources or introduces additional errors, limiting its practical applicability. The Reward Transformation (RT) framework was introduced to regret minimization to achieve last-iterate convergence through reward function regularization. However, it faces practical challenges: its performance is highly sensitive to manually tuned parameters, which often deviate from theoretical convergence conditions, leading to slow convergence, oscillations, or stagnation in local optima. Inspired by previous work, we propose an adaptive technique to address these issues, ensuring better consistency between theoretical guarantees and practical performance for RT Regret Matching (RTRM), RT Counterfactual Regret Minimization (RTCFR), and their variants in solving NFGs and EFGs more effectively. Our adaptive methods dynamically adjust parameters, balancing exploration and exploitation while improving regret accumulation, ultimately enhancing asymptotic last-iterate convergence and achieving linear convergence. Experimental results demonstrate that our methods significantly accelerate convergence, outperforming state-of-the-art algorithms.
BibTeX
@misc{ren2025efficient,
  author = {Hang Ren and Yulin Wu and Shuhan Qi and Jiajia Zhang and Xiaozhen Sun and Tianzi Ma and Xuan Wang},
  title = {{Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation}},
  year = {2025},
  eprint = {2509.13653},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.13653},
}
Figure