- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper gave a general framework for the anchoring algorithms in extensive-form games, and showed a last-iterate linear convergence rate to the Nash equilibrium.
Critical strengths
- The algorithm achieves linear convergence to the NE.
- The algorithm generalizes different anchoring algorithms in EFGs.
Critical weaknesses
The algorithm depends on a coefficient , which can be arbitrarily small. Hence, the convergence rate in the paper can be arbitrarily bad. This dependence also appears in previous papers that achieve linear convergence, such as [1][2]. A discussion about the relationship between these slope constants would be good.
[1] Wei, Chen-Yu, et al. "Linear last-iterate convergence in constrained saddle-point optimization." arXiv preprint arXiv:2006.09517 (2020).
[2] Liu, Mingyang, et al. "The power of regularization in solving extensive-form games." arXiv preprint arXiv:2206.09495 (2022).
Questions for authors
Could you please add these baseline algorithms? I would like to see if this anchoring framework performs better than previous algorithms.
- PCFR+
- Regularized algorithms such as regularized optimistic mirror descent
4 comments
Questions
Could you please add these baseline algorithms? I would like to see if this anchoring framework performs better than previous algorithms.
Thank you for this helpful request. We evaluated both baselines across all four games and added the results to Table 2 of the revision. All entries use the paper's metric: the saddle gap of the last iterate, with the first iteration falling below shown in parentheses (a dash means it is not reached within the horizon).
| Method | Kuhn | Leduc | Liar's Dice (4-sided) | Liar's Dice (5-sided) |
|---|---|---|---|---|
| moving center, (ours) | (5200) | (–) | (4600) | (8000) |
| re-center | (6400) | (–) | (3600) | (6400) |
| CFR+ | (–) | (–) | (200) | (100) |
| RTCFR+ | (400) | (6000) | (200) | (300) |
| Adp-RTCFR+ | (400) | (6000) | (200) | (100) |
| PCFR+ (new) | (400) | (22400) | (200) | (100) |
| Reg-DOMD, annealed (new) | (38800) | (–) | (–) | (–) |
PCFR+. Its last iterate reaches the floating-point floor on all four games. It falls below at the same iteration as the RTCFR+ family on Kuhn and both Liar's Dice games, and later on Leduc ( vs ). Note that RTCFR+ moves its reference by periodic hard resets ( in our family), in its native geometry; on 5-sided Liar's Dice, RTCFR+ itself enters at and Adp-RTCFR+ at . Moreover, the averaged strategies of PCFR+ reach this threshold no earlier ( with linear averaging, and with quadratic averaging).
Regularized optimistic mirror descent (Reg-DOMD, Liu et al.). With a fixed , this method converges to the regularized equilibrium, and the gap remains at across the four games. To ensure a strong baseline, we annealed (halving it every iterations) and tuned over configurations of and step size. It reaches only on Kuhn (earliest at iteration , compared to for the moving center). On the other three games, its best final gaps are (Leduc), (4-sided Liar's Dice), and (5-sided), compared to , , and for the moving center. The moving center achieves these gaps using one constant and requires no annealing schedule to tune.
Protocol. All methods are deterministic, eliminating seed variance. The moving center uses one setting, , across all four games without per-game tuning. RTCFR+ uses its published hyperparameters, PCFR+ has no tunable parameters, and only Reg-DOMD is tuned per game.
Summary of the comparison. RTCFR+ and Adp-RTCFR+, which update their reference via hard resets, reach on Leduc earlier than PCFR+, while Adp-RTCFR+ ties PCFR+ on the other three games. The Euclidean moving center (the variant covered by our theorems) reaches earlier than tuned Reg-DOMD on Kuhn and attains smaller gaps on the other three games, whereas PCFR+ converges earlier than it, as the revised Table 2 shows side by side. Within the Euclidean family, the moving center uses a single speed. Against the four re-centering periods, it ranks first on Kuhn and second on the other three games, whereas the period finishes above it on Leduc (these findings are now listed explicitly in Section 8). The paper's main contribution is the rate theory for this family, and these baselines place it in context.
Thank you again for your time and feedback. We hope the added discussion of the constants and the results for the two baselines address your concerns. We are happy to run further comparisons if needed.
Thank you for your response! I will keep my score.
We sincerely thank the reviewer for your careful reading and positive evaluation of our paper and response.
We thank the reviewer for the careful reading and for two concrete requests, both of which improved the paper.
Weaknesses
Thank you for this valuable suggestion. We have added the requested discussion to the revision (Section 4, "Relation to earlier constants", and Appendix I). In short, the constant you refer to and our γ are the same quantity.
(1) Wei et al. [1]. For bilinear games on polytopes, their SP-MS condition (Definition 1, exponent 0) is exactly dist(z,Z⋆)≤C1dist(0,F(z)+NZ(z)), which is metric subregularity with modulus γ=1/C. Consequently, an arbitrarily small C corresponds to an arbitrarily large γ in our notation (Lemma 4.3). The identity follows directly: for a polytope Z, the supremum in SP-MS equals the norm of the projection of −F(z) onto the tangent cone of Z at z. Because the tangent and normal cones are polar to each other, this equals dist(0,F(z)+NZ(z)).
Both rates then degrade in the same way. In Theorem 8 of Wei et al., the contraction is governed by C5∝η2C2=η2/γ2, while in our Lemma 4.3 it is governed by 1−ρJ≈1/(2γ2τ2) for large γ. The γ−2 dependence is a property of the game's geometry shared by exact linear-rate results; it is not specific to the moving center.
(2) Liu et al. [2]. Although the linear rate (1−ητ)t of Reg-DOMD (their Theorem 4.1) does not involve γ, it describes convergence toward the regularized equilibrium, which lies at a distance of O(τ) from the Nash set. Reaching an exact equilibrium requires annealing τ, at which point the guarantee becomes sublinear (their Theorem 4.2).
Therefore, the two results sit at different points along a single trade-off: a γ-free rate to a biased point, or a γ-dependent rate to an exact equilibrium without annealing.
(3) Is the rate still informative when γ is large? We conducted a new experiment on a family of games where γ is known in closed form, γ=2/ε (new Table 6, Appendix I). As γ increases by 30×, the rate decreases by 907×, and our prediction matches the measured rate to within 0.12% with no fitted constant:
(Rates are per iteration, at η=0.2, τ=0.5, β=0.05; the prediction is the exact slow eigenvalue of the mode system of Section 6.) Thus, the slowdown for large γ reflects the true behavior of the dynamics tracked by our theory, rather than looseness in the bound.