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

By Nathan Kallus, Masatoshi Uehara. 2019

118 citations recorded by the source corpus.

Demystifying the Curse of Horizon in Offline Reinforcement Learning in Order to Break It Offline reinforcement learning (RL), where we evaluate and learn new policies using existing off-policy data, is crucial in applications where experimentation is challenging and simulation unreliable, such as medicine. It is also notoriously difficult because the similarity (density ratio) between observed trajectories and those generated by any new policy diminishes exponentially as the horizon grows, known as the curse of horizon, which severely limits the application of offline RL whenever horizons are moderately long or even infinite. In “Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning,” Kallus and Uehara set out to understand these limits and when they can be broken. They precisely characterize the curse by deriving the semiparametric efficiency lower bounds for the policy-value estimation problem in different models. On the one hand, this shows why the curse necessarily plagues standard estimators: they work even in non-Markov models and therefore must be limited by the corresponding bound. On the other hand, greater efficiency is possible in certain Markovian models, and they give the first estimator achieving these much lower efficiency bounds in infinite-horizon Markov decision processes.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Statistics and Probability, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, background): “Recent work (Mousavi et al., 2020; Kallus and Uehara, 2019a,b; Tang et al., 2019; Uehara and Jiang, 2019) has refined this approach, in particular removing the need to have access to πβ .”
Minimax Weight and Q-Function Learning for Off-Policy Evaluation (2019, methodology): “Here we show that in the tabular setting, which is a special case of the linear setting, MWL and MQL can achieve the semiparametric lower bound of OPE (Kallus and Uehara, 2019a), because they coincide 10See Bartlett and Mendelson (2003) for the definition.”
Is Pessimism Provably Efficient for Offline RL? (2020, unknown): “…and Li, 2016; Thomas and Brunskill, 2016; Farajtabar et al., 2018; Liu et al., 2018; Xie et al., 2019; Nachum et al., 2019a;b; Tang et al., 2019; Kallus and Uehara, 2019; 2020; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin and Wang, 2020; Yin et al., 2020; Nachum and Dai,…”
Statistically Efficient Off-Policy Policy Gradients (2020, background): “Following similar arguments as in Kallus & Uehara (2019a), which study infinite-horizon OPE, one can show that this extension of EOPPG maintains its efficiency and 3-way robustness guarantees as long as our data satisfies appropriate mixing conditions (which ensures it appropriately approximates…”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, background): “…Li et al., 2015, Jiang and Li, 2016, Thomas and Brunskill, 2016, Guo et al., 2017, Wang et al., 2017, Liu et al., 2018, Farajtabar et al., 2018, Xie et al., 2019, Kallus and Uehara, 2019, Liu et al., 2019, Uehara and Jiang, 2019, Kallus and Uehara, 2020, Jiang and Huang, 2020, Feng et al., 2020].”