mlsanityData to 7 Oct 2026

Sparsity-Agnostic Lasso Bandit

arXiv 2007.08477 ↗First posted 16 Jul 2020stat.ML cs.LGcited by 44

Not on the map. Why?

Abstract (arXiv)

We consider a stochastic contextual bandit problem where the dimension d of the feature vectors is potentially large, however, only a sparse subset of features of cardinality s0 ll d affect the reward function. Essentially all existing algorithms for sparse bandits require a priori knowledge of the value of the sparsity index s0. This knowledge is almost never available in practice, and misspecification of this parameter can lead to severe deterioration in the performance of existing methods. The main contribution of this paper is to propose an algorithm that does not require prior knowledge of the sparsity index s0 and establish tight regret bounds on its performance under mild conditions. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms existing methods, even when the correct sparsity index is revealed to them but is kept hidden from our algorithm.

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 10; 2023: 12; 2024: 6; 2025: 10; 2026: 2.

44 papers.

Sort:

By area:

  1. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  2. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  3. 2021Multinomial Logit Contextual Bandits: Provable Optimality and Practicalitycited by 21
  4. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  5. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  6. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  7. 2022Contextual Information-Directed Samplingcited by 16
  8. 2022Thompson Sampling for High-Dimensional Sparse Linear Contextual Banditscited by 16
  9. 2022Variance-Aware Sparse Linear Banditscited by 11
  10. 2021Model Selection for Generic Contextual Banditscited by 7
  11. 2023Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneitycited by 7
  12. 2022Meta Representation Learning with Contextual Linear Banditscited by 6
32 more
  1. 2022Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Banditscited by 6
  2. 2023Semi-parametric inference based on adaptively collected datacited by 6
  3. 2023Anytime Model Selection in Linear Banditscited by 6
  4. 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 6
  5. 2023High-dimensional Contextual Bandit Problem without Sparsitycited by 5
  6. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  7. 2022Federated Online Sparse Decision Makingcited by 3
  8. 2023A Doubly Robust Approach to Sparse Reinforcement Learningcited by 3
  9. 2023High-dimensional Linear Bandits with Knapsackscited by 3
  10. 2025Linear Bandits with Partially Observable Featurescited by 3
  11. 2022High dimensional stochastic linear contextual bandit with missing covariatescited by 2
  12. 2023Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedbackcited by 2
  13. 2024Sparsity-Agnostic Linear Bandits with Adaptive Adversariescited by 2
  14. 2024Minimax Optimality in Contextual Dynamic Pricing with General Valuation Modelscited by 2
  15. 2022Advertising Media and Target Audience Optimization via High-dimensional Banditscited by 1
  16. 2023Stochastic Contextual Bandits with Long Horizon Rewardscited by 1
  17. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  18. 2023New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problemcited by 1
  19. 2024Symmetric Linear Bandits with Hidden Symmetrycited by 1
  20. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  21. 2025A Unified Regularization Approach to High-Dimensional Generalized Tensor Banditscited by 1
  22. 2025High-dimensional Nonparametric Contextual Bandit Problemcited by 1
  23. 2025Leveraging semantic similarity for experimentation with AI-generated treatmentscited by 1
  24. 2025Sparse Optimistic Information Directed Samplingcited by 1
  25. 2023Cooperative Thresholded Lasso for Sparse Linear Banditcited by 0
  26. 2024Differentially Private High Dimensional Banditscited by 0
  27. 2025Parameter-Adaptive Dynamic Pricingcited by 0
  28. 2025Sparse Nonparametric Contextual Banditscited by 0
  29. 2025Anomaly Detection in Networked Banditscited by 0
  30. 2025Navigating Sparsities in High-Dimensional Linear Contextual Banditscited by 0
  31. 2025Infrequent Exploration in Linear Banditscited by 0
  32. 2026Learning to Sparsify Stochastic Linear Banditscited by 0