mlsanityData to 7 Oct 2026

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

arXiv 2206.02887 ↗First posted 6 Jun 2022cs.LG stat.MLcited by 12

Not on the map. Why?

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.

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

Builds on

42 of 82 references.

References · 42

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,406
  3. 2016Error bounds for approximations with deep ReLU networkscited by 567
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  5. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  6. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  7. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  9. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  10. 2019Batch Policy Learning under Constraintscited by 242
  11. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  12. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 160
30 more
  1. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  2. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  3. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  6. 2019Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learningcited by 121
  7. 2019Deep Network Approximation Characterized by Number of Neuronscited by 120
  8. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  9. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  10. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  11. 2017Deep Reinforcement Learning for Unsupervised Video Summarization with Diversity-Representativeness Rewardcited by 105
  12. 2017Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activationscited by 104
  13. 2021Benchmarks for Deep Off-Policy Evaluationcited by 89
  14. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  15. 2019Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recoverycited by 73
  16. 2017Learning Cooperative Visual Dialog Agents with Deep Reinforcement Learningcited by 70
  17. 2015Provable approximation properties for deep neural networkscited by 60
  18. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  19. 2018On the Intrinsic Dimensionality of Image Representationscited by 57
  20. 2018Reinforcement Learning for Improving Agent Designcited by 55
  21. 2019Nonlinear Approximation and (Deep) ReLU Networkscited by 45
  22. 2020Interpretable Off-Policy Evaluation in Reinforcement Learning by Highlighting Influential Transitionscited by 41
  23. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inferencecited by 40
  24. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  25. 2021Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networkscited by 32
  26. 2016Deep nets for local manifold learningcited by 26
  27. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  28. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparisoncited by 22
  29. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  30. 2017Tracking as Online Decision-Making: Learning a Policy from Streaming Videos with Reinforcement Learningcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 5; 2024: 3; 2025: 1; 2026: 1.

12 papers.

  1. 2024Diffusion Model for Data-Driven Black-Box Optimizationcited by 24
  2. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  3. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  4. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  5. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  6. 2024SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learningcited by 5
  7. 2025Geometry of Neural Reinforcement Learning in Continuous State and Action Spacescited by 3
  8. 2023Sample Complexity of Neural Policy Mirror Descent for Policy Optimization on Low-Dimensional Manifoldscited by 1
  9. 2023Neural Network Approximation for Pessimistic Offline Reinforcement Learningcited by 1
  10. 2022On the Geometry of Reinforcement Learning in Continuous State and Action Spacescited by 0
  11. 2023Sample Complexity of Preference-Based Nonparametric Off-Policy Evaluation with Deep Networkscited by 0
  12. 2026Distributional Off-Policy Evaluation with Deep Quantile Process Regressioncited by 0