A PDE approach for regret bounds under partial monitoring
This addresses the challenge of learning with limited feedback in sequential decision-making, but appears incremental as it builds on existing PDE-based methods for regret analysis.
The paper tackles the problem of deriving regret bounds for learning under partial monitoring by rescaling the problem to derive a limiting PDE on Wasserstein space, and shows that finding smooth sub/supersolutions of this PDE can yield regret bounds and efficient algorithms.
In this paper, we study a learning problem in which a forecaster only observes partial information. By properly rescaling the problem, we heuristically derive a limiting PDE on Wasserstein space which characterizes the asymptotic behavior of the regret of the forecaster. Using a verification type argument, we show that the problem of obtaining regret bounds and efficient algorithms can be tackled by finding appropriate smooth sub/supersolutions of this parabolic PDE.