Timezone: »

 
Poster
Near-Optimal No-Regret Learning Dynamics for General Convex Games
Gabriele Farina · Ioannis Anagnostides · Haipeng Luo · Chung-Wei Lee · Christian Kroer · Tuomas Sandholm

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #539
in Poster Session 1 »
A recent line of work has established uncoupled learning dynamics such that, when employed by all players in a game, each player's regret after $T$ repetitions grows polylogarithmically in $T$, an exponential improvement over the traditional guarantees within the no-regret framework. However, so far these results have only been limited to certain classes of games with structured strategy spaces---such as normal-form and extensive-form games. The question as to whether $O(\mathrm{polylog} T)$ regret bounds can be obtained for general convex and compact strategy sets---as is the case in many fundamental models in economics and multiagent systems---while retaining efficient strategy updates is an important question. In this paper, we answer this in the positive by establishing the first uncoupled learning algorithm with $O(\log T)$ per-player regret in general convex games, that is, games with concave utility functions supported on arbitrary convex and compact strategy sets. Our learning dynamics are based on an instantiation of optimistic follow-the-regularized-leader over an appropriately lifted space using a self-concordant regularizer that is peculiarly not a barrier for the feasible region. Our learning dynamics are efficiently implementable given access to a proximal oracle for the convex strategy set, leading to $O(\log\log T)$ per-iteration complexity; we also give extensions when access to only a linear optimization oracle is assumed. Finally, we adapt our dynamics to guarantee $O(\sqrt{T})$ regret in the adversarial regime. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret bounds either in terms of the dependence on the number of iterations or on the dimension of the strategy sets.
Keywords: No-regret learning · extensive-form games · convex games · optimism
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Gabriele Farina (Meta AI; Carnegie Mellon University)
Ioannis Anagnostides (Carnegie Mellon University)
Haipeng Luo (University of Southern California)
Chung-Wei Lee (University of Southern California)
Christian Kroer (Columbia University)
Tuomas Sandholm (CMU, Strategic Machine, Strategy Robot, Optimized Markets)

More from the Same Authors