BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UC Irvine Donald Bren School of Information & Computer Sciences - ECPv5.12.3//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:UC Irvine Donald Bren School of Information & Computer Sciences
X-ORIGINAL-URL:https://ics.uci.edu
X-WR-CALDESC:Events for UC Irvine Donald Bren School of Information & Computer Sciences
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20240310T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20241103T090000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Los_Angeles:20240118T140000
DTEND;TZID=America/Los_Angeles:20240118T150000
DTSTAMP:20240418T132601
CREATED:20240117T012656Z
LAST-MODIFIED:20240201T155324Z
UID:20227-1705586400-1705590000@ics.uci.edu
SUMMARY:Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria
DESCRIPTION: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. \nOur 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]). \nJoint work with Aviad Rubinstein
URL:https://ics.uci.edu/event/aco-seminar-fast-swap-regret-minimization-and-applications-to-approximate-correlated-equilibria/
LOCATION:Donald Bren Hall\, Irvine\, CA\, 92697\, United States
ATTACH;FMTTYPE=image/jpeg:https://ics.uci.edu/wp-content/uploads/2024/01/Binghui_Peng_resize.jpg
END:VEVENT
END:VCALENDAR