Swap Regret

Follow this topic Ask about this topic

Latest papers

8 papers0 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism
Sep 15, 2026Tung MaiGame Theory Swap Regret
Adobe Research
Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
Aug 4, 2026Taira TsuchiyaFollow-the-Regularized-Leader Swap Regret
The University of Tokyo and RIKEN
Training with (Swap) Regret Loss in a Single-Layer Self-Attention Model: A Case Study on the Probability Simplex
Jul 25, 2026Chanwoo Park, Asuman OzdaglarSelf-Attention Swap Regret
1MIT EECS
Improved Multi-Dimensional Forecasting for Swap Regret
Jun 28, 2026Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg +3Swap Regret Regret Minimization
Cornell University
Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria
Jun 9, 2026Wongyu Lee, Francesco Lelli, Omran Ayoub +1Multi-Agent Coordination Swap Regret
Politecnico di Milano · Tilburg University · University of Applied Sciences and Arts of Southern Switzerland
Testable and Actionable Calibration for Full Swap Regret
May 18, 2026Konstantina Bairaktari, Lunjia Hu, Huy L. Nguyen +1Probability Calibration Swap Regret
Department of Computer Science, Aarhus University. · Khoury College of Computer Sciences, Northeastern University.
Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners
Feb 25, 2026Arnab Maiti, Junyan Liu, Kevin Jamieson +1Swap Regret Game Theory
University of Washington
Prior-Agnostic Incentive-Compatible Exploration
Feb 24, 2026Ramya Ramalingam, Osbert Bastani, Aaron RothSwap Regret Multi-Armed Bandits
Department of Computer and Information Sciences, University of Pennsylvania

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

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

Tung Mai

Adobe Research

Game Theory Swap Regret Decentralized Learning Regret Minimization

Open paper AskPDF arXiv

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.