Online Learning with an Almost Perfect Expert

We study the multiclass online learning problem where a forecaster makes a sequence of predictions using the advice of n experts. Our main contribution is to analyze the regime where the best expert makes at most b mistakes and to show that when b = o(log4n), the expected number of mistakes made by the optimal forecaster is at most log4n + o(log4n). We also describe an adversary strategy showing that this bound is tight and that the worst case is attained for binary prediction.