Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies offline RL with a differentiable function class. With the assumption that the covariance of the gradient of every function (w.r.t. the parameters) in the function class has a positive minimum eigenvalue, this paper proves sample complexity bounds that scale with the number of the parameters. The results in this paper recover existing results for linear models and generalized linear models (up to an additional $\sqrt{d}$ factor in the instance-dependent bound).
strength_and_weaknesses: Strength:
- The differentiable function class considered in this paper generalizes linear/generalized linear models. The sample complexity bounds for generalized linear models in this setting seem to be new.

Weakness:
- The two equations in Assumption 2.3 is required for every possible parameter $\theta$, which seems to be very strong. It’s unclear to me whether there are other function classes (beyond linear and generalized linear models) that can satisfy Assumption 2.3. For example, does a two-layer neural network with constant number of neurons satisfy Assumption 2.3?

clarity,_quality,_novelty_and_reproducibility: I find some of the claims in this paper confusing:

- The paragraph after assumption 2.2 states that “we make the following stronger coverage assumption …”. Why the following coverage assumption is stronger? Does Assumption 2.3 imply Assumption 2.2?
- The “Faster convergence in learning” paragraph (Page 7) uses the example that $\nabla f(\theta^\star,\phi)=0$ to demonstrate the faster rate. Does this statement requires  $\nabla f(\theta^\star,\phi(s,a))=0$ for every possible $s,a$? Does this example contradict with Assumption 2.3 (in particular, $\mathbb{E}[\nabla f(\theta^\star,\phi(s,a)) \nabla f(\theta^\star,\phi(s,a))^\top]\ge \kappa I$?
- The “Feature representation vs. Parameters” paragraph (Page 7) states that “when changing the model f with more complex representations, the learning hardness will not grow as long as the number of parameters needs to be learned does not increase”. It’s unclear to me what is the implication of this statement. It seems to me that this statement exactly means that the complexity of the function class does not increase with the feature dimension (when the number of parameters is fixed), so increasing the feature dimension further does not increase the expressivity of the function class fundamentally.
- It’s unclear to me why there is an extra $\sqrt{d}$ factor in Theorem 4.1. The conclusion section suggests that it comes from the covering argument for the differentiable function class. Could the authors elaborate? In particular, why can’t the uniform convergence techniques used in linear MDPs be applied here?

summary_of_the_review: My main concern is whether the differentiable function approximation setting considered in this paper contains new settings that is unknown in prior works. However, given that the results in this paper require some novel techniques, I will recommend a weak accept at this point.

=== after rebuttal ===
After reading through the authors' response, I tend to keep my score as weak accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies offline reinforcement learning with differentiable function class approximation (DFA). This function class incorporates a wide range of models with nonlinear/nonconvex structures. The authors show that offline RL with DFA is provably efficient via analyzing the pessimistic fitted Q-learning (PFQL) algorithm. They further improve the guarantee with a tighter instance-dependent characterization. 
strength_and_weaknesses: This paper provides novel theoretical results for the offline RL with function approximation. The authors of this paper study the differentiable function approximation, which is new to the area of offline RL, though some parts of the related theory are first studied by [Zhang et al. (2022)]. Their analysis is further improved based on the idea of variance awareness. Thus, the contribution is significant to this area. 

There are also several questions regarding this submission:

1. Can the authors provide some explanations on why in Theorem 3.2 and Theorem 4.1, the results only hold for $K \geq K_0$? What is the technical consideration behind $K_0$. How are $\kappa_1$ and $\kappa_2$ defined?

2. Is it possible to have an improvement on other factors ( e.g., $d$ ) beyond only an $H$ in the result in Theorem 4.1 based on the idea of variance awareness?

clarity,_quality,_novelty_and_reproducibility: Overall, the writing of this paper is clear to readers. The novelty is significant. And the authors provide detailed proof which can reproduce the main theoretical results.
summary_of_the_review: The technical contribution of this paper is significant. It provides novel ideas in the theoretical analysis of offline RL.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies parametric offline rl with a class of general differentiable function class approximation (DFA). The differentiable function class they consider is the set of functions $f(\theta, \phi)$ whose argument can be decomposed into two parts: $\theta$ is the parameter vector and $\phi$ is the feature map. They further assume that $f$ is third-time differentiable with respect to $\theta$ and their derivatives are jointly continuous wrt $\theta$ and $\phi$. This function class is a generalization of linear model where $f$ is not necessarily dot product of its arguments. 

Under two assumptions: (1) realizability + Bellman completeness, and (2)  the behavior policy is well exploratory over all dimensions of the gradient of DFA wrt $\theta$, they obtain a guarantee in a form that is similar to the linear MDP; though here they consider a much more general function class. Their bound scales linearly with d, H times the uncertainty quantifier across the trajectory of target policy. They also incorporate variance information to remove the factor $H$ in their learning bound.
strength_and_weaknesses: **Strengths** 

- A generalization result of offline linear MDP to differentiable function class and incorporation of variance information 

- The paper is well-written and easy to read 

- The remark about feature representation and parameters looks interesting and can give some room to think more about the problem of representation learning in offline RL.

**Weaknesses** 

- The data coverage assumption 2.3 is pretty some as it is equivalent to the uniform feature coverage assumption when realized to linear MDP, which is among the strongest data coverage assumption. 

- Optimization oracle at line 4 of Algorithm 1 is pretty strong as obtaining the global minimizer for a non-convex differentiable objective is difficult unless it is an overparameterized neural nets (see also the next point)

- However, the dependence on $d$ in the learning bound makes their result inapplicable to overparameterized neural networks where $d$ could be a high-order polynomial of the number of samples

- The assumption about third-time differentiability also cannot apply to neural networks (not necessarily overparameterized) with non-smooth activation such as ReLU. 
clarity,_quality,_novelty_and_reproducibility: - RHS of the equation in Corollary 3.3.: Remove the dot product <,> inside $\hat{f}$

- ”PFQL draws a unified view of model-based and model-free learning”: This is a bit unclear to me how PFQL is relevant ot model-based learning. 

- It’s interesting to root of 1/4 in Theorem 3.1. Where it comes from? 

- ”Assumption 2.3 reduces to 2.4” —> “Assumption 2.3 reduces to Example 2.4”
summary_of_the_review: See the strengths and weaknesses section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies offline reinforcement learning with differential function approximation (DFA) indexed by a parameter. Leveraging the ideas in DFA and the pessimism principle, the authors propose a value-iteration-based algorithm and analyze the suboptimality of the learned policy. The theoretical results generalize previous asymptotic analysis for DFA by constructing a finite-sample uncertainty quantification for the fitted value functions. A variant based on variance reduction is also provided and analyzed. The authors also discuss a few implications of this framework. 
strength_and_weaknesses: Strength:

1. This paper provides a new algorithm and finite-sample analysis for offline RL with DFA. The theory seems sound because the main arguments look correct to me, although the analysis is too overwhelming hence I did not check all the details. 

2. This paper provides a comprehensive discussion of the application of existing results to the DFA setting, including the pessimistic value iteration and its variance reduction results. 

3. The authors did a good job in positing this paper in the related literature, and include detailed discussion on the implications, making this paper fruitful and dense. 

Weakness:

1. All the results seem to be generalizations of existing algorithms and theoretical results. It may be helpful if the technical novelty can be discussed more thoroughly. 
clarity,_quality,_novelty_and_reproducibility: Quality: This paper is of good quality overall. 

Clarity: The results are clearly stated and related to the existing literature. 

Originality: Although the FDA setting seems less studied, I have the impression that the technical novelty of this paper is limited, or at least the authors need to highlight such novelty more. 
summary_of_the_review: I find this paper to be good overall. It provides new algorithms and analyses that generalize the existing ones to the FDA setting, and is quite intensive and comprehensive, covering almost all aspects of value iteration with offline data. This is a solid work although I find the technical novelty to be not very pronounced.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: ## Summary
This paper provides a systematic study of understanding of the statistical complexity for offline RL with differentiable function approximation (DFA). The paper analyses the *pessimistic fitted Q-learning* (PFQL) algorithm and show that PFQL with DFA is provably efficient. The paper improves the sample-complexity with horizon dependence but the sample complexity still depends on $d$. The paper focuses on theoretical results without any empirical verification.

*Decision:* Overall the feedback from the reviewers were positive. The initial reviews were all leaning towards acceptance. It seems like authors have done a good job on addressing some of the feedback and concerns raised by the reviewers during the rebuttal. I think this work is a valuable contribution to the ICLR community.

## Strengths
- The theoretical results on sample complexity with DAF for ORL is novel and a valuable contribution.
- The paper is well-written .
- Opens up a pathway for further research on problem of representation learning in offline RL.

## Weaknesses
- Some unclear statements pointed out by Reviewer 7cjK and Reviewer eR8G which are mainly addressed by the authors in the final revision.
- The data coverage assumption 2.3 is very strong.
- The theoretical results in this paper don't apply to existing overparameterized neural networks.


justification_for_why_not_higher_score: Although the paper is well-written and significant or important contribution which would hopefully open more research in this direction. The results still only applies to generalized linear models only. The results are only theoretical for now.
justification_for_why_not_lower_score: The paper is a novel contribution to an important growing area of research. Possibly opens up new research in this direction. Thus it is worth publishing at ICLR 2023.
Decision: Accept: poster