by , ,
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 introduceinformation 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.
Reference:
Information Directed Sampling for Linear Partial Monitoring J. Kirschner, T. Lattimore, A. KrauseIn Proc. Conference on Learning Theory (COLT), 2020
Bibtex Entry:
@inproceedings{kirschner20partialmonitoring,
	author = {Johannes Kirschner and Tor Lattimore and Andreas Krause},
	booktitle = {Proc. Conference on Learning Theory (COLT)},
	month = {July},
	title = {Information Directed Sampling for Linear Partial Monitoring},
	year = {2020}}