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.
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