acceptodds
Under review as a conference paper at ICLR 2027

Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games

Abstract

We prove that the last iterate of Optimistic Follow-The-Regularized-Leader (OFTRL) converges at a linear rate to a Nash equilibrium in multiplayer harmonic games. Our result holds under a mild game-regularity condition and for a large family of regularizers, including entropy, Tsallis, and log-barrier. Our analysis is based on a dual perspective of OFTRL: we prove that the interaction between optimism and the global structure of harmonic games leads to the dissipation of an energy function along the dual iterates, for which we establish tight quantitative bounds. Our result also holds for the Extragradient FTRL variant.

Primary area:
learning theory
Keywords:
learning in games, harmonic games, last-iterate convergence rates, optimistic FTRL

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_E8ZbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors claim to prove a linear last-iterate convergence rate for optimistic and extragradient FTRL in multiplayer harmonic games, a class beyond two-player zero-sum games that includes games with nonlinear, non-monotone operators and multiple equilibria. The rate is proved for a family of regularizers including entropy, Tsallis and log-barrier, under a regularity condition the authors call mild, and the reached equilibrium is identified as the Minty-equality equilibrium closest to the initialization in a weighted Bregman divergence.

Critical strengths

The proofs look correct. The linear last-iterate convergence rate for optimistic and extragradient FTRL in harmonic games with linear operators seems novel.

Critical weaknesses

The paper presents its result for harmonic games under a regularity condition it calls mild. However, Assumption 5 requires the Jacobian of the stationarity map to be nonsingular at the reachable equilibrium, which is not true of general harmonic games (see the argument below). Therefore, the result as proven applies to a strict subset of harmonic games, and calling the condition mild misrepresents its scope.

The result does hold for harmonic games with linear operators, for which the authors prove that Assumption 5 holds (Proposition E.6). Even there the novelty is limited. Last-iterate convergence to the set of equilibria was already known for these games [1], so what is new is the rate and the characterization of the limit point. The rate itself is a modest generalization of [2], which already gives one for two-player zero-sum games with a unique interior equilibrium. What the paper adds to [2] is the multiplayer case, multiple equilibria, the extragradient variant and other regularizers.

Argument. The reachable equilibrium satisfies the Minty equality (Corollary E.5). Differentiating it twice there makes the weighted Jacobian of the operator skew-symmetric on the tangent space, so the Jacobian in Assumption 5 is similar to a skew-symmetric matrix and singular whenever the effective dual space has odd dimension. Harmonic games with an odd-dimensional effective dual space therefore violate Assumption 5 at every reachable equilibrium.

[1] Legacci et al. No-regret learning in harmonic games: Extrapolation in the face of conflicting interests. NeurIPS, 2024.

[2] Lazarsfeld et al. When and why is optimistic multiplicative weights slow? The geometry of energy dissipation. arXiv:2605.13242, 2026.

Questions for authors
  1. Can you characterize the broader class of nonlinear harmonic games for which Assumption 5 holds?
6 comments
AuthorsOpenReview ↗

Rebuttal part 1/3

We thank the reviewer for their feedback.

Reply to Q1

  1. Can you characterize the broader class of nonlinear harmonic games for which Assumption 5 holds?

The verification of Assumption 5 in our paper is not limited to linear polymatrix games. Specifically, in Appendix B.4.2 we explicitly verify the condition for a nonlinear harmonic family whose Nash equilibrium set is nonconvex. We note that there exist other parameterized families of nonlinear harmonic games that also satisfy the condition. We will make these nonlinear examples more prominent.

As described in Remark 3.5, one key consequence of Assumption 5 is that it supplies a local linear error bound around reachable Nash equilibria. The use of local error bound assumptions and related regularity conditions to establish quantitative convergence rates has substantial precedent in the literature on learning in games and variational inequalities (see, e.g., [Azizian+2024, Assumption 2], [Wei+2021, Definition 1 and Theorem 8], and [Giannou+2022, Proposition 1]). In our proof, Proposition 5.6 converts the local error bound into an operator domination inequality that is uniform over compact reachable sets. Combining this inequality with the energy dissipation bounds yields the linear last iterate rate.

The energy dissipation bounds we prove in Lemma 5.4 do not require Assumption 5. Assumption 5 is important for establishing linear convergence rates. However, under weaker structural conditions, such as local Hölder error bounds around reachable Nash equilibria, the same dissipation framework can yield slower polynomial last-iterate convergence guarantees.

AuthorsOpenReview ↗

Rebuttal part 2/3

Novelty and technical contributions

The rate itself is a modest generalization of [2], which already gives one for two-player zero-sum games with a unique interior equilibrium. What the paper adds to [2] is the multiplayer case, multiple equilibria, the extragradient variant and other regularizers.

Quantitative last-iterate convergence rates for optimistic FTRL in harmonic games were explicitly left open by [Legacci+24a, Section 5], who conjectured linear convergence and noted that establishing it would likely require different techniques. Our work establishes such rates with the following scope and technical contributions:

  • Harmonic game operators. The analysis of [Lazarsfeld+26] exploits the linear skew-symmetric operator representation of two-player zero-sum games to analyze OMWU. In contrast, our guarantees hold for both OFTRL and EGFTRL for the broader class of multiplayer harmonic games under the stated regularizer, stepsize conditions and the nondegeneracy condition in Assumption 5 (which holds automatically in the subclass of linear operators; see Proposition E.6). However, in general, harmonic games induce nonlinear operators (see Appendix B.4 for examples), and thus our analysis cannot rely on the linear skew-symmetric structure of zero-sum game operators. Instead, our analysis exploits the underlying weighted Minty equality structure (expression 6) that corresponds to the harmonic property. We also explicitly verify Assumption 5 for a nonlinear harmonic family with a nonconvex Nash equilibrium set in Appendix B.4.2.

  • Unified proof for both algorithms with more general regularizers. [Lazarsfeld+26] analyzes OMWU as an optimistic correction to a forward discretization of a skew-gradient flow, while [Wei+21] analyzes OMWU through a primal potential function. We first introduce symmetrized primal-dual coordinates that convert the weighted Minty equality into an unweighted identity (Proposition 5.1) while preserving the OFTRL/EGFTRL update structure and the conjugate relationship between the transformed regularizer and energy (Proposition 5.2). Under this change of basis, our proof then starts from the backward Euler discretization of the energy-conserving FTRL flow: implicit FTRL (IFTRL), whose updates dissipate energy. We show how both OFTRL and EGFTRL approximate this implicit scheme. The key technical step is to control their coupling errors in the local geometry induced by the energy Hessian, and to show that these errors remain dominated by the implicit dissipation (Proposition 5.5, Appendix H). This yields a common quantitative explanation of last-iterate convergence for both algorithms for a general class of regularizers, including entropy, Tsallis, and log-barrier regularization, potentially differing across players. The resulting two-sided dissipation bounds match up to absolute constants and do not require Assumption 5 (Lemma 5.4), separating the mechanism producing dissipation from the additional regularity used to obtain a linear rate. We also establish a contrasting quantitative divergence result for vanilla FTRL in linear harmonic games (Theorem 4.5).

  • Multiple equilibria, identification of the limit, and equilibrium selection. Unlike the unique interior equilibrium setting of [Lazarsfeld+26], harmonic games can have a continuum of Nash equilibria (Appendix B.4.1) and more generally nonconvex Nash equilibrium sets (Appendix B.4.2). The latter cannot occur in two-player zero-sum games. This multiplicity creates a technical challenge: an operator-domination inequality relative to one fixed equilibrium fails at any other interior equilibrium because the stationarity residual vanishes, but the Bregman divergence from the reference equilibrium remains positive. Our analysis overcomes this obstruction by exploiting the set reachable from initialization: under Assumption 5, we identify a unique equilibrium within this set and establish operator domination on its compact subsets, even though the game may have many equilibria elsewhere. More precisely, we prove that there is at most one reachable Minty equality point (Proposition E.2) and that, under Assumption 5, every reachable Nash equilibrium is such a point (Proposition E.4, Corollary E.5). These arguments identify the selected limit as the weighted Bregman projection of initialization onto the Minty-equality set (Lemma I.1). We then convert the local error bound into an operator domination inequality that holds uniformly over compact reachable sets (Proposition 5.6, Appendix J). This establishes both the equilibrium selected by the dynamics and a global linear rate to that equilibrium, without assuming global uniqueness of a Nash equilibrium.

AuthorsOpenReview ↗

Rebuttal part 3/3

Additional references mentioned:

[Azizian+2024]: “The rate of convergence of bregman proximal methods: Local geometry versus regularity versus sharpness.”, SIAM Journal on Optimization, 2024.

[Wei+2021]: “Linear last-iterate convergence in constrained saddle-point optimization.”, ICLR 2021

[Giannou+2022]: “On the convergence of policy gradient methods to Nash equilibria in general stochastic games.” NeurIPS 2022

Reviewer_5cXXOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proved the linear last-iterate convergence rates for optimistic FTRL (OFTRL) in harmonic games. The authors claim that they use a dual and variational perspective of OFTRL. The authors also state that the last-iterate convergence rates also hold for extragradient FTRL.

The results are not surprising. The last-iterate convergence rates of optimistic variants is well-known in existing literature. This paper seems to just extend the well-known result to harmonic games, which is somehow incremental.

Critical strengths

The critical strength of this paper is mainly the problem setting is clear. The authors provide some intuitions in the main body, even though the intuition is not easy to follow.

Critical weaknesses

The main weakness of this paper is that Theorem 4.1 imposes the restrictive upper bound 1/(880LBωκM)1/(880LB\omega\kappa_M) on the stepsize: besides the unusually large constant 880880, four quantities LL, BB, ω\omega, and κM\kappa_M all enter the denominator. As a result, the stepsize may become so small that the algorithm would be difficult to use in realistic large-scale multi-agent problems. The reviewer believes that this restriction is an artifact of the analysis. Besides, the practical motivation of harmonic games in machine learning applications (e.g., GANs training) is not convincing compared with zero-sum games. Also note that the convergence analysis heavily depends on Assumption 5. Even though the authors have verified this assumption on linear polymatrix games, it is still not clear how to verify it for general nonlinear harmonic games. This significantly limits the applicability of the results in real-world problems.

Considering the above weaknesses, I am inclined to reject this paper. If I have essential misundersanding of this paper, I am willing to change my mind.

Questions for authors

Please reply to the above critical weaknesses.

7 comments
AuthorsOpenReview ↗

Rebuttal part 1/3

We thank the reviewer for their feedback.

Novelty and technical contributions

Quantitative last-iterate convergence rates for optimistic FTRL in harmonic games were explicitly left open by [Legacci+24a, Section 5], who conjectured linear convergence and noted that establishing it would likely require different techniques. Our work establishes such rates with the following scope and technical contributions:

  • Harmonic game operators. The analysis of [Lazarsfeld+26] exploits the linear skew-symmetric operator representation of two-player zero-sum games to analyze OMWU. In contrast, our guarantees hold for both OFTRL and EGFTRL for the broader class of multiplayer harmonic games under the stated regularizer, stepsize conditions and the nondegeneracy condition in Assumption 5 (which holds automatically in the subclass of linear operators; see Proposition E.6). However, in general, harmonic games induce nonlinear operators (see Appendix B.4 for examples), and thus our analysis cannot rely on the linear skew-symmetric structure of zero-sum game operators. Instead, our analysis exploits the underlying weighted Minty equality structure (expression 6) that corresponds to the harmonic property. We also explicitly verify Assumption 5 for a nonlinear harmonic family with a nonconvex Nash equilibrium set in Appendix B.4.2.

  • Unified proof for both algorithms with more general regularizers. [Lazarsfeld+26] analyzes OMWU as an optimistic correction to a forward discretization of a skew-gradient flow, while [Wei+21] analyzes OMWU through a primal potential function. We first introduce symmetrized primal-dual coordinates that convert the weighted Minty equality into an unweighted identity (Proposition 5.1) while preserving the OFTRL/EGFTRL update structure and the conjugate relationship between the transformed regularizer and energy (Proposition 5.2). Under this change of basis, our proof then starts from the backward Euler discretization of the energy-conserving FTRL flow: implicit FTRL (IFTRL), whose updates dissipate energy. We show how both OFTRL and EGFTRL approximate this implicit scheme. The key technical step is to control their coupling errors in the local geometry induced by the energy Hessian, and to show that these errors remain dominated by the implicit dissipation (Proposition 5.5, Appendix H). This yields a common quantitative explanation of last-iterate convergence for both algorithms for a general class of regularizers, including entropy, Tsallis, and log-barrier regularization, potentially differing across players. The resulting two-sided dissipation bounds match up to absolute constants and do not require Assumption 5 (Lemma 5.4), separating the mechanism producing dissipation from the additional regularity used to obtain a linear rate. We also establish a contrasting quantitative divergence result for vanilla FTRL in linear harmonic games (Theorem 4.5).

  • Multiple equilibria, identification of the limit, and equilibrium selection. Unlike the unique interior equilibrium setting of [Lazarsfeld+26], harmonic games can have a continuum of Nash equilibria (Appendix B.4.1) and more generally nonconvex Nash equilibrium sets (Appendix B.4.2). The latter cannot occur in two-player zero-sum games. This multiplicity creates a technical challenge: an operator-domination inequality relative to one fixed equilibrium fails at any other interior equilibrium because the stationarity residual vanishes, but the Bregman divergence from the reference equilibrium remains positive. Our analysis overcomes this obstruction by exploiting the set reachable from initialization: under Assumption 5, we identify a unique equilibrium within this set and establish operator domination on its compact subsets, even though the game may have many equilibria elsewhere. More precisely, we prove that there is at most one reachable Minty equality point (Proposition E.2) and that, under Assumption 5, every reachable Nash equilibrium is such a point (Proposition E.4, Corollary E.5). These arguments identify the selected limit as the weighted Bregman projection of initialization onto the Minty-equality set (Lemma I.1). We then convert the local error bound into an operator domination inequality that holds uniformly over compact reachable sets (Proposition 5.6, Appendix J). This establishes both the equilibrium selected by the dynamics and a global linear rate to that equilibrium, without assuming global uniqueness of a Nash equilibrium.

AuthorsOpenReview ↗

Rebuttal part 2/3

Constants in stepsize condition

The main weakness of this paper is that Theorem 4.1 imposes the restrictive upper bound 1/(880LBωκM)1/(880LB\omega \kappa_M) on the stepsize.

Our guarantee holds with a constant stepsize. The absolute constant 880 was not optimized, as stated in Remark H.2: it results from sufficient conditions ensuring that the coupling errors remain dominated by the dissipative term in Lemma 5.4. We therefore view this as a conservative sufficient bound, rather than a characterization of the largest stepsize permitting convergence. The parameters have different analytical roles. The Lipschitz constant LL controls the variation of the game operator, and the boundedness constant BB controls the size of dual increments (and note that continuous operators are automatically bounded on compact sets). Inverse dependence in the stepsize bound on these constants is a standard condition appearing in prior convergence analyses in the literature on learning in games (see, for example, [Cai+22, Def. 1 and Thm.1], [Legacci+24a, expression (3) and Theorems 3, 4], and [Wei+21, Lemma 1]). The constant ω\omega captures the local stability of the energy function Hessian (see Assumption 4), and when players run Optimistic MWU using entropic regularization, then ω=2\omega = 2 (see Appendix C.3). Finally, κM\kappa_M measures the imbalance of the harmonic weights and equals 11 when those weights are equal. Dependence on harmonic weights also appears in the asymptotic convergence guarantee of [Legacci+24a, Theorem 4]. We will clarify the distinction between these parameter dependencies and the unoptimized numerical constant. As briefly mentioned in the conclusion of Section 6, extending our quantitative analysis to adaptive stepsizes is an interesting open question.

Motivation of our work

The main motivation for our work is theoretical: to understand which structural properties of multiplayer games allow FTRL-type learning algorithms to converge in last-iterate to a Nash equilibrium. Harmonic games are a canonical component of the decomposition of any finite game into potential and harmonic parts, making them a fundamental setting for studying learning under conflicting interests. They include two-player zero-sum games with an interior equilibrium, but in general they have nonconstant-sum payoffs, have nonlinear and nonmonotone operators, and have nonconvex equilibrium sets (see, e.g., Appendix B.4). In recent years, there has been a growing body of work studying algorithms for learning in this fundamental class of harmonic games (see, e.g., [Legacci+24b], [Zhang+26], [Anagnostides+25], [Legacci+26], as discussed in Appendix A). Our paper advances this line of research by quantifying how quickly optimistic FTRL variants converge in last-iterate and by identifying the mechanism producing this convergence, answering an open question formulated in [Legacci+24a].

Non-degeneracy assumption for nonlinear harmonic games

The verification of Assumption 5 in our paper is not limited to linear polymatrix games. Specifically, in Appendix B.4.2 we explicitly verify the condition for a nonlinear harmonic family whose Nash equilibrium set is nonconvex. We note that there exist other parameterized families of nonlinear harmonic games that also satisfy the condition. We will make these nonlinear examples more prominent.

As described in Remark 3.5, one key consequence of Assumption 5 is that it supplies a local linear error bound around reachable Nash equilibria. The use of local error bound assumptions and related regularity conditions to establish quantitative convergence rates has substantial precedent in the literature on learning in games and variational inequalities (see, e.g., [Azizian+2024, Assumption 2], [Wei+2021, Definition 1 and Theorem 8], and [Giannou+2022, Proposition 1]). In our proof, Proposition 5.6 converts the local error bound into an operator domination inequality that is uniform over compact reachable sets. Combining this inequality with the energy dissipation bounds yields the linear last iterate rate.

The energy dissipation bounds we prove in Lemma 5.4 do not require Assumption 5. Assumption 5 is important for establishing linear convergence rates. However, under weaker structural conditions, such as local Hölder error bounds around reachable Nash equilibria, the same dissipation framework can yield slower polynomial last-iterate convergence guarantees.

AuthorsOpenReview ↗

Rebuttal part 3/3

References:

[Anagnostides+2025]: “A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition,” FOCS 2026.

[Azizian+2024]: “The rate of convergence of bregman proximal methods: Local geometry versus regularity versus sharpness.”, SIAM Journal on Optimization, 2024.

[Cai+2022]: “Finite-time last-iterate convergence for learning in multi-player games.” NeurIPS 2022

[Giannou+2022]: “On the convergence of policy gradient methods to Nash equilibria in general stochastic games.” NeurIPS 2022

[Lazarsfeld+2026]: “When and why is optimistic multiplicative weights slow? The geometry of energy dissipation, ” NeurIPS 2026.

[Legacci+2024a]: “No-regret learning in harmonic games: Extrapolation in the face of conflicting interests." NeurIPS 2024.

[Legacci+2024b]: “A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights,” ICML 2024.

[Legacci+2026]: “Adapting to conflict: Equilibrium structure and adaptive learning in harmonic games,” NeurIPS 2026.

[Wei+2021]: “Linear last-iterate convergence in constrained saddle-point optimization.”, ICLR 2021

[Zhang+2026]: “Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games.” EC 2026

Reviewer_wTEDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers multiplayer harmonic games and analyzes last-iterate behavior of OFTRL, EGFTRL and FTRL. The authors show linear convergence rates for the first two algorithms, and show geometric divergence from equilibrium for FTRL for linear harmonic games.

Critical strengths
  1. The results seem interesting and address an important question about convergence rates in harmonic games. I particularly like that the paper provides both convergence and divergence results, giving a nice contrast between OFTRL/EGFTRL and FTRL.
  2. The paper overall is well-written and results are clearly presented.
Critical weaknesses
  1. The paper only considers multiplayer harmonic games. While it is an interesting class of games, it is unclear how well these results could be extended to other classes of games.
  2. Theorem 4.1 provides linear rate guarantees using γ(w0)\gamma(w_0). The authors show that such a constant exist, but do not characterize it nor bound it. While proving that the constant is positive is sufficient for the convergence, understanding the magnitude is important to evaluate quantitative strength of the result. In particular, if the constant is very small, it will correspond to very slow convergence.
  3. While Section 5.1 provides some (technical) intuition through energy dissipation, I would appreciate a more conceptual explanation of the difference between the convergence of OFTRL/EGFTRL and the divergence of FTRL.
Questions for authors
  1. Regarding W2: Could the authors provide an explicit characterization or bounds for γ(w0)\gamma(w_0) in Theorem 4.1? Even a bound for a simpler setting might be informative.
  2. Regarding W3: What is the high-level intuition behind the different behaviors of OFTRL/EGFTRL and FTRL? In particular, which properties of their updates are important for convergence rather than divergence?
  3. Regarding W1: To what extent do the results rely on harmonicity assumptions? Could similar guarantees hold for a broader class of games, or perhaps for games that are only approximately harmonic? I am not asking for a general result, but would appreciate some discussion of possible extensions and limitations.
4 comments
AuthorsOpenReview ↗

Rebuttal part 1/2

We thank the reviewer for their constructive feedback and for highlighting the significance of our results.

Reply to Q1

Regarding W2: Could the authors provide an explicit characterization or bounds for γ(w0)\gamma(w_0) in Theorem 4.1? Even a bound for a simpler setting might be informative.

The proof provides the following explicit formula of the rate coefficient: $ \gamma(w_0) =\frac18\min ( \frac{2c_\ell b^2}{c_h}, \frac{4}{\eta_{\max}^2}), $ where ηmax⁡=1880LBωκM\eta_{\max}=\frac{1}{880LB\omega\kappa_M}.

Here, in the symmetrized coordinates of Section 5, let KUK_U denote the compact effective-dual set used in Appendix J. The constants cℓ,ch>0c_\ell,c_h>0 bound the energy Hessian restricted to the effective dual space over y0+conv(KU)y_0+\text{conv}(K_U), and b>0b > 0 satisfies ∥π0(u)∥2≥b∥u−u⋆∥2\|\pi_0(u)\|_2\ge b\|u-u^\star\|_2 for all u∈KUu \in K_U, where u⋆u^{\star} corresponds to the selected equilibrium. Appendix J constructs these constants, and Appendix K (page 59, lines 3132 and 3150) converts the resulting operator-domination coefficient into γ(w0)\gamma(w_0). Thus, the coefficient depends on the regularizer’s geometry, the initialization, and the error-bound strength associated with Assumption 5.

For a concrete instantiation, consider the nonlinear harmonic example in Appendix B.4.2 with standard entropic regularization and identical stepsizes. Let c=2p3,0−1≠0c=2 p_{3,0} -1 \neq 0, where $p_{3,0} $ is the third player’s initial probability of their first action. The selected equilibrium w∞w_{\infty} has the first two players playing uniformly and the third retaining their initial strategy. Writing E0=DQ(w∞,w0)E_0= D_Q(w_{\infty}, w_0), under the theorem’s stepsize condition, one can choose γ(w0)=c24exp⁡(−4E0).\gamma(w_0)=\frac{c^2}{4}\exp(-4E_0). This estimate follows by combining Lemma 5.4 with an explicit operator-domination bound for the example. We will include its derivation in the revision. Although not necessarily sharp, this bound explicitly shows how the guaranteed rate deteriorates as the effective interaction strength ∣c∣|c| decreases or the initial divergence E0E_0 increases. Such sensitivity of instance-dependent rate coefficients also occurs in two-player zero-sum games, as studied in [Wei+21, Cai+24, Lazarsfeld+26].

Reply to Q2

Regarding W3: What is the high-level intuition behind the different behaviors of OFTRL/EGFTRL and FTRL? In particular, which properties of their updates are important for convergence rather than divergence?

The best intuition can be gained from viewing OFTRL/EGFTRL and FTRL as distinct types of discretizations of the continuous-time FTRL Flow dynamics, as discussed in Section 5, page 8.

In harmonic games, the FTRL flow perfectly conserves energy. As FTRL is a forward Euler discretization of this flow, convexity implies that its discretization error is non-negative, leading to energy expansion (expression (16)). This explains why vanilla FTRL tends to move away from equilibrium, and Theorem 4.5 makes this behavior quantitative for linear harmonic operators.

In contrast, OFTRL and EGFTRL can both be viewed as approximations of the idealized Implicit FTRL (IFTRL) method, which is a backward Euler discretization of the flow. IFTRL evaluates the operator at the next iterate, which is defined implicitly. Again by convexity, the change in shifted energy along IFTRL is non-positive (expression (16)), so the implicit update implies energy dissipation in this case.

OFTRL approximates the behavior of IFTRL by extrapolating from current and previous payoff vectors, while EGFTRL approximates this behavior by evaluating the payoff vector at an auxiliary lookahead point. Our proof strategy for Lemma 5.4 compares these updates with an implicit update step. For a sufficiently small constant stepsize, we show that the coupling error is dominated by the dissipative term, so energy dissipation persists under both explicit algorithms. Under Assumption 5, our reachable-set analysis and operator-domination inequality then convert this dissipation into linear last-iterate convergence.

AuthorsOpenReview ↗

Rebuttal part 2/2

Reply to Q3

To what extent do the results rely on harmonicity assumptions? Could similar guarantees hold for a broader class of games, or perhaps for games that are only approximately harmonic? I am not asking for a general result, but would appreciate some discussion of possible extensions and limitations.

The harmonicity property provides the exact cancellation underlying the energy conservation along the continuous-time FTRL flow, and the energy dissipation bounds in discrete time. In particular, the harmonicity property corresponds to the weighted Minty equality (WMEQ) condition for the operator, as defined in expression (6). As explained in our reply to Q2 above, this equality cancels the first-order terms in the change in shifted energy for FTRL Flow and its forward and backward Euler discretizations, corresponding to FTRL and IFTRL, respectively (see expressions (15) and (16)).

Relaxing harmonicity is an interesting question for future work. One natural relaxation would be to require that the Minty inner product in (6) be nonnegative, replacing the equality with an inequality. Under this relaxation, the continuous time FTRL-flow would now have nonincreasing shifted energy along its trajectory. In discrete time, the one-step change in shifted energy under the idealized IFTRL algorithm would remain nonpositive, with an additional dissipative term arising from the Minty inequality. For EGFTRL, the same modification would preserve the energy-dissipation upper bound of Lemma 5.4 under the other regularity and stepsize conditions, since the remaining coupling error terms can be controlled as before. However, obtaining quantitative convergence rates would additionally require suitable error bounds and control of the geometry along the trajectory. For finite normal-form games, extending beyond the harmonic class through this route would additionally require allowing boundary Minty solutions, and this would require adapting the parts of our analysis that rely on interiority.

We will include a discussion of these possible extensions in the revised version, while leaving their full development to future work.

Thank you for the detailed responses and clarifications.

I have also read other reviewers' comments and share concerns about the mildness of Assumption 5 and its relationship to prior work. While I agree that these points limit the generality and novelty of the presented results, I still find the quantitative convergence guarantees and the analysis of the different behaviors of FTRL to be meaningful theoretical contributions.

Therefore, I maintain my positive score.

We thank the reviewer for their time and feedback, and for the positive assessment of our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.