A PDE approach for regret bounds under partial monitoring

2022/09/02 by Erhan Bayraktar, Bayraktar, Erhan, Ibrahim Ekren +3 · 2 citations
Decision Sciences · Psychology · Social Sciences · #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Misinformation and Its Impacts #Optimism, Hope, and Well-being #Optimization and Control (math.OC) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2209.01256

openalex publication_date 2022/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Comparison for semi-continuous viscosity solutions for second order PDEs on the Wasserstein space
• Reasoning without Regret

Related

• PDE approach to the problem of online prediction with expert advice: a\n construction of potential-based strategies
• Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
• Explore First, Exploit Next: The True Shape of Regret in Bandit Problems
• Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
• On Theorem 2.3 in "Prediction, Learning, and Games" by Cesa-Bianchi and Lugosi