acceptodds
Under review as a conference paper at ICLR 2027

Constant Regret in Finite Games via Higher-Order Optimism

Abstract

We introduce an uncoupled learning algorithm which, when employed by all players of an *arbitrary* -player normal form game with up to actions per player, guarantees individual regret, uniformly over the horizon of play. The proposed algorithm—which we call *higher-order optimism with discounting* (HOOD)—is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted -th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general finite games.

Primary area:
learning theory
Keywords:
regret, learning in games, regularized methods, higher-order optimism

Reviews

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

This paper studies uncoupled no-regret learning dynamics with gradient feedback for general-sum normal-form games and resolves a long-standing open problem: whether constant in T (number of rounds) individual regret is possible? The paper answers this question affirmatively by proposing a new algorithm that, when run by every player, ensures individual regret of order N3log⁡2KN^3\log^2 K where NN is the number players and KK is the number of actions for each player.

The algorithm is built on a (by now) standard framework: optimistic FTRL along with a lifting idea from Farina et al. 2022. The two new ingredients are: a new square-root lifted entropy regularizer and a discounted high-order difference predictor (replacing the standard predictor that simply uses the most recent payoff vector). The analysis relies on a intricate interplay between these two new ingredients.

Critical strengths
  • The paper resolves a major open problem in the field. While the idea of high-order difference was already utilized in the breakthrough of Daskalakis et al. (2021) to obtain polylogarithmic regret, it still requires significantly new ideas to finish the last mile and obtain constant regret.

  • The paper is generally very well written. Some choices/reasonings still feel a bit mysterious, but one can clearly see the authors' effort in trying to explain things in an intuitive way.

  • Despite the complicated proofs (which often come with huge constants), the constants in the final regret bounds are in fact surprisingly small and clean.

  • I appreciate the detailed and honest review of concurrent works in Appendix A.

Critical weaknesses

The only "critical" weakness I see is the following: while the proposed regret bound is constant in TT, it does have larger dependence on the other two parameters NN and KK compared to prior work. In particular, the increase in the dependence on NN (which is N3N^3) might very well outweigh the benefit of having no TT dependence in practice. It would be good to see what really happens empirically through some experiments, although I expect that it is quite difficult to beat vanilla optimistic Hedge.

Beyond that, I only have some minor comments:

  1. I am not sure I like the fact that the authors adopt a new name, FTRL+, for what's well known as optimistic FTRL in the literature. The authors seem to treat optimistic FTRL as always using vt−1v_{t-1} as the prediction v^t\hat{v}_t, but that's not just true; in the literature, optimistic FTRL is already stated with a general v^t\hat{v}_t.

  2. It might be good to compress Sec 3 a little bit, just to leave more space to explain the new ideas of this work. In my opinion, everything in Sec 3 (before Eq. 19) is fairly standard.

  3. L300: I understand that zi,t+1z_{i,t+1} is important for the analysis, but it's actually not used at all in the algorithm (so it seems weird to include it as part of the update rule).

Questions for authors

I don't have questions whose answers could materially affect my assessment, but I would like to hear the authors' comments on the following: as mentioned in the paper, the specific combination of the regularizer and the high-order predictor is critical for the analysis, but I wonder whether this combination is "optimal" in some sense. In other words, under the same analysis framework, do the authors believe that there might be an even better combination, or are there significant obstacles in this approach to go beyond the N3log⁡2KN^3\log^2K bound?

4 comments
AuthorsOpenReview ↗

Reply Post 1/2

Dear Reviewer 1rka,

Thank you for your thoughtful review, positive evaluation, and constructive remarks! We are especially glad that you appreciated the writing and the effort to explain things in an intuitive way.

We have taken all your remarks into account and we updated our paper accordingly, highlighting all changes in blue; please also find our responses to your comments and questions in a series of "official comments" below.



Dependence on NN

The only "critical" weakness I see is the following: while the proposed regret bound is constant in TT, it does have larger dependence on the other two parameters NN and KK compared to prior work. In particular, the increase in the dependence on NN (which is N3N^3) might very well outweigh the benefit of having no TT dependence in practice. It would be good to see what really happens empirically through some experiments, although I expect that it is quite difficult to beat vanilla optimistic Hedge.

Fair point, yes—but, at the same time, this applies to much of the "constant regret" literature. In our view, the key point isn't so much to shave off a logarithmic factor (which, as you say, may be irrelevant in practice), but to push the envelope of the existing algorithmic theory, to see what can and cannot be achieved with the various schemes at our disposal, and to examine new algorithmic tricks and techniques that could be useful well beyond the current context (lifting, higher-order optimism, the precise regularizer-optimism interplay, etc.). This theoretical thrust was the primary motivation—and contribution—of our paper.

Now, with respect to OptHedge in particular, the very recent work of Dagan et al. (2026) (https://arxiv.org/abs/2611.07078) showed that OptHedge with any learning rate greater than 2−Ω(NK)2^{-\Omega(NK)} (a very small value), can incur linear regret for at least one player in some game. In fact, even in the small NN regime, any fixed learning rate (up to some absolute constant) may incur 2Ω(K)2^{\Omega(K)} individual regret in some game. In view of this, the most principled candidate for a worst-case empirical comparison between OptHedge and HOOD would be the "difficult" games identified by Dagan et al. However, since this paper appeared only two days before the reviews were released (on Nov. 4, 2026), we are not in a position to provide a verified series of numerical experiments at this point—if the paper is accepted, we will be happy to do so at the camera-ready stage.


Terminology of OptFTRL

I am not sure I like the fact that the authors adopt a new name, FTRL+, for what's well known as optimistic FTRL in the literature. The authors seem to treat optimistic FTRL as always using vt−1v_{t-1} as the prediction v^t\hat v_t, but that's not just true; in the literature, optimistic FTRL is already stated with a general v^t\hat v_t.

We understand your concern. The problem is that, especially in the literature on games and variational inequalities (where the history of extrapolation-based methods goes back to the extra-gradient method of Korpelevich and Popov in the late 70's), the characterization "optimistic" is typically applied to the Popov choice v^t=v(xt−1/2)\hat v_t = v(x_{t-1/2}), leading to the specific incarnations of "optimistic gradient descent", "optimistic multiplicative weights / Hedge" and the like. This is particularly an issue in the case of "higher-order optimism", which specifically refers to the reuse of past gradient information.

So, even though we fully acknowledge that, as you pointed out, the "Optimistic FTRL" scheme of Rakhlin and Sridharan (2013a) is a "template" scheme with a general estimator v^t\hat v_t, we introduced the terminology FTRL+ as a way to (i) highlight the extrapolation origins of the method in the spirit of the original papers of Korpelevich (1976) and Popov (1980); and (ii) resolve this disconnect between (part of) the online learning literature and (part of) the game-theoretic / optimization literature, where "optimistic" can mean different things—especially in the context of "higher-order optimism".

Having said all that, we completely understand your concern, and we are torn ourselves on which terminology is more appropriate. We would greatly welcome your input on this.


Material in Section 3

It might be good to compress Sec 3 a little bit, just to leave more space to explain the new ideas of this work. In my opinion, everything in Sec 3 (before Eq. 19) is fairly standard.

We can trim some of the more "basic" parts of Section 3, but we believe that the description of the lifting mechanism and the RVU inequality should still be detailed to some extent in order to make the paper more accessible outside a narrow band of experts. The precise degree is, of course, subjective, but we want our paper to be as self-contained as possible.

AuthorsOpenReview ↗

Reply Post 2/2

Continued from Reply Post 1


Choice of HOOD components

I wonder whether this combination is "optimal" in some sense. In other words, under the same analysis framework, do the authors believe that there might be an even better combination, or are there significant obstacles in this approach to go beyond the N3log⁡2KN^3\log^2 K bound?

Great question, thanks for raising it!

First, as to the tightness of the specific dependencies:

  • The N3N^3 dependence is essentially due to (28), which is what makes the expansion in Appendix F summable. In more detail, the N3N^3 factor appears when counting the terms in the expansion that we explain in the proof overview: each continuing term of order pp has at most 3p(N−p)≤3N2/43p(N-p)\leq 3N^2/4 children in the expansion tree, each with an extra factor 2(N+1)η2(N+1)\eta. Summability requires this product to be small, which ultimately leads to the bound η≲N−3\eta\lesssim N^{-3}. As far as we can see, this count is tight (in the sense that we are not overcounting terms), cf. Appendix B.3, line 867 and onward.
  • The dependence on KK on the other hand basically comes from the range of the regularizer, since the bound (29) of Theorem 1 is 3L/η3L/\eta. In more detail, by Proposition 2, the range of (SRE) is at most 13L/613L/6, and the log⁡2K\log^2K term in L=4+log⁡K+14log⁡2KL=4+\log K+\frac14\log^2K comes from the logarithmic moment bound (C.5) that we use to control the derivatives of the regularizer.

In either case, we cannot discount the possibility of obtaining a better bound by playing around with the defining elements of HOOD—namely, the choice of regularizer, and the choice of predictor (and, perhaps, a different higher-order expansion). This was also the reason that we tried to present HOOD in the most modular way possible: for example, it is easy to check that the choice ρ(λ)=λ+λ\rho(\lambda) = \lambda+\sqrt\lambda for the affine scaling of the regularizer gives a second derivative contribution that is of order λ−3/2\lambda^{-3/2} in (C.48), and which can therefore be controlled by the bounded term 3Lλ(1−λ)3L\sqrt{\lambda(1-\lambda)} of (SRE). For any other choice of regularizer (e.g., a Tsallis variant), one would have to find a specific combination of ρ\rho and θ\theta that would yield an improvement over the estimates of Lemma C.4 (which are specific to the entropy).

At this point, we do not see which other combination could work better, but this would be a very fruitful direction for future research since, if possible, it would allow us to tighten the dependence on NN and KK while keeping the core components of HOOD intact.


Further discussion

Thank you again for your time and your positive evaluation. We are looking forward to a constructive discussion—please let us know if you have any further questions!

Kind regards,

The authors

I thank the authors for their detailed response and would like to keep my positive evaluation.

Thank you again for your time, input, and continued support!

Warm regards,

The authors

Reviewer_4VV8OpenReview ↗
Rating
4(+1)
Confidence
3(−1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes HOOD, an uncoupled learning algorithm that achieves O(N3log⁡2K)O(N^3 \log^2 K) individual regret in arbitrary finite general-sum games. This removes the dependence on the time horizon TT from the previous state-of-the-art regret bound of O(Nlog⁡2Klog⁡T)O(N \log^2 K \log T) (achieved by Cautious Optimism, excluding concurrent works that also achieves constant regret), at the cost of an additional N2N^2 factor in the number of players NN. This result is significant, as it resolves the open problem of achieving constant regret.

Critical strengths

This work is a significant theoretical work. Achieving constant individual regret in general games has been an important open problem. The authors achieve this via high-order optimism, which is a really good idea (even though concurrent works show that one step optimism is already enough for this purpose).

Critical weaknesses

I wonder about the computational complexity of the line search over λ\lambda. Do the results still hold if λ\lambda can only be computed up to some approximation error ϵ\epsilon? Given the significance of the result, for the algorithm to be practical, I believe its computational aspects deserve further discussion.

Questions for authors

The paper introduces a specific square-root entropic regularizer, and Proposition 2 establishes several stability properties of the resulting choice map. I wonder how these properties relate to the notion of intrinsic Lipschitzness introduced in Cautious Optimism (Soleymani et al., 2025). In particular, combining Eq. (C.73) with Eq. (C.2) seems to give an intrinsic Lipschitzness bound for the underlying entropy regularizer, while Eq. (C.97) establishes a similar type of stability condition for the Jacobian of the choice map. More broadly, is there a more general geometric condition that would suffice for the analysis? Could the authors extend their results to a broader family of regularizers?

Also, Eq. (24) suggests that the algorithm is implicitly controlling its effective learning rate through the lifted parameter yy. Is this related to the dynamic learning-rate control in Cautious Optimism? Could authors elaborate a little bit more and give some intuition on how conceptually the effective learning rate is updated?

4 comments
AuthorsOpenReview ↗

Reply Post 1/4

Dear Reviewer 4VV8,

Thank you for your thoughtful review, positive assessment, and constructive remarks! We have taken them all into account and updated our paper accordingly, highlighting all changes in blue. We are also posting our responses to your questions and remarks in a series of "official comments" below.


Computational complexity

I wonder about the computational complexity of the line search over λ\lambda. Do the results still hold if λ\lambda can only be computed up to some approximation error ϵ\epsilon? Given the significance of the result, for the algorithm to be practical, I believe its computational aspects deserve further discussion.

Thanks for this question—there are several points to note here.

First, we should point out that numerical approximation errors are not specific to HOOD: from a practical viewpoint, any algorithm involving transcedental functions—like the ordinary exponential function which appears in any incarnation of Hedge, OptHedge, and their variants—is de facto subject to floating-point arithmetic errors. Such errors can indeed affect the regret guarantees of these algorithms, just as approximation errors in the computation of λ(y)\lambda(y) can affect those of HOOD: in both cases, these errors could propagate to the sequence of strategies played by the algorithm over time, potentially affecting the incurred regret. However, these effects are usually abstracted away in theoretical regret analyses algorithms, which typically assume exact arithmetic—and which is the point of view that our paper adopted as well.

In light of this, the very short answer is that, from the standpoint of computational precision, HOOD is as practical as any Hedge-based algorithm (vanilla multiplicative weights, OptHedge, etc.).

To see this, note that each player's strategy update boils down to computing KK exponentials (for the softmax step), and the associated mass λ(y)\lambda(y). In a fixed-precision arithmetic model (such as the double-precision binary64 IEEE 754 format which is the most common in practice), both steps require O(K)\mathcal{O}(K) time:

  • For the softmax step: Computing an exponential to a fixed machine precision takes O(1)\mathcal{O}(1) time, so the softmax requires O(K)\mathcal{O}(K) time.
  • For the mass step: Computing the mass λ(y)\lambda(y) requires finding the maximizer of a strictly concave function over [0,1][0,1], namely Vy(λ)V_y(\lambda) of Eq. (C.33) in Appendix C. This function (and its derivatives) can be evaluated using fixed-precision arithmetic in O(K\mathcal{O}(K) time for any λ\lambda, so, assuming sufficiently accurate derivative-sign evaluations, a derivative-based bisection search can likewise compute λ(y)\lambda(y) to the prescribed numerical tolerance in O(K)\mathcal{O}(K ) time.

In a variable-precision model—which is much less common in practice because it is considerably slower and more costly—the comparison is more complicated, but also leads to the same conclusion. In more detail, if b=log⁡2(1/ε)b= \log_2(1/\varepsilon) denotes the requested number of bits at a given step, we have the following complexity estimates (assuming sufficient working precision, no numerical conditioning issues, and that all input quantities are available to the required precision):

  • For the softmax step: Computing an exponential to bb bits has quasi-linear complexity of the order of E(b)=O(blog⁡2b)=O~(b)E(b) = \mathcal{O}(b \log^2 b) = \mathcal{\tilde O}(b), using fast-integer multiplication and arithmetic-geometric-mean methods, as per the classical algorithm of Brent. As a result, computing the softmax to bb bits requires O~(Kb)\mathcal{\tilde O}(Kb) time.
  • For the mass step: Computing Vy(λ)V_y(\lambda) and its first two derivatives requires O~(Kb)\mathcal{\tilde O}(Kb) time for any λ\lambda. Then, using a derivative-based line-search with Newton's method, the bit complexity of computing the maximizer of Vy(λ)V_y(\lambda) to bb bits of precision is, again, O~(Kb)\mathcal{\tilde O}(Kb).

Finally, as for the ε\varepsilon-error propagation part of your question: this is difficult to quantify, because one must first specify the precise underlying arithmetic model, and this can be a very delicate affair. For example, under finite-precision floating-point arithmetic, addition of signed floats ceases to be associative, so the tracking of arithmetic errors is much more involved than the tracking of numerical errors.

To summarize: The mathematically pleasant "closed form" expression of the softmax in OptHedge still involves approximate expressions when the algorithm is deployed in practice, and the bit complexity of this approximation is of the same order as for HOOD. We included a version of the above discussion but not all of the above details in our paper because issues of floating-point arithmetic are usually not considered in the regret analysis of online learning algorithms; that said, we would be happy to do so if you find it relevant.

AuthorsOpenReview ↗

Reply Post 2/4

Continued from Reply Post 1


Intrinsic Lipschitzness

The paper introduces a specific square-root entropic regularizer, and Proposition 2 establishes several stability properties of the resulting choice map. I wonder how these properties relate to the notion of intrinsic Lipschitzness introduced in Cautious Optimism (Soleymani et al., 2025). In particular, combining Eq. (C.73) with Eq. (C.2) seems to give an intrinsic Lipschitzness bound for the underlying entropy regularizer, while Eq. (C.97) establishes a similar type of stability condition for the Jacobian of the choice map.

Thanks for this question. There is a lot to unpack here, so we proceed point-by-point.

To provide some context, intrinsic Lipschitzness (IL) is an instance of Bregman regularity, and is nested between the relative continuity (RC) condition of Lu (2018, https://arxiv.org/pdf/1710.04718) and the Riemann-Lipschitz continuity (RLC) condition of Antonakopoulos et al. (2020, https://openreview.net/forum?id=rkxZyaNtwB). Specifically, we have:

(RC)  ⟹  (IL)  ⟹  (RLC)\mathrm{(RC)} \implies \mathrm{(IL)} \implies \mathrm{(RLC)}

In view of this nesting, IL essentially translates to a bound on the first derivative of ψ\psi, namely a boound on the norm of the gradient of ψ\psi relative to the intrinsic geometry of ψ\psi, as follows:

\quad \text{for some $G>0$}. \tag{D1}$$ This should be contrasted to the notion of relative Lipschitz smoothness (RS), as introduced by Bauschke, Bolte & Teboulle (2017) and Lu, Freund & Nesterov (2018): a convex function $f$ is $L$-smooth relative to $\psi$ if $L\psi - f$ is convex. This is essentially a bound on the **second derivative** of $\psi$, namely a Hessian bound of the form $$\Vert \nabla^2 f(x) \Vert_{\nabla^2\psi(x)^{-1}} \leq L \quad \text{for some $L>0$}. \tag{D2}$$ This reformulation is important because, replacing $\nabla f$ with an arbitrary operator $A$, we get the Jacobian bound $$\Vert DA(x) \Vert_{\nabla^2\psi(x)^{-1}} \leq L \quad \text{for some $L>0$}.$$ This is in turn implied by the Bregman continuity (BC) condition of Antonakopoulos et al. (2019), which, in our notation, reads $$\Vert A(x') - A(x) \Vert_{\nabla^2\psi(x)^{-1}} \leq L \sqrt{D_{\psi}(x,x')} \quad \text{for some $L>0$}. \tag{BC}$$ This is closer, but still not what we have in our paper. In our case, ignoring the $\exp(M/4)$ factor, Condition (C.97) can be rewritten as $$\Vert DQ(y') - DQ(y) \Vert \leq H \sqrt{D_{\psi^\ast}(y,y')} \quad \text{for some $H>0$} \tag{C.97}$$ where $D_{\psi^\ast}$ denotes the Bregman divergence of the convex conjugate $\psi^\ast$ of $\psi$, and we used the fact that $D_\psi(Z(y'),Z(y)) = D_{\psi^\ast}(y,y')$. Consequently, compared to the previous conditions, this means the following: - (C.97) is a form of **second-order regularity** of $Q$, which, in the functional setting, would correspond to a bound on the **third derivative** of $\psi$ (as opposed to the **first derivative** for IL). - The operator norm in (C.97) is global, but the factor $M$ means that (C.97) is local; by contrast, (BC) involves a *local* operator norm, but holds *globally*. **To summarize:** In view of all this, the closest analogies that we can draw are as follows: 1. (C.97) can be seen as a sort of "Bregman smoothness" condition for $Q$, that is, a second-order analogue of Bregman continuity for the operator $Q$. 2. In the functional setting, (C.97) would correspond to a bound on the third derivatives of $\psi$, that is, two orders of smoothness higher than the first-order bound of (IL)/(RLC). Of course, drawing a unified picture of all these generalized smoothness conditions would be an excellent direction for future research, but one which lies beyond the scope of the current paper.
AuthorsOpenReview ↗

Reply Post 3/4

Continued from Reply Post 2


Choice of geometry and regularizer

More broadly, is there a more general geometric condition that would suffice for the analysis? Could the authors extend their results to a broader family of regularizers?

Great question, thanks!

To begin with, note that the proof only uses the regularizer, essentially, through its strong convexity and bounded range to get the RVU. It then also uses coercivity (C.66), the Jacobian bound (25), the stability of the mass (B.10), and (C.97). Said in a more synthetic fashion, what we need is for the Bregman divergence of the lifted regularizer to control locally both (i) the Jacobian times the strategy variation and (ii) the variation of the Jacobian. We expect that any steep lifted regularizer with these properties would give constant regret through the same proof trajectory (though with different constants, bounds and details, of course).

There are, however, two subtleties:

  • First, for (i), when the mass is small: in general, DψD_\psi only controls λ∥x′−x∥12\lambda\Vert x'-x\Vert_1^2 and not ∥x′−x∥12\Vert x'-x\Vert_1^2 itself (see (C.66), and (B.3) for the naive lift), as λx\lambda x and λx′\lambda x' are close to each other near 00 even when xx and x′x' are far apart. This means that the choice map has to make up for it with a condition of the form ∥J(y)∥op2≲λ(y)\Vert\mathcal J(y)\Vert_{\rm op}^2\lesssim\lambda(y), which is what (25) gives and what makes the two factors cancel in (B.7).
  • Similarly, for (ii): the proof of (C.97) matches the factor λ\sqrt\lambda of the Jacobian variation in (C.112) with the mass λ\lambda in (C.65), while (B.10) allows us to compare all these quantities at nearby scores.

As for employing a different regularizer in our analysis, consider a lift of the entropy of the form ψ(λx)=ρ(λ)h(x)+θ(λ)\psi(\lambda x)=\rho(\lambda)h(x)+\theta(\lambda) as in (23). Solving (11) at a fixed mass λ\lambda gives the logit map with temperature λ/ρ(λ)\lambda/\rho(\lambda), so (i) asks for ρ(λ)≳λ\rho(\lambda)\gtrsim\sqrt\lambda, which the naive choice ρ(λ)=λ\rho(\lambda)=\lambda does not satisfy. The mass is then the maximizer of Vy(λ)=ρ(λ)log⁡∑αexp⁡(λyα/ρ(λ))−θ(λ),V_y(\lambda)=\rho(\lambda)\log\sum_\alpha\exp(\lambda y_\alpha/\rho(\lambda))-\theta(\lambda), which is (C.33) for (SRE). Since ψ\psi has to be convex, VyV_y has as such to be concave for every yy, that is, θ′′\theta'' has to be greater or equal than the second derivative in λ\lambda of the first term of VyV_y. When ρ≡1\rho\equiv1, for instance, this first term is just log⁡∑αexp⁡(λyα)\log\sum_\alpha\exp(\lambda y_\alpha), whose second derivative is Varx(y)\mathrm{Var}_x(y) for x=Λ(λy)x=\Lambda(\lambda y), and with y=(log⁡x)/λy=(\log x)/\lambda for a fixed xx it is equal to Varx(log⁡x)/λ2\mathrm{Var}_x(\log x)/\lambda^2; hence θ′′≳λ−2\theta''\gtrsim\lambda^{-2} near 00, and this forces θ\theta to blow up like −log⁡λ-\log\lambda (as per the log⁡λ\log\lambda terms of LRL-OFTRL in Farina et al., 2022), and the range of ψ\psi, hence H0H_0 in (RVU), is then no longer bounded.

With ρ(λ)=λ+λ\rho(\lambda)=\lambda+\sqrt\lambda, on the other hand, this second derivative is only of order λ−3/2\lambda^{-3/2} (see (C.48)), which the bounded term −3Lλ(1−λ)-3L\sqrt{\lambda(1-\lambda)} of (SRE) takes care of. So for other base regularizers (say, Tsallis-like), one would have to find such ρ\rho and θ\theta and to redo the estimates of Lemma C.4, which are specific to the entropy; we have not undertaken this analysis, but it would be a very fruitful direction for future research.

AuthorsOpenReview ↗

Reply Post 4/4

Continued from Reply Post 3


Lifting as an adjusted learning rate

Also, Eq. (24) suggests that the algorithm is implicitly controlling its effective learning rate through the lifted parameter yy. Is this related to the dynamic learning-rate control in Cautious Optimism? Could authors elaborate a little bit more and give some intuition on how conceptually the effective learning rate is updated?

To some extent, yes, lifting can be seen as an effective learning rate: any lifting scheme of the general form (11) with an affinely weighted regularizer of the form (23) ultimately yields a strategy selection step of the form xt=Λ(ηtRt)x_t=\Lambda(\eta_t R_t), where Rt=yt+1/2/η=∑τ<tgτ+g^tR_t = y_{t+1/2}/\eta = \sum_{\tau<t}g_\tau+\hat g_t is the vector of cumulative regrets plus the prediction term g^t\hat g_t, and ηt=η λt/ρ(λt)\eta_t = \eta\,\lambda_t/\rho(\lambda_t), with λt=λ(yt+1/2)\lambda_t=\lambda(y_{t+1/2}) the mass given by (11), which depends on both ρ\rho and θ\theta (for (SRE), this gives ηt=η [1+λt−1/2]−1\eta_t=\eta\,[1+\lambda_t^{-1/2}]^{-1}). In this regard, (LiftFTRL+) can be seen as a version of OptFTRL, with a more general, regret-driven signal, and a state-dependent learning rate.

In the entropic case, the Cautious Optimism paper picks the learning rate λ∈(0,η]\lambda\in(0,\eta] and the strategy simultaneously, maximizing λ⟨r,x⟩+αlog⁡λ−h(x)\lambda\langle r,x\rangle+\alpha\log\lambda-h(x) (here rr denotes their optimistic cumulative regrets and α>0\alpha>0 is a positive constant); the closest analogue for HOOD would be the mass and the strategy update step in (11). Since in both cases the regrets enter linearly, lowering all of them by the same amount cc lowers the objective by exactly cλc\lambda (or ηcλ\eta c\lambda for HOOD, as yt+1/2=ηRty_{t+1/2}=\eta R_t), because they only appear through the linear term λ⟨r,x⟩\lambda\langle r,x\rangle, resp. ⟨y,λx⟩\langle y,\lambda x\rangle in (11), and ⟨1,x⟩=1\langle\mathbf 1,x\rangle=1; this can only decrease the maximizing λ\lambda, and hence the effective learning rate.


Further discussion

Thank you again for your time, input, and positive evaluation. Please let us know if you have any further questions or remarks—we are looking forward to a constructive discussion!

Kind regards,

The authors

Reviewer_TLRJOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies no-regret learning on repeated games under full information. The objective is to come up with an algorithm such that, for all general-sum normal-form games between NN players, each having at most KK pure strategies, under uncoupled self-play every player obtains "constant" regret with respect to the time horizon. Uncoupled self-play means all players deploy the same algorithm under their own stragies and own infomration feedback. The authors propose HOOD, which is a variant of lifted extrapolated FTRL, with a specific choice of predictor (for the extrapolation part) and a specific choice of regularizer on the lifted space. Using HOOD each player obtains O(N3log⁡2K)O(N^3 \log^2 K). The learning rate and the regret bound are totally independent of TT.

Critical strengths
  • Relative to pre-contemporaneous work, the result is significant on the theory side: Removing the dependence on the horizon and achieving a constant regret bound for uncoupled learning in general-sum games is relatively a final stage in a thread of research.

  • Theoretical elegance in the matching between their novel choice of predictor and the lifted regularizer. Also, the fixed (non-adaptive) learning rate and the regret not depending on T are notable.

  • The presentation of the paper is good. It has a nice flow, and it points to the main ideas and tricks in a concise and, at the same time, technical way.

Critical weaknesses
  • The very small step size and the N3N^3 dependence make the algorithm slow in practice.

  • Lower bounds and dependence on NN can be discussed in more detail. Also, a discussion of the computational complexity of the algorithm can be added.

  • Lack of experiments: Although the main thesis of the work is theoretical, having an experiment, even on, a toy problem, and a comparison to other algorithms would be informative.

Questions for authors

Comment:

  • On the contemporary wave of results: There are very recent results regarding the same questions; some of them are weaker than this paper, and some are stronger. From the summary of those papers in the appendix, I believe the difference in their approach is enough, and it should not be counted as a downside for this paper.

Questions: First I would be happy to see your opinion on the previous points, especially on the weakness section. In addition, I have two questions:

  • Does HOOD still work if each player has an upper bound on the number of players?

  • I also consulted and did a proof check with Claude, and it was just uncertain about Proposition F1. I also skimmed that part, but I would like to quote the question it proposed regarding this, and would appreciate further explanation on this. “Proposition F.1 is the crux of the argument, but its invariants (exhaustive classification of summands, label multiplicities, round shifts, and the product bound (F.8) for the generated class of multilinear maps) are asserted with brief justifications, and the notion of a ‘term’ is not formally defined. I could not find an error, but I would ask the authors to (i) define the class of expressions formally, and (ii) include a fully worked expansion for N = 2, where the full tree can be written explicitly. This would make the key mechanism, and the role of the repeated-label pairing, transparent to readers.”

Suggestions:

  • Mention that the predictor is reusable and can be incrementally updated (regarding the computational complexity and dependence on NN.)
  • The lifted regularizer basically makes a regret-dependent learning rate. It is useful to compare this algorithm with cautious learning in more detail. Also, the connection between this work and adaptive learning rates can be discussed.
  • Line 485: I think you mean last-iterate convergence. Since you already get NE convergence in zero-sum games. You can explicitly say the last-iterate results for future work.
4 comments
AuthorsOpenReview ↗

Reply Post 1/3

Dear Reviewer TLRJ,

Thank you for your careful review, positive assessment, and constructive remarks! We have taken them all into account and updated our paper accordingly, highlighting all changes in blue. We are posting our responses to your questions and remarks in a series of "official comments" below.


Step-size

The very small step size and the N3N^3 dependence may make the algorithm slow in practice.

Thanks for the question!

The somewhat small step-size is mandated by the worst-case analysis. We agree that, in some instances, HOOD may be slower than other algorithms, but this is just like, in some instances, the ellipsoid algorithm (which has polynomial worst-case complexity) is slower than the simplex algorithm (which has exponential worst-case complexity).

As we discuss below, the choice of step-size is not an artifact of the analysis: there are definite cases where vanilla algorithmic choices (like OptHedge) do much worse than HOOD. We cannot conjecture at this point whether a smoothed (or average-case) analysis framework would point to a different choice of step-size; this is a very interesting question for future research, but beyond the scope of our paper.


Lower bounds and dependence on NN

Lower bounds and dependence on NN can be discussed in more detail.

There are several points to note here:

  • First, the specific N3N^3 dependence for HOOD is due to (28), which is what makes the expansion in Appendix F summable. In more detail, the N3N^3 factor appears when counting terms in the expansion that we explain in the proof overview: each continuing term of order pp has at most 3p(N−p)≤3N2/43p(N-p)\leq 3N^2/4 children in the expansion tree, each with an extra factor 2(N+1)η2(N+1)\eta. Summability requires this product to be small, which ultimately leads to the bound η≲N−3\eta\lesssim N^{-3}. As far as we can see, this count is tight (in the sense that we are not overcounting terms), cf. Appendix B.3, line 867 and onward. We have added this discussion in Remark 2 of the main text.
  • Now, with respect to more "standard" algorithmic choices, the very recent work of Dagan et al. (2026) (https://arxiv.org/abs/2611.07078) showed that OptHedge with any learning rate greater than 2−Ω(NK)2^{-\Omega(NK)} (a very small value; much smaller than the 1/N31/N^3 learning rate of HOOD), incurs linear regret for at least one player. In fact, even in the small NN limit, any fixed learning rate (up to some absolute constant) may incur 2Ω(K)2^{\Omega(K)} individual regret. In other words, in the "vanilla" setting of OptHedge, the dependence of the maximum allowable learning rate on the number of players seems to be exponential in NN (compared to polynomial in the case of HOOD).
  • Beyond the lower bound of Dagan et al. we are not aware of a lower bound for a general class of algorithms.

NB: The paper of Dagan et al. appeared on arxiv on Nov. 4, 2026, two days before the reviews were released, so we only just discovered it ourselves.


Computational complexity

Also, a discussion of the computational complexity of the algorithm can be added.

Sure thing, we would be happy to elaborate on this—thanks for giving us the opportunity.

In short, the per-iteration complexity of HOOD is controlled by the predictor (HOP), which can be computed sequentially with N+1N+1 vectors b1,…,bN+1∈RKb_1,\dots,b_{N+1}\in\mathbb R^K per player (all initially set to zero). Indeed, with s0,t=gts_{0,t}=g_t, g^t=∑rbr,t−1\hat g_t=\sum_r b_{r,t-1} and for r=1,…,N+1r=1,\dots,N+1, sr,t=sr−1,t−br,t−1,br,t=δbr,t−1+(1−δ)sr−1,t,s_{r,t}=s_{r-1,t}-b_{r,t-1},\quad b_{r,t}=\delta b_{r,t-1}+(1-\delta)s_{r-1,t}, we get sr,t−δsr,t−1=sr−1,t−sr−1,t−1s_{r,t}-\delta s_{r,t-1}=s_{r-1,t}-s_{r-1,t-1}, hence sr=SδΔsr−1s_r=\mathrm S_\delta\Delta s_{r-1} by (D.1) and sN+1=es_{N+1}=e by (27), while also sN+1,t=gt−g^ts_{N+1,t}=g_t-\hat g_t, so (HOP) requires O(NK)\mathcal{O}(NK) time and memory.

As for the choice map of HOOD, each player's strategy update boils down to computing KK exponentials (for the softmax step), and the mass λ(y)\lambda(y). Assuming a fixed-precision arithmetic model (such as the double-precision binary64 IEEE 754 format, which is the most common in practice), both steps require O(K)\mathcal{O}(K) time:

  • Computing an exponential to a fixed machine precision requires O(1)\mathcal{O}(1) time, so computing the softmax requires O(K)\mathcal{O}(K) time.
  • Computing the mass λ(y)\lambda(y) requires finding the maximizer of a strictly concave function over [0,1][0,1], namely Vy(λ)V_y(\lambda) of Eq. (C.33) in Appendix C. This function (and its derivatives) can be evaluated using fixed-precision arithmetic in O(K)\mathcal{O}(K) time for any λ\lambda, so, assuming sufficiently accurate derivative-sign evaluations, a derivative-based line-search can likewise compute λ(y)\lambda(y) to a fixed numerical tolerance in O(K)\mathcal{O}(K ) time.

We have also included a version of the above discussion in Remark 3 of the main text.

AuthorsOpenReview ↗

Reply Post 2/3

Continued from Reply Post 1


Experiments

Lack of experiments: Although the main thesis of the work is theoretical, having an experiment, even on, a toy problem, and a comparison to other algorithms would be informative.

The most principled candidate for this comparison would be the "difficult" games identified in the very recent paper of Dagan et al. (https://arxiv.org/abs/2611.07078). However, since this paper appeared just two days before the reviews were released, on Nov. 4, 2026, we are not in a position to provide a verified series of numerical experiments at this point—if the paper is accepted, we will be happy to do so at the camera-ready stage.


On contemporaneous work

On the contemporary wave of results: There are very recent results regarding the same questions; some of them are weaker than this paper, and some are stronger. From the summary of those papers in the appendix, I believe the difference in their approach is enough, and it should not be counted as a downside for this paper.

Thanks a lot for saying so!


Estimated number of players

Does HOOD still work if each player has an upper bound on the number of players?

Yes, and this follows already from our main result by adding some "dummy players". In more detail, if everyone replaces NN by some fictitious upper bound M≥NM\ge N in Algorithm 1 and (28), then adding M−NM-N dummy players with constant payoffs (that do not affect the other players) changes nothing, but Theorem 1 then gives the bound 3L/η3L/\eta, of order M3log⁡2KM^3\log^2K.

In fact, the players do not even need to agree on the same bound for their predictors: if player ii uses its own bound Mi≥NM_i\ge N in (HOP), the proof still goes through, provided that every player takes a learning rate satisfying (28) with NN replaced by the largest bound max⁡iMi\max_i M_i. Indeed, the order of the predictor only needs to be at least N+1N+1, and a larger order just makes each step of the expansion cost a larger factor (of order Mi+1M_i+1 instead of N+1N+1, which comes from the discounting), so that a smaller learning rate keeps the expansion summable, which is all we need (see our answer to your second point). We added this remark in our revision (Remark 2).


Technical question

I also consulted and did a proof check with Claude, and it was just uncertain about Proposition F1. I also skimmed that part, but I would like to quote the question it proposed regarding this, and would appreciate further explanation on this. "Proposition F.1 is the crux of the argument, but its invariants (exhaustive classification of summands, label multiplicities, round shifts, and the product bound (F.8) for the generated class of multilinear maps) are asserted with brief justifications, and the notion of a 'term' is not formally defined. I could not find an error, but I would ask the authors to (i) define the class of expressions formally, and (ii) include a fully worked expansion for N = 2, where the full tree can be written explicitly. This would make the key mechanism, and the role of the repeated-label pairing, transparent to readers."

Thanks for the detailed Claude pass. The meaning of a "term" is explained in detail both in the proof overview and right above Proposition F.1 itself. Precisely, by a "term" we mean a fixed multilinear map, the same for all tt, whose arguments are strategy, payoff excesses and Jacobian factors taken at rounds t−qt-q, as in the two paragraphs before (F.8).

Moreover, in the proof overview—cf. Eq. (B.17)—we give the multilinear expansion for two players followed right after by the one for NN players, as well as the expansion of one term in (B.24); in addition, we also draw one step of the expansion tree at order pp in Figure 3. We believe that these elements give more intuitive "algorithmic" understanding for the expansion than working it out in full (in particular, how it continues, how it stops, and which terms are relevant): a fully unrolled expansion would be rather cumbersome even for N=2N=2, and it would be difficult to distill and regroup the most important elements thereof in a way that makes intuitive sense.


Reusing the predictor

Mention that the predictor is reusable and can be incrementally updated (regarding the computational complexity and dependence on NN.)

Good point, thanks—we will do so as explained in our answer to your previous point.

AuthorsOpenReview ↗

Reply Post 3/3

Continued from Reply Post 2


Lifting as an adjusted learning rate

The lifted regularizer basically makes a regret-dependent learning rate. It is useful to compare this algorithm with cautious learning in more detail. Also, the connection between this work and adaptive learning rates can be discussed.

To some extent, yes, it can be seen in this light: any lifting scheme of the general form (11) with an affinely weighted regularizer of the form (23) ultimately yields a strategy selection step of the form xt=Λ(ηtRt)x_t=\Lambda(\eta_t R_t), where Rt=yt+1/2/η=∑τ<tgτ+g^tR_t = y_{t+1/2}/\eta = \sum_{\tau<t}g_\tau+\hat g_t is the vector of cumulative regrets plus the prediction term g^t\hat g_t, and ηt=η λt/ρ(λt)\eta_t = \eta\,\lambda_t/\rho(\lambda_t), with λt=λ(yt+1/2)\lambda_t=\lambda(y_{t+1/2}) the mass given by (11), which depends on both ρ\rho and θ\theta (for (SRE), this gives ηt=η [1+λt−1/2]−1\eta_t=\eta\,[1+\lambda_t^{-1/2}]^{-1}). In this regard, we agree that (LiftFTRL+) can be seen as a version of OptFTRL, with a more general, regret-driven signal, and a state-dependent learning rate.

On the other hand, this is distinct from the type of adaptive learning rates considered by, among others, Rakhlin and Sridharan (2013a,b), or Syrgkanis et al. (2015), which are themselves variations of the AdaGrad / AdaHedge inverse root-mean-square family of learning rates, e.g., ηt=1/∑s=1t∥gs∥2\eta_t = 1 \big/ \sqrt{\sum_{s=1}^t \|g_s\|^2} or ηt=1/∑s=1t∥g^s+1−g^s∥2\eta_t = 1 \big/ \sqrt{\sum_{s=1}^t \|\hat g_{s+1} - \hat g_{s}\|^2}, depending on the precise context (for the origins of these ideas, see the paper of Auer et al., 2002, "Adaptive and Self-Confident On-Line Learning Algorithms"). These learning rates are better suited to exploit unknown characteristics of the game (like the various Lipschitz constants or the history of the encountered payoff vectors over time) and, as such, the analysis and the control achieved are orthogonal to what is achieved via lifting.

In short, adaptive learning rates in the spirit of Auer et al. and Rakhlin and Sridharan are history-dependent, whereas the effective learning rate induced by the lifting mechanism is state-dependent: the former are always (weakly) decreasing, whereas the latter could decrease or increase at any given iteration, depending on the state of the algorithm.

The "cautious optimism" paper of Soleymani et al.(2025b) belongs to the latter kind: when the game's regret state is rr, the paper's algorithm uses a learning rate λ∈(0,η]\lambda\in(0,\eta] that is chosen jointly with the strategy xx by maximizing the function λ⟨r,x⟩+αlog⁡λ−h(x)\lambda\langle r,x\rangle+\alpha\log\lambda-h(x) for some constant α>0\alpha>0 (whose value is not relevant here). As such, the "effective" learning rate of Soleymani et al. (2025) is also state-dependent and derived by the minimization of a lifted regularizer, in the spirit of the original work of Farina et al. (2022).

We included a version of the above discussion in our paper in Remark 1.


Further discussion

Thank you again for your time, your input, and your positive evaluation. We remain at your disposal should you have any further questions or comments.

Kind regards,

The authors

Dear authors,

Thank you for the detailed response and the revision. Several of my points are now well addressed. Regarding the experiments, I understand that a careful study on the instances of Dagan et al. needs more time. A basic toy sanity check, however, does not depend on those instances, especially since your point about instance-dependent versus worst-case behavior is ultimately an empirical one. As you mentioned too, I would encourage you to add such a sanity check in the final version.

Overall, I have decided to raise my score to accept.

Best regards, Reviewer TLRJ

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.