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 where and are the logging and target policies, d_t^(s_t) and d_t^(s_t) are the marginal distribution of the state at tth step, H is the horizon, n is the sample size and V_t+1^ is the value function of the MDP under . The result matches the Cramer-Rao lower bound in 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.

Tasks

Reproductions