Experimental Evidence for Asymptotic Non-Optimality of Comb Adversary Strategy

2019/12/03 by Zachary Chase, Chase, Zachary
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.GT #cs.LG

paper · pdf · doi:10.48550/arxiv.1912.01548

3 pages, 1 figure

arxiv created 2019/12/03 · arxiv updated 2019/12/04

Abstract

For the problem of prediction with expert advice in the adversarial setting with finite stopping time, we give strong computer evidence that the comb strategy for k=5 experts is not asymptotically optimal, thereby giving strong evidence against a conjecture of Gravin, Peres, and Sivan.

Related

• On the asymptotic optimality of the comb strategy for prediction with expert advice
• Towards Optimal Algorithms for Prediction with Expert Advice
• Prediction against a limited adversary
• Finite-Time 4-Expert Prediction Problem
• New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice