Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches

Abstract

We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for RL with a generic model class and analyze their statistical properties. Our algorithms have sample complexity governed by a new structural parameter called the witness rank, which we show to be small in several settings of interest, including factored MDPs. We also show that the witness rank is never larger than the recently proposed Bellman rank parameter governing the sample complexity of the model-free algorithm OLIVE (Jiang et al., 2017), the only other provably sample-efficient algorithm for global exploration at this level of generality. Focusing on the special case of factored MDPs, we prove an exponential lower bound for a general class of model-free approaches, including OLIVE, which, when combined with our algorithmic results, demonstrates exponential separation between model-based and model-free RL in some rich-observation settings.

arXiv commentCOLT 2019

Cited by in corpus (48)

• Information-Theoretic Considerations in Batch Reinforcement Learning
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Batch Value-function Approximation with Only Realizability
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Combating the Compounding-Error Problem with a Multi-step Model
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Learning to Combat Compounding-Error in Model-Based Reinforcement Learning
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Model-free Representation Learning and Exploration in Low-rank MDPs
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Robust Policy Gradient against Strong Data Corruption
• Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting
• Towards General Function Approximation in Zero-Sum Markov Games
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Episodic Linear Quadratic Regulators with Low-rank Transitions
• MobILE: Model-Based Imitation Learning From Observation Alone
• Online Sparse Reinforcement Learning
• On Effective Scheduling of Model-based Reinforcement Learning
• Model-Invariant State Abstractions for Model-Based Reinforcement Learning
• Provably Correct Optimization and Exploration with Non-linear Policies
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• PAC Reinforcement Learning without Real-World Feedback
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• PAC Bounds for Imitation and Model-based Batch Learning of Contextual Markov Decision Processes
• Transfer Reinforcement Learning under Unobserved Contextual Information
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• On the Expressivity of Neural Networks for Deep Reinforcement Learning
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Bad-Policy Density: A Measure of Reinforcement Learning Hardness
• Koopman Spectrum Nonlinear Regulators and Efficient Online Learning