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

By Nathan Kallus, Masatoshi Uehara. 2019

212 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Molecular Biology, 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 Artificial Intelligence

In Molecular Biology

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Reinforcement Learning via Fenchel-Rockafellar Duality (2020, background): “Applying the Lagrangian to (82) will result in objectives similar to those that have appeared in Kallus and Uehara (2019b); Tang et al. (2019).”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, methodology): “Independent of this work, Kallus & Uehara (2019b) extend the technique to the infinite horizon setting, whose estimator can be viewed as a variant of ours.”
Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, methodology): “Before turning to developing an eﬃcient estimator under the MDP model, we brieﬂy review how we can extend the eﬃcient ﬁnite-horizon DRL estimators of Kallus and Uehara (2019a) to be eﬃcient in the inﬁnite-horizon NMDP and TMDP settings.”
Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning (2019, positive): “Recently, this approach to efficient OPE has been extended to Markov decision process [10] and infinite-horizon problems [11]; in this paper we focus on the more general sequential decision process.”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, methodology): “Among the ideas that use marginalized state distribution [58] to improve over standard IPS, [27, 28] analyze double reinforcement learning estimator that makes use of both estimates for Q function and state density ratio.”
Efficiently Breaking the Curse of Horizon: Double Reinforcement Learning in Infinite-Horizon Processes (2019, methodology): “We show that adaptations of the doubly robust (DR) estimator in NMDPs (Jiang and Li, 2016) and in MDPs (Kallus and Uehara, 2019b) to the inﬁnite horizon case achieve these bounds, i.e. , are eﬃcient in the near-on-policy setting.”
Instabilities of Offline RL with Pre-Trained Neural Representation (2021, unknown): “…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, Yang et al., 2020, Nachum et al., 2019a, Zhang et al., 2020a,b].”
Harnessing Inﬁnite-Horizon Off-Policy Evaluation: Double Robustness via Duality (2019, methodology): “Independent of this work, Kallus & Uehara (2019b) extend the technique to the inﬁnite horizon setting, whose estimator can be viewed as a variant of ours.”
Efficient Evaluation of Natural Stochastic Policies in Offline Reinforcement Learning (2020, methodology): “(20) Here, the terms from (18) to (19) are the same as the decomposition in Kallus and Uehara (2019a).”
Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions (2022, result): “This is in accordance with similar results from [KU20] and [UIJKSX21].”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “One major line of work is concerned with the off-policy evaluation (OPE) problem [Li et al., 2015, Jiang and Li, 2016, Liu et al., 2018, Kallus and Uehara, 2019a,b, Uehara and Jiang, 2019, Xie et al., 2019, Yin and Wang, 2020, Duan and Wang, 2020].”
Statistically Efficient Off-Policy Policy Gradients (2020, unknown): “OPE is the problem of estimating J ( θ ) for a given θ from oﬀ-policy data.”
Off-Policy Evaluation via the Regularized Lagrangian (2020, background): “Off-policy evaluation has long been studied in the RL literature [9, 12, 13, 19, 23, 27].”
Offline Policy Selection under Uncertainty (2020, background): “…there is a rich literature of approaches for computing point estimates of the value of the policy (Dudík et al., 2011; Bottou et al., 2013; Jiang and Li, 2015; Thomas and Brunskill, 2016; Nachum et al., 2019; Zhang et al., 2020; Uehara and Jiang, 2020; Kallus and Uehara, 2020; Yang et al., 2020).”
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].”