# Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

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

## Key facts

- Cited by 140 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2019.

## Built on by (most cited first, 30 of 140)

- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [A Survey of Zero-shot Generalisation in Deep Reinforcement Learning](https://mlsanity.com/paper/2111.09794/) (2021)
- [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)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [On The Effect of Auxiliary Tasks on Representation Dynamics](https://mlsanity.com/paper/2102.13089/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap](https://mlsanity.com/paper/2103.12690/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [On the Power of Foundation Models](https://mlsanity.com/paper/2211.16327/) (2022)
- [Spectral Decomposition Representation for Reinforcement Learning](https://mlsanity.com/paper/2208.09515/) (2022)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)

## Abstract (arXiv)

Modern deep learning methods provide effective means to learn good representations. However, is a good representation itself sufficient for sample efficient reinforcement learning? This question has largely been studied only with respect to (worst-case) approximation error, in the more classical approximate dynamic programming literature. With regards to the statistical viewpoint, this question is largely unexplored, and the extant body of literature mainly focuses on conditions which permit sample efficient reinforcement learning with little understanding of what are necessary conditions for efficient reinforcement learning. This work shows that, from the statistical viewpoint, the situation is far subtler than suggested by the more traditional approximation viewpoint, where the requirements on the representation that suffice for sample efficient RL are even more stringent. Our main results provide sharp thresholds for reinforcement learning methods, showing that there are hard limitations on what constitutes good function approximation (in terms of the dimensionality of the representation), where we focus on natural representational conditions relevant to value-based, model-based, and policy-based learning. These lower bounds highlight that having a good (value-based, model-based, or policy-based) representation in and of itself is insufficient for efficient reinforcement learning, unless the quality of this approximation passes certain hard thresholds. Furthermore, our lower bounds also imply exponential separations on the sample complexity between 1) value-based learning with perfect representation and value-based learning with a good-but-not-perfect representation, 2) value-based learning and policy-based learning, 3) policy-based learning and supervised learning and 4) reinforcement learning and imitation learning.