A simple on-line procedure is considered for the prediction of a binary-valued sequence in the setup introduced and studied by Weissman and Merhav [2001], [2004], where only side information is available for the algorithm. The (non-randomized) algorithm is based on a convex combination of several simple predictors. If the side information is also binary-valued (i.e. original sequence is corrupted by a binary sequence) and both processes are realizations of stationary and ergodic random processes then the average of the loss converges, almost surely, to that of the optimum, given by the Bayes predictor. An analog result is offered for the classification of binary processes.

Machine learning algorithms for combining expert advice in sequential decision problems are considered. The goal of these algorithms is to perform, for any behavior of the system, asymptotically as well as the best expert. We provide a survey of these algorithms and show how they can be used for adaptive routing in different packet switched networks.