Doubly Robust Policy Evaluation and Optimization

By Miroslav Dud'ik, Dumitru Erhan, J. Langford, Lihong Li. 2014

324 citations recorded by the source corpus.

We study sequential decision making in environments where rewards are only partially observed, but can be modeled as a function of observed contexts and the chosen action by the decision maker. This setting, known as contextual bandits, encompasses a wide variety of applications such as health care, content recommendation 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 strengths and overcome the weaknesses of the two approaches by applying the doubly robust estimation 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 estimation 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 in policy evaluation and optimization.

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

In Management Science and Operations Research

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies (2015, methodology): “A supervised-to-contextual bandit transform was proposed in (Dud́ık et al., 2014) as a method for turning classification datasets into K-armed contextual bandit datasets.”
Machine Learning Methods That Economists Should Know About (2019, methodology): “Gopalan et al. [2015]), making computation much easier. Ruiz et al. [2017] applies state-of-the-art computational techniques from machine learning (in particular, stochastic gradient descent and variational inference) together with a number of approximations in order to make the method scalable to t”
Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “ics or healthcare. Applications of ofﬂine RL for recommender systems include slate and whole-page optimization (Swaminathan et al., 2017), applying doubly robust estimation to estimate website visits Dudík et al. (2014), and A/B testing for click optimization (Gilotte et al., 2018). Policy learning ”
Estimation Considerations in Contextual Bandits (2017, background): “There is also a significant body of research that leverages balancing for offline evaluation and learning of contextual bandit or reinforcement learning policies from logged data [57, 28, 44, 27, 43, 59, 37, 60, 10, 38, 64, 26, 39, 58, 66].”
Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning (2019, methodology): “The third approach is the doubly robust (DR) method, which combines DM and IS and is given by adding the estimated q -function as a control variate (Dudik et al., 2014; Jiang and Li, 2016; Scharfstein et al., 1999).”
Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning (2019, methodology): “The third approach is the doubly robust (DR) method, which combines DM and IS and is given by adding the estimated Q-function as a control variate [5, 7, 25].”
Optimal and Adaptive Off-policy Evaluation in Contextual Bandits (2016, methodology): “In particular, there are several estimators which are unbiased 33 under mild assumptions, such as inverse propensity scoring (IPS) [6], and sharp estimates on their 34 mean squared error (MSE) for policy evaluation are well-known [5].”
Off-policy evaluation for slate recommendation (2016, methodology): “We frame the slate recommendation problem as a combinatorial generalization of contextual bandits [3, 23, 13].”
Benchmarks for Deep Off-Policy Evaluation (2021, background): “…reinforcement learning, has been studied extensively in domains such as healthcare (Thapa et al., 2005; Raghu et al., 2018), recommender systems (Dudík et al., 2014; Theocharous et al., 2015; Swaminathan et al., 2017), education (Mandel et al., 2014), and robotics (Kalashnikov et al., 2018).”
Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes (2019, methodology): “While much work has studied efficient estimation underM1 (Dudik et al., 2014; Jiang and Li, 2016; Kallus and Uehara, 2019; Thomas and Brunskill, 2016), work on M2 has been restricted to the parametric, finite-state-finite-action case (Jiang and Li, 2016) and no globally efficient estimators have bee”
Policy Evaluation and Optimization with Continuous Treatments (2018, background): “For each context, the policy determines the action which provides highest rewards as its classification label [4].”
Off-Policy Evaluation via Off-Policy Classification (2019, methodology): “State of the art methods combine IS-based estimators and model-based estimators using doubly robust estimation and ensembles to produce improved estimators with theoretical guarantees [7, 8, 10, 13, 35].”
Bias-Reduced Doubly Robust Estimation (2015, methodology): “Recentelijk worden dubbel robuuste schatters ook overwogen door grote bedrijven, zoals Google en Microsoft, in de context van beleids-optimalisatie en evaluatie van inhoudelijke aanbevelingen en reclame op het internet (Dudı́k et al. 2015). Ondanks de dubbele bescherming tegen model misspecificatie,”
Causal mediation analysis for stochastic interventions (2019, unknown): “Estimation of total effects of stochastic interventions has been the subject of recent study (Robins et al., 2004; Didelez et al., 2006; Tian, 2008; Pearl, 2009; Taubman et al., 2009; Stitelman et al., 2010; Dı́az and van der Laan, 2013; Dudı́k et al., 2014; Haneuse and Rotnitzky, 2013; Young et al.”
Neurosymbolic Programming (2021, background): “More recently, there has been increased interest in studying generalization (and sample efficiency) when the target or test domain is not the same data distribution as the training domain (Bickel et al., 2009; Dudík et al., 2014; Chen et al., 2016; Beery et al., 2018; Taori et al., 2020).”