Online Prediction with History-Dependent Experts: The General Case

Nadejda Drenska, Jeff Calder

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 (Figure presented.) 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 (Figure presented.) at a rate of (Figure presented.) 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 [14] for (Figure presented.) experts and (Figure presented.) days of history.

Original languageEnglish (US)
Pages (from-to)1678-1727
Number of pages50
JournalCommunications on Pure and Applied Mathematics
Issue number9
StatePublished - Sep 2023

Bibliographical note

Publisher Copyright:
© 2022 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC.


Dive into the research topics of 'Online Prediction with History-Dependent Experts: The General Case'. Together they form a unique fingerprint.

Cite this