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 (105)

• Neural Architecture Search with Bayesian Optimisation and Optimal Transport
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• On the Sample Complexity of the Linear Quadratic Regulator
• VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning
• Learning Near Optimal Policies with Low Inherent Bellman Error
• ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• 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?
• Naive Exploration is Optimal for Online LQR
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features
• 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
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Feature-Based Q-Learning for Two-Player Stochastic Games
• Is Q-learning Provably Efficient?
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• 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
• Provably Efficient Exploration in Policy Optimization
• Harnessing Structures for Value-Based Planning and Reinforcement Learning
• $Q$-learning with Logarithmic Regret
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Policy Certificates: Towards Accountable Reinforcement Learning
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Adaptive Discretization in Online Reinforcement Learning
• Bellman-consistent Pessimism for Offline Reinforcement Learning
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Nonstationary Reinforcement Learning with Linear Function Approximation
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• MADE: Exploration via Maximizing Deviation from Explored Regions
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Provably Efficient Reinforcement Learning with Aggregated States
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Robust Policy Gradient against Strong Data Corruption
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• Offline Meta Learning of Exploration
• Towards Understanding Cooperative Multi-Agent Q-Learning with Value Factorization
• Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• On the Approximation of Cooperative Heterogeneous Multi-Agent Reinforcement Learning (MARL) using Mean Field Control (MFC)
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Generalized Decision Transformer for Offline Hindsight Information Matching
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• On Value Functions and the Agent-Environment Boundary
• Towards General Function Approximation in Zero-Sum Markov Games
• Learning Good State and Action Representations via Tensor Decomposition
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Episodic Linear Quadratic Regulators with Low-rank Transitions
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Online Sparse Reinforcement Learning
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Online Model Selection for Reinforcement Learning with Function Approximation
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning
• Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning
• Reinforcement Learning with Feedback Graphs
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• Efficient Local Planning with Linear Function Approximation
• Provably Correct Optimization and Exploration with Non-linear Policies
• Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
• PAC Reinforcement Learning without Real-World Feedback
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning
• Learning the Linear Quadratic Regulator from Nonlinear Observations
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Ranking Policy Gradient
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation
• Koopman Spectrum Nonlinear Regulators and Efficient Online Learning
• Gap-Dependent Bounds for Two-Player Markov Games
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Reinforcement Learning in Reward-Mixing MDPs
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Bad-Policy Density: A Measure of Reinforcement Learning Hardness