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.
49,538 characters
Off-Policy Evaluation and Learning for External Validity under a Covariate Shift
\maketitle
\begin{abstract}
We consider evaluating and training a new policy for the evaluation data by using the historical data obtained from a different policy. The goal of \emph{off-policy evaluation} (OPE) is to estimate the expected reward of a new policy over the evaluation data, and that of \emph{off-policy learning} (OPL) is to find a new policy that maximizes the expected reward over the evaluation data. Although the standard OPE and OPL assume the same distribution of covariate between the historical and evaluation data, a covariate shift often exists, i.e., the distribution of the covariate of the historical data is different from that of the evaluation data. In this paper, we derive the efficiency bound of OPE under a covariate shift. Then, we propose doubly robust and efficient estimators for OPE and OPL under a covariate shift by using a nonparametric estimator of the density ratio between the historical and evaluation data distributions. We also discuss other possible estimators and compare their theoretical properties. Finally, we confirm the effectiveness of the proposed estimators through experiments.
\end{abstract}
\section{Introduction}
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 \citep{kdd2009_ads, www2010_cb, AtheySusan2017EPL}. To accomplish this, we use \emph{off-policy evaluation} (OPE) and \emph{off-policy learning} (OPL). The goal of OPE is to evaluate a new policy by estimating the expected reward of the new policy \citep{dudik2011doubly,wang2017optimal,narita2019counterfactual,pmlr-v97-bibaut19a,Kallus2019IntrinsicallyES,Oberst2019}. In contrast, OPL aims to find a new policy that maximizes the expected reward \citep{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 \citep{ColeStephenR.2010GEFR}. This problem is known as a lack of \emph{external validity}
\citep{PearlJudea2015EVFD}. These situations where historical and evaluation data follow different distributions are also known as \emph{covariate shifts} \citep{shimodaira2000improving,NIPS2007_3248}. This situation is illustrated in Figure~\ref{fig:covariate_shift}.
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{rem:standard}. 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 \citep{shimodaira2000improving,Reddi2015}.
\paragraph{Contributions:} This paper has four main contributions. First, we derive an efficiency bound of OPE under the covariate shift (Section~\ref{sec:semi_lb}). Second, in Section~\ref{sec:pe_csa},
we propose estimators constructed by estimators of the density ratio, behavior policy, and conditional expected reward. Especially, we employ nonparametric density ratio estimation from \citet{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{sec:pe_csa}). Third, we propose other possible estimators for our problem setting and compare them (Section~\ref{sec:other_candidates}). Fourth, an algorithm of OPL is proposed based on efficient estimators (Section~\ref{sec:opl}). All proofs are shown in Appendix~\ref{sec:proof}.
\begin{wrapfigure}{r}{0.5\textwidth}
\begin{minipage}{.44\linewidth}
\scalebox{0.8}{\begin{tikzpicture}[
>=latex',node distance=2cm, minimum height=0.75cm, minimum width=0.75cm,
state/.style={draw, shape=circle, draw=mygreen, fill=mygreen!10, line width=0.5pt},
action/.style={draw, shape=rectangle, draw=red, fill=red!10, line width=0.5pt},
reward/.style={draw, shape=rectangle, draw=blue, fill=blue!10, line width=0.5pt}
]
\node[state] (S0) at (0,0) {$X \sim p(x)$};
\node[action,right of=S0] (A0) {$A$};
\node[reward,below of=A0] (R0) {$Y$};
\draw[->] (S0) -- (A0) node[pos=.45,above] {$\pi^\mathrm{b}$};
\draw[->] (S0) -- (R0);
\draw[->] (A0) -- (R0);
\end{tikzpicture}}
\caption*{Historical data}
\label{fig:sub-first}
\end{minipage}
\begin{minipage}{.47\linewidth}
\scalebox{0.8}{\begin{tikzpicture}[
>=latex',node distance=2cm, minimum height=0.75cm, minimum width=0.75cm,
state/.style={draw, shape=circle, draw=green, fill=green!10, line width=0.5pt},
action/.style={draw, shape=rectangle, draw=gray, fill=gray!10, line width=0.5pt},
reward/.style={draw, shape=rectangle, draw=gray, fill=gray!10, line width=0.5pt}
]
\node[state] (S0) at (0,0) {$X\sim q(x)$};
\node[action,right of=S0] (A0) {$A$};
\node[reward,below of=A0] (R0) {$Y$};
\draw[->] (S0) -- (A0) node[pos=.5,above] {$\pi^\mathrm{e}$};
\draw[->] (S0) -- (R0);
\draw[->] (A0) -- (R0);
\end{tikzpicture}}
\caption*{Evaluation data}
\label{fig:sub-first2}
\end{minipage}
\caption{OPE under a covariate shift. Covariate, action, reward are denoted by $X,A,Y$. Evaluation and behavior policies are denoted by $\pi^\mathrm{e},\pi^\mathrm{b}$. Here, $p(x)\neq q(x)$, and the density ratio $q(x)/p(x)$ is unknown. The density $p(y\mid a,x)$ is the same in historical and evaluation data. For the evaluation data, $A$ and $Y$ are not observed.}
\label{fig:covariate_shift}
\vspace{-1cm}
\end{wrapfigure}
\paragraph{Related work:}
The difference between distributions of covariates conditioned on a chosen action is also called a covariate shift \citep{pmlr-v28-zhang13d,pmlr-v48-johansson16}. A covariate shift in this paper refers to the different distributions of covariates between historical and evaluation data. \citet{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 \citep{PearlJ2011ToCa,PearlJudea2015EVFD}.
This paper focuses on statistical inference and learning instead of an identification strategy.
\section{Problem Formulation}
\label{sec:prob_for}
In this section, we introduce our problem setting and review existing literature.
\subsection{Data-Generating Process with Evaluation Data}
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 \emph{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 \emph{historical} and \emph{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 \emph{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:
\begin{align*}\textstyle
&\mathcal{D}^{\mathrm{hst}}=\{(X_i, A_i, Y_i)\}^{n^{\mathrm{hst}}}_{i=1}\sim p(x)\pi^{\mathrm{b}}(a \mid x)p(y \mid x,a),\ \ \ \mathcal{D}^{\mathrm{evl}}=\{Z_i\}^{n^{\mathrm{evl}}}_{i=1}\sim q(z),
\end{align*}
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 \emph{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{sec:notation}.
\begin{remark}
Although we do not explicitly use counter-factual notation \citep{rubin87}, if we assume the usual conditions, our results immediately apply (Appendix~\ref{sec:idenfication}).
\end{remark}
\subsection{Off-Policy Evaluation and Learning}
\label{sec:opeopl}
We are interested in estimating the expected reward of an \emph{evaluation policy} $\pi^{\mathrm{e}}(a \mid x)$, which is pre-specified for the evaluation data. Here, we assume a \emph{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:
\begin{align}\textstyle
\label{def:policy_value}
R(\pi^\mathrm{e}) := \mathbb{E}_{q(z)\pi^\mathrm{e}(a \mid z)p(y \mid a,z)}\left[y\right].
\end{align}
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 \emph{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$.
\begin{assumption}
\label{asm:global}
$0\leq r(x) \leq C_1,\,0\leq w(a,x)\leq C_2,\,0\leq Y_i \leq R_{\max}$.
\end{assumption}
\begin{assumption}
\label{asm:global2}
$0\leq \hat r(x) \leq C_1,\,0\leq \hat w(a,x)\leq C_2,\,0\leq \hat f(a,x) \leq R_{\max}$.
\end{assumption}
\subsection{Preliminaries}
\label{sec:pre}
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{def:policy_value}). The first estimator is an inverse probability weighting (IPW) estimator given by $\mathbb{E}_{n^{\mathrm{hst}}}[\hat w(A,X)Y]$ \citep{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)]$ \citep{HahnJinyong1998OtRo}, which is weak against model misspecification for $f(a,x)$. The third estimator is a doubly robust estimator \citep{robins94} defined as
\begin{align}\textstyle
\label{eq:doubl_conventional}
\mathbb{E}_{n^{\mathrm{hst}}}[\hat w(A,X)\{Y-\hat f(A,X)\}+\mathbb{E}_{\pi^\mathrm{e}(a\mid X)}[\hat f(a,X) \mid X]].
\end{align}
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 \citep[Theorem 25.20]{VaartA.W.vander1998As} \footnote{Formally, regular estimators means estimators whose limiting distribution is insensitive to local changes to the DGP. Refer to \citet[Chapter 7]{VaartA.W.vander1998As} }. This efficiency bound is
\begin{align}\textstyle
\label{eq:bound}
\mathbb{E}[w^2(A,X)\mathrm{var}[Y\mid A,X]]+\mathrm{var}[v(X)],
\end{align}
where $v(x)=\mathbb{E}_{\pi^\mathrm{e}(a\mid x)}[f(a,x)\mid x]$ \citep{narita2019counterfactual}. Such estimator is called an \emph{efficient estimator}. These estimators are also used for OPL \citep{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 \emph{Least-Squares Importance Fitting} (LSIF), which uses the squared loss to fit the density-ratio function \citep{kanamori2012kulsif}. We show details in Appendix~\ref{appdx:uLSIF}.
\remark[Difference from standard OPE problems] \label{rem:standard}
Our current problem, i.e., policy evaluation \emph{under a shift in domain and policy}, differs from a standard policy evaluation problem \emph{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 \citet{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 \emph{mixture distribution} \citep{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 \citep{QinJing1998IfCa}.
\section{Efficiency Bound under a Covariate Shift}
\label{sec:semi_lb}
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 \citep{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{sec:semi_ld}.
Here, we show the efficiency bound of OPE under a covariate shift.
\begin{theorem}
\label{thm:efficiency}
The efficiency bound of $R(\pi^\mathrm{e})$ under fully nonparametric models is
\begin{align}
\label{eq:bound2}
\Upsilon(\pi^\mathrm{e})=\rho^{-1}\mathbb{E}[r^2(X)w^2(A,X)\mathrm{var}[Y\mid A,X]]+(1-\rho)^{-1}\mathrm{var}[v(Z)],
\end{align}
where $v(z)=\mathbb{E}_{\pi^\mathrm{e}(a\mid z)}[f(a,z)\mid z]$. The efficiency bound under a nonparametric model with fixed $p(x)$ and $\pi^\mathrm{b}(a \mid x)$ is the same.
\end{theorem}
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{eq:bound}).
This is because the target functional does not include these two densities.
Second, the efficiency bound under a covariate shift (\ref{eq:bound2}) reduces to the bound without a covariate shift (\ref{eq:bound}) in a special case, $r(x)=1$ and $\rho=0.5$.
Then, we can see (\ref{eq:bound2})$=2\times $(\ref{eq:bound}). The factor $2$ originates from the scaling of asymptotic MSE. Third, we need to calculate the \emph{efficient influence function}, which is a key function to derive the efficiency bound. This function is useful to construct the efficient estimator.
\section{OPE under a Covariate Shift}
\label{sec:pe_csa}
For OPE under a covariate shift, we propose an estimator constructed from the following basic form:
\begin{align}\textstyle
\label{eq:double}
\mathbb{E}_{n^{\mathrm{hst}}}[\hat r(X)\hat w(A,X)\{Y-\hat f(A,X)\}]+\mathbb{E}_{n^{\mathrm{evl}}}[\hat v(Z)],
\end{align}
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{eq:doubl_conventional}), 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{eq:double}) is a consistent estimator for $R(\pi^\mathrm{e})$ since
\begin{align*}\textstyle
&\mathbb{E}_{n^{\mathrm{hst}}}[r(X)w(A,X)Y]+\mathbb{E}_{n^{\mathrm{evl}}}[\mathbb{E}_{\pi^\mathrm{e}(a \mid Z)}[f^{\dagger}(a,Z)\mid Z]]-\mathbb{E}_{n^{\mathrm{hst}}}[r(X)w(A,X)f^{\dagger}(A,X)]\\
&\approx \mathbb{E}_{n^{\mathrm{hst}}}[r(X)w(A,X)Y]+0
\approx R(\pi^\mathrm{e}).
\end{align*}
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{eq:double}) is a consistent estimator for $R(\pi^\mathrm{e})$ since
\begin{align*}\textstyle
&\mathbb{E}_{n^{\mathrm{hst}}}[r^{\dagger}(X)w^{\dagger}(a,x)\{Y-f(A,X) \}]+\mathbb{E}_{\mathrm{n^{evl}}}[\mathbb{E}_{\pi^\mathrm{e}(a \mid Z)}[f(a,Z)\mid Z]]\\
&\approx \mathbb{E}_{n^{\mathrm{evl}}}[\mathbb{E}_{\pi^\mathrm{e}(a \mid Z)}[f(a,Z)\mid Z]]+0
\approx R(\pi^\mathrm{e}).
\end{align*}
The formal result is given later in Theorem~\ref{thm:model}.
\begin{algorithm}[tb]
\caption{\small{Doubly Robust Estimator under a Covariate Shift}}
\label{alg:dml}
\begin{algorithmic}
\STATE \textbf{Input}: The evaluation policy $\pi^\mathrm{e}$.
\STATE Take a $\xi$-fold random partition $(I_k)^{\xi}_{k=1}$ of observation indices $[n^{\mathrm{hst}}] = \{1,\dots,n^{\mathrm{hst}}\}$ such that the size of each fold $I_k$ is $n^{\mathrm{hst}}_k=n^{\mathrm{hst}}/\xi$.
\STATE Take a $\xi$-fold random partition $(J_k)^{\xi}_{k=1}$ of observation indices $[n^{\mathrm{evl}}] = \{1,\dots,n^{\mathrm{evl}}\}$ such that the size of each fold $J_k$ is $n^{\mathrm{evl}}_k=n^{\mathrm{evl}}/\xi$.
\STATE For each $k\in[\xi]=\{1,\dots,\xi\}$, define $I^c_k:=\{1,\dots,n^{\mathrm{hst}}\}\setminus I_k$ and $J^c_k:=\{1,\dots,n^{\mathrm{evl}}\}\setminus J_k$.
\STATE Define $(\mathcal{S}_k)^{\xi}_{k=1}$ with $\mathcal{S}_k = \{\{(X_i, A_i, Y_i)\}_{i\in I^c_k}, \{Z_j\}_{j\in J^c_k}\}$.
\FOR{$k\in[\xi]$}
\STATE Construct estimators $\hat w_k(a, x)$, $\hat r_k(x)$, and $\hat f_k(a,x)$ using $\mathcal{S}_k$.
\STATE Construct an estimator $\hat{R}_k$ defined as (\ref{eq:case2}).
\ENDFOR
\STATE Construct an estimator $\hat R$ of $R$ by taking the average of $\hat{R}_k$ for $k\in[\xi]$, i.e.,
$\hat R = \frac{1}{\xi}\sum^{\xi}_{k=1}\hat{R}_k$.
\end{algorithmic}
\end{algorithm}
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 \citep{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{sec:pre}. Although
such complex estimators approximate the true values well, it is pointed out that such estimators often violate the Donsker condition \citep{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 \citep[Chapter 19]{VaartA.W.vander1998As}.}, which is required to obtain the asymptotic distribution of an estimator of interest, such as (\ref{eq:double}).
For deriving the asymptotic distributions of an estimator of $R(\pi^\mathrm{e})$ using estimators without the Donsker condition, we apply cross-fitting \citep{klaassen1987,ZhengWenjing2011CTME,ChernozhukovVictor2018Dmlf} based on (\ref{eq:double}).
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
\begin{align}\textstyle
\label{eq:case2}
\hat R_k = &{\mathbb{E}}_{n^\mathrm{hst}_{k}}[\hat r^{(k)}(X)\hat w^{(k)}(A,X)\{Y-\hat f^{(k)}(A,X) \}]+{\mathbb{E}}_{n^\mathrm{evl}_{k}}[\mathbb{E}_{\pi^\mathrm{e}}[\hat f^{(k)}(a,Z)|Z]],
\end{align}
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 \emph{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{alg:dml}.
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.
\begin{theorem}[Efficiency]
\label{thm:main2}
For $k\in \{1,\cdots,\xi\}$, assume $\alpha\beta=\mathrm{o}_{p}(n^{-1/2}),\alpha=\mathrm{o}_{p}(1),\beta=\mathrm{o}_{p}(1)$ where $\|\hat r^{(k)}(X)\hat w^{(k)}(A,X)-r(X)w(A,X)\|_2=\alpha,\|\hat f^{(k)}(A,X)-f(A,X)\|_2=\beta$. Then, $\sqrt{n}(\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})-R(\pi^\mathrm{e}))\stackrel{d}{\rightarrow}\mathcal{N}(0,\Upsilon(\pi^\mathrm{e}))$, where $\Upsilon(\pi^\mathrm{e})$ is the efficiency bound in Theorem \ref{thm:efficiency}.
\end{theorem}
Importantly, the Donsker condition is \emph{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 \citep{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.
\begin{lemma}
\label{lem:den}
Assume $\|\hat r(X)-r(X)\|_2 =\mathrm{o}_{p}(n^{-p})$ and $\|\hat w(A,X)-w(A,X)\|_2 = \mathrm{o}_{p}(n^{-p})$. Then, $\|\hat r(X)\hat w(A,X)-r(X)w(A,X)\|_2=\mathrm{o}_{p}(n^{-p})$.
\end{lemma}
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.
\begin{theorem}[Double robustness]
\label{thm:model}
For $k\in \{1,\cdots,\xi\}$, assume $\exists\,f^{\dagger},r^{\dagger},w^{\dagger}$, $\|\hat f^{(k)}(A,X)-f^{\dagger}(A,X)\|_2 =\mathrm{o}_{p}(1),\ \ \ \|\hat r^{(k)}(X)\hat w^{(k)}(A,X)-r^{\dagger}(X)w^{\dagger}(A,X)\|_2 =\mathrm{o}_{p}(1).$ If $r^{\dagger}(x)w^{\dagger}(a,x)=r(x)w(a,x)$ or $q^{\dagger}(a,x)=q(a,x)$ holds, the estimator $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$ is consistent.
\end{theorem}
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.
\begin{remark}[OPE with Known Distribution of Evaluation Data]
As a special case of OPE under a covariate shift, we consider a case where $q(x)$ is known. This case can be regarded as a standard OPE situation by regarding $p(x)\pi^\mathrm{e}(a\mid x)$ as the behavior policy, the evaluation policy as $q(x)\pi^\mathrm{e}(a\mid x)$, and $(A,X)$ as the action. The details of this setting is shown in Appendix~\ref{sec:known}
\end{remark}
\begin{remark}[Relation with \citet{PearlJudea2015EVFD}]
A transport formula \citep[(3.1)]{PearlJudea2015EVFD} essentially leads to the DM estimator $\mathbb{E}_{n^{\mathrm{evl}}}[\hat v(Z)]$. Though they propose a general identification strategy, they do not discuss how to conduct efficient estimation given finite samples.
\end{remark}
\begin{remark}[Construction of $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$] We construct $\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$ so that it has a doubly robust structure. The construction is also motivated by the efficient influence function. More specifically, this estimator is introduced by plugging the nuisance estimates into the efficient influence function.
\end{remark}
\section{Other Candidates of Estimators}
\label{sec:other_candidates}
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 \citep{Nada:1964,Wats:1964}. We show regularity conditions and formal results of Theorems~\ref{thm:ipw2}--\ref{thm:dm} in \cref{sec:proof}.
\subsection{IPW Estimators and DM Estimator}
We consider IPW and DM type estimators under a covariate shift for \emph{each case} where we have an oracle of $\pi^\mathrm{b}(a\mid x)$ and we do not have any oracles of nuisance functions, \emph{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)$:
\begin{align}\textstyle
\label{eq:kernel}
\hat q_h(x)=\frac{1}{n^{\mathrm{evl}}}\sum_{i=1}^{n^{\mathrm{evl}}}h^{-d}K\left(\frac{Z_i-x}{h^d}\right),\, \hat p_h(x)=\frac{1}{n^{\mathrm{hst}}}\sum_{i=1}^{n^{\mathrm{hst}}}h^{-d}K\left(\frac{X_i-x}{h^d}\right),
\end{align}
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.
\begin{theorem}[Informal]
\label{thm:ipw2}
When $\hat q(x)=\hat q_h(x),\,\hat p(x)=\hat p_h(x)$, the asymptotic MSE of $\hat R_{\mathrm{IPWCSB}}(\pi^\mathrm{e})$ is $\rho^{-1}\mathrm{var}[r(X)\{w(A,X)Y-v(X)\}]+(1-\rho)^{-1}\mathrm{var}[v(Z)]$.
\end{theorem}
\paragraph{Fully nonparametric IPW estimator:} Next, \emph{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.
\begin{theorem}[Informal]
\label{thm:ipw3}
When $\hat q(x)=\hat q_h(x),\,\hat p(x)=\hat p_h(x)$ and $\hat \pi^b(a\mid x)=\hat{\pi}^{b}_h(a \mid x)$, where $\hat \pi^\mathrm{b}_h(a \mid x)$ is a kernel estimator based on $\mathcal{D}^{\mathrm{hst}}$, the asymptotic MSE of $\hat R_{\mathrm{IPWCS}}(\pi^\mathrm{e})$ is $\Upsilon(\pi^\mathrm{e})$.
\end{theorem}
\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.
\begin{theorem}[Informal]
\label{thm:dm}
When $\hat f_h(a,x)$ is a kernel estimator based on $\mathcal{D}^{\mathrm{hst}}$, the asymptotic MSE of $\hat R_{\mathrm{DM}}(\pi^\mathrm{e})$ is $\Upsilon(\pi^\mathrm{e})$.
\end{theorem}
\begin{table*}[!]
\centering
\caption{Comparison of estimators.
Parentheses mean that efficiency is ensured when using specific estimators for nuisances such as kernel estimators. Non-Donsker means whether any non-Donsker type complex estimators can be allowed to plug-in with a valid theoretical guarantee. All of the estimators here do not require any parametric model assumptions. }
\scalebox{0.80}[0.80]{
\begin{tabular}{c|ccccc } \toprule
Estimator & Efficiency & Double Robustness & Nuisance Functions& Without Oracle of $\pi^\mathrm{b}(x)$ & Non-Donsker \\
\hline
$\hat R_{\mathrm{IPWCSB}}(\pi^\mathrm{e})$ & & & $r$ & \\
$\hat R_{\mathrm{IPWCS}}(\pi^\mathrm{e})$ & ( \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; ) & & $r,w$ & \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; & \\
$\hat R_{\mathrm{DM}}(\pi^\mathrm{e})$ & ( \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; ) & & $f$ & \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; & \\
$\hat{R}_{\mathrm{DRCS}}(\pi^\mathrm{e})$ & \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; & \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; & $r,w,f$ & \tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; &\tikz\fill[scale=0.4](0,.35) -- (.25,0) -- (1,.7) -- (.25,.15) -- cycle; \\ \bottomrule
\end{tabular}
}
\label{tab:comparison}
\end{table*}
\subsection{Comparison of Estimators}
We compare the estimators discussed so far.
This is also summarized in Table \ref{tab:comparison}. 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})$ \emph{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 \citep{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 \citep{RobinsJamesM.1997TACO}.
\section{OPL under a Covariate Shift}
\label{sec:opl}
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:
\begin{align*}\textstyle
&\hat \pi_{\mathrm{DRCS}} =\operatorname*{arg\,max}_{\pi\in \Pi} \hat{R}_{\mathrm{DRCS}}(\pi),\ \ \ \hat \pi_{\mathrm{DM}} =\operatorname*{arg\,max}_{\pi\in \Pi} \hat{R}_{\mathrm{
DM}}(\pi),\ \ \ \hat \pi_{\mathrm{IPWCS}} =\operatorname*{arg\,max}_{\pi\in \Pi} \hat{R}_{\mathrm{\mathrm{IPWCS}}}(\pi).
\end{align*}
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$ \citep{ZhouZhengyuan2018OMPL}, the regret bound of $\hat \pi_{\mathrm{DRCS}}$ is obtained.
\begin{theorem}[Regret bound of $ \hat \pi_{\mathrm{DRCS}} $]
\label{thm:regret}
Assume that for any $0< \epsilon < 1$, there exists $\omega$ such that $N_{H}(\epsilon,\Pi)=\mathcal{O}( \exp(1/\epsilon)^{\omega})$,\,$0<\omega < 0.5$. Also suppose that for $k\in \{1,\cdots,\xi\}$, $\|\hat r^{(k)}(X)-r(X)\|_2=\mathrm{o}_{p}(n^{-1/4})$, $\|1/\hat{\pi}^{(k)\mathrm{b}}(A,X)-1/{\pi}^{\mathrm{b}}(A,X)\|_2=\mathrm{o}_{p}(n^{-1/4})$, and $\|\hat f^{(k)}(A,X)-f(A,X)\|_2=\mathrm{o}_{p}(n^{-1/4})$. Then, by defining $\Upsilon_{*} =\sup_{\pi \in \Pi}\Upsilon(\pi)$, there exists an integer $N_{\delta}$ such that with probability at least $1-2\delta$, for all $n\geq N_{\delta}$, $$\textstyle R(\pi^{*})-R(\hat \pi_{\mathrm{DRCS}})=\mathcal{O}((\kappa(\Pi)+\sqrt{\log(1/\delta)})\sqrt{\frac{\Upsilon_{*}}{n}}).$$
\end{theorem}
In comparison to the standard regret results in \citet{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)$.
\section{Experiments}
\label{sec:exp}
In this section, we demonstrate the effectiveness of the proposed estimators using data obtained with bandit feedback. Following \citet{dudik2011doubly} and \citet{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{appdx:details_exp}). 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 \citet{Kallus2019IntrinsicallyES}. In Section~\ref{subsec:exp_ope}, we show the experimental results of OPE. In Section~\ref{subsec:exp_opl}, 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{appdx:details_exp}.
\begin{table}[!htbp]
\caption{OPE results. The alphabets (a),(b),(c) refer to the cases where the behavior policies are (a) $0.7\pi^d+0.3\pi^u$, (b) $0.4\pi^d+0.6\pi^u$, (c) $0.0\pi^d+1.0\pi^u$, respectively. The notation -- means each value is larger than $1.0$. }
\begin{minipage}[t]{.49\textwidth}
\begin{center}
\caption*{OPE with SatImage dataset}
\label{tbl:table1}
\scalebox{0.66}[0.66]{
\begin{tabular}{p{2mm}|p{5mm}p{6mm}|p{4mm}p{4.3mm}|p{5mm}p{6mm}|p{5mm}p{6mm}|p{5mm}p{6mm}}
\hline
\multirow{2}{*}{} & \multicolumn{2}{c|}{DRCS} & \multicolumn{2}{c|}{IPWCS} & \multicolumn{2}{c|}{DM} & \multicolumn{2}{c|}{IPWCS-R} & \multicolumn{2}{c}{DM-R} \\
& MSE & SD & MSE & SD & MSE & SD & MSE & SD & MSE & SD \\
\hline
(a) & 0.107 & 0.032 & -- & -- & \textbf{0.042} & 0.043 & \textbf{0.045} & 0.049 & 0.073 & 0.023 \\
(b) & \textbf{0.096} & 0.025 & -- & -- & 0.134 & 0.052 & \textbf{0.093} & 0.069 & 0.177 & 0.033 \\
(c) & \textbf{0.154} & 0.051 & -- & -- & 0.336 & 0.079 & \textbf{0.022} & 0.026 & 0.372 & 0.050 \\
\hline
\end{tabular}
}
\end{center}
\end{minipage}
\begin{minipage}[t]{.49\textwidth}
\begin{center}
\caption*{OPE with Vehicle dataset}
\label{tbl:table2}
\scalebox{0.66}[0.66]{
\begin{tabular}{p{2mm}|p{5mm}p{6mm}|p{4mm}p{4.3mm}|p{5mm}p{6mm}|p{5mm}p{6mm}|p{5mm}p{6mm}}
\hline
\multirow{2}{*}{} & \multicolumn{2}{c|}{DRCS} & \multicolumn{2}{c|}{IPWCS} & \multicolumn{2}{c|}{DM} & \multicolumn{2}{c|}{IPWCS-R} & \multicolumn{2}{c}{DM-R} \\
& MSE & SD & MSE & SD & MSE & SD & MSE & SD & MSE & SD \\
\hline
(a) & \textbf{0.029} & 0.019 & -- & --& \textbf{0.038} & 0.035 & 0.568 & 0.319 & 0.040 & 0.014 \\
(b) & \textbf{0.019} & 0.024 & -- & -- & \textbf{0.095} & 0.062 & 0.576 & 0.357 & 0.089 & 0.019 \\
(c) & \textbf{0.037} & 0.030 & --& -- & 0.213 & 0.049 & 0.233 & 0.193 & \textbf{0.210} & 0.031 \\
\hline
\end{tabular}
}
\end{center}
\end{minipage}
\end{table}
\begin{table}[!htbp]
\caption{OPL results. The alphabets (a),(b), and (c) refer to the cases where the behavior policies are (a) $0.7\pi^d+0.3\pi^u$, (b) $0.4\pi^d+0.6\pi^u$, (c) $0.0\pi^d+1.0\pi^u$, respectively. }
\label{tbl:table4}
\begin{minipage}[t]{.49\textwidth}
\begin{center}
\caption*{OPL with SatImage dataset}
\scalebox{0.68}[0.68]{
\begin{tabular}{l|rr|rr|rr}
\hline
& \multicolumn{2}{c|}{DRCS} & \multicolumn{2}{c|}{IPWCS} & \multicolumn{2}{c}{DM} \\
& RWD & SD & RWD & SD & RWD & SD \\
\hline
(a) & \textbf{0.723} & 0.035 & 0.423 & 0.063 & 0.658 & 0.045 \\
(b) & \textbf{0.710} & 0.035 & 0.482 & 0.096 & 0.641 & 0.048 \\
(c) & \textbf{0.652} & 0.046 & 0.460 & 0.131 & 0.465 & 0.070 \\
\hline
\end{tabular}
}
\end{center}
\end{minipage}
\begin{minipage}[t]{.49\textwidth}
\begin{center}
\caption*{OPL with Vehicle dataset}
\scalebox{0.68}[0.68]{
\begin{tabular}{l|rr|rr|rr}
\hline
& \multicolumn{2}{c|}{DRCS} & \multicolumn{2}{c|}{IPWCS} & \multicolumn{2}{c}{DM} \\
& RWD & SD & RWD & SD & RWD & SD \\
\hline
(a) & \textbf{0.496} & 0.017 & 0.310 & 0.030 & 0.411 & 0.040 \\
(b) & \textbf{0.510} & 0.029 & 0.290 & 0.051 & 0.393 & 0.052 \\
(c) & \textbf{0.480} & 0.044 & 0.280 & 0.041 & 0.313 & 0.065 \\
\hline
\end{tabular}
}
\end{center}
\end{minipage}
\end{table}
\subsection{Experiments of Off-Policy Evaluation}
\label{subsec:exp_ope}
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 \citep{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{sec:other_candidates}. 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{sec:other_candidates} 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{tbl:table1}, 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.
\begin{remark}
For DRCS and IPWCS, we also conducted experiments when we use the self-normalization following \citet{Swaminathan2015b}. The details and results are shown in Appendix~\ref{appdx:self_dml}. We also investigate the performance with an additional dataset in \cref{appdx:details_exp}.
\end{remark}
\subsection{Experiments of Off-Policy Learning}
\label{subsec:exp_opl}
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{sec:other_candidates} (DM), and $\hat \pi_{\mathrm{IPWCS}}$ with $r(x)$ and $w(a, x)$ estimated by kernel regression defined in Section~\ref{sec:other_candidates} (IPWCS). For the policy class $\Pi$, we use a model with the Gaussian kernel defined in \cref{appdx:opl_alg}. 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{tbl:table4}, 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{thm:regret}.
\vspace{-4mm}
\section{Conclusion and Future Direction}
\vspace{-3mm}
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 \citep{Bareinboim2016}. Complete identification algorithms have been developed in a more complex setting \citep{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.
\section*{Broader Impact}
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 \emph{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.
\bibliographystyle{arxiv}
\bibliography{CS-OPE,pfi3}
\newpage