ON THE ASYMPTOTIC OPTIMALITY OF THE COMB STRATEGY FOR PREDICTION WITH EXPERT ADVICE
成果类型：
Article
署名作者：
Bayraktar, Erhan; Ekren, Ibrahim; Zhang, Yili
署名单位：
University of Michigan System; University of Michigan; State University System of Florida; Florida State University
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/20-AAP1565
发表日期：
2020
页码：
2517-2546
关键词：
摘要：
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, Peres and Sivan (In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (2016) 528-547, ACM), the comb strategies are indeed asymptotically optimal for the adversary in the case of 4 experts.