Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper propose an algorithm named Constrained Pessimistic Policy Optimization (CPPO) for offline reinforcement learning, and PAC guarantees are provided for many specialized Markov Decision Processes under the partial coverage assumption of offline data.
main_review: "worse performance": the theoretical performance provided here is somewhat worse than prior arts. For tabular MDP, many results show a linear dependence of S, which is much better than Corollary 1. In addition, the linear mixture MDP doesn't include linear MDP as a special case, which is misleading. Definition 3 is different from the standard definition of linear MDP, which doesn't assume $\mu$ is known. This is substantial since the dimension of standard linear MDP is $Sd \gg d^2$. Summing up, a linear rate w.r.t. model dimension is achieved for CPPO, which is worse than the general sub-linear rate.

"computational issue": the authors should discuss the implementability of the proposed algorithm, which is missing here. As for me, CPPO is much more impractical than prior arts.

"model based vs. model free": the definitions of model based/model free are strange for me. Many "model free" results stated in this paper are commonly considered as model based methods, such as methods for tabular MDP and linear MDP and so on. Specifically, in tabular MDP, one constructs an empirical MDP with penalized rewards first, and then solves this model to get an optimal policy. In linear MDP, one uses least square to deal with the empirical MDP with penalty. The authors should make clear of this point.

"technique correctness": in Corollary 2, $c_3$ is at most $1/S$, which seems to be considered as a constant here.
summary_of_the_review: Given the above technique issues, I think this paper is not ready for publication.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper builds on a recent trend of pessimism for offline RL to return high performance policies on an event with large probability. 
The contribution of the paper is theoretical, and about model-based methods.
main_review: The work takes a model based perspective, where a general, intractable algorithm is proposed first.

The advantage of model based algorithm in certain applications (for example the lack requirement of Bellman completeness) is well motivated, e.g. remark 2 and also the conclusion. 

The bound is then specialized to several well studied setting of interests. Among these, the low-rank setting with unknown features is of particular interests. Per my understanding the computational tractability of the method is not discussed, and the algorithm is therefore not efficient in that respect.

Since the algorithm is model free but many proposals in this space are model-based, this work is a first serious attempt at a offline model based RL with pessimism.
summary_of_the_review: The paper provides a first good attempt at offline rl with pessimism, and should be accepted.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the model-based approach to offline RL employing the pessimism principle, which complements the line of research on model-free pessimism. Based on TV distance between the learned MLE model and the realizable ground truth, PAC guarantee of the learned policy is established for various examples, some of which have not been tackled with model-free pessimistic methods. 
main_review: Strength:
This work contributes to the literature of pessimism principle for offline RL by taking a model-based approach. It is an important complement to model-free type works by showing another way to get things done. 
The various examples unveil some untackled problems that can actually be dealt with the model-free framework elegantly. 
Comparison of state-of-the-art works is detailed and essential, which might be of use for upcoming works in the field. 
The paper is in general clearly written and main points are neatly presented. 

Weakness: 
The advantage of tackling infinite policy class is a little bit over-advertised. In model-based approach, the hardness of learning with complex policy class naturally takes over to complex model class. In fact, model-free approaches (e.g., Xie et al., 2021) can also deal with infinite policy class with bounded complexity. That’s why I feel the point a bit over-advertised. 
Implementation feasibility: Is the model-based approach easily implementable like function approximation with bonus functions (e.g., Jin et al, 2020)? It would be nice to have some discussions on this point. 

Other questions: 
Dependence on model class complexity: When the model class is infinite, the learning performance of MLE requires complexity measures like bracket numbers, hidden in the \xi_n in Appendix A. Is there any intuitions on how it compares to model-free approach? 
summary_of_the_review: In general, the paper is well written and main points are neatly addressed. With a model-based approach using concentration properties of MLE, this work contributes to the literature of pessimistic offline RL and shows various concrete examples the framework can deal with. Some weakness include the over-advertisement of tackling infinite policy class, and lack of discussion on feasibility of implementation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied offline RL for policy optimization and proposed a model-based algorithm with guarantees that can hold under partial coverage. The results can cover several existing popular model classes.  
main_review: Offline RL is a hot topic nowadays and relaxing the full coverage condition in theory is important. Overall, I feel this paper contains lots valuable results and is the first of such kind of guarantee for model-based algorithm+partial coverage. But more or less I feel a bit less exciting after reading the paper since it's hard to get the strong point. It should not be the case that If there exist guarantees for model-free algorithm under scenario A and B, we must have guarantees for model-based algorithm under scenarios A and B. I would like to gain some insights on why we want to study model-based algorithms in this offline setting over a model-free algorithm. Pessimism has been studied in quite a few other papers and so is the partial coverage condition. 

Some specific comments: 

1. One concern is about the algorithm. I do not feel it's a real algorithm and can be implemented in an efficient way. I hope the practitioner can gain some insights on algorithm design after reading the theory paper. In particular, even for linear mixture MDPs, you need to integrate over the whole state space which loses the computational efficiency. Please correct me if I am wrong. And no experiments which are a bit disappointed. It will be good to see the comparison between model-based algorithm and model-free algorithm with pessimism. 

2. I appreciate the authors would like to include as many examples as possible but some of them are not quite well-explained and the paper now is a bit dense. For example, the offline representation learning with a low-rank structure is not well-motivated. And there is no even motivation why people should study this. Is there any technical challenge? If so, it should be discussed clearly. Again, it might be hard to get the key point since for each setting, the rate has been studied and is not supervised.  

3. It may not be fair to say model-free offline RL approaches often require additional structural conditions in the function class (e.g., Bellman completion). The linear mixture MDPs might be a worse condition since it compresses too much information and there is no empirical evidence to justify it as far as I know. It's purely invented to prove something.

4. About the function class. What do you mean by "general function class"? What's your function class complexity measure, like VC-dimension or Rademacher complexity or else? In Theorem 1, I just saw |M|. Does it mean M has to be finite?
summary_of_the_review: This paper provides rich theoritical results for the important offline RL problem but it's a bit lacking a strong exciting point.
review_title: null

Meta-review: In this paper, the authors consider the offline RL with only realizability and partial coverage assumption, under which a model-based pessimistic policy optimization algorithm has been proposed and rigorously justified. Moreover, variety of special MDP models, including kernelized nonlinear regulator and linear mixture MDP, have been plugged into the general framework, which leads to different specific algorithm and refined guarantees. 

In general, the reviewers are positive to the submission. However, there are still issues need to be further discussed, 

- *Computation feasibility*: most of the reviewers raise the same concern about the computation feasibility and efficiency. Specifically, the proposed algorithm is too complicated, and thus, may not be practical. 

- *Comparison with existing statistical results*: both reviewers and I appreciate the summary in the paper about the coverage assumptions in the existing methods. However, a similar table for summarizing the complexity of existing algorithms, as well as detailed discussion, is also necessary for a better position of the proposed method among the literature, including both model-based and model-free RL.
Decision: Accept (Poster)