acceptodds
Under review as a conference paper at ICLR 2027

Constant Individual Regret in General Games

Abstract

Uncoupled no-regret dynamics provide a decentralized route to equilibrium. We study horizon-independent individual regret in finite -player normal-form games under full-information feedback. We show that standard Optimistic Hedge has worst-case regret at least exponential in either the number of players or the largest action-set size . This motivates ECHO-OFTRL: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. Simultaneously, for every horizon , each player in self-play incurs regret upper bounded by . With a regret-dependent learning rate, it also guarantees regret bounded by the self-play bound plus in the adversarial setting. More generally, we relate the regret bound to the order of the prediction-error filter's zero at one.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Online Learning, Optimism, Game Theory

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_oqLMOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies external regret in finite multiplayer games undder exact full information feedback. it proves that standard optimistic hedge with uniform initialization and a common fixed learning rate has worst case regret expoential in either the number of players or the number of actions. It also introduces ECHO-OFTRL. This combines lifted regularization with an EMA cascade for high order prediction, and proves O(N log m_max) individual regret on self play. Then it gives a regret dependent learning rate which addtionally provides adversarial regret of O(N log m_max + \sqrt(T log m_max)

Critical strengths
  1. the paper quantifies previously implicit game size dependence, proving expoential worst case regret.
  2. There is a methodological contribution beyond a single constant regret algorithm as the paper combines lifted regret with prediction error filter and provides an EMA construction which relevant norms remain controlled even when the number of player increases.
Critical weaknesses

The main comparison understates directly relevant concurrent results. Appendix A acknowledges Soleymani and Piliouras's complexity. O(\sqrt(N) log m_max). but table 1 exclude it. Their method also offers a closed form update, adversarial robustness, and O(m_i) update time and memory, compare with ECHO's O(N m_i). This reduces the significance of ECHO's algorithm guarantee and makes its contribution harder to assess. The main presentation should explicitly foreground the lower bounds and general filter framework.

Questions for authors

Under matching feedback and public knowledge assumptions, what additional guarantee or capability does ECHO provide relative to the multiplicative optimism method discussed in appendix A? Please clarify the distinction and incorporate that method into the main comparison table.

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

This paper studies individual regret guarantees for uncoupled learning dynamics in general-sum games. One prevailing open question in this area has been whether there exist algorithms that can obtain individual regret bounds that are constant with respect to the time horizon T. The paper's main contributions are two-fold: first, the authors show a lower bound proving that there are games in which the individual regret of some player using the canonical Optimistic Hedge/MWU algorithm with a fixed constant learning rate is at least exponential in either the total number of players N or the size of the player's action set m. Thus, for this canonical method, a constant regret bound in T necessarily comes at the expense of exponential dependencies in these game dimensions.

Second, the authors introduce and analyze a new optimistic FTRL variant called ECHO-OFTRL, which is based on some notion of higher-order optimism. For ECHO-OFTRL, the authors obtain individual regret bounds scaling like O(N log m), meaning constant with respect to the time horizon T, linear in the number of players N, and logarithmic in the action size. The result holds under a common learning rate that is constant with respect to the time horizon.

Critical strengths

In my opinion, the most significant result of the paper is the individual regret lower bound for Optimistic Hedge/MWU.

To put this result into context, within the learning in games subfield, there has been a handful of papers in the past several months (e.g., in August and early September 2027) that either (a) introduce new variants of Optimistic FTRL or Optimistic MWU/Hedge that obtain constant (wrt T) individual regret bounds or (b) obtain tighter analyses of the canonical Optimistic MWU algorithm leading to improved individual regret guarantees. In particular, for the latter, Ha recently released a preprint (2026a) showing a constant individual regret guarantee for Optimistic MWU in general-sum games (and in particular, this improved over the slightly older preprint of Ha, 2026b, that showed a log T individual regret bound for Optimistic MWU).

However, the lower bound results of the present paper show that, for this "vanilla" Optimistic Hedge/MWU variant, constant individual regret wrt T must come at the expense of an exponential dependence on the number of players or the size of the action sets. I believe this is a useful result for the field that establishes a limit on the effectiveness of the vanilla Optimistic Hedge/MWU variant without using some notion of higher-order optimism.

The constant individual regret upper bound for ECHO-OFTRL that has only linear dependence on N is also a strength of the paper, although the intuition for this result is lacking (see weaknesses).

Ha, 2026a, A horizon-independent regret bound for Optimistic Hedge in general-sum games.

Ha, 2026b, A logarithmic regret bound for Optimistic Hedge in general-sum games.

Critical weaknesses

In my opinion, the main weakness of the paper is in its writing. In my reading, the main body of the paper seems hastily written, and it is subsequently very difficult to get any high-level intuition for why ECHO-OFTRL yields the improved individual regret bound. In particular, I believe Section 4 is lacking in intuition in explaining how and why the higher-order optimism of the algorithm lead to the new bound. Thus, while I do believe the individual regret guarantee is significant, the presentation of Sections 4 and 5 make the main technical ideas difficult to follow.

Questions for authors
  1. Could the authors discuss whether the lower bounds of Theorem 3.1 and Theorem 3.2 break if the stepsize \eta can be time-varying or time-horizon dependent?
Reviewer_MtkAOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the authors study the individual regret in finite N-player normal-form games under full-information feedback where each player employs uncoupled no-regret learning dynamics. There are several existing works on the same or similar problems, developing a line of improved technical tools and regret bounds, but all the previous results (ignoring the concurrent works) requires dependency on the horizon TT. Therefore, in this paper, the authors aim to study horizon-independent individual regret in that setting.

In this paper, the authors first establishes a lower bound that, under Optimistic Hedge, the individual regret must exponentially depends on either number of players NN or the largest action-set size mmaxm_{max}. Then, the authors propose their no-regret algorithm ECHO-OFTRL that improves the dependence on NN to linear and on mmaxm_{max} to logarithmic. Moreover, they provide a unified perspective on how higher-order optimism can progressively improve the horizon dependence of regret.

Critical strengths
  • The problem itself is well-motivated and scientifically interesting: it is a natural follow-up research direction after the previous works on no-regret learning in N-player normal form game. Moreover, the paper establishes horizon-independent individual external regret of O(Nlog⁡mmax⁡)O(N\log m_{\max}) for general finite normal-form games, which is a strong theoretical improvement compared to previous related works, though slightly dominated by the concurrent work of Soleymani&Piliouras(2026)). The novel lower bound for Optimistic Hedge, the newly designed regularizer for ψi\psi_i, and most importantly, the general prediction-error filter analysis, provide interesting technical contributions.
  • I wasn't be able to finish reading all the proofs in the appendix, but for the parts that I read, the math is sound and solid.
Critical weaknesses

My main concerns are:

  • Novelty relative to previous and concurrent work could be better clarified. From my understanding, the paper builds on established techniques like nonnegative-regret lifting and higher-order optimism, and it shares substantial conceptual similarities with concurrent work (e.g., Abbadi et al., 2026). I believe this paper has its own technical contribution (e.g., the specially designed regularizer, the general prediction-error filter analysis), but when I first read the paper, they are mixed with the definition of existing algorithm, the proposed algorithm, theoretical results and proofs, and I don't have a clear idea of which techniques are genuinely new and how they improve upon previous approaches.

  • The presentation, especially for the intuition and motivation behind your technical contribution, can be improved. The current flow of Section 4 just introduces the ECHO-OFTRL algorithm by enumerating its components. It is technical sound, but several important algorithmic choices, especially the specially designed lifted regularizer and the EMA prediction-error filter, are introduced without sufficient intuition. For example, when I first read about the regularizer, it appears rather intricate and counterintuitive, but the paper does not clearly explain which limitations of previous regularizers motivate its construction or which geometric properties are essential to the improved regret bound. The lifted regret idea is also not well-explained, but it is rather simple. Then, in Section 4.2, the authors define the shift operators, prediction-error filter, and EMA cascade largely through mathematical definitions and algebraic identities, without first explaining the design objectives or why this particular filter is preferable to simpler high-order predictors. I feel this make the technical contribution of the paper harder to follow, and if the authors can provide some high-level explanations of the key design principles, it should largely improve the readability of the paper.

Questions for authors
  • Are there any specific reasons that motivates the construction of the regularizer ψi\psi_i in Section 4? Could the authors compare it against other regularizers (e.g., lifted entropy or logarithmic regularization) used in the literature?

  • Could the authors elaborate on the design principles behind the particular prediction-error filter in Section 4.2? Specifically, what motivates the choice F(z)=(1−z)δ(z)N−1F(z)=(1-z)\delta(z)^{N-1} and ρ=1−1/N\rho=1-1/N, and what advantages does this construction offer over alternative discounted high-order predictors, such as those used in Abbadi et al. (2026)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.