mlsanityData to 14 Oct 2026

Information Directed Sampling for Sparse Linear Bandits

arXiv 2105.14267 ↗First posted 29 May 2021stat.ML cs.LG math.STcited by 20

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 29 of its 59 references that are in the map. First posted on arXiv 29 May 2021.

Builds on

29 of 59 references.

References · 29

  1. 2013Learning to Optimize Via Posterior Samplingcited by 256
  2. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  4. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  5. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  6. 2013Confidence Intervals and Hypothesis Testing for High-Dimensional Regressioncited by 79
  7. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  8. 2017Ensemble Samplingcited by 62
  9. 2020High-Dimensional Sparse Linear Banditscited by 61
  10. 2021Reinforcement Learning, Bit by Bitcited by 59
  11. 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
  12. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 49
17 more
  1. 2019Doubly-Robust Lasso Banditcited by 49
  2. 2020Sparsity-Agnostic Lasso Banditcited by 44
  3. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  4. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 42
  5. 2017Minimal Exploration in Structured Stochastic Banditscited by 41
  6. 2020Information Directed Sampling for Linear Partial Monitoringcited by 40
  7. 2020Mirror Descent and the Information Ratiocited by 40
  8. 2018An Information-Theoretic Analysis for Thompson Sampling with Many Actionscited by 35
  9. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  10. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  11. 2020Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Banditscited by 28
  12. 2020Online Sparse Reinforcement Learningcited by 25
  13. 2017Information Directed Sampling for Stochastic Bandits with Graph Feedbackcited by 24
  14. 2019An Adaptive Empirical Bayesian Method for Sparse Deep Learningcited by 20
  15. 2019First-Order Bayesian Regret Analysis of Thompson Samplingcited by 17
  16. 2020Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selectioncited by 12
  17. 2020Spike-and-Slab Meets LASSO: A Review of the Spike-and-Slab LASSOcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 7; 2023: 5; 2024: 5; 2025: 2; 2026: 1.

20 papers.

Sort:

By area:

  1. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  2. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  3. 2022Contextual Information-Directed Samplingcited by 16
  4. 2022Thompson Sampling for High-Dimensional Sparse Linear Contextual Banditscited by 16
  5. 2023Leveraging Demonstrations to Improve Online Learning: Quality Matterscited by 13
  6. 2022Variance-Aware Sparse Linear Banditscited by 11
  7. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  8. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  9. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  10. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  11. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  12. 2022Adaptive Sampling for Discoverycited by 2
8 more
  1. 2022Uplifting Banditscited by 2
  2. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysiscited by 2
  3. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  4. 2023Stochastic Contextual Bandits with Long Horizon Rewardscited by 1
  5. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  6. 2025Sparse Optimistic Information Directed Samplingcited by 1
  7. 2023Thompson Sampling for Linear Bandit Problems with Normal-Gamma Priorscited by 0
  8. 2026Future Information-Directed Sampling for Bayesian Nonstationary Banditscited by 0