# Bilinear Bandits with Low-rank Structure

arXiv: https://arxiv.org/abs/1901.02470 · HTML: https://mlsanity.com/paper/1901.02470/

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2019.

## Built on by (most cited first, 30 of 55)

- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Nearly Minimax Algorithms for Linear Bandits with Shared Representation](https://mlsanity.com/paper/2203.15664/) (2022)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Bandit Phase Retrieval](https://mlsanity.com/paper/2106.01660/) (2021)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning](https://mlsanity.com/paper/2406.05064/) (2024)
- [Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback](https://mlsanity.com/paper/2412.19436/) (2024)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits](https://mlsanity.com/paper/2410.02068/) (2024)
- [Multi-armed Bandit Algorithm against Strategic Replication](https://mlsanity.com/paper/2110.12160/) (2021)
- [On High-dimensional and Low-rank Tensor Bandits](https://mlsanity.com/paper/2305.03884/) (2023)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Context Uncertainty in Contextual Bandits with Applications to Recommender Systems](https://mlsanity.com/paper/2202.00805/) (2022)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Online Policy Learning and Inference by Matrix Completion](https://mlsanity.com/paper/2404.17398/) (2024)
- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)
- [Low-Rank Online Dynamic Assortment with Dual Contextual Information](https://mlsanity.com/paper/2404.17592/) (2024)
- [Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics](https://mlsanity.com/paper/2510.16208/) (2025)

## Abstract (arXiv)

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 d1 by d2 matrix Theta^* that defines the reward, and has low rank r ll mind1,d2. Determination of Theta^* 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((d1+d2)3/2 √r T) where widetildeO hides logarithmic factors and T is the time horizon, which improves upon the regret of widetildeO(d1d2√T) attained for a na"ive 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"ive linear bandit reduction.