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

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

## Key facts

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

## Builds on (most cited first, 30 of 31)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation](https://mlsanity.com/paper/2006.06135/) (2020)
- [Harnessing Structures for Value-Based Planning and Reinforcement Learning](https://mlsanity.com/paper/1909.12255/) (2019)
- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [State Aggregation Learning from Markov Transition Data](https://mlsanity.com/paper/1811.02619/) (2018)
- [√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank](https://mlsanity.com/paper/1909.02506/) (2019)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Adaptive Discretization for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2007.00717/) (2020)
- [Low-rank State-action Value-function Approximation](https://mlsanity.com/paper/2104.08805/) (2021)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Empirical Dynamic Programming](https://mlsanity.com/paper/1311.5918/) (2013)

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

- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Matrix Estimation for Offline Reinforcement Learning with Low-Rank Structure](https://mlsanity.com/paper/2305.15621/) (2023)
- [Matrix Low-Rank Trust Region Policy Optimization](https://mlsanity.com/paper/2405.17625/) (2024)
- [Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation](https://mlsanity.com/paper/2410.23434/) (2024)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)

## 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.