mlsanityData to 14 Oct 2026

Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning

arXiv 2310.06793 ↗First posted 10 Oct 2023cs.LG stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. In both cases, each entry of the matrix carries important information, and we seek estimation methods with low entry-wise error. Importantly, these methods further need to accommodate for inherent correlations in the available data (e.g. for MDPs, the data consists of system trajectories). We investigate the performance of simple spectral-based matrix estimation approaches: we show that they efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error. These new results on low-rank matrix estimation make it possible to devise reinforcement learning algorithms that fully exploit the underlying low-rank structure. We provide two examples of such algorithms: a regret minimization algorithm for low-rank bandit problems, and a best policy identification algorithm for reward-free RL in low-rank MDPs. Both algorithms yield state-of-the-art performance guarantees.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 42 of its 64 references that are in the map. First posted on arXiv 10 Oct 2023.

Builds on

42 of 64 references.

References · 42

  1. 2020CURL: Contrastive Unsupervised Representations for Reinforcement Learningcited by 760
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  4. 2020Decoupling Representation Learning from Reinforcement Learningcited by 269
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  8. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  9. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  10. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 112
  11. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  12. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
30 more
  1. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  2. 2020Adaptive Reward-Free Explorationcited by 77
  3. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  4. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  5. 2019Bilinear Bandits with Low-rank Structurecited by 55
  6. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  7. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  8. 2020Low-Rank Generalized Linear Bandit Problemscited by 49
  9. 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 47
  10. 2016Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statisticscited by 45
  11. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  12. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 36
  13. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  14. 2017Stochastic Low-Rank Banditscited by 28
  15. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 25
  16. 2020Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimationcited by 25
  17. 2016Stochastic Rank-1 Banditscited by 23
  18. 2019Solving Bernoulli Rank-One Bandits with Unimodal Thompson Samplingcited by 23
  19. 2018Spectral State Compression of Markov Processescited by 18
  20. 2017Unperturbed: spectral analysis beyond Davis-Kahancited by 16
  21. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  22. 2019Learning Markov models via low-rank optimizationcited by 12
  23. 2021Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependencecited by 12
  24. 2022Online Low Rank Matrix Completioncited by 9
  25. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  26. 2019Low-rank matrix completion and denoising under Poisson noisecited by 6
  27. 2022Nearly Optimal Latent State Decoding in Block MDPscited by 5
  28. 2022Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Armscited by 4
  29. 2018Estimation of Markov Chain via Rank-Constrained Likelihoodcited by 3
  30. 2023Representations and Exploration for Deep Reinforcement Learning using Singular Value Decompositioncited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 6; 2025: 1; 2026: 3.

10 papers.

  1. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  2. 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 6
  3. 2024The Limits of Transfer Reinforcement Learning with Latent Low-rank Structurecited by 1
  4. 2024Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimationcited by 1
  5. 2025Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximationcited by 1
  6. 2026Catching a Moving Subspace: Low-Rank Bandits Beyond Stationaritycited by 1
  7. 2024Entrywise error bounds for low-rank approximations of kernel matricescited by 0
  8. 2024Online Matrix Completion: A Collaborative Approach with Hott Itemscited by 0
  9. 2026Factorized Spectral Representations for Reinforcement Learningcited by 0
  10. 2026Optimal Online Regret for Context-Lumpable Banditscited by 0