Online Learning with an Almost Perfect Expert

07/30/2018
by   Simina Branzei, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset