Tracking the Best Expert**The authors were supported by NSF grant IRI-9123692.

Abstract

We generalize the recent worst-case loss bounds for on-line algorithms where the additional loss of the algorithm on the whole sequence of examples over the loss of the best expert is bounded. The generalization allows the sequence to be partitioned into segments and the goal is to bound the additional loss of the algorithm over the sum of the losses of the best experts of each segment. This is to model situations in which the examples change and different experts are best for certain segments of the sequence of examples. In the single expert case the additional loss is proportional to log n, where n is the number of experts and the constant of proportionality depends on the loss function. When the number of segments is at most k+ 1 and the sequence of length l then we can bound the additional loss of our algorithm over the best partitioning by O(klogn + klog(l/k)). Note that it takes the same order of bits to denote the sequence of experts and the boundaries of the segments. When the loss per trial is bounded by one then we obtain additional loss bounds that are independent of the length of the sequence. The bound becomes O(k logn + klog(L/k)), where L is the loss of the best partition into k+1 segments. Our algorithms for tracking the best expert are simple adaptations of Vovk's original algorithm for the single best expert case. These algorithms keep one weight per expert and spend (1) time per weight in each trial. Acknowledgments We would like to thank Peter Auer and Phillip Long for valuable discussions.