PDE approach to the problem of online prediction with expert advice: a construction of potential-based strategies
This work addresses the problem of regret minimization in online learning for forecasters, but it appears incremental as it builds on existing potential function methods.
The authors tackled the problem of online prediction with expert advice by constructing potential-based strategies using a PDE approach, resulting in a conventional upper bound for worst-case regret justified by a verification argument.
We consider a sequence of repeated prediction games and formally pass to the limit. The supersolutions of the resulting non-linear parabolic partial differential equation are closely related to the potential functions in the sense of N.\,Cesa-Bianci, G.\,Lugosi (2003). Any such supersolution gives an upper bound for forecaster's regret and suggests a potential-based prediction strategy, satisfying the Blackwell condition. A conventional upper bound for the worst-case regret is justified by a simple verification argument.