[PDF][PDF] A game of prediction with expert advice

VG Vovk - Proceedings of the eighth annual conference on …, 1995 - dl.acm.org
Proceedings of the eighth annual conference on Computational learning theory, 1995dl.acm.org
We consider the following situation. 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 inn, where c and a are 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 …
Abstract
We consider the following situation. 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 inn, where c and a are 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.
ACM Digital Library