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

Xiang Ji, Minshuo Chen, Mengdi Wang, Tuo Zhao

Abstract

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 $\chi^2$-divergence. It is noteworthy that the restricted $\chi^2$-divergence measures the behavior and target policies' 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.

Introduction: The Curse of Dimensionality in OPE

In many real-world Reinforcement Learning (RL) scenarios—such as clinical trials or autonomous driving—it is often impossible to run a new policy directly due to safety or ethical concerns. Instead, researchers rely on Off-Policy Evaluation (OPE) to estimate the value of a "target policy" using historical data collected by a different "behavior policy."

A major hurdle in OPE is the curse of dimensionality. When states are represented by high-resolution images, standard nonparametric theory suggests that the amount of data required for accurate estimation grows exponentially with the number of pixels. However, in practice, deep learning models like Convolutional Neural Networks (CNNs) perform remarkably well on these tasks. This paper bridges the gap between empirical success and theoretical understanding by demonstrating that CNNs can exploit the low-dimensional manifold structure inherent in high-dimensional data.

The Bipedal Walker environment serves as a motivating example where high-dimensional visual inputs (pixels) are generated from a low-dimensional physical state space.

Methodology: Deep Fitted Q-Evaluation

The authors analyze the Deep Fitted Q-Evaluation (FQE) method, which iteratively estimates the Q-function (expected future reward) using supervised regression at each time step, working backward from the task's horizon. The study introduces three technical innovations to explain FQE's efficiency:

  1. Manifold Modeling: The state-action space is modeled as a $d$-dimensional Riemannian manifold embedded in a $D$-dimensional ambient space, where $d \ll D$.
  2. CNN Approximation Theory: A new proof shows that CNNs can efficiently approximate "Besov functions" (smooth functions) specifically when defined on these low-dimensional manifolds.
  3. Restricted $\chi^2$-divergence: A new metric is proposed to measure the mismatch between behavior and target policies. Unlike standard density ratios, this metric only considers differences detectable by the neural network, leading to tighter error bounds.

Theoretical Breakthroughs

The core contribution of this work is a sharp error bound that proves CNNs are "manifold-adaptive." As shown in the comparison below, the estimation error is dominated by the intrinsic dimension ($d$) rather than the ambient dimension ($D$).

Comparison of estimation error bounds across different OPE methods. Note the dependence on intrinsic dimension $d$ in the proposed work.

Specifically, the established bound is $\mathbb{E}|v^\pi - \hat{v}^\pi| = \tilde{O}(\kappa H^2 K^{-\frac{\alpha}{2\alpha+d}})$, where $K$ is the sample size, $H$ is the horizon, and $\alpha$ is the smoothness. This result explains why a CNN can evaluate a policy based on 10,000-pixel images as efficiently as if it were dealing with just a few physical variables.

Empirical Validation

Numerical experiments using OpenAI Gym's CartPole and Bipedal Walker environments support the theoretical findings. In the CartPole environment, the authors tested FQE across different visual resolutions (e.g., $3 \times 40 \times 150$ vs. $3 \times 20 \times 75$ RGB arrays). The results demonstrated resolution invariance: performance was nearly identical regardless of pixel count, confirming that the difficulty of the problem depends on the underlying 4-dimensional physics of the pole, not the ambient dimensionality of the image.

Conclusion and Future Work

This work provides a rigorous theoretical foundation for the use of deep CNNs in OPE, showing they can bypass the curse of dimensionality by adapting to the local geometric structure of data. While these results are promising, future research is needed to extend this analysis to time-homogeneous MDPs and to address the theoretical challenges of sample reuse across FQE iterations.

Summary updated

Abstract

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 $\chi^2$-divergence. It is noteworthy that the restricted $\chi^2$-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.
BibTeX
@inproceedings{ji2023sample,
  author = {Xiang Ji and Minshuo Chen and Mengdi Wang and Tuo Zhao},
  title = {{Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=9x3CO0ZU9LR},
}
Figure