Efficient Sparse Linear Bandits under High Dimensional Data

We propose a computationally efficient Lasso Random Project Bandit (LRP-Bandit) algorithm for sparse linear bandit problems under high-dimensional settings with limited samples. LRP-Bandit bridges Lasso and Random Projection as feature selection and dimension reduction techniques to alleviate the computational complexity and improve the regret performance. We demonstrate that for the total feature dimension d, the significant feature dimension s, and the sample size T, the expected cumulative regret under LRP-Bandit is upper bounded by Õ (T2 over 3 s 3 over 2 log7 over 6 d), where Õ suppresses the logarithmic dependence on T. Further, we show that when available samples are larger than a problem-dependent threshold, the regret upper bound for LRP-Bandit can be further improved to Õ (s√T log d). These regret upper bounds on T for both data-poor and data-rich regimes match the theoretical minimax lower bounds up to logarithmic factors. Through experiments, we show that LRP-Bandit is computationally efficient and outperforms other benchmarks on the expected cumulative regret.