Oral
in
Workshop: Learning in Presence of Strategic Behavior
Near-Optimal No-Regret Learning in General Games
Constantinos Daskalakis · Maxwell Fishelson · Noah Golowich
Abstract:
We show that Optimistic Hedge -- a common variant of multiplicative-weights-updates with recency bias -- attains regret in multi-player general-sum games. In particular, when every player of the game uses Optimistic Hedge to iteratively update her strategy in response to the history of play so far, then after rounds of interaction, each player experiences total regret that is . Our bound improves, exponentially, the regret attainable by standard no-regret learners in games, the regret attainable by no-regret learners with recency bias (Syrgkanis et al., 2015), and the bound that was recently shown for Optimistic Hedge in the special case of two-player games (Chen & Peng, 2020). A corollary of our bound is that Optimistic Hedge converges to coarse correlated equilibrium in general games at a rate of .
Chat is not available.