Game theory, on-line prediction and boosting

Yoav Freund, Robert E. Schapire

Research output: Contribution to conferencePaper

274 Scopus citations

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 languageEnglish (US)
Pages325-332
Number of pages8
DOIs
StatePublished - Jan 1 1996
Externally publishedYes
EventProceedings of the 1996 9th Annual Conference on Computational Learning Theory - Desenzano del Garda, Italy
Duration: Jun 28 1996Jul 1 1996

Other

OtherProceedings of the 1996 9th Annual Conference on Computational Learning Theory
CityDesenzano del Garda, Italy
Period6/28/967/1/96

All Science Journal Classification (ASJC) codes

  • Computational Mathematics

Fingerprint Dive into the research topics of 'Game theory, on-line prediction and boosting'. Together they form a unique fingerprint.

  • Cite this

    Freund, Y., & Schapire, R. E. (1996). Game theory, on-line prediction and boosting. 325-332. Paper presented at Proceedings of the 1996 9th Annual Conference on Computational Learning Theory, Desenzano del Garda, Italy, . https://doi.org/10.1145/238061.238163