Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
This work addresses the high variance problem in off-policy evaluation for reinforcement learning, offering theoretical insights that are incremental but important for improving estimator accuracy in long-horizon domains.
The paper analyzes the variance of importance sampling estimators in off-policy evaluation for finite-horizon MDPs, finding no strict variance reduction for per-decision or stationary methods compared to vanilla importance sampling, and provides conditions for variance reduction and asymptotic bounds showing exponential vs. polynomial gaps.
Off-policy policy estimators that use importance sampling (IS) can suffer from high variance in long-horizon domains, and there has been particular excitement over new IS methods that leverage the structure of Markov decision processes. We analyze the variance of the most popular approaches through the viewpoint of conditional Monte Carlo. Surprisingly, we find that in finite horizon MDPs there is no strict variance reduction of per-decision importance sampling or stationary importance sampling, comparing with vanilla importance sampling. We then provide sufficient conditions under which the per-decision or stationary estimators will provably reduce the variance over importance sampling with finite horizons. For the asymptotic (in terms of horizon $T$) case, we develop upper and lower bounds on the variance of those estimators which yields sufficient conditions under which there exists an exponential v.s. polynomial gap between the variance of importance sampling and that of the per-decision or stationary estimators. These results help advance our understanding of if and when new types of IS estimators will improve the accuracy of off-policy estimation.