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,...

Full description

Saved in:
Bibliographic Details
Published in:Journal of nonlinear science 2020-02, Vol.30 (1), p.137-173
Main Authors: Drenska, Nadejda, Kohn, Robert V.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Applications of mathematics
Classical Mechanics
Control methods
Economic Theory/Quantitative Economics/Mathematical Methods
Mathematical and Computational Engineering
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Minimax technique
Nonlinear differential equations
Optimal control
Parabolic differential equations
Partial differential equations
Theoretical
Zero sum games
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0938-8974
1432-1467
DOI:10.1007/s00332-019-09570-3