- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper establishes an individual regret bound for Optimistic Hedge in general-sum games, improving the previous 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
-
The paper significantly improves the regret bound for the original Optimistic Hedge algorithm without modifying its update rule.
-
The weighted-gap representation and factorial high-order difference bounds are technically interesting and may be useful beyond this setting.
-
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 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?
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). However, their explicit dependence on the game dimensions (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) regret lower bound. Whether a matching O(exp(nd)) upper bound can be formally established remains an open question.