More Robust Doubly Robust Off-policy Evaluation

By Mehrdad Farajtabar, Yinlam Chow, Mohammad Ghavamzadeh. 2018

294 citations recorded by the source corpus.

We study the problem of off-policy evaluation (OPE) in reinforcement learning (RL), where the goal is to estimate the performance of a policy from the data generated by another policy(ies). In particular, we focus on the doubly robust (DR) estimators that consist of an importance sampling (IS) component and a performance model, and utilize the low (or zero) bias of IS and low variance of the model at the same time. Although the accuracy of the model has a huge impact on the overall performance of DR, most of the work on using the DR estimators in OPE has been focused on improving the IS part, and not much on how to learn the model. In this paper, we propose alternative DR estimators, called more robust doubly robust (MRDR), that learn the model parameter by minimizing the variance of the DR estimator. We first present a formulation for learning the DR model in RL. We then derive formulas for the variance of the DR estimator in both contextual bandits and RL, such that their gradients w.r.t.~the model parameters can be estimated from the samples, and propose methods to efficiently minimize the variance. We prove that the MRDR estimators are strongly consistent and asymptotically optimal. Finally, we evaluate MRDR in bandits and RL benchmark problems, and compare its performance with the existing methods.

Subfields: Artificial Intelligence, Evaluation & Benchmarks

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 Evaluation & Benchmarks

Citations in the corpus

Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialog (2019, neutral): “[11, 29, 45, 60]).”
Human-centric Dialog Training via Offline Reinforcement Learning (2020, background): “, 2016)), or have performed off-policy policy evaluation (Farajtabar et al., 2018; Jiang and Li, 2016; Precup, 2000; Thomas and Brunskill, 2016).”
Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “More sophisticated estimators can be formed by training the model with knowledge of the policy to be evaluated (Farajtabar et al., 2018), and by trading off bias and variance more optimally (Thomas and Brunskill, 2016; Wang et al.”
Off-policy Bandits with Deficient Support (2020, methodology): “With terabytes of log data readily available in many online systems, a range of algorithms has been proposed for batch learning from such logged contextual-bandit feedback [5, 6, 20–22, 24, 26].”
Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning (2020, background): “Its accuracy can be improved by various techniques (Jiang & Li, 2016; Thomas & Brunskill, 2016; Guo et al., 2017; Farajtabar et al., 2018).”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, methodology): “…robustness for off-policy evaluation, orthogonal to the existing literature of doubly robust policy evaluation that solely devotes to variance reduction (Jiang & Li, 2016; Thomas & Brunskill, 2016; Farajtabar et al., 2018), mostly based on the idea of control variates (e.g. Asmussen & Glynn, 2007).”
Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, background): “Farajtabar et al. (2018) propose to optimize the choice of ˆ q ( s, a ) to minimize variance rather than use a plug-in.”
Striving for Simplicity in Off-policy Deep Reinforcement Learning (2019, background): “While there has been increasing interest in batch off-policy RL over the last few years [28, 56, 17, 25, 27], much of this focussed on off-policy policy evaluation, where the goal is to estimate the performance of a given target policy.”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “Although many improvements exist [13, 21, 38, 50], importance-weighting the entire trajectory can suffer from exponentially high variance, which is known as “the curse of horizon” [26, 27].”
Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning (2019, methodology): “Here, we follow the same procedure of transforming a classification data-set into a contextual bandit data set as in [5, 6].”
Learning When-to-Treat Policies (2019, background): “On the RL side, there has been extensive work focused on learning good models (Farajtabar et al., 2018; Hanna et al., 2017; Liu et al., 2018b).”
Hyperparameter Selection for Offline Reinforcement Learning (2020, methodology): “Moreover, OPE methods using doubly robust estimators combine both model-based and importance sampling based approaches (Dudík et al., 2011; Farajtabar et al., 2018; Jiang and Li, 2016; Thomas and Brunskill, 2016).”
Challenges of Real-World Reinforcement Learning (2019, methodology): “There are many more approaches such as MAGIC (Thomas & Brunskill, 2016) or more robust doubly robust (Farajtabar et al., 2018) that can be considered as well.”
Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes (2019, methodology): “We do this mostly for the sake of completeness since, while the influence function we derive below for the NMDP model appears as a central object in the structure of various previously proposed doubly-robust OPE estimators for RL (e.g., among others, Dudik et al., 2014; Farajtabar et al., 2018; Jian”
Off-Policy Policy Gradient with Stationary Distribution Correction (2019, background): “Some authors consider model-based approaches to OPPE (Farajtabar et al., 2018; Liu et al., 2018b), which usually perform better than importance sampling approaches empirically in policy evaluation settings.”
Batch Policy Learning under Constraints (2019, background): “However, despite our best effort, learning the dynamics model accurately proves highly challenging, as the horizon and dimensionality of this domain are much larger than popular benchmarks in the OPE literature (Jiang & Li, 2016; Thomas & Brunskill, 2016; Farajtabar et al., 2018).”
Representation Balancing MDPs for Off-Policy Policy Evaluation (2018, methodology): “MRDR [6] is a recent method that trains a Q function as275 the model-based part in DR to minimize the resulting variance.”
Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (2019, methodology): “Our approach can also be used in most of OPE estimators that leverage IS-based estimators, such as doubly robust [Jiang and Li, 2016], MAGIC [Thomas and Brunskill, 2016], MRDR [Farajtabar et al., 2018] under mild assumptions (Markov assumption).”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, methodology): “DM H YBRID D IRECT DR WDR MAGIC AM 6.6E-1 6.7E-1 6.6E-1 6.6E-1 Q-R EG 5.4E-1 6.3E-1 1.3E0 9.3E-1 MRDR 5.4E-1 7.3E-1 2.0E0 2.0E0 FQE 6.6E-1 6.6E-1 6.6E-1 6.6E-1 R ( λ ) 6.7E-1 6.6E-1 9.3E-1 1.0E0 Q π ( λ ) 6.6E-1 6.6E-1 6.6E-1 6.6E-1 T REE 6.7E-1 6.6E-1 9.4E-1”
Bias Correction of Learned Generative Models using Likelihood-Free Importance Weighting (2019, methodology): “…have a large variance, it would be worthwhile to compose our approach with other variance reduction techniques such as (weighted) doubly robust estimation in future work [33], as well as incorporate these estimates within a framework such as MAGIC to further blend with model-free OPE [14].”