Fast (distributional) swap regret and applications to approximate correlated equilibria

Speaker: Binghui Peng , Columbia Uniersity

Date: Wednesday, October 25, 2023

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description: 32-G575

Host: Rahul Ilango, MIT

Contact: Rahul Ilango, rilango@mit.edu

Relevant URL:

Speaker URL: http://www.cs.columbia.edu/~binghuip/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Binghui Peng: Fast (distributional) swap regret and applications to approximate correlated equilibria

Abstract: We give a simple and computationally efficient algorithm that, for any constant ε>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 ε, 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 STOC'2017, Ganor-CS APPROX'18, Goos-Rubinstein FOCS'2018}; and an $\tilde{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 widely conjectured to be computationally intractable (e.g. [Stengel-Forges MOR'08, Fujii'23]).

Joint work with Aviad Rubinstein

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2023.

Created by Noah Golowich at Tuesday, October 24, 2023 at 5:38 PM.