Poster
Near Minimax Optimal Players for the Finite-Time 3-Expert Prediction Problem
Yasin Abbasi Yadkori · Peter Bartlett · Victor Gabillon

Wed Dec 6th 06:30 -- 10:30 PM @ Pacific Ballroom #59 #None
in Posters Wed »
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.
Keywords: Online Learning

Author Information

Yasin Abbasi Yadkori (Adobe Research)
Peter Bartlett (UC Berkeley)
Victor Gabillon (QUT - ACEMS)

More from the Same Authors