CaltechAUTHORS
  A Caltech Library Service

Stochastic Linear Bandits with Hidden Low Rank Structure

Lale, Sahin and Azizzadenesheli, Kamyar and Anandkumar, Anima and Hassibi, Babak (2019) Stochastic Linear Bandits with Hidden Low Rank Structure. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20190327-085817695

[img] PDF - Submitted Version
See Usage Policy.

4Mb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190327-085817695

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1901.09490arXivDiscussion Paper
Record Number:CaltechAUTHORS:20190327-085817695
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190327-085817695
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94182
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:28 Mar 2019 15:08
Last Modified:28 Mar 2019 15:08

Repository Staff Only: item control page