Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: They analyze the linear DM method in detail. They prove that the estimator has an error form, which is written as an inner product of two residual functions. One is associated with the misspecification of Q-functions. Another is related to the misspecification of W-functions. 

main_review:  I appreciate the author's detailed analysis. In this paper, if I understand correctly, the main new finding of this paper is if you have realizability of marginal ratios and the existence of  I-\gamma F^{#}, you can show the PAC guarantee.  

1; if I understand correctly, the non-singularity (existence) of I-\gamma F^{#} is pretty much strong. If you use minimax-type estimators with linear models like modified RBM in CJ 2019 (this paper is for learning but for the modification of policy evaluation is easy), I guess that you can prove the closedness of Q-function class like TQ \subset Q' as you can write like a^{\top} (I-\gamma F) \phi  \subset b^{\top}\phi (Q and Q' are linear models with different radius ) I think this kind of discussion is essential. The present discussion in Section 3.1.1 really does not discuss this point. ( non-singularity of I-gamma F^{#} versus the closedness of Q-function linear class. )

2: Second, UIJKSX 2021 might already show one of the main findings of this paper. They showed that the realizability of marginal ratios and the closedness of the Bellman operator for marginal ratios are sufficient for PAC guarrantee. I think the non-singularity of I- gamma F^{#} essentially says the closedness of the bellman operator for marginal ratios. Pleasee refer to Lemma 4 in UIJKSX. I am sorry if I am wrong at this point.....( Note their estimators are DM methods when using linear models. The estimator is essentially the same as this paper. )

3: Line 341 " To the best of our knowledge, the present study is the first to report the density-ratio-estimation 342 interpretation of linear direct methods in unrealizable settings"
That sounds not correct. For example, if you see UIJKSX 2021, they show the realizability of marginal ratios and Q-functions are sufficient for PAC guarantee by presenting unrealizable settings first (theorem 10). The error takes the product form like the errors for marginal ratios and the errors for Q-functions. (Though this form is different from (6) in the author's paper, you can get rid of the boundedness of F^{#} in their expansion. ) 


[CJ ]Information-Theoretic Considerations in Batch Reinforcement Learning
https://arxiv.org/abs/1905.00360
[UIJKSX] Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency https://arxiv.org/pdf/2102.02981.pdf

-----------------------------------------------------

After thinking more, what I wrote regarding the first point and second point are wrong. I apologize for that. Please ignore them. 
Somehow, the mysterious assumption, the existence of (I-gamma F^{#}) helps and produces a nice result. 

limitations_and_societal_impact: No
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper consider off-policy evaluation using linear function approximation
under unrealizability setting.
Under such more relaxed assumption, they provide characterization of the linear direct method(DM)
as an error governed by two approximation residual $\mathcal{R}_B$ and $\mathcal{R}_X$,
$$
    \hat{J}(\pi) - J(\pi) = \mathbb{E}[\mathcal{R}_B(s,a)\mathcal{R}_X(s,a)] + O(1/\sqrt{n}),
$$
with $\mathcal{R}_B$ corresponding to Bellman residual and 
$\mathcal{R}_X$ corresponding to residual of marginal density ratio.
Leveraing this result, they establish a nonparametric tile-coding estimators 
to solve the unrealizability though with a slower convergence.
main_review: **Novelty:**
I have the major concern about the novelty of this paper,
where there is a large class of OPE literature about doubly robust estimator, e.g. [1-2], 
the paper fails to discuss and compare with.
Especially in [2] Theorem 3.1, the bias term of double robustness estimator can be characterized
as the inner product of two residual terms of Bellman residual and residual of marginal density ratio.
Although the two estimators compared is not exactly the same (doubly robust vs DM), 
the bias error decomposition looks quite similar.

I encourage the author to investigate deeper into those papers and find out the relationship.
It is possible that the similar error decomposition can imply linear DM is 
already a doubly robust estimator in some sense, which may be a very interesting finding.

**Quality, Clarity and Significance:**
I am satisfied with the quality and the clarity of the paper.
The theoretical significance is still lacking before comparison with doubly robust estimator.

Reference:

[1] Kallus, Nathan, and Masatoshi Uehara. "Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes." 

[2] Tang, Z., Feng, Y., Li, L., Zhou, D., Liu, Q. (2019). Doubly robust bias reduction in infinite horizon off-policy estimation.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This is a theoretical paper which addresses the RL off-policy evaluation with linear function approximation. It proves convergence results of linear function approximations and shows that the direct method (model the dynamics) is asymptotically equivalent to FQE (modeling the value function) and analyzes its convergence properties. Additionally, it proves consistency results for such methods under tile-coding, allowing for consistency (using non-parametric estimation) even under unrealizability of the linear approximators.
main_review: The paper presents interesting results and is well written. I did not check all the proofs in the paper (it is more theoretically oriented than my expertise), and therefore my confidence in the review is limited. It has two major drawbacks - The first and most obvious one is its reliance on linearity. It is uncommon for linear models to properly model MDPs of interest, and therefore I am not sure how impactful the results will be. The authors do provide consistency results using feature tiling which allows for consistency using tile-coding, and therefore the results could in essence be applied to highly nonlinear MDPs, but I expect such case to be limited to low dimensional MDPs in the same way non-parametric always suffer in high dimensions. Second, the set of assumptions the authors use, while not very strong, is very uncommon compared to the majority of OPE work, further limiting the potential of these results to have a large impact on the field.

The central result (theorem 6) is very reminiscent of the properties of the (very commonly used in OPE) doubly robust estimator. The DR is unbiased if either the behavior policy is know (analogous to R_X being realizable), or the control variate is accurate (analogous to R_B being realizable). I am not sure how useful the analogy is in this case, but since it is a very obvious analogy and DR is such a common estimator in OPE it might be worth exploring.
limitations_and_societal_impact: The authors discuss the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper characterizes the offline policy evaluation (OPE) error with linear function approximation in the discounted reward setting. With certain assumptions, this paper proves that the error of Linear Direct OPE algorithm (which is equivalent to the limit of Fitted Q-Evaluation algorithm) converges to the expectation of the product of two residuals. As a corollary, when either the function class is closed or the density ratio is realizable, the asymptotic error is zero. In addition, in the same setting the paper upper bounds the OPE error for tile-coding estimator.


main_review: This paper proves a novel asymptotic characterization of the OPE error with non-realizable linear function approximation. Compared with previous results, this paper exactly computes the dominant term of the OPE error, instead of providing an upper bound.

On the plus side, this paper is well written. Proofs are technically sound and solid. The results imply that the direct OPE (as well as the Fitted Q-Evaluation) algorithm automatically satisfies doubly-robust-type error bound: when either the Bellman residual is small or the density ratio can be well approximated, the estimation error is small. So this paper could contribute to the understanding of linear OPE tasks.

The main weakness of this paper is that the results are asymptotic (i.e., only holds when the number of samples approaches infinite). It is unclear how realistic are the phenomena described in this paper. For example, the convergence rate in Theorem 6 depends polynomially on the term 1/c_\mu, which is the minimum data density over all state-action pairs. For MDPs with large state/action space, the term could be much larger than the number of samples. In other words, it’s unclear whether the dominating term is still characterized by Eq. (6) in real-world OPE tasks.

In addition, this paper doesn’t directly tackle the difficulty of linear OPE tasks. On the one hand, the assumptions such as 1/c_\mu-dependence or upper bound of \|F^#_\gamma\|_2 exclude some natural hard instances. Are these assumptions an artifact of the analysis, or necessary for the result? On the other hand, the sample complexity of tile-coding estimators is exponential in the dimension d, which is not very realistic.

Minor issues which may cause unnecessary confusion:
-	The notation f* in Definition 8 and 9 is used to denote different functions.
-	Does Definition 3 depend on the policy \pi being evaluated (because the term (P\phi)(s,a) depends on \pi)? 

limitations_and_societal_impact: The authors adequately addressed limitations and potential negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors analyze the off-policy evaluation error of a direct estimator with linear function approximation under unrealizability. In Theorem 6, they derive the closed form of the asymptotic bias term as the number of samples approaching \infty. Besides, in section 3.2, they study another method where the feature mappings can be selected adaptively and provide the convergence analysis for their estimation to ground-truth J(\pi).
main_review: This paper is well-written, and the notation and definitions are clear. Their theoretical results are solid and interesting. But I’m concerned about the significance of the contribution of this paper.

(1) I’m feeling the theoretical results in Theorem 6 may not be novel enough. The bias decomposition in Theorem 6 is similar to the Eq (12) in [1], in which the authors proposed a “doubly robust” estimator and decomposed the bias to the residual of density ratio estimation error and value estimation error.

It seems that if we use linear functions to approximate density ratio and value function (e.g. see Example 2 and Example 7 in [2]) with the same data and plug them into the “doubly-robust estimator” in [1], it directly recovers the \hat J(\pi) estimator in Algorithm 1 in this paper. As a result, a bias term similar to Theorem 6 can be obtained by directly adapting from results in [1] to the linear setting as a special case with a different definition of “residual” (R_\chi & R_B in this paper v.s. \epsilon_{\hat w} & \epsilon_{\hat V} in [1]).

I wonder if the authors can discuss some connections and essential differences comparing with the results in [1], which is missing in the paper.

(2) Although the analysis in this paper fills some blanks in OPE research, I'm feeling the results in this paper is not substantial enough. It would be a more solid paper to me if there are more discussions about what we can do with the bias analysis, or say, how can we use that bias analysis (e.g. given two feature sets, can we identify the one with a smaller bias), or maybe more bias analysis beyond the linear setting with unrealizability.

Reference:

[1] Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation, Ziyang Tang, Yihao Feng, Lihong Li, Dengyong Zhou, and Qiang Liu

[2] Minimax Weight and Q-Function Learning for Off-Policy Evaluation, Masatoshi Uehara, Jiawei Huang, and Nan Jiang
limitations_and_societal_impact: I think the authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: The paper characterizes the asymptotic bias of off-policy evaluation using linear function approximation when realizability assumptions do not hold, with convergence rate analysis. The major concerns of the reviewers focused on the paper's lack of discussions of closely related results in MIS (e.g., Uehara et al, Tang et al); in fact, some of the high-level claims in the paper (e.g., first to discover connection between direct methods and density-ratio learning, first to provide "doubly robust" guarantee to LSTDQ) are already known in the prior works. 

After extensive post-rebuttal discussions, the AC decides that this is borderline paper that can go either way, but their personal recommendation is acceptance: the paper's exact characterization of the bias in LSTDQ is a significant result. As mentioned above, prior works have noticed the curious nature of LSTDQ and how it connects to MIS methods, but an exact characterization of its bias is missing, and different approaches to bounding the bias (e.g., under either realizability of value function or density ratio) yield different results, lacking unification. 

This paper solves this problem by providing the *exact* characterization of the bias, which takes the form of the product of realizability errors of value function and density ratio, respectively. For reference, the most comparable results that is previously known takes the form of minimum over these errors; see post-rebuttal discussions (also Remark 2 in Appendix A of Uehara et al, which does not require realizability). While multiplicative errors are known for doubly robust estimators (e.g., Tang et al, Kallus and Uehara), these are meta-estimators and require approximate value function and density ratio as inputs, so the results are somewhat orthogonal to the current paper. Furthermore, the paper complements the bias analysis by a convergence rate analysis, which takes care of non i.i.d. data and finite-sample effects. With all these, the AC feels that the paper will be a valuable reference for anyone who wants to investigate the statistical behavior of linear OPE estimators, and therefore recommends acceptance. 

Despite the AC's recommendation, the authors are noted that missing significant related works is a major issue, and a rejection will also be reasonable given that the revision needed is quite substantial that may warrant another round of reviewing. Regardless of the final decision, the authors are urged to fix overclaiming and draw connections to related works. Just to give a few pointers: 

- Abstract: "OPE ... has been advanced under the (approximate) realizability assumptions. However, such assumptions undermine the applicability of the results since the given environmental models may be completely wrong." This sentence suggests a qualitative difference from existing works, whereas the actual difference is more quantitative.

- Line 60: " new interpretation of the linear DMs as marginal density ratio estimator" Already known in the literature.

- A comparison to previous upper bounds on the bias should be provided.

Finally, some additional detailed comments from the AC:

1. The authors might want to reconsider the title, which is not very informative in its current form given that the central result is the exact characterization of bias and the connection between DM (LSTDQ) and MIS is somewhat known. Also, linear function approximation is a crucial component of the setup, which is not reflected in the title.

2. The authors mentioned the lower bound of Wang et al several times during discussions, but may have some slight misunderstanding of their results. It was mentioned that they assumed bounded $1/C_{\mu}$, which is not true. Wang et al's data assumption is about the minimal eigenvalue of $\Sigma$, which is a much weaker one; the authors should be careful when discussing related issues in the paper. On a somewhat related note, the paper's derivation requires invertible $\Sigma$, but that may not be necessary. In the usual LSTD analyses, $\Sigma$ and $(I-\gamma F^{\\#})$ is often multiplied together as a single matrix (usually in the form of $E[\phi(s)\phi(s) - \gamma \phi(s) \phi(s')]$, and the requirement of invertibility of $\Sigma$ may be an artifact of extracting out $\Sigma$. 

3. Def 9 for "Bellman residual" is not as interpretable as Def 8. For Def 8, one can easily see that the residual is 0 if the linear class realizes the true density ratio function. For Def 9, it is unclear/unintuitive why the residual is 0 when the linear class realizes the true value function (though I think $Q^{\\#}=Q^\pi$ when $Q^\pi$ is realizable and therefore the residual is $0$ in this case); the reference to $Q^{\\#}$ in the definition is somewhat undesirable since the quantity is a complicated expression in the estimator which does not make direct sense in the MDP. Also, if $Q^{\\#}$ is allowed in the expression, bias can be trivially written as $E_{p_0^\pi}[Q^{\\#} - Q^\pi]$ which is vacuous. Is it possible to rewrite it as an expression that looks like more standard forms of Bellman errors, e.g., replacing $B Q^{\\#} - q$ with $B q - q$?

Uehara et al. Minimax Weight and Q-Function Learning for Off-Policy Evaluation.

Kallus and Uehara. Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes.

Tang et al. Doubly robust bias reduction in infinite horizon off-policy estimation.

Wang et al. What are the Statistical Limits of Offline RL with Linear Function Approximation?
Decision: Accept (Poster)