Adaptive Doubly Robust Estimator from Non-stationary Logging Policy under a Convergence of Average Probability

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.

72,614 characters · 18 sections · 76 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractAdaptive experiments, including efficient average treatment effect estimation and multi-armed bandit algorithms, have garnered attention in various applications, such as social experiments, clinical trials, and online advertisement optimization. This paper considers estimating the mean outcome of an action from samples obtained in adaptive experiments. In causal inference, the mean outcome of an action has a crucial role, and the estimation is an essential task, where the average treatment effect estimation and off-policy value estimation are its variants. In adaptive experiments, the probability of choosing an action (logging policy) is allowed to be sequentially updated based on past observations. Due to this logging policy depending on the past observations, the samples are often not independent and identically distributed (i.i.d.), making obtaining an asymptotically normal estimator difficult. A typical approach for this problem is to assume that the logging policy converges in a time-invariant function. However, this assumption is restrictive in various applications, such as when the logging policy fluctuates or becomes zero at some periods. To mitigate this limitation, we propose another assumption that the average logging policy converges to a time-invariant function and show the doubly robust (DR) estimator's asymptotic normality. Under the assumption, the logging policy itself can fluctuate or be zero for some actions. We also show the empirical properties by simulations.

Introduction

Estimating the mean outcome of an action is an essential task in statistical inference under Neyman-Rubin potential outcomes model Luedtke2016. The average treatment effect (ATE) estimation Holland1986stat,rubin87,robins94,hirano2003efficient,ImaiKosuke2014Cbps,imbens_rubin_2015 and off-policy value (OPV) estimation for multi-armed bandit (MAB) algorithms Precup2000,dudik2011doubly,Mahmood20014,Li2015,jiang2016,wang2017optimal,Bibaut2019moreffficient are its special cases. We consider mean outcome estimation for dependent samples obtained from adaptive experiments ChowChang201112,Hahn2011,Kasy2021, including MAB algorithms Villar2018 and treatment regimes (TR) Zhang2012,zhao2012est_ind,Chakraborty2013. In adaptive experiments, we gather samples via logging policy (probability of choosing an action), which is sequentially updated based on past observations. For instance, Laan2008TheCA considered a situation where a research subject visits at each period $t=1,2,\dots,T$, and we select a treatment following a logging policy sequentially updated based on past observation to minimize the variance of an ATE estimator. Owing to the logging policy depending on the past observations, the samples are not independent and identically distributed (i.i.d.).

For statistical inference for the mean outcome, we aim to construct an asymptotically normal estimator, which also implies $\sqrt{T}$ consistency for a sample size $T$. Under the dependency, we cannot apply the standard central limit theorem (CLT). For mitigating this problem, existing studies proposed various approaches, and one of the main approaches is to apply the martingale CLT, which requires that the variance of the target random variable to a time-invariant one. Existing studies have proposed the following three strategies for satisfying this requirement. The first strategy is to assume that the logging policy converges to a time-invariant function in probability Laan2008TheCA,hadad2019,Kato2020adaptive. The second strategy is to assume the existence of batched samples, where there are infinite samples in each batch Hahn2011,Laan2014onlinetml,kelly2020batched,kato2020batch. The third strategy is to standardize the score function to equalize the variance of each period Luedtke2016.

figure[figure omitted — 619 chars of source]

However, these strategies are often restrictive in practice. For instance, we can raise the following two situations, where the first strategy is not applicable: (I) the logging policy fluctuates, and (II) the logging policy is $0$ or $1$ at a period. In best arm identification (BAI), kaufman2016complexity and garivier2016optimal showed that pulling arms with a specific ratio achieves the lower bound of the sample complexity. Their methods deterministically select an arm at a period to keep the ratio. Here, the logging policy does not converge to a time-invariance function. The value is $1$ for an arm and $0$ for the others. Therefore, we cannot apply an existing mean outcome estimator for the situations.

When the logging policy fluctuates, the martingale CLT is not applicable owing to the time-variant variance. To mitigate this problem, Luedtke2016 proposed standardizing the score function by its estimated variance, which is applicable to many cases. However, the estimator of Luedtke2016 does not achieve $\sqrt{T}$-consistency by splitting the samples to estimate the variance for the standardization.

For overcoming these problems, instead of the conventional strategies, this paper proposes a new strategy based on the assumption that the average logging policy converges to a time-invariant function in probability. This assumption is a generalization of the first strategy based on the assumption that the logging policy converges to a time-invariant function in probability. This is because when the logging policy itself converges, the average logging policy also converges. The new assumption is greatly useful in practice. For instance, we can apply our method to cases, where the logging policy can fluctuate, and the logging policy is $0$ or $1$ if the average logging policy converges. We also illustrate an example when the average logging policy converges in contrast to a case when the logging policy itself converges in Figure (ref).

\paragraph{Organization of this paper.} In Section (ref), we introduce our problem setting and the parameter that we want to estimate. In Section (ref), we propose two DR-type estimators and show the asymptotic normalities under the assumption that the average logging policy converges in probability. The first estimator is more natural and empirically performs well but requires conditions that are not easy to be confirmed (Theorem (ref)). The second estimator does not empirically perform well as the first one, but we can show the asymptotic normality by using an assumption that is easier to be confirmed (Theorem (ref)). In Section (ref), we numerically investigate the performance of the proposed estimators. In Section (ref), we discuss the remaining problems.

Problem Setting

In this section, we describe our problem setting.

Data-Generating Process (DGP)

Consider a time-series $t=1,2,\dots, T$. For each period $t$, let $A_t$ be an action in $\mathcal{A}=\{1,2,\dots,K\}$, $X_t\in\mathcal{X}$ be a covariate observed by the decision maker when choosing an action, and $\mathcal{X}$ be the space of covariate. Let a random variable denoting an outcome at period $t$ be $Y_t=\sum^K_{a=1}\mathbbm{1}[A_t = a]Y_t(a)$, where $Y_t(a)\in\mathbb{R}$ is a random variable denoting the potential (random) outcome of an action $a\in\mathcal{A}$. We have a dataset $\big\{(X_t, A_t, Y_t)\big\}^{T}_{t=1}$. The DGP is described as follows:

align*[align* omitted — 75 chars of source]

where $X_t$ is generated from $p(x)$, $A_t$ is generated from $p_t(a\mid x)$ at the period $t$, and $Y_t(a)$ is generated from $p(y_a\mid x)$. While $p(x)$ and $p(y_a\mid x)$ are invariant across periods, $p_t(a\mid x)$ can be different 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 with the space $\mathcal{M}_{t-1}$. The probability $p_t(a\mid x)$ is determined by a logging policy $\pi_t:\mathcal{A}\times\mathcal{X}\times\mathcal{M}_{t-1}\to(0,1)$. We also assume that $\pi_t$ is conditionally independent of $Y_t(a)$ to satisfy the unconfoundedness (Remark (ref)).

remark[Stable unit treatment value assumption] The DGP also implies the stable unit treatment value assumption, that is, $p(y(a)\mid x)$ is invariant for any $p_t(a\mid x)$ Rubi:86.

remark[Unconfoundedness] In this paper, unconfoundedness refers independence between $(Y_t(1),\dots, Y_t(K))$ and $A_t$ conditioned on $X_t$ and $\Omega_{t-1}$, which is required for identification of the mean outcome.

Parameter of Interest in Mean Outcome Estimation

Let a function $\pi^\mathrm{e}:\mathcal{A}\times \mathcal{X} \to\mathbb{R}$ be an evaluation weight. We consider estimating the mean outcome weighted by an evaluation weight $\pi^{\mathrm{e}}(a \mid x)$ defined as

align*[align* omitted — 101 chars of source]

dudik2011doubly regarded the weight as an policy that we want to evaluate by limiting the range into $(0,1)$ and the sum to $1$. The ATE is also a special case of the mean outcome for two actions $\mathcal{A}=\{1,2\}$, where $\pi^\mathrm{e}(1\mid x) = 1$ and $\pi^\mathrm{e}(2\mid x) = -1$. To identify $R(\pi^\mathrm{e})$, we assume the boundedness of the potential outcome.

assumptionFor all $a\in\mathcal{A}$ and $t\in\{1,2,\dots,T\}$, there exists a constant $C_Y$ such that $|Y_t(a)| \leq C_Y$

\paragraph{Notations.} Let us denote $\mathbb{E}[Y_t(a)\mid x]$ and $\mathrm{Var}(Y_t(a)\mid x)$ as $f^*(a, x)$ and $v^*(a, x)$, respectively. Let $\hat{f}_{t}(a, x)$ be an estimators 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$ and function $\mu$, let $\|\mu(Z)\|_2=\int |\mu(z)|^2 p(z) dz $ be the $L^{2}$-norm.

Preliminaries of Mean Outcome Estimation

Mean Outcome Estimation from Independent Samples

We introduce well-known estimators for a standard mean outcome estimation problem with i.i.d. samples where $\pi_1(a\mid x, \Omega_{0})=\pi_2(a\mid x, \Omega_{1})=\cdots=\pi(a\mid x)$. One of the standard estimators is an inverse probability weighting (IPW) estimator

align*[align* omitted — 168 chars of source]

which are also called importance sampling Horvitz1952. If $\hat{f}$ is a consistent estimator of $f^*$, the direct method (DM) estimator defined as $\sum^K_{a=1}\pi^\mathrm{e}(a \mid x)\hat{f}(a\mid X_t)$ is known to be consistent to the policy value $R(\pi^\mathrm{e})$. By extending an IPW, robins94, Scharfstein1999, and Robins1999 proposed an Augmented IPW (AIPW) estimator defined as

align*[align* omitted — 256 chars of source]

where $\hat{f}$ is a consistent estimator of $f^*$. In addition, a doubly robust (DR) estimator is also a standard choice Scharfstein1999,Bang2005, which is defined as

align*[align* omitted — 260 chars of source]

where $\hat{g}$ is a consistent estimator of $\pi$.

\paragraph{Semiparametric efficiency bound.} In many cases, we are interested in the asymptotic efficiency of the estimators. The lower bound of the asymptotic variance is defined for an estimator under some posited models of the DGP. If this posited model is a parametric model, then the lower bound is equal to the Cram\'{e}r-Rao lower bound. When this posited model is a non- or semiparametric model, the corresponding lower bound can still be defined bickel98. For OPV estimation setting, narita2019counterfactual shows that the semiparametric lower bound of the DGP under $p_1(a\mid x)=\cdots=p_T(a\mid x)=p(a\mid x)$ is

align*[align* omitted — 230 chars of source]

The asymptotic variance of the asymptotic distribution is also known as the asymptotic mean squared error (MSE). By constructing a mean outcome estimator achieving the semiparametric lower bound, we can also minimize the MSE between the estimator and the true value $R(\pi^\mathrm{e})$, not only obtain a tight confidence interval.

Mean Outcome Estimation from Dependent Samples

There are mainly three approaches for deriving the asymptotic normality of a mean outcome estimator from dependent samples: (i) assuming the convergence of the logging policy $\pi_t(a\mid x, \Omega_{t-1})$ to a time-invariant probability Laan2014onlinetml,hadad2019,Kato2020adaptive; (ii) assuming the presence of batched samples Hahn2011,Laan2014onlinetml,kelly2020batched; (iii) standardizing the score functions. Under the first approach, Laan2008TheCA and Kato2020adaptive put the following assumption.

assumptionFor all $a\in \mathcal{A}$ and $x\in \mathcal{X}$, $\hat{f}_{t-1}(a, x) \xrightarrow{\mathrm{p}} f^*(a, x)$ and $\pi_t(a\mid x, \Omega_{t-1})\xrightarrow{\mathrm{p}} \alpha(a\mid x)$, where $\alpha: \mathcal{A}\times\mathcal{X}\to(0,1)$ is a time-invariant function such that $\sum^K_{a'=1}\alpha(a'\mid x)=1$ and there exists a constant $C_\pi$ satisfying $\left| \frac{\pi^\mathrm{e}(a\mid x)}{\pi_t(a\mid x, \Omega_{t-1})}\right| \leq C_{\pi}$ for all $a\in \mathcal{A}$ and $x\in \mathcal{X}$, and $\Omega_{t-1}\in\mathcal{M}_{t-1}$.

Then, Laan2008TheCA proposed the adaptive version of an IPW (AdaIPW) estimator defined as $R^{\mathrm{AdaIPW}}_T(\pi^\mathrm{e})=\frac{1}{T}\sum^T_{t=1}\frac{\pi^\mathrm{e}(A_t\mid X_t)\mathbbm{1}[A_t=a]Y_t }{\pi_{t}(A_t\mid X_t, \Omega_{t-1})}$ and Laan2008TheCA and Kato2020adaptive proposed estimators based on an Adaptive AIPW (A2IPW) estimator $\widehat{R}^{\mathrm{A2IPW}}_T(\pi^\mathrm{e})$ defined as

align*[align* omitted — 237 chars of source]

where $\hat{f}_t$ is a consistent estimator of $f^*$ constructed only using $\Omega_{t-1}$. Under Assumption (ref). Kato2020adaptive showed the asymptotic normality of an A2IPW estimator.

proposition[Asymptotic distribution of an A2IPW estimator] Under Assumptions (ref) and (ref), $\sqrt{T}\left(\widehat{R}^{\mathrm{A2IPW}}_T(\pi^\mathrm{e})-R(\pi^\mathrm{e})\right)\xrightarrow{d}\mathcal{N}\left(0, \Psi(\alpha)\right)$.

Besides, By replacing the true logging policy $\pi_t$ with its estimator $\hat{g}_{t-1}$, kato2020theoreticalcomparison proposed an ADR estimator $\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e})$ defined as

align*[align* omitted — 231 chars of source]

kato2020theoreticalcomparison showed Proposition (ref) using sample-fitting, which is also used in Laan2014onlinetml. First, we assume boundedness and consistencies of nuisance estimators $\hat{f}_{t-1}$ and $\hat{g}_{t-1}$.

assumptionFor all $a\in \mathcal{A}$ and $x\in\mathcal{X}$, there exist constants $C_f, C_g > 0$ such that $|\hat{f}_{t-1}(a, x)| \leq C_f$ and $\left|\frac{\pi^\mathrm{e}(a\mid x)}{\hat{g}_{t-1}(a\mid x)}\right| \leq C_g$ for all $a\in\mathcal{A}$, $x\in\mathcal{X}$, and $t\in\{1,2,\dots,T\}$.

assumptionFor all $a\in \mathcal{A}$, $\|\hat{g}_{t-1}(a\mid X_t) - \alpha(a\mid X_t)\|_{2}=\mathrm{o}_{p}(1)$, $\|\hat{f}_{t-1}(a,X_t)-f^*(a,X_t)\|_2=\mathrm{o}_{p}(1)$.

In addition, we put the following assumption on the convergence rate.

assumptionFor all $a\in \mathcal{A}$, $\|\hat{g}_{t-1}(a\mid X_t) - \alpha(a\mid X_t)\|_{2}\|\hat{f}_{t-1}(a,X_t)-f^*(a,X_t)\|_2=\mathrm{o}_{p}(t^{-1/2})$.

Then, kato2020theoreticalcomparison proved the following proposition.

proposition[Asymptotic normality of an ADR estimator] Then under Assumptions (ref)--(ref), for the ADR estimator, \begin{align*} \sqrt{T}\left(\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e})-R(\pi^\mathrm{e})\right)\xrightarrow{d}\mathcal{N}\left(0, \Psi(\alpha)\right). \end{align*}

\paragraph{Sample splitting and Donsker's condition.} When estimating $f^*$ and $\frac{1}{t}\sum^t_{s=1}\pi_s$, we only use $\Omega_{t-1}$. Owing to this construction, we can derive the asymptotic normality of the semiparametric estimator without Donsker's condition. This technique is a variant of sample-splitting klaassen1987,ZhengWenjing2011CTME,ChernozhukovVictor2018Dmlf. See Laan2014onlinetml and kato2020theoreticalcomparison for more details.

Conditions for Asymptotic Normality

We consider a class of OPV estimators $\hat{R}_T$ such that there exists a function $\phi:\mathcal{X}\times\mathcal{A}\times \mathbb{R}\to \mathbb{R}$ satisfying

align*[align* omitted — 127 chars of source]

Such an estimator $\hat{R}_t$ and function $\phi$ are called asymptotically linear estimator and influence function, respectively. If samples are i.i.d., an asymptotically linear estimator has an asymptotic normality as $\sqrt{T}\left(\hat{R}_T(\pi^\mathrm{e})\right)\to\mathcal{N}(0, \mathbb{E}\left[\phi(X_t, A_t, Y_t)\phi(X_t, A_t, Y_t)\right])$. However, when samples are dependent, we need to carefully consider the condition for asymptotic normality of $\frac{1}{\sqrt{T}}\sum^T\phi(X_t, A_t, Y_t)$. A standard strategy is to apply martingale CLT to $\frac{1}{\sqrt{T}}\sum^T\phi(X_t, A_t, Y_t)$. For a martingale difference sequence (MDS), the martingale CLT is provided as follows.

proposition[CLT for a martingale difference sequence, GVK126800421, Proposition 7.9, p. 194] Let $\{R_t\}^\infty_{t=1}$ be a scalar martingale difference sequence with $\overline{R}_T=\frac{1}{T}\sum^T_{t=1}R_t$. Suppose that \begin{description} • $\mathbb{E}[R^2_t] = \sigma^2_t$, a positive value with $(1/T)\sum^T_{t=1}\sigma^2_t\to\sigma^2$, a positive value; • $\mathbb{E}[|R_t|^r] < \infty$ for some $r>2$; • $(1/T)\sum^{T}_{t=1}R^2_t\xrightarrow{p}\sigma^2$. \end{description} Then $\sqrt{T}\overline{R}_T\xrightarrow{d}\mathcal{N}(\bm{0}, \sigma^2)$.

Here, the martingale CLT requires a mean outcome estimator a asymptotically constant variance, and there are several directions to construct estimators satisfying the conditions. For instance, convergence of the logging policy is an instance. In this paper, because the assumption is too restrictive, we consider more practical assumptions.

Related Work

Compared with studies on mean outcome estimation for i.i.d. samples Horvitz1952,HahnJinyong1998OtRo,hirano2003efficient,Bang2005,dudik2011doubly,narita2019counterfactual,Bibaut2019moreffficient. there are fewer studies on mean outcome estimation for not i.i.d. samples. When the logging policy converges, Laan2008TheCA, Laan2014onlinetml, and Luedtke2016 proposed IPW, AIPW, and DR type estimators mainly for ATE estimation. Laan2008TheCA proposed an A2IPW estimator. Laan2014onlinetml only implied a possibility of an ADR estimator, and kato2020theoreticalcomparison showed it. Without the convergence assumption, the asymptotic normality still can be derived based on batched samples Hahn2011,Laan2014onlinetml and standardization Luedtke2016. Because an A2IPW estimator is unstable, hadad2019 proposed a stabilization method for an A2IPW estimator, and kato2020theoreticalcomparison empirically showed that an ADR estimator is more stable than an A2IPW estimator, which has the same asymptotic distribution.

A semiparametric estimator usually requires Donsker's condition for its $\sqrt{N}$-consistency, where $N$ is a sample size bickel98. For semiparametric inference without Donsker's condition, sample-splitting is a typical approach klaassen1987,ZhengWenjing2011CTME,ChernozhukovVictor2018Dmlf, which is also referred to as cross-fitting. As a variant of the sample-splitting for time-series, Laan2014onlinetml and kato2020theoreticalcomparison proposed adaptive-fitting. Kallus2019IntrinsicallyES also proposed mixingale-based sample-splitting.

Finally, we introduce existing studies in other related topics. Adaptive importance sampling is a sample selection framework for efficient Monte Carlo simulation, similar to adaptive experiments Kloek1978,NAYLOR1988103,evans1988,oh1992,Cappe2008,Portier2018ais. In causal inference, the conditional mean outcome is also a standard target, and Laan2008TheCA and kelly2020batched proposed methods for estimating it. The method of kelly2020batched is a variant of the generalized method of moments for martingales hayashi2000, which is also applied in Laan2014onlinetml. Li2010,Li2011 proposed off-policy policy evaluation of (adaptive) MAB algorithm using i.i.d. samples generated from a random policy.

ADR Estimator when Average logging policy Converges

Let us consider a situation where $\frac{1}{t}\sum^t_{s=1}\pi_s(a\mid x, \Omega_{s-1})$ converges to $\alpha(a\mid x)$ for all $x\in\mathcal{X}$ and $\{\Omega_{s-1}\}^t_{s=1}$ in probability. For this case, we consider an adaptive DR (ADR) estimator $\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e})$ defined as

align*[align* omitted — 230 chars of source]

where $\hat{g}_{t-1}(a\mid x)$ is an estimator of $\frac{1}{t}\sum^t_{s=1}\pi_s(a\mid x, \Omega_{s-1})$ or $\alpha(a\mid x)$, which is constructed only from $\Omega_{t-1}$. For instance, when minimizing the risk with the logistic loss, we can show that the solution is given as $\frac{1}{t}\sum^t_{s=1}\pi_s$. Let us consider the following risk of binary classification problem:

align*[align* omitted — 123 chars of source]

where $p_s(x\mid a=1)$ is the conditional density of $x$ at the period $t$. By taking the derivative and first order condition, the minimizer is given as $h^*(x) = \frac{\frac{1}{t}\sum^t_{s=1}p_s(x\mid a=1)}{p(x)}=\frac{1}{t}\pi_s(a\mid x, \Omega_{s-1})$. By the law of large numbers for martingales, the risk can be approximated by

align*[align* omitted — 117 chars of source]

Therefore, by naively applying the logistic regression for $\{(X_s, A_s)\}^t_{s=1}$, we can obtain the consistent estimator $\hat{g}$. This estimator

Convergence of the Average logging policy

In this paper, we show that even though the assumption does not hold, we can derive the asymptotic normality of a mean outcome estimator under the following alternative assumption that the average logging policy converges in probability.

assumptionFor all $a\in \mathcal{A}$, as $ t \to \infty$, \begin{align*} &\Big\|\frac{1}{t}\sum^t_{s=1}\pi_s(a\mid X, \Omega_{s-1})- \bar{\alpha}(a\mid X)\Big\|_2 \Big\|f^*(a,X)-\hat{f}_{t-1}(a,X)\Big\|_2=\mathrm{o}_{p}(t^{-1/2}),\\ &\|\hat{g}_{t-1}(a\mid X_t) - \bar{\alpha}(a\mid X_t)\|_{2}\|f^*(a,X_t)-\hat{f}_{t-1}(a,X_t)\|_2=\mathrm{o}_{p}(t^{-1/2}), \end{align*} where $\bar{\alpha}: \mathcal{A}\times\mathcal{X}\to(0,1)$ is a time-invariant function such that $\sum^K_{a'=1}\bar{\alpha}(a'\mid x)=1$ for all $x\in\mathcal{X}$ and there exists a constant $C_\alpha$ satisfying $\left| \frac{\pi^\mathrm{e}(a\mid x)}{\alpha(a\mid x)} \right| < C_\alpha$, and the expectation of the norm is defined over $X_t$.

assumptionFor all $a\in \mathcal{A}$, as $ T \to \infty$, \begin{align*} \Bigg|\frac{1}{T}\sum^T_{t=1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\frac{1}{t}\sum^t_{s=1}\pi_s(a\mid X, \Omega_{s-1})} - 1\right)\left(f^*(a, X) - \hat{f}_{t-1}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg| = \mathrm{o}_{p}(T^{-1/2}). \end{align*}

Assumption (ref) is weaker than Assumption (ref) because Assumption (ref) holds under Assumption (ref). Note that under Assumption (ref), the logging policy $\pi_t$ can be deficient; that is $\pi_t$ can be $0$ at a period $t$.

Asymptotic Normality of an ADR Estimator

kato2020theoreticalcomparison derived the asymptotic normality of the ADR estimator under Assumption (ref). In this section, we show the asymptotic normality under Assumption (ref).

theorem[Asymptotic normality of an ADR estimator when average logging policy converges] Under Assumptions (ref), (ref)--(ref) and (ref)--(ref), for the ADR estimator, $\sqrt{T}\left(\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e})-R(\pi^\mathrm{e})\right)\xrightarrow{d}\mathcal{N}\left(0, \Psi(\bar{\alpha})\right)$.

To show Theorem (ref), we decompose $\sqrt{T}\left(\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - R(\pi^\mathrm{e})\right)$ as

align*[align* omitted — 155 chars of source]

where $\ddot{R}_T(\pi^\mathrm{e})$ is defined as

align*[align* omitted — 209 chars of source]

The remaining problems are to show that

align[align omitted — 140 chars of source]

and

align[align omitted — 164 chars of source]

We separately show ((ref)) and ((ref)) in Lemma (ref) and (ref), respectively. First, we show Lemma (ref).

lemmaUnder Assumptions (ref), (ref)--(ref) and (ref)--(ref), $\sqrt{T}\Big(\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - \ddot{R}_T(\pi^\mathrm{e})\Big)=\mathrm{o}_p(1)$

Lemma (ref) is proved by a technique based on sample-splitting, as Laan2014onlinetml and kato2020theoreticalcomparison. Here, we show the sketch of proof. The full proof is shown in Appendix (ref) of the supplementary material.

proof[Sketch of proof] Let us define \begin{align*} &\phi_1(X_t, A_t, Y_t; g, f)=\sum^K_{a=1}\frac{\pi^\mathrm{e}(a\mid X_t)\mathbbm{1}[A_t=a]\left(Y_t - f(a, X_t)\right) }{g(a\mid X_t)},\ \ \ \phi_2(X_t; f)=\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)f(a, X_t). \end{align*} We decompose $\sqrt{T}\Big(\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - \ddot{R}_T(\pi^\mathrm{e})\Big)$ as \begin{align*} &\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - \ddot{R}(\pi^\mathrm{e})=\frac{1}{T}\sum^T_{t=1}\Bigg\{\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \hat{f}_{t-1}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\\ &\ \ \ -\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \hat{f}_{t-1}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right]\\ &\ \ \ + \phi_2(X_t; \hat{f}_{t-1}) - \phi_2(X_t; f^*) -\mathbb{E}\left[\phi_2(X_t; \hat{f}_{t-1}) - \phi_2(X_t; f^*)\mid \Omega_{t-1}\right]\Bigg\}\\ &\ \ \ + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \hat{f}_{t-1})\mid \Omega_{t-1}\right] + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; \hat{f}_{t-1})\mid \Omega_{t-1}\right]\\ &\ \ \ - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right] - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; f^*)\mid \Omega_{t-1}\right]. \end{align*} In the following parts, we separately show that \begin{align} &\sqrt{T}\frac{1}{T}\sum^T_{t=1}\Bigg\{\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \hat{f}_{t-1}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\\ &\ \ \ -\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \hat{f}_{t-1}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right]\nonumber\\ &\ \ \ + \phi_2(X_t; \hat{f}_{t-1}) - \phi_2(X_t; f^*) -\mathbb{E}\left[\phi_2(X_t; \hat{f}_{t-1}) - \phi_2(X_t; f^*)\mid \Omega_{t-1}\right]\Bigg\}= \mathrm{o}_p(1);\nonumber \end{align} and \begin{align} &\frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \hat{f}_{t-1})\mid \Omega_{t-1}\right] + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; \hat{f}_{t-1})\mid \Omega_{t-1}\right]\\ &- \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right] - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; f^*)\mid \Omega_{t-1}\right] = \mathrm{o}_p(1/\sqrt{T}).\nonumber \end{align} To show ((ref)), we show the mean of the LHS of ((ref)) is $0$ and its variance converges to $0$ in probability. To show ((ref)), we use Assumption (ref).

Next, Lemma (ref) provides the asymptotic normality of $\ddot{R}_T(\pi^\mathrm{e})$.

lemmaUnder Assumptions (ref) and (ref), $\sqrt{T}\Big(\ddot{R}_T(\pi^\mathrm{e}) - R(\pi^\mathrm{e})\Big)\xrightarrow{\mathrm{d}}\mathcal{N}\left(0, \Psi(\bar{\alpha}\right)$

Here, we show the sketch of proof. The full proof is shown in Appendix (ref) of the supplementary material.

proof[Sketch of proof] The proof procedure follows Kato2020adaptive. Let $\Gamma_t(a)$ be \begin{align*} \Gamma_t(a; \pi^\mathrm{e}) = \frac{\pi^\mathrm{e}(a\mid X_t)\mathbbm{1}[A_t = a](Y_t(a) - f^*(a\mid X_t))}{\bar{\alpha}(a\mid X_t)} - \pi^\mathrm{e}(a\mid X_t)f^*(a\mid X_t). \end{align*} Note that $\ddot{R}_T(\pi^\mathrm{e}) = \frac{1}{T}\sum^T_{t=1}\sum^K_{a=1}\Gamma_t(a; \pi^\mathrm{e})$. Then, for $Z_t = \sum^K_{a=1}\Gamma_t(a; \pi^\mathrm{e}) - R(\pi^\mathrm{e})$, we want to show that \begin{align*} \sqrt{T}\left(\ddot{R}_T(\pi^\mathrm{e}) - R(\pi^\mathrm{e})\right) = \sqrt{T}\left(\frac{1}{T}\sum^T_{t=1}Z_t\right) \xrightarrow{\mathrm{d}} \mathcal{N}\left(0, \sigma^2\right). \end{align*} Then, the sequence $\{Z_t\}^T_{t=1}$ is an MDS; that is, \begin{align*} &\mathbb{E}\big[Z_t\mid \Omega_{t-1}\big]= \mathbb{E}\left[\sum^K_{a=1}\Gamma_t(a; \pi^\mathrm{e}) - R(\pi^\mathrm{e})\mid \Omega_{t-1}\right] \\ &= \mathbb{E}\left[\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)f^*(a, X_t) - R(\pi^\mathrm{e}_t)\mid \Omega_{t-1}\right]\\ &\ \ \ + \mathbb{E}\left[\sum^K_{a=1}\frac{\pi^\mathrm{e}(a\mid X_t)\mathbbm{1}[A_t = a](Y_t(a) - f^*(a, X_t))}{\bar{\alpha}(A_t\mid X_t)}\mid \Omega_{t-1}\right] \\ &= 0 + \mathbb{E}\left[\mathbb{E}\left[\sum^K_{a=1}\frac{\pi^\mathrm{e}(a \mid X_t)\pi(a\mid X_t, \Omega_{t-1})(f^*(a, X_t) - f^*(a, X_t))}{\bar{\alpha}(a\mid X_t)}\mid X_t, \Omega_{t-1}\right]\mid \Omega_{t-1}\right] = 0. \end{align*} Therefore, to derive the asymptotic distribution, we consider applying the CLT for a MDS introduced in Proposition (ref). There are following three conditions in the statement. \begin{description} • $\mathbb{E}\big[Z^2_t\big] = \nu^2_t > 0$ with $\big(1/T\big) \sum^T_{t=1}\nu^2_t\to \nu^2 > 0$; • $\mathbb{E}\big[|Z_t|^r\big] < \infty$ for some $r>2$; • $\big(1/T\big)\sum^T_{t=1}Z^2_t\xrightarrow{\mathrm{p}} \nu^2$. \end{description} Because we assumed the boundedness of $z_t$ by assuming the boundedness of $Y_t$, $f^*$, and $\pi^\mathrm{e}/\bar{\alpha}$, the condition (b) holds. Therefore, the remaining task is to show the conditions (a) and (c) hold. Here, the convergence of the average logging policy has an important role by making th variance time-invariance asymptotically.

Then, from Lemma (ref) and (ref), we can show Theorem (ref).

Asymptotic Normality of a Modified ADR Estimator

To show the asymptotic normality of an ADR estimator, we need to check Assumption (ref), but it is not easy in practice. In this section, we modify the ADR estimator to guarantee the asymptotic normality more easily. We define a Modified ADR (MADR) $\widetilde{R}^{\mathrm{MADR}}_T(\pi^\mathrm{e})$ as

align*[align* omitted — 247 chars of source]

where $u(T)$ is a function of $T$ and

align*[align* omitted — 166 chars of source]

Then, we put the following assumption.

assumptionThere exists a function $u(T) > 0$ such that for all $a\in \mathcal{A}$, $\frac{u(T)}{\sqrt{T}}\to 0$ as $T\to\infty$, and for $T > u(T)$, \begin{align} &\Bigg\|\frac{1}{T-u(T)-1}\sum^{T}_{t=u(T)+1}\frac{\pi_t(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\Bigg\|_2\Bigg\|f^*(a,X_t)-\hat{f}_{u(T)}(a,X)\Bigg\|_2=\mathrm{o}_{p}(T^{-1/2}),\\ &\frac{1}{T}\sum^T_{u(T)+1}\left\|\frac{1}{t}\sum^{t}_{s=1}\pi_s(a\mid X, \Omega_{s-1}) - \hat{g}_{t-1}(a\mid X_t)\right\|_2\left\|f^*(a, X) - \hat{f}_{u(T)}(a, X)\right\|_2 = \mathrm{o}_{p}(T^{-1/2}), \end{align} where $\bar{\alpha}: \mathcal{A}\times\mathcal{X}\to(0,1)$ is a time-invariant function such that $\sum^K_{a'=1}\bar{\alpha}(a'\mid x)=1$ and there exists a constant $C_\alpha$ satisfying $\left| \frac{\pi^\mathrm{e}(a\mid x)}{\alpha(a\mid x)}\right| < C_\alpha$, and the expectation of the norm is over $X_t$.

Then, we show Lemma (ref) on the asymptotic bias of the MADR estimator.

lemmaUnder Assumptions (ref), (ref)--(ref) and (ref), $\sqrt{T}\Big(\widetilde{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - \ddot{R}_T(\pi^\mathrm{e})\Big)=\mathrm{o}_p(1)$

proof[Sketch of proof] By using $\phi_1(X_t, A_t, Y_t; g, f)$ and $\phi_2(X_t; f)=\sum^K_{a=1}\pi^\mathrm{e}(a\mid X_t)f(a, X_t)$ defined in the proof of Lemma (ref), we decompose $\sqrt{T}\Big(\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - \ddot{R}_T(\pi^\mathrm{e})\Big)$ as \begin{align*} &\widehat{R}^{\mathrm{ADR}}_T(\pi^\mathrm{e}) - \ddot{R}(\pi^\mathrm{e})=\frac{1}{T}\sum^T_{t=1}\Bigg\{\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\\ &\ \ \ -\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right]\\ &\ \ \ + \phi_2(X_t; \tilde{f}_{t-1,u(T)}) - \phi_2(X_t; f^*)\\ &\ \ \ -\mathbb{E}\left[\phi_2(X_t; \tilde{f}_{t-1,u(T)}) - \phi_2(X_t; f^*)\mid \Omega_{t-1}\right]\Bigg\}\\ &\ \ \ + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)})\mid \Omega_{t-1}\right]\\ &\ \ \ + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; \tilde{f}_{t-1,u(T)})\mid \Omega_{t-1}\right]\\ &\ \ \ - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right]\\ &\ \ \ - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; f^*)\mid \Omega_{t-1}\right]. \end{align*} Following the almost same process as the proof of Lemma (ref), we can show that \begin{align*} &\sqrt{T}\frac{1}{T}\sum^T_{t=1}\Bigg\{\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\\ &\ \ \ -\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)}) - \phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right]\nonumber\\ &\ \ \ + \phi_2(X_t; \tilde{f}_{t-1,u(T)}) - \phi_2(X_t; f^*)\\ &\ \ \ -\mathbb{E}\left[\phi_2(X_t; \tilde{f}_{t-1,u(T)}) - \phi_2(X_t; f^*)\mid \Omega_{t-1}\right]\Bigg\}= \mathrm{o}_p(1);\nonumber \end{align*} Therefore, we consider showing \begin{align} &\frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)})\mid \Omega_{t-1}\right]\\ &\ \ \ + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; \tilde{f}_{t-1,u(T)})\mid \Omega_{t-1}\right]\nonumber\\ &\ \ \ - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right]\\ &\ \ \ - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; f^*)\mid \Omega_{t-1}\right] = \mathrm{o}_p(1/\sqrt{T}). \end{align} If ((ref)) holds, then we can prove the statement. First, as shown in the proof of Lemma (ref), we bound the LHS of ((ref)) as follows: \begin{align} &\frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \hat{g}_{t-1}, \tilde{f}_{t-1,u(T)})\mid \Omega_{t-1}\right] + \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; \tilde{f}_{t-1,u(T)})\mid \Omega_{t-1}\right]\nonumber\\ &\ \ \ - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_1(X_t, A_t, Y_t; \bar{\alpha}, f^*)\mid \Omega_{t-1}\right] - \frac{1}{T}\sum^T_{t=1}\mathbb{E}\left[\phi_2(X_t; f^*)\mid \Omega_{t-1}\right] = \mathrm{o}_p(1/\sqrt{T})\nonumber\\ &\leq \Bigg|\frac{1}{T}\sum^T_{t=1} \mathbb{E}\Bigg[\frac{\pi^\mathrm{e}(a\mid X)\Big(\pi_{t}(a\mid X, \Omega_{t-1}) - \hat{g}_{t-1}(a\mid X)\Big)\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) }{\hat{g}_{t-1}(a\mid X)} \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &\leq \Bigg|\frac{1}{T}\sum^T_{t=1} \mathbb{E}\Bigg[\frac{\pi^\mathrm{e}(a\mid X)\Big(\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \hat{g}_{t-1}(a\mid X)\Big)\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) }{\hat{g}_{t-1}(a\mid X)} \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &\ + \Bigg|\frac{1}{T}\sum^T_{t=1} \mathbb{E}\Bigg[\frac{\pi^\mathrm{e}(a\mid X)\Big(\pi_{t}(a\mid X, \Omega_{t-1}) - \frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})\Big)\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) }{\hat{g}_{t-1}(a\mid X)} \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &\leq \frac{C}{T}\sum^T_{t=1} \Bigg|\mathbb{E}\Bigg[ \left(\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \hat{g}_{t-1}(a\mid X)\right)\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right)\mid \Omega_{t-1}\Bigg]\Bigg|\\ &\ \ \ + \Bigg|\frac{1}{T}\sum^T_{t=1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|, \end{align} where $C > 0$ is a constant. We can show that the first term ((ref)) converges with $\mathrm{o}_{p}(T^{-1/2})$. By using the {H\"{o}lder}'s inequality $\|\mu\nu \|_1 \leq \|\mu \|_2 \|\nu \|_2$, \begin{align*} & \frac{1}{T}\sum^T_{t=1} \Bigg|\mathbb{E}\Bigg[ \left(\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \hat{g}_{t-1}(a\mid X)\right)\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right)\mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ & \leq \frac{1}{T}\sum^T_{t=1}\left\|\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \hat{g}_{t-1}(a\mid X)\right\|_2\left\|f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right\|_2\nonumber\\ &\leq \frac{1}{T}\sum^T_{t=1}\left(\left\|\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \bar{\alpha}(a\mid X)\right\|_2 + \left\|\bar{\alpha}(a\mid X) - \hat{g}_{t-1}(a\mid X)\right\|_2\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times \left\|f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right\|_2\\ &= \frac{1}{T}\sum^T_{t=1}\Bigg(\left\|\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \bar{\alpha}(a\mid X)\right\|_2\left\|f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right\|_2\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \left\|\bar{\alpha}(a\mid X) - \hat{g}_{t-1}(a\mid X)\right\|_2\left\|f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right\|_2\Bigg). \end{align*} From the definition of $u(T)$, we can bound it as \begin{align*} &\frac{1}{T}\sum^{u(T)}_{t=1}\Bigg(\left\|\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \bar{\alpha}(a\mid X)\right\|_2\left\|f^*(a, X) - \hat{f}_{t-1}(a, X)\right\|_2\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \left\|\bar{\alpha}(a\mid X) - \hat{g}_{t-1}(a\mid X)\right\|_2\left\|f^*(a, X) - \hat{f}_{t-1}(a, X)\right\|_2\Bigg)\\ &\ \ \ + \frac{1}{T}\sum^T_{t=u(T)+1}\Bigg(\left\|\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1}) - \bar{\alpha}(a\mid X)\right\|_2\left\|f^*(a, X) - \hat{f}_{u}(a, X)\right\|_2\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \left\|\bar{\alpha}(a\mid X) - \hat{g}_{t-1}(a\mid X)\right\|_2\left\|f^*(a, X) - \hat{f}_{u}(a, X)\right\|_2\Bigg)\\ & \leq C \frac{u(T)}{T} + \frac{1}{T}\sum^{T}_{t=u(T)+1}\mathrm{o}_{p}(T^{-1/2}) +\frac{1}{T}\sum^{T}_{t=u(T)+1}\mathrm{o}_{p}(T^{-1/2})\\ & = \mathrm{o}_{p}(T^{-1/2}) + \mathrm{o}_{p}(T^{-1/2}) = \mathrm{o}_{p}(T^{-1/2}), \end{align*} where $C > 0$ is a constant. Next, we show that the second term ((ref)) converges with $\mathrm{o}_{p}(T^{-1/2})$. By using $u(T)$ of the statement, we have \begin{align} &\Bigg|\frac{1}{T}\sum^T_{t=1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &\leq \Bigg|\frac{1}{T}\sum^{u(T)}_{t=1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times \left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\\ &\ \ \ + \Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times \left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|. \end{align} Because all variables are bounded, for a constant $C > 0$, the first term ((ref)) is bounded as \begin{align*} &\Bigg|\frac{1}{T}\sum^{u(T)}_{t=1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\\ &\leq C\frac{u(T)}{T}. \end{align*} Here, from the definition of $u(T)$, $\frac{u(T)}{\sqrt{T}}\to 0$ as $T\to \infty$. Then, we consider bounding the second term ((ref)). First, we bound it as \begin{align} &\Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{t-1,u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &=\Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &=\Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\right)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &\ \ \ + \Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(1 - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\nonumber\\ &\leq \Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\\ &\ \ \ + \frac{1}{T}\sum^T_{t=u(T)+1} \Bigg|\mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(1 - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\nonumber\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|. \end{align} We separately bound ((ref)) and ((ref)). First, we bound ((ref)). By using the {H\"{o}lder}'s inequality $\|\mu\nu\|_1 \leq \|\mu \|_2 \|\nu \|_2$, \begin{align*} &\Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\right)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\\ &=\Bigg|\frac{1}{T}\sum^T_{t=u(T)+1} \mathbb{E}_X\Bigg[\pi^\mathrm{e}(a\mid X)\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\right)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right)\Bigg]\Bigg|\\ &=\Bigg|\mathbb{E}_X\Bigg[\pi^\mathrm{e}(a\mid X)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right)\frac{1}{T}\sum^T_{t=u(T)+1}\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\right)\Bigg]\Bigg|\\ &\leq \frac{T-u(T)-1}{T}\Bigg\|\pi^\mathrm{e}(a\mid X)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right)\Bigg\|_2\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \times \Bigg\|\frac{1}{T-u(T)-1}\sum^T_{t=u(T)+1}\left(\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\right)\Bigg\|_2\\ &\leq C\Bigg\|f^*(a, X) - \tilde{f}_{u(T)}(a, X)\Bigg\|_2\Bigg\|\frac{1}{T-u(T)-1}\sum^T_{t=u(T)+1}\frac{\pi_{t}(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\Bigg\|_2, \end{align*} where $\mathbb{E}_X$ denotes the expectation over $X$ and $C > 0$ is a constant. Then, we have $(\ref{eq:bound:term1})=\mathrm{o}_{p}(T^{-1/2})$ from Assumption (ref). Second, by using Assumption (ref), we show that ((ref)) is $\mathrm{o}_{p}(T^{-1/2})$ as \begin{align*} &\frac{1}{T}\sum^T_{t=u(T)+1} \Bigg|\mathbb{E}\Bigg[\pi^\mathrm{e}(a\mid X)\left(1 - \frac{\frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})}{\hat{g}_{t-1}(a\mid X)}\right)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\\ &\leq \frac{C}{T}\sum^T_{t=u(T)+1} \Bigg|\mathbb{E}\Bigg[\left(\hat{g}_{t-1}(a\mid X) - \frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})\right)\left(f^*(a, X) - \tilde{f}_{u(T)}(a, X)\right) \mid \Omega_{t-1}\Bigg]\Bigg|\\ &\leq \frac{C}{T}\sum^T_{t=u(T)+1} \Bigg\|\hat{g}_{t-1}(a\mid X) - \frac{1}{t}\sum^t_{s=1}\pi_{s}(a\mid X, \Omega_{s-1})\Bigg\|_2\Bigg\|f^*(a, X) - \tilde{f}_{u(T)}(a, X)\Bigg\|_2. \end{align*} Then, the term is $\mathrm{o}_{p}(T^{-1/2})$ from Assumption (ref).

By using Lemma (ref) and (ref), we can show the following theorem.

theorem[Asymptotic normality of $\widetilde{R}^{\mathrm{MADR}}_T(\pi^\mathrm{e})$] For $u(t) > 0$ such that $\frac{u(T)}{\sqrt{T}}\to 0$, under Assumptions (ref), (ref)--(ref) and (ref), MADR estimator has the asymptotic normality as \begin{align*} \sqrt{T}\left(\widetilde{R}^{\mathrm{MADR}}_T(\pi^\mathrm{e})-R(\pi^\mathrm{e})\right)\xrightarrow{d}\mathcal{N}\left(0, \Psi(\bar{\alpha}\right). \end{align*}

Unlike an ADR estimator, a MADR estimator does not require Assumption (ref). This property is an advantage from the theoretical viewpoint. However, as shown in experiments, an ADR estimator shows better empirical performance. The remaining problem is to check that standard estimators satisfy Assumption (ref). Here, we show an example where nuisance estimators satisfy the requirement. For instance, we consider $u(T) = T^{1/3}$, which satisfies $\frac{u(T)}{\sqrt{T}}\to 0$ as $T\to\infty$. Under some conditions, sample averages and regression estimators have $\mathrm{O}_{p}(T^{-1/2})$ convergence rate. Therefore, we can assume that there exist $p, q, r<1/2$ such that

align[align omitted — 341 chars of source]

Here, note that $\Bigg\|\frac{1}{T-u(T)-1}\sum^{T}_{t=u(T)+1}\frac{\pi_t(a\mid X, \Omega_{t-1})}{\hat{g}_{t-1}(a\mid X)} - 1\Bigg\|_2$ is bounded by

align*[align* omitted — 368 chars of source]

Therefore, we can assume ((ref)) by assuming $\Bigg\|\frac{1}{T-u(T)-1}\sum^{T}_{t=u(T)+1}\pi_t(a\mid X, \Omega_{t-1}) - \bar{\alpha}(a\mid X)\Bigg\|_2=\mathrm{o}_{p}(T^{-p})$ and $\Big\|\bar{\alpha}(a\mid X) - \hat{g}_{t-1}(a\mid X)\Big\|_2=\mathrm{o}_{p}(T^{-p})$. Then, we have $(\ref{eq:con1}) = \mathrm{o}_{p}(T^{-p})\mathrm{o}_{p}(u(T)^{-q}) = \mathrm{o}_{p}(T^{-p})\mathrm{o}_{p}((T^{1/3})^{-q})=\mathrm{o}_{p}(T^{-p}(T^{1/3})^{-q})=\mathrm{o}_{p}(T^{-(p+q/3)})$. In this case, for instance, if $p=7/18 (< 1/2)$ and $q=1/3$, we obtain $(\ref{eq:con1}) = \mathrm{o}_{p}(T^{-1/2})$. Similarly, we have $(\ref{eq:con2}) = \mathrm{o}_{p}(u(T)^{-q})\mathrm{o}_{p}(t^{-r}) = \mathrm{o}_{p}(T^{-q/3})\frac{1}{T}\sum^T_{t=1}\mathrm{o}_{p}(t^{-r})$. By a property of Riemann Zeta function, $\frac{1}{T}\sum^T_{t=1}\mathrm{o}_{p}(t^{-r}) = \mathrm{o}_{p}(T^{-r})$ Hence, if $r=7/18$ and $q=1/3$, we can show that $(\ref{eq:con2}) = \mathrm{o}_{p}(T^{-r-q/3}) = \mathrm{o}_{p}(T^{-1/2})$.

Monte Carlo Experiments

To investigate the empirical properties of ADR and Modified ADR (MADR) estimators, we simulate two situations based on whether the logging policy converges, where the average logging policy converges in all experiments. We compare ADR and MADR estimators with an IPW estimator with the true logging policy (IPW), IPW estimator with an estimated logging policy (EIPW), AIPW estimator without cross fitting (AIPW), DM estimator (DM), DR estimator without cross fitting (DR), and A2IPW estimator with the true logging policy (A2IPW). We also consider estimators with the following form:

align*[align* omitted — 251 chars of source]

When using $\hat{f} = \hat{f}_{t-1}$, we call it Average A2IPW (A3IPW) estimator; when using $\hat{f} = \tilde{f}_{t-1, u(T)}$, we call it an Modified A3IPW (MA3IPW) estimator. These estimators are special cases of ADR and MADR estimators where using $\frac{1}{t}\sum^{t}_{s=1}\pi_{s}(a\mid X_t, \Omega_{s-1})$ for $\hat{g}_{t-1}$. Note that only the ADR, MADR, EIPW, and DM estimators are applicable even when the true logging policy is unknown among these estimators. In addition, to the best of our knowledge, the EIPW, AIPW, and DR estimators are not shown to be asymptotically normal. When the logging policy does not converge to a time-invariant function, the A2IPW estimator also does not have the asymptotic normality. When the average logging policy converges and convergence rate conditions hold, the MADR and MA3IPW estimators have asymptotic normality. For the asymptotic normalities of ADR and MADR estimator, we need Assumption (ref), which is not easy to be confirmed.

figure[figure omitted — 288 chars of source]

Experiments with a Fluctuating logging policy

table[table omitted — 1,320 chars of source]

In this section, we conduct adaptive experiments for efficient ATE estimation following Laan2008TheCA and Hahn2011. For brevity, we consider a situation where there are two actions and no covariates; that is, there is no sample selection bias based on $p_t(a\mid x)$. We generate a pair of potential outcomes $(Y_t(1), Y_t(2),)$, where $Y_t(a)$ is generated from the normal distribution $\mathcal{N}(a, a)$. Let us define an ATE by defining an evaluation weight as $\pi^\mathrm{e}(1) = -1$ and $\pi^\mathrm{e}(2) = 1$. Laan2008TheCA and Hahn2011 showed that we can achieve the minimum asymptotic variance when choosing an action $1$ following a probability $\pi^*(1) = \frac{\sqrt{\mathrm{Var}(Y_t(1))}}{\sqrt{\mathrm{Var}(Y_t(1))} + \sqrt{\mathrm{Var}(Y_t(2))}}$ and the other action following $\pi^*(2) = 1-\pi^*(1)$. However, because we do not know $\mathrm{Var}(Y_t(a))$, we need to consider obtaining an estimator with the same asymptotic distribution as the one obtained under an optimal logging policy $\pi^*$. In this paper, we select an action with probability $1$ so that the ratio of $\sum^T_{t=1}\pi_1(1) = \sum^T_{t=1}\mathbbm{1}[A_t = 1]$ and $\sum^T_{t=1}\pi_1(2) = \sum^T_{t=1}\mathbbm{1}[A_t = 2]$ is $\frac{\sqrt{\mathrm{Var}(Y_t(1))}}{\sqrt{\mathrm{Var}(Y_t(1))} + \sqrt{\mathrm{Var}(Y_t(2))}} : \frac{\sqrt{\mathrm{Var}(Y_t(2))}}{\sqrt{\mathrm{Var}(Y_t(1))} + \sqrt{\mathrm{Var}(Y_t(2))}}$. If the average logging policy converges to $\tilde{\alpha}(a) = \pi^*(a)$, the asymptotic distribution of and ADR estimator is the same as that of an estimator obtained when choosing an action $a$ with a probability $\pi^*(a)$. To keep the desirable ratio, at each period $t$, we estimate the standard deviation $\mathrm{Var}(Y_t(a))$ using $\Omega_{t-1}$. Next, we construct an estimator $\hat{\pi}^*(a)$ of $\pi^*(a)$. If $\sum^T_{t=1}\mathbbm{1}[A_t = 1]\leq \hat{\pi}^*(a)$, we choose $A_t = 1$; otherwise, $A_t = 2$. We conduct this procedure for three cases with different sample sizes $T=250, 500, 750$. We conduct $100$ trials and calculate the root MSEs (RMSEs), the standard deviations of MSEs (SDs), and the coverage ratios (CRs) of the $95\%$ confidence interval; that is, a percentage that the confidence interval covers the true value. The results are shown in Table (ref) and Figure (ref). These results imply that the proposed estimators successfully estimate the mean outcome, although the EIPW estimator shows significantly bad performance. The DM estimator seems to estimate it well, but the confidence interval does not work, as the coverage ratio shows. In addition, in this experiment, we assume that there is no covariate for brevity. However, as the experiment of Section (ref), if there is a sample selection bias owing to a covariate-dependent logging policy, the DM estimator's performance relatively decreases. The ADR, MADR, A3IPW, and MA3IPW estimators have the same asymptotic distribution under appropriate conditions. Although the performances of A2IPW and MA3IPW are superior to ADR and MADR estimators, the estimators are applicable only when the true logging policy is known.

Experiments with a Converging logging policy

Next, we investigate the performances of the estimators for logging policies that converge to a time-invariant function. 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\}$, 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 logging policy $\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 the dataset $\mathcal{S}^{(1)}_{T_{(1)}}$. Then, we apply the evaluation policy $\pi^\mathrm{e}$ on the independent dataset $\mathcal{S}^{(2)}_{T_{(2)}}$, and artificially construct bandit data $\{(X'_t, A'_t, Y'_t)\}^{T_{(2)}}_{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})$ as $\frac{1}{T_{(2)}}\sum^{T_{(2)}}_{t=1}Y^{(m)}_t$. Next, using the datasets $\mathcal{S}^{(3)}_{T_{(3)}}$ and a MAB algorithm, we generate a bandit dataset as $\mathcal{S}=\{(X_t, A_t, Y_t)\}^{T_{(3)}}_{t=1}$. For the dataset $\mathcal{S}$, we apply the IPW estimator with the true logging policy, IPW estimator with estimated logging policy, AIPW estimator with cross fitting, DM estimator, DR estimator with cross fitting, A2IPW estimator, and ADR estimator. For estimating $\hat{f}$ and $\hat{g}$, we use the kernelized Ridge least squares and kernelized Ridge logistic regression, respectively. We use the Gaussian kernel for the kernel, and the hyper-parameters of the regularization and the kernel are chosen from $\{0.01, 0.1, 1\}$. Let us define an estimation error as $R(\pi^\mathrm{e}) - \widehat{R}(\pi^\mathrm{e})$. We conduct six experiments by changing the sample size and the MAB algorithms. For the sample size $T_{(3)}$, we use $250$, $500$, and $750$. For each sample size, we apply the LinUCB and LinTS algorithms. For the sample size $T_{(1)}$ and $T_{(2)}$, we use $1,000$ and $100,000$, respectively. For $100$ trials, we show the average root MSEs (RMSEs), the standard deviations of MSEs (SDs), and the coverage ratios (CRs) of the $95\%$ confidence interval. The results are shown in Table (ref) and Figure (ref). Among the estimators, the DR and ADR estimators achieve lower MSEs well, but only the ADR estimator is shown to be asymptotically normal when samples are dependent. Although the IPW estimator returns confidence intervals with a coverage ratio near $95\%$, the MSE is larger than DR-type estimators. Unlike the experiments with a fluctuating logging policy, the DM estimator does not perform owing to the estimation error of $f^*$. Note that the previous experiment, there is no covariate and no sample selection bias caused by $p_t(a\mid x)$. Hence, in this case, it is easy to estimate $f^*$. Here note that the A3IPW and MA3PIPW estimators require the true logging policy, unlike the ADR and MADR estimators.

figure[figure omitted — 570 chars of source]

table[table omitted — 2,796 chars of source]

Discussion

We discuss the remaining problems. First, we consider a paradox of using an estimated logging policy. hadad2019 pointed out an A2IPW estimator's unstable behavior using samples obtained from a MAB algorithm. On the other hand, kato2020theoreticalcomparison pointed out that the ADR estimator experimentally shows better performance than the A2IPW estimator even though their asymptotic properties are the same. This paper points out that estimating the logging policy is equivalent to estimating the average logging policy. In our experiment, directly using the average logging policy for an A2IPW estimator also improves the performance. Therefore, we conjecture that an ADR estimator's stabilization effect comes from the stability of the average logging policy.

Unlike an A2IPW estimator with the true logging policy, an ADR estimator does not suffer the deficient support problem Sachdeva2020. In many cases of MAB algorithms, the logging policy $\pi_t$ often becomes $0$. However, even if $\pi_t$ becomes $0$, we can show the asymptotic normality under Assumption (ref).

Next, in addition to the double robustness on the consistency, we explain the importance of the DR-type estimators' form. We showed the asymptotic normality only for the DR-type estimator. Readers may feel that we can show the other type estimators' asymptotic normality, such as an IPW-type estimator. However, it is not obvious how we use this paper's inference strategy to such estimators. As ChernozhukovVictor2018Dmlf discussed, the DR-type estimators relax the condition for asymptotic normality when using sample-splitting. The asymptotic normalities of our proposed estimators are also based on this property. Therefore, the form of the DR-type estimators is also essential.

Finally, Luedtke2016 pointed out that it is difficult to show the asymptotic normality when using a non-unique optimal treatment strategy; that is, $\pi_t$ fluctuates and does not converge. This problem is also partially solved in our proposed method if Assumption (ref) holds. For instance, in BAI, kaufman2016complexity proposed an algorithm that they deterministically choose an arm with a probability $1$ to keep some optimal selection ratio of arms. In this case, in addition to the deficient support problem, there is no unique treatment strategy. However, because the algorithm attempts to keep some desirable ratio, we can apply our method under Assumption (ref). We derived the asymptotically normal mean outcome estimator for dependent samples based on a new assumption that the average logging policy converges to a time-invariant function in probability. We can regard the average logging policy as a propensity score of inverse probability weighting under this setting. On the other hand, existing studies need to assume that the logging policy itself converges and use the logging policy as a propensity score. We also experimentally confirmed that the inverse weighting using the average logging policy is more stable than the A2IPW estimator, which uses the true logging policy itself.

Conclusion

We derived the asymptotically normal mean outcome estimator for dependent samples based on a new assumption that the average logging policy converges to a time-invariant function in probability. We can regard the average logging policy as a propensity score of inverse probability weighting under this setting. On the other hand, existing studies need to assume that the logging policy itself converges and use the logging policy as a propensity score. We also experimentally confirmed that the inverse weighting using the average logging policy is more stable than using the logging policy itself.