Optimal and Adaptive Off-policy Evaluation in Contextual Bandits

By Yu-Xiang Wang, Alekh Agarwal, Miroslav Dud'ik. 2016

239 citations recorded by the source corpus.

We study the off-policy evaluation problem---estimating the value of a target policy using data collected by another policy---under the contextual bandit model. We consider the general (agnostic) setting without access to a consistent model of rewards and establish a minimax lower bound on the mean squared error (MSE). The bound is matched up to constants by the inverse propensity scoring (IPS) and doubly robust (DR) estimators. This highlights the difficulty of the agnostic contextual setting, in contrast with multi-armed bandits and contextual bandits with access to a consistent reward model, where IPS is suboptimal. We then propose the SWITCH estimator, which can use an existing reward model (not necessarily consistent) to achieve a better bias-variance tradeoff than IPS and DR. We prove an upper bound on its MSE and demonstrate its benefits empirically on a diverse collection of data sets, often outperforming prior work by orders of magnitude.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability, Reinforcement Learning, Statistical Learning Theory

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

In Statistical Learning Theory

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “In these settings, the model is typically trained from offline data (Jiang and Li, 2015; Thomas and Brunskill, 2016; Farajtabar et al., 2018; Wang et al., 2017).”
The Mirage of Action-Dependent Baselines in Reinforcement Learning (2018, methodology): “In this direction, several recent methods have successfully mixed high-variance, unbiased on-policy gradient estimates directly with low-variance, biased off-policy or model-based gradient estimates to improve performance (O’Donoghue et al., 2016; Wang et al., 2016b; Gu et al., 2017a).”
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].”
Off-policy Bandits with Deficient Support (2020, neutral): “As for counterfactual estimator R̂(π ), most algorithms rely on some form of IPS weighting [5, 21, 22, 24, 25, 27] to correct the distribution mismatch between the logging policy π0 and each target policy π ∈ Π.”
Batch Stationary Distribution Estimation (2020, background): “, 2009) and off-policy evaluation (Wang et al., 2017; Xie et al., 2019).”
GenDICE: Generalized Offline Estimation of Stationary Values (2020, background): “Off-policy evaluation with importance sampling (IS) has has been explored in the contextual bandits (Strehl et al., 2010; Dudı́k et al., 2011; Wang et al., 2017), and episodic RL settings (Murphy et al.”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, background): “Off-Policy Value Evaluation The problem of off-policy value evaluation has been studied in contextual bandits (Dudík et al., 2011; Wang et al., 2017) and more general finite horizon RL settings (Fonteneau et al.”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, background): “The problem of off-policy policy evaluation has been heavily studied in contextual bandits [12, 49, 52] and in the more general RL setting [14, 21, 26, 29, 34, 36, 37, 50, 51].”
Intrinsically Efficient, Stable, and Bounded Off-Policy Evaluation for Reinforcement Learning (2019, background): “For example, [32, 35] propose hybrid estimators that blend or switch to DM when importance weights are very large.”
Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation (2018, methodology): “When extended to long-horizon problems, it faces an exponential blowup of variance, and variance-reduction techniques are used to improve the estimator [14, 39, 10, 42].”
Off-policy evaluation for slate recommendation (2016, methodology): “The IPS estimator is minimax optimal [34], so its exponential variance is unavoidable in the worst case.”
Benchmarks for Deep Off-Policy Evaluation (2021, background): “Although considerable theoretical (Thomas & Brunskill, 2016; Swaminathan & Joachims, 2015; Jiang & Li, 2015; Wang et al., 2017; Yang et al., 2020) and practical progress (Gilotte et al.”
Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (2019, methodology): “IS-based off-policy evaluation methods have also seen lots of interest recently especially for short-horizon problems, including contextual bandits [Murphy et al., 2001; Hirano et al., 2003; Dudík et al., 2011; Wang et al., 2017].”
Policy Evaluation and Optimization with Continuous Treatments (2018, methodology): “IPW is unbiased, with a slower rate of convergence dependent on the number of treatments [3], and it is optimal in the sense of minimax efficiency when no additional information about the reward structure is available [24].”
Horizon: Facebook's Open Source Applied Reinforcement Learning Platform (2018, background): “predict the performance of a newly learned policy without having to deploy it online [8, 13, 26, 38, 41].”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, background): “For contextual bandits, it has been shown that while DR is highly competitive, it is sometimes substantially outperformed by DM [56].”