Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
arXiv:1910.06508
Abstract
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 ) 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.
arXiv commentAccepted by ICML 2020, 21 pages, 1 figure
References in corpus (7)
- Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
- Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
- Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
- Learning from Scarce Experience
- Consistent On-Line Off-Policy Evaluation
- Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation
- Policy Optimization via Importance Sampling
Cited by in corpus (5)
- What are the Statistical Limits of Offline RL with Linear Function Approximation?
- CoinDICE: Off-Policy Confidence Interval Estimation
- Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
- Instabilities of Offline RL with Pre-Trained Neural Representation
- Statistically Efficient Off-Policy Policy Gradients