Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria

We give a simple and computationally efficient algorithm that, for any constant ǫ > 0, obtains ǫT -swap regret within only T = polylog(n) rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [BM07]. Our algorithm has an exponential dependence on ǫ, but we prove a new, matching lower bound.

Our algorithm for swap regret implies faster convergence to ǫ-Correlated Equilibrium (ǫ-CE) in several regimes: For normal form two-player games with n actions, it implies the first uncoupled dynamics that converges to the set of ǫ-CE in polylogarithmic rounds; a polylog(n)bit communication protocol for ǫ-CE in two-player games (resolving an open problem mentioned by [BR17, GC18, GR18]); and an Õ(n)-query algorithm for ǫ-CE (resolving an open problem of [Bab20] and obtaining the first separation between ǫ-CE and ǫ-Nash equilibrium in the query complexity model).

For extensive-form games, our algorithm implies a PTAS for normal form correlated equilibria, a solution concept often conjectured to be computationally intractable (e.g. [VSF08,Fuj23]).