event thumbnail image
The 25th International Conference on Machine Learning (ICML 2008)

No-Regret Learning in Convex Games

author: Geoffrey J. Gordon, +Machine Learning Department; School of Computer Science; Carnegie Mellon University

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.

You might be experiencing some problems with Your Video player.
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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: