# Thresholded Lasso Bandit

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

## Key facts

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

## Built on by (most cited first, 16 of 16)

- [Multi-task Representation Learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2202.10066/) (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)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks](https://mlsanity.com/paper/2311.13180/) (2023)
- [Sparsity-Agnostic Linear Bandits with Adaptive Adversaries](https://mlsanity.com/paper/2406.01192/) (2024)
- [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)
- [Reward-Relevance-Filtered Linear Offline Reinforcement Learning](https://mlsanity.com/paper/2401.12934/) (2024)
- [Cooperative Thresholded Lasso for Sparse Linear Bandit](https://mlsanity.com/paper/2305.19161/) (2023)
- [Differentially Private High Dimensional Bandits](https://mlsanity.com/paper/2402.03737/) (2024)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Anomaly Detection in Networked Bandits](https://mlsanity.com/paper/2508.20076/) (2025)

## Abstract (arXiv)

In this paper, we revisit the regret minimization problem in sparse stochastic contextual linear bandits, where feature vectors may be of large dimension d, but where the reward function depends on a few, say s0ll d, of these features only. We present Thresholded Lasso bandit, an algorithm that (i) estimates the vector defining the reward function as well as its sparse support, i.e., significant feature elements, using the Lasso framework with thresholding, and (ii) selects an arm greedily according to this estimate projected on its support. The algorithm does not require prior knowledge of the sparsity index s0 and can be parameter-free under some symmetric assumptions. For this simple algorithm, we establish non-asymptotic regret upper bounds scaling as O( log d + √T ) in general, and as O( log d + log T) under the so-called margin condition (a probabilistic condition on the separation of the arm rewards). The regret of previous algorithms scales as O( log d + √T log (d T)) and O( log T log d) in the two settings, respectively. Through numerical experiments, we confirm that our algorithm outperforms existing methods.