Abstract
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 game-playing algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the `dual' of this game.
Original language | English (US) |
---|---|
Pages | 325-332 |
Number of pages | 8 |
DOIs | |
State | Published - 1996 |
Externally published | Yes |
Event | Proceedings of the 1996 9th Annual Conference on Computational Learning Theory - Desenzano del Garda, Italy Duration: Jun 28 1996 → Jul 1 1996 |
Other
Other | Proceedings of the 1996 9th Annual Conference on Computational Learning Theory |
---|---|
City | Desenzano del Garda, Italy |
Period | 6/28/96 → 7/1/96 |
All Science Journal Classification (ASJC) codes
- Computational Mathematics