Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes and analyzes the adaptive pessimistic value iteration algorithm for offline reinforcement learning. The authors study the sample complexity of the proposed algorithm and prove matching upper and lower bound. The paper also studies the regime where no assumption about the behaviour policy is made and provide a sub-optimality upper bound. 


main_review: The main idea of the paper is to use Bernstein-type confidence interval in the algorithm and analysis, which gives the improved bound over the Hoeffding-type analysis (Jin et al. 2020). The authors provide thorough theoretical analysis including matching regret upper and lower bounds which is very nice. This paper is also well written and the problem setup is clearly defined. 

However, I still have the following concerns and questions. Please address these in the rebuttal and correct me if I misunderstand some critical part of the work. 

The advantage of using Bernstein-based analysis over the Hoeffding-based analysis is well established in the theoretical RL literatures. This makes the contribution of the paper somehow incremental and less interesting, although it seems that this is the first attempt to use such technique in offline RL. 

I think to study the sample complexity in offline RL, we first need to understand how to define “the optimal” algorithm in this problem. The minimax optimality is too weak as a criterion in the offline setting as it only considers the worst case, which gives a dependency on the minimum data coverage. So it seems that any algorithm that makes prediction based on the confidence interval is minimax optimal. Also, it is recently known that in offline RL, no algorithm can be instance-dependent optimal. And in fact, any “reasonable” algorithm, including pessimism, plug-in or even optimism, can find some niche where it dominates all the other algorithms (see [1] for details). So no matter how the confidence interval is constructed in practice (either Hoeffding-type or Berstain-type), it’s still not possible to get an "optimal" algorithm in the instance level. This seems to be a closely related issue that should be discussed in the paper. 

Since we cannot use minimax optimality or instance optimality to study the problem, one can instead define a “weighted minimax” with different weighting scheme, like the one used in the paper, the visitation under the optimal policy used in Jin et al. 2020, and the optimal value prediction error used in [1]. The choice of the weighting is kind of arbitrary as we have already known that any algorithm is good in some problem instance and we just need to find a weighting that is attached to the properties of good problems. I think this is the reason why both APVI and PVI can match the "corresponding" lower bound. 

Regarding the extension to the no-assumption case, I think the result presented in Theorem 5.1 is not very interesting. The result just says that if $\pi^*$ is not covered the algorithm will suffer linear regret. I think the assumption that $\pi^*$ is covered by the behaviour policy is actually acceptable. Otherwise if there is no information can be collected in the data the best an algorithm can do is to make a random guess. Please correct me if I made a mistake on this. 

[1] Xiao, C., Wu, Y., Mei, J., Dai, B., Lattimore, T., Li, L., Szepesvari, C. and Schuurmans, D., 2021, July. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning (pp. 11362-11371). PMLR.

limitations_and_societal_impact: No societal issue has been found.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: They propose a lower bound under the weak coverage assumption for offline RL. The lower bound is also reduced to several lower bounds in specific examples. They also show how this lower bound is achieved. 

main_review: * Originality: Main results (lower bound and upper bound) are novel and very meaningful. This paper also unifies several scattered lower bound for offline RL. That’s also a nice contribution. 

* Quality:  In the interest of time, I did not check the proof. But, according to a sketch of the analysis, it sounds correct. 

* Clarity: Yes, it is clear

* Significance: Many theory offline RL people would be excited with this work. I enjoyed it a lot. 


limitations_and_societal_impact: Some minor comments: 

* Line 304:  Var(r_1) is correct? Is it conditional variance? 
*  Line 272:  the use of C^{*} makes the bound sightly problem independent: I guess in the time-invariant setting, the dependence on C^{*}  sounds very natural since we can get the upper-bound characterized by  C^{*}.  Does it mean using C^{*}  in the time-variant setting is problematic? 
* Probably, worthwhile to note Liu et.al (2020) is assumption-free in a tabular case somewhere. They get an assumption-free result by setting the threshold for the offline data distribution. Then, they obtained an error based on the augmented MDP by this thresholding. Basically, I feel people can always get this assumption-free result by some type of thresholding on top of the original algorithm. Actually, Jin (2020) result is assumption-free (at least they claimed in this way) since there is a threshold parameter lambda.  So, might be not needed to emphasize too much. 
* Is they any relation for the Cramer-Rao lower bound for OPE?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the capability and intrinsic hardness of pessimistic value iteration algorithm in the finite-horizon tabular MDP case when data is i.i.d. collected from a behavior policy. By a fine-grained analysis, the PEVI (reduced to the i.i.d. tabular case) is modified to incorporate empirical variance into the pessimistic penalty term. These empirical quantities converge to their population counterparts, which is also shown by a lower bound as the intrinsic hardness of learning the MDP with data collected by the policy. Extensive examples & special cases are analyzed to provide a comprehensive analysis of pessimistic offline RL in this setting.
main_review: Originality:
This work falls under the umbrella of the pessimistic value iterations framework [Jin et al., 2020], and provides a fine-grained and comprehensive analysis of a special case: tabular MDP with i.i.d. data from a behavior policy. The approach is not novel, but new insights and deeper understanding of offline RL with pessimism are established, which adds to the knowledge of the community. 

Quality & Clarity:
The paper is technically sound and clearly written.

Significance:
The work adds to the knowledge of the community on offline RL by a fine-grained analysis. It might open possibilities of finer understanding of offline RL in more general settings, e.g., beyond tabular, beyond i.i.d. 

More comments:
Strength:
1. The fine-grained analysis of penalty function provides more insights and understanding of the offline RL with pessimism. 
2. The minimax optimal lower bound shows the intrinsic hardness of the problem.
Weakness / concerns:
1. The papers studies the special case of tabular MDP and i.i.d. trajectories, which might be a bit specific compared to the vanilla version [Jin et al., 2020]. 
2. The upper bound is not data-dependent, hence requires large sample size, while the work [Jin et al., 2020] poses no assumptions on the data except a minimal 'compliance' assumption. Would it be possible to give a data-dependent finite-sample version of the upper bound? Why do you prefer the current one?











Reference:
[Jin et al., 2020] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? arXiv preprint arXiv:2012.15085, 2020.
limitations_and_societal_impact: No. Maybe more discussions on limitations of the work can be an improvement.
review_title: null

Meta-review: This paper presents adaptive sample complexity bounds for offline RL. While the technique is not entirely novel, the results are new and interesting in the literature and thus the AC recommends acceptance. The authors are encouraged to incorporate comments from the reviewers.
Decision: Accept (Poster)