2020/07/24 by Nadejda Drenska, Robert V. Kohn, Drenska, Nadejda +1 · 2 citations
Computer Science · Decision Sciences · Mathematics · #35D40 #49L25 #Advanced Bandit Algorithms Research #Analysis of PDEs (math.AP) #Computer Science and Game Theory (cs.GT) #Data Stream Mining Techniques #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Machine Learning (cs.LG) #Optimization and Control (math.OC) #cs.GT #cs.LG #math.AP #math.OC #msc:35D40 #msc:49L25
paper · pdf · doi:10.48550/arxiv.2007.12732
arxiv created 2020/07/24 · openalex publication_date 2020/07/24 · arxiv updated 2020/07/28 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
The prediction of a binary sequence is a classic example of online machine learning. We like to call it the 'stock prediction problem,' viewing the sequence as the price history of a stock that goes up or down one unit at each time step. In this problem, an investor has access to the predictions of two or more 'experts,' and strives to minimize her final-time regret with respect to the best-performing expert. Probability plays no role; rather, the market is assumed to be adversarial. We consider the case when there are two history-dependent experts, whose predictions are determined by the d most recent stock moves. Focusing on an appropriate continuum limit and using methods from optimal control, graph theory, and partial differential equations, we discuss strategies for the investor and the adversarial market, and we determine associated upper and lower bounds for the investor's final-time regret. When d is less than 4 our upper and lower bounds coalesce, so the proposed strategies are asymptotically optimal. Compared to other recent applications of partial differential equations to prediction, ours has a new element: there are two timescales, since the recent history changes at every step whereas regret accumulates more slowly.