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

Xiang Ji, Minshuo Chen, Mengdi Wang, Tuo Zhao

Introduction

In Reinforcement Learning (RL), Off-Policy Evaluation (OPE) is the critical task of estimating how well a new "target" policy will perform using only historical data collected by a different "behavior" policy. This is essential in high-stakes fields like medicine or autonomous driving, where testing an unproven policy in the real world is dangerous or unethical.

This paper provides a theoretical breakthrough for OPE, proving that deep convolutional neural networks (CNNs) can bypass the notorious "curse of dimensionality." By exploiting the low-dimensional manifold structure inherent in many complex environments, the authors show that OPE accuracy depends on the intrinsic complexity of the state space (e.g., the physics of a system) rather than the raw number of pixels in the visual input.

The Curse of Dimensionality in OPE

The major hurdle in evaluating policies from visual data is the curse of dimensionality. Standard statistical theory suggests that as the number of input features (ambient dimension $D$) increases—such as the thousands of pixels in a camera feed—the amount of data needed to reach a certain accuracy grows exponentially.

Visual inputs in RL environments often have high ambient dimensionality (pixels) but are governed by low-dimensional intrinsic physics.

However, in practice, deep learning often works surprisingly well on high-dimensional data. This paper addresses the gap between theory and practice by modeling the state-action space as a low-dimensional manifold (with intrinsic dimension $d$) embedded within a high-dimensional space ($D$).

Methodology: Fitted Q-Evaluation with CNNs

The authors analyze the Fitted Q-Evaluation (FQE) algorithm, a popular iterative method that uses supervised regression to estimate the value of a policy. Their specific contribution lies in the theoretical analysis of FQE when implemented with Convolutional Neural Networks.

Key technical components of their approach include:

  • Manifold Modeling: The state-action space is treated as a $d$-dimensional Riemannian manifold.
  • Besov Spaces: The underlying Q-functions are assumed to belong to Besov spaces, a broad class of smooth functions well-suited for nonparametric analysis.
  • Restricted $\chi^2$-Divergence: They develop a new metric to quantify the "mismatch" between the behavior and target policies. Unlike standard metrics that compare raw probability densities (which can easily become infinite if policies don't overlap), this restricted version only measures differences that the specific neural network function class can actually "see."
  • CNN Approximation Theory: They derive a novel result showing how CNNs can efficiently approximate smooth functions on manifolds without being hindered by the ambient dimension $D$.

Key Insights and Results

The authors validated their theoretical findings using classic benchmarks from the OpenAI Gym, such as CartPole and LunarLander, processed via image-based states at varying visual resolutions.

Intrinsic vs. Ambient Dimension

The core breakthrough of the paper is the mathematical proof that the error bound for deep FQE depends on $d$ (e.g., the small number of parameters defining a robot's joints) rather than $D$ (the thousands of pixels in the image of that robot). This explains why practitioners can use high-resolution images in RL without needing an astronomical amount of data. CNNs are shown to be naturally "manifold-aware," automatically adapting to the local geometric structures of the data through their architecture.

Sharp Error Bounds and Resolution Invariance

The authors established a sharp error bound of $\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. Crucially, the ambient dimension $D$ is completely absent from the exponent.

In their experiments, FQE performance on high-resolution images was nearly identical to performance on low-resolution images. This confirms the theoretical claim: the network learns the underlying $d$-dimensional physics, rather than just memorizing $D$-dimensional pixels. As the sample size $K$ increases, the estimation error decays at a rate consistent with the intrinsic dimension, outperforming previous bounds that were sensitive to $D$.

Limitations and Future Work

While a significant step forward, the paper notes a few limitations:

  • Time-Inhomogeneous Assumption: The current theory focuses on time-inhomogeneous Markov Decision Processes (MDPs), where transitions change at each time step. Extending this to time-homogeneous MDPs is more complex due to temporal dependencies when reusing data.
  • Bellman Completeness: The analysis relies on the "Bellman completeness" assumption—the idea that the Bellman operator doesn't push functions out of the chosen Besov space. While standard in the literature, it remains a strong assumption.
  • Hyperparameter Sensitivity: While the theory suggests CNNs can adapt to manifolds, empirical results show that choosing the right learning rates and architectures remains vital for achieving these optimal rates in practice.

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