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.

https://openreview.net/forum?id=LdEm0umNcv

References in corpus (10)

• Doubly Robust Policy Evaluation and Learning
• Optimization for deep learning: theory and algorithms
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• 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?
• 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