Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analyzes the plug-in approach to off-policy evaluation and optimization in reinforcement learning, and sharpens some of the sample complexity bounds (assuming sufficiently exploratory data, time-homogenous MDPs). The key novelty is in upper-bounding the variance of estimated values cleverly by using higher-order powers of appropriate values. By doing so, the paper's derived bounds do not directly depend on the horizon of the MDP. One benefit of the proposed analysis is that a very similar line of reasoning is sufficient to derive horizon-independent bounds for both evaluation and optimization, as well as for tabular MDPs as well as linear MDPs with additional structure.
main_review: (After author feedback)
The authors' responses adequately addressed questions around significance, motivation and technical concerns. There were remaining questions about the novelty/originality and scope of contributions. The paper can be substantially stronger by addressing them (e.g. by weakening Assumption 2).

-----
The paper had a reasonable exposition, and the high-level ideas were explained clearly. This review focuses only on the weaknesses.

Correctness: Stepping through the appendix, there were two confusing points (detailed below). This makes me confused about Theorem 1 and 2. If this confusion is clarified, the paper would improve to be borderline. Given the confusions, I have not carefully checked the proofs of the policy optimization theorems.

Originality: The main idea is to use the total variance bounding technique of [27] in the off-policy setting. This is done in a pretty brute-force way (assume that there is sufficient exploration via Assumption 2). The derivations become somewhat more tedious (keeping track of the coverage coefficient in each step) but not novel.

Significance: Disappointed to see that motivation of the work was not clear. Beyond an academic exercise in sharpening the upper bounds, does this help explain some previously unexplained phenomenon? For instance, in practical applications of the plug-in approach, do we see that it works surprisingly well as H increases (while existing theory suggested that it should not)? 
Are there practical applications where Assumptions 1 and 2 (and for linear MDPs, the anchor data assumption) can reliably hold? Under the exploratory data assumption, would other approaches have a H-dependence even in time-homogenous MDPs? For instance, an off-policy policy gradient approach might depend on H while the plug-in approach does not (and this might guide us to choose the latter in large-H regimes). 
The anchor data assumption and construction was unusual to me. Are there practical applications where they are useful? (If not, they seemed to be just assumptions of convenience so as to transport results from tabular MDPs to linear MDPs without having to construct an epsilon-net). 
The paper unfortunately does not address any of these questions to establish the motivation or significance of its contributions.

Confusions:
Appendix B [Proof of Theorem 2]
0 <= c_1 <= 1. And 0 <= c_2 <= c_1. In Line 619, when setting c_2 = c_1 - ...(H), note that c_2 < 0 for large values of H which is not allowed.
But c_2 has to be set to such a term to witness a value gap that scales with H which is needed to assert the claim in Line 622.
Please clarify? I am skeptical that this MDP construction will witness an Omega(sqrt(H/(n*d_m))) estimation gap under Assumption 1 and 2.

Appendix A [Line 555]
Perhaps derive V_1(i) <= H for all i using Assumption 1 to make this more explicit.
This statement is easy to show under the uniform reward assumption that r_h < 1/H.
However under assumption 1, it takes more to assert this claim constructively. For example, time-homogeneity rules out situations where r_H = 1 and r_h =0 for h < H; and situations where a set of states only become reachable at H. In such situations however, this claim is false. Does time-homogeneity rule out all pathological situations where V_1(i) > H for some i?

Minor issues:
- Since Table 2 and Section 2 require knowing what Assumption 1 refers to, it may be better to define it in Sec2, and simply re-state it in Sec 4.2.
- Notation collision: r is defined as E[R] above. Unfortunately, r_i \sim P(R). This makes some objects ambiguous.
For instance, the empirical reward in Line 186 should be hat{r}(s,a) = \sum_i r_i 1{...}/n(s,a). As written currently, r(s_i, a_i) can be misunderstood as the expected reward of (s_i, a_i) rather than the realized reward r_i. This also affects the statement of Assumption 1 (what is r_h exactly? is there a typo in Line 198, r_i should be r_h?).
- Clarify the empirical MDP construction hat{M} for P(.|s,a) and R(s,a) when n(s,a)=0. Or specify the regime (under Assumption 2) clearly.
Perhaps bring Assumption 2 into Sec 3.2?

Typos:
Line 45 - related *line* of work
Line 47 - only *has* poly log
Line 65 - that *has* broadly
Line 84 - we *need* to deal
Line 155 - *even though P and R remain invariant when h changes*
Line 158 - cumulative *reward under policy \pi* is defined
Line 165 - perspective *on* policy evaluation
Line 177 - *computationally* efficient
Line 212 - min_s,a n(s,a) \approx H*K*d_m. The \forall s,a is superfluous.
Footnote 3 - lower bound *has* been provided
limitations_and_societal_impact: The authors do not address the societal impact of their contributions. However, this is a completely theoretical work that aims to sharpen the analysis of an existing algorithm, incremental improvement by using a known technique. So there societal impact of this work is unlikely to be adverse.
Re: the limitations, the authors do not discuss the plausibility of their assumptions nor the motivations of the linear MDP w/ anchor points setting.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provided horizon-free theoretical results for offline policy evaluation and improvement. It showed the bound for estimation error and sub-optimality under several assumption.
main_review: Originality. The proof of their results is origin.

Quality. This is a complete work. The showed both upper bound and lower bound under their assumption. However, the assumption might be too strong. Apart from the assumption previously notice, time-homogeneous is also strong since some other work on offline RL does need it.

Clarity. This paper is well-written. 

Significance. This paper is significance in the sense that horizon-free results can deepen our understanding for episodic RL.
limitations_and_societal_impact: The author addressed their limitation adequately.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The authors revisit offline RL on episodic MDPs both in the tabular and linear with anchors cases. They prove complexity bounds that are nearly horizon $H$ free (up to polylog terms in the horizon $H$), when the maximum return is 1 for both offline policy evaluation and offline policy optimization.
main_review: This is a remarkable theoretical paper. I took a great interest reviewing it and I think it will have a great impact in the offline policy evaluation/optimization community.

Major remarks:
- The writing around the assumptions is not as sharp as everywhere else:
   - line 197: almost surely -> It is with respect to the stochasticity or R and P? But since they are defined on a finite MDP, and since it is a finite sum, either this event is $0$ or $>0$.
   - lines 201-202: Assumption 1 is equivalent to the uniformly bounded reward isn't it? When moving from one to another, and back, you lose a factor $H$, but otherwise, they are equivalent.
   - line 203: it can be generalized but as I said in my previous remark, a factor $H$ appears, so it defeats the main arguments of the method.
   - Assumption 2 seems unnecessary to me. The actual assumption that matters and that is not formalized as such (even though it is well recalled in theorems), is that $K= \tilde{\Omega}(1/d_m)$.
- the actual dependency in $H$ is actually hidden in $d_m$: the longest horizon the MDP is the more skewed is going to be the state visitation distribution of any policy. And to prove that, many papers have shown that model-based planning (which may be wrongly called, because performing q-learning on the samples themselves until full convergence would lead to the same result) lead to worse performance than pessimistic/conservative planning **on average**. Maybe the authors should be more explicit about this effect.

Minor remarks:
- lines 64-66: I could not understand this sentence.
- line 98: refers to assumption 1, while it is only enounced 2 pages later.
- table 1: you use $\epsilon$ in Table 1, but it is introduced only line 113. Also, the writing about table 1 does not use the same parameters for the bounds, so it is a bit inconsistent.
- line 155: even -> even though.
- line 158: of $\pi$ -> delete
- lines 171-172: $(s_i=s,a_i=a,r_i,s'_i)$ and $(s_i=s,a_i=a,r_i,s'_i=s')$
- lines 275-276: local policy optimization was already done by Kakade2002, Petrik2016, and Laroche2019, just to name a few.
- lines 282-284 are a repetition of lines 280-281?


[Kakade2002] Kakade, S., & Langford, J. (2002). Approximately Optimal Approximate Reinforcement Learning. In International Conference on Machine Learning.

[Petrik2016] Petrik, M., Ghavamzadeh, M., & Chow, Y. (2016). Safe policy improvement by minimizing robust baseline regret. In Advances in Neural Information Processing Systems (pp. 2298-2306).

[Laroche2019] Laroche, R., Trichelair, P., & Des Combes, R. T. (2019, May). Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning (pp. 3652-3661).
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides near-matching, horizon-free upper and lower-bounds on the Offline Policy Evaluation (OPE) and Offline Policy Optimization (OPO), in finite horizon time-homogeneous MDPs, with tabular and linear MDP structures with anchor points.
main_review: The presentation of the paper is clear and illustrative, therefore I believe substantial improvements have been made since the previous submission in terms of paper polishing.

The additional setting of linear MDP with anchor points, on the other hand, seems not substantial. It's not a well-accepted setting and the analysis seems to be a straightforward extension of the tabular analysis, since after all anchor point means only d (s,a) pairs matter and so everything can be represented back into a table. Unlike the ICML reviewers, I think even the tabular results alone are worth publishing as a theoretical paper.

Besides that my main complaint is also on the strong assumption of uniform data coverage, which is too strong for most applications. A recent line of work performs offline reinforcement learning without a uniformly lower-bounded data distribution with the principle of pessimism. It has been shown that the optimal policy can be found as long as the offline data properly covers the visitation distribution of the optimal policy. Can the author comment on whether horizon-free learning possible without the uniform data coverage assumption? Also, this line of work is also worth covering in the related work section. 
limitations_and_societal_impact: NA
review_title: null

Meta-review: According to the reviews, which are all in favor of accepting the paper (although most of them only slightly), this is a solid contribution for which I recommend acceptance. The points raised in the reviews and discussed in the rebuttal (e.g. concerning motivation and some of the debated technical details) shall be taken into account when preparing the final version.
Decision: Accept (Poster)