An Information-Theoretic Analysis of Thompson Sampling
arXiv:1403.5341
Abstract
We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.
References in corpus (7)
- Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Further Optimal Regret Bounds for Thompson Sampling
- Generalized Thompson Sampling for Contextual Bandits
- Learning to Optimize Via Posterior Sampling
- Thompson Sampling for Complex Bandit Problems
Cited by in corpus (11)
- Bayesian Reinforcement Learning: A Survey
- Bao: Learning to Steer Query Optimizers
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
- Multi-scale exploration of convex functions and bandit convex optimization
- Multimodal Hierarchical Dirichlet Process-based Active Perception
- Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay
- Output-Weighted Sampling for Multi-Armed Bandits with Extreme Payoffs
- Bandit Convex Optimization: sqrt{T} Regret in One Dimension
- TSEB: More Efficient Thompson Sampling for Policy Learning
- Efficient Online Decision Tree Learning with Active Feature Acquisition