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.
52,178 characters · 17 sections · 30 citation commands
A Practical Guide of Off-Policy Evaluation for Bandit Problems
As an instance of sequential decision-making problems, the multi-armed bandit (MAB) problem has attracted significant attention in various applications, such as ad optimization narita2019counterfactual, personalized medicine ChowChang201112,Villar2018, and recommendation systems Li2010,Li2016. However, because we only observe an action chosen following a behavior policy, which yields sample selection bias in the observed dataset, it is not easy to evaluate a new policy (evaluation policy) from the log data. For solving this problem, off-policy evaluation (OPE) is proposed kdd2009_ads, Li2010, dudik2011doubly,Li2011,wang2017optimal,narita2019counterfactual,pmlr-v97-bibaut19a,Kallus2019IntrinsicallyES,Oberst2019.
As reviewed in this paper, OPE estimators require several conditions to achieve theoretical properties, such as unbiasedness, consistency, and asymptotic normality. For instance, we need to put an assumption such that an evaluation policy is independent of log data used for constructing the OPE because the correlation between the evaluation policy and an OPE estimator causes a biased result Li2011,kato_uehara_2020,kallus2020stochasticpolicy. However, although real-world applications often break the condition, existing studies did not pay much attention to which practical situation satisfies the condition.
In addition, we point out terminology problems in OPE. A confusing terminology may cause misuse of OPE methods. For example, narita2019counterfactual and saito2020large study methods for evaluating bandit policies, such as the Thompson sampling, but their experimental process has the potential to cause unexpected bias because the evaluation probability is not deterministic narita2019counterfactual and fail to reproduce trajectories of the bandit algorithms saito2020large. Although they propose OPE methods for bandit policy, their methods estimate a weighted average of expected reward over a fixed probability of choosing an action, not a data-dependent bandit policy; that is, the definition of evaluation policy differs between their theoretical results and experiments. Thus, the confusing use of terminologies potentially misleads the applications of OPE.
Five contributions are made: (i) summarizing the potential concern and limitations of OPE methods; (ii) organizing the OPE terminologies; (iii) categorizing situations in which OPE methods are applicable; (iv) showing some new results bridging existing studies and practical situations. This paper is organized as follows. In Section (ref) and (ref), we formulate our OPE problem setting and review OPE methods with the attention to the potential theoretical concerns. In Section (ref), based on cases of evaluation probabilities, we categorize the OPE methods. Built upon the categorization, we introduce a practical application of OPE in Section (ref) and show the experimental results in Section (ref).
In this section, we describe the problem setting of OPE.
Let $A_t$ be an action in $\mathcal{A}=\{1,2,\dots,K\}$, $X_t$ be the covariate observed by the decision maker when choosing an action, and $\mathcal{X}$ be the space of covariate. Let us denote a random variable of a reward at period $t$ as $Y_t=\sum^K_{a=1}\mathbbm{1}[A_t = a]Y_t(a)$, where $Y_t(a):\mathcal{A}\to\mathbb{R}$ is a potential outcome\footnote{We can express the reward without using the potential reward variable. See Appendix B of kato_uehara_2020}. This setting is also called bandit feedback. Suppose that we have access to a dataset $\mathcal{S}_T= \big\{(X_t, A_t, Y_t)\big\}^{T}_{t=1}$ with the following data-generating process (DGP):
where $p(x)$ denotes the density of the covariate $X_t$, $p_t(a\mid x)$ denotes the probability of choosing an action $a$ conditioned on a covariate $x$ at period $t$, and $p(y\mid a, x)$ denotes the density of a reward $Y_t$ conditioned on an action $a$ and covariate $x$. We assume that $p(x)$ and $p(y\mid a, x)$ are invariant across periods, but $p_t(a\mid x)$ can take different values across periods.
Let us call a function determines the probability $p_t(a\mid x)$ a behavior probability. For example, narita2019counterfactual uses a behavior probability defined as $\pi^\mathrm{b}_t:\mathcal{X}\to \Delta^K$, where $\Delta^K := \{(p_a) \in [0,1]^K\mid \sum^K_{a=1}p_a=1\}$. We also define a behavior policy as a system that determines the behavior probability. In MAB problems, the behavior policy can be considered as a function of the trajectory. In most existing studies, a behavior policy and probability are not distinguished, and both are called a behavior policy.
We consider estimating the value of an evaluation policy using samples obtained under the behavior policy. Let a policy generating a probability of choosing an action $\pi^\mathrm{e}:\mathcal{X}\to\Delta^K$ be an evaluation policy. Similar to the behavior probability, we also call $\pi^\mathrm{e}$ as the evaluation probability. In most existing studies, a behavior/evaluation policy and probability are not clearly distinguished, and both are called a behavior/evaluation policy. However, distinguishing them is critical, as mentioned; if an evaluation policy depends on a trajectory generated from the evaluation policy itself, we need to reproduce the trajectory for evaluating the evaluation policy. For example, MAB algorithms carefully select an arm in each period and balance the trade-off between exploration and exploitation using self-generated trajectories to update the parameter. However, in OPE, we have a trajectory generated from a behavior policy, which is usually different from that of the evaluation policy and cannot know the true real-time behavior of the evaluation policy. We discuss such terminology-related problems in Appendix (ref).
The goal of OPE for an evaluation policy generating an evaluation probability $\pi^{\mathrm{e}}(a \mid x)$ is to estimate the expected reward from the evaluation probability $\pi^{\mathrm{e}}(a \mid x)$ defined as $R(\pi^\mathrm{e}) := \mathbb{E}\left[\sum^K_{a=1}\pi^\mathrm{e}(a \mid x)Y_t(a)\right]$.
To identify the policy value $R(\pi^\mathrm{e})$, we assume overlaps of the distributions of policies and the boundedness of reward.
In addition to the above assumptions, we also assume that an evaluation probability $\pi^\mathrm{e}$ is deterministic Kallus2019IntrinsicallyES,kato_uehara_2020. For each situation, a deterministic evaluation probability has different meanings, such as a random variable independent from $\mathcal{S}_T$, random variable constructed converging a time-invariant function as $T\to\infty$, or not a random variable. Note that the deterministic evaluation probability does not mean that the evaluation probability $\pi^\mathrm{e}$ chooses a certain action with probability $1$. This assumption mainly implies that we cannot evaluate an evaluation probability constructed from samples correlated with the dataset $\mathcal{S}$. In Section (ref), we consider practical situations with deterministic evaluation policies.
Besides, let us also define the Average Treatment Effect (ATE) between actions $a$ and $a'$. Although breaking the definition of the evaluation probability, we can regard for all $ x\in \mathcal{X}$, $\pi^{\mathrm{\mathrm{e}, (1)}}(a\mid x)=1$ and $\pi^{\mathrm{\mathrm{e}, (2)}}(a'\mid x)=1$ as a deterministic evaluation probability in ATE estimation and apply existing OPE estimators to estimate the value. In this paper, when referring to OPE, we allow estimations of ATE to be contained in the target of OPE estimators.
{\bf Notations:} Let $\mathcal{S}_{t-1}\in\mathcal{M}_{t-1}$ be the history until $t-1$ period defined as $\mathcal{S}_{t-1}=\{X_{t-1}, A_{t-1}, Y_{t-1}, \ldots, X_{1}, A_1, Y_{1}\}$ with the space $\mathcal{M}_{t-1}$. Let us denote $\mathbb{E}[Y_t(a)\mid x]$ and $\mathrm{Var}(Y_t(a)\mid x)$ as $f^*(a, x)$ and $\nu^*(a, x)$, respectively. Let $\mathcal{F}$ be the classes of $f^*(a, x)$ and $\hat{f}_{t}(a, x\mid \mathcal{S}_{t-1})$ be an estimator of $f^*(a, x)$ constructed from $\mathcal{S}_{t-1}$. Let $\mathcal{N}(\mu, \mathrm{var})$ be the normal distribution with the mean $\mu$ and the variance $\mathrm{var}$. We often denote a behavior probability as $\pi^\mathrm{b}_t$ or $\pi^\mathrm{b}$, and an evaluation probability as $\pi^\mathrm{e}_t$ or $\pi^\mathrm{e}$. Additionally, let $\|\mu(X,A,Y)\|_2$ be $\mathbb{E}[\mu^2(X,A,Y)]^{1/2}$ for the function $\mu$.
We review three types of well-known estimators of $R(\pi^{\mathrm{e}})$. For simplicity, let us assume that the behavior probability $\pi^\mathrm{b}_t$ is known. In the case where the behavior probability $\pi^\mathrm{b}_t$ is unknown, we replace the behavior probability with its estimator. The first estimator is an inverse probability weighting (IPW) type estimator rubin87,hirano2003efficient,swaminathan15a given by $\frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)\Gamma^{\mathrm{IPW}}_t(a; \pi^\mathrm{b}_t)$, where
Even though this estimator is unbiased when the behavior probability is known, it suffers from high variance. The second estimator is a direct method (DM) type estimator $\frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)\Gamma^{\mathrm{DM}}_t(a; \hat{f})$, where
and $\hat{f}(a, X_t)$ is an estimator of $f^*(a, X_t)$ HahnJinyong1998OtRo. This estimator is known to be weak against model misspecification of $f^*(a, X_t)$. The third estimator is an augmented inverse probability (AIPW) type estimator $\frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_t, \hat{f})$, where
When replacing the behavior probability with its estimator, AIPW estimator is called doubly robust estimator robins94,ChernozhukovVictor2018Dmlf.
When theoretically evaluating OPE estimators, we often check the unbiasedness, consistency, asymptotic normality, and concentration inequality. For the above estimators, unbiasedness and/or consistency are satisfied in general. On the other hand, there are various methods for guaranteeing the asymptotic normality of the above estimator for specific choices of $\pi^\mathrm{b}$ and $\hat{f}$. For brevity, we explain the asymptotic distribution of the AIPW and Adaptive AIPW (A2IPW) Kato2020 estimators for the cases in which the behavior probability is fixed and updated through periods, respectively. First, we consider the case where $\forall t,\; \pi^\mathrm{b}_t(a\mid x)=\pi^\mathrm{b}(a\mid x)$ in the DGP ((ref)). In this case, by using some methods for deriving the asymptotic normality, such as double/debiased machine learning (DDM) proposed by ChernozhukovVictor2018Dmlf, we can derive the asymptotic distribution of AIPW type estimator. Let us define an AIPW estimator with an estimator $\hat{f}_T$ of $f^*$ as $\widehat{R}^{\mathrm{AIPW}}_T(\pi^\mathrm{e})=\frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a| X_t)\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_t, \hat{f}_T)$. Then, under some conditions, we can show that $\sqrt{T}\left(\widehat{R}^{\mathrm{AIPW}}_T(\pi^\mathrm{e}) - R(\pi^\mathrm{e})\right) \xrightarrow{\mathrm{d}}\mathcal{N}(0, \sigma^{2}_{\mathrm{AIPW}}(\pi^\mathrm{b}, \pi^\mathrm{e}))$, where $\sigma^{2}_{\mathrm{AIPW}}(\pi, \pi^\mathrm{e})= \mathbb{E}\Big[\sum^{K}_{a=1}\frac{\big(\pi^\mathrm{e}\big(a, X_t\big)\big)^2\nu^*\big(a, X_t\big)}{\pi^\mathrm{b}(k\mid X_t)}+ \Big(\sum^{K}_{k=1}\pi^\mathrm{e}(a, X_t)f^*(a, X_t) - R(\pi^\mathrm{e})\Big)^2\Big]$. Next, we consider the case where the behavior probability is time-dependent. When samples have dependency under a behavior probability $\pi^\mathrm{b}_t(a\mid x, \mathcal{S}_{t-1})$, one of useful OPE estimators is A2IPW estimator defined as $\widehat{R}^{\mathrm{A2IPW}}_T(\pi^\mathrm{e}) = \frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_t, \hat{f}_{t-1})$, where $\hat{f}_{t-1}$ is a step-wise consistent estimator of $f^*$ estimated only using samples $\mathcal{S}_{t-1}$. Then, for a converging behavior probability $\pi^\mathrm{b}_t$ such that $\pi^\mathrm{b}_t(a\mid x, \mathcal{S}_{t-1}) \xrightarrow{\mathrm{p}} \alpha(a\mid x)$ as $t\to \infty$, Kato2020 showed that, under some regularity conditions, $\sqrt{T}\left(\widehat{R}^{\mathrm{A2IPW}}_T(\pi^\mathrm{e})-R(\pi^\mathrm{e})\right)\xrightarrow{d}\mathcal{N}\left(0, \sigma^{2}_{\mathrm{A2IPW}}(\pi, \pi^\mathrm{e})\right)$, where $\sigma^{2}_{\mathrm{A2IPW}}(\pi, \pi^\mathrm{e})=\mathbb{E}\Big[\sum^{K}_{a=1}\frac{\big(\pi^\mathrm{e}\big(a, X_t\big)\big)^2\nu^*\big(a, X_t\big)}{\alpha(k\mid X_t)}+ \Big(\sum^{K}_{k=1}\pi^\mathrm{e}(a, X_t)f^*(a, X_t) - R(\pi^\mathrm{e})\Big)^2\Big]$. The detailed explanations are in Appendix (ref). As explained above, under certain conditions, it is known that the AIPW type estimators achieve the efficiency bound (a.k.a semiparametric lower bound), which is the lower bound of the asymptotic MSE of OPE, among regular $\sqrt{T}$-consistent estimators VaartA.W.vander1998As. Let us note that for the best regret order bandit algorithms, we cannot use them as the behavior policy of OPE because the asymptotic variance including $1/\pi^\mathrm{b}_t$ diverges. We discuss in Appendix (ref).
In this section, from the deterministic evaluation probability perspective, we categorize the situation where OPE is appropriate as follows: (a) OPE with a given fixed probability; (b) inter-temporal OPE (ITOPE); (c) sample splitting OPE (SSOPE); (d) on-policy off-policy evaluation (OPOPE). While an evaluation probability is given exogenously in case (a), it is constructed from samples in case (b)--(d). We illustrate the concepts of case (b)--(d) in Figure (ref).
When a fixed policy is given as the case (a), we can naively apply existing OPE methods. However, such a situation is not common in practice because we often construct an evaluation probability from samples. In such cases, we practically consider two cases, (b) ITOPE and (c) SSOPE, where we separate training and evaluation datasets for constructing and evaluating an evaluation probability, respectively. In ITOPE, we have a dataset with time series $\{-T',\dots-1,0,1,\dots, T\}$, where $T'\in\mathbb{N}$, and allow the behavior policy to be updated at period $t=1$ using samples obtained until that period. A defect of these approaches, we cannot use the whole dataset for constructing an evaluation probability. On the other hand, in the case (d) OPOPE, we can conduct OPE for a sequentially constructed evaluation probability owing to martingale property. In this case, although the whole dataset for constructing an evaluation probability is used for OPE, we only identify the average value of the sequence of policy value. We introduce the details as follows.
\paragraph{(a) OPE with a given probability:} In this case, the probability $\pi^\mathrm{e}$ is data-independent and given exogenously. We include ATE estimation in this situation.
\paragraph{(b) ITOPE:} In this case, we allow behavior and evaluation policies to be time-dependent. In ITOPE, for a time series $t=-T', \dots, -1, 0, 1, \dots, T$, we construct an evaluation probability using past samples obtained until $t=0$. Then, we estimate the policy value using samples from $t=1,2,\dots, T$, $\mathcal{S}$. For representing the dependency, let us denote an evaluation probability as $\pi^\mathrm{e}_{0:-T'}(a\mid x, \mathcal{S}_{0:-T'})$ and behavior probability as $\pi^\mathrm{b}_{0:-T'}(a\mid x, \mathcal{S}_{0:-T'})$, where $\mathcal{S}_{0:-T'}$ $ =\{X_{0}, A_{0}, Y_{0}, X_{-1}, A_{-1}, Y_{-1}, \ldots, X_{-T'}, A_{-T'}, Y_{-T'}\}$. In this case, we can estimate the policy value defined as $R'_{0:-T'}(\pi^\mathrm{e}) := \mathbb{E}\left[\sum^K_{a=1}\pi^\mathrm{e}(a \mid x, \mathcal{S}_{0:-T'})Y_t(a)\mid \mathcal{S}_{0:-T'}\right]$. This situation is similar to progressive validation blum1999beating. In this case, an AIPW type estimator $\widehat{R}^{\mathrm{AIPW}'}(\pi^\mathrm{e}_{0:-T'}) = \frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}_{0:-T'}(a\mid X_t, \mathcal{S}_{0:-T'})\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_{0:-T'}, \hat{f}_{0:-T'})$ has the asymptotic normality as shown in the following theorem, where $\hat{f}_{0:-T'}$ is an estimator of $f^*$ constructed from $\mathcal{S}_{0:-T'}$.
The proof is in Appendix (ref). The pointwise convergence assumption of $\hat{f}_{0:-T'}$ is for technical ease of proof.
\paragraph{(c) SSOPE:} In SSOPE, we randomly separate the dataset $\mathcal{S}$ into multiple subsets. We consider estimating an evaluation policy using a subset and estimate the value using the other subsets. If samples are i.i.d., the estimated evaluation policy is also independent of the evaluation datasets.
\paragraph{(d) OPOPE:} In OPOPE, we construct an evaluation probability using past samples obtained until period $t-1$ to evaluate the value at each period $t$. In this case, we can estimate the average policy values. Let us denote the evaluation policies as $\pi^\mathrm{e}_t(a\mid x, \mathcal{S}_{t-1})$, and assume that $\pi^{\mathrm{\mathrm{e}}}_t\xrightarrow{\mathrm{p}} \pi^\mathrm{e}$, where $\pi^\mathrm{e}$ is a time invariant probability. Let us define an Average Policy Value AIPW (AP) estimator as $\widehat{R}^{\mathrm{AP}}\big(\{\pi^\mathrm{e}_t\}^T_{t=1}\big) = \frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}_t(a\mid X_t, \mathcal{S}_{t-1})\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}, \hat{f}_{t-1})$, where note that $\hat{f}_t$ is an estimator of $f^*$ constructed from $\mathcal{S}_{t-1}$. Then, by using the AIPW estimator, we can show the following theorem.
The proof is in Appendix (ref). In practice, we face such a situation when estimating an evaluation probability from small samples with gathering more samples via bandit process. However, let us note that we cannot estimate the true bandit policy itself because we cannot reproduce the trajectory generated by the target bandit policy Appendix (ref).
In this section, we consider a case study of the best evaluation policy selection (BEPS), which is one of the most important applications of OPE. For ease of discussion, we only consider an unbiased, consistent, and asymptotically normal estimator under some conditions with deterministic evaluation probability. For example, AIPW and IPW estimators satisfy the requirements. Let us assume that there is a set of $L$-candidate evaluation policies, $\Lambda = \left\{\lambda^{(1)}, \lambda^{(2)}, \dots, \lambda^{(L)}\right\}$, which construct evaluation probabilities $\Pi^{\mathrm{e}} = \{\pi^{\mathrm{e},\lambda^{(1)}}_{\mathcal{S}}, \pi^{\mathrm{e},\lambda^{(2)}}_{\mathcal{S}}, \dots, \pi^{\mathrm{e},\lambda^{(L)}}_{\mathcal{S}}\}$ from a dataset $\mathcal{S}$. In this section, for a given dataset $\mathcal{S}_T$, our goal is to select the best evaluation policy $\lambda^{*}$ with the highest expected reward, i.e., $\lambda^{*} = \operatorname*{arg\,max}_{\lambda\in \Lambda} R(\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T})$. For achieving this goal, we propose three approaches: (I) estimating the policy value using samples $\mathcal{S}_T$, which also constructs the evaluation probabilities; (II) estimating the policy value using an evaluation dataset independent of the samples constructing the evaluation probability; (III) evaluation the policy value using cross-validation. We refer to these three approaches as In-Sample OPE (ISOPE), OPE with Evaluation Dataset (OPE2D), and Off-Policy Cross-Validation (OPCV). Among them, only OPE2D enables us to estimate the best $\lambda^{*}$ with keeping unbiasedness, consistency, and asymptotic normality. In ISOPE, we cannot guarantee the unbiasedness and asymptotic normality. In OPCV, instead of $R(\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T})$, we choose the best evaluation policy based on an unbiased, consistent, and asymptotically normal estimator of $R(\pi^{\mathrm{e},\lambda}_{\mathcal{S}'_T})$, where $\mathcal{S}'_T$ is a subset of $\mathcal{S}_T$. Finally, we discuss the criteria of the BEPS when multiple OPE estimators are given.
Let us consider constructing an OPE estimator from $\mathcal{S}_T$ for estimating a policy value of $\Pi^{\mathrm{e}}$. In this case, as pointed out in the existing studies, in general, we cannot construct an unbiased and asymptotic normal estimator, but can construct a consistent estimator if $\|\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T}- \pi^{\mathrm{e}*}\|_2 = \mathrm{o}_p(1)$ for a data-independent evaluation probability $\pi^{\mathrm{e}*}$. Let us consider an AIPW estimator $\widehat{R}^{\mathrm{AIPW}}_T(\pi^\mathrm{e}) = \frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a | X_t)\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_t, \hat{f}_T)$. Then, $\widehat{R}^{\mathrm{AIPW}}_T(\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T}) - R(\pi^{\mathrm{e}*})$ is equal to $\frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\left(\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T}(a | X_t) - \pi^{\mathrm{e}*}(a | X_t)\right)\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_t, \hat{f}_T)$ $+ \frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^{\mathrm{e}*}(a | X_t)\Gamma^{\mathrm{AIPW}}_t(a; \pi^\mathrm{b}_t, \hat{f}_T) - R(\pi^{\mathrm{e}*})$. If $\|\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T}- \pi^{\mathrm{e}*}\|_2 = \mathrm{o}_p(1)$, we can easily show $\widehat{R}^{\mathrm{AIPW}}_T(\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T}) \xrightarrow{\mathrm{p}} R(\pi^{\mathrm{e}*})$. However, for guaranteeing the asymptotic normality, it is known that we need to impose stronger restrictions for $\pi^{\mathrm{e},\lambda}_{\mathcal{S}_T}$ kallus2020stochasticpolicy. Although this estimator has an asymptotic bias, which does not disappear with $\sqrt{T}$-order ChernozhukovVictor2018Dmlf, this estimator is still useful owing to the consistency. ISOPE does not belong to the previous categorization because the evaluation probability is not deterministic. However, as a special case of ISOPE, if we use OPOPE of case (d) in Section (ref), we can guarantee the unbiasedness to the average of the policy value, but it requires a complicated procedure.
For estimating the policy values of $\Pi^{\mathrm{e}}$, let us consider constructing an OPE estimator from $\mathcal{S}'$, which is independent of $\mathcal{S}_T$. In this case, we can estimate the value of $R(\pi^{\mathrm{e},\lambda^{(m)}}_{\mathcal{S}_T})$ without loss of the asymptotic normality. This case requires us exogenous dataset $\mathcal{S}'$ but is most desirable from the theoretical perspective. OPE2D is closely related with the case (b) and (c) in the categorizations of Section (ref).
Cross-validation (CV) is a standard method for measuring the performance of methods. For simplicity, the dataset $\mathcal{S}_T$ is randomly separated into two datasets $\mathcal{S}^{(1)}_{T^{(1)}}$ and $\mathcal{S}^{(2)}_{T^{(2)}}$, where note that sample sizes are $T^{(1)}$ and $T^{(2)}$, respectively. Then, using the two datasets, we construct evaluation probabilities using $\mathcal{S}^{(1)}_{T^{(1)}}$ and estimate the policy value by using $\mathcal{S}^{(2)}_{T^{(2)}}$. Next, we construct evaluation probabilities using $\mathcal{S}^{(2)}_{T^{(2)}}$ and estimate the policy value by using $\mathcal{S}^{(1)}_{T^{(1)}}$. Finally, we calculate an average of the policy value estimators and choose an evaluation probability based on the averaged OPE estimator. In this case, we can estimate the policy values of $R(\pi^{\mathrm{e},\lambda^{(m)}}_{\mathcal{S}^{(1)}_{T^{(1)}}})$ and $R(\pi^{\mathrm{e},\lambda^{(m)}}_{\mathcal{S}^{(2)}_{T^{(2)}}})$ with asymptotic normality for $m\in\{1,2,\dots, M\}$ although we do estimate the policy value of $R(\pi^{\mathrm{e},\lambda^{(m)}}_{\mathcal{S}_{T}})$. OPCV belongs to the case (c) in the categorizations of Section (ref).
Let us assume that there is a set of $E$ OPE estimators, $\mathcal{E}=\left\{\widehat{R}^{(1)}, \dots, \widehat{R}^{(E)}\right\}$. Unlike the standard CV, in OPE, we cannot directly obtain the target metrics of the algorithm, $\frac{1}{T}\sum^{T}_{t=1}\sum^K_{a=1}Y_i(a, X_t)$. Thus, we need to use various OPE estimators approximating $\mathbb{E}\big[\sum^K_{a=1}\pi^\mathrm{e}(a, X_t)Y_t(a)\big]$. Then, which estimator should we use in the case with several OPE estimators? We raise the following three criteria of OPE estimators for BEPS.
\paragraph{Low asymptotic variance estimator:} First, we consider choosing an OPE estimator with the lowest asymptotic variance. The lower bound of the asymptotic variance is given as semiparametric lower bound (Appendix (ref)), and the asymptotic variances of several estimators, such as an AIPW estimator, are known to achieve this lower bound narita2019counterfactual. Therefore, from this perspective, a hopeful OPE estimator is an estimator with the lowest asymptotic variance. However, this approach is not useful if several OPE estimators achieve the lower bound.
\paragraph{Weighted estimator:} Second, we consider a new OPE estimator $\sum^E_{e}w_e\widehat{R}^{(E)}$ from $\mathcal{E}$ by weighting them using a weight $w_e$ such that $\sum^E_e w_e = 1$. A candidate for this weight is $w_e = 1/E$; that is, constructing a new estimator as the average of $\mathcal{E}$. Another candidate is using $e$-th element of $(I^\top_E\Sigma I_E)^{-1}I^\top_E\Sigma$ as the weight $w_e$if they asymptotically follow the multivariate normal distribution with covariance matrix $\Sigma$ GVK126800421.
\paragraph{Minimax criterion:} The final criterion is a minimax approach. In this criterion, for a dataset $\mathcal{S}$, we select the best evaluation policy as
In addition, we consider the following two-player zero-sum game; the player 1 decides the evaluation policy given as a linear combination of $\pi^{\mathrm{e}, \lambda^{(1)}}_{\mathcal{S}}, \dots, \pi^{\mathrm{e}, \lambda^{(L)}}_{\mathcal{S}}$; the player 2 constructs the estimator given as a linear combination of $\hat{R}^{(1)},\dots,\hat{R}^{(E)}$; The goal of player1/player2 is to maximize/minimize the estimated expected reward of the evaluation policy. Formally, the minmax strategy of player 1 is
where $\pi^{\mathrm{e}}_p = \sum^L_{l=1} p_l \pi^{\mathrm{e},\lambda^{(l)}}_{\mathcal{S}}$ and note that $\Delta^D := \{(p_d) \in [0,1]^K\mid \sum^D_{d=1}p_d=1\}$. Under some mild assumptions, we can compute $p^{*}$ via linear programming:
Such a minimax criterion is also adapted in existing machine learning studies wang2015. This criterion is conservative and aims to avoid the worst result.
In this section, we empirically investigate our arguments.
We investigate what causes by estimating policy value based on a dataset used for constructing evaluation probability. We generate an artificial pair of covariate and reward $(X_t, Y_t(1), Y_t(2), Y_t(3))$. The covariate $X_t$ is a $10$ dimensional vector generated from the standard normal distribution. For $a\in\{1,2,3\}$, the potential outcome $Y_t(a)$ is $1$ if $a$ is chosen by following a probability defined as $p(a\mid x) = \frac{\exp(g(a, x))}{\sum^3_{a'}\exp(g(a', x))}$, where $g(1, x) = \sum^{10}_{d=1} X_{t,d}$, $g(2, x) = \sum^{10}_{d=1} W_dX^2_{t,d}$, and $g(3, x) = \sum^{10}_{d=1} W_d|X_{t,d}|$, where $W_d$ is uniform randomly chosen from $\{-1, 1\}$. Let us generate three datasets, $\mathcal{S}^{(1)}_{T_{(1)}}$, $\mathcal{S}^{(2)}_{T_{(2)}}$, and $\mathcal{S}^{(3)}_{T_{(3)}}$, where $\mathcal{S}^{(m)}_{T_{(m)}} = \{(X^{(m)}_t, Y^{(m)}_t(1), Y^{(m)}_t(2), Y^{(m)}_t(3))\}^{T^{(m)}}_{t=1}$. Firstly, we train an evaluation probability $\pi^{\mathrm{e}(1)}$ by solving a prediction problem between $X^{(1)}_t$ and $Y^{(1)}_t(1), Y^{(1)}_t(2), Y^{(1)}_t(3)$ using the dataset $\mathcal{S}^{(1)}_{T_{(1)}}$. Then, we apply the evaluation policy $\pi^{\mathrm{e}(1)}$ on the independent dataset $\mathcal{S}^{(2)}_{T_{(2)}}$, and artificially construct bandit data $\{(X^{(m)}_t, A^{(m)}_t, Y^{(m)}_t)\}^{T^{(m)}}_{t=1}$, where $A_t$ is a chosen action from the evaluation policy and $Y^{(m)}_t = \sum^3_{a=1}\mathbbm{1}[A^{(m)}_t = a]Y^{(m)}_t(a)$. Then, we set the true policy value $R(\pi^{\mathrm{e}(1)})$ as $\frac{1}{T^{(2)}}\sum^{T^{(2)}}_{t=1}Y^{(m)}_t$. Next, using the datasets $\mathcal{S}^{(1)}_{T_{(1)}}$ and $\mathcal{S}^{(3)}_{T_{(3)}}$, we estimate the policy value as $\widehat{R}^{(1)}(\pi^{\mathrm{e}(1)}) = \frac{1}{T^{(1)}}\sum^{T^{(1)}}_{t=1}\sum^3_{a=1}\pi^{\mathrm{e}(1)}(a\mid X_t)Y^{(1)}_t(a)$ and $\widehat{R}^{(3)}(\pi^{\mathrm{e}(1)}) = \frac{1}{T^{(3)}}\sum^{T^{(3)}}_{t=1}\sum^3_{a=1}\pi^{\mathrm{e}(1)}(a\mid X_t)Y^{(3)}_t(a)$, respectively. Here, the estimator $\widehat{R}^{(1)}(\pi^{\mathrm{e}(1)})$ violates the assumption of deterministic evaluation policy because $\pi^{\mathrm{e}(1)}$ and $\mathcal{S}^{(1)}_{T_{(1)}}$ are correlated. Let us define estimation errors as $\mathrm{error1} = R(\pi^{\mathrm{e}(1)}) - \widehat{R}^{(1)}(\pi^{\mathrm{e}(1)})$ and $\mathrm{error2} = R(\pi^{\mathrm{e}(1)}) - \widehat{R}^{(3)}(\pi^{\mathrm{e}(1)})$, respectively. We conduct two cases of experiments by changing the sample size. The first case is $T^{(1)} = T^{(3)} = 100$, and the second case is $T^{(1)}=T^{(3)}=1000$. In both cases, we set $T^{(2)}=10000$. We plot the distributions of these errors in Figure (ref). If there is no bias, the error concentrates around on $0$. As expected, we can check that $\mathrm{error1}$ is biased, i.e., $\widehat{R}^{(1)}(\pi^{\mathrm{e}(1)})$ is biased. The results are shown in Figure (ref). These results imply that evaluating evaluation probability using samples used for constructing the probability may cause a serious bias even if we observe potential outcomes, and the bias reduces as the sample size increases.
Following dudik2011doubly and Chow2018, we evaluate the proposed estimators using classification datasets by transforming them into contextual bandit data. From the LIBSVM repository, we use the pendigits, mnist, sensorless, and connect-4 datasets \footnote{\url{https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/}}. 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. We create a set of $6$ evaluation policies, $\mathcal{E}$, as outputs of linear logistic regression, support vector machine (SVM) with linear kernel, SVM with the polynomial kernel, SVM with RBF kernel, and random forest. In each experiment, from a dataset, we generated sample $1000$ samples for training a behavior policy, $1000$ samples for creating evaluation policies, $1000$ samples for OPE, and $2000$ samples for calculating the true policy value. The more details of the experiment are shown in Appendix (ref).
For each dataset, we prepare a set of the following policy value estimators: IPW, DM, and AIPW. For the DM estimator, we estimate $f^*$ by linear and kernel ridge regression and denote them DM LR and DM KR, respectively. For the AIPW estimator, we estimate $f^*$ by kernel ridge regression. For selecting an OPE estimator from the set of OPE estimators, we introduce some criteria shown in Section (ref). First, we create a new OPE estimator by weighting the OPE estimators with equal weight (MEAN). We also applied minimax criteria of ((ref)) and ((ref)) and denote them Minimax and Mix, respectively. Finally, for an evaluation probability class $\Pi$, we select an OPE estimator as $\hat{\pi^\mathrm{e}} = \operatorname*{arg\,min}_{\pi^\mathrm{e}\in\Pi} \min_{\widehat{R}\in\mathcal{E}} - \widehat{R}\left(\pi^\mathrm{e}\right)$ and call it Maxmax. As a performance metric, we use the regret defined as $R(\pi^{\mathrm{e}*}) - R(\hat{\pi^\mathrm{e}})$, where $\pi^{\mathrm{e}'} = \operatorname*{arg\,max}_{\pi^\mathrm{e}\in\mathcal{E}}R(\pi^\mathrm{e})$ and $\hat{\pi^\mathrm{e}}$ is a chosen evaluation probability by a criterion. We conduct $100$ trials and calculate the means (Mean) and standard deviations (SD) of the regrets. The results are shown in Table (ref).
We also show experimental results of ISOPE and OPCV with multiple OPE estimators. We show them in Tables (ref) and (ref), respectively. For ISOPE experiment, unlike OPE2D experiment, we use the same dataset for both constructing and evaluating the evaluation probability. For OPCV experiment, we generated $1000$ samples for training a behavior policy, $2000$ samples for $2$ fold CV, and $2000$ samples for calculating the true policy value. After selecting the best method via CV, we reconstruct an evaluation probability using the whole $2000$ samples and measure its regret. The other settings are identical to the OPE2D experiments.
Note that, only in OPE2D experiments, we can directly evaluate the target policy value. Although the minimax criteria fail to select the best policy in OPE2D experiments, they work well in OPCV experiments. As the IPW estimator achieves both the best and worst performance, it is not easy to choose one OPE estimator. Among the proposed criteria, MEAN works stably in these experiments.
This study presented a guide for OPE. In OPE, there are various technical problems, but some existing studies tend to ignore them. In this paper, we organized the terminologies of OPE for avoiding the confusion in OPE applications and proposed several methods with new theoretical results. Among the applications, we focus on the BEPS problem and proposed several criteria for the practice of OPE. Finally, we showed empirical investigations of problems related to OPE.
Although OPE methods are expected to solve various applications, they may also return biased results by the abuse of them. This paper casts concern on this problem and shows a guide for the correct usage. Because OPE methods are potentially extensible to ethically sensitive areas, such as medicine, the OPE methods need to be applied with attention to possible issues that may arise.
Kaito Ariu was supported by the Nakajima Foundation Scholarship.
\onecolumn