Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This work constructs non-asymptotic confidence intervals for off-policy evaluation. This is achieved by assuming that the reward at any given time only depends on the state action pair, leveraging that assumed structure to define the difference between the empirical and estimated bellman residual operators as a Martingale difference sequence. This, in turn, then allows the authors to apply a Hoeffding-like concentration inequality which applies to Hilbert spaces. The authors then provide a derivation of the confidence bounds by considering the divergence between policies. The work improves on the rate of prior work from $O(n^{-\frac{1}{4}})$ to $O(n^{-\frac{1}{2}})$ and allows for estimation without the need of global optimality via the dual formulation, both of which are very nice additions to the literature. Experimental evaluation backs up the authors’ claims, showing very strong performance with respect to prior art. 


I found this paper to be very well written and presented, with impressively thorough theoretical results and good empirical validation. 
A couple of minor questions:

(1) Performance of the proposed method when the functions don’t lie in an RKHS. It appears that the formulation in appendix E provides a bound which uses Rademacher complexity and doesn’t rely on an RKHS. Can the authors provide intuition around how much worse we would expect this to be in practice? 

(2) Proposition G.1 makes a case for the necessity of assuming a smoothness condition in the absence of an independence between transition pairs. Under a milder condition on transition pair independence, e.g. a mixing condition, are similar bounds to those presented in the current work attainable?

review_title: Review for Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Bounds

final_score: rating: 7: Good paper, accept
review_content: The objective of this paper is to provide a method to produce tighter confidence intervals for off-policy evaluation. The paper claims to develop a new primal-dual perspective on OPE confidence intervals and a tight concentration inequality. It develops both theoretical and empirical evidence to support its claims. 

Previous methods (Feng et al. 2020) estimate the high upper confidence bound on the bellman residual for q_pi given a set of data and then perform a global optimization procedure to find the largest q function with an empirical error less than the upper bound on the residual. This paper proposes to estimate instead of a confidence interval for the expected bellman error over the empirical data set for any q function. The dual approach from other OPE estimators is then leveraged to create high confidence bounds on the objective function. 

This paper's strengths are that the presented method could significantly improve confidence intervals for off-policy evaluation with a moderate length horizon and when an RKHS can represent the q function. There is both theory and empirical data to gain insights into the effectiveness of the method and show it a possible solution. 

Although the method appears to be effective, I cannot yet recommend it for acceptance due to some of the unsubstantiated claims and a lack of clarity in the paper's writing. There are also some ways that the experiments should be improved. 

This paper claims to produce a tight concentration inequality, but this is not proven. The claim may be a confusion of the wording and that it is intended to mean that the presented method is only a relative improvement over existing methods. Can the authors clarify the intended scope of this claim? If the claim is to be a tight concentration inequality, then a proof showing it cannot be improved is required. 

Additionally, it is stated that this work is a "substantial extension of [dual form OPE] to the non-asymptotic region, and therefore is both of theoretical and practical significance." However, it is unclear what problem this paper overcomes in previous methods to make this a substantial extension to the non-asymptotic region. The formulation and the use of the dual form do not appear substantial as it is currently presented because, as the authors point out, many others have proposed this form. What is the source of this substantial extension?

In the definition of c_{q,k}, the supremum over x,y is used, but it is unclear if this is over the empirical data or any possible x,y. Can the authors clarify this?

Notes about experiments:
The results look very promising for the method, and the ablation studies in the appendix help understand some of its properties. However, there is significant room for improvement in experimental design. The main component lacking in the experiments is a demonstration of the limitations of the method. The only thing I can take away from these results is that this method worked on these problems. I do not doubt that this method is more effective than PDIS for moderate length horizons, but cannot predict when it will be useful. 

Horizons of length 50 and 100 were used, but the discount factor was set to 0.95, making the effective horizon only 20. I do not see why this is an effective choice for demonstrating the capabilities of the method. Furthermore, all of these environments are typically simulated with much longer horizons (at least a thousand steps for cart-pole, inverted pendulum, and the diabetes simulator). It would be helpful to see this method's capabilities in a more typical experimental setup. 

Another shortcoming of the experiments is that the behavior policy is only a high-temperature version of the evaluation policy. Typically, when off-policy estimation is performed, it is not to reduce the policy's noise but evaluate a different policy altogether. Since this work makes no claims or assumptions about the policy used to generate the data, it would make sense to demonstrate that the confidence intervals are accurate and reliable when using significantly different behavior policies or multiple behavior policies. 


Writing notes:
Overall, the paper's writing indicates that it was written for experts who already know and understand the paper's concepts. It would be more useful to the ICLR and RL communities if the paper were written for a more general audience. 

Minor notes: 
In Section 2, the objective function is called the expected reward, which implies an average reward setting, but this is not the objective function's formulation. The wording is confusing here. 

There is a missing reference to proof of theorem 4.2 in the appendix. 
The term IS is used for importance sampling, but the formulation is actually per decision importance sampling (PDIS). Specifying this would add clarity to the paper. 

Figure 1 (c) is not described.

--EDIT-- updated score to 7 after the author's response to questions and changes to the paper. 
review_title: A potentially practical method for OPE

final_score: rating: 6: Marginally above acceptance threshold
review_content: **General overview**
The paper studies an off-policy evaluation (OPE) problem for Markov decision processes (MDPs). It suggests an optimization-based method that can construct a non-asymptotic confidence interval, for a given confidence level, for the value function of a policy starting from a fixed initial distribution. The paper builds on the works of Feng et al. (2019, 2020); the main advantages of the current work with respect to the previous methods are that the suggested approach guarantees a faster convergence rate, it does not require full independence between transition pairs, and it does not need the global optimal solution of the underlying optimization problem, in order to construct guaranteed confidence intervals. The authors present some theoretical results about the construction, including a discussion on the special case of using RKHS approaches, and also present numerical experiments on benchmark problems, such as the inverted-pendulum, cartpole and type-1 diabetes.

**Strengths of the paper**
-- In general, constructing confidence regions for value functions of RL policies is an important problem (however, the paper only addresses a restrictive special case of this problem, see below).
-- The presented method is a clear improvement over a recent OPE confidence interval construction with fewer conditions and better rate (for this special case of OPE).
-- The properties of the method are analyzed theoretically, "primal" and "dual" bounds are given.
--  Illustrative numerical experiments are also presented on benchmark RL problems. 

**Weaknesses of the paper**
-- The paper is obscurely written, for example, several objects are not precisely defined. It is not clear from the description on page 2 whether the state and action spaces of the MDP are finite or they can be more general (for example, Borel spaces). If the state space is finite, then using RKHS approaches (at least theoretically) seems unnecessary. On the other hand, if the state space can be infinite, then some structural assumptions are needed, for example, about its measurability.
-- It is also not clear how should the quantity I_Q(omega, hat{D}_n) computed in practice. 
-- The precise interpretation of the theoretical results, such as Theorem 4.2, is not obvious, either.
-- A major drawback of this work is that it only considers the OPE problem from a fixed, known initial distribution of the states. This is no more general than solving the problem for only one particular starting state. A much more interesting problem would be to have a confidence region for the entire value function, under some structural assumptions on the problem.
-- The claim in the "Experiments" part that "Our method is safe (always captures the true value) and tight [...], while the other methods are either too lose or often fail to capture the ground truth" is dubious, as the goal (see also on page 2) is not to "always" capture the true value, but to capture it *with a given probability*. Also, increasing this probability will make the resulting interval less tight. Mathematically, the Type I and II errors are traded off against each other.

**Minor comments**
-- Some more explanations and motivations would be needed for the concept of "functional" Bellman loss.
-- In the sentence below equation (8) "sup" and "inf" should be used instead of "min" and "max" (or some argument should be given that the maximum and minimum can be actually obtained).
-- It would be better to cite the 2018 extended 2nd edition of Sutton and Barto's classical RL book, instead of its 1st edition published in 1998.
review_title: An improved confidence interval construction for a special case of off-policy evaluation in MDPs

final_score: rating: 7: Good paper, accept
review_content: This paper proposes an approach to construct confidence intervals using finite samples for off-policy evaluation. The paper improves the bound of a previous paper from $O(n^{-1/4})$ to $O(n^{-1/2})$ and avoids solving global optimum by introducing the dual. It is also noted that the results do not only apply to independent data. The authors further show the advantage of their method as compared to existing baselines in simulations, where their approach demonstrates good coverage and tight bound. The paper is well written. 

I have some comments/thoughts as below:
- how would point estimation of the policy value be derived using such an approach? In many cases, it's also desirable to give a point estimation so that we can compute mse , etc.
- it may be worth mentioning the findings (or some intuition) of the ablation study in Appendix H in the main body to be more educational, such as how the overlap between behavior policy and target policy influences the results.  

Please address and clarify these points above. 
review_title: This paper derives a tighter non-asymptotic confidence interval for off-policy evaluation.

Meta-review: The paper introduces new tighter non-asymptotic confidence intervals for off-policy evaluation, and all reviewers generally liked the results. I recommend acceptance of this paper. Some concerns of Reviewer2 and Reviewer3 are not fully addressed in your rebuttal. Please make sure to address all remaining issues.
Decision: Accept (Poster)