SOURCE-LINKED INTELLIGENCE

Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices

arXiv · AI, language, vision and robotics · article · Sep 15, 2026 · UTC

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret, independent of the horizon $T$. With $n$ players and at most $m$ actions each, the individual swap regret of every player is $O(\sqrt{n} m \log m \log^{5/2}(nm))$ at every finite horizon. Each player predicts the deviation gains, then uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. The proof combines a potential argument exploiting stationarity with a two-scale hig

Read original source ↗ Open in workspace

recordType

paper

region

Global