# Online Prediction With History-Dependent Experts: The General Case

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

## Key facts

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

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

- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [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)
- [Online Learning with Bounded Recall](https://mlsanity.com/paper/2205.14519/) (2022)
- [On prediction from expert advice with more than five experts](https://mlsanity.com/paper/2610.05186/) (2026)

## Abstract (arXiv)

We study the problem of prediction of binary sequences with expert advice in the online setting, which is a classic example of online machine learning. We interpret the binary sequence as the price history of a stock, and view the predictor as an investor, which converts the problem into a stock prediction problem. In this framework, an investor, who predicts the daily movements of a stock, and an adversarial market, who controls the stock, play against each other over N turns. The investor combines the predictions of n≥ 2 experts in order to make a decision about how much to invest at each turn, and aims to minimize their regret with respect to the best-performing expert at the end of the game. We consider the problem with history-dependent experts, in which each expert uses the previous d days of history of the market in making their predictions. We prove that the value function for this game, rescaled appropriately, converges as N→ ∞ at a rate of O(N-1/6) to the viscosity solution of a nonlinear degenerate elliptic PDE, which can be understood as the Hamilton-Jacobi-Issacs equation for the two-person game. As a result, we are able to deduce asymptotically optimal strategies for the investor. Our results extend those established by the first author and R.V.Kohn [13] for n=2 experts and d≤ 4 days of history. To appear in Communications on Pure and Applied Mathematics.