|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-01-106
2001-106
Potential-based
Algorithms in On-line Prediction and Game Theory
Nicolo Cesa-Bianchi and Gabor Lugosi
ABSTRACT
In this paper we show that several known algorithms for sequential
prediction problems (including the quasi-additive family of Grove
{\it 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 $\Lambda$-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.
Download
Postscript
|