Abstract

 We study minimax strategies for the online prediction problem with expert advice. It has been conjectured that a simple adversary strategy, called C OMB, is near optimal in this game for any number of experts. Our results and new insights make progress in this direction by showing that, up to a small additive term, C OMB is minimax optimal in the ?nite-time three expert problem. In addition, we provide for this setting a new near minimax optimal C OMB-based learner. Prior to this work, in this problem, learners obtaining the optimal multiplicative constant in their regret rate were known only when . We characterize, when K = 3, the regret of the game scaling as  which gives for the first time the optimal constant in the leading ( T ) term of the regret.