Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks

Abstract

Offline reinforcement learning (RL) leverages previously collected data for policy optimization without any further active exploration. Despite the recent interest in this problem, its theoretical results in neural network function approximation settings remain elusive. In this paper, we study the statistical theory of offline RL with deep ReLU network function approximation. In particular, we establish the sample complexity of $n=\tilde{\mathcal{O}}(H^{4+4\frac{d}{\alpha }}{\kappa }_{\mu }^{1+\frac{d}{\alpha }}{\epsilon }^{-2-2\frac{d}{\alpha }})$ for offline RL with deep ReLU networks, where ${\kappa }_{\mu }$ is a measure of distributional shift, {$H=(1-\gamma {)}^{-1}$ is the effective horizon length}, $d$ is the dimension of the state-action space, $\alpha$ is a (possibly fractional) smoothness parameter of the underlying Markov decision process (MDP), and $\epsilon$ is a user-specified error. Notably, our sample complexity holds under two novel considerations: the Besov dynamic closure and the correlated structure. While the Besov dynamic closure subsumes the dynamic conditions for offline RL in the prior works, the correlated structure renders the prior works of offline RL with general/neural network function approximation improper or inefficient {in long (effective) horizon problems}. To the best of our knowledge, this is the first theoretical characterization of the sample complexity of offline RL with deep neural network function approximation under the general Besov regularity condition that goes beyond {the linearity regime} in the traditional Reproducing Hilbert kernel spaces and Neural Tangent Kernels.

arXiv commenthttps://openreview.net/forum?id=LdEm0umNcv

References in corpus (18)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Doubly Robust Policy Evaluation and Learning
• Optimization for deep learning: theory and algorithms
• A Theoretical Analysis of Deep Q-Learning
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• GenDICE: Generalized Offline Estimation of Stationary Values
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Is Pessimism Provably Efficient for Offline RL?
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
• Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths

Cited by in corpus (1)

• Optimal policy evaluation using kernel-based temporal difference methods