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 = ( 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 ‍[]. 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 ( n )-bit communication protocol for ε-CE in two-player games (resolving an open problem mentioned by ‍[, ]); and an Õ( n )-query algorithm for ε-CE (resolving an open problem of ‍[] 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. ‍[, ]).

Authors

• Binghui Peng
• Aviad Rubinstein

Keywords

• Equilibrium computation
• Online learning