Stochastic Linear Bandits with Hidden Low Rank Structure
Stochastic Linear Bandits with Hidden Low Rank Structure
复制标题
具有隐藏低阶结构的随机线性强盗
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
B. Hassibi
中科院分区：
文献类型：
--
作者：
Sahin Lale;K. Azizzadenesheli;Anima Anandkumar;B. Hassibi
高维表示通常具有较低维的底层结构。在许多决策环境中尤其如此。例如，当动作的表示是从深度神经网络生成时，可以合理地预期低秩结构，而稀疏性等传统结构不再有效。子空间恢复方法，例如主成分分析（PCA），可以找到特征空间中潜在的低秩结构，并降低学习任务的复杂性。在这项工作中，我们提出了投影随机线性强盗（PSLB），这是一种当动作表示具有底层低维子空间结构时的高维随机线性强盗（SLB）算法。 PSLB 部署基于 PCA 的投影来迭代查找 SLB 中的低秩结构。我们证明，部署投影方法可以确保降维，并导致更严格的遗憾上限，即子空间的维数及其属性，而不是环境空间的维数。我们将图像分类任务修改为 SLB 设置，并凭经验表明，当预训练的 DNN 提供高维特征表示时，与最先进的算法相比，部署 PSLB 可以显着减少遗憾并更快地收敛到准确的模型。
High-dimensional representations often have a lower dimensional underlying structure. This is particularly the case in many decision making settings. For example, when the representation of actions is generated from a deep neural network, it is reasonable to expect a low-rank structure whereas conventional structures like sparsity are not valid anymore. Subspace recovery methods, such as Principle Component Analysis (PCA) can find the underlying low-rank structures in the feature space and reduce the complexity of the learning tasks. In this work, we propose Projected Stochastic Linear Bandit (PSLB), an algorithm for high dimensional stochastic linear bandits (SLB) when the representation of actions has an underlying low-dimensional subspace structure. PSLB deploys PCA based projection to iteratively find the low rank structure in SLBs. We show that deploying projection methods assures dimensionality reduction and results in a tighter regret upper bound that is in terms of the dimensionality of the subspace and its properties, rather than the dimensionality of the ambient space. We modify the image classification task into the SLB setting and empirically show that, when a pre-trained DNN provides the high dimensional feature representations, deploying PSLB results in significant reduction of regret and faster convergence to an accurate model compared to state-of-art algorithm.