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.
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.
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