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.
47,001 characters · 16 sections · 93 citation commands
The Adaptive Doubly Robust Estimator for Policy Evaluation in Adaptive Experiments and a Paradox Concerning Logging Policy
\affil[1]{CyberAgent Inc.} \affil[2]{Temple University}
Adaptive experiments, including efficient treatment effect estimation Laan2008TheCA,Hahn2011, treatment regimes Zhang2012,zhao2012est_ind, and multi-armed bandit (MAB) problems Gittins89,lattimore2020bandit, are widely accepted and used in real-world applications, for example, in social experiments Hahn2011, online advertisement zhang2012jointoptimization, clinical trials ChowChang201112,Villar2018, website optimization white2012bandit, and recommendation systems Lihong2010contextual. In those various applications, there is a significant interest in off-line counterfactual inference using samples obtained from past trials generated by a logging policy Lihong2010contextual,Li2011. Among several off-line evaluation criteria, this paper focuses on off-policy value estimation Li2015. The goal of OPVE is to estimate the expected value of the weighted outcome, which includes average treatment effect (ATE) estimation as a special case hirano2003,bang2005drestimation.
In OPVE, when the true logging policy is known, there are mainly three types of estimators: inverse probability weighting Horvitz1952, direct method (DM), and augmented IPW bang2005drestimation estimators. IPW-type estimators refer to a sample average of the outcomes weighted by the true logging policy. DM-type estimators refer to a sample average of an estimated conditional outcome. AIPW-type estimators consist of two components: the IPW part and the DM part. More details are given in Section (ref). In addition, when the true logging policy is unknown, we call IPW-type and AIPW-type estimators that use the estimated logging policy EIPW-type and DR-type estimators, respectively. In particular, and the focus of this paper, DR-type estimators are crucial in OPVE, since in most applications of interest the true logging policy is either unknown, difficult, or costly to obtain, making IPW and AIPW-type estimators often infeasible.
While existing OPVE methods typically assume that the samples are independent and identically distributed hirano2003,dudik2011doubly, adaptive experiments usually allow logging policies to be updated based on past observations, under which the generated samples are non-i.i.d. In this case, theoretical results shown under i.i.d. assumptions, such as consistency and asymptotic normality, are not guaranteed. In particular, the asymptotic normality is critical, as we can obtain $\sqrt{T}$-rate confidence intervals, where $T$ is the sample size. For this problem, Laan2008TheCA proposed an asymptotically normal AIPW estimator under dependent samples, with several follow-up studies, including hadad2019, Kato2020adaptive, and kelly2020batched. However, a DR-type estimator for dependent samples has never been formally proposed, despite its importance.
This paper proposes an asymptotically normal DR estimator for dependent samples. We call this DR estimator the adaptive DR (ADR) estimator. There are mainly two difficulties concerning this estimator. First, we cannot use the CLT for i.i.d. or martingale difference sequences, as done in Laan2008TheCA, hadad2019, and Kato2020adaptive. Second, when nuisance parameters are estimated with complicated models, the Donsker condition does not hold in general, which is required to show the asymptotic normality of semiparametric estimators, such as our proposed ADR estimator. In this paper, to solve these problems, we propose adaptive-fitting, inspired by the double/debiased machine learning for i.i.d. samples ChernozhukovVictor2018Dmlf. We also find that by using the ADR estimator, not only can OPVE be done without knowing the true logging policy, the ADR estimator paradoxically often outperforms the performance of AIPW estimators that use the true logging policy. We list our contributions as follows.
{\bf (I) Asymptotic normality of the ADR estimator.} We show the asymptotic normality of our proposed ADR estimator. To the best of our knowledge, a DR-type estimator for dependent samples obtained in adaptive experiments has not been formally proposed.
{\bf (II) Adaptive fitting.} While the asymptotic normalities of IPW and AIPW estimators are shown by the martingale CLT, we cannot directly apply this technique to our proposed ADR estimator. This is because the martingale condition does not hold when the true logging policy is unknown. To solve this problem, we utilize a novel sample-splitting method called adaptive-fitting to show the asymptotic normality of the ADR estimator. We generalize this technique as a variant of sample-splitting ChernozhukovVictor2018Dmlf for semiparametric inference with dependent samples without the Donsker condition. Unlike existing sample-splitting methods, which assume that samples are i.i.d., the proposed adaptive-fitting is applicable to non-i.i.d. samples. Note that this adaptive-fitting is different from martingale based estimators, such as Laan2008TheCA and hadad2019, which requires the true logging policy.
{\bf (III) Empirical paradox on using estimated logging policy.} Through experimental studies, we investigate the empirical performance of our proposed ADR estimator. We find that the ADR estimator often exhibits improved performances over other estimators using the true logging policy, such as the AIPW estimator. Estimators requiring the true logging policy tend to empirically be unstable due to the instability of the nuisance parameter; the instability being caused by the logging policy being near zero before convergence. Our finding implies that the ADR estimator mitigates this instability. We call this phenomenon a paradox concerning logging policy because using more information (the true logging policy) does not improve empirical performance. A similar paradox is known for IPW-type estimators for i.i.d. samples hahn1998role,Henmi2004paradox. However, we cannot explain our paradox from a conventional semiparametric efficiency perspective hahn1998role,hirano2003, as the asymptotic variances are the same between the ADR estimator (with an estimated logging policy) and the AIPW estimator (with the true logging policy), unlike IPW-type estimators.
{\bf Organization of this paper.} In Section (ref), we formulate our problem. In Section (ref), we introduce existing OPVE estimators for dependent samples. In Section (ref), we propose the ADR estimator, which is our main contribution. We call the method used for the ADR estimator adaptive-fitting, and generalize it in Section (ref). In Section (ref), we report a paradox through simulation studies and explain the cause of this phenomenon. In Section (ref), we conduct experiments using benchmark datasets.
Suppose that there is a time series $1,2,\dots, T$, and denote the set as $[T] = \{1,\dots,T\}$. For $t\in[T]$, let $A_t$ be an action in $\mathcal{A}=\{1,2,\dots,K\}$, $X_t$ be a covariate observed by a decision maker when choosing an action, and $\mathcal{X}$ be its space. Following the Neyman–Rubin causal model rubin1974, let a reward at period $t$ be $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 (random) outcome. We have a dataset $\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| x)$ denotes the probability of choosing an action $a$ conditional on a covariate $x$ at period $t$, and $p(y_a| x)$ denotes the density of a reward $Y_t(a)$ conditional on a covariate $x$. We assume that $p(x)$ and $p(y_a| x)$ are invariant across periods; that is, $\{(X_t, Y_t(1),\dots, Y_t(K))\}^T_{t=1}$ is i.i.d., but $p_t(a| x)$ can take different values across periods based on past observations. In this case, the samples $\big\{(X_t, A_t, Y_t)\big\}^{T}_{t=1}$ are correlated over time, that is, the samples are not i.i.d. Let $\Omega_{t-1}=\{X_{t-1}, A_{t-1}, Y_{t-1}, \dots, X_{1}, A_1, Y_{1}\}$ be the history and $\mathcal{M}_{t-1}$ be a set of possible histories until the $t$-th period. The probability $p_t(a| x)$ is determined by a logging policy $\pi_t:\mathcal{A}\times\mathcal{X}\times\mathcal{M}_{t-1}\to(0,1)$, such that $\sum^K_{a=1}\pi_t(a| x, \Omega_{t-1}) = 1$, which is a function of a covariate $X_t$, an action $A_t$, and history $\Omega_{t-1}$. We also assume that $\pi_t$ is conditionally independent of $Y_t(a)$ to satisfy unconfoundedness (Remark (ref)).
The goal of OPVE is to estimate the expected value of the sum of the outcomes $Y_t(a)$ weighted by an evaluation function $\pi^\mathrm{e}:\mathcal{A}\times \mathcal{X} \to\mathbb{R}$; that is,
where the expectation $\mathbb{E}_{(X_t, Y_t(1),\dots, Y_t(K))}$ is taken over $(X_t, Y_t(1), \dots, Y_t(K))$. We denote it as $\mathbb{E}$, when there is no ambiguity. As with dudik2011doubly, the evaluation function is usually referred to as an evaluation policy, where $\pi^\mathrm{e}(a| x)\in [0,1]$ and the sum is $1$. However, to not restrict it so we can include other forms, such as the ATE, we refer to it differently. The ATE is also a special case of OPVE for $\mathcal{A}=\{1,2\}$, where $\pi^\mathrm{e}(1| x) = 1$ and $\pi^\mathrm{e}(2| x) = -1$. To identify $R(\pi^\mathrm{e})$, we assume the overlap in the distributions of policies, convergence of $\pi_{t-1}$, and the boundedness of reward.
Assumption (ref) equivalently means that $\pi_{t}(a| x) > 0$ for all $a\in\mathcal{A}$ and $x\in\mathcal{X}$.
Although the reader may feel that Assumption (ref)--(ref) and the SUTVA (ref) are strong, we adopt it as a simple and basic case for the application, in order to introduce adaptive-fitting and the ADR estimator. We can extend the proposed method for different cases, such as when the data has the structure of batches or when the average of logging policy converges Kato2021nonstationary. Note that the convergence assumption (Assumption (ref)) is also explicitly or implicitly required in other studies, such as Laan2008TheCA and hadad2019.
We denote $\mathbb{E}[Y_t(a)| x]$ and $\mathrm{Var}(Y_t(a)| x)$ as $f^*(a, x)$ and $v^*(a, x)$, respectively. Let $\hat{f}_{t}(a, x)$ be an estimator of $f^*(a, x)$ constructed from $\Omega_{t}$. Let $\mathcal{N}(\mu, \mathrm{var})$ be the normal distribution with the mean $\mu$ and the variance $\mathrm{var}$. For a random variable $Z$ with density $p(z)$ and function $\mu$, let $\|\mu(Z)\|_2=\int |\mu(z)|^2 p(z) dz $ be the $L^{2}$-norm.
For estimating $R(\pi^\mathrm{e})$ from dependent samples, existing studies propose various estimators. An adaptive version of the IPW estimator is defined as $R^{\mathrm{AdaIPW}}_T(\pi^\mathrm{e})=\frac{1}{T}\sum^T_{t=1}\sum^K_{a = 1}\frac{\pi^\mathrm{e}(A_t| X_t)\mathbbm{1}[A_t=a]Y_t }{\pi_{t-1}(A_t| X_t, \Omega_{t-1})}$ Laan2008TheCA. If the model specification is correct, the direct method (DM) estimator $\frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\pi^\mathrm{e}(a | x)\hat{f}_{T}(a| X_t)$ is known to be consistent to $R(\pi^\mathrm{e})$. As an adaptive version of the AIPW estimator, Laan2008TheCA proposed an estimator $\widehat{R}^{\mathrm{AIPW}}_T(\pi^\mathrm{e})$ defined as
Using the martingale property, Laan2008TheCA showed asymptotic normality under Assumption (ref). hadad2019 and Kato2020adaptive organized the results ( Proposition (ref)).
We are often interested in the asymptotic efficiency of estimators. The lower bound of the asymptotic variance is defined for an estimator under some posited models of the DGP (ref). As with the Cram\'{e}r-Rao lower bound for the parametric model, we can also define the lower bound for the non- or semiparametric model bickel98. The semiparametric lower bound of the DGP (ref) under $p_1(a| x)=\cdots=p_T(a| x)=p(a| x)$ is given as follows hahn1998role,narita2019counterfactual:
The asymptotic variance of the asymptotic distribution is also known as the asymptotic mean squared error (MSE); that is, an OPVE estimator achieving the semiparametric lower bound also minimizes the MSE to the true value $R(\pi^\mathrm{e})$, not just obtaining a tight confidence interval.
There are various studies related to OPVE, including ATE estimation, under the assumption that samples are i.i.d. hahn1998role,hirano2003,dudik2011doubly,wang2017optimal,narita2019counterfactual,Bibaut2019moreffficient,Oberst2019. There are also several studies extending these methods to OPVE from dependent samples Laan2008TheCA,Laan2016onlinetml,Luedtke2016,hadad2019,Kato2020adaptive.
The AIPW estimator for dependent samples are proposed by Laan2008TheCA. hadad2019 proposed an evaluation weight to stabilize the estimator, which shares a similar motivation with weight clipping, or shrinkage, when i.i.d. samples are given Bembom2008,Bottou2013,Wang2017,Su2019,Su2020. Kato2020adaptive showed a non-asymptotic confidence interval of the AIPW estimator. Laan2016onlinetml and Luedtke2016 proposed an OPVE method without the convergence of the logging policies by using batches and standardization, respectively. Note that hadad2019 cannot weaken the assumptions regarding the logging policy, unlike Luedtke2016. kelly2020batched proposed an estimator similar to Laan2016onlinetml and applied it to linear regression. Estimators proposed by Laan2008TheCA, Luedtke2016, hadad2019, Kato2020adaptive, and kelly2020batched require the true logging policy, unlike our ADR estimator.
A semiparametric estimator usually requires the Donsker condition for its asymptotic normality bickel98. For semiparametric inference without the Donsker condition, sample-splitting is a typical approach klaassen1987,ZhengWenjing2011CTME,ChernozhukovVictor2018Dmlf. ChernozhukovVictor2018Dmlf referred to sample-splitting as cross-fitting and the semiparametric inference using cross-fitting as double-debiased machine learning (DML). For off-policy evaluation of reinforcement learning from dependent samples, KallusNathan2019EBtC proposed a mixingale-based sample-splitting.
For OPVE with dependent samples, this paper proposes the ADR estimator $\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e})$ defined as
where $\hat{g}_{t-1}$ is an estimator of $\pi_{t-1}$, constructed only from $\Omega_{t-1}$. We can use standard regression methods for constructing $\hat{f}_{t-1}$ and $\hat{g}_{t-1}$ if they satisfy the following assumptions.
Assumption (ref) requires convergence rates standard in regression estimators. For instance, we can apply nonparametric estimators proposed in MAB problems yang2002,qian2016kernel. Under the assumptions, we show the asymptotic normality of the ADR estimator.
Let us put forward the following assumption.
The proof is shown in Appendix (ref), which uses the following proposition from Kato2020adaptive.
We can prove this by the law of large numbers for martingales (Proposition (ref) in Appendix (ref)).
\paragraph{Donsker condition.} The main reason for using step-wise estimators $\{\hat{f}_{t-1}\}^T_{t=1}$ and $\{\hat{g}_{t-1}\}^T_{t=1}$ is to regard them as constants in the expectation conditioned on $\Omega_{t-1}$. The motivation is shared with DML. For asymptotic normality shown in Theorem (ref), we do not impose the Donsker condition on the nuisance estimators, $\hat{f}_{t-1}$ and $\hat{g}_{t-1}$, but only require the convergence rate conditions. We call this sample-splitting method, using $\hat{f}_{t-1}$ and $\hat{g}_{t-1}$, adaptive-fitting and discuss again in Section (ref). In the MAB problem, convergence rate conditions in nonparametric regression, such as a nearest-neighbor regression yang2002, Nadaraya-Watson regression qian2016kernel, random forest Feraud2016, kernelized linear models Chowdhury2017ker, and neural networks Zhou2020, have been shown. Note that we need to slightly modify the results for each situation because they are influenced by time-series behavior of logging probabilities.
\paragraph{Convergence rate of the logging policy.} In the main theorem, we do not explicitly describe the convergence rate of the logging policy. However, from Assumption (ref), which requires $\|\hat{g}_{t-1}(a| X_t) - \pi_{t-1}(a| X_t, \Omega_{t-1})\|_{2}=\mathrm{o}_{p}(t^{-p})$, $\|\tilde{\pi}(a| x) - \pi_{t-1}(a| X_t, \Omega_{t-1})\|_{2}=\mathrm{o}_{p}(t^{-p})$ is also required.
\paragraph{Theoretical comparison between AIPW and ADR estimators.} There are two major differences between AIPW and ADR estimators. First, the AIPW estimator requires {\it a priori} knowledge of the true logging policy, but the ADR estimator does not. Another main difference between the two is the convergence rate of nuisance estimators $\hat{g}_{t-1}$ and $\hat{f}_{t-1}$. For the AIPW estimator, only the uniform convergence in probability is required, but the ADR estimator requires specific convergence rates on $\hat{g}_{t-1}$ and $\hat{f}_{t-1}$. This difference comes from unbiasedness. The AIPW estimator is unbiased; therefore, the convergence of the asymptotic variance is essential, where it converges with $\mathrm{o}_{p}(1)$ if $\hat{f}$ and $\pi_t$ is $\mathrm{o}_{p}(1)$. Thus, the AIPW estimator does not require specific convergence rates. On the other hand, the ADR estimator requires the asymptotic bias term to vanish in a specific order. For this purpose, it imposes specific convergence rates on the nuisance estimators. From another perspective, a standard DML for i.i.d. samples and Theorem (ref) require $\|\hat{g}_{t-1}(a| X_t) - \pi_{t-1}(a| X_t, \Omega_{t-1})\|_{2}=\mathrm{o}_{p}(t^{-p})$, $\|\hat{f}_{t-1}(a,X_t)-f^*(a,X_t)\|_2=\mathrm{o}_{p}(t^{-q})$, and $p+q=1/2$.
\paragraph{Asymptotic efficiencies.} As shown in Theorem (ref) and Proposition (ref), ADR and AIPW estimators achieve the semiparametric lower bound. On the other hand, the asymptotic variance of the IPW estimator using the true logging policy $\pi_t$ is larger than the lower bound hirano2003,Laan2008TheCA,Kato2020adaptive. Although it is known that the IPW estimator using the estimated logging policy can achieve the lower bound under some conditions with i.i.d. samples hirano2003, the asymptotic property under dependent samples is still unknown.
We generalize the method used to derive the asymptotic normality of the ADR estimator as a variant of DML. Let us define the parameter of interest $\theta_0$ that satisfies $\mathbb{E}[\psi(W_t; \theta_0, \eta_0)] = 0$, where $\{W_t\}^T_{t=1}$ are observations, $\eta_0$ is a nuisance parameter, and $\psi$ is a score function. We consider obtaining an asymptotic normal estimator of $\theta_0$ when using complex and data-adaptive regression methods, such as random forests, neural networks, and Lasso, to estimate the nuisance parameter $\eta_0$. Under such a situation, the Donsker condition does not hold, in general. Sample-splitting is a typical approach to control the complexities of semiparametric inference without the Donsker condition klaassen1987,ZhengWenjing2011CTME,ChernozhukovVictor2018Dmlf. In DML of ChernozhukovVictor2018Dmlf, the dataset with i.i.d. samples $\{W_t\}^T_{t=1}$ is separated into several subgroups. Then, a semiparametric estimator for each subgroup is constructed, but the nuisance estimators are constructed from the other subgroups. Here, the nuisance estimators are independent in the expectation conditioned on the other subgroups. Thus, the complexities are controlled without the Donsker condition, and standard nonparametric convergence rate conditions on nuisance estimators suffice to show the asymptotic normality of the semiparametric estimator. ChernozhukovVictor2018Dmlf called the method cross-fitting.
However, cross-fitting of ChernozhukovVictor2018Dmlf cannot be applied when samples $\{W_t\}^T_{t=1}$ are dependent. Therefore, the ADR estimator uses step-wise nuisance estimators based on past observations $\Omega_{t-1}$. This construction is inspired by Laan2016onlinetml, which proposed a sample-splitting for batched dependent samples. The nuisance estimators are independent in the expectation over the $t$-th samples conditioned on $\Omega_{t-1}$. Thus, we can regard our sample-splitting as another approach for DML. We call this step-wise construction adaptive-fitting, in contrast to cross-fitting. We briefly summarize the procedure as follows: (i) at each step $t=1,2,\dots,T$, we estimate $\eta_0$ only using $\{W_s\}^{t-1}_{s=1}$ and denote the estimaters as $\{\eta_{t-1}\}^T_{t=1}$; (ii) then, we substitute $W_{t}$ and $\eta_{t-1}$ into $\psi$ and obtain an estimator $\hat{\theta}_T$ of $\theta_0$ by solving $\frac{1}{T}\sum^T_{t=1}\psi(W_t, \hat{\theta}_T, \eta_{t-1}) = 0$. Under this construction, if (a) an estimator $\check{\theta}_T$ obtained by solving $\frac{1}{T}\sum^T_{t=1}\psi(W_t, \check{\theta}_T, \eta_{0}) = 0$ has the asymptotically normal distribution and (b) the asymptotic bias decays with the rate faster than $\mathrm{o}_{p}(-1/\sqrt{t})$, we can obtain the asymptotically normal estimator of $\theta_0$. In Figure (ref), we illustrate the difference between cross-fitting (left) and adaptive-fitting (right). The y-axis represents samples used for constructing the OPVE estimator with nuisance estimators using samples represented by the x-axis. In the left graph, for $T/K$ samples, we calculate the sample average of the component including nuisance estimators based on the other $(K-1)T/K$ samples. In the right graph, at period $t$, we use nuisance estimators constructed from samples at $t=1,2,\dots,t-1$. To satisfy (a), we assumed that the convergence of the logging policy (Assumption (ref)). There are other ways to satisfy this condition. For example, we can assume the existence of batches as Laan2016onlinetml and kelly2020batched. We briefly introduce the ADR estimator for this case in Appendix (ref).
The advantage of the ADR estimator is that, unlike the AIPW estimator, it does not require the true logging policy. However, we find that the ADR estimator often achieves a smaller MSE than the AIPW estimator, which requires the true logging policy. We refer to this phenomenon as a paradox concerning logging policy.
hadad2019 pointed out that the AIPW estimator tends to be unstable when the nuisance parameter $\pi_{t-1}$ can take a value close to zero before converging to $\tilde{\pi}$. To prevent this instability, hadad2019 proposed the Adaptively Weighted AIPW (AW-AIPW) estimator by adding evaluation weights, which converge to a constant almost surely, to the AIPW estimator proposed in other studies, such as Laan2008TheCA. Note that the AW-AIPW estimator cannot mitigate the assumptions on the logging policy $\pi_{t-1}$ required in the AIPW Laan2008TheCA and our ADR estimator, namely $\pi_{t-1}$ is non-zero and converges. The aim of adaptive weighting is not in theoretical improvement of the AIPW estimator, but in its empirical stabilization.
The ADR estimator replaces the true logging policy $\pi_{t-1}$ with its estimator. We find that by replacing the true logging policy with its estimator, we can control the instability caused from $\pi_{t-1}$ by constructing well-formed $\hat{g}_{t-1}$. For example, if we know that the range of $\tilde{\pi}$ is $(\varepsilon, 1-\varepsilon)$ for $0< \varepsilon < 1-\varepsilon < 1$, we can add the clipping technique when estimating $\hat{g}_{t-1}$. For example, in early periods, we can set $\hat{g}_{t-1}$ as $0.5$. Such techniques is greatly beneficial. Note that if the range of $\tilde{\pi}$ is truly $(\varepsilon, 1-\varepsilon)$, the clipping of $\hat{g}_{t-1}$ does not cause clipping bias; that is, the estimator correctly converges to the asymptotic distribution shown in Theorem (ref).
The main difference between the AW-AIPW estimator and the ADR estimator is that the former requires information of the true logging policy $\pi_{t-1}$, while the latter does not by replacing it with its estimator. Note that the AW-AIPW estimator requires the same assumptions on $\pi_{t-1}$ as the AIPW and ADR estimator and loses unbiasedness due to the evaluation weight. In addition, the construction of the adaptive weight is not obvious when there are covariates $X_t$ because all but one method for weight construction in hadad2019 does not consider covariates. Our finding also shares motivation with weight clipping for i.i.d. samples, such as Bottou2013. We can regard the AW-AIPW estimator as a variant of this method, where the weight clipping can decay as $\pi_t$ converges, and be ignored asymptotically. However, our interest is in asymptotic normality from dependent samples without the true logging policy, which is not discussed in the literature.
For reasons given in the previous section, the ADR estimator may empirically perform better than the AIPW estimator because the estimator $\hat{g}_{t-1}$ stabilizes the ADR estimator by absorbing the instability of $\pi_{t-1}$. We empirically show this paradox using a synthetic dataset. We generate an artificial pair of covariate and potential outcome, $(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\}$, $Y_t(a)=1$ if $a$ is chosen with probability $q(a| x) = \frac{\exp(g(a, x))}{\sum^3_{a'=1}\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}$, $g(3, x) = \sum^{10}_{d=1} W_d|X_{t,d}|$, and $W_d$ is uniform randomly chosen from $\{-1, 1\}$. We 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}$. First, we train an evaluation function $\pi^\mathrm{e}$ by solving a prediction problem between $X^{(1)}_t$ and $Y^{(1)}_t(1), Y^{(1)}_t(2), Y^{(1)}_t(3)$ using $\mathcal{S}^{(1)}_{T_{(1)}}$. Then, we regard the evaluation function $\pi^\mathrm{e}$ as a logging policy and apply it on the independent dataset $\mathcal{S}^{(2)}_{T_{(2)}}$ to obtain $\{(X'_t, A'_t, Y'_t)\}^{T_{(2)}}_{t=1}$, where $A'_t$ is an action chosen from the evaluation function and $Y^{(m)}_t = \sum^3_{a=1}\mathbbm{1}[A^{(m)}_t = a]Y^{(m)}_t(a)$. Then, we estimate the true value $R(\pi^\mathrm{e})$ as $\frac{1}{T_{(2)}}\sum^{T_{(2)}}_{t=1}Y^{(m)}_t$. Next, using the datasets $\mathcal{S}^{(3)}_{T_{(3)}}$ and an MAB algorithm, we generate a bandit dataset $\mathcal{S}=\{(X_t, A_t, Y_t)\}^{T_{(3)}}_{t=1}$. For $\mathcal{S}$, we apply the ADR estimator, IPW estimator with the true logging policy (IPW), AIPW estimator (AIPW), AW-AIPW estimator (AW-AIPW) IPW estimator with estimated logging policy (EIPW), and DM estimator (DM). For the AW-AIPW estimator, we use the evaluation weight $\sqrt{\pi_{a,x}(t)}/T$, proposed in hadad2019. The other proposed weights of hadad2019 seem to be specific to situations without covariate $X_t$. For estimating $f^*$ and the logging policy, we use the kernelized Ridge least squares and logistic regression, respectively. We use a Gaussian kernel, and both hyper-parameters of the Ridge and kernel are chosen from $\{0.01, 0.1, 1\}$. We define the estimation error as $R(\pi^\mathrm{e}) - \widehat{R}(\pi^\mathrm{e})$. We conduct ten experiments by changing sample sizes and MAB algorithms. For the sample size $T_{(3)}$, we use $100$, $250$, $500$, $750$, and $10,000$ with the LinUCB and LinTS algorithms. For the sample sizes $T_{(1)}$ and $T_{(2)}$, we use $1,000$ and $100,000$ respectively. We conduct $100$ trials to obtain the root MSEs (RMSEs), the standard deviations of MSEs (SDs), and the coverage ratios (CRs) of the $95\%$ confidence interval (percentage that the confidence interval covers the true value). The results with $T=250$, $500$, $750$ are shown in Table (ref) and those with $T=750$ are shown in Figure (ref). The other results are shown in Appendix (ref). In all cases, the ADR estimator performs well compared to other methods. Although the AIPW estimator has asymptotic normality, the performance is not comparable with the ADR estimator. The reason why the AW-AIPW estimator underperforms is that the performance depends on the choice of evaluation weights, and the weight proposed by hadad2019 is not suitable for our case with covariates. The EIPW estimator suffers from the dependency problem. We postulate that this is owing to the instability of $\pi_t$.
Following dudik2011doubly, we evaluate the estimators using classification datasets by transforming them into contextual bandit data. From the LIBSVM repository CC01a, we use the {\tt mnist}, {\tt satimage}, {\tt sensorless}, and {\tt connect-4} datasets \footnote{\url{https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/.}}. The dataset description is in Table (ref) of Appendix (ref). We construct a logging policy as $\pi_t(a| x) = \alpha\pi^m_t(a| x)+(1-\alpha)\frac{0.1}{K}$, where $\alpha\in (0,1)$ is a constant, and $\pi^m_t(a| x)$ is a policy such that $\pi^m_t(a| x) = 1$ for an action $a\in\mathcal{A}$ and $\pi^m_t(a'| x) = 0$ for the other actions ($a'\neq a$). The policy $\pi^m_t(a| x)$ is determined by logistic regression and MAB algorithms. For MAB algorithms, we use upper confidence bound and Thompson sampling with a linear model, which are denoted as LinUCB Wei2011 and LinTS Agrawal2013. The evaluation function is fixed at $\pi^\mathrm{e}(a| x) = 0.9\pi^d(a| x)+\frac{0.1}{K}$, where $\pi_d$ is a prediction of a logistic regression.
We focus on the ADR estimator and compare it to the IPW, EIPW, AIPW, and DM estimators, as done in Section (ref). We omit the AW-AIPW estimator, as we found that the performance depends on the choice of the evaluation weight (see Section (ref)). Additionally, the paper does not consider or discuss situations where there exist covariates. We compare those estimators using the benchmark datasets generated through the process explained above. For $\alpha\in\{0.7, 0.4, 0.1\}$ and the sample sizes $800$, $1,000$, and $1,200$, we calculate the RMSEs and the SDs over $10$ trials. The results of {\tt mnist} and {\tt satimage} with the LinUCB policy and $T=1,000$ are shown in Tables (ref). The full results, including the results with the LinTS policy and i.i.d. samples, are shown in Appendix (ref). As discussed in Section (ref), the ADR estimator performs well. Although the asymptotic distributions of AIPW and ADR estimators are the same, the AIPW estimator shows poorer performance. As Section (ref), we consider this to be because the estimator of $\pi_t$ is absorbing the instability of $\pi_t$.
Note that the ADR, IPW, and AIPW estimators are asymptotically normal, but the IPW and APIW estimators are not feasible when the true logging policy is not given. To the best of our knowledge, asymptotic normality of the EIPW and DM estimators has not been shown when samples are dependent, and the proof is non-trivial owing to the dependency and the Donsker condition.
DR-type estimators are crucial in causal inference because they do not assume {\it a priori} knowledge of the true logging policy and they asymptotically follow a normal distribution under standard convergence rate conditions of nuisance estimators. However, existing studies have rarely discussed DR-type estimators when samples are dependent. We derived the ADR estimator and proposed adaptive-fitting as a variant of DML to obtain asymptotic normality. In experiments, we found a paradox that the ADR estimator tends to be more stable than the AIPW estimator and conjectured that this is because the ADR estimator absorbs the instability of the true logging policy $\pi_t$.
In OPVE with dependent samples, we need to put some assumptions on the behavior of $\pi_t$ to obtain asymptotic normality (Assumption (ref)). These assumptions can be broken if the time-series is very complicated. However, we note that this is a limitation of the entire field. The asymptotic normality and double robustness of OPVE estimators are necessary theoretical properties to avoid deriving false causality. Since causal inference is often used in applications related closely to public policy, we consider understanding these limitations critical.
\onecolumn