Contextual Decision Processes with Low Bellman Rank are PAC-Learnable

Abstract

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.

42 pages, 1 figure

Cited by in corpus (18)

• VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• 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?
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Provably Efficient Reinforcement Learning with Aggregated States
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Reinforcement Learning with Feedback Graphs
• PAC Reinforcement Learning without Real-World Feedback
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning