Timezone: »

 
Oral
Near-Optimal No-Regret Learning in General Games
Constantinos Daskalakis · Maxwell Fishelson · Noah Golowich

Tue Dec 07 12:20 AM -- 12:35 AM (PST) @
in Oral Session 1: Theory »
We show that Optimistic Hedge -- a common variant of multiplicative-weights-updates with recency bias -- attains ${\rm poly}(\log T)$ regret in multi-player general-sum games. In particular, when every player of the game uses Optimistic Hedge to iteratively update her action in response to the history of play so far, then after $T$ rounds of interaction, each player experiences total regret that is ${\rm poly}(\log T)$. Our bound improves, exponentially, the $O(T^{1/2})$ regret attainable by standard no-regret learners in games, the $O(T^{1/4})$ regret attainable by no-regret learners with recency bias (Syrgkanis et al., NeurIPS 2015), and the $O(T^{1/6})$ bound that was recently shown for Optimistic Hedge in the special case of two-player games (Chen & Peng, NeurIPS 2020). A direct corollary of our bound is that Optimistic Hedge converges to coarse correlated equilibrium in general games at a rate of $\tilde{O}(1/T)$.
Keywords:

Author Information

Constantinos Daskalakis (MIT)
Maxwell Fishelson (MIT)
Noah Golowich (MIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors