Spring 2022

Learning & Games Reading Group: Equilibrium Computation and Machine Learning

Tuesday, May 10, 2022 11:00 am12:30 pm PDT

Add to Calendar

Parent Program: 

Ioannis Anagnostides (Carnegie Mellon University)


Calvin Lab Room 116

Title: Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games

Abstract: In a recent breakthrough result, Daskalakis, Fishelson, and Golowich (NeurIPS 21) showed that if all agents in a multi-player general-sum game employ optimistic multiplicative weights update, the external regret of every player is bounded by $O(polylog(T))$ after $T$ repetitions of the game. In this talk we will describe new techniques that enabled us to extend their result from external regret to internal and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium at the near-optimal rate of $O(polylog(T)/T)$.

Bio: I am a first year PhD student at the school of computer science at Carnegie Mellon University, advised by Tuomas Sandholm. Previously, I completed my undergraduate studies at the National Technical University of Athens under the supervision of Dimitris Fotakis. My main research interests lie in the interface of algorithmic game theory and machine learning.

List of related papers: