Bilinear Bandits with Low-rank Structure

2019/01/08 by Kwang-Sung Jun, Jun, Kwang-Sung, Rebecca Willett +5 · 6 citations
Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Wireless Network Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1901.02470

openalex publication_date 2019/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

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₁ by d₂ matrix \mathbfΘ^* that defines the reward, and has low rank r ≪ min\d₁,d₂\. Determination of \mathbfΘ^* 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 \widetildeO((d₁+d₂)^3/2 √(r T)) where \widetildeO hides logarithmic factors and T is the time horizon, which improves upon the regret of \widetildeO(d₁d₂√(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.

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Stochastic Low-Rank Bandits

Cited by

• Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics
• Leveraging semantic similarity for experimentation with AI-generated treatments
• Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits
• Impact of Connectivity on Laplacian Representations in Reinforcement Learning
• Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
• Generalized Low-Rank Matrix Contextual Bandits with Graph Information

Related

• Low-Rank Generalized Linear Bandit Problems
• Low-rank Matrix Bandits with Heavy-tailed Rewards
• Linear Bandits with Partially Observable Features
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery
• Minimal Exploration in Structured Stochastic Bandits