A Game of Prediction with Expert Advice

摘要

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 exceedscL+a ln n, wherecandaare some constants,nis the size of the pool, andLis 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.