Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation

Abstract

We consider the off-policy estimation problem of estimating the expected reward of a target policy using samples collected by a different behavior policy. Importance sampling (IS) has been a key technique to derive (nearly) unbiased estimators, but is known to suffer from an excessively high variance in long-horizon problems. In the extreme case of in infinite-horizon problems, the variance of an IS-based estimator may even be unbounded. In this paper, we propose a new off-policy estimation method that applies IS directly on the stationary state-visitation distributions to avoid the exploding variance issue faced by existing estimators.Our key contribution is a novel approach to estimating the density ratio of two stationary distributions, with trajectories sampled from only the behavior distribution. We develop a mini-max loss function for the estimation problem, and derive a closed-form solution for the case of RKHS. We support our method with both theoretical and empirical analyses.

21 pages, 5 figures, NIPS 2018 (spotlight)

Cited by in corpus (70)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Conservative Q-Learning for Offline Reinforcement Learning
• Behavior Regularized Offline Reinforcement Learning
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections
• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Unifying Online and Counterfactual Learning to Rank
• Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Off-Policy Policy Gradient with State Distribution Correction
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Batch Value-function Approximation with Only Realizability
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Model Selection for Offline Reinforcement Learning: Practical Considerations for Healthcare Settings
• Off-Policy Evaluation via the Regularized Lagrangian
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding
• Learning and Planning in Average-Reward Markov Decision Processes
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• Batch Policy Learning under Constraints
• GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• An Equivalence between Loss Functions and Non-Uniform Sampling in Experience Replay
• Adaptive Estimator Selection for Off-Policy Evaluation
• Incremental Intervention Effects in Studies with Dropout and Many Timepoints
• Adaptive Trade-Offs in Off-Policy Learning
• C-Learning: Learning to Achieve Goals via Recursive Classification
• Offline Reinforcement Learning with Soft Behavior Regularization
• Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning
• Learning When-to-Treat Policies
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality
• Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounders
• Offline Policy Selection under Uncertainty
• Accountable Off-Policy Evaluation With Kernel Bellman Statistics
• Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
• Deeply-Debiased Off-Policy Interval Estimation
• Learning from User Interactions with Rankings: A Unification of the Field
• Average-Reward Off-Policy Policy Evaluation with Function Approximation
• Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning
• Generalized Off-Policy Actor-Critic
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Telescoping Density-Ratio Estimation
• Variance-Reduced Off-Policy Memory-Efficient Policy Search
• Fast Rates for the Regret of Offline Reinforcement Learning
• Robust Batch Policy Learning in Markov Decision Processes
• On Instrumental Variable Regression for Deep Offline Policy Evaluation
• Explaining Off-Policy Actor-Critic From A Bias-Variance Perspective
• Optimal Off-Policy Evaluation from Multiple Logging Policies
• Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games
• Don't Forget Your Teacher: A Corrective Reinforcement Learning Framework
• Supervised Off-Policy Ranking
• Off-Policy Actor-Critic with Emphatic Weightings
• Doubly Robust Off-Policy Value and Gradient Estimation for Deterministic Policies
• Active Offline Policy Selection
• Bridging the Gap Between $f$-GANs and Wasserstein GANs
• Off-Policy Interval Estimation with Lipschitz Value Iteration
• Conditional Importance Sampling for Off-Policy Learning
• Optimal Mixture Weights for Off-Policy Evaluation with Multiple Behavior Policies
• SDA: Improving Text Generation with Self Data Augmentation
• Minimax Model Learning
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation
• Off-Policy Self-Critical Training for Transformer in Visual Paragraph Generation
• Adaptive Experience Selection for Policy Gradient
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings