Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selection

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 tildeO(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 textitsparsity in statistics. To take advantage of the sparsity structure of the covariate, we propose a variable selection algorithm called textitBV-LASSO, which incorporates novel ideas such as binning and voting to apply LASSO to nonparametric settings. Our algorithm achieves the regret tildeO(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.