# Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networks

arXiv: https://arxiv.org/abs/2206.02887 · HTML: https://mlsanity.com/paper/2206.02887/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 82 references that are in the map.
- First posted on arXiv 6 Jun 2022.

## Builds on (most cited first, 30 of 42)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Deep Network Approximation Characterized by Number of Neurons](https://mlsanity.com/paper/1906.05497/) (2019)
- [Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1911.06854/) (2019)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [Deep Reinforcement Learning for Unsupervised Video Summarization with Diversity-Representativeness Reward](https://mlsanity.com/paper/1801.00054/) (2017)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Benchmarks for Deep Off-Policy Evaluation](https://mlsanity.com/paper/2103.16596/) (2021)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recovery](https://mlsanity.com/paper/1908.01842/) (2019)
- [Learning Cooperative Visual Dialog Agents with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.06585/) (2017)
- [Provable approximation properties for deep neural networks](https://mlsanity.com/paper/1509.07385/) (2015)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)

## Built on by (most cited first, 12 of 12)

- [Diffusion Model for Data-Driven Black-Box Optimization](https://mlsanity.com/paper/2403.13219/) (2024)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems](https://mlsanity.com/paper/2307.12975/) (2023)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learning](https://mlsanity.com/paper/2405.15920/) (2024)
- [Geometry of Neural Reinforcement Learning in Continuous State and Action Spaces](https://mlsanity.com/paper/2507.20853/) (2025)
- [Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifolds](https://mlsanity.com/paper/2309.13915/) (2023)
- [Neural Network Approximation for Pessimistic Offline Reinforcement Learning](https://mlsanity.com/paper/2312.11863/) (2023)
- [On the Geometry of Reinforcement Learning in Continuous State and Action Spaces](https://mlsanity.com/paper/2301.00009/) (2022)
- [Sample Complexity of Preference-Based Nonparametric Off-Policy Evaluation with Deep Networks](https://mlsanity.com/paper/2310.10556/) (2023)
- [Distributional Off-Policy Evaluation with Deep Quantile Process Regression](https://mlsanity.com/paper/2604.18143/) (2026)

## Abstract (arXiv)

We consider the off-policy evaluation problem of reinforcement learning using deep convolutional neural networks. We analyze the deep fitted Q-evaluation method for estimating the expected cumulative reward of a target policy, when the data are generated from an unknown behavior policy. We show that, by choosing network size appropriately, one can leverage any low-dimensional manifold structure in the Markov decision process and obtain a sample-efficient estimator without suffering from the curse of high data ambient dimensionality. Specifically, we establish a sharp error bound for fitted Q-evaluation, which depends on the intrinsic dimension of the state-action space, the smoothness of Bellman operator, and a function class-restricted chi2-divergence. It is noteworthy that the restricted chi2-divergence measures the behavior and target policies' it mismatch in the function space, which can be small even if the two policies are not close to each other in their tabular forms. We also develop a novel approximation result for convolutional neural networks in Q-function estimation. Numerical experiments are provided to support our theoretical analysis.