Efficient Last-Iterate Convergence in Solving Extensive-Form Games
Authors: Linjian Meng
Tianpei Yang
Youzhi Zhang
Zhenxing Ge
Shangdong Yang
Tianyu Ding
Wenbin Li
Bo An
Yang Gao
Venue: NeurIPS 2025 poster ()
Keywords: Counterfactual Regret Minimization
Extensive-Form Games
Last-Iterate Convergence
Primary area: theory
TL;DR: We present the first parameter-free last-iterate convergence of Counterfactual Regret Minimization algorithms.

Abstract: To establish last-iterate convergence for Counterfactual Regret Minimization (CFR) algorithms in learning a Nash equilibrium (NE) of extensive-form games (EFGs), recent studies reformulate learning an NE of the original EFG as learning the NEs of a sequence of (perturbed) regularized EFGs. Hence, proving last-iterate  convergence in solving the original EFG reduces to proving last-iterate convergence in solving (perturbed) regularized EFGs. However, these studies only establish last-iterate convergence for Online Mirror Descent (OMD)-based CFR algorithms instead of Regret Matching (RM)-based CFR algorithms in solving perturbed regularized EFGs, resulting in a poor empirical convergence rate, as RM-based CFR algorithms typically outperform OMD-based CFR algorithms. In addition, as solving multiple perturbed regularized EFGs is required, fine-tuning across multiple perturbed regularized EFGs is infeasible, making parameter-free algorithms highly desirable. This paper show that CFR$^+$, a classical parameter-free RM-based CFR algorithm, achieves last-iterate convergence in learning an NE of perturbed regularized EFGs. This is the first parameter-free last-iterate convergence for RM-based CFR algorithms in perturbed regularized EFGs. Leveraging CFR$^+$ to solve perturbed regularized EFGs, we get Reward Transformation CFR$^+$ (RTCFR$^+$). Importantly, we extend prior work on the parameter-free property of CFR$^+$, enhancing its stability, which is vital for the empirical convergence of RTCFR$^+$. Experiments show that RTCFR$^+$ exhibits a significantly faster empirical convergence rate than existing algorithms that achieve theoretical last-iterate convergence. Interestingly, RTCFR$^+$ show performance no worse than average-iterate convergence CFR algorithms. It is the first last-iterate convergence algorithm to achieve such performance. Our code is available at https://github.com/menglinjian/NeurIPS-2025-RTCFR.

Efficient Last-Iterate Convergence in Solving Extensive-Form Games
Linjian Meng', Tianpei Yang't Youzhi Zhang"t, Zhenxing Ge', Shangdong Yang', Tianyu Ding', Wenbin Li', Bo An', Yang Gao'
National Key Laboratory for Novel Software Technology. Nanjing University
2 Centre for Artificial Intelligence and Robotics, Hong Kong Institute of Science & Innovation, CAS Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing University of Posts and Telecommunications
Microsoft Corporation
Schooo of Computer Science and Engineering, Nanyang Technological University menglinjian @ smail.nju.ee www.i..nuuuuuu.... tianpei. yang @ @nju.edu.cn. youzhi. srarhi. @ cair-cas .rgg.hk, hk, zhenxingge amail.nju.eduu en, sdyang @wjupt.euu.c.. tianyuding @ microsoft.com liwenbin @ eju.edu.cnn boan @ ntu.edu.sg, gaoy gaoy@nju.edu.cn
Abstract
To establish last-iterate convergence for Counterfactual Regret Minimization (CFR) algorithms in learning a Nash equilibrium (NE) of extensive-form games (EFGs), cent studies reformulate learning an NE of the original EFG as learning the NEs a sequence of (perturbed) regularized EFGs. Hence, proving last-iterate convergence in solving the original EFG reduces to proving last-iterate convergence in solving (perturbed) regularized EFGs. However, these studies only establish last-iterate convergence for Online Mirror Descent (OMD)-based CFR algorithms instead of Regret Matching (RM)-based CFR algorithms in solving perturbed regularized EFGs, resulting in poor empirical convergence rate, as R.M-based CFR algorithms typically outperform OMD-based CFR algorithms. In addition, as solving multi- ple perturbed regularized EFGs is required, fine-tuning across multiple perturbed regularized EFGs is infeasible, making parameter-free algorithms highly desirable. This paper show that CFR classical parameter-free free RM- based CFR algorithm, achieves last-iterate convergence learning an NE of perturbed regularized EFGs. This is the first parameter- last-iterate convergence for RM-based CFR al- gorithms in perturbed regularized EFGs. Leveraging CFR* to solve perturbed regularized EFGs, we get Reward Transformation CFR+ (RTCFR*), Importantly, we extend prior work on the parameter-fi frree property of CFR enhancing its sta- bility, which is vital for the empirical convergence of RTCFR+ Experiments show that R cxhibits a significantly faster empirical convergence rate than existing algorithms that achieve theoretical last-iterate convergence. Interestingly, RTCFR show performance no worse than average-iterate convergence CFR algorithms. It is the first last-iterate convergence algorithm to achieve such performance. Our code is available at https: //gi thub. com/menglinjiiecccccmmcmmmmoo.me wan.iinnnannnnuunenaee 202- RTCFR.
1 Introduction
Extensive-form games (EFGs) are foundational model for capturing interactions among mul- tiple agents and sequential events, which are widely applied in simulating real-world scenarios, such as medical treatment [Sandholm, 2015], security games [Lisý et al., 2016], and recreational games [Brown and Sandholm, 2019b). A common goal to address EFGs is to learn a Nash equilibrium (NE), where no player can unilaterally improve their payoff by deviating from the equilibrium.
Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Recent research commonly employs regret minimization algorithms [Zhang et al., 2022b] to learn an NE in EFGs, Among them, Counterfactual Regret Minimization (CFR) algorithms are the most widely used ones for learning an NE in real-world EFGs [Bowling et al., 2015, Moravčík et al., 2017, Brown and Sandholm, 2018, 2019h, Pérolat et al., 2022]. They usually use Regret Matching (RM) algorithms [Hart and Mas-Colell, 2000, Gordon, 2006, Lanctot et al., 2009, Lanctot, 2013, Tammelin, 2014, Brown and Sandholm, 2019a, Farina et al., 2021, 2023, Xu et al., 2024b] as the local regularizer, since RM algorithms usually exhibit a faster empirical convergence rate than other local regret minimizers, such as Online Mirror Descent (OMD) [Nemirovskij and Yudin, 1983]. For convenience, we refer to the CFR algorithms that employ RM algorithms and OMD algorithms as local regularizers as RM-based CFR algorithms and OMD- CFR algorithms, respectively.
However, most regret minimization algorithms,, including CFR algorithms,, typically only achieve average-iterate convergence and their strategy profile may diverge or cycle, even in normal-form games (NFGs) [Bailey and Piliouras, 2018, Mertikopoulos et al., 2018]. Average-iterate convergence implies that the averaging of strategies is necessary, which increases computational and memory overhead. Additionally, when strategies are parameterized via function approximation, new approx- imation function must be trained to represent the average strategy, resulting in further approximation errors. Consequently, algorithms with last-iterate convergence to NE, which ensures that the sequence of strategy profiles converges to the set of NEs, are preferable.
To establish last-iterate convergence for CFR algorithms, recent studies [Pérolat et al., 2021, 2022, Liu et al., 2023] employ the Reward Transformation (RT) framework, which (i) transforms the task of learning an NE of the original EFG into learning the NEs of sequence of (perturbed) regularized EFGs and (ii) ensures the sequence of the NEs of these (perturbed) regularized EFGs converges to the set of NEs of the original EFG. Therefore, to ensure last-iterate convergence in learning an NE of the original EFG, it is sufficient to establish last-iterate convergence in learning an NE of (perturbed) regularized EFGs. Unfortunately, these studies only establish last-iterate convergence in learning an NE of (perturbed) regularized EFGs for OMD-based CFR algorithms, incurring a poor empirical convergence rate to the set of NEs of the original EFG, as illustrated in our experiments.
To improve the empirical convergence rate, we propose Reward Transformation CFR* (RTCFR +). utilizing CFR [Tammelin, 2014], a classical parameter-free RM-based CFR algorithm, to solve perturbed regularized EFGs. RTCFR+ + is inspired by two observations: (i) RM-based CFR algorithms (the CFR algorithms that employ RM algorithms as the local regret minimizer) usually outperform OMD-based CFR algorithms, and (ii) parameter-free algorithms, implying no parameters need to be tuned (Grand-Clément and Kroer, 2021], are desirable to solve multiple perturbed regularized EFGs because fine-tuning across all perturbed regularized EFGs is infeasible. Notably, the parameter in CFR algorithms typically refers to the step sizes. Based on the RT framework, if CFR* has last- iterate convergence in learning an NE of perturbed regularized EFGs, then RTCFR has last-iterate convergence in learning NE of the original EFG. Unfortunately, it remains unknown whether CFR achieves the parameter- free (i.c., holds for any step sizes) last-iterate convergence in learning an NE of perturbed regularized EFGs. It motivates a key question:
Does CFR+ have parameter-free last-iterate convergence
in learning NE of perturbed regularized EFGs?
To answer this question, we first provide the non-parameter-free (w.r.t. the step sizes) last-iterate convergence of CFR+, i.e. for any initial accumulated counterfactual regrets, CFR achieves last- iterate convergence in learning an NE of perturbed regularized EFGs when the step size exceeds positive constant. We then extend this non- cooo--paamtte-friie result to establish the parameter-fire free result, i.e., CFR + achieves last-iterate convergence for any initial accumulated counterfactual regrets and step sizes. Note that our parameter-fii free result holds for any initial accumulated counterfactual regrets-not not just the zero initialization in previous works [Farina et al., 2021] enhancing the stability of CFR + [Farina et al., 2023], which is critical for the empirical convergence of RTCFR in solving the original EFG. Without our parameter-fie free result, RTCFR + fails to empirically converge to the set of NEs of the original EFG! To the best of our knowledge, this is the first parameter-fiee free last-iterate convergence guarantee for RM-based CFR algorithms in learning an NE of perturbed regularized EFGs. As consequence, based on the convergences of the RT framework and CFR+. R achieves last-iterate convergence in learning an NE of the original EFG.
'hile Tammelin et al. [2015] establish parameter free average- iterate convergence of CFR + under any initialization, we show both last- and -etrage-ttertt convergence. Their proof techniques differ from ours and the recent RM- based CFR works, which are all based Farina et al. [2021]. See details in Appendix B.

---

Specifically, we propose novel techniques to overcome the challenges in the above two steps of the proof. First, the primary challenge in proving the non- non-parameeer--e result is that the smoothness of the instantaneous counterfactual regrets- the key property used in prior works [Liu et al., 2023] to establish the last-iterate convergence of CFR aggorithms-came be leveraged, since RM algorithms update within the cone of the strategy space while the final output lies in the strategy space itself. To address this, we exploit the fact that an NE represents a best response to others at each infoset in perturbed EFGs. More specifically, this fact allows a term-related to the accumulated counterfactual regrets and the utility obtained by deviating from an NE of perturbed EFGs-can -an be added. It enables the smoothness of the instantaneous counterfactual regrets to be leveraged, ensuring that the cumulative squared distance between the iterated strategy profiles and the NE of perturbed regularized EFGs remains bounded by constant across all iterations, thereby guarantecing last- iterate convergence. Second, the main challenge of proving our parameter-free result is that the property used in prior proofs of the parameter-free property of CFR+-th the strategy sequence produced by CFR+ remains invariant across different step sizes-hole only when the initial accumulated counterfactual regrets are zero [Farina et al., 2021]. We address this by leveraging the linearity of the projection alongside our non-parameter-free convergence result that holds for any initial accumulated counterfactual regrets. In particular, we use the linearity of projection to show that for any given initial accumulated counterfactual regrets and step sizes, there exists an alternative choice of these parameters that yields an identical strategy profile sequence. By then applying our non- non-parameter-Fee free result to this alternative setting, we establish that the resulting strategy profile sequence converges to the set of NEs of perturbed regularized EFGs, thus proving the parameter-free last-iterate convergence. Notably, We only provide parameter-free last-iterate convergence results for CFR In other words, RTCER+ not a parameter-free algorithm.
Experimental results across nine instances from five standard EFG benchmarks Kuhn Poker, Leduc Poker, Goofspiel, Liar's Dice, and Battleship, as well as two heads-up no-limit Texas Hold'en em (HUNL) Subganes-demonsttre rate compared to existing algorithms with theoretical last-iterate convergence guarantees. Interestingly, RTCFR even performs no worse well as average average-iterate iterate convergence CFR algorithms. Notably, it is the first last-iterate convergence algorithm to accomplish this level of performance.
that RTCFR* achieves significantly faster empirical convergence
2 Preliminaries
Extensive-form games (EFGs). EFG is a commonly used model for modeling tree-form sequential eecision-mmainn problems. An EFG can be formulated as G = {N, H. P, A, {u:}}. Here, . is the set of players. H is the set of all possible histories. The set of leaf nodes is denoted by 2. For each history h E H. the function P(h) represents the player acting at node h, and A(h) denotes the actions available at node h. To account for private information, the nodes for each player i are partitioned into collection I, referred to as information sets (infosets). For any infoset I E I, histories h, h E / are indistinguishable to player i. Thus, P(T)= = P(h), A(T) = A(h), vh E T. The notation I denotes I (Ziji E W.. We also use CT,T, a) to denote the set of infosets that belongs to and will counter after executing a E A(T at infoset T E I. The notations Amaz and Cmoz denote max [A()) and maxieN, A(T)) C,,, respectively. For each leaf node 2, there is a pair (2)(2), un (2)) [-1, 1] which denotes the payoffs for the min player (player 0) and the max player (player 1), respectively. We define as the maximum number of actions taken by all players along any path from the root to a leaf node. In two-player zero-sum EFGs, uo uo(=) To illustrate the components of an EFG, we provide an example in Appendix A.
ui (z), V2 E Z.
Sequence-form strategy. A sequence is an infoset-action pair (T,a), where 7 E I is an infoset and is an action belonging to A(1). Each sequence identifies path from the root node to the infoset I, selecting the action along this path. The set of sequences for player i is denoted by E, The last sequence encountered on the path from the root node words, Vi E N,, I E I,, I E Ci(pr). A sequence-form strategy for player is a nen-negative vector 2; indexed over the set of sequences E,. For each sequence q = (I, a) E E, (q) is the probability that player i reaches the sequence when following the strategy x, We formulate the sequence-form strategy space as a treeplex (Hoda et al., 2010]. Let X, denote the set of sequence-forn strategies for player i. We use (7) [a; (I, a)la E A()) to denote the slice of a given strategy æ; corresponding to sequences belonging to infoset 7, where ax, a) value of an at the sequence (T, For each D.
is denoted by P1 (p) E Σ.). In other
EFG, there always exists D such that Vi e N and x; X. |
3

---

Nash equilibrium (NE), NE describes a rational behavior where no player can benefit by unilaterally deviating from the equilibrium. For any player, her strategy the best response to the strategies of others. From the sequence-forn strategy framework, learning an NE of EFGs is represented by
min max x A/A mo Eo EIEXi
(1)
where A is the payoff matrix. We use X' and X' denote XxexX, and the set of NE, respectively.
Behavioral strategy. This strategy o, defined on each infoset. For any infoset E I, the probability for the action a E A(1) is denoted by a.). We use or o1 (o,(L,)) E A())] A to denote the strategy at infoset 1, where A AIA(2) is a (IA(1)) -idmmension simplex. If all players follow the strategy profile = {oro 0 } and reaches infoset I, the reaching probability is denoted by n" (/). The probability contribution from player i is represented by :h (?), while the contribution from the other players is represented by T (I), where -i refers to all players except player Notably, vi E N I E I, A(I), D, X, x, a) xp (1) (I,a), where o, is the corresponding behavioral strategy of x;,
Perturbed extensive-form games (Perturbed EFGs). This game is variant of the original EFG. Specifically, the strategy space of each infoset E I in a y-perturbed EFG is a y-perturbed simplex A, (A(2)) a subset of A | rather than the standard simplex A AIA(2) used in the original EFG, where y 0 is constant. Formally, for any (I) A,DD and a E A(J), the constraint y ( a) < 1 holds, where = P()). For convenience, we denote the set of sequence-form strategies for player i in the 7-perturbed EFGs as X7. y-perturbed EFGs with y > 0, any behavioral strategy o,. with (I) E =AA()) for all E N and I E I, can be uniquely mapped to a sequence-form strategy à; E X7, and vice versa. Specifically, Vi E NN, E Z, 61( d; (T)(/((((p)) 2 7. Notably, Vi E N, X7 is subset of X, Similarly, we use the notation X² and x to denote the joint strategy space X? and the set of NEs of y-perturbed EFGs, respectively.
Learning NE via regret minimization algorithms. For any sequence of strategies x!,,.., ,=. of of player i, player i's regret is R. = max Σ.= (e) x - 2;), where & is the loss for player: at iteration f. Regret minimization algorithms are algorithms ensuring R. grows sublinearly, To learn an NE of EFGs via regret minimization algorithms, we set E E with E = Axı and eT A xo. all players follow regret minimization algorithms, then the average strategy converges to the set of NEs in two-player zero-sum EFGs. In EFGs, there always exists L and P such that, Vz, x' E X. ||eT - e || < L| z'Il2 and | ||2 S P, where e = [e7 E W1, as well as and P are game-dependee dependent constants.
Counterfactual regret minimization (CFR) framework. This framework [Zinkevich et al., 2007, Farina al., 2019] is designed solve EFGs by decomposing the global regret RÝ into local regrets at each infoset, allowing for independent minimization within each infoset, rather than directly minimizing global regret. This approach has led the development of several superhuman Game AIs [Bowling et al., 2015, Moravčík et al., 2017, Brown and Sandholm, 2018, 2019b, Pérolat et al., 2022]. Formally, for player i, given the observed loss when all players follow x E X is E., the CFR framework computes the counterfactual values at each infoset I E Ij according to
of (I, -f,
Σ PECI(L))
(o (T)),
where (,, (1,a) a) is the value of e. at the sequence (1, o4') 10 (I', la' A(I')), and o, represents the behavioral strategy of player corresponds to I; Farina et al. [2019] demonstrate that
T
R
max E
xx) S
max
(00((), - e(l)
1m11
TET.
im1
where vf(1)= = of (1) = lop' al,a) E A(T) and of is the behavioral strategy of player i corresponds to at. It indicates that minimizing the local regret max,,(1) ΣT ((((())))))))))))( E I4 contributes to minimizing the global regret R².
Blackwell approachability framework. RM algorithms are come from this framework whose core insight lies in reframing the problem of regret minimization within the orignial strategy space Z as

---

regret minimization within cone 2 {)z E X2 0} [Blackwell, 1956, Abernethy et al..
2011. Farina et al., 2021]. Specifically, a regret minimization algorithm is instantiated in cone Z). where its output at iteration / is 0'. This corresponds to the strategy z' 0'/(0', 1) within Z. Given the loss L' at iteration f, the algorithm observes the transformed loss -m' = - (e' 2 l
and subsequently generates 0i+ The main advantage of this framework is its capacity to develop parameter-free algorithms. More details are provided below.
Regret Matching* (RM*). To minimize local regret within each infoset, CFR algorithms commonly employ local regret minimizers based on RM [Hart and Mas-Colell, 2000, Gordon, 2006, Bowling et al,,, 2015, Farina et al., 2021, 2023, Xu et al., 2022, 2024b, Cai et al., 2025], which show strong em- pirical convergence rate and are typically parameter-fres free. In this paper, we focus on RM+ [Tammmllin 2014], variant of RM that typically exhibits faster empirical convergence rate than vanilla RM. RM+ is a traditional algorithm grounded in Blackwell approachability framework. It corresponds to an OMD instantiated in the cone of the simplex [Farina et al., 2021]. Formally, at each iteration and infoset I E I, RM+ updates the strategy via
{ (-m) 01) 0 ER
1 (D,(0 "
0 g1+1
0 E arg min
of (f) = (0)
where i = P(D, > is the step size, (1) = - +0)) (1) represents the instantaneous counterfactual regret, and (u, v) = ((u) (10) (Vo((()) is the Bregman divergence associated with the quadratic regularizer v)() = y > 0, the output sequence
o 1-1/22 11 = 0,, for all the step size remains unchanged [Farina et al., 2021]. Combining RM+ with the CFR framework yields CFR+ [Taammelin, 2014), which is parameter-free
CFR algorithm and has been used to build superhuman poker AI [Bowling et al., 2015].
3 Problem Statement
To demonstrate the last-iterate convergence of CFR algorithms, Pérolat al. [2021, 2022], Liu et al. [2023] employ the RT framework. This framework reformulates the objective of learning an NE for the original EFG into finding NEs for series of (perturbed) regularized EFGs, and ensures that the sequence of NEs of the regularized EFGs converges to the set of NEs of the original EFG. Therefore, establishing last-iterate convergence in learning an NE of the original EFG reduces to establishing last-iterate convergence in learning an NE of (perturbed) regularized EFGs. Inspired by Pérolat et al. [2021], Liu et al. [2023], Abe et al. [2024], we consider the following perturbed regularized EFG:
min max a Ar; + pD - ((1.))). x
where y > O and j > 0 are constants, vb(-) is the quadratic regularizer, and r = [ro: rı E X is the reference strategy profile. The NE of this perturbed regularized EFG is unique and denoted by a"oop" or â "*.uerr To ensure the sequence of the NEs of the perturbed regularized EFGs converges to the set of NEs of the original EFG, valid approach is to continuously decreasing the value of y and updating r to "*HH" according to the studies in Abe et al. [2024], Bernasconi et al. [2024]. Another approach involves simultaneously reducing the values of and μs [Liu et al., 2023, Bernasconi et al., 2024]. Notably, in the approach where simultancously reducing the values of and μ., updating r to a-m.. is optional. Consequently, achieving the last-iterate convergence for solving Eq. (2) implies achieving the last-iterate convergence for solving Eq. (1). This paper refrains from investigating the RT framework and its convergence as these have been thoroughly investigated in other studies [Pérolat et al., 2021, Liu et al., 2023, Abe et al., 2024, Bernasconi et al., 2024, Wang et al., 2025].
The introduction of perturbation and regularization ensures the smoothness of counterfactual val- ues and the strong monotonicity, respectively. The smoothness is ||l! (4) of (1)I I O(ll@ a'Ili,, Va, ø' E X", where à and o' are the behavioral strategy profiles associated with & and a', respectively. The strong monotonicity indicates that Oi(e*
á a²)) 2 | i ='1 Vā, a' e x".
Although some works have investigated the last-iterate convergence of CFR algorithms for solving perturbed regularized EFGs [Liu et al., 2023], their algorithms do not use RM-based algorithms as the local regret minimizer. The absence of RM-based algorithms leads to significantly weaker empirical last-iterate convergence performance than traditional RM-based average-itenan convergence CFR algorithms, as shown in our experiments. In addition, as solving multiple perturbed regularized EFGs
5

---

is required. fine-tuning across all perturbed regularized EFGs is infeasible. Consequently, parameter- free algorithms, implying no parameters need to be tuned [Grand-Cllment and Kroer, 2021], are desirable. Based on these observations, we propose Reward Transformation CFR+ (RTCER+), utilizing CFR+ [Tammelinn 2014], a classical parameter- free RM-based CFR algorithm, to solve perturbed regularized EFGs defined in Eq. (2) (details of RTCFR* are in Section 4). Unfortunately, it remains unknown whether CFR achieves the parameter-free (i.e., holds for any step sizes) last-iterate convergence in solving Eq. (2). Thus, our objective is to establish the parameter-frve free last-iterate convergence for CFR in solving Eq. (2). More discussions about the related works are in Appendix B.
4 Last-Iterate Convergence of CFR in Solving Perturbed Regularized EFGs
Now, show that CFR exhibits last-iterate convergence for solving the perturbed regularized EFGs defined in Eq. (2). Before introducing the last-iterate convergence of CFR*, we first extend CFR to perturbed EFGs as the original CFR algorithm is only designed for the case where 7 0. Specifically, we (i) first update the accumulated counterfactual regrets within the original simplex's cone while ensuring strategy outputs lie within the perturbed simplex by mixing the non-perturbed strategy formed by the accumulated counterfactual regrets with the uniform vector, then (ii) compute the instantaneous counterfactual regrets using the non-perturbed strategy and the counterfactual values observed through following the output perturbed strategy. This enables the use of the strong monotonicity to establish last-iterate convergence in learning an NE of the perturbed regularized EFGs in Eq. (2), as shown in Eq. (6). Formally, the update rule of CFR + for learning an NE of the perturbed regularized EFGs in Eq. (2) iteration and infoset I I4 is
{ (-M ", - of 4 (1)
g++ (0 1)
07 E arg min
0, 0 ERACD
(1) (1 ar)o (1) +1)+1,, ar >|A(])
mf([)= 6((1) ((1),,
([(1,) a) aT) + Σ (6((T"),
e Adi + (V)((a)) (v)(r)) & A +VVx()) ~VV((r))
where 7) > 0 is the step size and (i(1) 7 (I). The second line in Eq. (3) mixes the non-perturbed strategy with the uniform vector 1, while the third line constructs the instanta- neous counterfactual regrets m using the non-perturbed strategy of derived from accumulated counterfactual regrets of and counterfactual values if obtained from the perturbed strategy o
Theorem 4.1 (Proof is in Appendix D). Assuming all players follow the update rule of CFR+ with any 0, E IR(A())) and r > O, the strategy profile á' converges to the set of NEs of the perturbed regularized EFGs defined in Eq. (2) with any 7 > 0 and >> 0.
Proof sketch of Theorem 4.1. Our proof consists of two steps. Firstly, we establish the non- parameter-free last-iterate convergence; that is, for all 03 E I2 (R((())) the last-iterate convergence of CFR+ in solving Eq. (2) holds when v) exceeds a certain constant. The principal challenge is that the smoothness of the instantancous counterfactual regrets cannot be used since RM algorithms update within the cone of the strategy space, cone A A(D), whereas the final output lies in the strategy space, A A(T), We address this challenge by leveraging the fact that an NE a best response to other strategies at each infoset in perturbed EFGs, as shown in the text around Eq. (5) and (6), as well as Lemma 4.4. Secondly, we derive the parameter-fres convergence result, namely, that the last-iterate
IR
convergence of CFR holds for all 0 E (R/4()) and > 0. The main challenge here is that the property used in previous proofs of the parameter-free property-thal the strategy sequence produced by CFR+ is invariant w.r.t. different step sizes 1) O-hllds only when 0 O. We overcome this by exploiting the linearity of the projection in CFR and the fact that our non non-parameter-frie last-iterate convergence of CFR + holds for all 0: E [AA(1) presented in the second paragraph following Lemma 4.4. The details of our proof sketch is shown in the following.

---

Lemma 4.2 (Adapted from the proof of Lemma 4 in Farina et al. [2021]). Assuming all players
follow the update rule of CFR+, then for any 0, 20 A(T) we have
(1, +) Du (0,; 01) S ( (m) 0,+1 01) (0 01)-
By applying Lemma 4.2 with 0 = of 22 (1) = (0, -
E A AlA(D), we get
De - 0.). (4) -
Also, we define
m, m 1 (1) (1) (1),0 ( (1))1,
a (1)= Eu (I,a)+ Σ
(0.
PEC,UL,)
ty fo AAi 14* V - (vo))) -
= A "
Then, adding 11( m (17.7 (7), (T),0] 0 07) to each hand side of Eq. (4), we can get
(1) o (1) 03) 1j (T) m. M... (
(5)
<Dulo; (1)0) ( + - (1), 01) (u(a ( (1), 7 um (1), 0
In OMD algorithms [Sokota et al., 2023], the addition of the term 17( -m, M.7 (I), 0 0)) is not required to exploit the smoothness of the instantaneous counterfactual regrets. However, this term is necessary to prove the last-iterate convergence of CFR+. This step is crucial in our proof, and to the best of our knowledge, no prior work has proposed similar approach.
Lemma 4.3 (Proof is in Appendix E.1). For any x' X, e Rl* i N. O, and y 2 0.
I; - x = Σ (T)( -1)))
TET.
= a -(; + Erec, (1') as where oa (I) = [og a)la E A(I) with of (1,
well as a and o' are the behavioral strategy profiles associated with x and x', respectively.
Combining Eq. (5) with Lemma 4.3, and setting C (1 a,)33 with Br = x " (T), we have m...P. (I)112
T
(1) m,
ΣΣΣN
EliENTET:
>Σ> G (I).))) m. us0i (1).)) -Dulo iEVTET
(m (1),07+1))
By using the strong monotonicity (0 Eee a; ))))))) | ar as shown in Lemma D.I) and the smoothness of instantaneous counterfactual regrets (I) m; 4-777 (L)l < O(I *...7 (22) (see details in Appendix D), we get
mm
Σ
n Col a
S
ΣEd cr Du (1),
iEN IEI,
+ + m 1.7 (T), 03) - (. (T), 0f+1) - 11(- m ::100:0 (T), of
where Co- | (6(L 21)² + S(P + 2μD)²
(A (Aman maz + 1) /22 ). Note that the form of smoothness we adopt differs from that commonly used in OMD algorithms [Sokota et al., 2023], where smoothness typically takes the form (Im - -m,+ -m))3 < O( x'+1ll) rather than
[m)(()) m (4..7. (D)]lB < 0(I --000 112. This difference also highlights that our proof approach diverges from the approach used by OMD algorithms. Then, if 0 < S (2C)), we get
ΣΣΣ
Do D MAT (I),
2
1=1
RENTEL,
p. M. (1), 0 - Do U. (1), (1),0++)) - T7( m ui (1), (1), 07+1) m
+
7

---

Lemma 4.4 (Proof is in Appendix E.2). Vi EEW, 1 E I, and 02 E R R (-m, " (T), 2 0.
Lemma 4.4 is from that an NE is a best response to others at each infoset in perturbed EFGs, i... Yo, (6) (67 (I), 10, (T)==;(())) 20, where (T) (1 (1-ar)a (T)+ (details are in Appendix E.2).
By using Lemma 4.4, we get vT || - 6 11 (0)), implying that ø' converges to @*PA7 with O<nSS/((Co))
Farina et al. [2021] show that when 0 = 0, for any 17 > 0. the sequence (#',""
remains the same. This implies that ě' converges to """"""""" for any > 0, showing the parameter-
free property. In this paper, we further show that for any initial 07 (R)) and 17 > 0, & converges to o "=*..7." (see advantages in discussions). This proof is simple yet novel, with the key insights being the linearity of the projection in CFR+ and that Σt=1 || =="00.0 s (1) holds independently of the value of f). Specifically, from the linearity of the projection CFR* for any accumulated (R(())) and 17 > 0, there exists a corresponding accumulated counterfactual regret sequence (0)', 00'
counterfactual regret sequence (0). of...... , . generated by any 0 IR
......) generated by 0 and 1/ m/((Co),, such that the resulting strategy profile sequence { x² ..... . are identical. Additionally, as the condition Σ | ------11 I (1) holds independently of the value of 0 (0)') Based on this analysis, we conclude that for any accumulated counterfactual regret generated by any 0) and 1) > 0, the corresponding strategy profile converges to a ""MMn"" which indicates the parameter-free freee property.
sequence (0) 10:00 02
sequence 5. Φ
Reward Transformation CFR (RTCFR*). RTCER* is the RT algorithm that applies CFR + to solve perturbed regularized EFGs, whose pseudocode is in Algorithm 1. As analyzed by Abe et al. [2024], Bernasconi et al. [2024], continuously decreasing Y and updating to " allows the sequence of the NEs of the perturbed regularized EFGs to converge to the set of NEs of the original EFG. Specifically, as shown in Algorithm 1, after T, iterations, RTCFR + updates y and r. with TT, representing the total number of iterations. The implementation of RICER + is in Appendix H.
For RTCER+, we do not examine the convergence of the se- quence of the NEs of the perturbed regularized EFGs to the set of NEs of the original EFG when the exact """"" is not learned but only an approximate " is obtained, as this problem can be solved by simultaneously decreasing the values of μl and 7, as mentioned in Section 3. Formally, line of Algorithm 1 can be modified as: ff (x and r T where 0<<<1. When < is close to 0, e.g., 1e-16, its effect on the empirical convergence rate of RTCFR is min- imal (Figure 3). Nonetheless, it ensures that the sequence of NEs for the perturbed regularized EFGs converges the set of NEs of the original EFG, even the exact a: 4o is not learned.
Algorithm RTCER*
1: Input: N. Tu. p, r
2: 0] t 0, 1,,, EI
3: for each n [1, 2...., .N] do
4: Build the perturbed regularized
EFGs in Eq. (2) via 14, 7, and r
5:
for each E [1, 2, ... T.] do
6: Ohtain 4' and 0f via the
update rule in Eq. (3) end for
7:
8:
7 7 0.5,
Tu+1
9:
0 - 07 0 VI
10:
end for
Firstly, to the best of our knowledge, we provide the first parameter-free last-iterate convergence for RM-based
Discussions.
11: Return a Tu+1
CFR algorithms in learning an NE of perturbed regularized EFGs. When considering NFGs, the last-iterate convergence result of CFR + (RM+) holds even when 7 = O, due to that the smoothness of counterfactual values and Lemma 4.4 hold in NFGs with any 7 2 O. Secondly, we extend the parameter-fin free results of CFR + from Farina et al. [2021], demonstrating that CFR converges with
the parameter-free property for any 0} [A())) not just when 0; O in Farina et al. [2021]. This new parameter-free result is significant. Specifically, it indicates that after updating y and r (line 8 of Algorithm 1), there no need to reset 0) to to get the parameter-free property (line 9 of Algorithm 1). This improves the stability of CFR+, i.e., rapid fluctuations in the strategy profiles across iterations, since such stability improves as the lower bound of the 1-norm of 0f increases [Farina et al., 2023] (for CFR+, from the proof of Lemma C.2 of Liu et al. [2022], we get that |10/ < 112- and the --norm lower bound is related to the 2-norm lower bound). Notably, as shown in Appendix G, resetting 0 to O after updating 7 and r (line 9 of Algorithm 1 becomes 0 0, VT E Z) causes RTCFR + to never converge (Figure 3)! Lastly, our proof approach for the parameter-free property can be used to show that CFR+'s average-iterate convergence holds for all 0 R Rl4(!) and 17 > 0. As our primary focus is last-iterate convergence, we discuss the parameter-free aterage-iterate convergence in Appendix F rather than the main text.
8

---

kuhn Poker
Lodur Poker
Battleship
10
10.1
10a
10
Exploiaaility
10-4
10-1
10
10
10'4
10
10-41
10-1c
N.B.
10-32
10000
15000
20000
50000
10000
15000
20000
5000
10000
15000
20000
Liar's
Liar's
10-3
Exploitabiity
10-2
10a
10-42
10a4
Goofspiel
Goofspiel (5)
Goofspplll (6)
10
10"4
10
Exploiaailltt
10-
10-1
10a4
10:10
10-1
10-12
10:41
10
10-4
10
10000
15000
20000
Rerations
Iterations
Iterations
RFC
RTPCER
PCFR
Reg-CFR
OMWU
RTOFR* (fine-tuned)
CFR
DCFR
R-NaD
OGDA
Figure 1: Last-iterate convergence rates of different algorithms. In all plots, the x-axis is the number of iteration, and the y-axis is exploitability, displayed on logarithmic scale. Liar's Dice (r) represents that every player is given die with sides. Goofspiel (z) denotes that each player is dealt cards. Battleship (x) implies the size of grids is x. The size of the tested games is in Appendix G (Table 2).
5 Experiments
Configurations. We now evaluate the empirical convergence rate of RTCFR* on five standard EFG benchmarks: Kuhn Poker, Leduc Poker, Goofspiel, Liar's Dice, and Battleship, all implemented using OpenSpiel [Lanctot et al., 2019]. We compare RTCER+ with classical CFR algorithms, such CFR+, PCFR + [Farina al., 2021], and DCFR [Brown and Sandholm, 201 2a],,, and those with theoretical guarantees for last-iterate convergence, including R-Nal) [Pérolat et al., 2021, 2022] and Reg-CFF RFg-CFR [Liu et al., 2023]. Additionally, we evaluate traditional last-iterate convergence algorithms, such as OMWU and OGDA [Wei et al., 2021, Lee et al., 2021]. The algorithm imple- mentations are based on the open-source LiteEFG code [Liu et al., 2024], which offers significant Sopedddp-pppooiimttel 100 times faster than OpenSpiel's default implementation for the same number of iterations. For RTCFR* we set the initial values of 7) ?, and μ 1, 10, and 1c-3. respectively. The number of iterations Tn required to update and r. is set to 100. For Reg-CFF we use the parameters from the original paper. For R-NaD, we initialize μ = le-5 (R-NaD does not include the parameter 7), set T, = 1000, and use a learning rate of 0.1. For OMWU and OGDA, we set 1) to 0.5 and 0.1, respectively. All algorithms employ alternating updates to enhance empirical convergence rates. Each algorithm is run for 20,000 (N 20000/T.,) iterations analyze long-term

---

Table I: Hyperparameters used in RTCFR* (fine-tuned).
Kuhn Poker
Ledue Poker
Battleship (3)
Liar's Dice (4)
Liar's Dice (5)
0.1
0.001
0.1
0.01
0.0005
T
10
50
Liar's Dice (6)
Goofspiel (4)
Goofspiel (5)
Goofspiel (6)
0.0001
0.1
0.05
0.005
500
100
behavior. The experiments are conducted machine equipped with Xeon(R) Gold 6444Y CPU and 256 GB of memory. More experimental results including (i) performance RTCER under simultaneous decrease of μ and y, (ii) performance of RTCFR* + under reset accumulated regrets as O, (iii) comparison with average-iterate convergence CFR algorithms, (iv) performance of RTCFR in HUNL Subgames, and (v) performance of RTCFR under different hyperparameters, are in Appendix G.
Results. The experimental results are presented in Figure 1. RTCER+ demonstrates superior performance compared to all other tested algorithms except PCFR + Specifically, RTCFR* exhibits the fastest convergence rate actoss all games when compared to CFR In comparison to existing theoretical last-iterate convergence CFR algorithms, such as Reg-CFR and R-NaD, RTCFR* is only surpassed by Reg-CFR during the initial stages in small-scale games like Kuhn Poker and Goofspiel (4). Similarly, when compared to traditional last-iterate convergence algorithms, RTCFR is only outperformed by OGDA in small-scale games such as Kuhn Poker and Goofspiel (4). Inspired by RTCER and the performance of PCFR + we propose RTPCER which employs PCFR to solve the perturbed regularized EFG defined in Eq. (2) instead of CFR + For RTPCFR use the same parameters as RTCFR* Among RTCER* RTPCER* and PCFR+ no single algorithm consistently outperforms the others across all EFGs, their performance varies depending the specifie EFG. This variability may be attributed to the fact that RTCER and RTPCFR have not been fine-tuned also include a comparison with the fine-tuned RTCFR which
for individual EFGs. Therefore, is denoted as RTCFR (fine-tuned) in Figure 1. Our findings demonstrate that fine-tuning enables RTCER outperform all tested algorithms. The parameters used for the fine-tuned RTCFR presented in Table 1. However, the automatic udjustment of y, μ1 and T. remains an open problem. One of our future research directions is investigate the automotive adjustment of these parameters.
6 Conclusions
We explore the last-iterate convergence of parameter-free R.M-based CFR algorithms. We establish that classical parameter- free RM-based CFR algorithm. CFR + achieves last- convergence in learning an NE of perturbed regularized EFGs. To our knowledge, this is the first parameter- free last- iterate convergence of R.Mbbaed CFR algorithms in perturbed regularized EFGs. Experimental results show that our proposed algorithm, RTCFR+ exhibits a significantly faster empirical convergence rate than existing algorithms that achieve theoretical last-iterate convergence.
Limitations. The main limitation RTCFR is its dependency on parameter tuning. Specifically, RTCFR* requires careful fine-tuning of parameters μ,, and T., which prevents it from being a parameter-free algorithm. Interestingly, when both μ and 7 are simultaneously reduced, RTCFR achieves last-iterate convergence in learning an NE of the original EFGs, irrespective of the values of 14, 7, and T.. These parameters only impact the empirical convergence rate. Therefore, advancing automated methods to learn optimal values for μ. and T, represents a promising direction for future research.
Acknowledgements
This work supported part by the National Natural Science Foundation China under Grants 62192783 and 02506157, the Jiangsu Science and Technology Major Project BG2024031, the Fundamental Research Funds for the Central Universities (14380128) 28), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the InnoHK funding.
10

---

References
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. Adaptively perturbed mirror descent for learning in games. In Proceedings of the 41st International Conference on Machine Learning, 2024.
Jacob Abernethy, Peter Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Conference on Learning Theory, pages 27-46. JMLR Workshop and Conference Proceedings, 2011.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics in time-varying games. In Proceedings of the 34th International Conference Neural Information Processing Systems, 2024.
James P. Bailey and Georgios Piliouras. Multiplicatiie weights update in zero-sum games. In Proceedings of the 19th ACM Conference Economics and Computation, pages 321-338, 2018.
Martino Bernasconi, Alberto Marchesi, and Francesco Trovò. Learning extensive-form perfect equilibria in two-player zero-sum sequential games. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 2152-2160. PMLR, 2024.
David Blackwell. An analog of the minimax theorem for vector payoffs. 1956.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218):145-149)) 2015.
Noam Brown and Tuomas Sandholm. Strategy-based warm starting for regret minimization in games. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 4424444444444 2018.
Noam Brown and Tuomas Sandholm. Solving imperfect-infooraatio games via discounted regret minimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence pages 1839.1836, 2019a.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Noam Brown, Tuomas Sandholm, and Brandon Amos. Depth-limited solving for imperfect- information games. Proceedings of the 28th International Conference on Neural Information Processing Systems, 2018.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-inffomatioon games. In Proceedings of the 30th International Conference on Neural Information Processing Systems, 2020.
Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Weiqiang Zheng. Last-iterate convergence properties of regret-matching algorithms in games. In Proceedings of the 14th International Conference Learning Representation, 2025.
Darshan Chakrabarti, Julien Grand-Clément, and Christian Kroer. Extensive-form game solving via Blackwell approachability on treeplexes. In Proceedings of the 35th International Conference on Neural Information Processing Systems, 2024.
Gabriele Farina and Tuomas Sandholm. Fast payoff matrix sparsification techniques for structured extensive-fol games. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, 2022.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequential decision processes and extensive-form games. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 1917-1925, 2019.

---

Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5363-5371, 2021.
Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-War Lee, and Haipeng Luo. Regret matching+: (in)stability and fast convergence games. In Proceedings of the 37th Conference on Neural Information Processing Systems, volume 36, pages 61546-6157,, 2023.
Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-reeall abstraction with earth mover's s distance in imperfect-informatiie games. In Proceedings of the 28th AAAI Conference on Artificial Intelligence, 2014.
Geoffrey J. Gordon. No-regret algorithms for online convex programs. In Proceedings of the 19th International Conference on Neural Information Processing Systems, pages 489-496, 2006.
Julien -eneentééentt and Christian Kroer. Conic Blackwell algorithm: Parameter-free convex- concave saddle-point solving. In Proceedings of the 35th International Conference on Neural Information Processing Systems, volume 34, 2021.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 127-1150, 2000.
Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
Michael Johanson, Nolan Bard, Mare Lanctot, Richard Gibson, and Michael Bowling, Efficient nash equilibrium approximation through monte carlo counterfactual regret minimization. In Proceedings of the 1 11th International Conference on Autonomous Agents and Multiagent Systems- Volume 2, 2012.
Marc Lanctot. Monte Carlo Sampling and Regret Minimization for Equilibrium Computation and Decision-Making in Large Extensive Form Games. University of Alberta (Canada), 2013.
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling, Monte carlo sampling for regret minimization in extensive games. Proceedings of the 22nd International Conference on Neural Information Processing Systems, pages 1078-1086, 2009.
Marc Lanctot, Edward Lockhart, bean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, al. Openspiel: A framework for reinforcement learning in games, 2019.
Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Proceedings of the 35th International Conference on Neural Information Processing, pages 14293-14305, 2021.
Boning Li and Longbo Huang. Efficient online pruning and abstraction for imperfect informa- tion extensive-fore form games. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Boning Li, Zhixuan Fang, and Longbo Huang. RI-efr: improving action abstraction for imperfect information extensive-form games with reinforcement learning. In Proceedings of the 41 International Conference Machine Learning, 2024.
Viliam Lisy, Trevor Davis, and Michael Bowling. Counterfactual regret minimization in sequential security games. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, pages 544-550, 2016.
Mingyang Liu, Asuman F. Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive- formm games. In Proceedings of the 12th International Conference Learning Representations, 2023.
Mingyang Liu, Gabriele Farina, and Asuman Ozdaglar. LiteRFG: efficient python library for solving extensive-form games. arXiv preprint arXiv:2407.20351, 2024.
12

---

Weiming Liu, Huacong Jiang, Bin Li, and Houqiang Li. Equivalence analysis between counterfactual regret minimization and online mirror descent. In Proceedings of the 37th International Conference on Machine Learning, pages 13717-13745, 2022.
Linjian Meng, Youzhi Zhang, Zhenxing Ge, Tianyu Ding. Shangdong Yang, Zheng Xu, Wenbin Li, and Yang Gao. Last-iterate convergence of smooth Regret Matching+ variants in learning Nash equilibria, 2025.
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algoritmms, pages 2703-2717, 2018
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-511 2017.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Julien Pérolat, Rémi Munos, lean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro A. Ortega, Neil Burch, Thomas W. Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Marc Lanctot, and Karl Tuyls. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. Proceedings of the 38th International Conference Machine Learning, pages 8525-8535, 2021.
Julien Pérolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, al. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 378(6623) 2022.
Tuomas Sandholm. Steering evolution strategically: Computational game theory and opponent exploitation for treatment planning, drug design, and synthetic biology. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 4057-4061, 2015.
Samuel Sokota, Ryan D'Orazio, J. Zico Kolter, Nicolas Loizou, Mare Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In Proceedings of the 12th International Conference on Learning Representutions, 2023.
Eric Steinberger. Pokerrl https: //gi:://tiit htgggtttub.... cowm///nnheeeiigoooo/ooeee... 2019.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint 1rXiv:1407.5042. 2014.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling, Solving heads-up limit texas hold' em. In Proceedings of the 24th International Conference on Artificial Intelligence, pages 645-652, 2015.
Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng, Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie J Su, and Yaodong Yang. Magnetic mirror descent self-play preference optimization. Proceedings of the 13th International Conference on Learning Representutions, 2025.
Zifan Wang, Yi Shen, Michael Zavlanos, and Karl Henrik Johansson. No-regret learning in strongly monotone games converges to a nash equilibrium. 2023.
Chen-Yu Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In Proceedings of the 9th International Conference on Learning Representations, 2021.
Hang Xu, Kai Li, Haobo Fu, Qiang Fu, and Junliang Xing- Autocfr: learning to design counterfac- tual regret minimization algorithms. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, volume 36, pages 5244-5251, 2022.
13

---

Hang Xu, Kai Li, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Dynamic discounted counterfactual regret minimization. Proceedings of the 12th International Conference on Learning Representations, 2024a.
Hang Xu, Kai Li, Bingyun Liu, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Minimizing weighted counterfactual regret with optimistic online mirror descent. In Proceedings of the 33rd International Joint Conference Artificial Intelligence, pages
2024b.
Hugh Zhang, Adam Lerer, and Noam Brown. Equilibrium finding in normal-form games via greedy regret minimization. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, volume 36, pages 9484-9492, 2022a.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero-sum games. In Proceedings of the 39th International Conference on Machine Learning, pages 26772-26808 2022b.
Naifeng Zhang, Stephen McAleer, and Tuomas Sandholm. Faster game solving via hyperparameter schedules. arXiv preprint wrXiv:2404.09099 2024.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 1729-1736 2007.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We clearly show the assumptions used in our proof (Section 2 and 3), and diseuss the primary limitation of RTCFR+ in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification:
We provide the full set of assumptions and a complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce the main experimental results of this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We will provide the code once this paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
soteeeesabbsiisoooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppulcc///eecccc/ genpliiiiggdde....eeee /CodeSubmia agionoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, we do.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the details of the computer where the experiments are conducted.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http///eerri...eee
dinee???d
Answer: [Yes]
Justification:
This paper only investigates the convergence of some algorithms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper only investigates the convergence of some algorithms.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The code that used is cited.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We only use LLM for writing and editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https:/ /ttp:/::///e.p../eeeee /00p:////c.....eeeeee/e////////0 for what should or should not be described.
21

---

A An Example of Extensive-Form Games
To illustrate the components of an EFG, we provide an example using the classic game of Matching Pennies, as depicted its game tree representation in Figure 2. As shown in Sec- tion 2, an EFG formally defined by the tuple G [N, P, }. In this example, the set of players is commences at the root of the tree, which cor- responds to the empty history Ø E H. The player function P(h) determines who moves at history h; here, P O, so the player O makes the first move. The actions available to the player 0 at this initial decision node are given by A(Ø) [heads, tails).
PO
heads
tails
{0,1} The game
heads
tails
heads
tails
1-1
-11
-11
1-1
Once the player 0 chooses an action, the game transitions to
Figure 2: A classical EFG: Matching pennies games. "PO" and "P1" represents the player 0 and 1, respectively
history. For instance, if the player chooses "heads", the new history becomes (PO:heads). At this stage, the player function dictates that is the player I's turn to act, i.e., P(PO:heads) = P(PO:tails) = 1. central concept in EFGs for modeling games with hidden information is the partition of each player's decision nodes into information sets Z. In Figure 2, the dashed line connecting the player I's two decision nodes signifies that they belong the same infoset. This means that when the player 1 makes choice, they are unaware of the player O's preceding move; the histories (PO:heads) and (PO:tails) are indistinguishable the player A formal requirement is that the set of available actions must be identical for all nodes within an information set, which holds true here as the available actions are A(PO:heads) A(POrtails) (heads, tails].
After the player 1 selects an action, the game concludes, reaching a terminal history. also known leaf node E Z. Each leaf node is associated with payoff vector that specifies the utility for each player, (2), un (=)). For example, if the sequence of actions is (heads, heads), the game terminates with the payoff vector (1, 1)). indicating gain of for the player and loss of 1 for the player 1. Conversely, if the coins do not match, as in the history (heads, tails), the payoff is (-,,1). Since for any terminal history z, the payoff's for the player 0 and the player such that uo(2)= = u1 (2), this particular EFG is classified as a two-player. zero-sum game. This single example effectively demonstrates how an EFG captures the sequential structure, information constraints, and outcomes of a strategic interaction.
structured
B Related Work
Counterfactual Regret Minimization (CFR) algorithms. CFR algorithms are among the most widely used methods for solving real-world EFGs [Bowling et al., 2015, Moravčík et al., 2017, Brown and Sandholm, 2018, 2019b, Pérolat et al., 2022]. The core idea of CFR is to decompose the problem of regret minimization across the entire game into subproblems within each infoset, employing regret minimization algorithm was introduced by Zinkevich et [2007], which utilize RM [Hart and Mas-Colell, 2000] as local regret minimizer. To enhance the performance of CFR, a common approach is to design more effective local regret minimizers, as the choice of local regret minimizer largely determines the overall CFR algorithm's 's efficiency. Advanced local regret minimizers are typically based on RMM including RM+ [Tammelin, 2014], Discounted RM (DRM) [Brown and Sandholm, 2019a], and Predictive RM+ (PRM+) [Farina et al., 2021], which correspond to CFR [Tammelin, 2014], Discounted CFR (DCFR) [Brown and Sandholm, 90]9a], and Predictive CFR (PCFR*) [Farina et al., 2021], respectively. However, CFR algorithms typically achieve theoretical convergence to the set of NEs of EFGs only through the average of iterates, also be called as average-iterate convergence.
local regret minimizer. The vanilla CFR algorithm
Last-iterate convergence results of CFR algorithms. Pérolat et al. [2021] provide the first last- iterate convergence result for CFR algorithms in learning an NE of EFGs by transforming the task of learning an NE of the original EFG into finding the NEs of sequence of regularized EFGs and
22

---

ensuring the sequence of the NEs of these regularized EFGs converges to the set of NEs of the original EFG. However, their analysis assumes continuous-tima feedback, condition rarely satisfied in practical scenarios. Subsequently, Liu et al. [2023] presents the first last-iterate convergence result for CFR under the discrete-time feedback by transforming the task of learning an NE of the original EFG into finding the NEs of sequence of perturbed regularized EFGs rather than only regularized EFGs, since the addition of perturbation introduces the smoothness of counterfactual values. Nevertheless, both algorithms do not leverage RM algorithms the local regret minimizer, leading to a suboptimal empirical last-iterate convergence rate compared to traditional R.M-based CFR algorithms that only achieve average- iterate convergence, demonstrated in our experiments.
Last-iterate convergence results of RM algorithms. Except this paper, Cai et al. [2025], Meng et al. [2025] also investigate the last-iterate convergence of RM algorithms. However, their results mainly focus on non-parameter-free RM algorithms, whereas we considers parameter-free RM algorithms. Specifically, Cai et al. [2025]. Meng et al. [2025] mainly investigate smooth RM+ variants [Farina et al., 2023]. The lack of the parameter-free property in the results of Cai et al. [2025], Meng et al. [2025] makes them less applicable when solving real-world games. Although Cai et al. [2025] investigate RM+ (CFR+ uses RM as the local regret minimizer), a parameter-free RM algorithm. their proof techniques related to RM+ primarily follow our proof techniques. Furthermore, the results in Cai et al. [2025], Meng et al. [2025] are confined to NFGs, whereas we focus on EFGs.
We establish the first parameter-free free last-iterate convergence for R.M-based CFR algorithms in learning an NE of perturbed regularized EFGs. Notably, our parameter- property holds for any initial accumulated counterfactual regrets not only the zero initialization in previous works [Farina et al., 2021]. While CFR+'S +s 's parameter-free property in its first theoretical convergence result (Tammmelin et al., 2015] holds for any initial accumulated counterfactual regrets, this result is exclusively limited to average-iterate convergence. In contrast, our proof technique simultancously establishes both parameter-free last-iterate (Theorem 4. and average-iterate convergence (Theorem F.1) for CFR under any initial accumulated counterfactual regrets'. Notably, the proof techniques employed by Tammelin et al. [2015] differ fundamentally from those utilized in ours and most recent works on RM-based CFR algorithms [Farina et al., 2023, Xu et al., 2022, 2024a.b, Zhang et al., 2024]. These works, including ours, adopt the Blackwell upprouchability framework (as introduced in Section 2) in Farina et al. [2021] to prove the convergence of RM-based CFR algorithms,, while Tammelin et al. [2015] use the potential function [Zhang et al., 2022a]. Unfortunately, as previously mentioned, the parameter-free property in Farina et al. [2021] (even including Farina et al. [2023], Xu et al. [2022, 2024a.b), Zhang et al. [2024)) holds only under the condition where the initial accumulated counterfactual regrets are zero. Lastly, experiments show that our algorithm, RTCFR substantially outperform existing algorithms that achieve theoretical last-iterate convergence.
In this paper, we only focus on the last-iterate convergence and do not consider the best-iterate convergence because it offers limited utility in real-world games [Anagnostides et al., 2024, Wang et al., 2023]. With the best-iterate convergence, computing the exploitability of each iteration s strategy profile is necessary to select an optimal strategy, but this task is typically challenging due to the vast size of real-world games, such as HUNL,, which reaches a size of 10170, In contrast, the last-iterate convergence circumvents the need to compute exploitability for every iteration; it simply requires the selection of the strategy from the final iteration.
C Discussion on the Application of RTCER+ in Large-Scale Games and Its Integration with Other Technologies
Firstly, R + can be directly applied to large-scale games without any modifications. In fact, the modifications introduced by RTCFR over CFR+ are minimal. As demonstrated in our imple- mentation provided in Appendix F, RTCFR+ requires fewer than 30 additional lines compared to CFR (specifically, lines 33, 40-41, 47-49, 51-55, and 62-66 of the RTCFR implementation in Appendix H). The main limitation of applying RTCFR* + to large-scale games lies in the need to tune the hyperparameters μ. and T., which can vary significantly across different games. Addressing the dependency on tuning μ. 7, and Tu remains central direction for future work. It is important to clarify, however, that this requirement originates from the RT framework itself; all existing algorithms based on the RT framework require tuning of these parameters.
Farina et al. [2021] also only establish parameter- free average-iterate convergence.
23

---

Secondly, integrating RTCFR* with the other technologies requires case-by-case analysis. (i) For algorithms that solely modify the game tree, such as depth-limite solving [Brown et al., 2018, 2020J. impact-recall abstraction [Ganzfried and Sandholm, 2014], action abstraction [Li et al., 2024], and Vector CFR [Johanson et al., 2012], RTCER* can be directly applied since RTCFR* only requires execution on the new game tree. This process is straightforward and presents no significant challenges. (ii) Regarding warm-start [Brown and Sandholm, 2016], while its concept of setting initial accumulated counterfactual regrets using an efficient initial strategy is insightful, current integration with RTCER + is not feasible. Specifically, the warm-start approach in Brown and Sandholm [2016] is an enhancement tailored for the original CFR. Formally, the analysis presented the bottom left of page four in Brown and Sandholm [2016] demonstrates that the substitute regret is given by (1, T(o" (I.a)= x (f)). This formulation implies that RT (I, a) can be negative, property that does not hold in CFR + and RTCER* (iii) As for sparsification [Farina and Sandholm, 2022], which optimizes the computation of loss gradients (E), the last line of Eq. (3)), RTCFR* + can seamlessly integrate. This compatibility arises because RTCFR+ + solely requires the input of loss gradients, which then facilitates strategy updates through the update rules defined in the first four lines of Eq. (3). (iv) The pruning approach in Li and Huang [2025] can be directly integrated with RTCER+ Since this pruning approach modifies the game tree before the algorithm execution (e.g., "permanently and correctly eliminating sub-optimal branches before the CFR begins") "), it aligns with our earlier statement on game-tres tree modification approaches. Hence, RTCFR + can be directly applied.
D Proof of Theorem 4.1
Proof. To prove the last-iterate convergence of CFR+ in learning an NE of perturbed regularized EFGs defined in Eq. (2), we introduce the following lemmas.
Lemma D.1 (Adapted from Lemma D.4 in Sokota et al. (2023]. For any x: E X, 2 0, and 7 2 0,
Σ TEN
(eT xz xx "17 >
(
x;
x. (1 2 ul| - x 1..000111
iE
where E8 Ax + (x))) - 1 (ib(r)) and ET - A'xo + + (x)) (r)())))
Lemma D.2 (Proof is in Appendix E.3). For any x. E X, E, I E I, / 2 0, and y 2 0.
[| S (T)]1 S P 2nD
where 05 (J) (1, E A(T)), (T, -t + Erecttt, (I)))) with èg Aa + (xo)) μ (r)oo)) and è A v (Vb((r)) as well as a is the behavioral stralegy profile associated with x.
Lemma D.3 (Proof is in Appendix E.4). For any xr x. E X, E N. 1 I 1 0, and 2 0.
|1,7 (4) og (1)l2 S 2(L + 1) - -'1l; - 2( + 2 2) 2 10, -oili
where 68 (T) 09 aa E A(T)), 60 (T, = - + Σ Erec.(r, (bg (T)), (T))) with eg
Ax; + (xa)) - ( and e = A + [V - (r) as well as a and of are the behavioral strategy profiles associated with x and x', respectively.
Lemma D.4 (Proof is in Appendix E.5). For any  a' E X with 7 >
and 2 0.
|6 -61111 < Amoz Cmax + 12, - 22
nH
where à and â' are the behavioral strategy profiles associated with & and 4', respectively.
By substituting 0, = 0, (..... (T) = 1-01 (T) of o, (I) - 1 < Do(o,
(1)-) into Lemma 4.2, we get
- ( un (I), (1) Do .09) (7)
Adding n m un (I), 0 1 - 0j) to each hand side of Eq. (7), we have
(T),((), o 2i (T) 11 + ny m ma (T), 0/+ 07)
<D (0; (1) -0))-100 (o, unn (1), 0 + m m.r (l), 0 -0) - (o ,0),
24

---

which implies
of (T) 01)
<Dolo (1), 01) + m (1) 0/) - Dola, (1() - - - (1) 0
(1),
(1) m
u. (T) 0 0) - - 03)
<D>(oRinT 01) 1/( m
" (1), 01) Do (1), 0 yu m m (1).0)*))
(8)
+n² [1 m pm (1)
|0
0:11 De (07 .0)
2 (T). 01) nk m
2
(1) 01) D " (T), 0) ny( m 0000 (1)))
(1 m PPT P (T)
where the second inequality comes from that Va, b E IR, p > 0. (a, b) < /||a|//22 | 1b6l1//2p)) (in
this case, a = (T) m -1..:"---"-11 (T), b = 0,+11 ff. and p 1), and the last inequality is from that
Va, b E IR I|a bl/ |bb a 2 (a b) (in this case, 0,+1 and b = 0²).
Arranging the terms in Eq. (8), we get
( of 14 (T) 03) - 1 (1 m mI (1)
2
<D (1), 01) + ( (m. 07) - (o(oo.nnmm)) (1), 17(( m 2... (1), 0
According to the definition of (1), we have
1, (m) 7.2 (T) 0 =1- -, (..)).)))))
(60)))
-0
where the second equality comes from that
0
-z)( (6()) (0)(1) (1) (0 1)
1 09) 0.
(6)()) (1)
Therefore, we have
m (1) uur. 31)
"| ((-66(0))((0)));,)))) <D (n) M.M. 2
u.n. (1),0(t)))n()))) m 7... (1),0(+)).
Let 3,- = क mint (I). Continuing from Eq. (9), we get
as)8; (m((T) - -m....1.11 (T)
n3:1-6 (1 (1- - (11-))-11--0)))) a1)o (1)) - 11
2
me. (1- (1)) 7
- (1)) 07) ((,,
(o, H.7. (1) 0 - - .... (T), of+1)
A.
|m,(1)) m
1..0000 (T)
=n8(1-6(() (1 (0)) +
(T) 71) - 21 (1--))) 03)
2
(1- (D (1)
0 + ( (1),0) (1107 0- 17/ m,
7.7
(1).0 01
(I),
|m m.mar (1)
- 0: (I)) -
2
$ (1 - )3) (o) Mo (T), 01) + - 7.. (1) - Do (.. 0111 - 7 m... 0)+1))
By applying Lemma 4.3, we have
(1) 0000 (1))
n S'
2
ENEATEE
Su (Dolo (1) 2000 10
(1).))()))))))(( - (1),0++1)))) - 7. (1),07+1))
SENTEI,
25

---

where Çi = (1- a1)51. (1- Since 0 s 5i S 1 (as
0 S 31 S and 0 - as S 1), we get
-m; 1. (1)1
LEΣN IiENTET
IiEN
ΣΣ (r(D T (1)))))))))) m 1101 -mm (1),00 (1),0++1)).
(1),0(t))) -
iENTEZ,
By applying Lemma D.I, we obtain
(m((1)-m, m.
EEEEE EHEATEZ
So (T) MA ( -D (1),0++*)-)) ΣΣ iENTEI
m.7 (1)
(10)
Now, we use the smoothness the instantaneous counterfactual regrets to transform (1)
m m. (T) into term only related to || -.-.u... [2- Formally, for the term (T)
1... (T)) from the definition of (T) and viz; ...... (7), we have
m;
[T) - (D)12
+ (1), (1),o, 1. 11)
=I (00000000""000000000000000000000 (T), 265 1
unt (n)t)mo)) (1).0 (1)
-T)
+2 +=440001(((0000)))01100111111"10 (1)) un0 (1) (6, (0))) m.0.0. (1))
(1)
(. (T))
+4 (11 "n (b) (I).o, ( (T)
where o. (1) 87 (1)-1 By using Amaz maxjez IA(I),, we have
1-a1
m1((1) - m m. (1))
(T] 6,.11.05 (()) 4
maz (()
1470 (T)
(11)
+ +44 ( (I) (0, 1:77 (I), (1)))
For the term (1 - in Eq. (11), we have
((()())) (0)(1), of m. (1))
-1())((),(((0-0 - o. (T)
(12)
- - (1)112
S(P+ + 21D)) of "
where the last line is from Lemma D.2. For the term of (6) 100 (F)) a 2..5 (I))l in Eq. (11), we get
(I)) 20000 (T)) (0) 1000 MA (
(I) 6,147.6 (I), H.7. (T)
(13)
(T) 6, (T)
14 (T))
<I) ... (4))
where the last incquality comes from ( < as ". in simplex. By substituting Eq. (12) and (13) into Eq. (11), as well as using Amax 2 1, we obtain
(T) :4:77 (T) 1/
<2]10[(1) 67 m... (1)l12 + 4. (P (P 22DD) 67 W0 (1)
(14)
+ 412 (6) 0, (T)
26.42 maz
(1)
0:000 (1) + 442 max (P (2+D)))((lo;(1) - -0:
26

---

By applying Lemma D.3 into Eq. (14), we get
[Im m "1
7. 11)
12.4 (L || x 2 11 + 12.4 maz (P 22D))21103 6,.4...11
(15)
+ 4A (P 22D) o. u. (1)
< 122 (L + 2)² || 4 "... [| + 16 16A + 22 o, 3,..7..113
By applying Lemma D.4 into Eq. (15), we get
(1) -m; 4.7.0 (1)112
$12A4 max (I++)) - 277 1 11+16 (P (Amor Cmaz +1)
1 x amm.. (16)
72H
By substituting Eq. (16) into Eq. (10), we have
ΣΣΣ " Amas (1((L-A)+16((+22DD)) (Aman Omno 1mn=+1)22 || 16'-2mmmm:: 2-....111 LENEEE
AmannOmn
unll - -
72H
Ci (Ps( ".. (T) P... (T) -mm M.r (T),((()))) 11,
KENTET;
which implies
T urllat x 2.2.0
n A Amar (((++)))++((++2)))) (Amaz 0mao+1)2 11 1.7.111
72H
ΣΣ (Dplos (T),0)) m 11.00 (0, " (T),0 ) 1mm (1) KENIEI.
Obviously, if
1C 2 (6(L+))+8(P+22))))) (Aman Cmac
22H
20,211
2 I[ (6 (L+ 8(A max Cmax ()
we have
mm b x 1.7001
ΣΣ iENTEI,
1. -D,,0)))>(('""" 160 ) )-n(-m,
m an (I),07 +))),
By using Lemma 4.4, we have that m #... (T). 07 2 As a result, we get
-Dy uir (I), (I),0T++) 0T - イp m;;"" a.iii (I), 07 S Then, we conclude that VT 2
WT 1''--a0 -
ΣΣ 1.: (T).0)+n(( ( m u.u. (T)
2
NENIEL.
1 -4.7. (2000))
which implies the asymptotic last-iterate convergence of the sequence { 42 ... /² ......) to NE 4 aaPo of the perturbed regularized EFG since < Ç S (as mentioned above).
As analyzed in Farina et al. [2021], if 0] 0. for any 7 0, the generated sequence ( .²...., _t, ....... remains identical, achieving the parameter-free property. this paper, we further establish that for any initial 0} (RAA()))) and n7 0, the sequence o' converges to t487..
27

---

We first prove that for the accumulated counterfactual regret sequence {0). 07 ...... ......} gen- erated by / E RlA(T)
20 and 17 > O, there exists a corresponding sequence (0) 07" ..... ....
generated by 0 E R and vf - p/(2C)), such that the resulting strategy profile sequence is identical. By the update rule of CFR defined in Eq. (3) and the analysis in Farina et al. [2021]. 0,+1 E arg min oi 0. { (-m 0,) + :; (0,, 00) can be expressed
{ "² .'' ...
as the projection 0 10] + (T)+ where [1] max (. 0). Setting 0 r/'0) for z it follows that 07+1 = 10 r/ ( and (7) = / /: 1) 0 /0) 1) hold [Chakrabarti
al., 2024]. Furthermore, it is evident that Ei= || x "P - O(1) holds independently of the value of the initial accumulated counterfactual regret.
Based the ahove analysis, conclude that (i) for any accumulated counterfactual regret sequence (0). ... o.....} generated by any I E accumulated counterfactual regret sequence {0)'. ..... 0 ......
( and 17 > 0, there exists a corresponding generated by 0 and r/
v/(2C)), such that the resulting strategy profile sequence {i) _² ......'...... } are identical, as well as (ii) the strategy profile sequence { ( x ....,.... ......) generated by the accumulated counterfactual regret sequence (0)'. , 0 .......> converges to "u...... Therefore, we have that for any 0 [RA(())) and 17 > the generated strategy profile sequence { x2 ....., .... converges a aa demonstrating the parameter-free property. We complete the proof.
E Proof of Useful Lemmas
E.1 Proof of Lemma 4.3
Proof.
From the definition of EiE, क. (1)(==(()),(()000(() we get
Σ के (1)
TET;
(17)
Σ m
()))=
Σ E (1),
Ie7:
IEI
For the term EiET, /5
we have
Σ
(1)
IEI.
Σ
np (T) Σ
dilT.a)
((I.a)+ E (-o((T)),
(18)
IEI
aEA(T)
E Σ
7े' (T)((LO))((
Σ E (T)((I)) Σ (T)
(EI.EA(()
TET.EA(1)
P'EC.1.))
Then, by substituting Eq. (18) into Eq. (17), we have
Σ
IEI.
Σ m/ (0)
Σ Ef (dd(())))))))))
Σ Σ (To((T))))
Σ
(-o((T))
1E4,
(EZ:EA(()
(ELBEA()
P'C,(La)
Σ कं (1)
Σ Σ (dd
Σ
-
A(T)
(19)
We denote the initial infosets as Zimitt i.e. for any I E Iimit, there does not exist l" E I such that 1 E C1",", a") holds for a a" e A(I"), For the term Σiez, क.
28

---

ΣIEI, ( in Eq. (19), it follows that [
E JEZ, (EC))
E E क. (())()(())))((1))
(20)
Σ क. ( (T),
IEI
Since the probability of reaching any I E Ij always regardless of the strategies or o', have that Yo, o', and T,mit, ai (I) = n (I). Substituting this into Eq. (20), we obtain
Σ TEI
की of (f)
=E
IEIIE
(21)
Σ TET
(1)
a)) REA(T)
Σ
(((l,a)+ E (-op(()) NEC((T.)
Σ
Σ
JEL, aEA(I)
where the last line follows from the recursion. Substituting Eq. (21) into Eq. (19), we obtain
Σ
-((())
IEI.
=Σ Σ
T (((0))((1))))((111) (M) at] (l,, xx()
TET DEA(1)
e N, I, xf (1) x, and प. (1)o[(1,a) x²(1,a) via the definition of the sequence-form strategy. It finishes the proof.
E.2
Proof of Lemma 4.4
Proof. First, when 0, O, have that V/ Iz, (-m 162 (I), 0,) =
Next, we prove by contradiction that when 0, 0, VI Z,, it holds that (-m; "...0 (I), 01) 2 0.
Suppose there exists one I' E I, and 0z, > 0 such that (-m (())))) 0',)) < O. We construct new strategy of which matches 0, ",0.7.5 (not o *...7.r except at the infoset 7', where it defined as (0'//00,.. 1). For (- m
(-m" m.r (T'), p,))) we have
m (T),, 0',)
( (r' (or o. a. ((" (T)))
(6,7 1477 (I'), ((') 0 ".
16/ uo ( 1.
; (I') -((('))
Since (-m 9- (1'), < and |10%~11 > 0. we have 1 ((')),(((,,)))))))),,), 0 O (1') > 0.
We define ( = (1 11-1ayll (I) + 71 for all I. Additionally, we know that o. u4 (I) (1 ai ) 4.7. (1) + 7 for all I E I, and that (- 0... (I") of "p (I')-o((T')) 0. Hence, +11
follows that (-ò -4.7. (I'), 8 2.... (I') (((T)) >
The correspond sequence-forn strategy of át is represented by a'. According to Lemma 4.3 and the definition of NE, we get
Σ mp (1)(-07-411))) (0).),,.(1()))) IEI,
S.
(22)
Since of matches o o 2.55 except at the infoset 1', and given that a((T) = (1 a))o((1) +71
for all 1 In, well " (1) (1 ar)o; 2..5
( (I) + 71 for all I I, we obtain
29

---

( (1) - (1) = holds for all I E Ij except I'. Therefore, we get
(eT u 2.77
x
Σ
#i a'
(1)--; (I), 10 (1) (1)--:(1) o((
JEL.
(23)
{ 1.70 (T)), P (T') - ((()) 0,
where af is the sequence-form strategy profile associated with o; By the definition of é/. it follows that ét E X However, from the definition of NE, as shown in Eq. (22), (ep (am-. O, which contradicts the result in Eq. (23). Therefore, there exists no E I, and 0,,
3 2. 2 S
such that (-m (H". 0'.) < 0. Consequently, when 0, 0 for all I E I, it holds that {-m;
".177.0 (I), 01) 2 0.
Through the discussion of the above two situations, we complete the proof.
E.3 Proof of Lemma D.2
Proof. From the definition of 8g (I), we get
(00())))))]]) aEA(I)
Σ (6
Σ 11 (I,a) Σ
aEA(I)
PEC,(L,))
Σ aεA(1)
1-
Σ
Σ
(T)
(24)
Σ aEA(I)
Σ
Σ
(EA(T))CC((..))
Σ aCA(T)
21,)
Σ
Σ
(()
(EA())EC)((a))
E (-E)
I'ELa'EA(T))
where the last line is from recursion. Continuing from the above inequality, we get
ΣΣ |1 1 (T'a')l
PET d'A(!))
(25)
=I l1T + (V - (v:))l)
S1e, + (V) + = s P 2nD,
where Ey Aai and lt A' By substituting Eq. (25) into Eq. (24), we have 1: 16 (1) < P 2nD.
completes the proof.
E.4 Proof of Lemma D.3
Proof. From the definition of (Z) and og' (T), we have
1107 (T) 09' (2)
<|100 (T) 65' (T)
Σ || (T,
Σ
(oT((")
ē (I,a) Σ (T), (("))
as A(T)
(TE).(T.a)
('EC((T))
< Σ
-1- (T, a) + è (T,a)ll+
Σ Σ
(T(( - (")) (T)))
AEA(T)
AEA(T) P'CA(L,))
30

---

Then, we have
(0) 69 (T)lz
Σ 1 (I,a)t (I,a)ll
AEA(1)
+ Σ
(EA(T))CC.U.
(26)
Σ (L,) (I.a)lI+ aEA(I)
E (10(1),,(())--0(()))))))))
Σ
E (((E( (f),
aEAL)))CC....))
For the term [1 in Eq. (26), we get
- (101))))11)))0)0)))) <1)6 ((())
((')) (T'))l
(27)
-((''))l
where the last line comes from Lemma D.2. For the term (| o(())) (69 (r)))l Eq. (26), we get
(T) (6 (()) |1 (1))
of (()))
S160f (1') of (1))))ll))()))
(28)
6 65 (T')ll,
where the last line comes from |))((())) S 1. By substituting Eq, (27) and (28) into Eq. (26), we obtain
16 (I) 09' (1)l
of (T)
67' of'( (I)I
< Σ
(T Et' (I,a)ll++ Σ Σ
(P+ 2TD) ((T')
ME ((1)
aEA()) PEG((T))
(29)
Σ
Σ
[6 - (T)
REA(T) (T.))
<I 2 1|: + (P + 2/D)|l - Al||,;
where the last line is from recursion. For the term -/ē - in Eq. (29), we get
E
1 2 111 = [| (N;)) (vb(()))) C pV (v
=1 -1 + μæ= et¹² - -paill
(30)
<L| 2'111 + u|| x'Ilı
S(L + p)]l x x' a'|l1, 1|
where Eg Aai and e9- A A'xp. By substituting Eq. (30) into Eq. (29), we get
||o] (I) 06' (1)ll2 s (L+ (L+M)] 2'11 (P + 2μD) o'11ı -|| +|66% (T) 0g' (nll < 2(L 1) x'Il 2(P 2μD) of
where the second line is from bb, e E R. (b+ c)² < 212 2x2 (in this case, (T. + u4) - and (P + 2pD))la, ofll1). It completes the proof.
x
31

---

E,5
Proof of Lemma D.4
Proof. From the definition of ||ō; - -1 we get
1/.-0/111
Σ (E)))
Σ
(T,a)
(T,a) (pr)
(((p)) ||I
(TTTa))((p1)) (((Ta))0:(p1) (pp))((((1))
Σ
Σ
2.(p1)0((0))
(ET,0E(())
=E
(p()))(((pr)) |0 [1(_ (EZ(
E
E
E
(pr))((((1))
ΣΣ (ET(
E
(1t.1:/10000...aaaa/000000000000 (31)
(pr))
For the term
(T,)) H. [0) (31), we have [b)((,a)d((pp) =. (pr)ll
(32)
For the term ([ - (nn)l (31), we have | (0: -
=
(33)
By substituting Eq. (32) and (33) into Eq. (31), we have
||0 10ā-6ā111==
=E (((D))(((pr)
(z. 1|
1
(ET,
(,(I,a)
2x(p1) (1(((p1) 2.(p1) [2 -
ΣΣ
(
AET,EA(1))
Since at(T,a)/ = Ti( a)) I 1, we obtain
|0; 100-661l15 Σ Σ
3((p)) T
1 [((pr)
IET,
Σ E ΣΣΣ (ET: 7
where the last inequality comes from (1) < 1/7" for all i E N e I, and &; X? (this follows from the facts that H denotes the maximum number of actions taken by all players along any path from the to a leaf node and the probability of selecting each action is guaranteed be greater than in perturbed EFGs). For the term Σie,, EmEACH) z [(()(r)) (pr)ll, we get
Σ TEL, aEA(T)
Σ
7 [((((p)) - #((P1)l1
3
Σ TET, aEAll) PEE, (L.)
Σ
Σ
711 (I, (I, a)la
Amaz Omaa
(1((1,)) 21,1aa)ll1
TET. aEAlI)
Therefore, we have
Amar Cmaz + 7
||ār K1ll S Σ Σ
(T, (T(T,a)lli
IEI, REA(1)
Amar Cmaz
[ -.'11
It finishes the proof.
32

---

Our Parameter-Free Average-Iterate Convergence of CFR
Now, we extend the proof of CFR + in Farina al. [2021] via our proof approach in Appendix D to demonstrate that for all > 0, CFR*'s average-iterate convergence holds for all 0 E 20 RAAD) not
only for 0 = O. This result is significant because it implies that even when the strategies generated during the initial iterations are discarded, CFR + remains achieving average-iterate convergence. Specifically, since average-iterate convergence holds for all 0) E R 20
glA 02 can be treated as new
) ensuring that CFR enjoys average-iterate convergence for all n after iteration t. Indeed, discarding the initial phase strategies is a common technique to improve the empirical convergence rate of CFR+ (Steinberger, 2019].
Theorem F1. Assuming all players follow the update rule of CFR+ with any 0] E RRA(D))
and T converges the set of NEs of the perturbed regularized EFGs defined in Eqq. (2) with any y 2 0 and 2 as T + cc.
20
? the average strategy profile x² Et=1 x¹
Proof. By substituting 0, (1= - E [A(T) with E,(1) A())
into Lemma 4.2, we get
((m (o, Du(a, (0 09) m/ 0,t1 07)
(o( ()( D2 (0 0%)
04) ()) According to the definition of (T), we have
(m, - 07) =()((1) (0))0)))0(( -
(1)
where the second equality comes from that
0 (0).
(T)(T) (o(()), -
)1,0% 0,
-
Therefore, we have
'< -() {D)(o.(1),0) (- ) -0)).
(34)
Continuing from Eq. (34), we have
7| (1) (1) (1-ar)o;(1)
<(1 ar) (D)(o()))) =
(I) 01), -1)1)
which implics
リ (1- -1 <(1 - a.) (Do 1
71)
0,+1 -0))
Therefore, we get
7( (( - (.)) s (1 (1-ai) [ ((m 07 01))
Continuing from Eq. (34), we have
! (T) - (T) (T) - oz(
<(1 01) ) (T) (a,(a,(T),0)) D (T) -()))
By applying Lemma 4.3, we get
T
C a -2,)
1=1
(Daloi(T,0)) (1)
Σ
(1 1 am)
(m,(TT), 07))
7
n
VEN TET.
33

---

where z; is the sequence- crruence-form strategy corresponding to o,. Using & to denote (1 aa)) ( (I), we
get
T
T
(1(o,(1).05)
(o(o)(1),0))) (1;;
Σ
Di)s
ΣΣΣ
ST
"
!=liENTEI
(pla,(1).0))
(a(a,(1),07)))
ΣΣΣ EliENTET.
E1
+1m
-0))
7
(35)
Lemma F.2 (Adapted from Lemma 11 of Wei et al. [2021]). If the player i follow the update rule of CFR with 1 0 then for any I I, and t 2 1, we have
|10 0 - n| (T)
By substituting Lemma F.2 into Eq. (35), we get
(Dllo(())0))
Do(o:(1),0)t) + m
Σ ae 2.)) S Σ ΣEM
Σ &1
ENN IEZ.
Assuming (1) < M, we have
(o(ar((),0))
Σ (2, -
ΣΣΣ &
+ nM
EliEN TET:
(36)
Delov(1). 01)
ΣΣS &
Σ nM
IEL,
According to the analysis in Appendix D, we have that for any accumulated counterfactual regret se- quence (0). .................. .f....> generated by any 0) R A(T) and 1) 0, there exists corresponding 20
accumulated counterfactual regret sequence {0)', 08' ....... 0 ..... generated by 0 R!A(0) and n' > 0, such that the resulting strategy profile sequence { .......,. E' ....... } are identical, where 0-" rr'0i/n To analysis the convergence rate of the accumulated counterfactual regret sequence (0) 07' . 0y',. }. from Eq. (36), have
20
+ +n/TM) (a(a:((),0f) "f
Σ C al a.) S Σ
Σ &r
(37)
IEN IEZ.
By substituting 0 010 into Eq. (37), we get
Do(os(T), Y0i)
E (e, - a.) -
ΣΣS &
"f + 7/TM
IEN IEZ,
From the fact that Va, b E Rdd ||a blll/2 = bb
[b-al13/2
all3/2 = ( b). by using a = o1(1) and
[00)
we get
T
|0 (T)
(n/0))2
Σ E4 -
a.)
+ +
(38)
2n'
2n'n²²
ieN TET,
As (I) E A AIA(I), we have (la:())]1
S In addition,
(2/0)) = 1/110011/(227²))
Continuing from Eq. (38), we get
10
Σ 1=1
Σ
Σ
El
+ r/
+ T'TM)
2nT
2n?
iEN TET.
34

---

Table 2: Sizes of the games.
Game
#Histories
#Infosets
#Terminal histories
#Depth
#Max size of infosets
Kuhn Poker
58
12
30
6
Ledue Poker
9,457
936
5,520
12
Battleship (3)
732,607
81,027
532.132
Liar's Dice (4)
8,181
1,024
4,080
Liar's Dice (5)
51,181
5,120
25,575
14
Liar's Diec (6)
294,883
24,576
147,420
16
Goofspiel (4)
1,077
162
576
7
14
Goofspiel (5)
26,931
2,124
14,400
46
Goofspiel (6)
969,523
34,482
518,400
11
230
Subgame 3
398,112,843
69,184
261,126,360
10
1,980
Subgame 4
244,005,483
43,240
158,388,120
8
1,980
We use Ma denote max( m2x( In addition, as 0 S (1-ay) and 0 S x1 S we have 0 & &τ I 1. Therefore, we get
Σ (e #t 21)
+ tT +
1)M +
2ny'
TET:
By setting of
1/ 2( + 1)M9. we have
(e, - ai) s v 2(T 1)M
<
V MTT with any 0) RR A() and 17 > 0. It completes the proof.
G Additional Experiments
Sizes of the Games. Before introducing our additional experiments, we present the sizes of the games used our study, as detailed in Table 2. this table, #Histories denotes the total number of histories within the game tree, whereas #Infosets represents the count of information sets. The term #Terminal histories indicates the number of leaf nodes, and #Depth refers to the game's tree depth, defined the maximum sequence of actions in any single history. Finally, #Max size of infosets signifies the largest number of historics contained within a single infosct.
Performance of RTCFR* under simultaneous decrease of and we present the results for RTCER + with modifications in line 8 where μ. X (1 ? +- y 0.5, and r <- &T.+1, with <= lc 16, shown in Figure 3. We denote this variant as "RTCFR* + V2". Our findings reveal similar.
that the empirical convergence performance of RTCER+ and RTCER
Performance of R under reset accumulated regrets as O. we examine the performance of RTCER+ that resets 0) to O, which is denoted "Unstable RTCFR*" in Figure 3. The parameters of Unstable RTCFR are same as RTCER in Section 5. We observe that Unstable RTCFR never converges across all tested games.
Comparison with average-iterate convergence CFR algorithms. We compare the last-iterate convergence performance of RTCFR with the average-iterate performance of CFR+ PCFR + and DCFR. The experimental results are shown in Figure 4. With fine-tuning, RTCFR outperforms the werage-iterate performance of CFR+, PCFR+, and DCFR in nearly all tested games, except for Liar's Dice (6). Even without fine-tuning, RTCER+ achieves superior performance to the average-iterate of CFR+-, PCFR+, and DCFR in of the evaluated 9 games (Kuhn Pker, Ledue Poker, Liar's Dice (4), Liar's Dice (5), and Goofspiel (4)). addition, as shown in Figure 4, even when considering only PCFR+ and DCFR, no single algorithm consistently outperforms the other two across all games.
Convergence rates in the initial phase. We now present the results of algorithms RTCFR and RTPCER+ alongside CFR R-NaD, Reg-CFR, OMWU, OGDA, PCFR and DCFR, over the first 1000 iterations. The results shown in Figure 5. Consistent with the results in Figures 1, R * and PCFR demonstrate superior performance compared to the other algorithms. However, no single algorithm without fine-tuning outperforms all others across all games.
Performance of R in HUNL Subgames. We now present the convergence rate of RTCFR+ within HUNL Subgames, particularly the ones open-sourced by Libratus [Brown and Sandholm.
35

---

kuhn
Lodur Poker
Battleship
10
10
10
10
101
Exploiaabiity
10"4
10a4
10"44
10-4
10"4
10.2
10-39
10000
15000
20000
5000
10000
15000
20000
5000
10000
15000
20000
Liar's
Liar's
100
105
10
10-
Exploitabiiit
10
10-1
10a0
10:4
10:20
10-2
10:15
10"1
Goofspiel
Goofsplel (5)
Goofisplel (6)
10"
10a3
10-1
10-1
Expleitability
10
10-1
10-1
10-1
10-4
10:1
10000 Rerations
15000
20000
Iterations
Iterations
Unstable RTCFR
Figure 3: Last-iterate convergence rates of RTCER* RTCFR* + V2, and Unstable RTCER
2018]. We compare R with CFR PCFR+, and DCFR+ Given the immense size of HUNL Subgames, we implement the tested algorithm using vector CFR. We employ the open-source code from Poker RL [Steinberger, 2019, Xu et al., 2024b], which supports vector CFR and Subgames from Libratus, specifically Subgame 3 and Subgame 4. The comparison of RTCFR and the last- iterate convergence performance of CFR 1CFR and DCFR* illustrated in Figure while the comparison of RTCFR and the werage-iterate convergence performance of CFR PCFR CFR+, and DCFR* depicted in Figure? RTCFR exceeds the last-iterate convergence performance of CFR and PCFR across both HUNL Subgames. Additionally, in Subgame3, RTCFR+ also surpasses the average-iterate convergence performance CFR+ + and PCFR
worth noting that CFR+ and PCFR+ do not provide last-iterate convergence guarantee. For DCFR, RTCER+ as well CFR+ and PCFR+ underperform in both last-iterate and average-iterate convergence performance. We speculate this is because DCFR is fine-tuned specifically for the tested HUNL Subgames, unlike the other evaluated algorithms.
Performance of RTCFR* + under different hyperparameters. We investigate the convergence rates of RTCFR* under various hyperparameter settings. Specifically, we focus on the impact of μ and on the convergence rates, as we observe that only needs to be set to sufficiently small value. The tested ranges for μ and T, are [le-4 4, 5e 4, le- 3, 5e 3, le - 2, 5e 2, le - 1, [10, 50, 100, 500, 1000). respectively. Experimental results reveal that the performance of RTCFR* primarily contingent upon the value of μ. elucidate this dependency, we discuss the performance implications of varying y values. Specifically, for small μ values, CFR encounters difficulties in
1] and
36

---

kuhn Poker
Lodur Poker
Battleship
10
10"3
10-1
10a
Exploitaility
10-4
10-
10
10.
10-11
10-1c
10-32
10000
15000
20000
50.00
10000
15000
20000
5000
10000
15000
20000
Liar's
Liar's
10:
10'2
Exploitablitt
10-
10
10-1
10
10-1
10-19
10-11
10
10
Goofspiel
Goofspiel (5)
Goofispiel (6)
10.
1.9
10:3
Exploitablltty
10-2
10-
10
10-1
10-
10'
10-1
10-12
24
10
10-4
10000 Rerations
15000
20000
Iterations
Iterations
RTCFR-
RTCFR- (fine-tuned)
PCFR
Figure 4: Comparison with classical Everage-iterate convergence CFR algorithms.
accurately learning an NE of perturbed regularized EFGs. Consequently, this challenge persists irrespective of the value of Ta. enabling that learning an NE of perturbed regularized EFGs becomes impossible. As a result, attaining an NE of the original game becomes impracticable for any T, value, which is also consistent with the experimental results. Conversely, when is optimal, neither too small nor too large, this condition enables CFR learn sufficiently accurate approximate an NE of perturbed regularized EFGs. These allow RTCFR to achieve commendable performance. However, for large μ values, although CFR are capable learning the exact NE of perturbed regularized EFGs, the requisite number of reference strategy updates becomes excessively large. Hence, observe that with large μ values, a smaller T, yields better performance. Based on these analyses, we advocate for the prioritization of determining j value, followed by the value of T,, when practically applying our algorithm.
37

---

10a
10
Explotaability
10-4
10.4
10.1
10.5
1074
10-12
1079
10-55
10n*
600
800
1000
600
800
1000
600
800
1000
Liar's Diice
Liar's Dice
Lar''s Dice
10a
10
10-1
Explottability
30
10-4
10-2
M M
10.11
10-13
10-15
600
800
1000
600
800
1000
400
600
800
1000
Goofssiil (4)
Goofispell (5)
Goofspiel
10a
10a
10
10-1
Exploitabiiity
10
10-2
10
10-32
10-15
600
800
1000
600
800
1000
400
600
800
1000
RTPCFR
Reg-CFR
R-NaD
OMWU
DCFR
Figure 5: Last-iterate convergence rates over the first 1000 iterations.
Subgame3
Subgame4
Explottabiity
1.44
20"
10-1
10--
10-4
10-3
10-2
3000
3000
Iterations
Iterations
CFR POFR
DCFR
RTCFR
Figure 6: Comparison with the last-iterate convergence performance of CFR+, PCFR+ and DCFR in HUNL Subgames.
38

---

Subgamee
Subgamed
10
20
10-4
10
10-3
10-3
3000
2000
3000
Iterations
Iterations
CFR
PCFR
DCFR
RTCFR
Figure 7: Comparison with the average-iterate convergence performance of CFR PCFR and DCFR in HUNL Subgames.
kuhn Poker
Loduc Poker
Battleship (3)
10-1
10-)
10"
Expinitabiltt
10-4
20
www.
16-4
10-1
1
10-3
Liar's Dice (4)
Liar's Dice (5)
Lir's Dice (6)
107
10P
10
10-
10-1
10-4
10-4
Expleitability
10-4
10
10'*
10'4
10:93
10-22
10-14
10
10:2
Gootspiel (4)
Goofspiel (5)
Goofspiel (6)
10a
100
Exploitabiiity
10-1
10-a
10"²
Iterations
Iterations
Iterations
T,-10
T,=50
T,-100
T,-500
7,-1000
Figure 8: Last-iterate convergence rates of RTCER* with μ 0.0001.
39

---

kuhn Roker
Loduc Poker
Battlaship (3)
10
10
10"
10
10:3
Expletabiltty
10"
10-4
10
10-1
10
10"l
16a4
10
15000
Liar's Dice (4)
Liar's Dire (5)
Liar's Dice (6)
10P
10:3
10-1
10-
10-1
Expleitability
10-4
10"4
10-1
10-1
10-1
10-4
10-41
10-41
10-4
10-
15000
10000
20000
Goafsplel (4)
Goafspial (5)
Gocfspial (6)
105
10-1
Expleiaabiity
10-1
10"1
10-
10
10:4
10
10->
10-4
10-1
10
10'1
Iterations
Iterations
Iterations
CFR+
T,-10
T,-50
T,-100
7,-500
T,-
Figure 9: Last-iterate convergence rates of RTCFR* with μ 0.0005.
40

---

kuhn Roker
Leduc Poker
Battlaship (3)
10
10
10a
Expletabblity
10
10-1
10-1
10-4
10-1
10-11
10-9
19
10
20000
Liar's Dice (4)
Liar's Dice (5)
Liar's Dice (6)
100
10-1
10-1
10
10-4
10
Expleitability
10
10-1
10-1
10
10-9
10-42
10-11
10-1
10-15
10-4
10**
15000
20000
Gonfspicl (4)
Goofspial (5)
Gocfspial (6)
10a
100
100
10:
10-1
Expleitability
10:
10-1
10-4
10-4
30
10
10:4
Iterations
Iterations
Iterations
CFR+
T,-10
T,-50
T,-100
7,-500
7,-
Figure 10: Last-iterate convergence rates of RTCER* with μr = 0.001.
41

---

kuhn Roker
Leduc Poker
Battlaship (3)
10a
10
10
10a
Explettabiiiy
10-
30
10-1
10:42
10-44
10-4
20000
Liar's Dice (4)
Liar's Dice (5)
Liar's Dico (6)
10
10"
10-
10-4
Expleitability
16--
10-4
10-2
10a
10.42
10:4
10-1
10-15
10-0
10-1
15000
100000
15000
20000
Goofspicl (4)
Goafspial (5)
Gocfspial (6)
10-3
Expleitabilit
10-1
10
10
20-4
10-
10
10-11
10-
10--
10
10
10:99
10'7
Iterations
Iterations
Iterations
CFR+
T,-10
T,-50
T,-100
7,-500
7
Figure 11: Last-iterate convergence rates of RTCER* with μr = 0.005.
42

---

kuhn Roker
Leduc Poker
Battlaship (3)
10
10-1
10-1
Expleltability
10
10-3
10-
10-4
10-4
10-4
10"4
Liar's Dicce (4)
Liar's Dice (5)
Liar's Dico (6)
10"
10-
1.0
10
10-1
Expleitability
10-
10
10:2
10-22
10-14
10000
20000
Goafspiel (4)
Goofspial (5)
Gocfspial (6)
10a
10F
1.0
10a0
10
4
10-1
Expleitabiitty
10:4
10
10:
10
10-4
10--
10-42
10-24
10-14
10-1
20000
Iterations
Iterations
Iterations
CFR+
1,-10
T,-50
T₂-100
7,-500
7,-1000 1800
Figure 12: Last-iterate convergence rates of RTCER* with μ = 0.01.
43

---

kuhn Roker
Leduc Poker
Battlaship (3)
10
10a
10"
10-1
Expleltability
10-1-
10
10-2
10-31
10-1
10-14
Liar's Dice (4)
Liar's Dice (5)
Liar's Dice (6)
10a
100
10-
10.4
Expleitability
10-1
10-1
30
10-²
10-22
10-14
20000
Go coofspiel (4)
Goofspial (5)
Gocfspial (6)
10:1
10"
10.4
10-
10-1
Expleitability
10
10
10
10"0
10-1
11
10-4
10:94
10-15
10-5
Iterations
Iterations
Iterations
CFR+
T,-10
T,-50
T,-100
7,-500
7.-1800
Figure 13: Last-iterate convergence rates of RTCER* with μ 0.05.
44

---

kuhn Roker
Leduc Poker
Battlaship (3)
10
10"1
10-1
Expleltabiity
10"0
10
10-1
10
10.2
10
10-1
15000
Liar's Dice (4)
Liar's Dice (5)
Liar's Dice (6)
100
10-3
10-4
Expleitability
10
10-1
10
10-42
10.2
10-15
15000
20000
Goofspicl (4)
Goofspial (5)
Gocfspial (6)
10a
10:
100
10a0
10-
10-1
Expleitabiiity
10
10
10
10:
10-2
10-4
10-32
10:41
10-0
10-4
10-45
10.2
Iterations
Iterations
Iterations
CFR+
1,-10
T,-50
T,-100
7,-500
7,-1000 1800
Figure 14: Last-iterate convergence rates of RTCFR* with μ 0.1.
45

---

kuhn Roker
Leduc Poker
Battlaship (3)
10
10
10a
Expletabblity
10
10-4
10a
10-9
10
10:91
10-1
10-12
10-4
Liar's Dice (4)
Liar's Dice (5)
Liar's Dice (6)
10a
10f
100
Explnitability
20-1
10-1
10
10
M4 www
15000
Go Goafspiel (4)
Goofspinl (5)
Gocfspial (6)
100
10-2
109
10-1
Expleitability
10
10-
10
16:4
10-2
10
10t
10-4
10
Iterations
Iterations
Iterations
CFR+
T,-10
T,-50
T₂-100
7,-500
7,-1000 1800
Figure 15: Last-iterate convergence rates of RTCFR* with μ 0.5.
46

---

H Implementation of RTCER*
In this section, present detailed description of the implementation of RTCHR which is adapted from the open-source implementation of CFR by LiteEFG [Liu et al., 2024].
import LiteEFG
class RICFRPlusGraph (LiteEFG. Graph)
Graph):
def -_init__ (self, gamma-le- mu-1e-3, shrink,iter-100 default parameters
super ()...init__(
self timestep self chrink_iter shrink_iter shrink_iter is T_u
6
# Initialization of RICFR+
with LiteEFG ev 1.0 LitefFG. const const 0.0)
unperturbed.strategy" is \sigma
self self. wwwperturbed.stratee.... - LiteEFG const (self.
action_set.size, 1.0 self selffaactin_set_sizze
perturbed_strateeg;
\hat(\sigma)
self strateey = LiteEFG. const(self action_set_
1.0 /
# regret_ is \bm(\theta)
self regret_buffer action_set_size, 0.0)
# ref ref_strategy is \bm(r)
self. ref ret_rre__steee strategy = LiteEFG. const action_set_ 1.0 self action_
the following three variables are used to compute nabla (pbm(()(r))) note that self ralf.ref_reeahpprre \nabla (psi((bm(r))C)
self ref rea.hhhh.pro - LiteEFG. const (self.
action_set_size 1.0)
self wwr.fpaaent__rcchppeeeee
LiteEFG. const (self.
action_set_ 1.0)
self pereet__to_child.pp......pp = LiteEFG const (self.
action_set_size, 1.0)
25
self ittratiion LiteEFG. const (1, 0)
26
self mu = LiteEFG. const mu)
self gamma LiteEFG. const (1, gamma)
self alpha_ self gamma www.se......c.nccooeeeeeeooeeeee actioa.sttionnnttsiii....
30
with LiteEFG backvard self itlffiteration. inplace iat.aaccssssi..tttttttooo... # to compute the (hat(\b(vv)).. defined in (4)
gradient LiteEFG. agggFFG.gggoggteecc. (ev, aggregator="sux") self.utille utility self (self reach rech strategy self rela.ref_reach_ppppp ref to compute the \langle (hat((bm(v))_ire t_i(I) \rangle defined in (4) ev inplace (LiteEFG dotaddient, self umperturbod.strttee)))
ref
*sigma"
# gradient ev is the instantaneous counterfactual regret hatt(\b(m))
defined in (4)
self regrett_uffeerr inplace (LiteEE. maximum (self. regret_buffer gradient ev, 0.0))
38
# to get (tigna-(t-1)_i())
self unperturbed implace (LiteEFG. normalize self.regret_bufferr p_norm-1.0, ignore_negative- True))
# to employ PCFR+ to solve the perturbed regularized EFGs, please the following line
47

---

self. umprttubed_srraeey. inplace (LiteEFG normalize (
self reffer gradient ev, p_norm=1.0,
ignore_ )egattvegaai to get 1har((siigaa>((t11_1111
43
self strategy. inplace (LiteEFG normalize self
(Apha_I))selll smperturrbe__stratee) self gamma,
p_norm=1.0, agaore.negative=Trun.
46
# update gamma and the reference strategy profile with LiteEFG
self gamma. implace (self gamma 0.5) self ref_strategy inplace (self strategy 1.0)
51
with LiteEFG. forward
# to compute Anabla \psi ((bm(r)) after updating the reference strategy profile
self, self. par.. (Lptace (LiteEFG . (self.. (self.
ref ref_reech_prob. "sum", object="parent", player=" self", padding-1))
self parentt.to_child_.rrot inplace (LiteeFE aggregate(
self.ref_strateey, "sum", "pjeent"" player-" self", padding=1))
self seef_rrach__pe prob. implace (self, parent reachttreeahhprote
self par.nt.to..ciid.ppe......
58
def update.graph env AAte@FG.Envvionnne None:
61
self timestep if self timestep=:: env update strategy, (pd_color=(2))
62
env wtt.eestttt............... env env wsel. env (av.update
if self.timester % self.shrink_iter -- 0:
upd_color-(1))
66
upd_color- [2])
upd.color=(0], upd_player=1)
upd_color=:01, upd_player=2)
else:
env e env
[pd_color=:0], upd-player=1)
71
[0], upd-player=2)
def purrent_strateg, (self, type_name= "last (est-ittrate")
LiteEFG. GraphNode:
74
return self strategy
48


Reviews:
[{"review_id": "CBRgy99DMe", "reviewer": "Reviewer_kpKA", "summary": "The paper considers the problem of establishing last-iterate convergence rates for parameter-free CFR-based algorithms in extensive-form zero-sum games. Its main contribution is a last-iterate convergence guarantee for the CFR+ type algorithm, which combines the local-regret decomposition of Zinkevich et al. with the RM+ algorithm as the local no-regret algorithm.\n\nThe analysis is conducted within the Reward Transformation (RT) framework, which has been proposed to establish last-iterate convergence guarantees through gradual perturbations of the original game. In particular, the RT framework considers a $\\gamma$-perturbed version of the original game, in which the strategy space at each information set is restricted to the $\\gamma$-bounded-away simplex. The key insight is that if last-iterate convergence can be proven in the perturbed game and then it cab extended to the original game by gradually reducing $\\gamma \\to 0$.\n\nWhile the RT framework has previously been used to provide last-iterate convergence properties for OMD/CFR-type algorithms, the main\ncontribution of the paper is establishing similar results but for the parameter-free CFR+ type of algorithms. The main technical contribution of the paper is establishing that CFR+ admits last-iterate convergence to the equilibrium of the $\\gamma$-perturbed game. Leveraging this result and the structure of the RT framework, the authors can then provide a parameter-free algorithm with last-iterate convergence guarantees.\n\nAdditionally, the paper includes experimental results demonstrating that the proposed algorithm outperforms prior approaches on large-scale extensive-form games.", "questions": "1. Concerning the experimental evaluations, the RTCFR+ outperforms also the convergence rates of time-average algorithms?\n\n2. Is there a reason for using Nash Equilibrium instead of min-max equilibrium? I think the latter would be more appropriate since your work is on zero-sum games.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The considered setting is well-motivated: establishing last-iterate convergence guarantees in zero-sum extensive-form games (EFGs) since step-size selection typically plays a critical role in convergence behavior.\n\n2. To prove that CFR+ exhibits last-iterate convergence in perturbed games, the authors first present a non-parameter-free analysis, showing convergence when the step-size exceeds a certain constant. This two-step approach seems fairly interesing. Overall, the paper appears to possess technical depth.\n\n3. The experimental evaluations are very interesting and standard benchmarks are used.\n\n**Weaknesses**\n\n1. The final algorithms RTCFR+ needs parameters $\\mu,\\eta$ that makes it a bit questionable whether it can be technically considered as parameter-free. That being said, the authors in the experimental evaluations do not fine-tune making the comparison fair. Nevertheless at least on the theoretical level this creates me some doubts on the \\textit{parameter-free take-away message}. I believe that probably the take-away should emphasize more on the practical merits of the approach.\n\n2. Although the introduction is clearly written and effectively situates the paper within the existing literature, the main technical sections are difficult to follow. While this is somewhat expected due to the inherently complex and notation-heavy nature of EFGs, there is room to improve the clarity and accessibility of the theoretical exposition.", "was_revised": true, "final_justification": "The author-reviewer discussion has clarified all of my concerns and thus I believe that the results of the paper will be of interest for the neurips audience.", "rebuttal": "Thank you for your thoughtful comments and the positive evaluation\n\n\n\n**W1: The final algorithms RTCFR+ needs parameters $\\mu,\\eta$ that makes it a bit questionable whether it can be technically considered as parameter-free. I believe that probably the take-away should emphasize more on the practical merits of the approach.**\n\n**A:**  \n\n- We apologize for any confusion regarding the term \"parameter-free.\" In this paper, all references to \"parameter-free\" pertain exclusively to CFR+ for solving perturbed regularized EFGs. RTCFR+ itself is not a parameter-free algorithm. We will explicitly state this in the limitations section of the final manuscript to ensure clarity. \n- The practical advantage of our approach is that it eliminates the need for parameter tuning when solving perturbed regularized EFGs. This is beneficial as it reduces the cost associated with parameter tuning, making our algorithm more readily applicable to real-world games compared to algorithms that require parameter tuning for solving perturbed regularized EFGs.\n\n\n\n**Q1: Does RTCFR+ outperforms also the convergence rates of time-average algorithms**\n\n**A:** We compare the last-iterate convergence performance of RTCFR+ with the average-iterate performance of CFR+, PCFR+, and DCFR (Table 1). With fine-tuning, RTCFR+ outperforms the average-iterate performance of CFR+, PCFR+, and DCFR in nearly all tested games, except for Liar's Dice (6). Even without fine-tuning, RTCFR+ achieves superior performance to the average-iterate of CFR+, PCFR+, and DCFR in 5 out of the evaluated 9 games (Kuhn Pker, Leduc Poker, Liar's Dice (4),  Liar's Dice (5), and Goofspiel (4)). In addition, as shown in Table 1, even when considering only CFR+, PCFR+, and DCFR, no single algorithm consistently outperforms the other two across all games.\n\nTable 1: Comparison between the last-iterate convergence performance of RTCFR+ with the average-iterate convergence performance of CFR+, PCFR+, and DCFR.\n\n| Game                | RTCFR$^+$ | RTCFR$^+$ (fine-tuned) | CFR$^+$  | PCFR$^+$ | DCFR     |\n| :------------------ | :-------- | :--------------------- | :------- | :------- | :------- |\n| **Kuhn Poker**      | 2.49e-15  | 6.94e-18               | 1.49e-05 | 8.56e-09 | 1.59e-05 |\n| **Leduc Poker**     | 1.97e-13  | 1.97e-13               | 7.08e-06 | 1.56e-05 | 9.72e-06 |\n| **Battleship (3)**  | 1.64e-02  | 8.60e-16               | 2.74e-04 | 1.74e-07 | 1.58e-04 |\n| **Liar's Dice (4)** | 3.19e-16  | 4.86e-17               | 4.28e-06 | 1.99e-07 | 1.90e-06 |\n| **Liar's Dice (5)** | 4.12e-07  | 5.29e-16               | 6.00e-06 | 1.10e-06 | 3.58e-06 |\n| **Liar's Dice (6)** | 6.17e-05  | 8.49e-06               | 2.47e-06 | 4.80e-05 | 2.56e-06 |\n| **Goofspiel (4)**   | 1.05e-08  | 6.77e-17               | 9.57e-06 | 2.88e-08 | 5.31e-07 |\n| **Goofspiel (5)**   | 3.38e-05  | 5.12e-16               | 4.43e-05 | 1.23e-06 | 3.70e-05 |\n| **Goofspiel (6)**   | 2.73e-05  | 1.55e-07               | 4.50e-05 | 6.23e-06 | 3.62e-05 |\n\n\n\n**Q2: Is there a reason for using Nash Equilibrium instead of min-max equilibrium**\n\n**A:** In this paper, we consider two-player zero-sum games, where the min-max equilibrium is the same as NE. Specifically, as shown in [1], “in two-player zero-sum games the concept of equilibrium, which is based on stability, and the concept of minmax, which is based on security levels, coincide.”\n\n\n\nAdditional References:\n\n[1] Maschler, Michael, Shmuel Zamir, and Eilon Solan. *Game theory*. Cambridge University Press, 2020."}, {"review_id": "jYj1q8B7Uj", "reviewer": "Reviewer_NuVT", "summary": "The paper addresses the open question of obtaining *last-iterate* convergence guarantees for Counterfactual Regret Minimization (CFR) algorithms without the need to tune a learning-rate schedule.  \nPrior work has either provided last-iterate convergence by switching to slower Online Mirror Descent–type updates or retained the fast, regret-matching (RM) updates at the cost of only proving convergence of the *average* strategy.  \nThe authors prove that the widely-used CFR\\\\(^{+} \\\\) algorithm enjoys *parameter-free* last-iterate convergence when solving perturbed and regularised two-player zero-sum extensive-form games (EFGs).\n\nThe technical contribution has two main steps.  \nFirst, it is shown that CFR\\\\(^{+} \\\\) converges in the last iterate whenever the internal step size exceeds a fixed constant.  \nThe proof leverages a novel term involving counterfactual regrets and best-response utilities to control the dynamics even though RM updates evolve on a cone rather than a simplex.  \nSecond, a coupling argument exploits the linearity of CFR\\\\(^{+} \\\\) projections to translate any arbitrary (possibly small) step size to one in the proven range while leaving the sequence of strategies unchanged, thereby delivering a truly parameter-free guarantee.  \nCombining this insight with the Reward-Transformation framework yields the proposed algorithm, RTCFR\\\\(^{+} \\\\), whose perturbation parameter is halved periodically while the reference strategy is updated.\n\nEmpirical results on nine benchmark games (including Kuhn, Leduc, Goofspiel, and Battleship) demonstrate that RTCFR\\\\(^{+} \\\\) converges substantially faster, in exploitability, than earlier last-iterate methods such as Reg-CFR, R-NaD, Online Mirror Descent with Weighted Updates (OMWU), and Optimistic Gradient Descent Ascent (OGDA).  \nIn many cases it even outperforms the classical, average-iterate CFR\\\\(^{+} \\\\), all while keeping default hyper-parameters fixed across games.  \nThese findings suggest that practitioners can now obtain both rapid convergence and last-iterate guarantees without step-size tuning.", "questions": "- The density of notation and the clarity of the problem setup may pose challenges for readers.  \n  In particular, for readers unfamiliar with extensive-form games (EFGs), the exposition makes it difficult to develop a clear understanding of the problem the paper aims to solve.  \n  I found it nontrivial to grasp how the objective is captured by the Nash equilibrium formulation in equation (1).  \n  Furthermore, following the discussion on perturbed extensive-form games, I was also left without a clear picture of the overall problem or the specific objective functions being optimized.  \n  The paper transitions quickly into discussing regret minimization and defines the players’ regrets, but without a firm grounding in the problem setting, it is difficult to contextualize these definitions.  \n  I understand that space constraints may be a factor, but from the perspective of a non-expert reader, the problem formulation remains opaque.  \n  A brief high-level overview early on, possibly accompanied by a simple running toy example, would significantly improve accessibility and comprehension.\n\n- Since the paper's main contribution lies in solving perturbed EFGs, it would be helpful to elaborate on how the perturbation and regularization may affect the game’s payoffs.  \n  In particular, more practical guidance on selecting the parameters \\\\( \\\\gamma \\\\) and \\\\( \\\\mu \\\\) would be valuable, especially to ensure that the resulting equilibrium remains a reasonable approximation of the unperturbed game's solution.  \n  This would be beneficial for practitioners aiming to apply the method.\n\n- All experiments are conducted on games of moderate size.  \n  It would strengthen the empirical results to include an evaluation of the method’s scalability to larger, imperfect-information games.", "limitations": "The density of notation and the clarity of the problem setup may pose challenges for readers.\nIn particular, for readers unfamiliar with extensive-form games (EFGs), the exposition makes it difficult to develop a clear understanding of the problem the paper aims to solve.\nI found it nontrivial to grasp how the objective is captured by the Nash equilibrium formulation in equation (1).\nFurthermore, following the discussion on perturbed extensive-form games, I was also left without a clear picture of the overall problem or the specific objective functions being optimized.\nThe paper transitions quickly into discussing regret minimization and defines the players’ regrets, but without a firm grounding in the problem setting, it is difficult to contextualize these definitions.\nI understand that space constraints may be a factor, but from the perspective of a non-expert reader, the problem formulation remains opaque.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The addressing question is very important and significant. However, the presentation is quite hard to understand. For details, please see the questions.", "was_revised": true, "final_justification": "Dear AC and authors,\n\nAs I am not very familiar with the topic, I am happy to defer to the AC’s decision based on the other reviewers’ comments.\n\nBest wishes,\nYour reviewer", "rebuttal": "Thank you for your positive feedback and insightful suggestions for improvement.\n\n\n\n**Q1：It nontrivial to grasp how the objective is captured by the Nash equilibrium formulation in equation (1).**\n\n**A:** According to the Minimax theorem, the solution of equation (1), namely $min_{x_0} max_{x_1} x_0^T A x_1$, is also the solution of $max_{x_1} min_{x_0} x_0^T A x_1$. As we consider zero-sum games, this solution implies that each player aims to minimize the maximum possible gain of the opponent. This stable state, where neither player can unilaterally change their strategy to improve their outcome, is NE since the definition of NE is a rational behavior where no player can benefit by unilaterally deviating from the equilibrium (lines 133-134).\n\n\n\n**Q2:  I was also left without a clear picture of the overall problem or the specific objective functions being optimized.**\n\n**A:**  We apologize the confusion about the overall problem. Our primary objective, as stated at the end of Section 3, is: \"Our objective is to establish the parameter-free last-iterate convergence for CFR+ in solving Eq. (2).\" In other words, we aim to demonstrate that CFR+ achieves parameter-free last-iterate convergence when learning an NE of perturbed regularized EFGs, as specifically emphasized in the introduction, lines 68-69. \n\n\n\n\n\n**Q3: A simple running toy example, would significantly improve accessibility and comprehension.**\n\n**A:** We will include a toy extensive-form game, which will significantly enhance the clarity of our paper.\n\n\n\n**Q4: It would be helpful to elaborate on how the perturbation and regularization may affect the game’s payoffs.**\n\n**A:** As we stated in lines 215-218, \"The introduction of perturbation and regularization ensures the smoothness of counterfactual values and strong monotonicity.\" More precisely:\n\n- Perturbation does not affect the game's payoffs but instead modifies the strategy space to ensure the smoothness of counterfactual values. \n- In contrast, regularization means an additional regularization term is added to the game's payoffs, thereby imparting strong monotonicity.\n\nThis smoothness and strong monotonicity reduce the difficulty of proving last-iterate convergence. Specifically:\n\n- Smoothness of counterfactual values allows us to establish a relationship between the gap in counterfactual values and the gap between strategies (line 126). \n- Strong monotonicity guarantees the uniqueness of solutions. Precisely, strong monotonicity ensures that the NE of the perturbed regularized EFG is unique.\n\nLastly, it is important to note that increasing either the perturbation or regularization weights causes the NE of the perturbed regularized EFG to diverge further from the NE of the original EFG. Therefore, as you mentioned, the selection of $\\gamma$ and $\\mu$ is critical. We provide a detailed discussion of this issue in **Q5**.\n\n\n\n**Q5: More practical guidance on selecting the parameters and would be valuable.**\n\n**A:** As outlined in Section E (lines 771-788), we have empirically evaluated various values of the parameters of RTCFR+ ($\\mu$ and $T_u$; for $\\gamma$, we observe that it only needs to be set to a sufficiently small value) and provided selection guidelines to optimize performance. Here, we provide a brief intuition about this parameter.\n\n- Selecting an extremely small $\\mu$ may hinder the CFR's ability to learn NE of the perturbed regularized game, resulting in learning an NE of perturbed regularized EFGs becomes impossible. As a result, attaining an NE of the original game becomes impracticable for any $T_u$.\n- When $\\mu$ is optimal, neither too small nor too large, this enables CFR+ to learn sufficiently accurate approximate an NE of perturbed regularized EFGs.  These allow RTCFR+ to achieve commendable performance.\n- For large $\\mu$ values, although CFR+ are capable of learning the exact NE of perturbed regularized EFGs, the requisite number of reference strategy updates becomes excessively large. Hence, we observe that with large $\\mu$ values, a smaller $T_u$ yields better performance. \n\nBased on these analyses, we advocate for the prioritization of determining  $\\mu$’s value, followed by the value of $T_u$ , when practically applying RTCFR+.\n\n\n\n**Q6: It would strengthen the empirical results to include an evaluation of the method’s scalability to larger, imperfect-information games.**\n\n**A:** If sufficient computational resources is available, we will extend larger games in the final version. It is worth noting, however, that the games currently evaluated in our paper are already larger in scale than those in related work focused on the last-iterate convergence of CFR algorithms (e.g., Pérolat et al. (2021) and Liu et al. (2023)), demonstrating a step forward in this specific area of research."}, {"review_id": "h4NRi3gtbO", "reviewer": "Reviewer_mv8m", "summary": "The authors introduce methods of applying the *reward transformation* technique of Perolat et al. (2021-22) and Liu et al. (2023) to regret matching in two-player zero-sum extensive-form games, arriving at RTCFR+, an algorithm with guaranteed last-iterate convergence and fast practical performance.", "questions": "Some of these questions were alluded to above. I also welcome any other comment regarding the points raised in the main body of the review.\n\n1. Could you compare your Theorem 4.1 to previously-known results (such as Lemma 1 of [1] above)? In particular, why does your proof require anything at all specific about extensive-form games or CFR?\n2. Could you provide a rate of last-iterate convergence for Theorem 4.1?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper claims that RTCFR+ is parameter-free, which to me means that it, like CFR+, works \"out-of-the-box\" and does not require the user to set any hyperparameters. This is evidently false: in Algorithm 1, I see at least three \"interesting'' hyperparameters: $T_u$, $\\mu$, $\\gamma$. Moreover, these hyperparameters may significantly affect both the theoretical (at least up to constant factors) and practical performance of the algorithm. Thus, I do not think it is valid to call RTCFR+ \"parameter-free\". \n\nIt is well known that algorithms that do exhibit last-iterate convergence, such as OGD, do not perform well in practice for extensive-form games. Moreover, as admitted by the authors on p.25, RTCFR+ does not consistently outperform the prior state of the art, PCFR+. In my opinion, this means that the practical contribution of the paper is not very strong. Along a similar line, it seems weird not to include the PCFR+ results in the main body, given that PCFR+ (or slight variations thereof) is the practical state of the art right now for extensive-form games. \n\nThe technical ideas of the paper mostly follow immediately from known previous ideas, namely, regret matching and reward transformation. I am also confused why the proof of Theorem 4.1 is so long. Doesn't that result follow immediately from the fact that CFR+ is no-regret?  See e.g. Lemma 1 of [1]---unless I'm missing something, Theorem 4.1 is a special case of it?", "was_revised": true, "final_justification": "As I stated in the below discussion, I think the changes proposed by the reviewers (including myself) require another round of review, and therefore I will maintain my score. That said, I do not mind if I am outvoted (as it looks like it might be the case.)\n\n----\n\nEdit 8/4: On second thought, the paper is probably interesting enough to warrant an increase in score despite these issues. Increased to 4.", "rebuttal": "We appreciate the time you dedicated to our manuscript.\n\n\n\n**W1: The paper claims that RTCFR+ is parameter-free. This is evidently false.** \n\n**A:** We apologize for the confusion. In this paper, all references to \"parameter-free\" pertain exclusively to CFR+ for solving perturbed regularized EFGs. At no point do we assert that RTCFR+ is parameter-free. For instance, at the end of Section 3 Problem Statement, we explicitly state, \"Our objective is to establish the parameter-free last-iterate convergence for CFR+ in solving Eq. (2).\" Moreover, in the limitations section at the end of the paper, we indicate that RTCFR+ requires parameter tuning.\n\nTo eliminate any ambiguity, we will add a prominent statement in the introduction and reinforce it in the Limitations section of the final version to state clearly that RTCFR+ is a non-parameter-free algorithm. This will significantly enhances the clarity of our paper.\n\n\n\n**W2: RTCFR+ does not consistently outperform the prior state of the art, PCFR+. In my opinion, this means that the practical contribution of the paper is not very strong.**\n\n**A:**\n\n- PCFR+ lacks the theoretical last-iterate convergence guarantee, whereas our RTCFR+ does offer this guarantee. As we stated in Section 1 Introduction, average-iterate convergence not only increases  computational and memory overhead, but also results approximation errors when strategies are parameterized via function approximation. Therefore, our RTCFR+ shows a promising and practical alternative to the average-iterate convergence algorithms (e.g., PCFR+) for solving large-scale games.\n\n- Compared to existing algorithms that exhibit theoretical last-iterate convergence guarantees—such as Reg-CFR, R-NaD, OMWU, and OGDA—our RTCFR+ demonstrates the fastest empirical last-iterate convergence rate. This makes RTCFR+ more suitable for solving practical applications than these algorithms.\n\n  \n\n**W3: The technical ideas of the paper primarily build on established concepts in regret matching and reward transformation.**\n\n**A:** In this paper, our focus is not on combining regret matching and reward transformation, but rather on, after integrating these two methods, whether RM-based CFR algorithms (e.g., CFR+) achieve parameter-free last-iterate convergence when solving perturbed regularized EFGs within the reward transformation framework. Specifically, as stated in lines 69–69, the central question is: “Does CFR+ have parameter-free last-iterate convergence when learning an NE of perturbed regularized EFGs?”\n\nOur primary technical contributions are proving that \"CFR+ has parameter-free last-iterate convergence in learning an NE of perturbed regularized EFGs.\" Specifically, as stated in our introduction: \"we propose novel techniques to overcome the challenges in the above two steps of the proof\" (line 83-84, beginning of the penultimate paragraph of the introduction). Specifically, our novel contributions are:\n\n- (i) We exploit the fact that an NE represents a best response to others at each infoset in perturbed EFGs to enable the smoothness of the instantaneous counterfactual regrets to be leveraged.\n- (ii) We leverage the linearity of the projection to extend our non-parameter-free convergence result to be parameter-free regime.\n\n\n\n**Q1: I am also confused why the proof of Theorem 4.1 is so long. Doesn't that result follow immediately from the fact that CFR+ is no-regret? See e.g. Lemma 1 of [1]. Could you compare your Theorem 4.1 to previously-known results (such as Lemma 1 of [1] above)?**\n\n**A:** You referenced [1], which appears to be missing from the review. Could you please provide it? We would be pleased to offer a detailed response.\n\nAdditionally, it is important to emphasize that, to the best of our knowledge, prior to the NeurIPS 2025 deadline, no study has directly established last-iterate convergence solely from the \"no-regret\" property. All existing works rely on extensive proofs to demonstrate the last-iterate convergence of no-regret algorithms.\n\n\n\n**Q2: Could you provide a rate of last-iterate convergence for Theorem 4.1?**\n\n**A:** Currently, we cannot provide a finite-time rate. To our knowledge, no existing research on RM-based CFR algorithms has established a finite-time last-iterate convergence rate. This remains an open question, which arises not only from the intrinsic complexity of RM algorithms but also from the intricacies of both EFGs and the counterfactual regret minimization framework.\n\nSecond, to the best of our knowledge, even when restricting attention solely to normal-form games—where the complexities of EFGs and the counterfactual regret minimization framework are absent—finite-time last-iterate convergence of RM algorithms has only been achieved by RS-ExRM+ and RS-SPRM+ [Cai et al., 2025]. However, RS-ExRM+ and RS-SPRM+ sacrifices the parameter-free property. In other words, even in normal-form games, no existing work establishes both finite-time last-iterate convergence and a parameter-free nature for RM algorithms, let alone in the extensive-form games we consider."}, {"review_id": "mRxzYVivI7", "reviewer": "Reviewer_L64t", "summary": "This paper introduces RTCFR⁺, a step-size parameter-free RM-based CFR+ variant for last-iterate convergence to Nash equilibria in perturbed extensive-form games (EFGs). It aims to bridge two research gaps: (1) the slow empirical convergence of theoretically sound OMD-based CFR methods (e.g., Reg-CFR), and (2) the lack of last-iterate convergence guarantees for RM-based algorithms (e.g., CFR+) in perturbed regularized EFGs. By proving CFR+ achieves step-size parameter-free last-iterate convergence in this setting and embedding it in a Reward Transformation framework, RTCFR⁺ demonstrates faster empirical convergence than existing last-iterate methods across multiple benchmarks, though without new theoretical convergence guarantees for the overall approach.", "questions": "1. In Line 136, computation via the full matrix $\\mathbf{A}$ suggests per-iteration complexity scales with histories rather than infosets or sparsification[1]. Does RTCFR⁺ leverage modern CFR optimizations (e.g., polyhedron merging for monotonic infosets) to achieve infoset-linear complexity?\n\n2. Line 152 assumes NEs satisfy γ-perturbed constraints. How are NEs computed when optimal strategies violate γ-bounds (e.g., pure strategies)?\n\n3. How is exploitability calculated under perturbation? Does it measure deviation in the original or perturbed game—particularly critical for Figures 1–3?\n\n4. Algorithm 1 (Line 8) updates reference strategies at fixed intervals. Could pathological strategy sequences at update points prevent convergence? Is there theoretical assurance?\n\n5. Why does Reg-CFR stagnate near 1e-5 exploitability in Kuhn Poker/Goofspiel (Fig 1)? Is this due to numerical precision limits, hyperparameters, or inherent properties?\n\n[1] Farina et al. Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games. AAAI 2022.", "limitations": "This paper does not provide a theoretical bound for the number of iterations T.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. Establishes the first step-size parameter-free last-iterate convergence proof for RM-based CFR in perturbed regularized EFGs.\n\n2. Comprehensive experiments across multiple EFG benchmarks show RTCFR⁺ significantly outperforms existing last-iterate convergence methods.\n\n3. Directly addresses the pertinent question: \"Does CFR+ have parameter-free last-iterate convergence in learning an NE of perturbed regularized EFGs?\"\n\n**Weaknesses**\n\n1. Overstated claims: The \"parameter-free\" assertion applies only to step sizes (η). Critical hyperparameters (γ, μ, Tᵤ) in Algorithm 1 require tuning, contradicting the broader implication of parameter insensitivity. This overshadows the legitimate contribution regarding step-size independence.\n\n2. Narrow applicability: The method operates under restrictive conditions (perturbed EFGs, RM-based local regret minimizers, last-iterate focus, step-size parameter freedom), severely limiting practical deployment scenarios.\n\n3. Unclear practical utility: No comparison to average-iterate performance of CFR+/PCFR+—the dominant practical approaches. If RTCFR⁺ under last-iterate constraints fails to surpass these methods under standard average-iterate metrics, its real-world value diminishes despite theoretical novelty. In addition, I am not quite sure whether some efficient acceleration techniques can be applied to RTCFR+ (see Question 1). If these efficient acceleration techniques are not used, the contribution of the empirical results will be greatly reduced.\n\n4. Insufficient distinction from prior work on parameter-free RM+ last-iterate convergence: The novelty of the proposed method requires clearer articulation, particularly in contrast to Cai et al. (2025) [1], which also established parameter-free last-iterate convergence for RM+ algorithms in games.\n\nLine 132: the --> there\n\nLine 141: This sentence is grammatically incorrect.\n\n[1] Cai et al. Last-iterate convergence properties of regret-matching algorithms in games. ICLR 2025", "was_revised": true, "final_justification": "I think the work design the first last iterative algorithm in EFG that performs no worse than average iterative algorithms in experiments, which I don't find in my first review. I raise my score accordingly.", "rebuttal": "Thank you for your time and for sharing your critical perspective on our manuscript.\n\n\n\n**W1: Overstated claims. The \"parameter-free\" assertion applies only to step sizes (η). Critical hyperparameters (γ, μ, Tᵤ) in Algorithm 1 require tuning.**\n\n**A:** We agree that the \"parameter-free\" property specifically refers to the CFR+ solver's independence from step-size tuning (η), not the entire RTCFR+ framework. Our core contribution, as articulated in the Introduction, is indeed the first proof of this step-size-free last-iterate convergence for CFR+ in the context of perturbed regularized EFGs. To ensure this is perfectly clear to the reader, in the final version, we will explicitly state that RTCFR+ is a non-parameter-free algorithm under the limitations section. \n\nSecondly, our algorithm reduces the cost of parameter tuning. Since $\\eta$ does not require adjustment, our algorithm is more applicable to solving real-world games compared to those algorithms that necessitate parameter tuning when solving perturbed regularized EFGs.\n\nLastly, the parameters (γ, μ, Tᵤ) are inherent to the Reward Transformation (RT) framework itself, which our algorithm is built upon. Investigating the parameter-free nature of the RT framework is outside the scope of this paper.\n\n\n\n**W2: The method operates under restrictive conditions (perturbed EFGs, RM-based local regret minimizers, last-iterate focus, step-size parameter freedom)**\n\n**A:** \n\n- Our RTCFR+ is designed to solve original EFGs, rather than perturbed EFGs; the perturbations are introduced only as part of the procedure within RTCFR+. In other words, RTCFR+ is not limited to perturbed EFGs and remains applicable to the original EFGs. \n- A key advantage of RTCFR+ is its use of RM-based local regret minimizers, which replace the OMD-based minimizers employed in prior work (Pérolat et al., 2021; Liu et al., 2023) to improve the empirical last-iterate convergence rate.\n- Last-iterate convergence and a parameter-free design are not limitations; on the contrary, they are highly desirable properties for practical applications, yielding more stable and deployment-friendly algorithms.\n\n\n**W3: No comparison to average-iterate performance of CFR+/PCFR+**\n\n**A:** We compare the last-iterate convergence performance of RTCFR+ with the average-iterate performance of CFR+, PCFR+, and DCFR (Table 1). With fine-tuning, RTCFR+ outperforms the average-iterate performance of CFR+, PCFR+, and DCFR in nearly all tested games, except for Liar's Dice (6). Even without fine-tuning, RTCFR+ achieves superior performance to the average-iterate of CFR+, PCFR+, and DCFR in 5 out of the evaluated 9 games (Kuhn Pker, Leduc Poker, Liar's Dice (4),  Liar's Dice (5), and Goofspiel (4)). In addition, as shown in Table 1, even when considering only CFR+, PCFR+, and DCFR, no single algorithm consistently outperforms the other two across all games.\n\nTable 1: Comparison between the last-iterate convergence performance of RTCFR+ with the average-iterate convergence performance of CFR+, PCFR+, and DCFR.\n\n| Game                | RTCFR$^+$ | RTCFR$^+$ (fine-tuned) | CFR$^+$  | PCFR$^+$ | DCFR     |\n| :------------------ | :-------- | :--------------------- | :------- | :------- | :------- |\n| **Kuhn Poker**      | 2.49e-15  | 6.94e-18               | 1.49e-05 | 8.56e-09 | 1.59e-05 |\n| **Leduc Poker**     | 1.97e-13  | 1.97e-13               | 7.08e-06 | 1.56e-05 | 9.72e-06 |\n| **Battleship (3)**  | 1.64e-02  | 8.60e-16               | 2.74e-04 | 1.74e-07 | 1.58e-04 |\n| **Liar's Dice (4)** | 3.19e-16  | 4.86e-17               | 4.28e-06 | 1.99e-07 | 1.90e-06 |\n| **Liar's Dice (5)** | 4.12e-07  | 5.29e-16               | 6.00e-06 | 1.10e-06 | 3.58e-06 |\n| **Liar's Dice (6)** | 6.17e-05  | 8.49e-06               | 2.47e-06 | 4.80e-05 | 2.56e-06 |\n| **Goofspiel (4)**   | 1.05e-08  | 6.77e-17               | 9.57e-06 | 2.88e-08 | 5.31e-07 |\n| **Goofspiel (5)**   | 3.38e-05  | 5.12e-16               | 4.43e-05 | 1.23e-06 | 3.70e-05 |\n| **Goofspiel (6)**   | 2.73e-05  | 1.55e-07               | 4.50e-05 | 6.23e-06 | 3.62e-05 |\n\n\n\n\n\n**W4: The novelty of the proposed method requires clearer articulation, particularly in contrast to Cai et al. (2025), which also established parameter-free last-iterate convergence for RM+ algorithms in games.**\n\n**A:** \n\n- **Problem Domain: Our work focuses on EFGs, while Cai et al. focus on normal-form games.** This is a critical difference, as the analysis for EFGs is substantially more complex due to the necessity of handling counterfactual values.  For instance, Lemma 4.3, 4.4, B.2, and B.3 in our paper pertain to counterfactual values, a theoretical aspect entirely absent in Cai et al. (2025). And these results cannot be obtained from Cai et al. (2025) directly as counterfactual values significantly increases the complexity of the analysis. In fact, as stated in Appendix A Related Work, their proof techniques related to the parameter-free last-iterate convergence for RM+ primarily follow our proof techniques\n- **Different Levels of Parameter-Free Guarantees**: The parameter-free guarantee of RM+ in Cai et al. (2025) holds only when the initial accumulated counterfactual regrets are all set to zero (see their Algorithm 1). **However, they do not investigate the parameter-free guarantee when the initial accumulated counterfactual regrets are nonzero—a case addressed by our work.** This distinction is central to RTCFR+, as noted in lines 78-79: **RTCFR+ cannot converges to an NE of the original EFG without the parameter-free guarantee for arbitrary initial accumulated counterfactual regrets!** Specifically, as indicated in lines 335-337, if the accumulated counterfactual regrets are reset to zero each time a new perturbed regularized EFG is encountered, experimental results (Figure 3) demonstrates that RTCFR+ fails to converge.\n\n\n\n**Q1: Computation via the full matrix suggests per-iteration complexity scales with histories rather than infosets or sparsification[1].**\n\n**A:** While our theoretical analysis uses matrix notation for clarity, our implementation is built upon the highly optimized LiteEFG framework [Liu et al., 2024]. The operations you mentioned are implemented within LiteEFG. Thus, we are not familiar with the specifics. Notably, the second author of LiteEFG (the advisor of LiteEFG's first author) is also the first author of [1]. Excluding the internal details of LiteEFG, our current code (Appendix F) is indeed infoset-linear.\n\n\n\n**Q2: Line 152 assumes NEs satisfy γ-perturbed constraints. How are NEs computed when optimal strategies violate γ-bounds (e.g., pure strategies)?**\n\n**A:**  Lines 152-153 discuss the NE of γ-perturbed EFGs (line 153 specifies “the set of NEs of γ-perturbed EFGs”). The definition of γ-perturbed EFGs ensures that all strategies within these EFGs adhere to γ-perturbed constraints, which naturally includes NE strategies of γ-perturbed EFGs. \n\nIn addition, note that, the perturbation is not related to the game we finally want to solve. The perturbation is only used for the internal operation of our algorithm.\n\n\n\n**Q3: How is exploitability calculated under perturbation? Does it measure deviation in the original or perturbed game—particularly critical for Figures 1–3?**\n\n**A:** In this paper, we do not calculate exploitability in perturbed EFGs. The exploitability shown in all the figures within the paper refers solely to that of the original EFGs. \n\nAgain, as we stated in Q2, the perturbation is not related to the game we finally want to solve. The perturbations only used for the internal operation of our algorithm.\n\n\n\n**Q4: Algorithm 1 (Line 8) updates reference strategies at fixed intervals. Could pathological strategy sequences at update points prevent convergence? Is there theoretical assurance?**\n\n**A:** While theory suggests updating the reference strategy only after finding an exact NE of the perturbed regularized EFG, updating at fixed intervals is a common and practical approach used in prior work [Pérolat et al., 2021].\n\nCrucially, our algorithm includes a mechanism to ensure convergence: as detailed in lines 311-322, introducing µ←µ×(1−ς) in line 8 of Algorithm 1—gradually reducing the regularization weight—has minimal impact on the empirical convergence rate of RTCFR+ (Figure 2). However, it ensures that for any fixed intervals, the sequence of NEs for the perturbed regularized EFGs converges to the set of NEs of the original EFG. Therefore, Algorithm 1 guarantees the ability to learn the NE of the original EFGs.\n\n\n\n**Q5: Why does Reg-CFR stagnate near 1e-5 exploitability in Kuhn Poker/Goofspiel (Fig 1)?**\n\n**A:** As stated in line 352, we adopt the hyperparameters from the original Reg-CFR paper. The exploitability curve presented in the original paper also exhibits this result (Fig 1, [https://arxiv.org/pdf/2206.09495v1]).\n\n\n\n**Q6: This paper does not provide a theoretical bound for the number of iterations T.**\n\n**A:**  Currently, we cannot provide a finite-time rate. To our knowledge, no existing research on RM-based CFR algorithms has established a finite-time last-iterate convergence rate. This remains an open question, which arises not only from the intrinsic complexity of RM algorithms but also from the intricacies of both EFGs and the counterfactual regret minimization framework.\n\nSecond, to the best of our knowledge, even when restricting attention solely to normal-form games—where the complexities of EFGs and the counterfactual regret minimization framework are absent—finite-time last-iterate convergence of RM algorithms has only been achieved by RS-ExRM+ and RS-SPRM+ [Cai et al., 2025]. However, RS-ExRM+ and RS-SPRM+ sacrifices the parameter-free property. In other words, even in normal-form games, no existing work establishes both finite-time last-iterate convergence and a parameter-free nature for RM algorithms, let alone in the extensive-form games we consider."}]

Author rebuttal:

Meta-review: This paper shows that the classical parameter-free RM-based CFR algorithm achieves last-iterate convergence in learning an NE of perturbed regularized EFGs, while previous studies were only able to show convergence for OMD-based algorithms. Given the practical advantage of the RM algorithm and the lack of good theoretical understanding of this simple algorithm, I believe that the results are significant enough and likely to inspire more future studies. Therefore, despite that this is an asymptotic result and that it does not eventually lead to a parameter-free algorithm for solving the original EFGs, I still support acceptance. All reviewers (including mv8m) have converged to supporting acceptance as well, with the expectation that the authors will revise the paper as promised to remove the overstatement on the "parameter-free" property and incorporate additional empirical results.
Decision: Accept (poster)