Near Minimax Optimal Players for the Finite-Time 3-Expert Prediction Problem
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 → ∞. We characterize, when K = 3, the regret of the game scaling as � 8/(9π)T ± log(T ) 2 which gives for the first time the optimal constant in the leading ( √ T ) term of the regret.
The paper studies the classic prediction with experts advice problem. There are a finite number k of experts and a finite number T of rounds. There is a player that makes sequential decisions for T rounds based on the advice of the k experts, and his goal is to minimize the maximum regret he can experience (minimax regret). Naturally, the optimal adversarial strategy is a key quantity to study here. This paper takes up the conjectured minimax optimal adversarial strategy called "Comb strategy" in the Gravin et al. paper and shows that it is indeed minimax optimal in the case of 3 experts. The high level proof structure is to show that the comb strategy is optimal assuming that in all the future rounds the comb strategy will be employed and then induct. (Comb strategy is not the exact optimal though --- thus one has to lose a bit in terms of optimality, and bound how the error accumulates as one inducts) One of the useful lemmas in doing this is the "exchangeability property", which shows that deviating from comb strategy in exactly one round will give a regret that is independent of which round one deviates off of it. The need for this property arises naturally when one takes the induction proof structure above. The proof of this property proceeds by considering another adversarial strategy twin-comb, also proved to be optimal for geometric horizon setting by Gravin et al., and then showing that playing Comb + non-comb is same as playing twin-comb + comb where non-comb is a mixture of {Comb, twin-comb}. The question is how to generalize this for arbitrary number of experts k. For general k, is it possible to push this idea through with the generalized twin-comb? And what would be the appropriate generalization? This is not immediately clear from the paper, but I still think the contribution as it is already meets the NIPS bar, and certainly has some neat ideas. 
Given that this paper takes a conjectured optimal strategy, whose optimality for a small number of experts can be verified directly by writing a computer program to compute optimal adversarial values, its primary value can lie only in the new techniques it introduces. The main challenge is that since the comb adversary is not the exactly optimal adversary, all the nice properties of optimality are gone, and one has to control how the errors of this suboptimal strategy accumulate in order to establish approximate optimality. The "exchangeability" property is the main new idea for doing this. There is also the other nice contribution of proving that the player's algorithm that flows out of the comb adversary, which itself is not the exactly optimal but only approximately optimal, is an approximately optimal algorithm. Usually, when the adversary is not optimal, proving optimality for the algorithm that simulates it is not straight-forward. While the techniques don't immediately generalize, the general approach of controlling COMB adversary's errors with an exchangeability technique seems like the way to go for general k. Given this, and the fact that the work is technically interesting, I would say it meets the NIPS bar.