Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes the use of Bellman-consistent pessimism for offline RL with general function approximation (under realizability and completeness assumptions), and manages to obtain non-trivial "dataset-dependent" sample complexity guarantees that generally hold under all possible data coverage scenarios of the dataset (i.e., the sample complexity bound gracefully degrades from guaranteeing a near-optimal policy under standard coverage assumptions to offering no improvement over the data collection policy in the most degenerate case). Such adaptivity makes the proposed approach attractive as it does not rely on any specific data coverage assumption. The paper provides two algorithms: the first attains sharp theoretical guarantees in a computationally inefficient manner, while the second attains worse guarantees in a more practical way.
main_review: Originality: While the use of pessimism in offline RL to avoid strong data coverage assumptions has already been studied in many recent papers, this paper has a clear discussion of prior works and clearly demonstrates its new contributions beyond prior works. I particularly enjoy the decomposition of the error bound (into on-support and off-support components) and the related statistical analysis, which bring new technical insights to this field.

Quality: The paper is technically sound and the claimed results are correct.

Clarity: The paper is well-written and I enjoy reading this paper.

Significance: Compared with prior works which use other notions of pessimism to obtain other forms of "dataset-dependent" performance guarantees (e.g., Liu et al. 2020 [15], Jin et al. 2020 [16]), the approach proposed in this paper enjoys several advantages such as more general guarantees under weaker coverage/function class assumptions. The ability to automatically adapt to the best bias-variance tradeoff in terms of $C_2$ is particularly important, as the hyperparameters tuning tasks commonly required in prior works are in fact very challenging in offline RL. 
On the downside, I would like to say that most of the results in this paper are still far from being practical (see the limitation section for more details). Still, they are definitely important theoretical contributions.

Minor Comments:

1. In the abstract, the notation $d$ is used without any explanation. It would be better to say something like "$d$-dimensional linear MDP" earlier.

2. Line 69: The use of "where" before "most prior approaches" seems strange. Did you mean "whereas"?

3. Line 154: It should be $\Delta f_{\pi}(s_0,\pi)$ rather than $\Delta f(s_0,\pi)$.

4. Line 177: "Rather than committing to"

5. Algorithm 1: $\eta$ should also be input.
limitations_and_societal_impact: While Bellman-consistent pessimism brings some theoretical advantages over prior pessimistic approaches, it also introduces additional issues which may make it perform worse than prior approaches in practice. The original form of Bellman-consistent pessimism (described in Section 3) is definitely very difficult to implement, and the paper provides a more practical variant PSPI in Section 4. However, PSPI only has a much slower $O(n^{-1/5})$ rate in general, which makes it not necessarily more appealing than prior algorithms (e.g., the ones in Liu et al. 2020 [15]) when one wants strong statistical performance. Moreover, since the algorithms in Liu et al. (2020) may converge much faster than PSPI (the former should converge in $O(\frac{\log n}{1-\gamma})$ optimization rounds while the latter may require $O(n^{2/5})$ optimization rounds), the computational complexity of PSPI can be much higher (as in each optimization round PSPI needs to solve a regularized loss minimization problem). Finally, while the authors claim that an important advantage of Bellman-consistent pessimism is that it does not require a density estimation step (and I fully agree with this point), the current paper assumes a known deterministic initial state $s_0$; when $s_0$ is generated by an initial state distribution $d_0$, I would expect Bellman-consistent pessimism to require the knowledge of $d_0$ --- note that estimating $d_0$ from the batch data may also involve density estimation, and the final performance bound may degrade with the estimation error of $d_0$.

Of course, every approach has limitations. The paper's theoretical contributions are significant.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the idea of pessimism in offline RL not through the addition of (negative) bonuses, but by incorporating pessimism implicitly in the loss function. This brings several advantages, see detailed comments below.
main_review: There are several things to like about the paper.

1) handling of general function classes
2) approximation error evaluated over distributions rather than point wise
3) related to 2), the transfer error notion is the weakest I’ve seen in this space
4) while the algorithm is theoretical, a computationally tractable implementation is given. 

The implementable version has a bad convergence rate but the authors give a sound explanation for why this is the case (increased complexity of the policy class). I agree with them that this can likely be lowered substantially on specific function classes.

While I have a very high opinion of the work, I think in few places the exposition may need to be improved. Already in the abstract:

1) “Our theoretical guarantees only require Bellman closedness as standard in the exploratory setting, in which case bonus-based pessimism fails to provide guarantees”
Asm 2 requires `completeness’ with regards to any policy in the prescribed class, not just the greedy one as commonly done in online RL (e.g., Zanette et al ’20, Jin et al ’21, Du et all ‘21, Jiang et al. '17). Thus, your assumption is much stronger as every policy in your policy class needs to play nice with the prescribed function class. 

2) ``Our result improves upon a recent bonus-based approach by O(d) in its sample complexity when the action space is finite.’’ 
I would put more emphasis that the action space needs to be small (non-exponential in d). There is a well known sqrt(d) gap between the small & large action space already in linear bandits.

Minor: the completeness assumption could be further motivated by recent lower bounds already in the linear setting (which you cover with your more general theory); for policy learning, the work Weisz et al ’21 (Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions) implies an offline lower bound of the same order and likewise Zanette ’21 (Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL) has explicit lower bounds for policy learning in the offline setting. 

limitations_and_societal_impact: none
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the pessimism in offline RL with general function approximation given i.i.d. transition data. An information-theoretic analysis is established for an inefficient method, where instead of point-wise pessimism, a notion of Bellman-consistent pessimism is considered. In this way, the theoretical guarantee is established only under closedness assumptions. An instantiation to linear MDP is considered and improved upon literature. Besides, a practical and efficient policy iteration method is proposed, whose performance is analyzed as well.
main_review: Originality:
The work falls under the umbrella of pessimism for offline RL. The notion of Bellman consistent pessimism is novel and settles the problem of offline RL with general function approximation in an elegant and standard way. 

Quality:
The results are generally technically sound. I've briefly gone through the proofs and they look sound. 

Clarity:
The paper is clearly written and well organized, with examples illustrating implications of main results.

Significance:
This work is an important step forward in understanding and practicing pessimism for offline RL under general function approximation. Though the data generating process (i.i.d. transitions) is a bit simplified, it will open the possibility for future research. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies offline reinforcement with function approximation, where the function class is general (but finite), without the strong assumption of coverage of the dataset. It proposes an algorithm based on a new notion of Bellman-consistency combined with pessimism that is applied globally (at the initial state) and not point-wise. Under realizability and completeness, the authors prove general suboptimality guarantees against any policy that depends on the level of "mismatch" with the data distribution. This bias-variance trade-off is optimized implicitly in the analysis without requiring tuning of specific hyperparameters. Finally, the authors provide a computationally efficient version of the algorithm that preserves the nature of these theoretical guarantees.
main_review: This is a good paper. It addresses an important subject - offline RL with general function approximation (actually general without assumptions like bounded Eluder dimension), and attempts to eliminate a problematic assumption - coverage of the dataset is clearly not achievable in many settings. I really like the approach for dealing with limited coverage - the implicit trade-off using the $C_2$ constant is a powerful result that is also very intuitive. I also like the practical variant of the algorithm although its convergence rate is quite slow, since it manages to leverage mirror descent techniques in the offline setting. I am familiar with these only in the online setting, were they previously used for offline RL as well? If so, it should be discussed.

However, I still think that there are some concerns that must be addressed before I can vote this paper a clear accept.
One thing that really bothered me is that $\epsilon_r$ depends on $\epsilon_{\mathcal{F}} $. The problem is that $\epsilon_{\mathcal{F}} $ cannot be computed (even without thinking of efficiency) since we do not have access to the Bellman operator. I understand that in many related work this is completely circumvented by assuming strong realizability (i.e., $\epsilon_{\mathcal{F}} =0 $), but I feel that it is a little bit of a hidden assumption - one cannot really instantiate this algorithm and get the guarantees of theorem 3.1. Do the authors have a suggestion about unknown $\epsilon_{\mathcal{F}} $?

While the authors provide a good amount of discussion, there are a few points where I needed more intuition and explanation.
The first point is definition 1 which is hard to process so early in the paper and could use better explanation/intuition in the lines that follow. For example, is there a good reason for this parameter to be small for many policies?
Another point is in theorem 3.1 where the second term in the bound is very hard to comprehend. Although the authors try to explain this in the discussions that follow, I was still missing a basic description of this term (in words) and maybe some examples.
Moreover, I couldn't understand how figure 1 helps to illustrate it.

As a non-expert in offline reinforcement learning, I was missing more comparisons to related work and clear statements about what a previous paper did compared to what the authors did - both in terms of results and more importantly techniques. For example, what is state-of-the-art for offline RL with coverage explicitly? what techniques did they use? why does it break when there is no coverage? how does your approach deal with that?
A specific point that bothered in the context of related work is line 120 where the authors say that completeness assumption can be only avoided in some rare cases and cite [22]. I looked at that paper and it looks like this case is not that rare - general function class with only realizability assumption albeit with some coverage assumption. Does the "rare" term reflect the coverage assumption? Is it because this is the only paper? I feel like this should be described a lot more clearly.

To me it looks like the bound on the complexity of $\Pi_{SPI} $ in the efficient algorithm is way too trivial. Did you attempt to prove better bounds on it in the general case (of course in many examples it is going to be small)? Is it not possible in the general case? If so, you should provide an example where this complexity really grows exponentially with $T $.

Finally, just two typos I found. In the equation after line 151 you use $\epsilon_r $, but it is defined only a few lines afterwards. Is it supposed to be $\epsilon$ there? Also, I couldn't find equation 4.1. Looks like it should be the equation after line 284. Is that correct?

Post rebuttal: I thank the authors for these clarifications and raise my score to 7.
  
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: Reviewers agreed that this paper constitutes a significant step forward for offline reinforcement learning with general function approximation, as it facilitates weaker notions of both transfer error and approximation error than prior work. While the algorithm in the paper is primarily theoretical, the authors also give a more practical/implementable version, which is valuable as well. In addition, the paper is clear and well-written.
Decision: Accept (Oral)