Prediction with Expert Advice: A PDE Perspective

摘要

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 et al. (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, SODA '16, (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2016). Our techniques are similar to those of Kohn and Serfaty (Commun Pure Appl Math 63(10):1298-1350, 2010), where scaling limits of some two-person games led to elliptic or parabolic PDEs.