Online Learning and Game Theory
published: Feb. 25, 2007, recorded: May 2005, views: 5594
Report a problem or upload filesIf 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.
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.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !