High-Dimensional Sparse Linear Bandits
arXiv:2011.04020
Abstract
Stochastic linear bandits with high-dimensional sparse features are a practical model for a variety of domains, including personalized medicine and online advertising. We derive a novel dimension-free minimax regret lower bound for sparse linear bandits in the data-poor regime where the horizon is smaller than the ambient dimension and where the feature vectors admit a well-conditioned exploration distribution. This is complemented by a nearly matching upper bound for an explore-then-commit algorithm showing that that is the optimal rate in the data-poor regime. The results complement existing bounds for the data-rich regime and provide another example where carefully balancing the trade-off between information and regret is necessary. Finally, we prove a dimension-free regret upper bound under an additional assumption on the magnitude of the signal for relevant features.
arXiv commentAccepted by NeurIPS 2020
References in corpus (9)
- Simultaneous analysis of Lasso and Dantzig selector
- Confidence Intervals and Hypothesis Testing for High-Dimensional Regression
- Least squares after model selection in high-dimensional sparse models
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Doubly-Robust Lasso Bandit
- Simple Regret Minimization for Contextual Bandits
- Adaptive Exploration in Linear Contextual Bandit
- Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis
- Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit
Cited by in corpus (7)
- Near-optimal Representation Learning for Linear Bandits and Linear RL
- Bandit Algorithms for Precision Medicine
- 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
- Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
- Pareto Optimal Model Selection in Linear Bandits