2020/09/17 by Wenhao Li, Li, Wenhao, Ningyuan Chen +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2009.08265
openalex publication_date 2020/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a contextual online learning (multi-armed bandit) problem with high-dimensional covariate x and decision y. The reward function to learn, f(x,y), does not have a particular parametric form. The literature has shown that the optimal regret is O(T(dx+dy+1)/(dx+dy+2)), where dx and dy are the dimensions of \mathbf x and \mathbf y, and thus it suffers from the curse of dimensionality. In many applications, only a small subset of variables in the covariate affect the value of f, which is referred to as sparsity in statistics. To take advantage of the sparsity structure of the covariate, we propose a variable selection algorithm called BV-LASSO, which incorporates novel ideas such as binning and voting to apply LASSO to nonparametric settings. Our algorithm achieves the regret O(T(dx^*+dy+1)/(dx^*+dy+2)), where dx^* is the effective covariate dimension. The regret matches the optimal regret when the covariate is d^*x-dimensional and thus cannot be improved. Our algorithm may serve as a general recipe to achieve dimension reduction via variable selection in nonparametric settings.