Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling

Abstract

Motivated by the many real-world applications of reinforcement learning (RL) that require safe-policy iterations, we consider the problem of off-policy evaluation (OPE) -- the problem of evaluating a new policy using the historical data obtained by different behavior policies -- under the model of nonstationary episodic Markov Decision Processes (MDP) with a long horizon and a large action space. Existing importance sampling (IS) methods often suffer from large variance that depends exponentially on the RL horizon $H$. To solve this problem, we consider a marginalized importance sampling (MIS) estimator that recursively estimates the state marginal distribution for the target policy at every step. MIS achieves a mean-squared error of $$\frac{1}{n}{\sum }_{t=1}^H{\mathbb{E}}_{\mu }\left[\frac{d_t^{\pi }(s_t{)}^2}{d_t^{\mu }(s_t{)}^2}{\mathrm{Var}}_{\mu }\left[\frac{{\pi }_t(a_t|s_t)}{{\mu }_t(a_t|s_t)}(V_{t+1}^{\pi }(s_{t+1})+r_t)|s_t\right]\right]+\tilde{O}(n^{-1.5})$$ where $\mu$ and $\pi$ are the logging and target policies, $d_t^{\mu }(s_t)$ and $d_t^{\pi }(s_t)$ are the marginal distribution of the state at $t$th step, $H$ is the horizon, $n$ is the sample size and $V_{t+1}^{\pi }$ is the value function of the MDP under $\pi$. The result matches the Cramer-Rao lower bound in \citet{jiang2016doubly} up to a multiplicative factor of $H$. To the best of our knowledge, this is the first OPE estimation error bound with a polynomial dependence on $H$. Besides theory, we show empirical superiority of our method in time-varying, partially observable, and long-horizon RL environments.

Published at the Neural Information Processing Systems (NeurIPS) 2019

References in corpus (4)

• Doubly Robust Policy Evaluation and Learning
• Continuous State-Space Models for Optimal Sepsis Treatment - a Deep Reinforcement Learning Approach
• Consistent On-Line Off-Policy Evaluation
• Combining Parametric and Nonparametric Models for Off-Policy Evaluation

Cited by in corpus (25)

• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• 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
• CoinDICE: Off-Policy Confidence Interval Estimation
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning
• Bootstrapping Fitted Q-Evaluation for Off-Policy Inference
• Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning
• Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
• Average-Reward Off-Policy Policy Evaluation with Function Approximation
• Nearly Horizon-Free Offline Reinforcement Learning
• Universal Off-Policy Evaluation
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games
• Scalable Safety-Critical Policy Evaluation with Accelerated Rare Event Sampling
• Supervised Off-Policy Ranking
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• Stateful Offline Contextual Policy Evaluation and Learning
• Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approach
• Variance-Aware Off-Policy Evaluation with Linear Function Approximation