Online Learning and Game Theory

author: Adam Kalai, Toyota Technological Institute at Chicago
published: Feb. 25, 2007,   recorded: May 2005,   views: 28927


Related content

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.
Lecture popularity: You need to login to cast your vote.
  Delicious Bibliography

 Watch videos:   (click on thumbnail to launch)

Watch Part 1
Part 1 1:03:51
Watch Part 2
Part 2 33:55


We consider online learning and its relationship to game theory. In an online decision-making problem, as in Singer's lecture, one typically makes a sequence of decisions and receives feedback immediately after making each decision. As far back as the 1950's, game theorists gave algorithms for these problems with strong regret guarantees. Without making statistical assumptions, these algorithms were guaranteed to perform nearly as well as the best single decision, where the best is chosen with the benefit of hindsight. We discuss applications of these algorithms to complex learning problems where one receives very little feedback. Examples include online routing, online portfolio selection, online advertizing, and online data structures. We also discuss applications to learning Nash equilibria in zero-sum games and learning correlated equilibria in general two-player games.

See Also:

Download slides icon Download slides: Online_Learning_&_Game_Theory.ppt (880.0┬áKB)

Help icon Streaming Video Help

Link this page

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

Reviews and comments:

Comment1 ram, January 6, 2008 at 6:57 p.m.:

Second video doesn't play past 9:20 seconds

Comment2 ram, January 10, 2008 at 12:45 a.m.:

works now.

Comment3 Praveen, December 26, 2008 at 7:08 p.m.:

Apparently, the stream is not available any more. I get the error "Stream not found". Is it possible to look into the problem?

Comment4 Lik, January 5, 2013 at 1:34 p.m.:

Animal training

Comment5 professional wikipedia editors, March 6, 2023 at 3:50 p.m.:

I think it's the best tutorial I've ever seen. Please let others know about this subject so that we may get more information like this

Write your own review or comment:

make sure you have javascript enabled or clear this field: