Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

Abstract

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.

To appear in ICLR 2020

References in corpus (9)

• Trust Region Policy Optimization
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction
• Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
• Approximate Policy Iteration Schemes: A Comparison
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model

Cited by in corpus (26)

• A Survey of Zero-shot Generalisation in Deep Reinforcement Learning
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Adaptive Discretization in Online Reinforcement Learning
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Which Mutual-Information Representation Learning Objectives are Sufficient for Control?
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Learning Good State and Action Representations via Tensor Decomposition
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• On the Expressivity of Neural Networks for Deep Reinforcement Learning
• Extracting Latent State Representations with Linear Dynamics from Rich Observations