No-regret learning in convex games
GJ Gordon, A Greenwald, C Marks - Proceedings of the 25th …, 2008 - dl.acm.org
GJ Gordon, A Greenwald, C Marks
Proceedings of the 25th international conference on Machine learning, 2008•dl.acm.orgQuite a bit is known about minimizing different kinds of regret in experts problems, and how
these regret types relate to types of equilibria in the multiagent setting of repeated matrix
games. Much less is known about the possible kinds of regret in online convex programming
problems (OCPs), or about equilibria in the analogous multiagent setting of repeated convex
games. This gap is unfortunate, since convex games are much more expressive than matrix
games, and since many important machine learning problems can be expressed as OCPs …
these regret types relate to types of equilibria in the multiagent setting of repeated matrix
games. Much less is known about the possible kinds of regret in online convex programming
problems (OCPs), or about equilibria in the analogous multiagent setting of repeated convex
games. This gap is unfortunate, since convex games are much more expressive than matrix
games, and since many important machine learning problems can be expressed as OCPs …
Quite a bit is known about minimizing different kinds of regret in experts problems, and how these regret types relate to types of equilibria in the multiagent setting of repeated matrix games. Much less is known about the possible kinds of regret in online convex programming problems (OCPs), or about equilibria in the analogous multiagent setting of repeated convex games. This gap is unfortunate, since convex games are much more expressive than matrix games, and since many important machine learning problems can be expressed as OCPs. In this paper, we work to close this gap: we analyze a spectrum of regret types which lie between external and swap regret, along with their corresponding equilibria, which lie between coarse correlated and correlated equilibrium. We also analyze algorithms for minimizing these regret types. As examples of our framework, we derive algorithms for learning correlated equilibria in polyhedral convex games and extensive-form correlated equilibria in extensive-form games. The former is exponentially more efficient than previous algorithms, and the latter is the first of its type.
ACM Digital Library