The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
40,247 characters
Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits~
\maketitle
\begin{abstract}
\noindent It has become increasingly common for data to be collected adaptively, for example using contextual bandits. Historical data of this type can be used to evaluate
other treatment assignment policies to guide future innovation or experiments. However, policy evaluation is challenging if the target policy differs from the one used to collect data, and popular estimators, including doubly robust (DR) estimators, can be plagued by bias, excessive variance, or both.
In particular, when the pattern of treatment assignment in the collected data looks little like the pattern generated by the policy to be evaluated,
the importance weights used in DR estimators explode, leading to excessive variance.
In this paper, we improve the DR estimator by adaptively weighting observations to control its variance.
We show that a $t$-statistic based on our improved estimator is asymptotically normal under certain conditions,
allowing us to form confidence intervals and test hypotheses.
Using synthetic data and public benchmarks, we provide empirical evidence for our estimator's improved accuracy and inferential properties
relative to existing alternatives.
\end{abstract}
\section{Introduction}\label{sec:introduction}
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 \citep{murphy2003optimal}; in targeted advertising one may want to understand how alternative advertisements perform for different consumer segments \citep{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~\citep{dudik2011doubly,imbens2015causal,agarwal2017effective,kallus2020optimal}. However, it has been increasingly common for data to be collected in adaptive experiments, for example using \emph{contextual bandit} algorithms \citep[e.g.,][]{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.
\begin{figure}[t]
\centering
\includegraphics[width=.6\linewidth]{images/intro.pdf}
\caption{Distribution of DM and DR policy value estimates in Example~\ref{example} over $1000$ simulations. The interquartile range (IQR) box represents the middle $50\%$ of the data, and the whiskers are extended by $1.5$ of the IQR past the low and high quartiles. DM is highly skewed and has large downward bias due to adaptive data collection, while DR has high variance and heavy tails due to large importance weights from the poor overlap between the data-collection mechanism and the target policy.
}
\label{fig:intro}
\end{figure}
One common approach to off-policy evaluation, often called the \emph{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 \citep{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.
\begin{example}
\label{example}
We run a contextual bandit experiment with a Thompson sampling agent \citep{thompson1933likelihood}, collecting $1000$ observations for one simulation. At each time $t$, a context $X_t$ is sampled from the context space $\{x_0, x_1, x_2, x_3, x_4\}$ with probability $[0.6, 0.1, 0.1, 0.1, 0.1]$. The agent chooses one $W_t=w_j$ out of five treatments $\{w_0, w_1, w_2, w_3, w_4\}$ based on assignment probabilities that are computed using previous observations, and observes the outcome $\operatorname{\mathbb{I}}\{i=j\} + \varepsilon_t$, where $\varepsilon_t$ is standard normal. The target policy always assigns treatment $W_t=w_0$.
\end{example}
\noindent 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{fig:intro} shows that it has substantial bias.
An unbiased alternative, \emph{inverse propensity weighting} (IPW) \citep{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 \emph{low overlap} between policies,
this requires the weights, and therefore the variance, to be large \citep{imbens2004nonparametric}.
The doubly robust (DR) estimator \citep{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 \citep{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 \citep{hadad2021confidence}.
This difference in behavior is caused by \emph{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{example}, the set of contexts for which overlap worsens has total probability $0.4$,
but, as shown in Figure~\ref{fig:intro}, 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 \citep{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, \cite{zhang2020inference} proposes the use of
a hypothesis test for the policy value based on the average of batch-specific studentized statistics. \citeauthor{zhang2020inference} shows that the variance is stabilized
within each batch using this hypothesis test. \cite{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.
\cite{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 \cite{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.
\section{Setting}
We begin by formalizing the problem of off-policy evaluation in contextual bandits and introducing some notation.
We use potential outcome notation \citep{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.
\begin{assumption} For all periods $t$, \\
\label{assu:data}
\vspace{-.4cm}
\begin{enumerate}[(a)]
\item $(X_t, Y_t(1) \ldots Y_t(K))$ are independent and identically distributed;
\item $(Y_t(1) \ldots Y_t(K)) \perp\!\!\!\perp W_t \mid X_t,\ H_{t-1}$
\item $e_t(x,w)>0$ for all $(x,w)$.
\end{enumerate}
\end{assumption}
Our goal is to estimate the quantity
\begin{equation}
Q(\pi)
:= \sum_{w=1}^K \operatorname{\mathbb{E}}[\pi(X_t, w) Y_t(w)],
\end{equation}
which is the average outcome attained when individuals are assigned treatment in accordance with the policy $\pi$, typically called the \emph{average policy value}.
Because Assumption~\ref{assu:data}(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]}$.
\section{Doubly robust estimator}
\label{sec:dr}
The doubly robust (DR) estimator considered here takes the form
\begin{equation}
\label{eq:qdr}
\widehat{Q}_T^{DR}(\pi) := \frac{1}{T} \sum_{t=1}^{T} \widehat{\Gamma}_t(X_t, \pi),
\end{equation}
\noindent where the objects being averaged are \emph{doubly-robust scores},
\begin{equation*}
\label{eq:aipw}
\widehat{\Gamma}_t(X_t, \pi)
:= \sum_{w} \pi(X_t,w) \Big( \widehat{\mu}_t(X_t, w) + \frac{\operatorname{\mathbb{I}}\{W_t=w\}}{e_t(X_t,w)}(Y_t-\widehat{\mu}_t(X_t, w))\Big).
\end{equation*}
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 \citep{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.
\begin{proposition}[Unbiasedness] For any $\pi\in\Pi$, we have
\label{prop:aipw_unbiased}
\[ \operatorname{\mathbb{E}}\big[\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t\big] = \sum_w \pi(X_t, w)\mu(X_t, w) \ \mbox{ and }
\ \operatorname{\mathbb{E}}\big[\widehat{Q}_T^{DR}(\pi)\big]
=
\operatorname{\mathbb{E}}\Big[\frac{1}{T} \sum_{t=1}^{T}
\operatorname{\mathbb{E}}\big[\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}\big]
\Big]
= Q(\pi).
\]
\end{proposition}
\noindent We refer readers to Appendix~\ref{sec:proof_aipw_unbiased} 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.
\begin{proposition}[Dominant Term of Variance]
\label{prop:aipw_var} Under Assumption~\ref{assu:data}, suppose there are positive, finite constants $C_0$, $C_1$ such that for all $w$ and $t$, $\operatorname{Var}(Y_t(w)\mid X_t)\in[C_0, C_1]$. Suppose there is a finite constant $C_2$ such that
$\norm{\mu}_{\infty} < C_2$ and $\norm{\widehat{\mu}_t}_{\infty} < C_2$ for all $t$. Then, there exist positive, finite constants $L$, $U$ depending only on $C_0, C_1, C_2$ such that for any $\pi\in\Pi$ and all $t$,
\begin{equation}
\label{eq:gamma_condvar_x}
L\leq \ensuremath{\mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}, X_t}\right)} \Big/ \operatorname{\mathbb{E}}\Big[\sum_{w}\frac{\pi^2(X_t,w)}{e_t(X_t,w)}\Big|H_{t-1}, X_t\Big] \leq U.
\end{equation}
\end{proposition}
\noindent The proof is deferred to Appendix~\ref{sec:proof_aipw_var}. Averaging over the contexts in \eqref{eq:gamma_condvar_x}, we derive a variant for the context-free conditional variance.
\begin{equation}
\label{eq:gamma_condvar}
L\leq \ensuremath{\mathrm{Var}_{}\left({\widehat{\Gamma}_t(X_t, \pi)|H_{t-1}}\right)} \Big/ \operatorname{\mathbb{E}}\Big[\sum_{w}\frac{\pi^2(X_t,w)}{e_t(X_t,w)}\Big|H_{t-1}\Big] \leq U.
\end{equation}
\section{Adaptive weighting}
\label{sec:noncontextual_weighting}
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 \eqref{eq:qdr} can have high variance and heavy tails with large samples. This phenomenon is demonstrated in Figure~\ref{fig:intro}.
In light of Proposition~\ref{prop:aipw_var}, 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.
\begin{equation}
\label{eq:qnc}
\widehat{Q}^{NC}_T(\pi) :=
\sum_{t=1}^T
\frac{h_t}{\sum_{s=1}^T h_s}
\widehat{\Gamma}_t(X_t, \pi),
\end{equation}
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 \eqref{eq:gamma_condvar}:
\begin{equation}
\label{eq:hnc_infeasible}
h_t := \phi\Big(
\operatorname{\mathbb{E}}\Big[
\sum_{w}
\frac{\pi^2(X_t;w)}{e_t(X_t;w)}\Big|H_{t-1}\Big]
\Big),
\end{equation}
where different functions $\phi$ yields weights that have different properties:
\begin{enumerate}[(i)]
\item \texttt{StableVar}: $\phi(v)=\sqrt{1/v}$ yields weights $h_t$ that approximately standardize the terms of $\widehat{Q}^{NC}_T$.
\item \texttt{MinVar}: $\phi(v)=1/v$ yields weights $h_t$ that approximately minimize the variance of $\widehat{Q}^{NC}_T$.
\end{enumerate}
We refer to both weights in \eqref{eq:hnc_infeasible} as \emph{non-contextual} weights, since the realized context $X_t$ is integrated out. In practice, one may not compute oracle weights \eqref{eq:hnc_infeasible} exactly. We thus use a feasible approximation in our simulation,
\begin{equation}
\label{eq:hnc_feasible}
\widetilde h_t := \phi\Big(
\frac{1}{t-1}
\sum_{s=1}^{t-1}
\sum_{w}
\frac{\pi^2(X_s;w)}{e_t(X_s;w)}
\Big).
\end{equation}
The idea of \texttt{MinVar} weighting scheme is similar to the weighted IPW estimator proposed in \cite{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 \texttt{StableVar} weights are less effective at reducing variance than \texttt{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 \eqref{eq:hnc_infeasible}.
To start, we introduce additional assumptions on the data generating process and the nuisance estimator $\hat{\mu}_t$.
\begin{assumption}
\label{assu:clt_condition}
Suppose that the following conditions are satisfied:
\begin{enumerate}[(a)]
\item $\operatorname{Var}(Y_t(w)|X_t=x)\geq C_0$ and $\operatorname{\mathbb{E}}[Y_t^4(w)|X_t=x]\leq C_1$ for all $w, x$ and some positive constants $C_0, C_1$.
\item $e_t(x,w) \geq Ct^{-\alpha}$
for all $w, x$ and some constants $C$ and $ \alpha\in[0,\frac{1}{2})$.
\item $\sup_{w,x}|\mu(x,w)|$ and $\sup_{t,w,x}|\hat\mu_t(x,w)|$ are uniformly bounded and $\hat \mu_t$ is convergent in the sense that,
for some function $\mu_\infty$,
$\sup_{w,x}|\hat\mu_t(x, w)-\mu_\infty(x, w)| \to 0$ almost surely.
\end{enumerate}
\end{assumption}
Assumption~\ref{assu:clt_condition}(a) is satisfied for various types of non-constant random variables including, for example, bounded rewards. Assumption~\ref{assu:clt_condition}(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 \cite{hadad2021confidence}. Assumption~\ref{assu:clt_condition}(c) is standard in the literature on DR estimators \citep{imbens2004nonparametric,chernozhukov2016double}. We state a limit theorem,
proven in Appendix~\ref{sec:proof_noncontextual_clt}, for for $\hat{Q}_T^{NC}$ using \texttt{StableVar} weighting.
\begin{theorem}
\label{thm:non_contextual}
Under Assumptions~\ref{assu:data} and~\ref{assu:clt_condition}, estimator $\widehat{Q}_T^{NC}(\pi)$ with \texttt{StableVar} weights is consistent for true policy value $Q(\pi)$. Furthermore, suppose that assignment probabilities $e_t$ satisfy
\begin{equation}
\label{eq:e_convergence}
\sup_{x,w}\bigg|\frac{e_t^{-1}(x,w)}{\operatorname{\mathbb{E}}[e_t^{-1}(x,w)]} - 1\bigg|\rightarrow0, \quad a.s.
\end{equation}
Then non-contextual \texttt{StableVar} weighting yields an asymptotically normal studentized statistic
\begin{equation}
\label{eq:clt_noncontextual}
\frac{\widehat{Q}_T^{NC}(\pi)-Q(\pi)}{\big(\widehat{V}^{NC}_T(\pi)\big)^{1/2}}
\xrightarrow{d}\operatorname{\mathcal{N}}(0,1),
\ \text{ where } \
\widehat{V}_T^{NC}(\pi) := \frac{\sum_{t=1}^T h_t^2\big(\widehat{\Gamma}_t(X_t, \pi) -\widehat{Q}_T^{NC}(\pi) \big)^2 }{\big(\sum_{t=1}^T h_t \big)^2}.
\end{equation}
\end{theorem}
Condition \eqref{eq:e_convergence} 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 \eqref{eq:e_convergence}
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 \cite{krishnamurthy2020tractable},
it holds without qualification.
\section{Adaptive contextual weighting}
\label{sec:contextual_weighting}
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{sec:noncontextual_weighting}.
Figure~\ref{fig:arm0} demonstrates how, in Example~\ref{example},
the contextual variance proxy from \eqref{eq:gamma_condvar_x} 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{fig:arm0}) used in \eqref{eq:hnc_infeasible}.
\begin{figure}[H]
\centering
\includegraphics[width=.8\linewidth]{images/motivation_contextual.pdf}
\caption{In Example~\ref{example}, the contextual variance proxy $\sum_{w}\pi^2(X_t,w)/e_t(X_t,w)$ from Proposition~\ref{prop:aipw_var} varies significantly by context. We plot
the median and bands indicating $2.5$th and $97.5$th percentiles over $1000$ simulations.}
\label{fig:arm0}
\end{figure}
We thus propose \emph{contextual} weighting to observe such variation of score variance in context:
\begin{equation}
\label{eq:qc}
\widehat{Q}_T^C(\pi) = \sum_{t=1}^T \frac{h_t(X_t)}{\sum_{s=1}^T h_s(X_t)}\widehat{\Gamma}_t(X_t, \pi).
\end{equation}
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 \eqref{eq:gamma_condvar_x},
\begin{equation}
\label{eq:hc}
h_t(x) = \phi\Big(\sum_{w}\frac{\pi^2(x,w)}{e_t(x,w)}\Big), \quad x\in \operatorname{\mathcal{X}},
\end{equation}
where, as in Section~\ref{sec:noncontextual_weighting},
$\phi(v)=\sqrt{1/v}$
for \texttt{StableVar} weights and $\phi(v)=1/v$ for \texttt{MinVar} weights.
Like its counterpart with non-contextual weights, the estimator \eqref{eq:qc} admits a central limit theorem when contextual \texttt{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$.
\begin{theorem}
\label{thm:contextual}
Suppose Assumptions~\ref{assu:data} and~\ref{assu:clt_condition} hold and the context space $\operatorname{\mathcal{X}}$ is discrete, estimator $\widehat{Q}^C_T(\pi)$ with \texttt{StableVar} weights is consistent for the true policy value $Q(\pi)$.
Further, suppose that assignment probabilities $e_t$ satisfy that,
\begin{equation}
\label{eq:e_pair_convergence}
\begin{aligned}
\sup_{x,w} \bigg|\frac{\operatorname{\mathbb{E}}[e_t^{-1}(x,w)]}{e_t^{-1}(x,w)}-1 \bigg|\rightarrow 0, \mbox{ and }\sup_{x,x',w,w'} \bigg|\frac{\operatorname{\mathbb{E}}[e_t^{-1}(x,w) e_t^{-1}(x',w')]}{e_t^{-1}(x,w) e_t^{-1}(x',w')} -1 \bigg|\rightarrow 0, \quad \mbox{a.s. and in }L_1.
\end{aligned}
\end{equation}
Then contextual \texttt{StableVar} weighting \eqref{eq:hc} yields an asymptotically normal studentized statistic:
\begin{equation}
\label{eq:clt_contextual}
\begin{aligned}
&\frac{\widehat{Q}_T^{C}(\pi)-Q(\pi)}{\big(\widehat{V}^{C}_T(\pi)\big)^{1/2}}\xrightarrow{d}\operatorname{\mathcal{N}}(0,1),\mbox{ where } \\
\widehat{V}_T^{C}(\pi) = \sum_{t=1}^T \Big(&\frac{h_t(X_t)}{\sum_{s=1}^T h_s(X_t)}\widehat{\Gamma}_t(X_t, \pi) - \sum_{s=1}^T\frac{h_t(X_s)h_s(X_s)}{\big(\sum_{s'=1}^T h_{s'}(X_s)\big)^2} \widehat{\Gamma}_s(X_s, \pi) \Big)^2 .
\end{aligned}
\end{equation}
\end{theorem}
\noindent We defer the proof to Appendix~\ref{sec:proof_contextual_clt}. Condition \eqref{eq:e_pair_convergence} requires the similar stability from assignment probabilities as Condition \eqref{eq:e_convergence}, 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.
\section{Experimental results}
\label{sec:simulation}
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
\begin{equation}
\widehat{Q}^{DM}_T(\pi)=T^{-1}\sum_{t=1}^T\sum_{w}\widehat{\mu}_{T}(X_t,w)\pi(X_t, w),
\end{equation}
(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 \texttt{MinVar} and \texttt{StableVar} weights as in Section~\ref{sec:noncontextual_weighting}, and (iv) the adaptively-weighted estimator with contextual \texttt{MinVar} and \texttt{StableVar} weights as in Section~\ref{sec:contextual_weighting}.
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{sec:synth}, we have a synthetic data-generating process (DGP). In Section~\ref{sec:class}, the DGP is adapted from multi-class classification datasets on OpenML \citep{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{sec:dr}, 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{sec:noncontextual_weighting} \&~\ref{sec:contextual_weighting} with the variance proxy $\sum_w (\pi_1(x,w)-\pi_2(x,w))^2/e_t(x,w)$.
\paragraph{Metrics.} In Section~\ref{sec:synth}, 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{thm:non_contextual} and~\ref{thm:contextual}. In Section~\ref{sec:class}, we focus on RMSE, bias, and standard errors.
\subsection{Synthetic datasets}
\label{sec:synth}
\begin{figure}
\centering
+ \includegraphics[width=\linewidth]{images/region_contrast.pdf}
\caption{Evolution of estimates of contrast value between best contextual policy and best non-contextual policy with synthetic data in Section \ref{sec:synth}. X-axis is the sample size. Error bars indicate $95\%$ confidence intervals based on averaging over $10^5$ replications of the simulation.}
\label{fig:region}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=\linewidth]{images/contrast_hist.pdf}
\caption{Histogram of studentized statistics of the form $(\widehat{\Delta}_T - \Delta) / \widehat{V}_T^{1/2}$ for estimating the contrast value between best contextual policy and best non-contextual policy at $T=7000$ with synthetic data in Section \ref{sec:synth}. Numbers aggregated over $10^5$ replications.}
\label{fig:region_hist}
\end{figure}
\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 \emph{no-signal} setting, $\mu(x,w)=0$ for all contexts and treatments. In the \emph{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 \citep{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$.
\begin{itemize}
\item \textbf{RMSE.} Figure \ref{fig:region} shows that in both scenarios, adaptive weighting reduces RMSE significantly as compared to DR, and contextual weighting has a larger improvement than non-contextual weighting. When there is signal, DM is outperformed by all other methods as a result of substantial bias. When there is no signal, it performs best, as the systematic biases in evaluating each of the two policies---which generate identical rewards in the case of no signal---cancel out.
\item \textbf{Inference.} Figures \ref{fig:region} shows that
in the signal scenario, adaptive weighting has nominal coverage with improved power relative to DR; in the no-signal scenario, only non-contextual weighting has nominal coverage. Such inferential properties are also verified by the t-statistics shown in Figure \ref{fig:region_hist}. This is in line with our theorems---Theorem ~\ref{thm:contextual} for contextual weighting requires higher-order stability of assignment probabilities as compared to Theorem~\ref{thm:non_contextual}. DM tends to be much more biased than variable, so confidence intervals based on the assumption of asymptotic normality with negligible bias and variance of approximately $\widehat{V}^{DM}_T(\pi) = T^{-2}\sum_{t=1}^T\big(\widehat{Q}^{DM}_T(\pi)-\sum_{w}\widehat{\mu}_{T}(X_t,w)\pi(X_t,w)\big)^2$ do not yield much coverage in our simulations; thus, we omit it in our coverage plots.
\end{itemize}
\subsection{Sequential classification with bandit feedback}
\label{sec:class}
\begin{table}[t]
\centering
\begin{tabular}{|cc|cc|cc|}
\hline
Classes & Count &Features & Count &Observations & Count \\
\hline
$2$ & 66 & $\leq 10$ & 46 & $\leq 1$k & 44\\
$>2$, $\leq 8$ & 16 &$>10$, $\leq 50$ & 36 & $>1$k, $\leq 10$k & 32\\
$>8$ & 4 & $>50$ & 4 & $>10$k & 10\\
\hline
\end{tabular}
\hfill
\caption{Characteristics of $86$ public datasets used for sequential classification in Section~\ref{sec:public_datasets}.}
\label{tab:dataset}
\end{table}
\begin{figure}[tb]
\centering
\includegraphics[width=\linewidth]{images/dataset.pdf}
\caption{Comparison among different estimators when evaluating the contrast between optimal contextual policy and best fixed-arm policy across $86$ datasets. Each point corresponds to one dataset, and its cartesian coordinates are bias and standard error normalized by RMSE of DR estimate for the same dataset. Note that the distance of each point from zero is its relative RMSE.}
\label{fig:dataset}
\end{figure}
\begin{figure}
\centering
\begin{subfigure}[t]{\textwidth}
\centering
\includegraphics[width=\linewidth]{images/dataset_compare.pdf}
\caption{Contextual weighting \emph{v.s.} non-contextual weighting. Each point corresponds to one dataset, and its cartesian coordinates are bias and S.E. of the contextual weighting normalized by the RMSE of its non-contextual counterpart. }
\label{fig:dataset_compare}
\end{subfigure}
\vspace{0.5cm}
\begin{subfigure}[t]{\textwidth}
\includegraphics[width=\linewidth]{images/dataset_compare_2.pdf}
\caption{\texttt{MinVar} \emph{v.s.} \texttt{StableVar}. Each point corresponds to one dataset, and its cartesian coordinates are bias and standard error of the \texttt{MinVar} weighting normalized by the RMSE of the \texttt{StableVar} counterpart. }
\label{fig:dataset_compare_2}
\end{subfigure}
\caption{Pairwise comparison when evaluating the contrast between best contextual policy and best non-contextual policy across $86$ datasets.}
\end{figure}
\paragraph{Data generating process} In this section we follow prior work \citep{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 \citep{OpenML2013} (see Appendix~\ref{sec:dataset} for the list of datasets), which vary in number of classes, number of features, and number of observations, as summarized in Table~\ref{tab:dataset}.
\paragraph{Data collection} A linear Thompson sampling agent \citep{agrawal2013thompson} is used to collect data with assignment probability floor $t^{-0.5}/K$, where $K$ is number of arms/classes.
\label{sec:public_datasets}
\paragraph{Performance} For each dataset, we calculate bias and standard error (S.E.) of all estimators based on $100$ simulations.
\begin{itemize}
\item \textbf{Adaptive weighting \emph{v.s.} DR.} Figure~\ref{fig:dataset} uses DR as a baseline and shows its comparison with adaptive weighting and DM on various datasets. Each subplot corresponds to an estimation method, wherein each point denotes a dataset, and its $(x,y)$ coordinates are bias and standard error normalized by RMSE of DR estimate on the same dataset. It can be seen that all adaptive weighting schemes reduce RMSE as compared to DR in most datasets. In many, RMSE is reduced by half. We also note that across various datasets, standard error accounts for most of the RMSE with adaptive weighting and DR estimates, while bias is the main factor for DM.
\item \textbf{Non-contextual \emph{v.s.} contextual.} Figure~\ref{fig:dataset_compare} proceeds to investigate within adaptive weighting, how contextual weighting performs as compared to its non-contextual counterpart. In the left panel, each point denotes a dataset, and its $(x,y)$ coordinates are bias and standard error of contextual \texttt{MinVar} normalized by RMSE of non-contextual \texttt{MinVar} on the same dataset. The same visualization approach is applied to contextual and non-contextual \texttt{StableVar} in the right panel. We see a clear improvement in RMSE of contextual weighting over the non-contextual.
\item \textbf{\texttt{MinVar} \emph{v.s.} \texttt{StableVar}.} We compare the two adaptive weighting choices \texttt{MinVar} and \texttt{StableVar} in Figure~\ref{fig:dataset_compare_2}. As before, each point corresponds to a dataset. The $(x,y)$ coordinates are bias and standard error of \texttt{MinVar} normalized by its \texttt{StableVar} counterpart in forms of both non-contextual weighting (left panel) and contextual weighting (right panel). We can see that \texttt{MinVar} typically reduces RMSE relative to \texttt{StableVar}.
\end{itemize}
\section{Discussion}
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.
\section*{Acknowledgements}
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.
\bibliographystyle{apalike}
\bibliography{reference}
\clearpage