# Sparsity-Agnostic Lasso Bandit

arXiv: https://arxiv.org/abs/2007.08477 · HTML: https://mlsanity.com/paper/2007.08477/

## Key facts

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

## Built on by (most cited first, 30 of 44)

- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Multi-task Representation Learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2202.10066/) (2022)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Variance-Aware Sparse Linear Bandits](https://mlsanity.com/paper/2205.13450/) (2022)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Semi-parametric inference based on adaptively collected data](https://mlsanity.com/paper/2303.02534/) (2023)
- [Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity](https://mlsanity.com/paper/2306.06291/) (2023)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Meta Representation Learning with Contextual Linear Bandits](https://mlsanity.com/paper/2205.15100/) (2022)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [High-dimensional Contextual Bandit Problem without Sparsity](https://mlsanity.com/paper/2306.11017/) (2023)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [A Doubly Robust Approach to Sparse Reinforcement Learning](https://mlsanity.com/paper/2310.15286/) (2023)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [High dimensional stochastic linear contextual bandit with missing covariates](https://mlsanity.com/paper/2207.11165/) (2022)
- [Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13791/) (2023)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models](https://mlsanity.com/paper/2406.17184/) (2024)
- [Leveraging semantic similarity for experimentation with AI-generated treatments](https://mlsanity.com/paper/2510.21119/) (2025)
- [Advertising Media and Target Audience Optimization via High-dimensional Bandits](https://mlsanity.com/paper/2209.08403/) (2022)
- [Stochastic Contextual Bandits with Long Horizon Rewards](https://mlsanity.com/paper/2302.00814/) (2023)
- [Fixed-Budget Best-Arm Identification in Sparse Linear Bandits](https://mlsanity.com/paper/2311.00481/) (2023)

## 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.