Fast swap regret minimization and applications to approximate correlated equilibria

We give a simple and computationally efficient algorithm that, for any constant varepsilon>0, obtains varepsilon T-swap regret within only T = mathsfpolylog(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 [Blum and Mansour 2007]. Our algorithm has an exponential dependence on varepsilon, but we prove a new, matching lower bound. Our algorithm for swap regret implies faster convergence to varepsilon-Correlated Equilibrium (varepsilon-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 varepsilon-CE in polylogarithmic rounds; a mathsfpolylog(n)-bit communication protocol for varepsilon-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein'2017, Goos-Rubinstein'2018, Ganor-CS'2018]); and an tildeO(n)-query algorithm for varepsilon-CE (resolving an open problem of [Babichenko'2020] and obtaining the first separation between varepsilon-CE and varepsilon-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for mathitnormal mathitform mathitcorrelated mathitequilibria, a solution concept often conjectured to be computationally intractable (e.g. [Stengel-Forges'08, Fujii'23]).