2020/08/31 by Jeff Calder, Calder, Jeff, Nadejda Drenska +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #35D40 #49L25 #Advanced Bandit Algorithms Research #Analysis of PDEs (math.AP) #Asymptotically optimal algorithm #Combinatorics #Computer Science and Game Theory (cs.GT) #Computer science #De Bruijn graph #De Bruijn sequence #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Graph #Machine Learning (cs.LG) #Mathematical optimization #Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC) #Poisson distribution #Statistics #cs.GT #cs.LG #math.AP #math.OC #msc:35D40 #msc:49L25
paper · pdf · doi:10.48550/arxiv.2008.13703
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/08/31 · openalex publication_date 2020/08/31 · arxiv updated 2020/09/01 · openalex created_date 2022/07/26 · openalex updated_date 2026/08/06
We establish sharp asymptotically optimal strategies for the problem of\nonline prediction with history dependent experts. The prediction problem is\nplayed (in part) over a discrete graph called the d dimensional de Bruijn\ngraph, where d is the number of days of history used by the experts. Previous\nwork [11] established O(\ε) optimal strategies for n=2 experts and\nd\≤ 4 days of history, while [10] established O(\ε1/3)\noptimal strategies for all n\≥ 2 and all d\≥ 1, where the game is\nplayed for N steps and \ε=N-1/2. In this paper, we show that\nthe optimality conditions over the de Bruijn graph correspond to a graph\nPoisson equation, and we establish O(\ε) optimal strategies for all\nvalues of n and d.\n