Asymptotically optimal strategies for online prediction with history-dependent experts
This provides a theoretical advancement in online learning algorithms for scenarios where predictions depend on historical data, though it appears incremental relative to prior work.
The paper tackles the problem of online prediction with history-dependent experts by establishing asymptotically optimal strategies, achieving an O(ε) optimality for all numbers of experts (n) and history days (d), improving upon previous O(ε^{1/3}) results.
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(\varepsilon)$ optimal strategies for $n=2$ experts and $d\leq 4$ days of history, while [10] established $O(\varepsilon^{1/3})$ optimal strategies for all $n\geq 2$ and all $d\geq 1$, where the game is played for $N$ steps and $\varepsilon=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(\varepsilon)$ optimal strategies for all values of $n$ and $d$.