Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes

Abstract

Off-policy evaluation (OPE) in reinforcement learning allows one to evaluate novel decision policies without needing to conduct exploration, which is often costly or otherwise infeasible. We consider for the first time the semiparametric efficiency limits of OPE in Markov decision processes (MDPs), where actions, rewards, and states are memoryless. We show existing OPE estimators may fail to be efficient in this setting. We develop a new estimator based on cross-fold estimation of $q$-functions and marginalized density ratios, which we term double reinforcement learning (DRL). We show that DRL is efficient when both components are estimated at fourth-root rates and is also doubly robust when only one component is consistent. We investigate these properties empirically and demonstrate the performance benefits due to harnessing memorylessness.

References in corpus (5)

• Adaptive Concentration of Regression Trees, with Application to Random Forests
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Fast rates for empirical risk minimization over càdlàg functions with bounded sectional variation norm
• More Efficient Off-Policy Evaluation through Regularized Targeted Learning

Cited by in corpus (31)

• Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Distributed Double Machine Learning with a Serverless Architecture
• CoinDICE: Off-Policy Confidence Interval Estimation
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding
• Batch Policy Learning in Average Reward Markov Decision Processes
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• Localized Debiased Machine Learning: Efficient Inference on Quantile Treatment Effects and Beyond
• Off-Policy Evaluation and Learning for External Validity under a Covariate Shift
• Robust Policies For Proactive ICU Transfers
• Learning When-to-Treat Policies
• Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounders
• Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning
• Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
• Fast Rates for the Regret of Offline Reinforcement Learning
• Robust Batch Policy Learning in Markov Decision Processes
• Projected State-action Balancing Weights for Offline Reinforcement Learning
• Statistically Efficient Off-Policy Policy Gradients
• Bounding the Difference between the Values of Robust and Non-Robust Markov Decision Problems
• Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games
• Optimal Off-Policy Evaluation from Multiple Logging Policies
• Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorability
• Estimating the Long-Term Effects of Novel Treatments
• Double Robust Representation Learning for Counterfactual Prediction
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Scalable Safety-Critical Policy Evaluation with Accelerated Rare Event Sampling
• Identification of Subgroups With Similar Benefits in Off-Policy Policy Evaluation
• Stateful Offline Contextual Policy Evaluation and Learning
• Conditional Importance Sampling for Off-Policy Learning