2022/03/15 by Laura Greenstreet, Nicholas J. A. Harvey, Greenstreet, Laura +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2203.07577
openalex publication_date 2022/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Prediction with expert advice is a foundational problem in online learning. In instances with T rounds and n experts, the classical Multiplicative Weights Update method suffers at most √((T/2)ln n) regret when T is known beforehand. Moreover, this is asymptotically optimal when both T and n grow to infinity. However, when the number of experts n is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to \0,1\ costs that suffers at most √(T/2π) + O(1) regret with O(T2) pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts' advice that works even for costs in [0,1] and with O(1) processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.