Information Directed Sampling for Linear Partial Monitoring
arXiv:2002.11182
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.
References in corpus (12)
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
- Bayesian Optimization with Gradients
- Information Directed Sampling and Bandits with Heteroscedastic Noise
- An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
- An Adaptive Algorithm for Finite Stochastic Partial Monitoring
- Exploiting gradients and Hessians in Bayesian optimization and Bayesian quadrature
- Exploration by Optimisation in Partial Monitoring
- Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring
- Adaptive Exploration in Linear Contextual Bandit
- Correlational Dueling Bandits with Application to Clinical Treatment in Large Decision Spaces
- Utility-based Dueling Bandits as a Partial Monitoring Game
Cited by in corpus (6)
- Asymptotically Optimal Information-Directed Sampling
- Reinforcement Learning, Bit by Bit
- Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
- Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
- Experimental Design for Regret Minimization in Linear Bandits
- Stochastic Linear Bandits with Protected Subspace