mlsanityData to 7 Oct 2026

Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems

arXiv 2401.07298 ↗First posted 14 Jan 2024stat.ML cs.LGcited by 19

Not on the map. Why?

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.

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

Builds on

13 of 49 references.

References · 13

  1. 2019Bilinear Bandits with Low-rank Structurecited by 54
  2. 2020Low-Rank Generalized Linear Bandit Problemscited by 48
  3. 2013Provable Inductive Matrix Completioncited by 31
  4. 2020An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Samplingcited by 30
  5. 2017Stochastic Low-Rank Banditscited by 28
  6. 2016Stochastic Rank-1 Banditscited by 23
  7. 2019Solving Bernoulli Rank-One Bandits with Unimodal Thompson Samplingcited by 23
  8. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  9. 2016Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entriescited by 18
  10. 2017Generalized High-Dimensional Trace Regression via Nuclear Norm Regularizationcited by 12
  11. 2016Low-rank Bandits with Latent Mixturescited by 11
  12. 2017Bernoulli Rank-1 Bandits for Click Feedbackcited by 11
1 more
  1. 2016Structured Stochastic Linear Banditscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 5; 2026: 7.

19 papers.

Sort:

By area:

  1. 2024Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learningcited by 10
  2. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 9
  3. 2024Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theorycited by 7
  4. 2024Low-rank Matrix Bandits with Heavy-tailed Rewardscited by 6
  5. 2025Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functionscited by 6
  6. 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 5
  7. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  8. 2025Quantum Lipschitz Banditscited by 4
  9. 2025Generalized Low-Rank Matrix Contextual Bandits with Graph Informationcited by 4
  10. 2024Low-Rank Online Dynamic Assortment with Dual Contextual Informationcited by 2
  11. 2025A Unified Regularization Approach to High-Dimensional Generalized Tensor Banditscited by 1
  12. 2025Online Minimization of Polarization and Disagreement via Low-Rank Matrix Banditscited by 1
7 more
  1. 2026Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendationscited by 1
  2. 2026Catching a Moving Subspace: Low-Rank Bandits Beyond Stationaritycited by 1
  3. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  4. 2024Active learning of neural population dynamics using two-photon holographic optogeneticscited by 0
  5. 2026Acting on the Unseen: Communication-Free Collaborative Filtering for Decentralized Multi-Robot Task Allocationcited by 0
  6. 2026Efficient Online Lexicographic Generalized Low-Rank Matrix Banditscited by 0
  7. 2026Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensorscited by 0