Prediction, Learning, and Games
This important new text and reference for researchers and students in machine learning, game theory, statistics and information theory offers the first comprehensive treatment of the problem of predicting individual sequences. Unlike standard statistical approaches to forecasting, prediction of individual sequences does not impose any probabilistic assumption on the data-generating mechanism. Yet, prediction algorithms can be constructed that work well for all possible sequences, in the sense that their performance is always nearly as good as the best forecasting strategy in a given reference class. The central theme is the model of prediction using expert advice, a general framework within which many related problems can be cast and discussed. Repeated game playing, adaptive data compression, sequential investment in the stock market, sequential pattern analysis, and several other problems are viewed as instances of the experts' framework and analyzed from a common nonstochastic standpoint that often reveals new and intriguing connections. Old and new forecasting methods are described in a mathematically precise way in order to characterize their theoretical limitations and possibilities.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Prediction with Expert Advice
Tight Bounds for Speciﬁc Losses
Efﬁcient Forecasters for Large Classes of Experts
Prediction with Limited Feedback
Prediction and Playing Games
achieved algorithm assume Cesa-Bianchi Chapter class of experts classiﬁcation compound actions computed consider constant convergence convex convex set Corollary correlated equilibria cumulative loss deﬁned deﬁnition denote example Exercise exponential potential exponentially weighted average ﬁnite ﬁrst ﬁxed forecasting strategy Hannan consistency Hoeffding's inequality implies inequality internal regret investment strategy Kullback-Leibler divergence l(It Legendre Lemma limsup logarithmic loss loss function lower bound martingale matrix minimax regret minimax theorem minimize mixability mixed strategy mixture forecaster multi-armed bandit Nash equilibrium Note obtain optimal outcome sequence outcome Yt parameter partial monitoring Perceptron play probability distribution proof of Theorem random variables regret bound result row player satisﬁes Section sequence of outcomes share forecaster shortest path problem side information square loss static experts Theorem 2.2 tree experts update upper bound vector Vn(F Warmuth weighted average forecaster