Efficient Last-Iterate Convergence in Solving Extensive-Form Games

Thank you for your time and for sharing your critical perspective on our manuscript.

W1: Overstated claims. The "parameter-free" assertion applies only to step sizes (η). Critical hyperparameters (γ, μ, Tᵤ) in Algorithm 1 require tuning.

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.

Secondly, 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.

Lastly, 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.

W2: The method operates under restrictive conditions (perturbed EFGs, RM-based local regret minimizers, last-iterate focus, step-size parameter freedom)

A:

• 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.
• 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.
• 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.

W3: No comparison to average-iterate performance of CFR+/PCFR+

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.

Table 1: Comparison between the last-iterate convergence performance of RTCFR+ with the average-iterate convergence performance of CFR+, PCFR+, and DCFR.

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.

A:

• 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
• 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.

Q1: Computation via the full matrix suggests per-iteration complexity scales with histories rather than infosets or sparsification[1].

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.

Q2: Line 152 assumes NEs satisfy γ-perturbed constraints. How are NEs computed when optimal strategies violate γ-bounds (e.g., pure strategies)?

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.

In 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.

Q3: How is exploitability calculated under perturbation? Does it measure deviation in the original or perturbed game—particularly critical for Figures 1–3?

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.

Again, 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.

Q4: Algorithm 1 (Line 8) updates reference strategies at fixed intervals. Could pathological strategy sequences at update points prevent convergence? Is there theoretical assurance?

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].

Crucially, 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.

Q5: Why does Reg-CFR stagnate near 1e-5 exploitability in Kuhn Poker/Goofspiel (Fig 1)?

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]).

Q6: This paper does not provide a theoretical bound for the number of iterations T.

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.

Second, 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.

I think the author should emphasize a core contribution of the work: designing the first last-iterative algorithm in EFG that performs no worse than average-iterative algorithms in experiments. May I ask if this is a core contribution? If so, I think this work is worth accepting.

As the author also acknowledges that RTCFR+ is not a parameter-free algorithm, I believe the title of the article is inappropriate. I think the title should highlight the last-iterate with strong experimental performance. I'm not sure if the title can be modified, but I suggest changing the title of this work.

Therefore, even if we only consider the experimental part and not the theoretical proof part, I believe this article is still worth accepting. Therefore, I have revised my score to 4. I think this article can receive a higher score if the author can do the following in rebuttal phase:

1. Apply the RTCFR+method to larger scale games and attempt to combine it with techniques such as depth-limited solving [1,2], impact-recall abstraction [3], action abstraction [4], warm-start[5], sparsification [6], pruning [7], etc. If possible, I would like the author to write a separate section discussing the application prospects of RTCFR+in large-scale games and its combination with these common technologies.

2. Attempt to apply the RTCFR+ method to multiplayer games, as the convergence of the last-iterate method in multiplayer games is worth studying [8].

[1] Brown et al. Depth-Limited Solving for Imperfect-Information Games. NIPS 2018

[2] Brown et al. Combining Deep Reinforcement Learning and Search for Imperfect-Information Games. NIPS 2020

[3] Ganzfried et al. Potential-Aware Imperfect-Recall Abstraction with Earth Mover’s Distance in Imperfect-Information Games. AAAI 2014

[4] Li et al. RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning. ICML 2024

[5] Brown el al. Strategy-Based Warm Starting for Regret Minimization in Games. AAAI 2016

[6] Farina et al. Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games. AAAI 2022

[7] Li et al. Efficient Online Pruning and Abstraction for Imperfect Information Extensive-Form Games. ICLR 2025

[8] Lu et al. Divergence-Regularized Discounted Aggregation: Equilibrium Finding in Multiplayer Partially Observable Stochastic Games. ICLR 2025

We appreciate your feedback and suggestions.

Q1: I think the author should emphasize a core contribution of the work: designing the first last-iterative algorithm in EFG that performs no worse than average-iterative algorithms in experiments. May I ask if this is a core contribution? If so, I think this work is worth accepting.

A: Thank you for your suggestion. This is one of the core contribution of our work. As far as we know, our RTCFR+ is the first last-iterate convergence algorithm in EFG that demonstrates performance no worse than average-iterate algorithms in experiments. We will emphasize this point further in the final version.

Q2: As the author also acknowledges that RTCFR+ is not a parameter-free algorithm, I believe the title of the article is inappropriate. I think the title should highlight the last-iterate with strong experimental performance. I'm not sure if the title can be modified, but I suggest changing the title of this work.

A: We acknowledge that the current title is not quite appropriate. In the final version, we will revise the title to "Efficient Last-Iterate Convergence in Solving Extensive-Form Games."

Q3.1: Apply the RTCFR+method to larger-scale games and attempt to combine it with techniques such as depth-limited solving [1,2], impact-recall abstraction [3], action abstraction [4], warm-start[5], sparsification [6], pruning [7], etc.

We attempt to utilize RTCFR+ to address larger-scale games, such as heads-up no-limit Texas Hold’em (HUNL) Subgames, specifically those open-sourced by Libratus [Brown and Sandholm, 2018]. For the aforementioned methods, we note that there is no available open-source code. As a result, we opted for another method with an existing open-source implementation suitable for larger-scale games—Vector CFR [9]: "on the way from the root to the leaves, we will pass forwards two vectors: one containing the probabilities of us and one containing the probabilities of the opponent reaching the current game state, for each player’s $n$ possible private chance outcomes." Theoretically, Vector CFR achieves an $n$-fold speedup, where $n$ denotes the number of chance outcomes (1326 in HUNL as chance outcomes is the possible private hands in HUNL).

We employ the open-source code from Poker RL [Eric Steinberger, 2019; Xu et al., 2024b], which supports Vector CFR and Subgames from Libratus, specifically Subgame 3 and Subgame 4. These Subgames have Histories numbering $4.0 \times 10^8$ and $2.4 \times 10^8$, respectively. These are $400$ and $240$ times greater than the largest game tested in this paper (Goofspiel (6), as shown in Table 1 of our paper). The experimental results after 5,000 iterations are (we present the last-iterate convergence performance for RTCFR+):

RTCFR+ surpasses the last-iterate convergence performance of CFR+ and PCFR+ in all two HUNL Subgames. Furthermore, in Subgame3, RTCFR+ also outperforms the average-iterate convergence performance of CFR+ and PCFR+. Notably, CFR+ and PCFR+ do not exhibit last-iterate convergence guarantee.

In fact, without the acceleration provided by Vector CFR, it would be infeasible to conduct experiments on HUNL Subgames. For instance, in our current work, the largest game evaluated—Goofspiel (6)—requires approximately 76 minutes to complete 5,000 iterations of RTCFR+. In contrast, HUNL Subgames are several hundred times larger than this benchmark; yet, with Vector CFR, we are able to finish 5,000 iterations of RTCFR+ within just 21 minutes.

Additional References:

[9] Johanson, Michael, Nolan Bard, Marc Lanctot, Richard G. Gibson, and Michael Bowling. "Efficient Nash equilibrium approximation through Monte Carlo counterfactual regret minimization." In Aamas, pp. 837-846. 2012.

Q3.2: Discuss the application prospects of RTCFR+ in large-scale games and its combination with these common technologies

Firstly, RTCFR+ 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 implementation 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 F). The main limitation of applying RTCFR+ to large-scale games lies in the need to tune the hyperparameters $\mu$, $\gamma$, and $T_u$, which can vary significantly across different games. Addressing the dependency on tuning $\mu$, $\gamma$, and $T_u$ remains a 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.

Secondly, integrating RTCFR+ with the mentioned approaches requires case-by-case analysis.

• For algorithms that solely modify the game tree, such as depth-limited solving [1,2], impact-recall abstraction [3], action abstraction [4], and Vector CFR [9], RTCFR+ can be directly applied since RTCFR+ only requires execution on the new game tree. This process is straightforward and presents no significant challenges.
• Regarding the warm-start approach [5], while its concept of setting initial accumulated counterfactual regrets using an efficient initial strategy is insightful, current integration with RTCFR+ is not feasible. Specifically, [5] is an enhancement tailored for the original CFR. Formally, the analysis presented on the bottom left of page four in [5] demonstrates that the substitute regret is given by $R^{\prime T}(I,a) = T(v^{\prime \sigma}(I,a) - v^{\prime \sigma}(I))$. This formulation implies that $R^{\prime T}(I,a)$ can be negative, a property that does not hold in CFR$^+$ and RTCFR$^+$.
• As for sparsification [6], which optimizes the computation of loss gradients ($\ell^t_i$, 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).
• The pruning approach in [7] can be directly integrated with RTCFR+. 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-tree modification approaches. Hence, RTCFR+ can be directly applied.

As previously discussed in Q3.1, since none of the approaches in [1–8] provide open-source code, we adopt Vector CFR [9] to extend our RTCFR+ method for solving larger-scale games as Poker RL provide the open-source code of Vector CFR. In addition, as mentioned earlier, Vector CFR offers significant acceleration, which is crucial for scaling RTCFR+ to larger-scale games.

We also attempt to implement the algorithms you mentioned, but we cannot make it successful.

Thanks to the author for the detailed explanation and supplementary experiments. The HUNL subgame experiment is excellent. The convergence curve can be displayed in the revision, and the DCFR algorithm can be added. Vector CFR utilises the properties of HUNL-type games, where players' hands do not change, so each information set can be parallelised or vectorised in each iteration. I would like to know whether the HUNL experiment in the author's implementation ran for 500 iterations or 5000 iterations? From the results, it seems to be 500 iterations.

Thank you to the author for the detailed discussion of various optimisation methods in IIG and the exploration of multi-player games. And I have another question: since RTCFR+ solves problems under a perturbed EFG, does this mean that RTCFR+ can handle situations where opponents choose off-tree actions or low-probability actions better than other CFR algorithms? Traditional CFR algorithms do not perform well when handling opponents' low-probability actions[11].

[11] Gabriele Farina, Christian Kroer, Tuomas Sandholm. Regret minimization in behaviorally-constrained zero-sum games. ICML 2017

We appreciate the time you dedicated to our manuscript.

W1: The paper claims that RTCFR+ is parameter-free. This is evidently false.

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.

To 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.

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.

A:

• 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.

• 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.

W3: The technical ideas of the paper primarily build on established concepts in regret matching and reward transformation.

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?”

Our 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:

• (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.
• (ii) We leverage the linearity of the projection to extend our non-parameter-free convergence result to be parameter-free regime.

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)?

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.

Additionally, 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.

Q2: Could you provide a rate of last-iterate convergence for Theorem 4.1?

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.

Second, 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.

Thank you for your positive feedback and insightful suggestions for improvement.

Q1：It nontrivial to grasp how the objective is captured by the Nash equilibrium formulation in equation (1).

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).

Q2: I was also left without a clear picture of the overall problem or the specific objective functions being optimized.

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.

Q3: A simple running toy example, would significantly improve accessibility and comprehension.

A: We will include a toy extensive-form game, which will significantly enhance the clarity of our paper.

Q4: It would be helpful to elaborate on how the perturbation and regularization may affect the game’s payoffs.

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:

• Perturbation does not affect the game's payoffs but instead modifies the strategy space to ensure the smoothness of counterfactual values.
• In contrast, regularization means an additional regularization term is added to the game's payoffs, thereby imparting strong monotonicity.

This smoothness and strong monotonicity reduce the difficulty of proving last-iterate convergence. Specifically:

• Smoothness of counterfactual values allows us to establish a relationship between the gap in counterfactual values and the gap between strategies (line 126).
• Strong monotonicity guarantees the uniqueness of solutions. Precisely, strong monotonicity ensures that the NE of the perturbed regularized EFG is unique.

Lastly, 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.

Q5: More practical guidance on selecting the parameters and would be valuable.

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.

• 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$.
• 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.
• 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.

Based on these analyses, we advocate for the prioritization of determining $\mu$’s value, followed by the value of $T_u$ , when practically applying RTCFR+.

Q6: It would strengthen the empirical results to include an evaluation of the method’s scalability to larger, imperfect-information games.

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.

Q6: It would strengthen the empirical results to include an evaluation of the method’s scalability to larger, imperfect-information games.

A: We have conducted experiments on larger-scale games. We utilize RTCFR+ to address larger-scale games, such as heads-up no-limit Texas Hold’em (HUNL) Subgames, specifically those open-sourced by Libratus [Brown and Sandholm, 2018]. We employ the open-source code from Poker RL [Eric Steinberger, 2019; Xu et al., 2024b], which supports Subgames from Libratus, specifically Subgame 3 and Subgame 4. These Subgames have Histories numbering $4.0 \times 10^8$ and $2.4 \times 10^8$, respectively. These are $400$ and $240$ times greater than the largest game tested in this paper (Goofspiel (6), as shown in Table 1 of our paper). We compare with CFR+ and PCFR+ since Poker RL does not support Reg-CFR, R-NaD, OMWU, and OGDA. The experimental results after 5000 iterations demonstrate that RTCFR+ surpasses the last-iterate convergence performance of CFR+ and PCFR+ in all two HUNL Subgames.

Thank you for your thoughtful comments and the positive evaluation

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.

A:

• 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.
• 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.

Q1: Does RTCFR+ outperforms also the convergence rates of time-average algorithms

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.

Table 1: Comparison between the last-iterate convergence performance of RTCFR+ with the average-iterate convergence performance of CFR+, PCFR+, and DCFR.

Q2: Is there a reason for using Nash Equilibrium instead of min-max equilibrium

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.”

Additional References:

[1] Maschler, Michael, Shmuel Zamir, and Eilon Solan. Game theory. Cambridge University Press, 2020.