# Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 49 references that are in the map.
- First posted on arXiv 14 Jan 2024.

## Builds on (most cited first, 13 of 13)

- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries](https://mlsanity.com/paper/1605.07129/) (2016)
- [Generalized High-Dimensional Trace Regression via Nuclear Norm Regularization](https://mlsanity.com/paper/1710.08083/) (2017)
- [Low-rank Bandits with Latent Mixtures](https://mlsanity.com/paper/1609.01508/) (2016)
- [Bernoulli Rank-1 Bandits for Click Feedback](https://mlsanity.com/paper/1703.06513/) (2017)
- [Structured Stochastic Linear Bandits](https://mlsanity.com/paper/1606.05693/) (2016)

## Built on by (most cited first, 20 of 20)

- [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 Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theory](https://mlsanity.com/paper/2411.00401/) (2024)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Low-Rank Online Dynamic Assortment with Dual Contextual Information](https://mlsanity.com/paper/2404.17592/) (2024)
- [Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits](https://mlsanity.com/paper/2608.04324/) (2026)
- [Active learning of neural population dynamics using two-photon holographic optogenetics](https://mlsanity.com/paper/2412.02529/) (2024)
- [A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits](https://mlsanity.com/paper/2501.10722/) (2025)
- [Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits](https://mlsanity.com/paper/2510.00803/) (2025)
- [Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendations](https://mlsanity.com/paper/2602.08067/) (2026)
- [Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity](https://mlsanity.com/paper/2605.20269/) (2026)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Acting on the Unseen: Communication-Free Collaborative Filtering for Decentralized Multi-Robot Task Allocation](https://mlsanity.com/paper/2605.25584/) (2026)
- [Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors](https://mlsanity.com/paper/2609.33025/) (2026)
- [Optimal Online Regret for Context-Lumpable Bandits](https://mlsanity.com/paper/2610.18258/) (2026)

## Abstract (arXiv)

In the stochastic contextual low-rank matrix bandit problem, the expected reward of an action is given by the inner product between the action's feature matrix and some fixed, but initially unknown d1 by d2 matrix Theta^* with rank r ll d1, d2, and an agent sequentially takes actions based on past experience to maximize the cumulative reward. In this paper, we study the generalized low-rank matrix bandit problem, which has been recently proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms on this problem, we first propose the G-ESTT framework that modifies the idea from citejun2019bilinear by using Stein's method on the subspace estimation and then leverage the estimated subspaces via a regularization idea. Furthermore, we remarkably improve the efficiency of G-ESTT by using a novel exclusion idea on the estimated subspace instead, and propose the G-ESTS framework. We also show that G-ESTT can achieve the tildeO(√(d1+d2)MrT) bound of regret while G-ESTS can achineve the tildeO(√(d1+d2)3/2Mr3/2T) bound of regret under mild assumption up to logarithm terms, where M is some problem dependent value. Under a reasonable assumption that M = O((d1+d2)2) in our problem setting, the regret of G-ESTT is consistent with the current best regret of tildeO((d1+d2)3/2 √rT/Drr)~citeplu2021low (Drr will be defined later). For completeness, we conduct experiments to illustrate that our proposed algorithms, especially G-ESTS, are also computationally tractable and consistently outperform other state-of-the-art (generalized) linear matrix bandit methods based on a suite of simulations.