This is a set of notes for a paper covered by the learning theory reading group, which I’m posting here with some keywords so I can easily search for them. I doubt they’ll be useful for anyone else, but who knows?
These notes cover the whole paper. Despite the usual disclaimer, this set of notes may actually be thorough enough to be useful to someone besides myself because I was presenting this week. The exposition in the paper is excellent, and it’s pretty basic, so you’re probably still better off just reading the paper directly, though :-).
We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth. The analysis of this algorithm yields a simple proof of von Neumann’s famous minmax theorem, as well as a provable method of approximately solving a game. We then show that the on-line prediction model is obtained by applying this gameplaying algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the “dual” of this game.