Multiplicative Optimism for Constant Regret in Games
Multiplicatively Optimistic Regret Matching gives near-constant external regret in general-sum games under self-play.
The paper introduces Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games. In simultaneous full-information self-play, each player's external regret is O(sqrt(n) log d) uniformly over all horizons, using only one-step optimism. The proof combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement. A learning-rate safeguard yields O(sqrt(T log d)) regret against adversarial utilities.
- MORM is an uncoupled learning rule for finite general-sum games.
- Self-play external regret is O(sqrt(n) log d) for every horizon.
- Analysis uses regret matching, multiplicative stability, and Hellinger control.
- A safeguard restores O(sqrt(T log d)) regret versus adversarial utilities.
Full article65 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.21976