Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning

2019-09-12 · Nathan Kallus, Masatoshi Uehara

Off-policy evaluation (OPE) in reinforcement learning is notoriously difficult in long- and infinite-horizon settings due to diminishing overlap between behavior and target policies. In this paper, we study the role of Markovian and time-invariant structure in efficient OPE. We first derive the efficiency bounds for OPE when one assumes each of these structures. This precisely characterizes the curse of horizon: in time-variant processes, OPE is only feasible in the near-on-policy setting, where behavior and target policies are sufficiently similar. But, in time-invariant Markov decision processes, our bounds show that truly-off-policy evaluation is feasible, even with only just one dependent trajectory, and provide the limits of how well we could hope to do. We develop a new estimator based on Double Reinforcement Learning (DRL) that leverages this structure for OPE using the efficient influence function we derive. Our DRL estimator simultaneously uses estimated stationary density ratios and $q$-functions and remains efficient when both are estimated at slow, nonparametric rates and remains consistent when either is estimated consistently. We investigate these properties and the performance benefits of leveraging the problem structure for more efficient OPE.

📄 PDF Abstract BibTeX arXiv:1909.05850

Code (0)

등록된 구현이 없습니다.

Tasks

Off-policy evaluationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounders

2020-07-27 · Andrew Bennett, Nathan Kallus, Lihong Li, Ali Mousavi

Off-policy evaluation (OPE) in reinforcement learning is an important problem in settings where experimentation is limited, such as education and healthcare. But, in these very same settings, observed actions are often c…

Off-policy evaluation reinforcement-learning Reinforcement Learning (RL)

Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning

2020-03-24 · ICLR 2020 1 · Ali Mousavi, Lihong Li, Qiang Liu, Denny Zhou

Off-policy estimation for long-horizon problems is important in many real-life applications such as healthcare and robotics, where high-fidelity simulators may not be available and on-policy evaluation is expensive or im…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

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

2018-10-29 · NeurIPS 2018 12 · Qiang Liu, Lihong Li, Ziyang Tang, Dengyong Zhou

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 (near…

Primal-Dual Spectral Representation for Off-policy Evaluation

2024-10-23 · Yang Hu, Tianyi Chen, Na Li, Kai Wang 외

Off-policy evaluation (OPE) is one of the most fundamental problems in reinforcement learning (RL) to estimate the expected long-term payoff of a given target policy with only experiences from another behavior policy tha…

Off-policy evaluation Reinforcement Learning (RL)

Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling

2019-10-15 · ICML 2020 1 · Yao Liu, Pierre-Luc Bacon, Emma Brunskill

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 dec…

Off-policy evaluation Reinforcement Learning