No-Regret Learning in Convex Games
Description
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.
| Slides | |
| 0:00 | No-Regret Learning in Convex Games |
| 0:02 | Background |
| 1:35 | Normal-Form Picture |
| 2:05 | This Talk |
| 2:39 | Convex Games (Known) |
| 3:18 | Convex Games (Contrib) - 1 |
| 4:22 | Convex Games (Contrib) - 2 |
| 4:41 | Convex Games (Contrib) - 3 |
| 4:56 | Convex Games (Contrib) - 4 |
| 5:22 | Outline |
| 5:55 | Convex Games |
| 7:09 | Online Convex Programs |
| 7:57 | External Regret |
| 8:33 | Action Transformations - 1 |
| 8:55 | Action Transformations - 2 |
| 9:19 | Φ-Regret |
| 10:26 | Regret Examples |
| 10:48 | Φ = Finite Element |
| 11:50 | Φ = EF Transformations |
| 11:59 | Algorithm Idea - 1 |
| 11:59 | Algorithm Idea - 2 |
| 12:52 | Algorithm Idea - 3 |
| 13:06 | Algorithm - 1 |
| 13:16 | Algorithm - 2 |
| 13:28 | Algorithm - 3 |
| 15:12 | Algorithm - 4 |
| 15:36 | Theorem - 1 |
| 15:44 | Proof of no Φ-Regret |
| 16:00 | Making it Fast |
| 16:33 | Half of Kernel Trick |
| 16:59 | Kernelized Φ => Fast |
| 17:33 | Theorem - 2 |
| 18:48 | Summary - 1 |
| 19:12 | Summary - 2 |
| 19:23 | Summary - 3 |
| 19:40 | Related Work - 1 |
| 20:14 | Related Work - 2 |
| 20:40 | - Questions |
Lecture rating
| People found this lecture: | ||
| Worth seeing | ||
| because it is: | ||
| Valuable and informative | ||
| Well presented | ||
| Easily understandable | ||
| Acceptably recorded | ||
| You need to login to cast your vote. | ||
Report a problem or upload files
If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
SEE ALSO:
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !



