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() optimal strategies for n=2 experts and d 4 days of history, while [10] established O(^1/3) optimal strategies for all n 2 and all d 1, where the game is played for N steps and =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() optimal strategies for all values of n and d.

Tasks

Reproductions