We study multiclass online learning, where a forecaster predicts a sequence of elements drawn from a finite set using the advice of n experts. Our main contributions are to analyze the scenario where the best expert makes a bounded number b of mistakes and to show that, in the low-error regime where [Formula: see text], the expected number of mistakes made by the optimal forecaster is at most [Formula: see text] We also describe an adversary strategy showing that this bound is tight and that the worst case is attained for binary prediction.
Keywords: expert advice; forecasting algorithms; lower bounds; multiclass decision making; online learning.