# Doubly-Robust Lasso Bandit

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2019.

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

- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Doubly robust Thompson sampling for linear payoffs](https://mlsanity.com/paper/2102.01229/) (2021)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (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)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Variance-Aware Sparse Linear Bandits](https://mlsanity.com/paper/2205.13450/) (2022)
- [Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit](https://mlsanity.com/paper/2109.11612/) (2021)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity](https://mlsanity.com/paper/2306.06291/) (2023)
- [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)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Meta-Learning Hypothesis Spaces for Sequential Decision-making](https://mlsanity.com/paper/2202.00602/) (2022)
- [Reward Imputation with Sketching for Contextual Batched Bandits](https://mlsanity.com/paper/2210.06719/) (2022)
- [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)
- [Lifelong Bandit Optimization: No Prior and No Regret](https://mlsanity.com/paper/2210.15513/) (2022)
- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization](https://mlsanity.com/paper/2605.10405/) (2026)
- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [Does Sparsity Help in Learning Misspecified Linear Bandits?](https://mlsanity.com/paper/2303.16998/) (2023)
- [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)
- [Low-Rank Online Dynamic Assortment with Dual Contextual Information](https://mlsanity.com/paper/2404.17592/) (2024)

## Abstract (arXiv)

Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, d. In many applications however, it is often the case that contexts are high-dimensional with only a sparse subset of size s0 (ll d) being correlated with the reward. We consider the stochastic linear contextual bandit problem and propose a novel algorithm, namely the Doubly-Robust Lasso Bandit algorithm, which exploits the sparse structure of the regression parameter as in Lasso, while blending the doubly-robust technique used in missing data literature. The high-probability upper bound of the regret incurred by the proposed algorithm does not depend on the number of arms and scales with log(d) instead of a polynomial function of d. The proposed algorithm shows good performance when contexts of different arms are correlated and requires less tuning parameters than existing methods.