2019/12/05 by Vladimir A. Kobzar, Robert V. Kohn, Kobzar, Vladimir A. +3
Computer Science · Decision Sciences · Mathematics · #35Q68 #35Q93 #49L20 #68W27 #91A05 #93C20 #Advanced Bandit Algorithms Research #Analysis of PDEs (math.AP) #Computer Science and Game Theory (cs.GT) #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #FOS: Mathematics #I.2.8 #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #acm:35Q68 #acm:35Q93 #acm:49L20 #acm:68W27 #acm:91A05 #acm:93C20 #cs.GT #cs.LG #math.AP #math.OC #msc:35Q68 #msc:35Q93 #msc:49L20 #msc:68W27 #msc:91A05 #msc:93C20 #stat.ML
paper · pdf · doi:10.48550/arxiv.1912.03132
To appear in MSML2020. arXiv admin note: text overlap with arXiv:1911.01641
openalex publication_date 2019/12/05 · openalex created_date 2019/12/13 · arxiv created 2020/06/29 · arxiv updated 2020/07/02 · openalex updated_date 2026/07/28
This work addresses the classic machine learning problem of online prediction with expert advice. A new potential-based framework for the fixed horizon version of this problem has been recently developed using verification arguments from optimal control theory. This paper extends this framework to the random (geometric) stopping version. To obtain explicit bounds, we construct potentials for the geometric version from potentials used for the fixed horizon version of the problem. This construction leads to new explicit lower and upper bounds associated with specific adversary and player strategies. While there are several known lower bounds in the fixed horizon setting, our lower bounds appear to be the first such results in the geometric stopping setting with an arbitrary number of experts. Our framework also leads in some cases to improved upper bounds. For two and three experts, our bounds are optimal to leading order.