Skip to yearly menu bar Skip to main content


Poster

Near Minimax Optimal Players for the Finite-Time 3-Expert Prediction Problem

Yasin Abbasi Yadkori · Peter Bartlett · Victor Gabillon

Pacific Ballroom #59

Keywords: [ Online Learning ]


Abstract: We study minimax strategies for the online prediction problem with expert advice. It has been conjectured that a simple adversary strategy, called COMB, 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, COMB is minimax optimal in the finite-time three expert problem. In addition, we provide for this setting a new near minimax optimal COMB-based learner. Prior to this work, in this problem, learners obtaining the optimal multiplicative constant in their regret rate were known only when $K=2$ or $K\rightarrow\infty$. We characterize, when $K=3$, the regret of the game scaling as $\sqrt{8/(9\pi)T}\pm \log(T)^2$ which gives for the first time the optimal constant in the leading ($\sqrt{T}$) term of the regret.

Live content is unavailable. Log in and register to view live content