Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The variance of ETD can grow up exponentially so this paper proposes to use a periodically restarted variant (namely, the PER-ETD) as an improvement.  The authors show that the proposed method has a polynomial sample complexity, and provide some experimental validation. 
main_review: Pros:
1. In my opinion, this paper does answer an important question in off-policy value evaluation. The contribution is solid, and the proposed algorithm intuitively makes sense.
2. The analysis in this paper is quite novel. The trade-off between variance and bias is very interesting.
3. Theorem 1 is interesting in capturing how the sample complexity depends on the mismatch level.
4. The advantage of this work over the concurrent paper (Zhang2021) is clear.



Cons:
1. It seems that the algorithm is not using all the data in an efficient manner. It seems to me that the update for the theta parameter mostly depends on the the last data point within the last period. Is that right? Most data points in the period are only used to update F? Is there a better way to make full use of the data? Maybe some variant similar to least square type methods?
2. This paper considers a projected version of ETD.  Is it possible to remove the projection operator? In addition, there are a few papers on how to remove projection for the analysis of stochastic approximation under Markovian noise which should be mentioned in this paper.

   R. Srikant and L. Ying,  Finite-time error bounds for linear stochastic approximation and TD learning, COLT 2018. 
    
    B. Hu and U. Syed, Characterizing the exact behaviors of temporal difference learning algorithms using Markov jump linear system theory, NeurIPS 2019.
    
   M. Kaledin, E. Moulines, A. Naumov, V. Tadic, H. Wai. Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise, COLT 2020. 
 
   C. Z. Chen, S. Zhang, T. T. Doan, S. T. Maguluri, and J.-P. Clarke, Performance of Q-Learning with Linear Function Approximation: Stability and Finite-Time Analysis.



summary_of_the_review: Overall I am still positive on this paper. The analysis is very interesting and insightful in characterizing the trade-off between variance and bias. Currently my score is 6 but I am willing to increase my score if all my comments are addressed. 


---------------------------------------------------
I think the authors' response to my comments are very reasonable. I have increased my score to 8.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose an improved variant of emphatic temporal difference (ETD) aimed at addressing issues of high variance when faced with a large mismatch between behavior and target policies. The main improvement of PER-ETD, the proposed algorithm, comes from periodically clearing the follow-on trace at logarthmically increasing periods. The authors present a finite-time analysis for both the PER-ETD(0) and PER-ETD($\lambda$) case showing how bias and variance depends on the time between clearing the trace. This is used to derive a schedule that effectively minimizes the variance and bias to achieve polynomial sample complexity. The authors conclude by illustrating these improved properties in Baird's counter-example MDP. The results confirm the effect on bias and variance of the period parameter and highlight's that $\lambda=1$ no longer results in the closest fixed-point to the optimal solution. 
main_review: The paper is well written and easy to follow. The analysis make the improvements of PER-ETD over ETD evident and convincing, and the empirical results, while limited, illustrate well the theoretical contributions when dealing with a significant mismatch.

I think the experiments should have contained some results in settings that aren't constructed to diverge. Specifically, I would have liked to see how PER-ETD performs compared to ETD and TD a bit more broadly. I think small illustrative domains are sufficient for this kind of work, but having more than a single domain/setting to either show that we see the same predicted effects in different settings or to give a more complete picture would have improved this work. For instance, an experiment which varies mismatch could have helped illustrate how mismatch affects PER-ETD, ETD, and TD, and possibly help visualize the two-phase behavior discussed in the paper.

That being said, I find the overall contributions sufficient for acceptance. The work is well motivated, novel, and provides a notable improvement over ETD. A more complete comparison would have been nice, but, as it stands, this is likely to be of interest to parts of RL community and is worth sharing.

Questions:
================

- Is setting the same step size really "fair"? I can understand keeping the same step-size for different $b$ for the purpose of illustrating the theoretical contributions, but why is it fair to use a fixed step size across different algorithms?
- What does the shaded area represent?
summary_of_the_review: The paper is well written and easy to follow. The analysis make the improvements of PER-ETD over ETD evident and convincing, and the empirical results, while limited, illustrate well the theoretical contributions when dealing with a significant mismatch.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposed a new off-policy evaluation successor method of ETD. The method has reduced variance by leveraging a simple and effective way that restarting follow-on trace iteration every couple of updates. The authors also provide theoretical analysis that shows that the proposed method improves the converge rate from an exponential one to a polynomial one with the guarantee of the same fixed converging points. The empirical results show that the proposed method could converge in the case that neither TD nor ETD does. 
main_review: Strengths:
- The paper is well written and clear to follow.
- Strong theoretical analysis
- The proposed tricks are simple and elegant.

Some suggestion:
- Adding an experiment to discuss the choice of behavior policy and target policy would be appreciated.
- Figure 1&2 is hard to read, perhaps you could plot the line with variance bar

summary_of_the_review: Overall, I think the paper is solid and sound, it is marginally above the acceptance threshold. However, I would consider changing the scores if my concerns are addressed.

------------
After Rebuttal:
After reading the author's rebuttal and the comments of other reviewers, I decided to increase the score to 8. I appreciate the author's thorough and conscientious rebuttal to address all my concerns.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a technique of reducing the variance of emphatic algorithms by resetting the trace periodically, and that increasing the period logarithmicaly can result in an optimal way of trading off bias and variance of the resulting learned value function. The authors prove such a method obtains the optimal tradeoff and results in convergence in settings where predecessor variants fails (TD and ETD). The paper proves these claims theoretically, and show an illustration on the Baird domain for empirical support.
main_review: The paper addresses a fundamental problem in reinforcement learning, and proposes a simple solution to this problem, with theoretical guarantees. The paper discusses the issues with off-policy evaluation, specifically the problem of distribution correction, for which emphatic algorithms have been introduced. It proposes that previous methods like GTD deal with this poorly, due to this distribution mismatch, though it is not clear why that is the case, or is it specified. The paper would benefit from a clear explanation on what objective function these class of methods optimize and how that differs, and how one is preferable to the other, since both these class of methods have been algorithms that can deal with off-policy learning. Page 3 -> "cardinality of the state", maybe you mean "states" or "state space"? The vector of values for all the states has the same notation as the value function, and capitalized like random variables, which is a bit confusing. $B_\phi$ is not introduced. Page 5, "helps to stabilize" -> "helps stabilize". Lemma 1 (geometric ergodicity) -- can you explain what this lemma says in words, it is not clear why this will be useful or you need it in your analysis. There is no row space above "Proposition 1". There are a lot of constants introduced that it's easy to lose sight of what they mean and get confused, if ever they were introduced at the beginning of the paper. One way to make the paper more clear would be to hide all these details and explain high level the steps of the analysis or proof. In proposition 1, $\zeta$ should be $\zeta^b$ everywhere? Is $\rho_max$ defined anywhere? What is $T_a$? The explanations below Theorem 1 are confusing because I'm not sure how to interpret $a$, and I don't understand where the threshold comes from. Below proposition 4., should that be "PER-ETD" instead of "ETD" ?  Above "Experiments", in the "impact of $\lambda$ on error bound, do you mean "eligibile traces" or "the eligible trace" maybe? Figure 3. what is the space in which these are plotted? The first sub-figure is also missing the y-axis. How confident are we that these methods are scalable in the general spaces we use these methods in? Is there such a way of increasing the period still applicable?
summary_of_the_review: The paper addresses a fundamental problem in RL is a simple way and proves that such a method achieves an optimal tradeoff between bias and variance in emphatic algorithms, leading to polynomial sample complexity. The claims of the paper are also illustrated in a toy domain, showing great potential. The paper could benefit from some more explanations and clarity.
review_title: null

Meta-review: This paper investigates TD-based off-policy policy evaluation. This topic is of interest as most SOTA DRL methods are built upon unsound algorithms, whereas more sound variants are difficult to use in practice and have not been widely adopted. This paper introduces a new variant of ETD that addresses the variance issue with the existing algorithm, along with theory characterizing sample efficiency. The paper includes a well done illustrative empirical study to support the theory. The reviewers all scored the paper highly. 

The AC pointed out several minor issues in the presentation that the authors should address for camera ready.  In addition the grammar and word usage is rough in some places. Please take time to improve the text.
Decision: Accept (Poster)