Information Directed Sampling for Linear Partial Monitoring
Johannes Kirschner, Tor Lattimore, Andreas Krause
Subject areas: Bandit problems, Partial monitoring
Presented in: Session 2A, Session 2E
[Zoom link for poster in Session 2A], [Zoom link for poster in Session 2E]
Abstract:
Partial monitoring is a rich framework for sequential decision making under uncertainty that generalizes many well known bandit models, including linear, combinatorial and dueling bandits. We introduce information directed sampling (IDS) for stochastic partial monitoring with a linear reward and observation structure. IDS achieves adaptive worst-case regret rates that depend on precise observability conditions of the game. Moreover, we prove lower bounds that classify the minimax regret of all finite games into four possible regimes. IDS achieves the optimal rate in all cases up to logarithmic factors, without tuning any hyper-parameters. We further extend our results to the contextual and the kernelized setting, which significantly increases the range of possible applications.