Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of off-policy evaluation using deep convolutional neural network. The main contribution of this paper is a theoretical justification of the ability that a deep neural network captures low-rank structures in high-dimensional datasets in off-policy RL settings. Although preliminary results on off-policy evaluation problem has been obtained in Nguyen-Tang et al. (2021), this work is stronger without the data coverage assumption. Also, it leverages a restricted $\chi^2$-divergence which is generally tighter than the density ratio. Finally, the sample complexity is measured in terms of the intrinsic dimension of the problem, that is significantly smaller than the data dimension.

Overall, the proposed theoretical analysis on the convergence of deep fitted Q-evaluation for off-policy RL and CNN networks achieves superior regret bound result due to the ability to capture low-dimensional structure.

strength_and_weaknesses: 
The main strength of this paper is that it provides the first regret bound result on off-policy evaluation with deep neural network approximation with practical assumptions. The authors provide a theorem that bounds the sample complexity in terms of the intrinsic dimension and the $\chi^2$-divergence between the sampling policy and the target policy, where both the dimension and the divergence generally improves upon previous results.

However, there are a several vagueness and weakness, listed as follows

- The paper spends lots of effort in introducing the background (at least the CNN part is a little bit distracting, as the CNN structure does not seem to influence the complexity analysis?)
- On the other hand, the authors does not provide much explanation about what leads to the theoretical success of capturing the intrinsic dimension of the dataset. Has similar tools been leveraged in the literature of supervised learning? 
- Similarly, what is the intuition behind the proof that removes the data coverage assumption?
- The paper adopted the Besov spaces and the Besov closure property, and the sample complexity is dependent on the Besov parameter $\alpha$. How does this $\alpha$ affect the sample complexity and the scope of hypothesis class?
- Theorem 2 appears abruptly. What is this theorem for? Is Theorem 2 basically a Lemma essential for proving Theorem 1? This part seems incomplete.
- In the experimental section, the authors Illustrate their claim by showing that the performance under high resolution and low resolution are similar. However, that might be due to the simplicity of the CartPole problem, let along the fact that $3\times 40\times 150$ and $3 \times 20 \times 75$ are not significantly different. More empirical validations are needed to truly verify their claim.

Also, there are a few typos:
- In the definition of Reach, the $inf$ has to be taken on $x \in \bar{\mathcal{T}}$ instead of $\mathcal{T}$?
- In the convolutional network part, $\mathcal{W}_{j, :, :}$ is not $D \times C$ (Caption of Figure 2)
clarity,_quality,_novelty_and_reproducibility: The writing of this paper is mostly ok in the sense that it is easy to follow. However, some part essential for understanding the significance of this work is missing in the main context, especially the technical part. Also, the experimental result does not seem to properly address the main claim.
summary_of_the_review: Overall, the paper seems prospective, it provides a sharper sample complexity under a more general assumption. I will consider raising my score if the technical novelty of this paper, Theorem 2, and the experimental results can be better explained.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
This paper provides new sample complexity guarantees for convolutional neural networks applied to off-policy Q-learning of MDPs with low-dimensional manifold structure.

The work is novel in that it provides a new characterization of the sample-complexity in terms of the underlying manifold dimension rather than the the ambient dimension of the data and action space -- which can be extremely large for state spaces defined in terms of image and video data. The bound is also novel in that it is utilizes the \chi^2 divergence between the logging policy and the target policy, rather than the maximum density ratio which can be unbounded for continuous action spaces.

The authors define their bound with respect to a restricted but flexible class of Besov functions which captures many of the essential aspects of modern convolutional neural networks.

Finally, the paper concludes with a limited set of experiments on the CartPole environment which demonstrate that Q-functions fitted on images do learn with fewer examples than the ambient dimension of the data.

strength_and_weaknesses: Strengths:
- Novel and tighter sample complexity bound for off-policy deep Q-learning with convnets that is characterized in terms of the dimension of the underlying data manifold and the \chi^2 divergence between on- and off-line policies.

Weaknesses:
- the class of convnet functions used in the does not include skip connections which are always used in modern CNN architectures like ResNets. Does incorporating skip connections change the analysis or complexity bounds?
- the experimental results are suggestive but quite cursory. It would be interesting to test networks with different numbers of channels, layers and see if the empirical estimation errors actually increase and decrease in accordance with what is predicted by the new bounds.
- the bounds agree with empirical findings that CNNs seem to have a sample complexity that is lower than the ambient image dimension. But it's not clear if the theory will yield advances in applications.

clarity,_quality,_novelty_and_reproducibility: The paper is very clear, novel and reproducible. And I found it to be high quality.

summary_of_the_review: This work provides novel and improved bounds that further our understanding of how and why deep Q-learning (with convnets) performs well in very high dimensional state spaces. As such it is of interest to theorists currently working at the intersection of deep learning and RL. I support adding this paper to the 2023 ICLR program.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the off-policy evaluation problem in MDPs using function approximations. To estimate the offline target policy, the fitted Q-evaluation method is used, and to approximate Q-functions, CNNs are used. Their theoretical results show that when state-action space has low-dimensional structures, the finite-sample estimation error of FQE converges, depending on (1) the intrinsic dimension without suffering from the curse of high dimensionality, and (2) a function class-restricted  $\chi^2$ -divergence which measures the distribution shift between the experience data distribution and the target policy. They use an experiment on CartPole to evaluate their theory.

strength_and_weaknesses: Strengths:
- The paper is well written.
- The regret bound with provided theoretical analysis, and especially using a function class-restricted  $\chi^2$ -divergence for insufficient data coverage are new.

Weaknesses:
- The results seem to be a combination of existing results: the sample complexity in Besov space of off-policy evaluation using deep neural networks from [1] and low-dimensional manifolds in deep networks from [2,3,4,5].

 [1]  Thanh Nguyen-Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. Sample complexity of ofﬂine reinforcement learning with deep relu networks. arXiv preprint arXiv:2103.06671, 2021.
 [2]  Minshuo Chen, Haoming Jiang, Wenjing Liao, Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. NeurIPS 2019.
 [3] Minshuo Chen, Haoming Jiang, Wenjing Liao, Tuo Zhao. Nonparametric regression on low-dimensional manifolds using deep ReLU networks: Function approximation and statistical recovery.2022.
 [4] Hao Liu, Minshuo Chen, Tuo Zhao, Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. ICML 2021.
 [5] Minshuo Chen, Hao Liu, Wenjing Liao, Tuo Zhao. Doubly robust off-policy learning on low-dimensional manifolds by deep neural networks. 2020.
- Recently, several results about the sample complexity of offline RL without using function approximations are published. 
The authors are missing a discussion about these works. 


clarity,_quality,_novelty_and_reproducibility: The paper is well written, however, the theoretical results seem to be a combination of existing works.
summary_of_the_review: The novelty and originality of this paper are low. I lean toward rejecting this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The manuscript studies the estimation error of fitted Q-evaluation with convolutional neural networks under the assumption of a low dimensional state-action space. 
The main contribution is that the decay rate of the estimation error only depends on the dimension of the state-action space rather than the ambient dimension. 
The result builds on an new approximation result for Besov functions on submanifold, which is established in the manuscript. 

strength_and_weaknesses: **Strengths:**
* Sound rigorous analysis; proper application of adequate mathematical tools.

**Weaknesses:**
* Little insight into the main steps of the proof is given in the main body.
* Experimens are weak: I do not believe that a theoretical paper necessarily requires experiments. However, if experiments are provided, they should be well designed and provide substantial insight to the theoretical results. The biggest shortcomings of the experiments is their implications: 1) "performance [i.e., the fitted value function] of FQE on high-resolution data and low-resolution data is similar" 2) "estimation becomes increasingly accurate as sample size K increases". Where these findings don't contradict the Theorem 1 they do not evaluate its main claim, which is a error decay rate, which is independent of the ambient dimension. I think the experiments would be much stronger if tested for this rate, i.e., for a given setup simply increase the number of samples $K$ and then plot the estimation error on a log log plot including the predicted power law decay of $O(K^{-\frac{\alpha}{2\alpha+d}})$. 
clarity,_quality,_novelty_and_reproducibility: **Clarity:** 
The manuscript is written very clearly and easy to follow. 
One thing that limits the insight provided by the main body of the manuscript is that it hardly sheds light into the proof techniques.
Occasionally, things could be improved, in particular in the Definition of Besov spaces as well as the statement of the main result in Theorem 1 -- see the more detailed comments down below. 

**Quality:**
The manuscript is written very well, the theoretical tools are adequate and are applied properly.

**Novelty:** 
The study of the estimation error under the assumption of a low dimensional state-action space appears to be novel. I can right now not judge the relation of the theoretical tools to existing results on the generalization error under the assumption of low dimensionality in the context of supervised learning. 

summary_of_the_review: The manuscript studies an important and timely problem within the theory of reinforcement learning. 
It is well written and provides a result on the estimation error, which depends on the intrinsic dimension of the state-action space and offers an analogon to existing result in the context of supervised learning.
Overall, I believe this manuscript provides a valuable contribution to the theoretical RL literature. My main critcism is summarized in the following points:

* *Insights into the proof and tools:* The manuscript would be stronger if it provided more insight into the techniques and main steps in the proof of the main results. In particular, this would is more important in my view compared to the discussion of the $\chi^2$ distance and absolute density ratio, which could be moved to the appendix without big sacrifices, as well as as the paragraph *Sample Complexity Comparison*, which does not offer too much insight compared to Table 1.
* *Experiments:* The experiments show that estimated value function does only weakly depend on the ambient dimension. However, this does not imply anything about the estimation error nor its decay rate for increasing sample size, which is the content of Theorem 1. I think a much more suitable experiment to get experimental evidence for Theorem 1 would be one that evaluates the estimation error and compares the decay to the predicted power law decay $O(K^{-\frac{\alpha}{2\alpha+d}})$. In its current form, I think the space used for the experimental section could be of better use to provide more insight to the proof. However, with experiments confirming the predicted power law decay and possibly its tightness, a presentation of them would be justified in the main body of the manuscript.
* *Definition of Besov space:* Currently, the definition is not very clear to pass. More precisely, $U$ is not introduced in the definition of the Besov norm and it is unclear which atlas is to be taken in the definition of the global Besov norm since its value does depend on the atlas (it could even be infinite). Further, I am suprised to not see any charts appearing in the definition and thus I am wondering what the difference to the notion of the Besov norm induced by the ambient space.
* *Relation to existing results:* The manuscript does give an extensive overview of results on Q-value function estimation. However, the relation to results using Besov functions defined and low dimensional structures in the context of supervised learning is not discussed sufficiently.
* *Presentation of Theorem 1:* The choice $\mathcal F$ as a family induced by a CNN is only implicit and should be made explicit. Further, I believe that Algorithm 1 should be in the main body since in its current form it is required to parse the main result.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper offers the first theoretical analysis of deep fitted Q that provides statistical rates that adapt to the intrinsic dimensionality of the state-action space.

Despite similar statements for instrinsic dimension dependence appearing in past work for simpler or different problems like empirical risk minimization, causal inference, static policy learning; this paper offers such an analogous result for deep fitted q evaluation.

For this reason the paper makes a solid theoretical contribution; and this is recognized by most reviewers.

There is some concern that the experimental evaluation is not rich enough; but give that the main contribution is a theoretical guarantee I dont view this as an obstacle for acceptance. Moreover the limited experiments that the authors run do give practical evidence for adaptivity to intrinsic dimension. Moreover, based on reviews the authors did enrich a bit their set of experiments.
justification_for_why_not_higher_score: Primarily of theoretical interest. Moreover similar results appear in other settings; hence not a groundbreaking theoretical development. 
justification_for_why_not_lower_score: A solid theoretical contribution for the well established setting of deep fitted q iteration.
Decision: Accept: poster