Doubly Robust Policy Evaluation and Learning

By Miroslav Dud'ik, J. Langford, Lihong Li. 2011

810 citations recorded by the source corpus.

We study decision making in environments where the reward is only partially observed, but can be modeled as a function of an action and an observed context. This setting, known as contextual bandits, encompasses a wide variety of applications including health-care policy and Internet advertising. A central task is evaluation of a new policy given historic data consisting of contexts, actions and received rewards. The key challenge is that the past data typically does not faithfully represent proportions of actions taken by a new policy. Previous approaches rely either on models of rewards or models of the past policy. The former are plagued by a large bias whereas the latter have a large variance. In this work, we leverage the strength and overcome the weaknesses of the two approaches by applying the doubly robust technique to the problems of policy evaluation and optimization. We prove that this approach yields accurate value estimates when we have either a good (but not necessarily consistent) model of rewards or a good (but not necessarily consistent) model of past policy. Extensive empirical comparison demonstrates that the doubly robust approach uniformly improves over existing techniques, achieving both lower variance in value estimation and better policies. As such, we expect the doubly robust approach to become common practice.

Subfields: Emergency Medical Services, 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 Emergency Medical Services

In Management Science and Operations Research

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Improving a Neural Semantic Parser by Counterfactual Learning from Human Bandit Feedback (2018, background): “From a machine learning perspective, related work can be found in the areas of counterfactual bandit learning (Dudik et al., 2011; Swaminathan and Joachims, 2015a), or equivalently, off-policy reinforcement learning (Precup et al.”
Can Neural Machine Translation be Improved with User Feedback? (2018, methodology): “estimated reward: regression model trained on logged rewards sampled outputs: expected estimated reward ⇒ multiplicative and additive control variate (Dudík et al., 2011; Jiang and Li, 2016)”
Machine Learning Methods That Economists Should Know About (2019, background): “Gopalan et al. [2015]), making computation much easier.”
Recommendations as Treatments: Debiasing Learning and Evaluation (2016, background): “To get unbiased estimates of recommendation quality despite missing observations, consider the following connection to estimating average treatment effects of a given policy in causal inference, that was already explored in the contextual bandit setting (Li et al., 2011; Dud´ık et al., 2011).”
The Mirage of Action-Dependent Baselines in Reinforcement Learning (2018, background): “Dud´ık et al. (2011) introduced the community to doubly-robust estimators, a speciﬁc form of control variate, for off-policy evaluation in bandit problems.”
Deep-Treat: Learning Optimal Personalized Treatments From Observational Data Using Neural Networks (2018, methodology): “The doubly robust estimation techniques combine the direct and IPS methods and generate more robust counterfactual estimates (Dudı́k, Langford, and Li 2011; Jiang and Li 2016).”
Counterfactual reasoning and learning systems: the example of computational advertising (2012, methodology): “cting a sampling distribution that reduces the variance. Our situation is less favorable because we want to use a same sampling distribution to obtain estimates for many counterfactual distributions. Dudík et al. (2011) propose a variance reduction method that extends the invariant predictor method ”
Counterfactual inference for consumer choice across many product categories (2019, background): “An alternative approach is to evaluate and compare different pricing policies directly in the held-out data in a model-free way inspired by the policy learning literature (Dudik et al., 2011; Zhou et al., 2018).”
Estimation Considerations in Contextual Bandits (2017, methodology): “Specifically, we transform a K-class classification task into a K-armed contextual bandit [28] and we use 300 public benchmark datasets for our evaluation.”
Balanced Policy Evaluation and Learning (2017, methodology): “[13] propose a weighting-based approach that combines the direct and IPW approaches by adapting the doubly robust (DR) estimator [11, 34, 35, 38]: ⌧̂DR(⇡) = 1 n Pn i=1 Pm t=1 ⇡t(Xi)μ̂t(Xi) + 1 n Pn i=1(Yi μ̂Ti(Xi))⇡Ti(Xi)/'̂Ti(Xi).”
The State of Applied Econometrics - Causality and Policy Evaluation (2016, neutral): “A literature in machine learning considers this problem ([Beygelzimer and Langford, 2009]; [Dud́ık et al., 2011]); some open questions include the ability to obtain confidence intervals on differences between policies obtained from these methods.”
Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning (2016, methodology): “The work that introduced the DR estimator for MDPs (Jiang & Li, 2015) derived it as a generalization of a doubly robust estimator for bandits (Dud´ık et al., 2011).”
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (2015, methodology): “DR was later applied to policy learning in contextual bandits (Dudı́k et al., 2011), whose finite-time variance is shown to be typically better than IS. The DR estimator in this work generalizes the work of Dudı́k et al. (2011) to sequential decision-making problems.”
Recursive partitioning for heterogeneous causal effects (2015, background): “(16) and Beygelzimer and Langford (15) propose a related approach for finding the optimal treatment policy that combines inverse propensity score methods with “direct methods” [e.”
Counterfactual Estimation and Optimization of Click Metrics for Search Engines (2014, background): “It would be interesting to see how to leverage successful ideas in related work [5, 12] to address this issue.”