mlsanityData to 7 Oct 2026

Stochastic Low-Rank Bandits

arXiv 1712.04644 ↗First posted 13 Dec 2017cs.LG stat.MLcited by 28

Not on the map. Why?

Abstract (arXiv)

Many problems in computer vision and recommender systems involve low-rank matrices. In this work, we study the problem of finding the maximum entry of a stochastic low-rank matrix from sequential observations. At each step, a learning agent chooses pairs of row and column arms, and receives the noisy product of their latent values as a reward. The main challenge is that the latent values are unobserved. We identify a class of non-negative matrices whose maximum entry can be found statistically efficiently and propose an algorithm for finding them, which we call LowRankElim. We derive a DeclareMathOperatorpolypoly O((K + L) poly(d) Delta-1 log n) upper bound on its n-step regret, where K is the number of rows, L is the number of columns, d is the rank of the matrix, and Delta is the minimum gap. The bound depends on other problem-specific constants that clearly do not depend K L. To the best of our knowledge, this is the first such result in the literature.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Dec 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 9; 2023: 5; 2024: 9; 2025: 2.

28 papers.

Sort:

By area:

  1. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  2. 2022Multi-task Representation Learning with Stochastic Linear Banditscited by 20
  3. 2024Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problemscited by 19
  4. 2023Optimal Algorithms for Latent Bandits with Cluster Structurecited by 11
  5. 2021Learning User Preferences in Non-Stationary Environmentscited by 10
  6. 2024Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learningcited by 10
  7. 2024Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedbackcited by 10
  8. 2022Online Low Rank Matrix Completioncited by 9
  9. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  10. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 9
  11. 2023Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricingcited by 8
  12. 2022An Experimental Design Approach for Regret Minimization in Logistic Banditscited by 7
16 more
  1. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  2. 2021Multi-armed Bandit Algorithm against Strategic Replicationcited by 5
  3. 2022On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structurecited by 5
  4. 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 5
  5. 2022Context Uncertainty in Contextual Bandits with Applications to Recommender Systemscited by 4
  6. 2022Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Armscited by 4
  7. 2025Generalized Low-Rank Matrix Contextual Bandits with Graph Informationcited by 4
  8. 2023Context-lumpable stochastic banditscited by 3
  9. 2024Low-Rank Online Dynamic Assortment with Dual Contextual Informationcited by 2
  10. 2022Targeted Advertising on Social Networks Using Online Variational Tensor Regressioncited by 1
  11. 2022A Scalable Recommendation Engine for New Users and Itemscited by 1
  12. 2023Efficient Generalized Low-Rank Tensor Contextual Banditscited by 1
  13. 2024Towards Domain Adaptive Neural Contextual Banditscited by 1
  14. 2025A Classification View on Meta Learning Banditscited by 1
  15. 2022Uncertainty-Based Non-Parametric Active Peak Detectioncited by 0
  16. 2024Online Matrix Completion: A Collaborative Approach with Hott Itemscited by 0