mlsanityData to 7 Oct 2026

High-Dimensional Sparse Linear Bandits

arXiv 2011.04020 ↗First posted 8 Nov 2020stat.ML cs.LG math.STcited by 61

Not on the map. Why?

Abstract (arXiv)

Stochastic linear bandits with high-dimensional sparse features are a practical model for a variety of domains, including personalized medicine and online advertising. We derive a novel Omega(n2/3) dimension-free minimax regret lower bound for sparse linear bandits in the data-poor regime where the horizon is smaller than the ambient dimension and where the feature vectors admit a well-conditioned exploration distribution. This is complemented by a nearly matching upper bound for an explore-then-commit algorithm showing that that Theta(n2/3) is the optimal rate in the data-poor regime. The results complement existing bounds for the data-rich regime and provide another example where carefully balancing the trade-off between information and regret is necessary. Finally, we prove a dimension-free O(√n) regret upper bound under an additional assumption on the magnitude of the signal for relevant features.

Key facts. Cited by 61 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 12; 2023: 11; 2024: 13; 2025: 13; 2026: 4.

61 papers.

Sort:

By area:

  1. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  2. 2021Neural Contextual Bandits without Regretcited by 40
  3. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  4. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  5. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  6. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  7. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  8. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  9. 2022Contextual Information-Directed Samplingcited by 16
  10. 2022Thompson Sampling for High-Dimensional Sparse Linear Contextual Banditscited by 16
  11. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  12. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
38 more
  1. 2021Bandit Algorithms for Precision Medicinecited by 12
  2. 2022Variance-Aware Sparse Linear Banditscited by 11
  3. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 9
  4. 2022Distributed Linear Bandits under Communication Constraintscited by 8
  5. 2023Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricingcited by 8
  6. 2024Multi-Armed Bandits with Network Interferencecited by 8
  7. 2023Nearly Minimax Optimal Submodular Maximization with Bandit Feedbackcited by 7
  8. 2023Anytime Model Selection in Linear Banditscited by 6
  9. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  10. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  11. 2022Meta-Learning Hypothesis Spaces for Sequential Decision-makingcited by 5
  12. 2023High-dimensional Contextual Bandit Problem without Sparsitycited by 5
  13. 2024Linear Causal Bandits: Unknown Graph and Soft Interventionscited by 5
  14. 2025Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interferencecited by 5
  15. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  16. 2022Federated Online Sparse Decision Makingcited by 3
  17. 2022Lifelong Bandit Optimization: No Prior and No Regretcited by 3
  18. 2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3
  19. 2023Contextual Dynamic Pricing with Strategic Buyerscited by 3
  20. 2023Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inferencecited by 3
  21. 2023A Doubly Robust Approach to Sparse Reinforcement Learningcited by 3
  22. 2023High-dimensional Linear Bandits with Knapsackscited by 3
  23. 2024Tree Search-Based Evolutionary Bandits for Protein Sequence Optimizationcited by 3
  24. 2024Online Policy Learning and Inference by Matrix Completioncited by 3
  25. 2025Linear Bandits with Partially Observable Featurescited by 3
  26. 2022Bandit Theory and Thompson Sampling-Guided Directed Evolution for Sequence Optimizationcited by 2
  27. 2024Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraintscited by 2
  28. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  29. 2024Sparsity-Agnostic Linear Bandits with Adaptive Adversariescited by 2
  30. 2022Advertising Media and Target Audience Optimization via High-dimensional Banditscited by 1
  31. 2023Stochastic Contextual Bandits with Long Horizon Rewardscited by 1
  32. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  33. 2024Symmetric Linear Bandits with Hidden Symmetrycited by 1
  34. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  35. 2025A Unified Regularization Approach to High-Dimensional Generalized Tensor Banditscited by 1
  36. 2025High-dimensional Nonparametric Contextual Bandit Problemcited by 1
  37. 2025Optimization of Epsilon-Greedy Explorationcited by 1
  38. 2025On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-ballscited by 1

50 most cited of 61 All 61 (JSON)