Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.16751 · 2 citations · 26 references
Computer Science

Abstract

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon $T$. With $n$ players and at most $m$ actions each, every player's individual swap regret is $O(\sqrt n\,m\log m\log^{5/2}(nm))$ at every finite horizon. The dynamics use the classical Blum-Mansour framework with optimism. Each player predicts the deviation gains, uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. Our new ingredients include a tailored row normalization map and a two-scale higher-order predictor. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most $7\sqrt{mT\log m}$ in the adversarial setting.

View source

Similar papers

Sep 2026

A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games

Optimistic Hedge with a constant step size can further achieve individual external regret under expected loss-vector feedback and proves factorial bounds on high-order differences of probability-weighted pairwise loss gaps, then applies finite-difference interpolation in a fixed Euclidean norm.

Junsoo Ha · 2 citations

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t...

Yu-Heng Zhang · 1 citation
#machine learning Preprint Sep 2026

Multiplicative Optimism for Constant Regret in Games

This work introduces Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games that combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement.

Ashkan Soleymani, Georgios Piliouras · 4 citations
#machine learning Preprint Nov 2026

Logarithmic Regret for Alternating Mirror Descent

Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether Alt...

Tian-Long Nan, C. Kroer · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.