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{\frac{T\ln n}{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\ln 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\le (1+O(\sqrt{\ln \ln n\mathrm{/}\ln n}))\sqrt{t\ln n\mathrm{/}2}$ simultaneously for every $t\ge 1$.