论文标题
通过非参数变量选择，上下文在线学习的尺寸降低
Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selection
论文作者
论文摘要
我们考虑了上下文的在线学习（多臂强盗）问题，其中具有高维协变量$ \ MATHBF {X} $和决策$ \ Mathbf {y} $。学习的奖励功能，$ f（\ mathbf {x}，\ mathbf {y}）$，没有特定的参数形式。 The literature has shown that the optimal regret is $\tilde{O}(T^{(d_x+d_y+1)/(d_x+d_y+2)})$, where $d_x$ and $d_y$ are the dimensions of $\mathbf x$ and $\mathbf y$, and thus it suffers from the curse of dimensionality.在许多应用程序中，协变量中只有一小部分变量会影响$ f $的值，$ f $的值被称为统计信息中的\ textit {sparsity}。为了利用协变量的稀疏结构，我们提出了一种称为\ textit {bv-lasso}的可变选择算法，该算法结合了新颖的想法，例如binning和投票，将套索应用于非参数设置。我们的算法实现了后悔的$ \ tilde {o}（t^{（d_x^*+d_y+1）/（d_x^*+d_y+2）}）$，其中$ d_x^*$是有效的协变量尺寸。当协变量为$ d^*_ x $维度时，遗憾与最佳的遗憾相匹配，因此无法改善。我们的算法可以作为一般配方，以通过非参数设置中的可变选择实现尺寸降低。
We consider a contextual online learning (multi-armed bandit) problem with high-dimensional covariate $\mathbf{x}$ and decision $\mathbf{y}$. The reward function to learn, $f(\mathbf{x},\mathbf{y})$, does not have a particular parametric form. The literature has shown that the optimal regret is $\tilde{O}(T^{(d_x+d_y+1)/(d_x+d_y+2)})$, where $d_x$ and $d_y$ 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 \textit{sparsity} in statistics. To take advantage of the sparsity structure of the covariate, we propose a variable selection algorithm called \textit{BV-LASSO}, which incorporates novel ideas such as binning and voting to apply LASSO to nonparametric settings. Our algorithm achieves the regret $\tilde{O}(T^{(d_x^*+d_y+1)/(d_x^*+d_y+2)})$, where $d_x^*$ 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.
