# Low-Rank Generalized Linear Bandit Problems

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

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

- [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)
- [Multi-task Representation Learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2202.10066/) (2022)
- [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)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [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)
- [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)
- [Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits](https://mlsanity.com/paper/2410.02068/) (2024)
- [On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure](https://mlsanity.com/paper/2211.15129/) (2022)
- [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)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [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)
- [Adaptive Sampling for Discovery](https://mlsanity.com/paper/2205.14829/) (2022)
- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)
- [A Complete Characterization of Learnability for Stochastic Noisy Bandits](https://mlsanity.com/paper/2410.09597/) (2024)
- [Leveraging semantic similarity for experimentation with AI-generated treatments](https://mlsanity.com/paper/2510.21119/) (2025)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)

## Abstract (arXiv)

In a low-rank linear bandit problem, the reward of an action (represented by a matrix of size d1 × d2) is the inner product between the action and an unknown low-rank matrix Theta^*. We propose an algorithm based on a novel combination of online-to-confidence-set conversion~citepabbasi2012online and the exponentially weighted average forecaster constructed by a covering of low-rank matrices. In T rounds, our algorithm achieves widetildeO((d1+d2)3/2√rT) regret that improves upon the standard linear bandit regret bound of widetildeO(d1d2√T) when the rank of Theta^*: r ll mind1,d2. We also extend our algorithmic approach to the generalized linear setting to get an algorithm which enjoys a similar bound under regularity conditions on the link function. To get around the computational intractability of covering based approaches, we propose an efficient algorithm by extending the "Explore-Subspace-Then-Refine" algorithm of~citetjun2019bilinear. Our efficient algorithm achieves widetildeO((d1+d2)3/2√rT) regret under a mild condition on the action set X and the r-th singular value of Theta^*. Our upper bounds match the conjectured lower bound of citejun2019bilinear for a subclass of low-rank linear bandit problems. Further, we show that existing lower bounds for the sparse linear bandit problem strongly suggest that our regret bounds are unimprovable. To complement our theoretical contributions, we also conduct experiments to demonstrate that our algorithm can greatly outperform the performance of the standard linear bandit approach when Theta^* is low-rank.