Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case

DOI10.1002/CPA.22049MaRDI QIDQ6049541zbMATH OpenOpenAlexFDO

Authors Nadejda Drenska, Jeff Calder

Publication date 11 October 2023

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2008.00052

Mathematics Subject Classification ID

Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Dynamic programming (90C39) 2-person games (91A05)

Abstract: 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 $ngeq2$ 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 $Noinfty$ 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 $dleq4$ days of history. To appear in Communications on Pure and Applied Mathematics.

Recommendations

• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History‐Dependent Experts
• Prediction, Learning, and Games
• Asymptotically optimal strategies for online prediction with history-dependent experts
• Prediction with expert advice: a PDE perspective
• Finite-time 4-expert prediction problem

Cites work

• A decision-theoretic generalization of on-line learning and an application to boosting
• A deterministic-control-based approach to fully nonlinear parabolic and elliptic equations
• A deterministic‐control‐based approach motion by curvature
• A finite difference approach to the infinity Laplace equation and tug-of-war games
• Absolutely minimal Lipschitz extension of tree-valued mappings
• Asymptotically optimal strategies for online prediction with history-dependent experts
• How to use expert advice
• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• scientific article; zbMATH DE number 21887 (Why is no real title available?)
• scientific article; zbMATH DE number 5681750 (Why is no real title available?)
• On the asymptotic optimality of the comb strategy for prediction with expert advice
• Prediction with expert advice: a PDE perspective
• Prediction, Learning, and Games
• The limit shape of convex hull peeling
• The obstacle problem for the \(p\)-Laplacian via optimal stopping of tug-of-war games
• The weighted majority algorithm
• Towards optimal algorithms for prediction with expert advice
• Tug-of-War and Infinity Laplace Equation with Vanishing Neumann Boundary Condition
• Tug-of-war and the infinity Laplacian
• Tug-of-war with noise: a game-theoretic view of the \(p\)-Laplacian
• User’s guide to viscosity solutions of second order partial differential equations

Cited in

(4)

• Prediction with expert advice: a PDE perspective
• Asymptotically optimal strategies for online prediction with history-dependent experts
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History‐Dependent Experts
• Numerical solution of a PDE arising from prediction with expert advice

This page was built for publication: Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6049541)