Potential-Based Algorithms in Online 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 offering a new and unified 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.
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...