Tight worst-case loss bounds for predicting with expert advice

摘要: We consider on-line algorithms for predicting binary or continuous-valued outcomes, when the algorithm has available predictions made by N experts. For a sequence of trials, we compute total losses both and experts under loss function. At end trial sequence, compare to best expert, i.e., expert with least on particular sequence. show that large class functions, outcomes proposed Vovk exceeds at most amount c ln N, where is constant determined This upper bound does not depend any assumptions how experts'' are generated, can be arbitrarily long. give straightforward method finding correct value lower this c, asymptotically tight. The based probabilistic adversary argument. functions which holds includes square loss, logarithmic Hellinger loss. also another including absolute have an Omega((l log N)^(1/2)) bound, l number trials. Vovk''s achieves same worst-case bounds as outcomes. earlier achieved using slightly more complicated algorithm.