Game players learn with constant regret using multiplicative optimism
Multiplicative Optimism for Constant Regret in Games
Computer Science and Game TheoryMachine Learning
Summary
When multiple players interact in a game, they want to learn strategies that minimize mistakes compared to the best fixed choice over time. The authors introduce a new learning rule called Multiplicatively Optimistic Regret Matching that helps players quickly reduce regret in such games. This method achieves very low regret even over long periods, and also works when opposed by challenging or unpredictable opponents. Their approach mixes clever prediction steps with controls on how strategies change over time.
What this means in practice
- •For game developers: Improve AI agents in multi-player games to quickly adapt strategies with minimal regret during gameplay.
- •For algorithmic trading teams: Design trading algorithms that adjust strategies dynamically in competitive markets with uncertain outcomes to reduce cumulative loss.
Authors
Ashkan Soleymani, Georgios Piliouras
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.