Prediction with Expert Advice: a PDE Perspective
This provides a continuum perspective on a known problem, offering theoretical insights but is incremental in applying existing PDE methods to this domain.
The paper tackles the classic online prediction with expert advice problem under adversarial conditions by characterizing the game's value as the viscosity solution of a nonlinear PDE, revealing minimax optimal strategies for both predictor and opponent.
This work addresses a classic problem of online prediction with expert advice. We assume an adversarial opponent, and we consider both the finite-horizon and random-stopping versions of this zero-sum, two-person game. Focusing on an appropriate continuum limit and using methods from optimal control, we characterize the value of the game as the viscosity solution of a certain nonlinear partial differential equation. The analysis also reveals the predictor's and the opponent's minimax optimal strategies. Our work provides, in particular, a continuum perspective on recent work of Gravin, Peres, and Sivan (Proc SODA 2016). Our techniques are similar to those of Kohn and Serfaty (Comm Pure Appl Math 2010), where scaling limits of some two-person games led to elliptic or parabolic PDEs.