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 √fracT ln n2. 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 √t ln n---a factor of √2 worse---and it has remained unknown whether this factor of √2 is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies Rt ≤ bigl(1 + O(√ln ln n / ln n)bigr)√t ln n / 2 simultaneously for every t ≥ 1.