Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation

Zhaohan Guo, Philip S. Thomas, Emma BrunskillNeurIPS 2017 · OpenReview

Introduction

Evaluating a new policy by deploying it in the real world can be risky and costly, especially in high-stakes environments like healthcare or robotics. Off-policy evaluation (OPE) algorithms solve this by using historical data collected from a previous policy to evaluate a new one. The gold standard for OPE is Importance Sampling (IS), which is unbiased and robust to partial observability.

However, standard IS suffers from the "curse of horizon": the variance of its estimates grows exponentially with the number of sequential decisions (the horizon) in an episode. For long-horizon tasks, the evaluation becomes so noisy it is practically useless. This paper introduces strategies to slash this variance by leveraging "options" (temporally extended actions) and a novel algorithm called Incremental Importance Sampling (INCRIS) that intelligently drops unnecessary data weights.

Methods: Breaking the Curse of Horizon

The authors propose three primary strategies to combat the exponential variance growth in long-horizon problems:

1. Temporal Abstraction (Options) Instead of evaluating every primitive action (e.g., moving a robot's joint by one degree), the evaluation is shifted to "options"—high-level actions like "move to the door." By treating a sequence of actions as a single high-level choice, the effective length of the problem shrinks. Crucially, if the old and new policies use the same sub-policy to achieve a goal, the importance weights for those steps cancel out (become 1), drastically reducing variance.

2. Stationary Options & Partitioning The paper identifies "stationary options"—sub-tasks that consistently end in the same state distribution (e.g., a robot resetting to a home position). This property allows the trajectory to be partitioned into independent segments. Each segment can be evaluated separately and summed up, preventing variance from compounding over the entire episode.

3. Incremental Importance Sampling (INCRIS) As the core algorithmic contribution, INCRIS utilizes a Covariance Test to determine which importance weights are strictly necessary. If a past weight does not correlate with future rewards (zero covariance), INCRIS drops it. While this introduces a tiny amount of bias, it yields a massive reduction in variance, optimizing the estimate for the lowest possible Mean Squared Error (MSE).

Experiments and Key Results

The authors evaluated their methods on two simulated environments: NoisyTaxi (a partially observable gridworld) and a Synthetic MDP designed to mimic real-world complexities like medical treatments or digital advertising.

Exponential Variance Reduction with Options

In the NoisyTaxi domain, leveraging options significantly stabilized the evaluation. Using 3-step options instead of primitive actions reduced the MSE by an order of magnitude. Furthermore, using the "stationary option" property to partition trajectories at specific subgoals (like passenger pickup) resulted in another 10x reduction in MSE.

MSE reduction using options-based policies

INCRIS Outperforms Standard Baselines

In the synthetic MDP experiment, the INCRIS algorithm was compared against standard IS, Per-Decision IS (PDIS), and Weighted IS (WIS). INCRIS outperformed these baselines by one to two orders of magnitude. It proved particularly effective at identifying when sub-episodes could be treated as independent, automatically dropping weights to save on variance.

INCRIS performance comparison against baselines

Limitations and Future Work

While these methods offer substantial improvements, there are limitations:

  • Domain Knowledge: Effectively using options requires the researcher to define subgoals beforehand. The paper does not focus on discovering these options automatically.
  • Covariance Estimation Noise: INCRIS relies on estimating covariance from historical data. With extremely small datasets, the covariance estimate itself might be noisy, potentially leading to sub-optimal weight-dropping decisions.
  • Scaling to Hierarchies: The authors suggest that while they focused on a single level of options, the mathematics could be extended to deep hierarchical structures (like the MAX-Q framework), which would be necessary for scaling to even more complex, real-world tasks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{guo2017using,
  author = {Zhaohan Guo and Philip S. Thomas and Emma Brunskill},
  title = {{Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=By-9T8buZS},
}
Figure