Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The papers presents an algorithms called OPDVR (Off-Policy Double Variance Reduction) based on variance reduction, which is seemingly designed with offline RL in mind, even though the main attribute of offline RL (data constraint and lack of support) is fully missed. The paper contains several theoretical results; their core contribution (among others) is for the stationary case, where transition probabilities are not function of time. They basically present a sample complexity that grows with $H^2$, an improvement over previous results by a factor of $H$. The authors provide similar result for the infinite-horizon (discounted) case as well, and expand their findings for the non-stationary case too. 

Main weakness: While this paper is a nice theoretical contribution, discussions on the "practical" impact of the basic assumptions, and how they can be relaxed to become useful in real-world, are missing, [see the comments below]. 
main_review: -- The data coverage assumption, even though it is less strong than others in the literature, is still non-realistic. It must be remarked that in practice (where offline RL matters and indeed aims for), data is given; hence, any assumption about data is meaningless. As a matter of course, in almost all the problems that I know as someone who has been involved in real-world offline RL, only a tiny fraction of the state-action joint space is covered by the data. While I appreciate an interesting theoretical work like the results of this paper, the authors must note that the first step to make something useful in the offline RL literature is to set aside coverage assumptions. Note also that when dealing with situations under data constraints (which should be the definition of offline RL), optimality is no longer a concern, since we know it in advance that it is not feasible; yet in many domains of interest (like healthcare) even small data still contains valuable information and must be used. My strong recommendation always is to focus on how to use limited information in such data, if you hope that your algorithm goes beyond interesting mathematical proofs. 

-- Line 157-160: A policy that satisfies monotonicity condition -> this needs explanation and example. In particular, if you are given an offline fixed data, how likely is this assumption to hold? Without such intuitions the results can easily become misleading.

-- No experimental result is given. Most importantly, you need to justify why someone should care about improving sample complexity by a factor of $H$. As a suggestion, you may start with some fixed dataset and shrink its size in a few stages by randomly removing trajectories from the dataset. And, show the final/best performance of your algorithm against others. Also note that in fixed data scenarios, convergence rate is not a concern for offline RL, almost always.

Minor: Line 87: in the definition of MDP, T is used for transition probability, but replaced by P right after. 

limitations_and_societal_impact: A theoretical work; no direct societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a variance-reduced Q learning algorithm for offline policy optimization, and shows that the proposed algorithm is minimax-optimal up to logarithmic factors.
main_review: The authors extend the variance reduction technique from the generative model to offline scenarios, and achieve sharp error bound on finite horizon homogeneous, finite horizon inhomogeneous and infinite horizon setting. The results are technically sound. I have some minor concerns on the significance of the paper. I want to remark that, such doubling procedure have already been introduced in [1], see Section 3.4 of the corresponding paper. Meanwhile, as the authors point out, in the offline scenarios, the data are highly dependent which leads to additional technical difficulties. However, if I understand correctly, what the author do is only sampling sufficient episodes to guarantee each state-action pair has sufficient number of data with high probability, then we can follow the analysis of the generative model setting. I think the authors should make this difference between generative model setting more clear, if there are some other technical efforts to deal with this issue. Furthermore, I have a question regarding the range of $\epsilon$, as in [1], the results only hold when the number of data exceeds certain threshold, which means the result can only hold for $\epsilon \in (0, 1]$. Does the same issue come here? I think the authors better make some discussions on that.

[1] Martin J Wainwright. Variance-reduced q-learning is minimax optimal. arXiv preprint arXiv:1906.04697, 2019. 
limitations_and_societal_impact: The authors have properly discussed them.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper focuses on the theoretical understanding of offline reinforcement learning. Assuming weak coverage (Assumption 2.1), which appears to be necessary, the authors propose a double variance deduction learning algorithm. The algorithm has two key components: variance reduction (Eq. (2)) that decompose the key estimation of P_t(\cdot|s,a)V_{t+1} into two components that are estimated separately at different stages; and doubling where parameters are instantiated twice. The authors show strong theoretical results of the proposed algorithm: (new) order-optimal sample complexity for the stationary case, order optimal results for the finite-horizon non-stationary setting and improved results for the infinite horizon discounted setting.
main_review: The paper is well written. Although highly theoretical, the paper presents clear structure and intuition to facilitate its understanding.  

The work is a bit outside my area of expertise. While I understood the ideas in the paper, I was not able to fully follow its analysis. The results look good to me with sufficient novelty and technical depth. However, I will yield to reviewers with better expertise in this area. 

I understand that the paper is theoretical in nature and such papers often do not have numerical evaluations. Still, I wonder about the empirical performance and implications of the proposed algorithm. After all, one purpose of theoretical work is to inspire practitioners to develop useful algorithms in practice. Therefore, it would be desirable to see some numerical evaluations of the proposed algorithm, as well as the comparisons with existing algorithms. 



limitations_and_societal_impact: I would like to suggest some discussions on the practical implications of the proposed algorithm.
review_title: null

Meta-review: The submission proposes OPDVR for offline policy optimization, and sample complexities for finite-horizon case and discounted infinite-horizon case are presented. Though some concerns on the pratical side are proposed, all reviewers agree that the paper has a great theoretical contribution. Thus I recommend accept, and also encourage the authors to have some pratical results in the camera ready version. 
Decision: Accept (Poster)