Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
40,247 characters · 10 sections · 28 citation commands
Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits
Off-policy evaluation is the problem of estimating the benefits of one treatment assignment policy using historical data that was collected using another. For example, in personalized healthcare we may wish to use historical data to evaluate how particular groups of patients will respond to a given treatment regime for the design of future clinical trials murphy2003optimal; in targeted advertising one may want to understand how alternative advertisements perform for different consumer segments li2011unbiased. The estimation challenge arises since an individual's outcome is observed only for the assigned treatments, so counterfactual outcomes for alternative treatments are not observed. There is a large literature on this problem in the cases where historical observations, which are collected by one or multiple policies, are independent from one another dudik2011doubly,imbens2015causal,agarwal2017effective,kallus2020optimal. However, it has been increasingly common for data to be collected in adaptive experiments, for example using contextual bandit algorithms agrawal2013thompson,lattimore2018bandit, russo2017tutorial. Contextual bandits trade off exploration and exploitation in an attempt to learn the policy that best targets the treatment assignment to an observation's context (e.g., a patient's characteristics). In these experiments, assignment probabilities depend on the context in a way that is updated over time as the algorithm learns from past data. In this paper, we focus on off-policy evaluation using data collected by contextual bandits.
One common approach to off-policy evaluation, often called the direct method (DM), is to use the historical data to estimate a regression model that predicts outcomes for each treatment/context pair, then averages this model's predictions for treatments assigned by the target policy. However, regression models fit to adaptively collected data tend to be biased villar2015multi,nie2017adaptively,shin2019sample,shin2020conditional, and this bias is inherited by DM estimators. In particular, downward bias tends to arise when fitting data generated by a bandit, as treatments for which we observe random downward fluctuations early on tend to be sampled less afterward than those for which we observe upward ones. Therefore, downward fluctuations get corrected less than upward ones when more data arrives. Consider the following example.
A natural implementation of the direct method estimates the target policy value by $T^{-1}\sum_{t=1}^{T} \hat\mu_0(X_t)$, where $\hat\mu_0(x)$ is the sample mean calculated from observed outcomes under treatment $w_0$ on context $x$. Figure (ref) shows that it has substantial bias.
An unbiased alternative, inverse propensity weighting (IPW) horvitz1952generalization, weights observations from the collected data to look like treatment were assigned using the target policy. However, when the assignments made during data collection differ substantially from those made by the target policy, called low overlap between policies, this requires the weights, and therefore the variance, to be large imbens2004nonparametric. The doubly robust (DR) estimator dudik2011doubly, also unbiased, reduces variance by combining DM and IPW. It uses a weighted average of regression residuals to correct the bias of the DM estimator, reducing variance to a degree determined by the accuracy of the regression model's predictions. This estimator is optimal in large samples when historical observations are independent and identically distributed bickel1993efficient. With observations from adaptive experiments, while what is optimal is not well understood, there is strong evidence that DR estimator is outperformed by other estimators in terms of mean squared error hadad2021confidence.
This difference in behavior is caused by drifting overlap in adaptive experiments. As the experimenter shifts the data-collection policy in response to what they observe, overlap with the target policy can deteriorate. As a result, the variance of both the IPW and DR estimators can be unacceptably large. This is exacerbated in contextual settings, as importance weights can grow without bound even when there exists a relatively small set of contexts for which overlap is low. In Example (ref), the set of contexts for which overlap worsens has total probability $0.4$, but, as shown in Figure (ref), this is enough to inflate the variance of the DR estimator.
Recently, shrinking importance weights toward one has been explored as a variance reduction strategy for the DR estimator charles2013counterfactual,wang2017optimal,su2019cab,su2020doubly. This can substantially reduce variance by introducing a potentially small bias if the amount of shrinkage is chosen well, but choosing this is a challenging tuning problem. An alternative approach focuses on local stabilization. For example, when data is collected in batches, zhang2020inference proposes the use of a hypothesis test for the policy value based on the average of batch-specific studentized statistics. zhang2020inference shows that the variance is stabilized within each batch using this hypothesis test. luedtke2016statistical propose a locally studentized version of the DR estimator that does not require batched collection, using a rolling-window estimate of a term in the DR estimator's standard deviation. hadad2021confidence refine this approach, observing that the optimal way to aggregate observations with different variances is not an inverse standard deviation weighted (standardized/studentized) average but an inverse variance weighted one. Focusing on the case of multi-armed bandits, they show that locally inverse variance weighted averages can reduce asymptotic variance while retaining its desirable inferential properties if a particular approximate rolling-window variance estimate is used. We view our method as an extension of hadad2021confidence to contextual bandits, where the story of local stabilization is more complex because the relevant notion of local variance depends on context as well as treatment.
We begin by formalizing the problem of off-policy evaluation in contextual bandits and introducing some notation. We use potential outcome notation imbens2015causal, denoting by $Y_t(w)$ a random variable representing the outcome that would be observed if at time $t$ an individual were assigned to a treatment $w$ from a finite set of options $\{1 \ldots K\}$. In any given experiment, this individual can be assigned only one treatment $W_t$, so we observe only one realized outcome $Y_t = Y_t(W_t)$. Associated to each individual is a context $X_t$; a policy $\pi$ assigns individuals with context $x$ to a treatment $w$ with probability $\pi(x,w)$.
We focus on the “stationary” environment where individuals, represented by a context $X_t \in \mathcal{X}$ and a vector of potential outcomes $\big(Y_t(1),$ $\ldots, Y_t(K)\big)$, are independent and identically distributed. However, our observations $(X_t, W_t, Y_t)$ are neither independent nor identically distributed because the assignment $W_t$ depends on the observations before it. We assume that an individual's treatment assignment is randomized, with nonzero probability of receiving each treatment,\footnote{We do, however, permit the assignment probability $e_t(x,w)$ to decay to zero as $t$ grows. This is typically what happens in bandit experiments when treatment $w$ is, on average, suboptimal for individuals with context $x$.} as a function of their context and previous observations. We write $H_t = \{(X_s,W_s,Y_s): s \le t\}$ for the history of observations up to time $t$; $e_t(x,w)=\operatorname{\mathbb{P}}(W_t=w \mid X_t=x, H_{t-1})$ for the conditional randomization probability, also known as the propensity score; and $\mu_t(x,w)=\operatorname{\mathbb{E}}[Y_t(w) \mid X_t=x]$ for the regression of the outcome on context. We summarize these assumptions as follows.
Our goal is to estimate the quantity
which is the average outcome attained when individuals are assigned treatment in accordance with the policy $\pi$, typically called the average policy value.
Because Assumption (ref)(a) implies $\mu_t(x,w)$ is constant in $t$, we will write $\mu(x,w)$ in its place from here on. To simplify notation, we will also write \smash{$\sum_{w} f(\cdot, w)$} for \smash{$\sum_{w=1}^K f(\cdot, w)$}, write $||f(z)||_{\infty}$ for the sup-norm $\sup_{z \in \mathcal{Z}} |f(z)|$ of a function $f: \mathcal{Z} \to \mathbb{R}$, and let $Q(x, \pi) := \sum_{w} \ensuremath{\mathbb{E}_{}\left[{\pi(X_t, w) Y_t(w)|X_t=x}\right]}$.
The doubly robust (DR) estimator considered here takes the form
where the objects being averaged are doubly-robust scores,
Above, $\widehat{\mu}_t(x,w)$ is an estimate of the outcome regression $\mu(x, w)$ based only on the history $H_{t-1}$. Similar estimators are widely used, including in bandit settings dudik2011doubly, howard2018uniform, van2008construction,hadad2021confidence.
Recalling that the assignment probabilities $e_t(X_t, w)$ and the estimated regression $\widehat{\mu}_{t}(X_t, w)$ are functions of the history, it is straightforward to show that the DR scores \smash{$\widehat\Gamma_t(\pi)$} are unbiased estimators of the policy value $Q(\pi)$ conditional on past history and, by the tower property, their average $\widehat Q_T^{DR}(\pi)$ is unbiased.
We refer readers to Appendix (ref) for proof details. The variance of the DR estimator is largely governed by the similarity between the policy being evaluated and the assignment probabilities. This phenomenon is expected since we should be better able to evaluate policies that assign treatments in a similar manner as that used when collecting data. The next proposition, which quantifies this intuition, is convenient when considering variance-minimizing schemes in the next section.
The proof is deferred to Appendix (ref). Averaging over the contexts in (ref), we derive a variant for the context-free conditional variance.
When overlap between the evaluation policy and the assignment mechanism deteriorates as $t$ grows (in the sense that $\sum_w \pi^2(X_t, w) / e_t(X_t, w)$ increases), the DR estimator (ref) can have high variance and heavy tails with large samples. This phenomenon is demonstrated in Figure (ref). In light of Proposition (ref), the problem is that the DR estimator is a uniformly-weighted average of scores \smash{$\widehat \Gamma_t$} with variances that can differ dramatically. We can improve on the DR estimator by averaging those scores with non-uniform weights $h_t$ that stabilize variance \smash{$\operatorname{Var}(\widehat{\Gamma}_t(X_t, \pi) \mid H_{t-1})$} term-by-term.
As stabilizing weights, we consider both weights that approximately standardize the terms \smash{$\widehat \Gamma_t$} and approximate inverse variance weights. Both rely on the variance proxy from (ref):
where different functions $\phi$ yields weights that have different properties:
We refer to both weights in (ref) as non-contextual weights, since the realized context $X_t$ is integrated out. In practice, one may not compute oracle weights (ref) exactly. We thus use a feasible approximation in our simulation,
The idea of MinVar weighting scheme is similar to the weighted IPW estimator proposed in agarwal2017effective, where the authors use the (context-independent) inverse variance to weight samples from multiple logging policies. The essential difference is that, in the adaptive setting we consider, each observation is from a new logging policy, so we must estimate inverse variance weights for each observation instead of for a relatively small number of logging policies.
The StableVar weights are less effective at reducing variance than MinVar, but would allow us to construct asymptotically valid confidence intervals if we had access to an oracle that would allow us to compute the conditional expectation in (ref). To start, we introduce additional assumptions on the data generating process and the nuisance estimator $\hat{\mu}_t$.
Assumption (ref)(a) is satisfied for various types of non-constant random variables including, for example, bounded rewards. Assumption (ref)(b) requires that exploration in the adaptive experiments should not be reduced faster than some polynomial decay rate, and is also enforced when analyzing the asymptotics of adaptive weighting for multi-armed bandits in hadad2021confidence. Assumption (ref)(c) is standard in the literature on DR estimators imbens2004nonparametric,chernozhukov2016double. We state a limit theorem, proven in Appendix (ref), for for $\hat{Q}_T^{NC}$ using StableVar weighting.
Condition (ref) says that the inverse of assignment probabilities, which essentially represents the variance of estimating the value of each arm, is asymptotically equivalent to its expectation. To understand it, consider the thought experiment of running multiple simulations of a bandit setting in which arms are identical. If the bandit algorithm is “too greedy”, spurious fluctuations in arm value estimates at the beginning can decide the algorithm's long-run behavior. In some of these simulations, $e_t(x, w)$ may increase to one while in others it may decay to zero. Condition (ref) requires that the long-run behavior of the assignment algorithm is stable. For many bandit algorithms, it will hold if, for every point of the context space, the signal from the best arm is strong enough to have it discovered eventually. For some tractable contextual bandit algorithms, for example krishnamurthy2020tractable, it holds without qualification.
We can control variance better by using context-dependent weights $h_t(x)$. Thinking of the DR estimator $\widehat Q_T^{DR}(\pi)$ as a double sum \smash{$T^{-1}\sum_{t=1}^T \sum_{x \in \operatorname{\mathcal{X}}} \mathbb{I}\{X_t=x\} \widehat \Gamma_t(x,\pi)$}, it is natural to stabilize terms in the inner sum rather than the outer, as proposed in Section (ref).
Figure (ref) demonstrates how, in Example (ref), the contextual variance proxy from (ref) varies with context. Recall that the target policy always assigns treatment $w_0$: $\pi(\cdot, w_0)=1$. For context $x_0$, treatment $w_0$ is optimal, so $e_t(x_0, w_0)$ increases over time as the experimenter learns to assign it. Thus, the variance proxy $\sum_{w}\pi^2(x_0,w)/e_t(x_0,w)$ decreases. For other contexts, $w_0$ is suboptimal and the variance proxy increases, which drives the increase in the non-contextual variance proxy (dashed black line in Figure (ref)) used in (ref).
We thus propose contextual weighting to observe such variation of score variance in context:
Here, adaptive weight $h_t(\cdot)$ is a function of context $x\in\operatorname{\mathcal{X}}$. The normalized term \smash{$h_t(X_t)/\sum_{s=1}^T h_s(X_t)$} weights the score \smash{$\widehat{\Gamma}_t$.} We define the contextual adaptive weight $h_t(x)$ as a function of the context-specific variance proxy from (ref),
where, as in Section (ref), $\phi(v)=\sqrt{1/v}$ for StableVar weights and $\phi(v)=1/v$ for MinVar weights.
Like its counterpart with non-contextual weights, the estimator (ref) admits a central limit theorem when contextual StableVar weights are used. However, our result requires more fragile assumptions on the data generating process and assignment mechanism. Again, we focus on evaluating a fixed-arm policy that always assigns a pre-specified treatment $w$.
We defer the proof to Appendix (ref). Condition (ref) requires the similar stability from assignment probabilities as Condition (ref), while this time it in addition requires a more strict assumption---a pair of inverse of $e_t$ needs to be asymptotically equivalent to its expectation.
This section provides an empirical investigation of different estimators for off-policy evaluation in contextual bandits.\footnote{Reproduction code can be found at \url{https://github.com/gsbDBI/contextual_bandits_evaluation}.} We consider four estimators: (i) the DM estimator
(ii) the DR estimator $\smash{T^{-1} \sum_{t=1}^T \widehat{\Gamma}_t}(X_t, \pi)$, (iii) the adaptively-weighted estimator with non-contextual MinVar and StableVar weights as in Section (ref), and (iv) the adaptively-weighted estimator with contextual MinVar and StableVar weights as in Section (ref). In all estimators, $\hat \mu_t(\cdot,w)$ is a linear model fit via least squares on the observations $\{(X_s,Y_s) : W_s=w,\ s < t\}$.
We consider two setups. In Section (ref), we have a synthetic data-generating process (DGP). In Section (ref), the DGP is adapted from multi-class classification datasets on OpenML OpenML2013. In both cases, we show that adaptive weighting reduces variance and MSE significantly and that contextual weighting outperforms non-contextual weighting.
\paragraph{Target policies.} We estimate the contrast $\Delta = Q(\pi_1)-Q(\pi_2)$ between the best contextual policy $\pi_1$ and the best non-contextual policy $\pi_2$. The former assigns individuals with context $x$ to the treatment $w^*(x)=\arg\max_w \operatorname{\mathbb{E}}[Y_t(w) \mid X=x]$; the latter assigns all individuals to $w^*=\arg\max_w \operatorname{\mathbb{E}}[Y_t(w)]$. To construct this estimator $\widehat{\Delta}_T$ and corresponding estimated variance $\widehat{V}_T$, we re-visit the discussion starting from Section (ref), defining the doubly robust score for the contrast as the difference in doubly robust scores for the two policies. We use variants of the adaptive weights discussed in Sections (ref) & (ref) with the variance proxy $\sum_w (\pi_1(x,w)-\pi_2(x,w))^2/e_t(x,w)$.
\paragraph{Metrics.} In Section (ref), we evaluate the performance of each estimator in terms of its root mean squared error (RMSE), bias, and the radius and coverage of $95\%$ confidence intervals based on the approximate normality of studentized estimates, as in Theorems (ref) and (ref). In Section (ref), we focus on RMSE, bias, and standard errors.
\paragraph{Data-generating process} We consider a four-arm contextual bandit setting. Each time step, the algorithm observes a vector of context $X_t \sim \operatorname{\mathcal{N}}(0, I_3)$ drawn independently. We consider two outcome models. In the no-signal setting, $\mu(x,w)=0$ for all contexts and treatments. In the signal setting, we divide the context space into four regions, depending on whether the first two coordinates $X_{t, 1}$ and $X_{t, 2}$ are above or below $0.5$. In each region, one of the treatments has $\mu(x,w)=0.7$, where all others have $\mu(x,w)=0$, so each region is associated with a distinct treatment with positive mean outcome. In both settings, we observe $Y_t = \mu(X_t,W_t) + \varepsilon_t$ where $\varepsilon_t \sim \operatorname{\mathcal{N}}(0,1)$.
\paragraph{Assignment probabilities} A modified Thompson sampling algorithm interacts with the environment, collecting data in batches of size $100$. During the first batch, the agent assigns arms uniformly at random. For each subsequent batch, the agent first discretizes context space using PolicyTree sverdrup2020policytree based on previous observations. Next, for each subspace, the algorithm computes tentative Thompson sampling assignment probabilities. Finally, a lower bound is imposed on these probabilities, so that final assignment probabilities are guaranteed to satisfy $e_t\geq t^{-0.8}/4$.
\paragraph{Data generating process} In this section we follow prior work dudik2011doubly,dimakopoulou2017estimation,su2020doubly,wang2017optimal and use multi-class classification datasets to generate bandit problems. The idea is to transform a sequential classification problem into a bandit problem, by taking features as contexts and classes as arms. At each time step, the bandit algorithm is shown a vector of features sampled uniformly from the dataset and must choose a corresponding class. If it manages to label the observation correctly, the bandit algorithm receives reward $Y_t = 1 + \varepsilon_t$ for $\varepsilon_t \sim \operatorname{\mathcal{N}}(0,1)$; otherwise, $Y_t = \varepsilon_t$. Here, we consider $86$ public datasets from OpenML OpenML2013 (see Appendix (ref) for the list of datasets), which vary in number of classes, number of features, and number of observations, as summarized in Table (ref).
\paragraph{Data collection} A linear Thompson sampling agent agrawal2013thompson is used to collect data with assignment probability floor $t^{-0.5}/K$, where $K$ is number of arms/classes.
\paragraph{Performance} For each dataset, we calculate bias and standard error (S.E.) of all estimators based on $100$ simulations.
Off-policy evaluation on adaptive data can be challenging, as observations are dependent and overlap between the target policy and data-collection policy often deteriorates over the course of data collection. Many estimators suffer from bias or high variance. In this paper, we propose a set of heuristics that address the issue by modifying the DR estimator through averaging doubly robust scores using adaptive, non-uniform weights. When chosen appropriately, these weights are able to reduce variance, at the cost of a small finite-sample bias. We prove that our estimators have consistency and asymptotic normality under certain conditions. Empirically, our estimators outperform existing alternatives with lower RMSE and expected coverage.
A number of important research directions remain. For example, it would be of interest to know if some of our more stringent sufficient conditions for asymptotic normality can be weakened, allowing for inference based on approximate normality in more general settings. Another interesting avenue of research would be to consider whether adaptive weights as presented here could be beneficial for learning optimal policies using logged data from bandit algorithms.
The authors would like to thank Stefan Wager, Sanath Kumar Krishnamurthy, and Kristine Koutout for helpful discussions. The authors are also grateful for the generous support provided by Golub Capital Social Impact Lab. S.A. acknowledges support from the Office of Naval Research grant N00014-19-1-2468 and Schmidt Futures. R.Z. acknowledges support from the Total Graduate Fellowship and PayPal Graduate Fellowship. D.A.H. acknowledges support from the Stanford Institute for Human-Centered Artificial Intelligence.