2020/09/04 by Yining Wang, Yi Chen, Wang, Yining +7 · 3 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics #Statistics Theory (math.ST) #cs.LG #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.2009.02003
54 pages, 4 figures
arxiv created 2020/09/04 · openalex publication_date 2020/09/04 · arxiv updated 2020/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(s√(T)) regret with high probability, which is nearly independent in the ``ambient'' regression model dimension d. We further attain a sharper O(√(sT)) regret by using the 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.