acceptodds
Under review as a conference paper at ICLR 2027

A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games

Abstract

Can simple no-regret dynamics attain smaller regret in self-play than against arbitrary adversaries? In -player general-sum games, Daskalakis et al. 2021 proved an individual regret bound for Optimistic Hedge, which improves upon the classical adversarial regret bound. In this work, we show that Optimistic Hedge with a constant step size can further achieve individual external regret under expected loss-vector feedback. The time-averaged play consequently enjoys a coarse correlated equilibrium gap , where . The improvement comes from a larger admissible step size . Our analysis proves factorial bounds on high-order differences of probability-weighted pairwise loss gaps, then applies finite-difference interpolation in a fixed Euclidean norm. These estimates sharpen the analysis of Daskalakis et al. 2021 and yield a logarithmic regret bound.

Primary area:
optimization
Keywords:
game theory, no-regret learning, optimistic hedge

Reviews

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

This paper establishes an O(nlog⁡dilog⁡T)O(\sqrt{n}\log d_i\log T) individual regret bound for Optimistic Hedge in general-sum games, improving the previous O(nlog⁡dilog⁡4T)O(n\log d_i\log^4 T) result. The main technical contribution is a refined high-order smoothness analysis using weighted loss gaps, centered-logit recurrences, and finite-difference interpolation.

This is

Critical strengths
  1. The paper significantly improves the regret bound for the original Optimistic Hedge algorithm without modifying its update rule.

  2. The weighted-gap representation and factorial high-order difference bounds are technically interesting and may be useful beyond this setting.

  3. The proof is generally well structured, and I did not identify any clear mathematical errors in the main argument.

Critical weaknesses

The comparison with recent algorithms is incomplete. In particular, MORM (arXiv:2609.21976) achieves (O(\sqrt{n}\log d)) regret with simple closed-form updates, although it uses a different algorithm.

Questions for authors

The logarithmic regret guarantee requires a horizon-dependent learning rate. Is this dependence on TT inherent to the proposed high-order smoothness analysis, or could the argument be extended to obtain a comparable guarantee with a horizon-independent learning rate?

1 comment

We appreciate the reviewer for positive comments.

Comparison with more recent work

We thank the reviewer for pointing out the recent work that we’ve missed. In the updated manuscript, we add MORM and a brief discussion in Section 4 about a recent line of work that establishes horizon-independent regret upper bounds.

Q. Can similar argument be extended to obtain a horizon-independent step size?

The horizon dependence is not strictly inherent to the high-order smoothness analysis itself. For instance, Ha, arXiv 2026. “A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games” recently demonstrated that a similar approach based on the recurrence map reduction can yield a horizon-independent regret bound of On,d(1)O_{n,d}(1). However, their explicit dependence on the game dimensions (n,d)(n, d) remains implicit, and very recent work of Dagan et al. arXiv 2026. “Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation” showed that Optimistic Hedge with a fixed step size can suffer an Ω(2nd)\Omega(2^{nd}) regret lower bound. Whether a matching O(exp⁡(nd))O(\exp(nd)) upper bound can be formally established remains an open question.

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

This paper studies individual regret bounds for the canonical Optimistic Hedge (e.g,. Optimistic MWU) in multiplayer general-sum games. The main result is an individual regret bound scaling like O(log T) under a globally fixed stepsize (the scales inversely in log T). This improves the individual regret guarantees for Optimistic Hedge in general-sum games from O(log^4 T) (as proven by Daskalakis-Fishelson-Golowich 2021), down to O(log T). The key technical result is to obtain tighter bounds on higher-order differences on players' loss sequences that are subtituted into the standard (variance-refined) RVU inequality.

Critical strengths

The main strength of the paper is in obtaining a tighter analysis of Optimistic Hedge/MWU that improves its individual regret guarantee by polylogarithmic factors. As summarized in Table 1, there have been several lines of work in the past few years that improve on the bound of (Daskalakis-Fishelson-Golowich 2021) for general-sum games, but using more complex variants of Optimistic MWU. Over the past few months, several additional results have even obtains constant individual regret bounds in this setting, but again with more complicated variants of Optimistic MWU. In contrast, the present result establishes that O(log T) regret is attainable just using standard OMWU.

Critical weaknesses

In my opinion, the paper's presentation could be improved to offer more intuition of the analysis and comparison with several prior results. While the paper's main regret bound indeed improves over the prior result of Daskalakis-Fishelson-Golowich 2021, this type of improvement has felt somehwat expected/forthcoming given the results of, e.g., Soleymani et al. 2025. E.g., in my view, it is not super surprising that a tighter analysis of OMWU could lead to a log T individual regret bound. The technical result of bounding the higher-order differences of losses is also the natural starting point of obtaining such an improvement. However, I believe the paper could be improved with more discussion on why OMWU is amenable to tighter high-order difference bounds. In particular, I think the centered-logit recurrence formulation in Section 5.3 could be substantially expanded, since this is the key reduction to a certain dual space through which the analysis proceeds. I think the paper and its contributions would be enhanced by explaining whether a similar/related formulation also holds for other optimistic FTRL instantiations, what analytic properties of negative-entropy/softmax allow the analysis to go through, etc. However, the result by itself is still an improvement over the prior rate of Dakalakis et al. 2021.

Questions for authors

Questions:

  1. Can you discuss and give intuition on whether this analysis could be further pushed to obtain a constant regret bound (with respect to T). In the authors view, what are the remaining technical challenges in proving such a result?

Major suggestions:

  • A major suggestion is to remove all mentions of a "constant stepsize". This terminology is misleading (in relation to prior work in the learning in games subfield), because the admissible learning rate in the paper's main result is not an absolute constant and instead depends on the time-horizon T. In this paper, I believe it would be more appropriate to say a "fixed stepsize". Note this is in contrast to other results where \eta can indeed be as large as some absolute constant, with no dependence on T.

Minor suggestions:

  • Include a statement of Parseval's identity (either in the preliminaries or appendix).
1 comment

We thank the reviewer for thoughtful and constructive feedback.

Quality of Presentation

We acknowledge that the presentation of our analysis in the initial draft has room for improvements, and should offer cleaner intuition behind our result. In the updated the manuscript, we improved the overall writing, and exposition of our analysis as follows:

  • We added brief summaries of the key intuition behind our analysis in Abstract, Section 2, and the beginning of Section 5.
  • We added comparison of our result with Ha (2026) and MORM to Section 4.
  • We expanded Section 5.3 to explain the motivation behind the recurrence map representation of Optimistic Hedge.
  • We changed all the phrases “constant step size” to “fixed step size” across the manuscript.

The Intuition Behind the Analysis

In short, our analysis can be summarized as (1) reformulating Optimistic Hedge as a recurrence of centered-logits zitz_i^t and weighted loss gaps hith_i^t, which admit sharper high-order estimates, and (2) transferring this smoothness guarantee back to the original loss sequence.

The improvement on the number of players from nn to n\sqrt{n} comes from the sharper high-order derivative estimate in (1), which uses the softmax structure of the Optimistic Hedge update rule (Lemma 5.6).

On the other hand, the improvement on the logarithmic factor from log⁡4T\log^4 T to log⁡T\log T comes from using the sequence hith_i^t, which admits a time-invariant norm and allows a direct transfer of high-order difference estimates via finite-difference relation (Lemma 5.4), circumventing the inductive arguments of Daskalakis et al. (2021).

We clarify these points in the paragraph "Improvement upon Daskalakis et al., (2021)" in Section 6, and also in Section E.

Extension to Different OFTRL Algorithms

We believe the similar proof strategy can apply to different OFTRL instances. In fact, the regularizer of OFTRL determines two concrete parts of our argument. In the recurrence map F, we can simply replace softmax with the strategy that minimizes the cumulative loss (including the prediction term), and the regularization. For a separable regularizer R(x)=∑ar(xa)R(x) = \sum_a r(x_a) with positive curvature and an interior solution, the loss gap between actions aa and bb is weighted by watwbt/∑cwct\sqrt{w_a^tw_b^t/\sum_c w_c^t}, where wat=1/r’’(xat)w_a^t = 1/r’’(x_a^t). Entropic regularization yields wat=xatw_a^t = x_a^t, which recovers our original hith_i^t. The key question for different regularizers would be whether their corresponding recurrence maps would admit sharp high-order derivative bounds.

Q. Possibility for a Constant Regret

Recent work from Ha, arXiv 2026. “A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games” showed that a horizon-independent On,d(1)O_{n,d}(1) regret bound is indeed achievable for Optimistic Hedge based on similar recurrence-map reduction argument. However, their proof relies on a nonconstructive argument for obtaining an exact finite difference relation Δkhit=∑m<kcm⋅Δmhit\Delta^k h_i^t = \sum_{m<k} c_m \cdot \Delta^m h_i^t, and leave the dependence on game dimensions (n,d)(n, d) implicit. We believe the key technical challenge in obtaining a dimension-explicit constant regret lies designing a constructive argument for obtaining the relation Δkhit=∑m<kcm⋅Δmhit\Delta^k h_i^t = \sum_{m<k} c_m \cdot \Delta^m h_i^t up to a very small error. At this point, however, we do not see a clear path to such a relation.

Reviewer_eWCcOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper improves the individual regret bound for Optimistic Hedge, a fundamental algorithm in online learning and games, from O(nlog⁡dlog⁡4T)O(n \log d \log^4 T) (Daskalakis et al., 2021) to O(nlog⁡dlog⁡T)O(\sqrt{n}\log d \log T). It seems that the improvement comes from a tighter analysis of the smoothness of higher-order differences of loss sequences generated by self-play.

Critical strengths

This result is mathematically substantial, and very interesting since the faster O(log⁡T)O(\log T) is already achieved by Optimistic Hedge.

Critical weaknesses

The current quality of the write-up is a serious concern for me. I think the result is strong, but many parts of the paper need a major revision.

For example, even in the abstract, the main proof ideas are described using phrases such as "factorial bounds on high-order differences of probability-weighted pairwise loss gaps" and "finite-difference interpolation in a fixed Euclidean norm." What do these mean? How is the reader supposed to understand the new proof ideas from such descriptions? The introduction is also not very helpful for the broader ICLR audience, and many parts could be misleading. The same issue appears in the main text. For example, what does "A sup-norm bound, however, discard ... " in Line 226 mean? or what about "the squared norm ... already equals the stability variance"? what is a stability variance? Do you mean Varxit(ℓit−ℓit−1)Var_{x_i^t} (\ell_i^t - \ell_i^{t -1})? I can go on ...

I strongly suggest that the authors rewrite the paper with a clearer picture of what they want to communicate. This is a strong mathematical result, and it deserves a much better exposition. I am willing to reconsider if the write-up is improved substantially.

Questions for authors
  • Can you elaborate more directly and in a concise way what is the main mathematical novelty? How the analysis got improved compared to (Daskalakis et al., 2021)? In particular, I wonder what led to improved n\sqrt{n} rate?

  • How does this result compares to more recent work? I understand that these works are recent, but a comparison may be worth it: arXiv:2609.22839, arXiv:2609.21976, arXiv:2609.16751.

  • Could the authors provide some intuition as to whether they believe the rate O(nlog⁡T)O(\sqrt{n} \log T) is tight for Optimistic Hedge?

2 comments
AuthorsOpenReview ↗

Improved the overall quality of presentation in the updated manuscript

We deeply thank Reviewer eWCc for helpful and constructive feedback.

Quality of Presentation

We acknowledge that the overall quality of the initial write-up had a lot of room for improvement. In the updated manuscript, we improved the overall writing across the entire main paragraphs, and reflected the reviewer’s comments regarding unclear phrases, ambiguous terminologies, and (unnecessarily) complicated explanations of our analysis.

Abstract

We replaced ambiguous, unclear description of our analysis with more precise language as:

... Instead of directly analyzing the loss sequence ℓit\ell_i^t, we analyze a different sequence hith_i^t that represents Optimistic Hedge and admits a sharper smoothness estimate. Then, we transfer that estimate back to the original loss. The sharp estimate of the high-order difference Δkhit\Delta^kh_i^t and a direct comparison between Δkhit\Delta^kh_i^t and Δhit\Delta h_i^t together circumvents the induction arguments in Daskalakis et al., 21’, and yield the improved logarithmic regret upper bound.

Section 1

We expanded the introduction to motivate the broader audience of ICLR. The introduction now includes examples of practical games whose equilibrium enjoys favorable provable guarantees (e.g., GANs match data distribution at a Nash equilibrium, and NLHF produces robust policy against competing opponents in language-model alignment)

Section 2

At the end of the paragraph “The high-order smoothness framework” we clarify that while our analysis builds upon the smoothness framework of Daskalakis et al., 21’, our recurrence-map reduction itself is novel and could be of an independent interest for future regret analysis in games.

Section 4

  • We removed unclear, confusing phrases like “The usual entropy bound”, “a sufficiently large multiple of … keeps the remainder bounded …”, and replaced them with more precise and simple words.
  • We added Ha, arXiv 2026. “A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games” and Soleymani & Piliouras, arXiv 2026. “Multiplicative Optimism for Constant Regret in Games” to Table 1, and added paragraphs that compares them with our result.

Section 5

Overall, we removed all the confusing phrases, ambiguous terminologies, and unnecessarily complicated explanations of proofs. We also expanded some of the key paragraphs that explain the intuition behind our analysis.

  • (Intro) We added a brief summary of a high-level picture of our analysis.
  • (Section 5.1) We replaced ambiguous phrases like “... bound the prediction-error variance sum by half the stability variance sum …” with more precise ones, such as “... bound the prediction error Varxit(ℓit−ℓit−1)Var_{x_i^t}(\ell_i^t-\ell_i^{t-1}) by the stability Varxit(ℓit)Var_{x_i^t}(\ell_i^t) …”
  • (Section 5.3) We expanded the paragraph “Centered-logit recurrence” and added a short text that explains the motivation behind the recurrence map representation.
  • (Section 5.4) We removed confusing explanations of technical proofs behind Lemma 5.8, and simplified the paragraph that explains its implication.

We’d greatly appreciate it if the reviewer could reevaluate the updated manuscript based on the above improvements.

Q. Mathematical Novelty & What Led to Improved Rates

Our mathematical novelty lies in our approach that (1) reformulates Optimistic Hedge as a recurrence of centered-logits zitz_i^t and weighted loss gaps hith_i^t, which admit sharper high-order estimates (through Lemma 5.6 -> Lemma 5.7 -> Lemma 5.8 -> Lemma 5.5), and (2) transfers this smoothness guarantee back to the original loss sequence (Lemma 5.2).

The improvement on the number of players from nn to n\sqrt{n} comes from the sharper high-order derivative estimate in Lemma 5.6. The particular softmax form of Optimistic Hedge update rule is the key ingredient: the softmax operator inside the map FiF_i allows us to invoke the joint-cumulant upper bound (Lemma C.6), and improves the dependence on the number of players from nn to n\sqrt{n}.

The improvement on the logarithmic factor from log4Tlog^4T to logTlogT, on the other hand, comes from the choice of sequence hith_i^t. Daskalakis et al., 21’ controls Varxit(ℓit−ℓit−1)Var_{x_i^t}(\ell_i^t-\ell_i^{t-1}) by directly analyzing the high-order difference of loss sequence ℓit\ell_i^t. As the underlying probability xitx_i^t of the variance Varxit(⋅)Var_{x_i^t}(\cdot) changes with time, they rely on inductive arguments to transfer the estimates of Δkℓit\Delta^k \ell_i^t to Varxit(ℓit−ℓit−1)Var_{x_i^t}(\ell_i^t-\ell_i^{t-1}), and this produces the polylogarithmic factor log4Tlog^4T. In contrast, our choice of hith_i^t instead admits a time-invariant norm ∣∣⋅∣∣||\cdot||, which allows us to directly transfer the high-order difference estimate Δkhit\Delta^k h_i^t to the first difference Δhit\Delta h_i^t through the finite-difference interpolation based on the Parseval’s identity (Lemma 5.4).

We also emphasize that our initial draft summarizes the key differences from Daskalakis et al., 21’ in Appendix E.

In short, the improvement stems from (a) a sharper high-order estimate (Lemma C.6 -> Lemma 5.3) and (b) the choice of sequence hith_i^t that admits a finite-difference relation (Lemma 5.4) that avoids inductive arguments in Daskalakis et al., 21’.

Q. Comparison with Recent Work

Our O(logT)O(logT) upper bound and the horizon-independent On,d(1)O_{n,d}(1) upper bound from Ha, arXiv 2026 “A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games” are complementary to each other: Ha, 26’ leaves the dependence on the game dimension (n,d) implicit, and our result provides an explicit dependency on game dimensions (n,d).

MORM achieves state-of-the-art regret upper bound, but unlike Optimistic Hedge, it is unclear whether MORM can have an efficient kernelized implementation for extensive-form games as in Farina et al., ICML 2022. “Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games”.

We added the above discussion to Section 4 in the updated manuscript.

Q. Tightness of the Result

Ha, (2026) recently showed that Optimistic Hedge can attain a horizon-independent regret in general-sum games, so the logarithmic horizon dependence is not tight. If we fix the horizon dependence at O(logT), the logarithmic dependence on the number of actions dd arises from the standard RVU inequality for Optimistic Hedge, and therefore, we believe log d would be actually tight. For the number of player nn, the square-root dependency arises from merging player-wise high-order derivative upper bounds (25) in Lemma 5.6, so we suspect n\sqrt{n} could be actually tight as well. However, we do not have a clear proof for the both dependencies.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.