Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection

Abstract

We consider the stochastic contextual bandit problem under the high dimensional linear model. We focus on the case where the action space is finite and random, with each action associated with a randomly generated contextual covariate. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. However, it is very challenging as we need to balance exploration and exploitation. We propose doubly growing epochs and estimating the parameter using the best subset selection method, which is easy to implement in practice. This approach achieves $\tilde{\mathcal{O}}(s\sqrt{T})$ regret with high probability, which is nearly independent in the ``ambient'' regression model dimension $d$. We further attain a sharper $\tilde{\mathcal{O}}(\sqrt{sT})$ regret by using the \textsc{SupLinUCB} framework and match the minimax lower bound of low-dimensional linear stochastic bandit problems. Finally, we conduct extensive numerical experiments to demonstrate the applicability and robustness of our algorithms empirically.

arXiv comment54 pages, 4 figures

References in corpus (5)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Simultaneous analysis of Lasso and Dantzig selector
• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits

Cited by in corpus (3)

• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Online Sparse Reinforcement Learning
• Information Directed Sampling for Sparse Linear Bandits