Online Learning with an Almost Perfect Expert
We study the online learning problem where a forecaster makes a sequence of binary 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(_4n), the expected number of mistakes made by the optimal forecaster is at most _4n + o(_4n). We also describe an adversary strategy showing that this bound is tight.
READ FULL TEXT