Bilinear Bandits with Low-rank Structure

Abstract

We introduce the bilinear bandit problem with low-rank structure in which an action takes the form of a pair of arms from two different entity types, and the reward is a bilinear function of the known feature vectors of the arms. The unknown in the problem is a $d_1$ by $d_2$ matrix ${\mathbf{\Theta }}^{\ast }$ that defines the reward, and has low rank $r\ll \min \{d_1,d_2\}$. Determination of ${\mathbf{\Theta }}^{\ast }$ with this low-rank structure poses a significant challenge in finding the right exploration-exploitation tradeoff. In this work, we propose a new two-stage algorithm called "Explore-Subspace-Then-Refine" (ESTR). The first stage is an explicit subspace exploration, while the second stage is a linear bandit algorithm called "almost-low-dimensional OFUL" (LowOFUL) that exploits and further refines the estimated subspace via a regularization technique. We show that the regret of ESTR is $\tilde{\mathcal{O}}((d_1+d_2{)}^{3/2}\sqrt{rT})$ where $\tilde{\mathcal{O}}$ hides logarithmic factors and $T$ is the time horizon, which improves upon the regret of $\tilde{\mathcal{O}}(d_1{d}_2\sqrt{T})$ attained for a naïve linear bandit reduction. We conjecture that the regret bound of ESTR is unimprovable up to polylogarithmic factors, and our preliminary experiment shows that ESTR outperforms a naïve linear bandit reduction.

arXiv commentAccepted to ICML'19

References in corpus (9)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Online Clustering of Bandits
• Spectral bandits for smooth graph functions
• Online Stochastic Linear Optimization under One-bit Feedback
• Stochastic Low-Rank Bandits
• Hierarchical Exploration for Accelerating Contextual Bandits
• Structured Stochastic Linear Bandits
• Horde of Bandits using Gaussian Markov Random Fields

Cited by in corpus (3)

• Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Best Arm Identification in Graphical Bilinear Bandits