Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the problem of off-policy evaluation and shows that it is possible to interpolate between the two common families of algorithms: importance sampling of policies which is unbiased but high variance, and correcting state distributions, which is low variance but could be very biased since the distributions need to be estimated. The resulting algorithm is tested empirically on small tabular tasks and it is shown that there are indeed intermediate values in the spectrum that achieve better MSE than either of the extremes.
main_review: This paper was a pleasure to read. Despite not having strong experiments, the key idea is very cool and advances off-policy research in a clear way, and the paper is written very well. I only have a couple of high-level comments / questions, and some minor proofreading remarks.

1) Figure 1 intuition is important but gets lost afterwards. It would be great to show that the error is lowest when split at the hallway, but for that z would need to depend on the state. Can the authors provide an intuition about this?
2) Larger experiments are promised (optimistically!) in the appendix but not found. I think smaller experiments are fine, but it would be nice to have more insight about the trends. For example it seems that when the policies are further apart n=1 is optimal (single importance sampling ratio). Do the authors have intuition of what this would look like in practice?

Minor comments
* Lines 29-30: something funky with the phrasing
* 68: d^pi_t is usually phrased as probability which might be clearer. Also I guess it should be s_t, a_t
* Big equation on page 2: Something off with the indices here — shouldn't the sum start at t=0 (since numbering rewards starts from 0 in tau)? 
* Also, shouldn’t d_0 be a part of the definition of d^pi for probability of (s,a) at the initial time step?
* 115: third I think? Marking the relevant equality would be clearer
* Figure 3(b): why does variance decrease for the intermediate amounts of trajectories?
* 159: Maybe named paragraph here?
* 160: CWPDIS mentioned for the first time
* 162: amount amount
* Figure 4: it would be clearer to denote lines by policy distance instead, since the targets are different for the two tasks
* 181-182: No larger continuous state spaces in the appendix :(
* 198: what is H here?
* 200: has has
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes an estimator for off-policy evaluation (OPE) that unifies trajectory-based per-decision importance sampling with stationary distribution importance sampling using an n-step approach analogous to multistep temporal-difference learning. The paper presents n-step estimators for both ordinary importance sampling and weighted importance sampling, and investigates their properties on two tabular OPE environments.
main_review: I recommend publishing the paper at NeurIPS 2021 despite minor concerns about scope.

**Quality:**

The proposed estimator is derived in a principled fashion, and the experiments are aimed at understanding properties of the proposed estimator and seem well-done to me.
The main thing that disappointed me about the paper was that it restricted itself to n-step methods instead of also doing the obvious next step and incorporating exponential weighting to get an estimator analogous to TD($\lambda$).
A secondary concern is that there is no guidance for how to set the "switching time" parameter for an environment a priori.
In general I'm not a fan of introducing parameters, but the paper appears to do it for the purposes of better understanding two existing algorithms instead of doing it to improve performance, so I'm ok with it.
One could also argue that another experiment in a larger domain is needed, but I was satisfied with the existing experiments.

**Clarity:**

The paper is written clearly and is very easy to understand. There are some minor grammatical errors throughout (some of which I've pointed out below). The paper doesn't try to obfuscate or dress up what it's doing, which is frankly a breath of fresh air.

**Significance:**

The proposed method provides a useful unification of two existing algorithms (useful because intermediate values can often perform better than either extreme), which could easily be built upon. Interestingly, the n-step approach forms a bridge to multi-step TD learning, which provides another perspective on the problem.

**Originality:**

The paper takes a well-known technique (n-step estimates) and applies it to a different problem. To the best of my knowledge the proposed method is novel.

**Misc. comments, questions, and suggestions for improvement:**

Line 29: There's an extra "can" in this sentence.

Line 31: "If" should be lowercase.

Line 42: "the first part" is repeated.

Line 43: "using" should be uppercase.

Line 69: It was a little confusing to define $c=\sum_{t=0}^{L} \gamma^t$ instead of just writing it out.

Line 146: "to" is repeated.

Line 151: should be "allow us to control the variance's dependency"

Line 162: "amount" is repeated.

Figure 3: Thank you for plotting confidence intervals! I can easily see whether differences are statistically significant by checking if the shaded regions overlap.

Line 160: The acronym CWPDIS is never actually defined anywhere that I could find. I'm guessing it's Conditional? Weighted Per-Decision Importance Sampling?
limitations_and_societal_impact: I was satisfied with the paper's discussion of limitations and societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper introduces a novel n-step method which interpolates between PDIS ($n=H$) and density estimation ($n=0$) methods (the DICE family). The paper derives the relationship between density ratio corrections and likelihood ratio corrections, leading to the development of the proposed algorithm. The paper empirically investigates multiple ablation studies of the bias/variance tradeoff of the proposed algroithm.
main_review: I recommend to accept this paper. [S1] The connection between density ratio and likelihood ratio corrections is insightful. [S2] The proposed algorithm is simple and provides an avenue to avoid a common criticism of DICE methods: the difficulty in estimating the density ratio and resultant bias. [S3] The empirical evaluation is motivating. Finally, [S4] the paper is quite well-written and very clear.

I have only very minor reservations: [W1] the empirical investigation exclusively uses weighted-PDIS and weighted-SIS, so interpolates between two biased methods. [W2] By using small toy domains where SIS can perfectly estimate the density ratio, many  of the stated difficulties of SIS are not investigated, leaving open-ended the contribution of this paper in harder problem settings.

---

**[W1]**: Weighted estimators

I would be curious to see a more clear demonstration of the bias-variance tradeoff by additionally investigating the non-weighted versions of these estimators---at the very least a non-weighted version of PDIS. The bias on the graph MDP is sufficiently small for all values of the estimator, that I wonder if the empirical estimate of bias is more noise than signal (Figure 3a), but I would have expected to see the bias decay more strongly as n -> L. In the case of Figure 4a, I am surprised that the PDIS estimate _increases_ bias over the weighted-SIS estimate leaving the bias-variance tradeoff claims poorly supported.

---

**[W2]**: Small domains

I generally don't mind small domains. I believe they were harmful in this case where the true density ratio is representable within the function approximation class. Using even the toy Mountain Car domain with a reduced function approximator would provide some additional value by demonstrating the impact of the proposed n-step estimator when SIS has much worse bias. Currently the best value of $n$ is often very close to 0 (near SIS), but in larger/more realistic settings I wonder if this would continue to be the case.

---
Minor question: would it be possible to derive an expression for minimizing the MSE w.r.t. parameter $n$ analytically? I wonder if this could be estimated easily from the data. At the very least, I would be curious to see how effectively an n-fold cross-validation approach selects the optimal value of $n$.

---

**Edit after discussion period:**

After concerns about the correctness of the proof have been resolved, I continue to feel this paper is a solid contribution to the field. My previous concerns were only minor in strength and have been well-addressed with the author response and I do not feel that I would need to re-review after the new experiments are added to the paper. I recognize the discussion period was rather quiet for this paper, but frankly, I believe this paper left little need for added discussion---to me it is a clear accept.
limitations_and_societal_impact: Limitations and societal impact are sufficiently addressed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The scope of the paper is within off-policy evaluation (OPE) in reinforcement learning (RL). The paper aims to develop a spectrum of OPE methods which interpolate between trajectory based importance sampling (IS) and stationary state distribution IS. 
main_review: To briefly summarize my review and justify my score, I believe the paper is wrong. The method introduced relies on Lemma 1 which as far as I can tell is not correct. This perhaps leads to some inconsistent results which the authors do not address in the experimental section. Having said that, I think the idea of generating a family of estimators interpolating between IS and SIS is a good one, and I will therefore do my best to provide feedback which will be useful in the future if the authors can find a mathematically consistent way to generate such estimators.

The estimators presented in the paper rely on the derivation of equation (1), which uses Lemma 1. I believe the Lemma is wrong. An easy way to see that the Lemma is probably wrong is that the LHS is independent of \gamma and L and only depends on the MDP dynamics and policies, while the density ratios on the RHS do depend on \gamma. As a quick counter example to demonstrate it, think of a deterministic two state system, which always starts at s0, with two actions (a0 and a1). The agent always starts at s0, from which a0 leaves the agent in s0 and a1 transitions to the absorbing state s1. Assume a state independent evaluation/behavior policy which has probability \pi_{e/b}(a0) to take action a0. To compute the LHS of lemma 1 for S_z = s0 (ignoring actions for now), we note that if S_z = s0, it means a0 was always taken, and therefore E[\rho_{1:z} | S_z = s0] = (\pi_{e}(a0) / \pi_{b}(a0))^z. On the other hand the RHS can be shown to be equal \frac{\sum_t^L \gamma^t \pi_{e}(a0)}{\sum_t^L \gamma^t \pi_{e}(a1)}. Note that these expression may differ slightly depending on how to interpret an inconsistency the authors have in the notation and definition which I will detail later. These quantities are obviously different. Looking at the actual proof in the appendix, one place where it is wrong is in their use of the term P_{e/b}(S_z, A_z) which is not well defined as the probability of the MDP being in (S_z, A_z) is a function of time which is absent in the derivation. In their proof and justification of a later part of the derivation the authors invoke explicitly incorporating the time into the state which might help here. If you do that you can maybe make the claim that \gamma = 1, and get rid of that dependency, but as the counter example shows you will still not get the Lemma 1 equivalence. More importantly, the inclusion of that assumption (time explicit in the state) is misleading. While it is possible to do it, it is a very uncommon practice in RL (usually for the episodic case you just have the episode end at a given time but have time dependent value function/policies), and if the authors make that very unusual and restrictive assumption it should not be hidden at the end of the appendix.

Based on this error alone, I do not believe the paper is publishable at this point. Additionally, while I do not expect the empirical results to be valid given the error, I think there are several inconsistencies in the results which can suggest that something is wrong:
Fig 3 and 4 top middle : if n=0 corresponds to SIS and n=L to PDIS the bias should be monotonically decreasing with n. Instead it is not monotonic in Fig 3 and sometimes monotonically increasing in fig 4.
Fig 3 and 4 bottom right : Why for some parameter (# of trajectories or epsilon) the variance increases with n and for some decreases, where the logic of interpolation between SIS to PDIS would predict monotonic increase for all.

Some other comments:
- The definition of J(\pi) and d^\pi is inconsistent between the first paragraph of the "notation" section in the background and the "density based IS" section (indexing of t).
- Maybe I missed it, but CWPDIS is never discussed before it is given before eq. 3, and is not cited. While it would be familiar to people who know the OPE literature well, it is not used commonly enough to appear without citation. On that note, it is a little ironic that eq. 3 appears as an analogue of CWPDIS without proof of consistency, since CWPDIS was originally introduced by Pillip Thomas of an example of how naively meshing two estimators (in the case presented in his thesis meshing PDIS and WIS into what was then known as WPDIS) can easily result in inconsistent estimators.
- In any future work, I would strongly encourage the authors to include a continuous environment in their experiments. One of the main failing mechanisms of SIS compared to IS is that any type of non-markovianity (or partial observability) would lead to inconsistent estimators. Meanwhile such partial observability doesn't effect IS as long as the policies are Markovian. Thus, it would be interesting to see how interpolation between SIS and IS can work in continuous domains where a form of partial observability is introduced through function approximation.

Last, I would like to point out that the paper has too many typos for what I feel is acceptable in a submission.
limitations_and_societal_impact: At the moment, OPE papers of this sort are mostly theoretical and therefore have limited societal impact. The long term goal of OPE work is to allow deployment of RL policies in risk sensitive domains, which would have negative impact if not done properly. The authors acknowledge the importance of OPE in that regard and thus satisfy the criterion for discussing the potential negative impact of their work.
review_title: null

Meta-review: The paper considers the problem of off-policy evaluation and shows that it is possible to interpolate between the importance sampling estimator, which is unbiased but high variance, and correcting state distributions, which is low variance but could be very biased since the distributions need to be estimated. The authors showed that the optimal estimator with lowest MSE is indeed taking an intermediate values in the spectrum to mix these two estimators. 

The proposed estimator is derived in a principled fashion, the results are insightful, and the paper is very well written. Generally this paper's contribution are non-trivial yet interesting, and it can definitely be a valuable addition in the vast literature of off-policy evaluation in RL. Some potential drawback of this paper includes simplistic experiments that are aimed only for proof-of-concept, and the restriction to to n-step estimators.  During the discussion phase, the reviewer also recommends doing another round of improvement before publications to study the confounding effect of these two estimators. Please try to do so to improve the (already good) quality of this work. 

In general I believe the merits of this work surpass the improvements required. So I also recommend acceptance.

Decision: Accept (Poster)