# Asymptotically optimal strategies for online prediction with history-dependent experts

arXiv: https://arxiv.org/abs/2008.13703 · HTML: https://mlsanity.com/paper/2008.13703/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2020.

## Built on by (most cited first, 4 of 4)

- [A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit](https://mlsanity.com/paper/2202.05767/) (2022)
- [Numerical solution of a PDE arising from prediction with expert advice](https://mlsanity.com/paper/2406.05754/) (2024)
- [An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB](https://mlsanity.com/paper/2609.14892/) (2026)
- [On prediction from expert advice with more than five experts](https://mlsanity.com/paper/2610.05186/) (2026)

## Abstract (arXiv)

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≤ 4 days of history, while [10] established O(varepsilon1/3) optimal strategies for all n≥ 2 and all d≥ 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.