Multiplicative Optimism for Constant Regret in Games
Ashkan Soleymani, Georgios Piliouras
cs.GT · cs.LG · math.OC
Quick verdict
Proposes MORM: one-step optimism gives constant O(√n log d) regret in general-sum self-play; proof appears sound; no experiments, large constants.
Summary
The paper introduces MORM (Multiplicatively Optimistic Regret Matching), a deterministic uncoupled learning rule for finite n-player general-sum games. Under simultaneous full-information self-play with exact expected-utility observations, every player's external regret is bounded by 96√n(2+log d) uniformly over all horizons — constant in T — using a fixed learning rate η=1/(32√n) and one-step optimism: the previous round's centered utility enters the update multiplicatively as 1+4ηu. The proof rests on a custom potential: an ℓ-order-(2+log d) aggregation of a piecewise scalar function whose reciprocal negative branch makes gradient weights multiplicatively stable, so curvature is controlled by gradient weights; combined with squared-Hellinger control of strategy movement this yields a potential-level RVU inequality whose negative movement terms absorb prediction errors, giving √n rather than n player dependence. A learning-rate-only safeguard extends the guarantee to arbitrary adaptive adversarial utilities at O(√T log d) and is proven inactive under self-play (Proposition E.2). Time-averaged play is an O(√n log d/T)-coarse correlated equilibrium. Compared with concurrent constant-regret algorithms (ECHO-OFTRL: n^21 log^4 d; HOOD: n^3 log^2 d), MORM has far smaller parameter dependence and O(d) per-iteration cost. Limitations: purely theoretical with no experiments; requires exact full-information feedback; only external regret and time-average CCE (no last-iterate guarantee); optimality of the √n dependence remains open.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under simultaneous full-information self-play in any fixed n-player finite general-sum game, MORM gives every player external regret ≤ 96√n(2+log d) for every horizon T, with fixed rate η = 1/(32√n) and no horizon knowledge (Theorem 4.10).
- This is, to the authors' knowledge, the first uncoupled algorithm in this setting with O(√n log d) individual regret, improving on concurrent constant-regret methods ECHO-OFTRL (n^21 log^4 d) and HOOD (n^3 log^2 d) in both n and d dependence while using only one-step optimism.
- A learning-rate-only safeguard yields regret ≤ 96√n(2+log d) + 21√(T(2+log d)) against arbitrary adaptive adversarial utilities while provably leaving the self-play trajectory bit-for-bit unchanged (Theorem E.1, Proposition E.2).
- Time-averaged play is a 96√n(2+log d)/T-coarse correlated equilibrium, so ε-CCE is reached in O(√n log d/ε) rounds (Corollary 2.5).
Strengths
Quantitative advance over all prior fast self-play results
Table 1 places MORM at O(√n log d) constant-in-T regret versus T^{1/4} (Syrgkanis et al. 2015), n log d log^4 T (Daskalakis et al. 2021), n log^2 d log T (Cautious Optimism 2025), and the concurrent constant-regret results ECHO-OFTRL (n^21 log^4 d) and HOOD (n^3 log^2 d) — simultaneously improving n, d, T dependence with one-step optimism and O(d) iteration cost.
Auditable, constant-explicit proof chain
The end-to-end algebra is checkable from the text: nη² = 1/1024, absorption coefficient 1/4 − 50nη² = 103/512 > 1/5 (Section 3.5), path length ≤ 16nc, terminal potential 61c/16 < 4c, and regret 3c/η = 96√n(2+log d); the potential-level RVU inequality (3.11) with coefficient 10η² reproduces exactly from Lemmas 4.4 and 4.6.
Clean mechanism isolating why √n (not n) is achievable
Adversarial safeguard with trajectory preservation
Rigorous handling of non-smooth points
Weaknesses
No empirical evaluation at all
Feedback model outruns the motivation
Only external regret and time-average CCE
Open optimality and no lower bounds
Priority positioning in a crowded concurrent landscape
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies uncoupled no-regret learning in fixed finite n-player general-sum games with utilities in [0,1] and at most d actions per player, under simultaneous play and exact full-information observation of each player's expected-utility vector (eq. 2.1). The central claim (Theorems 2.4 and 4.10) is that MORM — regret matching with a custom potential plus a one-step multiplicative optimistic correction 1+4ηu^(t−1) — gives every player external regret ≤ 96√n(2+log d) for every horizon T, with fixed rate η = 1/(32√n) and c = 2+log d. Secondary claims: an ε-CCE guarantee for time-averaged play at rate 96√n(2+log d)/T (Corollary 2.5), and an adversarial extension via a learning-rate-only safeguard achieving 96√n(2+log d) + 21√(T(2+log d)) against arbitrary adaptive utilities (Theorem E.1), provably inert in self-play (Proposition E.2). The paper is explicit that constant regret per se was first achieved by concurrent high-order-optimism algorithms (ECHO-OFTRL, HOOD); its contribution is the parameter dependence (√n log d versus n^21 log^4 d and n^3 log^2 d per Table 1), one-step optimism, and O(d) iteration cost.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What does constant regret in games mean in this paper?
Each player's cumulative external regret — the gap between its cumulative utility and that of the best fixed action in hindsight — stays bounded by 96√n(2+log d) no matter how many rounds the players keep learning with MORM in the same finite general-sum game. As a consequence, the time-averaged play converges to a coarse correlated equilibrium at rate O(√n log d/T), so roughly O(√n log d/ε) rounds reach equilibrium error ε.
Is this the first algorithm to achieve constant regret in general games?
No. Two concurrent 2026 works — ECHO-OFTRL (Liu, Farina, Ozdaglar) and HOOD (Abbadi, Laraki, Mertikopoulos) — first established horizon-independent individual regret, but with high-order optimism and large player dependence (n^21 log^4 d and n^3 log^2 d respectively). This paper's contribution is a much simpler one-step optimistic rule, MORM, with substantially smaller dependence (√n log d) and O(d) cost per iteration.
How is MORM different from Optimistic Hedge (OMWU)?
Optimistic Hedge multiplies exponential weights by an exponential of the last observed utility. MORM instead uses regret-matching-style power weights coming from a custom potential, and multiplies them by a linear correction (1 + 4η times the last centered utility). The potential is engineered so its curvature is controlled by its own gradient weights, which is what makes the constant-regret proof work; Remark 2.1 shows the same multiplicative-correction idea under entropy recovers an OMWU-like variant.
Does the algorithm need to know the number of rounds or the other players' payoffs?
It needs the public parameters n (number of players) and d (max actions per player) only through the fixed learning rate 1/(32√n) and scale 2+log d; the horizon T is never needed. It is uncoupled: each player uses only its own past utility observations. Against adversarial (non-self-play) utilities, an optional safeguard automatically shrinks only the learning rate.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Text extraction omitted portions of Section 3.3, the statements of Proposition 4.7 and Lemma 4.8, the end of Appendix D, and part of Appendix A; the visible tails of these proofs are consistent with the derivations quoted in the overview, but those statements could not be read verbatim.
- Table 1 superscripts were flattened by extraction (e.g., n21 log4 d read as n^21 log^4 d); the concurrent papers' bounds were not verifiable against their own texts.
- No figures beyond Table 1; none appear load-bearing.
- arXiv v1 (Sep 2026); concurrent-work comparisons reflect v1 numbers.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.