Multiplicative Optimism for Constant Regret in Games

Ashkan Soleymani; Georgios Piliouras

cs.GTSep 18, 2026

Multiplicative Optimism for Constant Regret in Games

Authors: Ashkan Soleymani, Georgios Piliouras

Organizations: MIT · Google Deepmind

Abstract

We introduce Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games. Under simultaneous full-information self-play, every player achieves external regret $O(\sqrt n\log d)$ uniformly over all horizons, using only one-step optimism. The analysis combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement. A learning-rate safeguard additionally gives $O(\sqrt{T\log d})$ regret in the face of adversarial utilities.

Figures & tables

Method	Regret in Games	Iteration Cost	Adversarial Regret	Optimism Order
Hedge
( Cesa-Bianchi and Lugosi, 2006 )	$\mathcal{O}(\sqrt{T\log d})$	$\mathcal{O}(d)$	$\mathcal{O}(\sqrt{T\log d})$	$0$
Optimistic FTRL / OMD
( Syrgkanis et al., 2015 )	$\mathcal{O}(\sqrt{n}\log d\,T^{1/4})$	Reg. dep.	$\mathcal{O}(\sqrt{T\log d})$	$1$
Optimistic Hedge
( Chen and Peng, 2020 )	$\mathcal{O}(n\log^{5/6}d\,T^{1/6})^{\dagger}$	$\mathcal{O}(d)$	$\mathcal{O}(\sqrt{T\log d})$	$1$

Table 1: Comparison of no-regret learning algorithms in finite general-sum games. Here

n

is the number of players,

T

the number of rounds, and

d

the maximum number of actions. Universal constants are suppressed. Computational cost is the per-player cost of one learning update after the utility vector is available and does not include the cost of computing that vector. Optimism order

0

denotes a non-optimistic method, while order

1

uses one-step prediction.

\dagger

applies only to two-player games.

\ddagger

Clairvoyant MWU gives the stated bound only on a selected subsequence of iterates.

\lx@sectionsign

The adversarial guarantee for Multiplicatively Optimistic Regret Matching ( MORM ) uses the learning-rate safeguard in Appendix E , which leaves the self-play run unchanged.

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 110 papers

A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
Sep 19, 2026Junsoo HaGame Theory Regret Minimization
Constant regret in general games via higher-order optimism
Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosFollow-the-Regularized-Leader Regret Minimization
Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism
Sep 15, 2026Tung MaiGame Theory Swap Regret
Adobe Research

Sep 19, 2026J/K move · Enter open · S save

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

Junsoo Ha

Game Theory Regret Minimization

Open paper AskPDF arXiv

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

O_{n,d}(1)

individual regret in general-sum games with

n

players and

d=(d_1,\ldots,d_n)

actions, under expected loss-vector feedback. As a corollary, its time-averaged play enjoys an

O_{n,d}(1/T)

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

(n,d)

-dependence remains implicit.

Abstract

Regret Minimization

Explore similar work

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

Constant regret in general games via higher-order optimism

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism