On the asymptotic optimality of the comb strategy for prediction with expert advice
This provides a theoretical confirmation for a specific case in online learning, but it is incremental as it builds on prior conjectures and focuses on a limited scenario.
The paper tackled the problem of proving asymptotic optimality for comb strategies in adversarial prediction with expert advice under geometric stopping, and showed that these strategies are indeed optimal for the case of 4 experts, as previously conjectured.
For the problem of prediction with expert advice in the adversarial setting with geometric stopping, we compute the exact leading order expansion for the long time behavior of the value function. Then, we use this expansion to prove that as conjectured in Gravin et al. [12], the comb strategies are indeed asymptotically optimal for the adversary in the case of 4 experts.