Information Directed Sampling for Sparse Linear Bandits
arXiv:2105.14267
Abstract
Stochastic sparse linear bandits offer a practical model for high-dimensional online decision-making problems and have a rich information-regret structure. In this work we explore the use of information-directed sampling (IDS), which naturally balances the information-regret trade-off. We develop a class of information-theoretic Bayesian regret bounds that nearly match existing lower bounds on a variety of problem instances, demonstrating the adaptivity of IDS. To efficiently implement sparse IDS, we propose an empirical Bayesian approach for sparse posterior sampling using a spike-and-slab Gaussian-Laplace prior. Numerical results demonstrate significant regret reductions by sparse IDS relative to several baselines.
References in corpus (12)
- Confidence Intervals and Hypothesis Testing for High-Dimensional Regression
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Minimal Exploration in Structured Stochastic Bandits
- Spike-and-Slab Meets LASSO: A Review of the Spike-and-Slab LASSO
- An Information-Theoretic Analysis for Thompson Sampling with Many Actions
- Information Directed Sampling for Stochastic Bandits with Graph Feedback
- Mirror Descent and the Information Ratio
- Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
- Sparsity-Agnostic Lasso Bandit
- First-Order Bayesian Regret Analysis of Thompson Sampling
- Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection