Potential-Based Algorithms in Online Prediction and Game Theory

Nicolò Cesa-Bianchi, Gábor Lugosi

Abstract

. In this paper we show that several known algorithms for sequential prediction problems (including the quasi-additive family of Grove et al. and Littlestone and Warmuth's Weighted Majority), for playing iterated games (including Freund and Schapire's Hedge and MW, as well as the -strategies of Hart and Mas-Colell), and for boosting (including AdaBoost) are special cases of a general decision strategy based on the notion of potential. By analyzing this strategy we derive known performance bounds, as well as new bounds, as simple corollaries of a single general theorem. Besides oering a new and unied view on a large family of algorithms, we establish a connection between potential-based analysis in learning and their counterparts independently developed in game theory. By exploiting this connection, we show that certain learning problems are instances of more general game-theoretic problems. In particular, we describe a notion of generalized regret and show its applications in learning theory. Key words and phrases: universal prediction, on-line learning, Blackwell's strategy, Perceptron algorithm, weighted average predictors, internal regret, boosting. ?
BibTeX
@inproceedings{cesabianchi2001potential,
  author = {Nicolò Cesa-Bianchi and Gábor Lugosi},
  title = {{Potential-Based Algorithms in Online Prediction and Game Theory}},
  booktitle = {Conference on Learning Theory},
  year = {2001},
  doi = {10.1007/3-540-44581-1\_4},
}

Loading related content...

Figure