Near-Optimal Offline Reinforcement Learning via Double Variance Reduction

Abstract

We consider the problem of offline reinforcement learning (RL) -- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open even in basic settings such as \emph{tabular} Markov Decision Processes (MDPs). In this paper, we propose Off-Policy Double Variance Reduction (OPDVR), a new variance reduction based algorithm for offline RL. Our main result shows that OPDVR provably identifies an $\epsilon$-optimal policy with $\tilde{O}(H^2/d_m{\epsilon }^2)$ episodes of offline data in the finite-horizon stationary transition setting, where $H$ is the horizon length and $d_m$ is the minimal marginal state-action distribution induced by the behavior policy. This improves over the best known upper bound by a factor of $H$. Moreover, we establish an information-theoretic lower bound of $\Omega (H^2/d_m{\epsilon }^2)$ which certifies that OPDVR is optimal up to logarithmic factors. Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards.

References in corpus (24)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• Stochastic Variance Reduction Methods for Policy Evaluation
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Variance-reduced $Q$-learning is minimax optimal
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Batch Value-function Approximation with Only Realizability
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Is Pessimism Provably Efficient for Offline RL?
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Provably Efficient Exploration in Policy Optimization
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Policy Certificates: Towards Accountable Reinforcement Learning
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited

Cited by in corpus (10)

• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Corruption-Robust Offline Reinforcement Learning
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Nearly Horizon-Free Offline Reinforcement Learning
• Representation Learning for Online and Offline RL in Low-rank MDPs
• On the Optimality of Batch Policy Optimization Algorithms
• Improving Long-Term Metrics in Recommendation Systems using Short-Horizon Reinforcement Learning
• UMBRELLA: Uncertainty-Aware Model-Based Offline Reinforcement Learning Leveraging Planning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings