mlsanityData to 7 Oct 2026

Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure

arXiv 2206.03569 ↗First posted 7 Jun 2022cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

The practicality of reinforcement learning algorithms has been limited due to poor scaling with respect to the problem size, as the sample complexity of learning an ε-optimal policy is tildeOmegaleft(|S||A|H3 / ε2right) over worst case instances of an MDP with state space S, action space A, and horizon H. We consider a class of MDPs for which the associated optimal Q^* function is low rank, where the latent features are unknown. While one would hope to achieve linear sample complexity in |S| and |A| due to the low rank structure, we show that without imposing further assumptions beyond low rank of Q^*, if one is constrained to estimate the Q function using only observations from a subset of entries, there is a worst case instance in which one must incur a sample complexity exponential in the horizon H to learn a near optimal policy. We subsequently show that under stronger low rank structural assumptions, given access to a generative model, Low Rank Monte Carlo Policy Iteration (LR-MCPI) and Low Rank Empirical Value Iteration (LR-EVI) achieve the desired sample complexity of tildeOleft((|S|+|A|)poly(d,H)/ε2right) for a rank d setting, which is minimax optimal with respect to the scaling of |S|, |A|, and ε. In contrast to literature on linear and low-rank MDPs, we do not require a known feature mapping, our algorithm is computationally simple, and our results hold for long time horizons. Our results provide insights on the minimal low-rank structural assumptions required on the MDP with respect to the transition kernel versus the optimal action-value function.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 31 of its 66 references that are in the map. First posted on arXiv 7 Jun 2022.

Builds on

31 of 66 references.

References · 31

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  9. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  11. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  12. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
19 more
  1. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  2. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  3. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  4. 2020Q-learning with Logarithmic Regretcited by 59
  5. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  6. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  7. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
  8. 2020Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimationcited by 25
  9. 2019Harnessing Structures for Value-Based Planning and Reinforcement Learningcited by 24
  10. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  11. 2018State Aggregation Learning from Markov Transition Datacited by 20
  12. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  13. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  14. 2022Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learningcited by 16
  15. 2020Adaptive Discretization for Model-Based Reinforcement Learningcited by 13
  16. 2021Low-rank State-action Value-function Approximationcited by 10
  17. 2021Learning Good State and Action Representations via Tensor Decompositioncited by 7
  18. 2013Empirical Dynamic Programmingcited by 6
  19. 2017Survival-Supervised Topic Modeling with Anchor Words: Characterizing Pancreatitis Outcomescited by 1

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 2; 2025: 2.

7 papers.

  1. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  2. 2022Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Armscited by 4
  3. 2023Matrix Estimation for Offline Reinforcement Learning with Low-Rank Structurecited by 2
  4. 2024Matrix Low-Rank Trust Region Policy Optimizationcited by 2
  5. 2024Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimationcited by 1
  6. 2025Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximationcited by 1
  7. 2025ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertaintycited by 0