Potential-based Algorithms in On-line Prediction and Game Theory
Lists
Only you see this
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},
title = {{Potential-based Algorithms in On-line Prediction and Game Theory}},
booktitle = {Conference on Learning Theory},
year = {2001},
doi = {10.1007/3-540-44581-1\_4},
}Loading related content...