Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

Abstract

We consider a linear stochastic bandit problem where the dimension $K$ of the unknown parameter $\theta$ is larger than the sampling budget $n$. In such cases, it is in general impossible to derive sub-linear regret bounds since usual linear bandit algorithms have a regret in $O(K\sqrt{n})$. In this paper we assume that $\theta$ is $S-$sparse, i.e. has at most $S-$non-zero components, and that the space of arms is the unit ball for the $||.|{|}_2$ norm. We combine ideas from Compressed Sensing and Bandit Theory and derive algorithms with regret bounds in $O(S\sqrt{n})$.

Cited by in corpus (17)

• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• Active Learning of Linear Embeddings for Gaussian Processes
• Doubly-Robust Lasso Bandit
• High-Dimensional Sparse Linear Bandits
• Bayesian Optimization in a Billion Dimensions via Random Embeddings
• A One-bit, Comparison-Based Gradient Estimator
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• A Simple Unified Framework for High Dimensional Bandit Problems
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Thresholded Lasso Bandit
• Sparsity-Agnostic Lasso Bandit
• Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selection
• Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case
• Pareto Optimal Model Selection in Linear Bandits
• Online Action Learning in High Dimensions: A Conservative Perspective
• Stochastic continuum armed bandit problem of few linear parameters in high dimensions
• Scalable Bayesian Optimization with Sparse Gaussian Process Models