Doubly-Robust Lasso Bandit

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_0(\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.

arXiv commentCorrections to previous version

References in corpus (7)

• Nearly unbiased variable selection under minimax concave penalty
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Simultaneous analysis of Lasso and Dantzig selector
• On the conditions used to prove oracle results for the Lasso
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Balanced Linear Contextual Bandits
• Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

Cited by in corpus (11)

• High-Dimensional Sparse Linear Bandits
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• Sparsity-Agnostic Lasso Bandit
• A Simple Unified Framework for High Dimensional Bandit Problems
• Thresholded Lasso Bandit
• Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity
• Regret Minimization in Isotonic, Heavy-Tailed Contextual Bandits via Adaptive Confidence Bands
• Doubly robust Thompson sampling for linear payoffs
• Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selection
• New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem
• Online Action Learning in High Dimensions: A Conservative Perspective