A game of prediction with expert advice
Vladimir Vovk · 1995
We consider the following problem. At each point of discrete time the learner must make a prediction; he is given the predictions made by a pool of experts. Each prediction and the outcome, which is disclosed after the learner has made his prediction, determine the incurred loss. It is known that, under weak regularity, the learner can ensure that his cumulative loss never exceeds cL+a ln n, where c and a are some constants, n is the size of the pool, and L is the cumulative loss incurred by the best expert in the pool. We find the set of those pairs (c, a) for which this is true.]1998 Academic Press 1. MAIN RESULT Our learning protocol is as follows. We consider a learner who acts in the following environment. There are a pool of n experts and the nature, which interact with the learner in the following way. At each trial t, t=1, 2,...: 1. Each expert i, i=1,..., n, makes a prediction #t(i) # 1,