Prediction with Expert Advice: A PDE Perspective

Nadejda Drenska, Robert V. Kohn

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)137-173
Number of pages37
JournalJournal of Nonlinear Science
Volume30
Issue number1
DOIs
StatePublished - Feb 1 2020

Keywords

  • Dynamic programming
  • Prediction with expert advice
  • Regret minimization
  • Two-person games
  • Viscosity solutions

ASJC Scopus subject areas

  • Modeling and Simulation
  • Engineering(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Prediction with Expert Advice: A PDE Perspective'. Together they form a unique fingerprint.

  • Cite this