Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation
Evaluating a policy by deploying it in the real world can be risky and costly. Off-policy policy evaluation (OPE) algorithms use historical data collected from running a previous policy to evaluate a new policy, which provides a means for evaluating a policy without requiring it to ever be deployed. Importance sampling is a popular OPE method because it is robust to partial observability and works with continuous states and actions. However, the amount of historical data required by importance sampling can scale exponentially with the horizon of the problem: the number of sequential decisions that are made. We propose using policies over temporally extended actions, called options, and show that combining these policies with importance sampling can significantly improve performance for long-horizon problems. In addition, we can take advantage of special cases that arise due to options-based policies to further improve the performance of importance sampling. We further generalize these special cases to a general covariance testing rule that can be used to decide which weights to drop in an IS estimate, and derive a new IS algorithm called Incremental Importance Sampling that can provide significantly more accurate estimates for a broad class of domains.
[I have read the other reviews and the author feedback, and updated my rating to be borderline accept. The paper will be substantially stronger with more realistic expts.
In the absence of such expts, I suspect that the IncrIS estimator will run into substantial computational challenges and sub-optimal MSE in realistic scenarios.]
The paper introduces new off-policy estimators to evaluate MDP policies. The options-based estimator of Theorem3 is a straightforward adaptation of per-step importance sampling. 
Section6 makes an interesting observation: if at any step in the trajectory we know that the induced state distribution is the same between the behavior policy and the evaluation policy, we can partition the trajectory into two sub-parts and conduct per-step importance sampling on each sub-part. This observation may prove to be more generally useful; in this paper, they exploit this observation to propose the IncrIS estimator. 
IncrIS uses sample variance and covariance estimates (presumably; this detail is missing in their experiment description) to detect what prefix of sampled trajectories can be safely ignored [i.e. yields smaller (estimated) MSE of per-step importance sampling on the resulting suffix]. This is an interesting approach to bias-variance trade-offs in importance-sampling-estimator design that can be explored further; e.g. covariance testing requires us to fix the choice of k (ignored prefix length) across the entire set of trajectories. Can we condition on the observed trajectories to adaptively discard importance weights?
In summary, the contributions up to Section 6 seem very incremental. IncrIS introduces an intriguing bias-variance trade-off but the experimental evidence (MSE in a constructed toy MDP)is not very convincing. In realistic OPE settings, it is likely that horizons will be large (so IncrIS can shine), but there may be lots of sampled trajectories (computational challenge for IncrIS to compute \hat{MSE}), and we almost certainly won't be in the asymptotic regime where we can invoke strong consistency of IncrIS (so, \hat{MSE} may yield severely sub-optimal choices, and IncrIS may have poor empirical MSE). Due to these intuitions, a more realistic experiment will be much more informative in exploring the strengths and weaknesses of the proposed estimators.
Minor:
66: \ldots
112: one *can* leverage *the* advantage?