Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Prediction with expert advice is a fundamental problem in online learning. When the time horizon T is known in advance, the minimax cumulative regret over n experts is asymptotically sqrt T n over 2. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to T, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time t, the best known guarantee has been sqrt t n ---a factor of sqrt 2 worse---and it has remained unknown whether this factor of sqrt 2 is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies R t (1 + O(sqrt n / n)) sqrt t n / 2 simultaneously for every t 1.