Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper focuses on OPE for linear MDPS in an offline setup. The proposed algorithm accounts for the value-function variance in the dataset, and bounds the resulting value error as a function of that variance.
main_review: The paper is written fairly well, though there are several grammar errors or typos. As an example, line 85: "there exists \gamma_h and \mu_h...". Nonetheless, I appreciate the idea of using the variance to improve data efficiency. The results seem like they make sense. But, specifically, I have the following several questions to the authors:
1. Why exactly do you split the data? In Sec. 2 you suggest this would be explained in Sec. 3, but I didn't find such an explanation.
2. The expectation of the weighted covariance matrix in (2.6) is taken w.r.t. \tilde{\pi}. If I understand correctly, it means that directly using the data to estimate it is straightforward. However, the variance inside that equation is taken w.r.t. \pi. How is that done? I can't find a place in the text or algorithm which show how you reweigh the variance to match the target distribution.
3. I don't understand how the norm in Remark 4.3 characterizes the distribution shift. I guess this relates to my previous question. 

After I understand the answers to the above questions I can decide whether I think this paper should be published or not. In other words, I'm open to change my score either positively or negatively. 
limitations_and_societal_impact: Irrelevant.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the off-policy evaluation (OPE) problem in reinforcement learning with linear function approximation. They propose to incorporate the variance information of the value function to improve the sample efficiency of OPE. This has better theoretical properties.
main_review: 1.As for the final variance estimator \hat{\sigma}_h, why use a mechanism similar to clip? And using it, we can get \hat{\sigma}_h>1, this is very different from variance. so what is the motivation to set such range?
2. The paper said "Theorem 4.1 suggests that Algorithm 1 provably achieves a tighter instance-dependent error bound for OPE than that in [10]."  But from formula (B.1), the dominant term in error bound is not better than [10]. And What about the rest of error bound?
3. in experiments, From Fig.1. ,  the variance of the proposed methods is very large. In general, the larger the variance, the more unstable the OPE error.
limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The variance-aware OPE method uses the estimated variance of the value function to reweight the Bellman residual in Fitted Q-Iteration. It shows that the algorithm achieves a tighter error bound than the best-known result.
main_review: It is a really good paper with high quality. Especially, such a variance-aware structure helps people to understand what is essential in the linear MDP model and improves over the existing Duan et al. in a non-trivial way (from the statistical sense). The use of two folds of data to estimate $\widehat{\sigma}$ is neat and the fisher information interpretation for $\Lambda^{-1}$ is appropriate. I think it makes a very good contribution to the OPE community for the purpose of understanding instance-optimal / problem-dependent RL.

Only one small concern: it would be better if $s_{k, h}^{\prime} \neq s_{k, h+1}$ can be got rid of (especially Yin et al. does not really use this, their data is coming in a sequential way). But I can understand the authors since without this the analysis could be nasty due to the data dependence within the episodes. 

An additional comment: since your bound include the variance structure, in the special case of tabular MDP, could your result match the dominate term in Yin & Wang 20 (square root of their MSE bound)? It would interesting if your result can achieve that since their bound is statistically optimal (matching the Cramer-Rao lower bound) for tabular RL.  

This is within one of the best in my batch therefore I will choose my score as acceptance.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new off-policy evaluation (OPE) algorithm in the finite horizon MDP setting. The reviewer finds the new results are sightly incremental compared with the existing results and thus suggests not accepting the paper.
main_review: This paper proposes a new off-policy evaluation (OPE) algorithm in the finite horizon MDP setting. Compared with the regular LSVI-type algorithm, the proposed algorithm involves an extra estimation step on the variance of the next-step state value and uses it to reweight the sample in the least-square regression for estimating value functions. The theoretical analysis shows that the leading term of the OPE error bound now depends on the weighted coverage matrix rather than the original coverage matrix.

My main concern is that the new theoretical result is, most of the time, equal to the previous result, while it is hard to say that it can be better than the original results with regard to the order of H. This is because the variance $\sigma(s, a)$ in average is just of order H. There might be certain state-action pairs having close-zero state-action values or having a deterministic transition distribution to the next state, but the difference showing up in the new error bound is not clearly an improvement since it does not change the order and the constants can not be directly compared.
limitations_and_societal_impact: yes
review_title: null

Meta-review: This paper studies off-policy evaluation in linear MDPs. The authors extend the FQI work of [10] by reweighing the Bellman residual by an estimate of the value function variance. This slightly improves the instance-dependent sample efficiency, by up to a factor of H.
The paper is fairly incremental compared to [10] and of somewhat limited scope, but executed well overall to warrant acceptance.

Decision: Accept (Poster)