Is Pessimism Provably Efficient for Offline RL?

Abstract

We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators. Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the "best effort" among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the "irrelevant" trajectories that are less covered by the dataset and not informative for the optimal policy.

This version adds results on RKHS, and a data-splitting algorithm

References in corpus (20)

• StarCraft II: A New Challenge for Reinforcement Learning
• Conservative Q-Learning for Offline Reinforcement Learning
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Critic Regularized Regression
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Batch Value-function Approximation with Only Realizability
• Planning to Be Surprised: Optimal Bayesian Exploration in Dynamic Environments
• Reinforcement Learning via Fenchel-Rockafellar Duality
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• On Kernelized Multi-armed Bandits
• The Importance of Pessimism in Fixed-Dataset Policy Optimization
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation
• Doubly Robust Off-Policy Value and Gradient Estimation for Deterministic Policies

Cited by in corpus (16)

• Value Penalized Q-Learning for Recommender Systems
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Heuristic-Guided Reinforcement Learning
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Corruption-Robust Offline Reinforcement Learning
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Continuous Doubly Constrained Batch Reinforcement Learning
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Combining Online Learning and Offline Learning for Contextual Bandits with Deficient Support
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation