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.
49,538 characters · 16 sections · 43 citation commands
Off-Policy Evaluation and Learning for External Validity under a Covariate Shift
In various applications, such as ad-design selection, personalized medicine, search engines, and recommendation systems, there is a significant interest in evaluating and learning a new policy from historical data kdd2009_ads, www2010_cb, AtheySusan2017EPL. To accomplish this, we use off-policy evaluation (OPE) and off-policy learning (OPL). The goal of OPE is to evaluate a new policy by estimating the expected reward of the new policy dudik2011doubly,wang2017optimal,narita2019counterfactual,pmlr-v97-bibaut19a,Kallus2019IntrinsicallyES,Oberst2019. In contrast, OPL aims to find a new policy that maximizes the expected reward ZhaoYingqi2012EITR,KitagawaToru2018WSBT,ZhouZhengyuan2018OMPL,Chernozhukov2019.
Although an OPE method provides an estimator of the expected reward of a new policy, most existing studies presume that the distribution of covariates is the same between the historical and evaluation data. However, in many real-world applications, the expected reward of a new policy over the distribution of evaluation data is of significant interest, which can be different from the historical data. For example, in the medical literature, it is known that the result of a randomized controlled trial (RCT) cannot be directly transported because the covariate distribution in a target population is different ColeStephenR.2010GEFR. This problem is known as a lack of external validity PearlJudea2015EVFD. These situations where historical and evaluation data follow different distributions are also known as covariate shifts shimodaira2000improving,NIPS2007_3248. This situation is illustrated in Figure (ref).
Under a covariate shift, standard methods of OPE do not yield a consistent estimator of the expected reward over the evaluation data. Moreover, a covariate shift changes the efficiency bound of OPE, which is the lower bound of the asymptotic mean squared error (MSE) among reasonable $\sqrt{n}$-consistent estimators. Besides, standard theoretical analysis of OPE cannot be applied to the covariate shift case as in Remark (ref). To handle the covariate shift, we apply importance weighting using the density ratio between the distributions of the covariates of the historical and evaluation data shimodaira2000improving,Reddi2015.
\paragraph{Contributions:} This paper has four main contributions. First, we derive an efficiency bound of OPE under the covariate shift (Section (ref)). Second, in Section (ref), we propose estimators constructed by estimators of the density ratio, behavior policy, and conditional expected reward. Especially, we employ nonparametric density ratio estimation from kanamori2012kulsif to estimate the density ratio. The proposed estimator is an efficient estimator, which achieves the efficiency bound under mild nonparametric rate conditions of the estimators of nuisance functions. In addition, this estimator is robust to model-misspecification of estimators in the sense that the resulting estimator is consistent if either (i) models of the density ratio and the behavior policy or (ii) a model of the conditional average treatment effect is correct. Importantly, we do not require the Donsker conditions for those estimators by applying the cross-fitting (Section (ref)). Third, we propose other possible estimators for our problem setting and compare them (Section (ref)). Fourth, an algorithm of OPL is proposed based on efficient estimators (Section (ref)). All proofs are shown in Appendix (ref).
\paragraph{Related work:} The difference between distributions of covariates conditioned on a chosen action is also called a covariate shift pmlr-v28-zhang13d,pmlr-v48-johansson16. A covariate shift in this paper refers to the different distributions of covariates between historical and evaluation data. DahabrehIssaJ.2019Gcif,JohanssonFredrik2018LWRf,pmlr-v108-sondhi20a analyzed the treatment effect estimation under a covariate shift; however, our perspective and analysis are completely different from theirs. Besides, there are many studies regarding the external validity on a causal directed acyclic graph PearlJ2011ToCa,PearlJudea2015EVFD. This paper focuses on statistical inference and learning instead of an identification strategy.
In this section, we introduce our problem setting and review existing literature.
Let $A_i$ be an action taking variable in $\mathcal{A}$ and $Y_i\in\mathbb{R}$ be a reward of an individual $i\in\mathbb{N}$. Let $X_i$ and $Z_i$ be the covariate observed by the decision maker when choosing an action, and $\mathcal{X}$ be the space of the covariate. Let a policy $\pi:\mathcal{X}\times\mathcal{A}\to[0,1]$ be a function of a covariate $x$ and action $a$, which can be considered as the probability of choosing an action $a$ given $x$. In this paper, we have access to historical and evaluation data. For the historical data, we can observe a dataset $\mathcal{D}^{\mathrm{hst}}=\{(X_i, A_i, Y_i)\}^{n^{\mathrm{hst}}}_{i=1}$, which are independent and identically distributed (i.i.d.)for the evaluation data, we can observe an i.i.d. dataset $\mathcal{D}^{\mathrm{evl}}=\{Z_i\}^{n^{\mathrm{evl}}}_{i=1}$, where $n^{\mathrm{hst}}$ and $n^{\mathrm{evl}}$ denote the sample sizes of historical and evaluation data, respectively. We assume $\mathcal{D}^{\mathrm{hst}}$ and $\mathcal{D}^{\mathrm{evl}}$ are independent. Then, the data-generating process (DGP) is defined as follows:
where $n^{\mathrm{hst}}=\rho n$, $n^{\mathrm{evl}}=(1-\rho)n$, $p(x)$ and $q(x)$ are densities\footnote{We use $x$ and $z$ exchangeably noting the spaces of $X$ and $Z$ are the same such as $q(x),q(z)$ and $p(x),p(z)$. On the other hand, we strictly distinguish $X_i$ and $Z_i$ noting these are different random variables.} over $\mathcal{X}$, and $\rho\in(0,1)$ is a constant. The policy $\pi^{\mathrm{b}}(a \mid x)$ of the historical data is called a behavior policy. We generally assume $p(x),\,q(x)$ and $\pi^\mathrm{b}(a\mid x)$ to be unknown. In comparison to the usual situation of OPE, the density of historical data, $p(x)$, can be different from that of the evaluation data, $q(x)$.
\paragraph{Notation:} This paper distinguishes the covariates between the historical and evaluation data as $X_i$ and $Z_i$, respectively. Hence, for a function $\mu:\mathcal{X}\to\mathbb{R}$, $\mathbb{E}[\mu(X)]$ and $\mathbb{E}[\mu(Z)]$ imply taking expectation over historical and evaluation data, respectively. Likewise, the empirical approximation is denoted as $\mathbb{E}_{n^{\mathrm{hst}}}[\mu(X)]=1/n^{\mathrm{hst}}\sum_{i}\mu(X_i)$ and $\mathbb{E}_{n^{\mathrm{evl}}}[\mu(X)]=1/n^{\mathrm{evl}}\sum_{i}\mu(Z_i)$. Additionally, let $\|\mu(X,A,Y)\|_2$ be $\mathbb{E}[\mu^2(X,A,Y)]^{1/2}$ for the function $\mu$, $\mathbb{E}_{p(x,a,y)}[\mu(x,a,y)]$ be $\int \mu(x,a,y)p(x,a,y)\mathrm{d}(x,a,y)$, the asymptotic MSE of estimator $\hat R$ be $\mathrm{Asmse}[\hat R]=\lim_{n\to \infty}n \mathbb{E}[(\hat R-R)^2]$, and $\mathcal{N}(0,A)$ be a normal distribution with mean $0$ and variance $A$. Besides, we use functions $r(x)=q(x)/p(x)$, $w(a,x)=\pi^\mathrm{e}(a\mid x)/\pi^\mathrm{b}(a\mid x)$, and $f(a,x)=\mathbb{E}[Y\mid X=x,A=a]$. Let us denote the estimators of $r(x)$, $w(a,x)$, and $f(a,x)$ as $\hat r(x)$, $\hat w(a, x)$, and $\hat f(a, x)$, respectively. Other notations are summarized in Appendix (ref).
We are interested in estimating the expected reward of an evaluation policy $\pi^{\mathrm{e}}(a \mid x)$, which is pre-specified for the evaluation data. Here, we assume a covariate shift, which is a common situation in the literature of external validity. Under a covariate shift, while the conditional distribution of $y$ are the same between historical and evaluation data, the distribution of evaluation data is different from historical data, i.e., the distribution of evaluation data with evaluation policy $\pi^\mathrm{e}$ follows $q(z)\pi^\mathrm{e}(a \mid z)p(y\mid a,z)$. Then, we define the expected reward of evaluation policy as follows:
Then, the first goal is OPE; i.e., estimating $R(\pi^{\mathrm{e}})$ using the historical data $\{X_i,A_i,Y_i\}_{i=1}^{n^{\mathrm{hst}}}$ and evaluation data $\{Z_i\}^{n^{\mathrm{evl}}}_{i=1}$. The second goal is OPL; i.e., training a new policy that maximizes the expected reward as $\pi^* = \operatorname*{arg\,max}_{\pi\in\Pi}R(\pi)$, where $\Pi$ is the policy class. In some cases, to construct an estimator $R(\pi)$, we use $r(x)$, $w(a,x)$, and $f(a,x)$. These functions are called nuisance functions. Let $\hat{r}(x)$, $\hat{w}(a,x)$, and $\hat{f}(a,x)$ be their estimators.
\paragraph{Assumptions:} We assume strong overlaps for $r(x)$, $w(a, x)$ and theirs estimators and boundedness for $Y_i$ and $\hat{f}$ using a constant $R_{\max} > 0$.
Here, we review the existing works of OPE, OPL, and the density ratio estimation.
\paragraph{Standard OPE and OPL:} We review three types of standard estimators of $\mathbb{E}_{p(x)\pi^\mathrm{e}(a\mid x)p(y\mid x,a)}[y]$ under the case where $q(x)=p(x)$ in ((ref)). The first estimator is an inverse probability weighting (IPW) estimator given by $\mathbb{E}_{n^{\mathrm{hst}}}[\hat w(A,X)Y]$ Horvitz1952,rubin87,cheng1994,hirano2003efficient,swaminathan15a. Even though this estimator is unbiased when the behavior policy is known, it often suffers from high variance. The second estimator is a direct method (DM) estimator $\mathbb{E}_{n^{\mathrm{hst}}}[\hat f(A,X)]$ HahnJinyong1998OtRo, which is weak against model misspecification for $f(a,x)$. The third estimator is a doubly robust estimator robins94 defined as
Under certain conditions, it is known that this estimator achieves the efficiency bound (a.k.a semiparametric lower bound), which is the lower bound of the asymptotic MSE of OPE, among regular $\sqrt{n}$-consistent estimators VaartA.W.vander1998As \footnote{Formally, regular estimators means estimators whose limiting distribution is insensitive to local changes to the DGP. Refer to VaartA.W.vander1998As }. This efficiency bound is
where $v(x)=\mathbb{E}_{\pi^\mathrm{e}(a\mid x)}[f(a,x)\mid x]$ narita2019counterfactual. Such estimator is called an efficient estimator. These estimators are also used for OPL ZhangBaqun2013Reoo,AtheySusan2017EPL.
\paragraph{Density Ratio Estimation:} To estimate $R(\pi)$, we apply an importance weighting using the density ratio between distributions of historical and evaluation covariates. For example, if we know $r(x)$ and $w(a,x)$, we can construct an estimator of $R(\pi^\mathrm{e})$ as $\mathbb{E}_{n^{\mathrm{hst}}}[r(X)w(A,X)Y]$. If we know the behavior policy as in an RCT, we can exactly know $w(a,x)$. However, since we do not know the density ratio $r(x)$ directly even in an RCT, we have to estimate $r(x)$ using the covariate data: $\{X_i\}_{i=1}^{n^{\mathrm{hst}}}$ and $\{Z_i\}_{i=1}^{n^{\mathrm{evl}}}$. To estimate the density ratio $r(x)$, we use a nonparametric one-step loss based estimator. For example, we employ Least-Squares Importance Fitting (LSIF), which uses the squared loss to fit the density-ratio function kanamori2012kulsif. We show details in Appendix (ref).
\remark[Difference from standard OPE problems]
Our current problem, i.e., policy evaluation under a shift in domain and policy, differs from a standard policy evaluation problem only under a shift in the policy. For our domain and policy shift problem, we assume a stratified sampling, i.e, fixed $\rho$ w.r.t $n$. Instead, in the literature of a policy shift, people assume a sampling scheme is i.i.d. As in WooldridgeJeffreyM.2001APOW, the difference of these two sampling schemes makes the analysis different.
We can also assume that samples are i.i.d in our problem by treating $\rho$ is a random variable and assuming each replication follows a mixture distribution DahabrehIssaJ.2019Gcif. However, under this assumption, the efficiency bound cannot be calculated in an explicit form. Besides, $\rho$ is often given as a constant value by some design QinJing1998IfCa.
We discuss the efficiency bound of OPE under a covariate shift. Efficiency bound is defined for an estimand under some posited models of the DGP bickel98. If this posited model is a parametric model, it is equal to the Cram\'{e}r-Rao lower bound. When this posited model is non or semiparametric model, we can still define a corresponding Cram\'{e}r-Rao lower bound. In this paper, we modify the standard theory under i.i.d. sampling to the current problem with a stratified sampling scheme. The formal definition is shown in Appendix (ref).
Here, we show the efficiency bound of OPE under a covariate shift.
Three things are remarked. First, the knowledge of the density function of the historical data $p(x)$ and the behavior policy $\pi^\mathrm{b}(a\mid x)$ does not change the efficiency bound ((ref)). This is because the target functional does not include these two densities. Second, the efficiency bound under a covariate shift ((ref)) reduces to the bound without a covariate shift ((ref)) in a special case, $r(x)=1$ and $\rho=0.5$. Then, we can see ((ref))$=2\times $((ref)). The factor $2$ originates from the scaling of asymptotic MSE. Third, we need to calculate the efficient influence function, which is a key function to derive the efficiency bound. This function is useful to construct the efficient estimator.
For OPE under a covariate shift, we propose an estimator constructed from the following basic form:
where $\hat r(x)$, $\hat w(a,x)$, and $\hat f(a,x)$ are nuisance estimators of $r(x)$, $w(a,x)$, and $f(a,x)$, and $\hat v(z)=\mathbb{E}_{\pi^\mathrm{e}(a\mid z)}[\hat f(a,z)\mid z]$. As well as the standard doubly robust estimator ((ref)), the above form is designed to have the double robust structure regarding the model specifications of $r(x)w(a, x)$ and $f(a, x)$. First, we consider the case where $\hat r(x)=r(x)$ and $\hat w(a,x)=w(a,x)$, but $\hat f(a,x)$ is equal to $f^{\dagger}(a,x)$ and different from $f(a,x)$, i.e., we have correct models for $r(x)$ and $w(a,x)$, but not for $f(a,x)$. Then, ((ref)) is a consistent estimator for $R(\pi^\mathrm{e})$ since
Second, we consider the case where $\hat f(a,x)=f(a,x)$, but $\hat r(x)$ and $\hat w(a,x)$ are equal to functions $r^{\dagger}(x)$ and $w^{\dagger}(a,x)$, which are different from $r(x)$ and $w(a,x)$, respectively, i.e, we have correct models for $f(a,x)$, but not for $r(x)$ and $w(a,x)$. Then, ((ref)) is a consistent estimator for $R(\pi^\mathrm{e})$ since
The formal result is given later in Theorem (ref).
Next, we consider estimating $r(x)$, $w(a,x)$, and $f(a,x)$. For example, for $f(a,x)$ and $w(a,x)$, we can apply complex and data-adaptive regression and density estimation methods such as random forests, neural networks, and highly adaptive Lasso DiazIvan2019Mlit. Note that $\hat w(a,x)$ is estimated as $\pi^\mathrm{e}/\hat{\pi}^{b}$ since $\pi^\mathrm{e}$ is known, where $\hat \pi^{b}$ is an estimator of $\pi^\mathrm{b}$. For $r(x)$, we can use the data-adaptive density ratio method in Section (ref). Although such complex estimators approximate the true values well, it is pointed out that such estimators often violate the Donsker condition VaartA.W.vander1998As,ChernozhukovVictor2018Dmlf. \footnote{When the square integrable envelope function exists and the metric entropy of the function class is controlled at some rates, Donker's condition is satisfied VaartA.W.vander1998As.}, which is required to obtain the asymptotic distribution of an estimator of interest, such as ((ref)).
For deriving the asymptotic distributions of an estimator of $R(\pi^\mathrm{e})$ using estimators without the Donsker condition, we apply cross-fitting klaassen1987,ZhengWenjing2011CTME,ChernozhukovVictor2018Dmlf based on ((ref)). The procedure is as follows. First, we separate data $\mathcal{D}^{\mathrm{hst}}$ and $\mathcal{D}^{\mathrm{evl}}$ into $\xi$ groups. Next, using samples in each group, we estimate the nuisance functions nonparametrically. Then, we construct an estimator of $R(\pi^\mathrm{e})$ using the nuisance estimators. For each group $k\in\{1,2,\dots,\xi\}$, we define
where ${\mathbb{E}}_{n^\mathrm{hst}_{k}}$ is the sample average over $k$-th partitioned historical data with $n^\mathrm{hst}_{k}$ samples and ${\mathbb{E}}_{n^\mathrm{evl}_{k}}$ is the sample average over $k$-th partitioned evaluation data with $n^\mathrm{evl}_{k}$ samples. Finally, we construct an estimator of $R(\pi^\mathrm{e})$ by taking the average of the $K$ estimators, $\{\hat R_k\}$. We call the estimator doubly robust estimator under a covariate shift (DRCS) and denote it as $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$. The whole procedure is given in Algorithm (ref).
In the following, we show the asymptotic property of $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$. First, $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$ is efficient.
Importantly, the Donsker condition is not needed for nuisance estimators owing to the cross-fitting and the doubly robust form of $\hat{R}_{\mathrm{DRCS}}$. What we only need are rate conditions. The rate conditions are mild since these are nonparametric rates smaller than $1/2$. For example, this is satisfied when $p=1/4$, $q=1/4$. With some smoothness conditions, the nonparametric estimator $\hat f(a,x)$ can achieve this convergence rate WainwrightMartinJ2019HS:A. Regarding $r(x)w(a,x)$, we can show that if $\hat r(x)$ and $\hat w(a,x)$ similarly satisfy some nonparametirc rates, $\hat r(x)\hat w(a,x)$ satisfies it as well.
Next, we formally show double robustness of the estimator, i.e., the estimator is consistent if either $r(x)w(a,x)$ or $f(a,x)$ is correct.
In a standard OPE, the DR type estimator is consistent when we know a behavior policy. In contrast, under a covariate shift, even when the behavior policy is known, we cannot claim $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$ is consistent since $r(x)$ is unknown. This result suggests the estimation of $r(x)$ is crucial.
We have discussed the doubly robust estimator in the previous section. Next, we propose other estimators under a covariate shift based on IPW and DM estimators. We analyze the property of each estimator with nuisance estimators obtained from the classical kernel regression Nada:1964,Wats:1964. We show regularity conditions and formal results of Theorems (ref)--(ref) in (ref).
We consider IPW and DM type estimators under a covariate shift for each case where we have an oracle of $\pi^\mathrm{b}(a\mid x)$ and we do not have any oracles of nuisance functions, respectively. In comparison to a standard OPE case, we can consider two fundamentally different IPW type estimators.
\paragraph{IPW estimator with oracle $\pi^\mathrm{b}(x)$:} This is a natural setting in an RCT and and A/B testing since we assign actions following a certain probability in theses cases. Let us define an IPW estimator under a covariate shift with the true behavior policy $\pi^\mathrm{b}(a\mid x)$ (IPWCSB) as $\hat R_{\mathrm{IPWCSB}}(\pi^\mathrm{e})=\mathbb{E}_{n^{\mathrm{hst}}}\left[\frac{\hat q(X)}{\hat p(X)}\frac{\pi^\mathrm{e}(A\mid X)Y}{\pi^\mathrm{b}(A\mid X)}\right]$. For example, we use classical kernel density estimators of $q(x)$ and $p(x)$:
where $K(\cdot)$ is a kernel function, $h$ is the bandwidth of $K(\cdot)$, and $d$ is a dimension of $x$. When using a kernel estimator, we obtain the following theorem.
\paragraph{Fully nonparametric IPW estimator:} Next, for the case without the oracle $\pi^\mathrm{b}$, let us define an IPW estimator under a covariate shift (IPWCS) as $\hat R_{\mathrm{IPWCS}}(\pi^\mathrm{e})=\mathbb{E}_{n^{\mathrm{hst}}}\left[\frac{\hat q(X)\pi^\mathrm{e}(A \mid X)Y}{\hat p(X)\hat \pi^\mathrm{b}(A \mid X)}\right]$. This estimator achieves the efficiency bound.
\paragraph{DM Estimator:} Finally, we define a nonparametric DM estimator $\hat R_{\mathrm{DM}}(\pi^\mathrm{e})$ as $\textstyle \mathbb{E}_{n^{\mathrm{evl}}}[\mathbb{E}_{\pi^\mathrm{e}(a\mid Z)}[\hat f(a,Z)\mid Z]]$. This estimator achieves the efficiency bound.
We compare the estimators discussed so far. This is also summarized in Table (ref). First, the estimator $\hat R_{\mathrm{DRCS}}$ allows any non-Donsker type complex estimators with lax convergence rate conditions of the nuisance estimators. However, the analyses of $\hat R_{\mathrm{IPWCS}}$ and $\hat R_{\mathrm{DM}}$ are specific to the kernel estimators though the asymptotic MSE of $\hat R_{\mathrm{IPWCS}},\,\hat R_{\mathrm{DM}}$ and $\hat R_{\mathrm{DRCS}}$ are the same in this special case. When the kernel estimators are replaced with any non-Donsker type complex estimators, the rate condition $\|\hat r(X)\hat w(A,X)-r(X)w(A,X)\|_2=\mathrm{o}_{p}(n^{-1/4})$ or $\|\hat f(A,X)-f(A,X)\|_2=\mathrm{o}_{p}(n^{-1/4})$ cannot guarantee the $\sqrt{n}$-consistency and efficiency even if we use cross-fitting. Second, the only $\hat{R}_{\mathrm{DRCS}}$ has double robustness; however, $\hat R_{\mathrm{IPWCS}}$ and $\hat R_{\mathrm{DM}}$ do not have this property.
\paragraph{Comparison among IPW estimators:} We can observe that the asymptotic MSE of $\hat R_{ \mathrm{IPWCS}}$\footnote{In this paragraph, we omit $\pi^\mathrm{e}$ from the estimator $\hat R(\pi^\mathrm{e})$.} is smaller than that of $\hat R_{\mathrm{IPWCSB}}$. This result looks unusual since $\hat R_{\mathrm{IPWCSB}}$ uses more knowledge than $\hat R_{ \mathrm{IPWCS}}$. The intuitive reason for this fact is that $\hat R_{ \mathrm{IPWCS}}$ is considered to be using control variate. The same paradox is known in other works of causal inference RobinsJM1992Eeeb. Note that this fact does not imply $\hat R_{ \mathrm{IPWCS}}$ is superior to $\hat R_{\mathrm{IPWCSB}}$ since more smoothness conditions are required in $\hat R_{\mathrm{IPWCS}}$, and this can be violated in practice RobinsJamesM.1997TACO.
In this section, we propose OPL estimators based on the doubly robust estimator $\hat R_{\mathrm{DRCS}}(\pi^\mathrm{e})$ to estimate the optimal policy that maximizes the expected reward over the evaluation data. The optimal policy $\pi^*$ is defined as $ \pi^* = \operatorname*{arg\,max}_{\pi\in \Pi} R(\pi)$, where recall that $\Pi$ is a policy class. By applying each OPE estimator, we can define the following estimators:
To obtain a theoretical implication, for simplicity, we assume $\mathcal{A}$ is a finite state space and the policy class $\Pi$ is deterministic. Then, for the $\epsilon$-Hamming covering number $N_{H}(\epsilon,\Pi)$ and its entropy integral $\kappa(\Pi):=\int_{0}^{\infty} \sqrt{\log N_{H}(\epsilon^2,\Pi)}\mathrm{d}\epsilon$ ZhouZhengyuan2018OMPL, the regret bound of $\hat \pi_{\mathrm{DRCS}}$ is obtained.
In comparison to the standard regret results in swaminathan15a,KitagawaToru2018WSBT, we do not assume we know the true behavior policy. Because $\hat{R}_{\mathrm{DRCS}}(\pi)$ has the double robust structure, we can obtain the regret bound under weak nonparametric rate conditions without assuming the behavior policy is known. Besides, this theorem shows that the variance term is related to attain the low regret. This is achieved by using the efficient estimator $\hat{R}_{\mathrm{DRCS}}(\pi)$.
In this section, we demonstrate the effectiveness of the proposed estimators using data obtained with bandit feedback. Following dudik2011doubly and Chow2018, we evaluate the proposed estimators using the standard classification datasets from the UCI repository by transforming the classification data into contextual bandit data. From the UCI repository, we use the SatImage, Vehicle, and PenDigits datasets \footnote{\url{https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/multiclass.html}}. For each dataset, we randomly choose $800$ samples (the results with other sample sizes are reported in Appendix (ref)). First, we classify data into historical and evaluation data with probability defined as $\textstyle p(hist=+1|X_i) = \frac{C_{\mathrm{prob}}}{1+\exp(-\tau(X_i)+0.1\varepsilon)}$, where $hist=+1$ denotes that the sample $i$ belongs to the historical data, $C_{\mathrm{prob}}$ is a constant, $\varepsilon$ is a random variable that follows the standard normal distribution, $X_{k,i}$ is the $k$-th element of the vector $X_i$, and $\tau(X_i) = \sum^5_{j=1}X_{j,i}$. By adjusting $C_{\mathrm{prob}}$, we classify $70\%$ samples as the historical data and $30\%$ samples as the evaluation data. Thus, we generate the historical and evaluation data under a covariate shift. Then, we make a deterministic policy $\pi_d$ by training a logistic regression classifier on the historical data. We construct three different behavior policies as mixtures of $\pi^d$ and the uniform random policy $\pi^u$ by changing a mixture parameter $\alpha$, i.e., $\pi^\mathrm{b} = \alpha\pi^d+(1-\alpha)\pi^u$. The candidates of the mixture parameter $\alpha$ are $\{0.7, 0.4, 0.0\}$ as Kallus2019IntrinsicallyES. In Section (ref), we show the experimental results of OPE. In Section (ref), we show the experimental results of OPL. In both sections, the historical $p(x)$ and evaluation distributions $q(x)$ are unknown, and the behavior policy $\pi^\mathrm{b}$ is also unknown. More details, such as the description of the data and choice of hyperparameters, are in Appendix (ref).
For the experiments, we use an evaluation policy $\pi^\mathrm{e}$ defined as $0.9\pi^d+0.1\pi^u$. Here, we compare the MSEs of five estimators, DRCS, DM, DM-R, IPWCS, and IPWCS-R. DRCS is the proposed estimator $\hat{R}_{\mathrm{DRCS}}$ where we use kernel Ridge regression for estimating $f(a,x)$ and $w(a, x)$ and use KuLISF kanamori2012kulsif for $r(x)$. For this estimator, we use $2$-fold cross-fitting. DM denotes the direct method estimator $\hat R_{\mathrm{DM}}(\pi^\mathrm{e})$ with $f(a,x)$ estimated by Nadaraya-Watson regression defined in Section (ref). DM-R is the same estimator, but we use the kernel Ridge regression for $f(a,x)$. IPWCS is the IPW estimator $\hat R_{\mathrm{IPWCS}}(\pi^\mathrm{e})$, where we use kernel regression defined in Section (ref) to estimate $r(x)$ and $w(a, x)$. IPWCS-R is the same estimator, but we use KuLISF to estimate $r(x)$. Note that nuisance estimators in DM-R and IPWCS-R do not satisfy the Donsker condition.
The resulting MSE and the standard deviation (SD) over $20$ replications of each experiment are shown in Tables (ref), where we highlight in bold the best two estimators in each case. DRCS generally outperforms the other estimators. This result shows that the efficiency and double robustness of DRCS translate to satisfactory performance. IPW based estimators have unstable performance. While IPWCS-R shows the best performance in SatImage dataset, it has severely low performance for Vehicle dataset. IPWCS has a poor performance in both datasets. The larger instability of IPWCS-R is mainly due to the nuisance estimators in IPWCS-R do not satisfy the Donsker condition. When the behavior policy is similar to the evaluation policy, the DM estimators (DM and DM-R) also work well.
In the experiments of OPL, we compare the performances of three estimators for the optimal policy maximizing expected reward over the evaluation data: $\hat \pi_{\mathrm{DRCS}}$ with $f(a,x)$ and $w(a, x)$ estimated by kernel Ridge regression and $r(x)$ estimated by KuLISF (DRCS), $\hat \pi_{\mathrm{DM}}$ with $f(a, x)$ estimated by kernel regression defined in Section (ref) (DM), and $\hat \pi_{\mathrm{IPWCS}}$ with $r(x)$ and $w(a, x)$ estimated by kernel regression defined in Section (ref) (IPWCS). For the policy class $\Pi$, we use a model with the Gaussian kernel defined in (ref). For DRCS, we use $2$-fold cross-fitting and add a regularization term.
We conducted $10$ trials for each experiment. The resulting expected reward over the evaluation data (RWD) and the standard deviation (SD) of estimators for OPL are shown in Table (ref), where we highlight in bold the best estimator in each case. For all cases, the estimator $\hat \pi_{\mathrm{DRCS}}$ outperforms the other estimators. We can find that, when an estimator of OPE shows high performance, a corresponding estimator of OPL also shows high performance. The results show that the statistical efficiency of the OPE estimator translates into better regret performance as in Theorem (ref).
We calculated the efficiency bound for OPE under a covariate shift and proposed OPE and OPL methods for the situation. Especially, DRCS has doubly robustness and achieves the efficiency bound under weak nonparametric rate conditions.
The proposed OPE estimator is the efficient estimator under the simplest setting in a transportability problem Bareinboim2016. Complete identification algorithms have been developed in a more complex setting NIPS2014_5536; however, statistical efficient estimation methods have not been considered. Our work opens the door to this new direction. How to conduct efficient estimation in such a complex setting is an interesting future work.
Because the policies in sequential decision-making problems are critical in various real-world applications, the OPE methods are employed to evaluate the new policy and reduce the risk of deploying a poor policy. We focus on the OPE under a covariate shift a historical and evaluation data, which has many practical applications. For example, in the advertising applications, we usually deliver ads only in the particular region as the test-marketing at the beginning, then expand to other regions that have different feature distribution. Thus we face the covariate shift in the evaluation and training a new policy for the new region.
Though its practical importance, the OPE methods under the covariate shift have not been researched well, and people apply standard OPE methods to cases under the covariate shift. As we explained, the standard methods are not robust against the covariate shift. Among the standard methods, the IPW estimator is not consistent, and the DM and DR estimator has consistency when the model of conditional outcome is correct. In particular, under a covariate shift, the standard DR estimator is not doubly robust; namely, it is consistent only when the model of conditional outcome is correct. Thus, the standard estimator has a potential risk to mislead the user's decision making and might cause serious problems in the industry because many decision makings such as ad-optimization rely on the result of the evaluation. On the other hand, the proposed estimator has a doubly robust property. This robustness helps to avoid such potential risk of incorrect decision making.