PreprintCC BY 4.0arXiv
Multiplicative Optimism for Constant Regret in Games
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(√nlog 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(√(Tlog d)) regret in the face of adversarial utilities.
Related
- The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Near-Optimal √K-Regret for Online Learning in Uninformed Markov Games
- Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
- Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes
BibTeX
@misc{soleymani2026multiplicative,
title = {{Multiplicative Optimism for Constant Regret in Games}},
author = {Ashkan Soleymani and Georgios Piliouras},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21976},
eprint = {2609.21976},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21976},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Multiplicative Optimism for Constant Regret in Games
AU - Ashkan Soleymani
AU - Georgios Piliouras
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21976
UR - https://arxiv.org/abs/2609.21976
AB - 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(√nlog 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(√(Tlog d)) regret in the face of adversarial utilities.
ER -