论文标题
与历史依赖专家的在线预测渐近最佳策略
Asymptotically optimal strategies for online prediction with history-dependent experts
论文作者
论文摘要
我们为与历史依赖专家的在线预测问题建立了敏锐的最佳策略。预测问题（部分）在一个称为$ d $ dimensional de bruijn图的离散图上播放，其中$ d $是专家使用的历史日数。以前的工作[11]建立了$ o（\ varepsilon）$ $ n = 2 $专家的最佳策略和$ d \ leq 4 $天的历史，而[10]建立了$ o（\ varepsilon^{1/3}）$最佳策略，用于所有$ n \ geq 2 $ d $ d $ d \ geq 1 $ n $ n $ n $ n $ n $ n $ n $ n $ $ \ varepsilon = n^{ - 1/2} $。在本文中，我们表明de bruijn图的最佳条件对应于图泊松方程，并为所有值$ n $和$ d $的$ o（\ varepsilon）$最佳策略建立。
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$.
