Game Theory, On-Line Prediction and Boosting

Freund, Yoav; Schapire, Robert E.

doi:10.1145/238061.238163

Game Theory, On-Line Prediction and Boosting

Yoav Freund, Robert E. Schapire

COLT 1996 pp. 325-332

doi:10.1145/238061.238163 /colt/1996/freund1996colt-game/

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 gameplaying algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the “dual ” of this game. 1

PDF COLT Semantic Scholar

Cite

Text

Freund and Schapire. "Game Theory, On-Line Prediction and Boosting." Annual Conference on Computational Learning Theory, 1996. doi:10.1145/238061.238163

Markdown

[Freund and Schapire. "Game Theory, On-Line Prediction and Boosting." Annual Conference on Computational Learning Theory, 1996.](https://mlanthology.org/colt/1996/freund1996colt-game/) doi:10.1145/238061.238163

BibTeX

@inproceedings{freund1996colt-game,
  title     = {{Game Theory, On-Line Prediction and Boosting}},
  author    = {Freund, Yoav and Schapire, Robert E.},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1996},
  pages     = {325-332},
  doi       = {10.1145/238061.238163},
  url       = {https://mlanthology.org/colt/1996/freund1996colt-game/}
}