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

Hang Ren [email protected], Yulin Wu [email protected], Shuhan Qi [email protected], Jiajia Zhang [email protected], Xiaozhen Sun [email protected], Tianzi Ma [email protected], Xuan Wang [email protected] · 2025

Read Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation by Hang Ren [email protected], Yulin Wu [email protected], Shuhan Qi [email protected], Jiajia Zhang [email protected], Xiaozhen Sun [email protected], Tianzi Ma [email protected], Xuan Wang [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-13653.txt.

Introduction

Hang Ren and six co-authors improve regret minimization in a 2025 game theory paper. Regret methods find Nash equilibria in normal-form and extensive-form games, but they normally guarantee convergence only for the average strategy, which is costly to store and compute. A reward transformation trick can force the last strategy itself to converge, yet its hand-tuned settings often misbehave.

The team makes the transformation adaptive, adjusting its parameters during play to balance exploration and exploitation and to control how regret accumulates. Applied to regret matching and counterfactual regret minimization and their variants, the methods align practice with theory, reach linear convergence, and beat leading algorithms in experiments on both small and large games.

Catalog record

CREATORHang Ren [email protected], Yulin Wu [email protected], Shuhan Qi [email protected], Jiajia Zhang [email protected], Xiaozhen Sun [email protected], Tianzi Ma [email protected], Xuan Wang [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-13653

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation Hang Ren [email protected], Yulin Wu [email protected], Shuhan Qi [email protected], Jiajia Zhang [email protected], Xiaozhen Sun [email protected], Tianzi Ma [email protected], Xuan Wang [email protected] 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. Hang Ren, Yulin Wu, Shuhan Qi, Jiajia Zhang, Xiaozhen Sun, Tianzi Ma and Xuan Wang † † heading: - 2025 1- 11/22; Revised 5/31 -/- 24-2008 † † shortheadings: Regret Minimization via Adaptive Reward Transformation / Ren, Wu, Qi, Zhang, Sun, Ma and Wang † † firstpage: 1 † † editor: Tor Lattimore keywords game theory algorithm, Nash equilibrium, regret minimization, last-iterate convergence, reward transformation 1 Introduction Game theory provides essential frameworks for solving real-world problems, with Normal-form Games (NFGs) and Extensive-form Games (EFGs) serving as key models for studying strategic interactions, particularly in scenarios involving imperfect information and sequential decisions. A primary objective in game theory is to find or approximate Nash equilibria. Over time, numerous algorithms have been proposed, but the most efficient approaches are based on no-regret learning, valued for their simplicity, parameter-free nature, and effectiveness. This foundation underlies Regret Matching (RM) ( Hart and Mas-Colell 2000 ) in NFGs, as well as its extensive-form counterparts—Counterfactual Regret Minimization (CFR) ( Zinkevich et al. 2007 ) and CFR+ ( Tammelin 2014 ) —which leverage these properties to approximate Nash equilibria via the average strategy. Despite the advantages of average-strategy convergence, it requires considerable computational resources and introduces additional errors when approximating the average strategy, limiting its applicability in large-scale games. For instance, players may be unable to recall all past decisions, and deep learning-based methods struggle to effectively average historical strategies or parameters, complicating the integration of neural networks in these solutions. This limitation has led to the use of additional neural networks in Deep CFR ( Brown et al. 2019 ) to train the average strategy, which in turn introduces further errors. These limitations strongly motivate the development of regret minimization algorithms that achieve convergence using only the last strategy—a concept known as last-iterate convergence. Ideally, last-iterate convergence should be faster than that of the average strategy, as averaging inherently incorporates suboptimal strategies, which can hinder efficient convergence to an optimal solution. However, common methods such as regret matching, regret matching+, and Hedge often fail to achieve this property both theoretically and empirically, even in normal-form games ( Farina et al. 2024 ) . Although empirical studies have shown that CFR can achieve better performance with its last strategy compared to its average ( Lockhart et al. 2019 ) , and Cai et al. 2023 observed rapid last-iterate convergence in certain cases with extragradient RM+ and predictive RM+, a comprehensive theoretical framework explaining these phenomena in EFGs is still lacking. Recent studies have demonstrated that Optimistic Gradient Descent Ascent (OGDA), Optimistic Multiplicative Weights Update (OMWU), and regularized counterfactual regret minimization (Reg-CFR) achieve last-iterate convergence in two-player zero-sum games, both in normal and extensive forms ( Wei et al. 2020 ; Lee et al. 2021 ; Liu et al. 2022a ) . However, these methods face significant limitations, including the need for careful hyper-parameter tuning and complex gradient calculations, which can hinder their practical effectiveness in large-scale games, with some even failing to converge reliably. An alternative approach, inspired by evolutionary game theory, is the Reward Transformation (RT) framework ( Bauer et al. 2019 ; Perolat et al. 2021 ; Perolat et al. 2022 ) . This method, when applied to Follow the Regularized Leader (FTRL) and Multiplicative Weights Update (MWU) in continuous-time feedback games, has shown results comparable to or better than those of OGDA and OMWU ( Abe et al. 2022b ; Abe et al. 2022a ) , although its performance in real-world applications remains suboptimal. Recently, the RT framework has been adapted to RM+ and CFR+ for solving discrete-time feedback games, achieving last-iterate convergence in complex games for the first time ( Meng et al. 2023 ) . However, it has also encountered several challenges: the introduction of RT-term parameters, which are usually manually tuned and set to be fixed in practice, deviates from convergence theory, and performance is highly sensitive to these parameters, often leading to slow convergence, oscillations, or stagnation at local optima. In this work, inspired by the work of Perolat et al. 2021 and Meng et al. 2023 , we propose adaptive RT regularization techniques for regret minimization algorithms, including RM, CFR, and their variants, to achieve efficient last-iterate convergence for finding Nash equilibrium in two-player zero-sum games. Our main contributions are as follows: • We extend the convergence analysis of the RT framework beyond Meng et al. 2023 ’s RTRM+ to general RTRMs algorithms, proving a best-iterate rate of O(1/\sqrt{T}) and asymptotic last-iterate convergence. We identify unresolved bottlenecks in Meng et al. 2023 , including reference strategy selection and fixed RT-term and regret weights, which cause instability and hinder convergence, thus improving the framework’s robustness. • We propose an adaptive technique to address these bottlenecks from three aspects: (1) dynamically selecting reference strategies, (2) adjusting RT weights to either accelerate convergence or explore new optimization directions, and (3) improving the regret accumulation process by introducing adaptive discounted regret weighting ( Brown and Sandholm 2019 ) , which better aligns with achieving last-iterate convergence. • We apply the adaptive RT framework to EFGs using laminar regret decomposition and prove its asymptotic last-iterate convergence. This addresses the technical challenges in guaranteeing the convergence of RTCFR+ as established in Meng et al. 2023 . • We evaluate our adaptive methods against state-of-the-art average-iterate and last-iterate convergence algorithms in both NFGs and EFGs, demonstrating significant performance improvements. The structure of the paper is as follows: In Section 2, we discuss related work on equilibrium-finding algorithms, average-iterate convergence, and last-iterate convergence algorithms. In Section 3, we introduce preliminaries on NFGs and EFGs, the details of regret minimization, and the RT framework. Section 4 presents the convergence analysis of the RT framework and identifies its bottlenecks, which we address with our proposed adaptive method in Section 5, including parameter selection and RM structure optimization for consistency with last-iterate convergence. In Section 6, we extend our work to CFRs for solving EFGs with imperfect information, followed by experimental evaluation in Section 7. Finally, we

Read the complete text