Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria

Abstract: We give a simple and computationally efficient algorithm that, for any constant \eps>0, obtains εT distributional 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 [Blum-Mansour JMLR’07]. Our algorithm has an exponential dependence on \eps, but we prove a new, matching lower bound.

Our algorithm for swap regret implies faster convergence to \eps-Correlated Equilibrium (\eps-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 \eps-CE in polylogarithmic rounds; a polylog(n)-bit communication protocol for \eps-CE in two-player games (resolving an open problem mentioned by [Babichenko-Rubinstein STOC’2017, Ganor-CS APPROX’18, Goos-Rubinstein FOCS’2018}; and an $\tilde{O}(n)$-query algorithm for \eps-CE (resolving an open problem of [Babichenko 2020] and obtaining the first separation between \eps-CE and \eps-Nash equilibrium in the query complexity model). For extensive-form games, our algorithm implies a PTAS for normal form correlated equilibria, a solution concept widely conjectured to be computationally intractable (e.g. [Stengel-Forges MOR’08, Fujii’23]).

Joint work with Aviad Rubinstein