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({\log }_{4}n)$, the expected number of mistakes made by the optimal forecaster is at most ${\log }_{4}n+o({\log }_{4}n)$. We also describe an adversary strategy showing that this bound is tight and that the worst case is attained for binary prediction.