Fast swap regret minimization and applications

Abstract:   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 [Blum & Mansour '07]. 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, resolving open problems from [Von Stengel & Forges '08, Babichenko & Rubinstein '17, Ganor & Karthik '18, Babichenko '20, Fujii '23].   In follow up work our algorithm has already been used to design new learning algorithm for Principal-Agents problems [Collina, Gupta, Roth '24], and a new efficient algorithm for high dimensional calibration [Peng '25] (the latter result resolves open questions by [Abernethy & Mannor '11, Hazan & Kakade '12]).