- 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 where is the number players and 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 , it does have larger dependence on the other two parameters and compared to prior work. In particular, the increase in the dependence on (which is ) might very well outweigh the benefit of having no 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:
-
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 as the prediction , but that's not just true; in the literature, optimistic FTRL is already stated with a general .
-
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.
-
L300: I understand that 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 bound?
4 comments
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 bound?
Great question, thanks for raising it!
First, as to the tightness of the specific dependencies:
- The dependence is essentially due to (28), which is what makes the expansion in Appendix F summable. In more detail, the factor appears when counting the terms in the expansion that we explain in the proof overview: each continuing term of order has at most children in the expansion tree, each with an extra factor . Summability requires this product to be small, which ultimately leads to the bound . 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 on the other hand basically comes from the range of the regularizer, since the bound (29) of Theorem 1 is . In more detail, by Proposition 2, the range of (SRE) is at most , and the term in 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 for the affine scaling of the regularizer gives a second derivative contribution that is of order in (C.48), and which can therefore be controlled by the bounded term of (SRE). For any other choice of regularizer (e.g., a Tsallis variant), one would have to find a specific combination of and 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 and 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
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 N
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) (a very small value), can incur linear regret for at least one player in some game. In fact, even in the small N regime, any fixed learning rate (up to some absolute constant) may incur 2Ω(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
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), 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, 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
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.