Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper proposes an algorithm for estimating any parameter of the distribution of returns in an off-policy manner, and derives confidence intervals for the quantities of interest. The paper also shows how the proposed algorithm can be extended to deal with many issues commonly faced when applying RL to real world problems (nonstationarity, non-markovian observations, etc.).
main_review: I strongly recommend accepting the paper for publication.

**Quality:**

Overall the quality of the paper is very high. The methods are derived in a principled fashion, and important properties (guaranteed coverage etc.) are proved. The experiments also seem to be well done and are helpful for illustrating properties of the proposed method.

**Significance:**

The proposed algorithm is very likely to be significant for both practitioners, as well as researchers to build upon. The generality and effectiveness of the proposed algorithm seems extremely useful, as are the confidence bounds that are important for any real-world application of off-policy learning.

**Clarity:**

The paper is written clearly, although somewhat difficult to understand due to the complicated concepts involved and the large amount of ground covered within the paper. The paper is quite dense with notation, but the authors have helpfully included a notation table in the appendices.

**Originality:**

The proposed algorithm is novel to the best of my knowledge.

**Miscellaneous comments, questions, and suggestions to improve the paper:**

Citing authors by last name and date instead of with an arbitrary number makes it possible for the reader to recognize what paper is being referred to if they're already familiar with it. It's also nice to give explicit credit to authors whose work is being built upon.

Line 76: Why use discounting when there's a horizon length $T$? Is it just for the sake of generality?

Line 84: It would be nice to comment on assumptions, explaining why they were made, any ramifications/limitations due to them, whether they are common, restrictive, etc.

Line 273: What is the utility of confidence intervals that don't hold with the specified probability? Are they even confidence intervals in that case?

It might be better to plot confidence intervals rather than standard error. The reason I write this is that non-overlapping confidence intervals imply statistical significance, whereas non-overlapping standard error does not. This doesn't seem to matter as much for this paper though, as the experiments focused more on investigating properties of the proposed algorithm rather than comparing it against competitors (of which there seem to be few).
limitations_and_societal_impact: The paper does a thorough and honest job of addressing limitations and potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces UnO, a framework for estimating confidence bounds for many parameters of the reward in an off-policy setting and with finite state-action spaces. In this work, first an estimator for the CDF of the return is provided, which makes use of an importance sampling correction. From this estimator, it is easy to derive estimators for many useful parameters. Although these estimators are in general biased, it is possible to derive high confidence bounds for any of these parameters.
main_review: 

The paper is very well written and easy to follow. The authors provided a very extensive literature review on off-policy parameter estimation methods. 

One thing that is missing in the paper is an analysis of which assumptions are needed in order to apply a concentration inequality for such parameters. Since the proposed estimators rely on importance sampling, a lot of concentration inequalities are not suitable. For instance, standard high confidence bounds require some moments of the importance weights to be bounded, which reflects on a condition on the Renyi divergence between the target and behavioral policies[1]. It is not clear to me how these conditions will change when computing a bound for a general nonlinear function of F. In general, these concentration inequalities might be impossible to apply without further analysis.

I am happy to increase my score if the authors will clarify in the paper the issue above.

[1]Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, pp. 5442–5454, 2018.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes UnO, which is an off-policy evaluation method that estimates any distributional parameter (mean, variance, etc.) simultaneously by estimating the entire distribution of returns and it provides high-confidence bounds for these parameters. Moreover, UnO can be used in settings with partial-observability, non-Markovianity, non-stationarity, and distribution shifts.
main_review: The paper is very easy to follow despite the fact that it presents a lot of ideas, I particularly liked the visualization in Figure 3. Although there is a lot of content in the paper, I think everything was explored with sufficient depth. Only questions I had about the technical parts were about how to address cases with unknown $\beta$'s or unknown $\epsilon$'s and these limitations are discussed in Appendix B.2. Maybe, more of Appendix B.2 can be incorporated into the main paper in the final version using the additional page.

As far as I understood, the main advantage of UnO is to obtain estimates for a variety of useful parameters (with high-confidence bounds that all hold simultaneously) without relying on individual methods to estimate each parameter separately. Then, for UnO to be a feasible alternative to such individual methods, it is crucial for it to be at least competitive with respect to state-of-the-art solutions. However, experiments are lacking in terms of comparisons with the existing literature. Only comparison that is made is with respect to [92] and only in terms of estimating mean and variance. I would like to see more thorough comparisons with the existing methods in terms of all parameters considered in Figure 4.

Again as far as I understood, the reason why comparisons are lacking is that there is no method that can estimate other parameters in confounded and non-Markovian environments. I am not too familiar with the literature on off-policy evaluation but if that is the case, then it should be highlighted in the introduction that UnO is the first method to estimate these parameters in such environments. Even then, I would still like to see comparisons that evaluate whether UnO is in fact able to learn better estimates in confounded and non-Markovian environments (compared with methods that ignore confoundedness and non-Markovianity).
limitations_and_societal_impact: Authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Follow-up:
I check the paper again and now I am persuaded that the proof can be extended to the reward with continuous distribution. There seems no fundamental technical barrier to me. So I deem this issue as resolved and add 1 point.
However, my concern regarding the significance of the paper remains unchanged. The estimator proposed in the paper is based on the importance ratio and estimated CDF which is not novel. I also do NOT think the universality of such an estimator is a big contribution. (It is quite obvious that universality can follow from such estimators.)
Many significant previous works on OPE have been focused on proposing estimators with important properties, such as doubly robustness (e.g. https://arxiv.org/abs/1511.03722), free of curse of horizon (e.g. https://arxiv.org/pdf/1810.12429.pdf), etc. So there are many other properties that is more meaningful and applicable than a mere universality. An estimator that is only universal but does not come with any other desired and important properties is not an interesting estimator and will be of limited use in practice.

Therefore, I think the universality claimed by this paper is not interesting and significant enough. I feel this paper's significance is a little overstated. 

============================
This paper studied the OPE problem for sequential decision-making and proposed an estimator that estimates and bounds the entire distribution of returns. The method is model-free and can obtain high confidence bounds for the parameters of the distribution. The method works under different settings of MDP: fully observable MDP vs POMDP; Markovian vs non-Markovian.

main_review: Originality: This paper is original. It is the first to study the estimation of a various of parameters of the reward distribution as far as I can tell. 

Quality: The quality is OK. Theoretical results have clear proof and empirical results are well-explained. 

Clarity: The writing is very clear and easy for the readers to understand. 

Significance: The significance of this paper is affected by several factors. First, this paper assumes the return distribution is discrete. This assumption is too strong and restrictive, and the proof of the main results of the paper relies on this assumption. This assumption greatly simplifies the analysis and limits the usefulness of the results. Does the uniformity still hold under the general distribution assumption? As a comparison, in most of the related work, the only assumption on the reward distribution is usually a sub-Gaussian noise. Second, the proposed estimator hat{F} is naive. I suspect that it will suffer from the curse of the horizon. Still, this is avoided under the assumption of a discrete return distribution. 
Third, the main Theorem 2 and 3 rely on knowing the confidence interval defined below Line 161. However, in the general case finding these CIs is itself the major challenge. Therefore, I think all the main results rely on strong assumptions/oracles, which greatly hurts the significance of the results. It is only universal under very simple settings and has very limited usage.


limitations_and_societal_impact: Well addressed.
review_title: null

Meta-review: The paper studies off-policy evaluation through estimates and high-confidence bounds on any parameter of the return distribution, such as its mean, variance, IQR, etc. The authors make use of importance sampling, an often-used tool in observational studies, proving that it leads to unbiased and consistent estimation of the cumulative distribution of rewards. This is later extended to provide high-confidence bounds on the CDF, and for parameters of the CDF. The implications of various commonly made assumptions are discussed and the estimators are evaluated empirically. 

The reviews were predominantly positive, arguing for acceptance with one exception. One of the main limitations raised by reviewer j4b9 was that the return distribution is assumed to be discrete. The authors clarified in their response that this limitation may be removed. Additional clarifications were made by the authors which imply only small modifications to the manuscript. 
Decision: Accept (Poster)