A wonderful synthesis of the literature on competitive, individual-sequence forecasting with expert advice. That is, the problems considered are all variants on a situation where you need to make a prediction about the future (or more generally take an action whose consequences will only be revealed in the future), have access to a range of "experts" or forecasting algorithms, and want to ensure that, no matter what actually happens, your performance will be close to that of the best expert. This is thus a study of sequential decision-making under uncertainty without probability. Often, but not always, the solution lies in taking weighted averages of the experts, giving more weight to those which have done well in the past. This works not because past performance provides any kind of inductive evidence of future success, but merely because it keeps your predictions from drifting too far from what is, in fact, working. (Perversely, many of the proofs rely on probabilistic arguments, but they don't make probabilistic assumptions.) Of course, it may be that even the best expert is very bad, but the possibility of improving on the experts is not really considered, though it's certainly possible (at least with convex loss functions).

Anyone at all interested in machine learning, forecasting, information, game theory, or decision-making under uncertainty needs to read this. It may also be useful to epistemologists. ( )