Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications
This work provides a unified algorithmic solution for partial monitoring, impacting applications like dynamic pricing and bandit problems, though it is incremental as it builds on existing linear formulations.
The paper tackles the problem of sequential decision-making in partial monitoring by extending the linear formulation and showing that information-directed sampling (IDS) is nearly worst-case rate optimal for all finite-action games, with a unified analysis covering stochastic, contextual, and kernelized settings.
Partial monitoring is an expressive framework for sequential decision-making with an abundance of applications, including graph-structured and dueling bandits, dynamic pricing and transductive feedback models. We survey and extend recent results on the linear formulation of partial monitoring that naturally generalizes the standard linear bandit setting. The main result is that a single algorithm, information-directed sampling (IDS), is (nearly) worst-case rate optimal in all finite-action games. We present a simple and unified analysis of stochastic partial monitoring, and further extend the model to the contextual and kernelized setting.