Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper derives finite-sample bounds for off-policy TD learning algorithms. The main idea is to propose a generalized Bellman operator and rewrite the off-policy TD learning as stochastic approximation algorithms. Then it remains to show under what kind of conditions this generalized Bellman operator is a contraction mapping. The proof technique can be used as a general tool to derive finite sample bounds for existing off-policy learning algorithms. 
main_review: The paper is well written and the problem setups are defined clearly. I really enjoy reading this paper. 

The nice thing about the generalized Bellman operator is to provide a unified framework to study the finite sample guarantees of off-policy TD learning algorithms. Also, in the derived bound we can clearly see the bias-variance trade off. Although I am not very familiar with previous theoretical analysis on these algorithms, this does look like a very nice contribution to the literature.  

There are some quantities used in the presented results, such as $c_\text{max}, \rho_\text{max}, D_{c, \text{min}}$. It might be good to give some example to show how large these quantities are so that the reader can get some intuitions when the bounds will be large or small. 
Furthermore, the paper focus on the policy evaluation problem. How do the results imply for the control setting? 
limitations_and_societal_impact: No societal issue has been found.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a generalized Bellman operator for off-policy methods and provides finite-sample bounds for the associated stochastic approximation algorithm. These bounds can be applied to several previous off-policy TD algorithms such as Retrace and Tree-Backup, which allows one to assess their tradeoffs in the form of a variance term and a contraction factor.

main_review: Overall, I enjoyed the paper and think it can improve our understanding of off-policy TD methods through a theoretical analysis of sample complexities. The writing was clear and the paper was easy to follow. I particularly appreciated the clear exposition and proof sketches. 
I would be interested in seeing the next works in this direction with extensions to function approximation.
I do have some certain clarifications questions written below and would raise my score if these are addressed.

Comments and questions:
- Interesting formulation for the generalized Bellman operator. It seems fruitful to consider those generalizations as a basis for further theoretical analysis.

- The proposed general stochastic approximation update doesn't match the original update for Tree-Backup and Retrace. In particular, there is a importance sampling ratio in the TD-error but, in the original Tree-Backup/Retrace update, there is no such ratio and the target is replaced by \sum_a' pi(a'|s') q(s', a'). This target should intuitively have lower variance than the importance-sampled one and perhaps the bounds can be refined to account for this. 
At the very least, it would be important to mention this difference between the original algorithms and the variants currently described in the paper. 

- I think the sample bounds established on the various TD methods are interesting and I appreciate that they can meaningfully discriminate between the tradeoffs of each algorithm. In particular, the decomposition into variance and contraction factor is interesting. Pushing this a bit further, can you propose new update rules that improve sample complexity by optimizing these theoretical bounds? I think the theory would be stronger if it could also be to design new algorithms in addition to understanding previous ones. 

- As a suggestion to improve clarity, for the individual sample complexities, I suggest omitting the exact iteration bound and specifiyng the step sizes every time since it follows the template of theorem 2.2. I would only include the parameter values to be substituted (c(s,a), \rho(s,a), etc.), along with the value of \omega (the contraction factor) and the sample complexity. It would be nice to additionally include the 'variance' term too. It may be easier to compare algorithms at a glance in this form.  

- An explanation of the effect of n (from n-step updates) in the theoretical bounds would be a nice inclusion. As far as I can tell, this only affects the f(.) function which plays a role in both the variance and contraction factor terms. 

- A clarification question about proposition 2.4: This proposition guarantees the existence of certain weights \mu for which the Bellman operator is a contraction mapping. Does it matter if this \mu does not correspond to the stationary distribution of any policy? For the standard analyses of on-policy TD, usually the weighting does in fact correspond to the stationary distribution of the behaviour policy.

- Are there any papers analyzing the vanilla IS algorithm and giving finite-sample bounds? I'm a bit surprised there are none since it seems closely related to standard on-policy TD.
- How do these bounds compare to the on-policy TD sample bounds?

Minor comments:
- In several parts, the variable 'a' is overloaded in both the sum and as a argument e.g. line 189 in the definition of D_c, 'a' is used in both the sum and the variable of the function. This would need to be clarified.
- Line 218: The matrix 'A' is referenced but hasn't been introduced up to this point. 
- Line 128: Instead of referring to c(.,.) and rho(.,.) both as generalized importance sampling ratios, perhaps the it would be clearer to call c(.,.) something else, such as a 'trace' (following the terminology in the Retrace paper), since it actually consists of a product of the one-step importance sampling ratios. 

limitations_and_societal_impact: While the limitations are discussed briefly, it would be nice to expand on that: which parts are less satisfying or that could be improved in the present work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a unified framework for understanding several existing tabular off-policy TD algorithms for policy evaluation. Central to this new framework is a generalized Bellman equation and its contraction. The unified framework provides new insights about the bias-variance trade-off of those existing algorithms, as well as finite sample analysis.
main_review: Overall I think this is a solid work and the paper is well written, easy to follow. I checked the proof of Proposition 2.4 in detail, which I believe is the most important ingredient to all the theoretical results in the paper. It looks correct to me. With Proposition 2.4, I do expect all other results to hold.

I have only a few points.
1. In both Line 223 and Line 402, the authors mention the possible extension to linear function approximation. It looks not straightforward to me. With FA, we typically need a projection operator w.r.t. to the norm induced by the sampling distribution (or some other distribution we can sample from). However the generalized Bellman operator is contractive w.r.t. the ergodic distribution of M''. So one possible approach is to design a method to sample according to M''. By the construction of M'', this looks nontrivial. I understand this FA thing is just a possible future, but I might be nice if the authors could discuss this more to give readers more insights.
2. In general I like works unifying existing methods. With this unified framework, is it possible to come up with some new algorithms to optimize the bias variance tradeoff revealed by the analysis? I think by doing so the papers can have more algorithmic contribution.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The reviewers reached a consensus that this paper makes solid contributions. I recommend acceptance. The authors should still carefully revise their paper on the clarity issues raised by the reviewers and explain more about the intuitions for better readablity. 
Decision: Accept (Poster)