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.
