mlsanityData to 7 Oct 2026

Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits

arXiv 2211.05964 ↗First posted 11 Nov 2022stat.ML cs.LG math.STcited by 16

Not on the map. Why?

Abstract (arXiv)

We consider the stochastic linear contextual bandit problem with high-dimensional features. We analyze the Thompson sampling algorithm using special classes of sparsity-inducing priors (e.g., spike-and-slab) to model the unknown parameter and provide a nearly optimal upper bound on the expected cumulative regret. To the best of our knowledge, this is the first work that provides theoretical guarantees of Thompson sampling in high-dimensional and sparse contextual bandits. For faster computation, we use variational inference instead of Markov Chain Monte Carlo (MCMC) to approximate the posterior distribution. Extensive simulations demonstrate the improved performance of our proposed algorithm over existing ones.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 16 of its 52 references that are in the map. First posted on arXiv 11 Nov 2022.

Builds on

16 of 52 references.

References · 16

  1. 2020High-Dimensional Sparse Linear Banditscited by 61
  2. 2019Doubly-Robust Lasso Banditcited by 49
  3. 2019Variational Bayes for high-dimensional linear regression with sparse priorscited by 44
  4. 2020Sparsity-Agnostic Lasso Banditcited by 44
  5. 2014Bayesian linear regression with sparse priorscited by 40
  6. 2020Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Banditscited by 28
  7. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  8. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  9. 2015On the Computational Complexity of High-Dimensional Bayesian Variable Selectioncited by 18
  10. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  11. 2020Thresholded Lasso Banditcited by 16
  12. 2022Contextual Information-Directed Samplingcited by 16
4 more
  1. 2020Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selectioncited by 12
  2. 2018Efficient Linear Bandits through Matrix Sketchingcited by 11
  3. 2021Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Banditcited by 8
  4. 2020Online Batch Decision-Making with High-Dimensional Covariatescited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 5; 2026: 2.

16 papers.

Sort:

  1. 2024Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlocited by 10
  2. 2023Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneitycited by 7
  3. 2024Thompson Sampling in Partially Observable Contextual Banditscited by 5
  4. 2025Linear Bandits with Partially Observable Featurescited by 3
  5. 2024Sparsity-Agnostic Linear Bandits with Adaptive Adversariescited by 2
  6. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  7. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  8. 2024Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regretcited by 1
  9. 2025On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-ballscited by 1
  10. 2025Sparse Optimistic Information Directed Samplingcited by 1
  11. 2023Efficiently Tackling Million-Dimensional Multiobjective Problems: A Direction Sampling and Fine-Tuning Approachcited by 0
  12. 2024Sparse Linear Bandits with Blocking Constraintscited by 0
4 more
  1. 2025Sparse Nonparametric Contextual Banditscited by 0
  2. 2025Navigating Sparsities in High-Dimensional Linear Contextual Banditscited by 0
  3. 2026Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approachcited by 0
  4. 2026Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Samplingcited by 0