acceptodds
Under review as a conference paper at ICLR 2027

A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games

Abstract

Can simple learning rules keep their regret bounded in self-play? Recent work achieves constant regret bounds through modified regularization and higher-order prediction. Yet for Optimistic Hedge, arguably the most canonical method in games, the best known individual regret bound remains logarithmic. In this work, we prove that plain Optimistic Hedge with a constant step size can attain individual regret in general-sum games with players and actions, under expected loss-vector feedback. As a corollary, its time-averaged play enjoys an coarse correlated equilibrium (CCE) gap. Our analysis represents Optimistic Hedge as a real-analytic recurrence on a compact space, which yields an exact finite-order difference relation that eliminates horizon dependence. Our proof hinges on nonconstructive Noetherianity argument of Frisch (1967), so the -dependence remains implicit.

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

Reviews

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

The paper establishes the existence of a fixed step size for which the Optimistic Hedge algorithm achieves a horizon-independent regret bound in all finite games of given dimensions. The proof is non-constructive and relies on tools from real analytic geometry, and, as a result, both the step size and the regret bound remain implicit, and their dependence on the number of players and actions is unknown.

Critical strengths

The paper’s main strength lies in its result and its connection with distant tools from real analytic geometry, which, despite being non-constructive, remain of some interest.

Critical weaknesses

First, I have some reservations about the value of the result from a machine learning and computational viewpoint. The step size for which Optimistic Hedge achieves constant regret as well as the resulting bound are left implicit and are not computable from the analysis, and their existence relies on general and rather exotic non-constructive tools from real analytic geometry, notably the Noetherianity of rings of analytic germs. As a consequence, even from a theoretical standpoint, I believe the result does not meaningfully achieve the aim of establishing a constant regret bound for this algorithm, as an important motivation for such a result would be to provide new computational or algorithmic insights and explicit bounds that other researchers in the field or practitioners could build upon. This should be contrasted with the paper by Daskalakis, Fishelson & Golowich, "Near-Optimal No-Regret Learning in General Games," which establishes an explicit polylogarithmic regret bound for Optimistic Hedge and introduces new and insightful computational tools for proving such bounds, notably their higher-order smoothness framework, which the present paper also makes use of.

Second, I found the proofs quite difficult to follow, and I believe the exposition could be substantially improved. Indeed, the tools introduced are from highly specialized subareas of pure mathematics and clearly unfamiliar to researchers in learning in games and likely to all of the machine learning community, and despite this, they receive only minimal explanation. For this reason also, I believe the paper, if well rewritten, would be better suited to a mathematical game theory or theoretical computer science conference or journal. It is also unclear how specific the argument is to Optimistic Hedge given the generality of the tools used, in that the new part of the analysis appears to rely on the analyticity of the update map while the Hedge-specific ingredients are imported from prior work, often again with minimal and terse exposition. This reinforces my view that the paper in its current form is not clear enough and does not help clarify our understanding of the Optimistic Hedge algorithm, or more generally of learning in games.

Questions for authors
  1. What part of the argument are specific to Optimistic Hedge in the proof, and what parts would generalize to other algorithms ?
  2. How is the finite game structure specifically used here ? Can one obtain at least an order of magnitude for the regret bound ?
  3. Lemmas C.8 and C.9 rely on results stated for complex analytic settings. How exactly do these transfer to the real analytic setting used here, and where is semianalyticity essential ? Could the proof be made more simple and natural by using specific tools tailored to this algorithm and games rather than very general, non-constructive tools ?
  4. What is the practical purpose of such a result ? Even from a theoretical standpoint, does this algorithm help us better understand the behaviour of Optimistic Hedge for a given fixed, explicit step size ?
Reviewer_9bnZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates individual regret when all players use optimistic Hedge in multiplayer general-sum games. The authors show that, using optimistic Hedge with a sufficiently small constant learning rate, each player can achieve a horizon-independent regret bound (although the dependence on the number of players and actions is not made explicit). Existing algorithms that achieve constant external regret require solving an optimization problem at each step, whereas optimistic Hedge selects strategies in closed form and therefore does not require such optimization. In the proof, the authors first reduce the regret analysis to bounding the differences in losses between each player's actions and the changes in these differences. They then show that differences of sufficiently high order can be expressed exactly as combinations of lower-order differences. This allows them to bound the changes in the loss differences over time sufficiently tightly so that the positive terms in the regret bound are canceled by the negative terms of RVU bounds, as in standard analyses of optimistic Hedge in two-player zero-sum games.

Critical strengths

The main strength of this paper is that it shows that the standard optimistic Hedge algorithm achieves horizon-independent individual regret in general-sum games. This is an important result that provides a new theoretical insight into a well-known existing algorithm. In particular, it is interesting that constant regret can be achieved without introducing higher-order predictions or complex regularizers.

Critical weaknesses

The main weakness of this paper is its lack of clarity. Throughout the paper, there are many expressions that are difficult to understand without additional context. Since there are also many other unclear or ambiguous expressions, I think the paper needs careful proofreading. In Sections 5.2 and 5.3, the authors introduce several auxiliary functions and higher-order differences, but it is not well explained why they are needed and how they are used to obtain the final regret bound.

Relatedly, Sections 5.3, 5.4, and Appendices C.3 and C.4 use advanced mathematical tools that may be unfamiliar to researchers in the learning in games community. However, the paper does not sufficiently explain why these tools are needed or how they are used. The use of advanced mathematical tools is not an issue in itself, but the paper should provide enough explanation for readers to understand the main ideas of the proofs and verify their correctness. The main text contains little explanation, and too much information is left to the appendix. I also suspect that some of the mathematical tools are more general than necessary. I would encourage the authors to consider whether similar results can be obtained using simpler tools, or at least whether the proofs can be presented more simply. The paper introduces many mathematical constructions and technical concepts without sufficiently explaining their purpose or role in the proofs. I think the paper needs substantial improvements to its explanations and organization.

The second major weakness is that the quantitative guarantees of the main result are not explicit, and its advantages over existing work are not sufficiently clear. Although Theorem 4.1 guarantees horizon-independent regret, the dependence on the number of players and actions is not specified. Furthermore, the authors only prove the existence of a sufficiently small upper bound on the learning rate, without providing a concrete choice of learning rate. This makes it difficult to evaluate the quantitative significance and practical relevance of the result.

In comparing their work with Liu et al. (2026) and Abbadi et al. (2026), which also achieve constant external regret, it is emphasized that their algorithm uses closed-form updates and does not require solving an optimization problem or performing root-finding at every round. While this is an advantage, I do not think it is particularly strong. In particular, the existing studies provide explicit regret bounds and learning rates, whereas the present paper does not.

Questions for authors

none

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

The paper gives horizon-independent and constsnt individual regret for Optimistic Hedge in finite general-sum games, with On,d(1/T)O_{n,d}(1/T) convergence rate to coarse correlated equilibrium.

Critical strengths

Very nicely written paper and very interesting result! The result definitely improves our theoretical understanding of the optimisitic hedge.. The use of Noetherianity to eliminate the horizon-dependent remainder is also very interesting and may have implications beyond the scope of this paper.

Critical weaknesses

I don't find any critical weakness of this paper as I support acceptance. There are a few minor typos that I listed below.

Questions for authors
  1. Abstract, lines 20–21: “hinges on nonconstructive Noetherianity argument” , to “hinges on a nonconstructive Noetherianity argument.”
  2. Mixed usage of author'' and authors''

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.