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

Yang Cai, Vineet Gupta, Yanchen Jiang +4

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 asymptot…