Doubly-Robust Lasso Bandit

2019/07/26 by Gi-Soo Kim, Myunghee Cho Paik, Kim, Gi-Soo +1 · 5 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1907.11362

Corrections to previous version

openalex publication_date 2019/07/26 · arxiv created 2020/02/13 · arxiv updated 2020/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

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 s₀ (≪ 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.

Citations

• Nearly unbiased variable selection under minimax concave penalty
• Estimation of Regression Coefficients When Some Regressors are not Always Observed
• Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit
• Doubly Robust Estimation in Missing Data and Causal Inference Models
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Balanced Linear Contextual Bandits

Cited by

• Sparse Optimistic Information Directed Sampling
• Navigating Sparsities in High-Dimensional Linear Contextual Bandits
• Adaptive Data Augmentation for Thompson Sampling
• Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions
• High-dimensional Nonparametric Contextual Bandit Problem

Related

• Thresholded Lasso Bandit
• Lasso Bandit with Compatibility Condition on Optimal Arm
• Sparsity-Agnostic Lasso Bandit
• A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem
• High dimensional stochastic linear contextual bandit with missing covariates