Asymptotically optimal strategies for online prediction with history-dependent experts

Abstract

We establish sharp asymptotically optimal strategies for the problem of online prediction with history dependent experts. The prediction problem is played (in part) over a discrete graph called the $d$ dimensional de Bruijn graph, where $d$ is the number of days of history used by the experts. Previous work [11] established $O(\epsilon )$ optimal strategies for $n=2$ experts and $d\le 4$ days of history, while [10] established $O({\epsilon }^{1/3})$ optimal strategies for all $n\ge 2$ and all $d\ge 1$, where the game is played for $N$ steps and $\epsilon =N^{-1/2}$. In this paper, we show that the optimality conditions over the de Bruijn graph correspond to a graph Poisson equation, and we establish $O(\epsilon )$ optimal strategies for all values of $n$ and $d$.