2023/10/30 by Binghui Peng, Aviad Rubinstein, Peng, Binghui +1 · 6 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Machine Learning (cs.LG) #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.2310.19647
openalex publication_date 2023/10/30 · openalex created_date 2023/11/01 · openalex updated_date 2026/07/28
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 and Mansour 2007]. 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 [Babichenko-Rubinstein'2017, Goos-Rubinstein'2018, Ganor-CS'2018]); and an O(n)-query algorithm for ε-CE (resolving an open problem of [Babichenko'2020] 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. [Stengel-Forges'08, Fujii'23]).