The Adaptive Doubly Robust Estimator and a Paradox Concerning Logging Policy
Year: 2022

Abstract:
The doubly robust (DR) estimator, which consists of two nuisance parameters, the conditional mean outcome and the logging policy (the probability of choosing an action), is crucial in causal inference. This paper proposes a DR estimator for dependent samples obtained from adaptive experiments. To obtain an asymptotically normal semiparametric estimator from dependent samples with non-Donsker nuisance estimators, we propose adaptive-fitting as a variant of sample-splitting. We also report an empirical paradox that our proposed DR estimator tends to show better performances compared to other estimators utilizing the true logging policy. While a similar phenomenon is known for estimators with i.i.d. samples, traditional explanations based on asymptotic efficiency cannot elucidate our case with dependent samples. We confirm this hypothesis through simulation studies.

heading: 1 Introduction
text: Adaptive experiments, including efficient treatment effect estimation (van der Laan, 2008; Hahn et al., 2011), treatment regimes (Zhang et al., 2012a; Zhao et al., 2012), and multi-armed bandit (MAB) problems (Gittins, 1989; Lattimore & Szepesvári, 2020), are widely accepted and used in real-world applications, for example, in social experiments (Hahn et al., 2011), online advertisement (Zhang et al., 2012b), clinical trials (Chow & Chang, 2011; Villar, 2018), website optimization (White, 2012), and recommendation systems (Li et al., 2010). 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 (the probability of choosing an action: Li et al., 2010, 2011). Among several off-line evaluation criteria, this paper focuses on off-policy value estimation (OPVE: Li et al., 2015). 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 (Hirano et al., 2003; Bang & Robins, 2005).
In OPVE, when the true logging policy is known, there are mainly three types of estimators: inverse probability weighting (IPW: Horvitz & Thompson, 1952), direct method (DM), and augmented IPW (AIPW Bang & Robins, 2005) 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 3. 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 (i.i.d.: Hirano et al., 2003; Dudík et al., 2011), adaptive experiments usually allow logging policies to be updated based on past observations, under which the generated samples are non-i.i.d.
∗masahiro_kato@cyberagent.co.jp
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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√ T -rate confidence intervals, where T is the sample size. For this problem, van der Laan (2008) proposed an asymptotically normal AIPW estimator under dependent samples, with several follow-up studies, including Luedtke & van der Laan (2016, 2018), Hadad et al. (2021), Kato et al. (2020), and Zhan et al. (2021). However, a DR-type estimator for dependent samples has not been formally proposed, despite its importance.
Readers might think that, in many experimental designs, the experiment can be manipulated by the experimenter, thus the information of the logging policy is always accessible. However, the logging policy is often not recorded. This is because it is costly to do so in adaptive experiments, since we need to preserve a policy for each sample. Consider the case of Thompson sampling, where we select the arm with the highest expected reward sampled from the posterior distribution (Thompson, 1933). In this case, if we want to know the logging policy, we need to calculate the probability that each arm is chosen from the posterior distribution. The calculation of this probability is not necessary for the bandit algorithm itself, but is an additional task for policy evaluation. In addition, to compute the logging policy, we not only need to record the information of the posterior distribution, but also need to calculate the probability by Monte Carlo simulation from the posterior distribution, if no analytical solution is available. This is a difficult task in terms of both computational volume and computational resource. Moreover, in adaptive experiments in industry (e.g. AB tests), the number of logs is often in the order of several million. In such cases, storing the logging policy is also a difficult task. By using DR-type estimators, we can alleviate this cost. Further, as we report below as a paradox, it is even possible that DR-type estimators, that do not use the true logging policy, outperform estimators using the true logging policy,
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 central limit theorem (CLT) for i.i.d. or martingale difference sequences directly, as done in van der Laan (2008), Hadad et al. (2021), and Kato et al. (2020). 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 (Chernozhukov et al., 2018). 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.
(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.
(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 samplesplitting (Chernozhukov et al., 2018) 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.
(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 (Hahn, 1998; Henmi & Eguchi, 2004). However, we cannot explain our paradox from a conventional semiparametric efficiency perspective (Hahn, 1998; Hirano et al., 2003),
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.
Organization of this paper. In Section 2, we formulate our problem. In Section 3, we introduce existing OPVE estimators for dependent samples. In Section 4, 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 5. In Section 6, we report a paradox through simulation studies and explain the cause of this phenomenon. In Section 7, we conduct experiments using benchmark datasets.

heading: 2 Problem setting
text: Suppose that there is a time series 1, 2, . . . , T , and denote the set as [T ] = {1, . . . , T}. For t ∈ [T ], let At be an action in A = {1, 2, . . . ,K}, Xt be a covariate observed by a decision maker when choosing an action, and X be its space. Following the Neyman–Rubin causal model (Rubin, 1974), let a reward at period t be Yt = ∑K a=1 1[At = a]Yt(a), where Yt(a) : A → R is a potential (random)
outcome. In summary, we have a dataset { (Xt, At, Yt) }T t=1
with the following data-generating process (DGP):
Step 1: we observe a covariate Xt ∼ p(x); Step 2: we choose At = a with probability pt(a|x);
Step 3: we observe an outcome Yt = ∑K a=1 1[At = a]Yt(a), where Yt(a) ∼ pa(y|x),
where p(x) denotes the density of the covariate Xt, pt(a|x) denotes the probability of choosing an action a conditional on a covariate x at period t, and pa(y|x) denotes the density of a reward Yt(a) conditional on a covariate x. We assume that p(x) and pa(y|x) are invariant across periods, and Xt and Yt(a) are drawn from these densities independently of the other period random variables; that is, {(Xt, Yt(1), . . . , Yt(K))}Tt=1 is i.i.d., but pt(a|x) can take different values across periods based on past observations. In this case, the samples { (Xt, At, Yt) }T t=1
are correlated over time, that is, the samples are not i.i.d. Let Ωt−1 = {Xt−1, At−1, Yt−1, . . . , X1, A1, Y1} be the history andMt−1 be a set of possible histories until the t-th period. The probability pt(a|x) is determined by a logging policy πt : A× X ×Mt−1 → (0, 1), such that ∑K a=1 πt(a|x,Ωt−1) = 1, which is a function of a covariate Xt, an action At, and history Ωt−1. We also assume that πt is conditionally independent of Yt(a) to satisfy unconfoundedness (Remark 2). Remark 1 (Stable unit treatment value assumption (SUTVA)). The DGP implies SUTVA; that is, pa(y|x) is invariant to random assignments in other periods (Angrist et al., 1996). Remark 2 (Unconfoundedness). In this paper, unconfoundedness refers to independence between (Yt(1), . . . , Yt(K)) and At, conditional on Xt and Ωt−1, which is required for identification.

heading: 2.1 OPVE
text: The goal of OPVE is to estimate the expected value of the sum of the outcomes Yt(a) weighted by an evaluation function πe : A×X → R; that is,
R(πe) := E(Xt,Yt(1),...,Yt(K)) [ K∑ a=1 πe(a|Xt)Yt(a) ] ,
where the expectation E(Xt,Yt(1),...,Yt(K)) is taken over (Xt, Yt(1), . . . , Yt(K)). We denote it as E, when there is no ambiguity. As with Dudík et al. (2011), the evaluation function is usually referred to as an evaluation policy, where πe(a|x) ∈ [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 A = {1, 2}, where πe(1|x) = 1 and πe(2|x) = −1. To identify R(πe), we assume the overlap in the distributions of policies, convergence of πt−1, and the boundedness of reward. Assumption 1. For all t ∈ [T ], a ∈ A, x ∈ X , and Ωt−1 ∈Mt−1, there exists a constant Cπ > 0, such that
∣∣∣ πe(a|x)πt(a|x,Ωt−1) ∣∣∣ ≤ Cπ . Assumption 1 equivalently means that πt(a|x) > 0 for all a ∈ A and x ∈ X .
Assumption 2. For all x ∈ X and a ∈ A, πt(a|x,Ωt−1)− π̃(a|x) p−→ 0, where π̃ : A×X → (0, 1).
Assumption 3. For all t ∈ [T ] and a ∈ A, there exists a constant CY > 0, such that |Yt(a)| ≤ CY .
Although the reader may feel that Assumption 1–2 and the SUTVA 1 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 (Kato, 2021).

heading: 2.2 Notations
text: We denote E[Yt(a)|x] and Var(Yt(a)|x) as f∗(a, x) and v∗(a, x), respectively. Let f̂t(a, x) be an estimator of f∗(a, x) constructed from Ωt. Let N (µ, var) be the normal distribution with the mean µ and the variance var. For a random variable Z with density p(z) and function µ, let
‖µ(Z)‖2 = ( ∫ |µ(z)|2p(z)dz )1/2 be the L2-norm.

heading: 3 Preliminaries of OPVE

heading: 3.1 Existing estimators
text: For estimating R(πe) from dependent samples, existing studies propose various estimators. An adaptive version of the IPW estimator is defined as RIPWT (π e) = 1T ∑T t=1 ∑K a=1 πe(At|Xt)1[At=a]Yt πt−1(At|Xt,Ωt−1) . If the model specification is correct, the direct method (DM) estimator RDMT (π e) = 1 T ∑T t=1 ∑K a=1 π
e(a|x)f̂T (a|Xt) is known to be consistent to R(πe). As an adaptive version of the AIPW estimator, van der Laan (2008) proposed an estimator R̂AIPWT (π e) defined as
1
T T∑ t=1 K∑ a=1
{ πe(a|Xt)1[At = a] ( Yt − f̂t−1(a,Xt) ) πt−1(a|Xt,Ωt−1) + πe(a|Xt)f̂t−1(a,Xt) } .
Using the martingale property, van der Laan (2008) showed asymptotic normality under Assumption 2.

heading: 3.2 Asymptotic efficiency
text: 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 described in Section 2. As with the Cramér-Rao lower bound for the parametric model, we can also define the lower bound for the non- or semiparametric model (Bickel et al., 1998). The semiparametric lower bound of the DGP under p1(a|x) = · · · = pT (a|x) = p(a|x) is given as follows (Hahn, 1998; Narita et al., 2019):
Ψ(πe, p) = E [ K∑ a=1 ( πe(a|Xt) )2 v∗(a,Xt) p(a|Xt) + ( K∑ a=1 πe(a|Xt)f∗(a,Xt)−R(πe) )2 ] .
The asymptotic variance of the asymptotic distribution is also known as the asymptotic mean squared error (MSE); that is, an OPVE estimator R̂T achieving the semiparametric lower bound also minimizes the MSE to the true value R(πe), E [( R̂T −R(πe) )2] , not just obtaining a tight
confidence interval.

heading: 3.3 Related work
text: There are various studies related to OPVE, including ATE estimation, under the assumption that samples are i.i.d. (Hahn, 1998; Hirano et al., 2003; Dudík et al., 2011; Wang et al., 2017b; Narita et al., 2019; Bibaut et al., 2019; Oberst & Sontag, 2019). There are also several studies extending these methods to OPVE from dependent samples (van der Laan, 2008; van der Laan & Lendle, 2014; Luedtke & van der Laan, 2016, 2018; Hadad et al., 2021; Kato et al., 2020; Zhang et al., 2020, 2021; Zhan et al., 2021; Bibaut et al., 2021).
The AIPW estimator for dependent samples are proposed by van der Laan (2008). van der Laan & Lendle (2014) and Luedtke & van der Laan (2016) proposed an OPVE method without the convergence of the logging policies by using batches and standardization, respectively. Hadad et al. (2021) and Zhan et al. (2021) extended the method of Luedtke & van der Laan (2016) and proposed using an evaluation weight to stabilize the estimator and to evaluate regret minimization algorithms, where the logging policy converges to 0 for sub-optimal arms. The former shares a similar motivation with weight clipping, or shrinkage, when i.i.d. samples are given (Bembom & van der Laan, 2008; Bottou et al., 2013; Wang et al., 2017a; Su et al., 2019, 2020). Howard et al. (2021) and Kato et al. (2020) showed a non-asymptotic confidence interval of the AIPW estimator. Zhang et al. (2020) proposed an estimator of a linear regression model for samples with batches. Estimators proposed by van der Laan (2008), Luedtke & van der Laan (2016), Hadad et al. (2021), Kato et al. (2020), and Zhang et al. (2020) require the true logging policy, unlike our ADR estimator.
A semiparametric estimator usually requires the Donsker condition for its asymptotic normality (Bickel et al., 1998). For semiparametric inference without the Donsker condition, sample-splitting is a typical approach (Klaassen, 1987; Zheng & van der Laan, 2011; Chernozhukov et al., 2018). Chernozhukov et al. (2018) referred to sample-splitting as cross-fitting and the semiparametric inference using cross-fitting as double-debiased machine learning (DML). The DML has been extended for several settings (Chiang et al., 2019; Chang, 2020; Jung et al., 2021). For off-policy evaluation of reinforcement learning from dependent samples, Kallus & Uehara (2019) proposed a mixing-based sample-splitting, which requires a different assumption from martingales.
In the recent literature, there has been a growing interest in the evaluation of regret minimization algorithms, where the logging policy πt(a|x) converges to 0 for sub-optimal arms a ∈ A. In this case, Assumption 1 does not hold. Note that if the logging policy does not converge to 0, we incur a linear regret in the regret minimization problem. Along with stabilizing unstable behavior with the logging policy, Hadad et al. (2021) showed that their proposed method can estimate the policy value of regret minimization algorithms with expected regret close to log T order. Because the method of Hadad et al. (2021) cannot deal with covariates, Zhan et al. (2021) extended the method in this direction. Their method can evaluate algorithms with the expected regret close to √ T order. Unlike those studies, our proposed ADR estimator may not be applicable to this setting. However, we do not consider this to be a practical limitation. The evaluation of regret minimization algorithm is a very important problem, but in industry, uniformly random arm selection and regret minimization algorithm are often used together for sanity checks, in which Assumption 1 is satisfied. It is also believed that using such a uniformly random arm selection will stabilize the logging policy and improve the empirical performance of OPVE. In our paper, we instead focus more on the instability caused by the time-varying logging policy.

heading: 4 The ADR estimator
text: For OPVE with dependent samples, this paper proposes the ADR estimator R̂ADRT (π e) defined as
1
T T∑ t=1 K∑ a=1
{ πe(a|Xt)1[At = a] ( Yt − f̂t−1(a,Xt) ) ĝt−1(a|Xt) + πe(a|Xt)f̂t−1(a,Xt) } ,
where ĝt−1 is an estimator of πt−1, constructed only from Ωt−1. We can use standard regression methods for constructing f̂t−1 and ĝt−1 if they satisfy the following assumptions. Assumption 4. For p, q > 0 such that p+ q = 1/2, ‖ĝt−1(a|Xt)−πt−1(a|Xt,Ωt−1)‖2 = op(t−p), and ‖f̂t−1(a,Xt)− f∗(a,Xt)‖2 = op(t−q), where the expectation of the norm is taken over Xt. Assumption 5. There exists a constant Cf such that |f̂t−1(a, x)| ≤ Cf ∀a ∈ A, x ∈ X .
Assumption 6. There exist a constant Cg such that 0 < ∣∣∣ πe(a|x)ĝt−1(a|x) ∣∣∣ ≤ Cg ∀a ∈ A, x ∈ X .
Assumption 4 requires convergence rates standard in regression estimators. For instance, we can apply nonparametric estimators proposed in MAB problems (Yang & Zhu, 2002; Qian & Yang, 2016). Under the assumptions, we show the asymptotic normality of the ADR estimator. Theorem 1 (Asymptotic distribution of an ADR estimator). Under Assumptions 1–6,
√ T ( R̂ADRT (π e)−R(πe) ) d−→ N (0,Ψ(πe, π̃)) .
Let us put forward the following assumption.
Assumption 7. For all x ∈ X and a ∈ A, f̂t−1(a, x)− f∗(a, x) p−→ 0.
The proof is shown in Appendix B, which uses the following proposition from Kato et al. (2020). Proposition 1 (Asymptotic distribution of an AIPW estimator (Corollary 1, Kato et al. (2020)).). Under Assumptions 1–3, 5, and 7, √ T ( R̂AIPWT (π e)−R(πe) ) d−→ N (0,Ψ(πe, π̃)).
Remark 3 (Consistency and double robustness). The ADR estimator has double robustness, as with standard DR estimators; that is, if either f̂ or ĝ is consistent, the ADR estimator is also consistent.
Theorem 2 (Consistency). Under Assumptions 1–3 and 5–6, if either f̂t−1 or ĝt−1 is consistent, R̂ADRT p−→ R(πe).
We can prove this by the law of large numbers for martingales (Proposition 3 in Appendix A).
Donsker condition. The main reason for using step-wise estimators {f̂t−1}Tt=1 and {ĝt−1}Tt=1 is to regard them as constants in the expectation conditioned on Ωt−1. The motivation is shared with DML. For asymptotic normality shown in Theorem 1, we do not impose the Donsker condition on the nuisance estimators, f̂t−1 and ĝt−1, but only require the convergence rate conditions. We call this sample-splitting method, using f̂t−1 and ĝt−1, adaptive-fitting and discuss again in Section 5. In the MAB problem, convergence rate conditions in nonparametric regression, such as a nearest-neighbor regression (Yang & Zhu, 2002), Nadaraya-Watson regression (Qian & Yang, 2016), random forest (Féraud et al., 2016), kernelized linear models (Chowdhury & Gopalan, 2017), and neural networks (Dongruo Zhou, 2020), 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.
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 4, which requires ‖ĝt−1(a|Xt)− πt−1(a|Xt,Ωt−1)‖2 = op(t−p), ‖π̃(a|x)− πt−1(a|Xt,Ωt−1)‖2 = op(t−p) is also required.
Theoretical comparison between AIPW and ADR estimators. There are two major differences between AIPW and ADR estimators. First, the AIPW estimator requires 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 ĝt−1 and f̂t−1. For the AIPW estimator, only the uniform convergence in probability is required, but the ADR estimator requires specific convergence rates on ĝt−1 and 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 op(1) if f̂ and πt is op(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 1 require ‖ĝt−1(a|Xt) − πt−1(a|Xt,Ωt−1)‖2 = op(t−p), ‖f̂t−1(a,Xt)− f∗(a,Xt)‖2 = op(t−q), and p+ q = 1/2. Asymptotic efficiencies. As shown in Theorem 1 and Proposition 1, ADR and AIPW estimators achieve the semiparametric lower bound under the DGP defined in Section 2 with p1(a|x) = · · · = pT (a|x) = p(a|x). On the other hand, the asymptotic variance of the IPW estimator using the true logging policy πt is larger than the lower bound (Hirano et al., 2003; van der Laan, 2008; Kato et al., 2020). 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 (Hirano et al., 2003), the asymptotic property under dependent samples is still unknown.

heading: 5 Adaptive-fitting: DML for dependent samples
text: 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 θ0 that satisfies E[ψ(Wt; θ0, η0)] = 0, where {Wt}Tt=1 are observations, η0 is a nuisance parameter, and ψ is a score function. We consider obtaining an asymptotic normal estimator of θ0 when using complex and data-adaptive regression methods, such as random forests, neural networks, and Lasso, to estimate the nuisance parameter η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 (Klaassen, 1987; Zheng & van der Laan, 2011; Chernozhukov et al., 2018). In DML of Chernozhukov et al. (2018), the dataset with i.i.d. samples {Wt}Tt=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. Chernozhukov et al. (2018) called the method cross-fitting.
However, cross-fitting of Chernozhukov et al. (2018) cannot be applied when samples {Wt}Tt=1 are dependent. Therefore, the ADR estimator uses step-wise nuisance estimators based on past observations Ωt−1. This construction is inspired by van der Laan & Lendle (2014), which proposed a sample-splitting for batched dependent samples. The nuisance estimators are independent in the expectation over the t-th samples conditioned on Ω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, . . . , T , we estimate η0 only using {Ws}t−1s=1 and denote the estimators as {ηt−1}Tt=1; (ii) then, we substitute Wt and ηt−1 into ψ and obtain an estimator θ̂T of θ0 by solving 1T ∑T t=1 ψ(Wt, θ̂T , ηt−1) = 0. Under this construction, if
(a) an estimator θ̌T obtained by solving 1T ∑T t=1 ψ(Wt, θ̌T , η0) = 0 has the asymptotically normal
distribution and (b) the asymptotic bias decays with the rate faster than op(−1/ √ t), we can obtain the asymptotically normal estimator of θ0. In Figure 1, 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, . . . , t− 1. To satisfy (a), we assumed that the convergence of the logging policy (Assumption 2). There are other ways to satisfy this condition. For example, we can assume the existence of batches as van der Laan & Lendle (2014) and Zhang et al. (2020). We briefly introduce the ADR estimator with this case in Appendix C.
Remark 4 (The EIPW and DM estimator). To obtain asymptotic normality via DML, we need a doubly robust structure on the estimator to reduce the asymptotic bias caused by the estimation errors of the nuisance parameters. For this reason, even by using DML, we cannot show the asymptotic normality of the IPW estimator, with an estimated logging policy (EIPW estimator), and the DM estimator, which do not have the doubly robust structure. For example, let us define the EPW estimator as 1T ∑T t=1 ∑K a=1
πe(a|Xt)1[At=a]Yt(a) ĝt−1(a|Xt) . Then, the bias is∣∣∣ 1T ∑Tt=1∑Ka=1 πe(a|Xt)1[At=a]Yt(a)ĝt−1(a|Xt) − 1T ∑Tt=1∑Ka=1 πe(a|Xt)1[At=a]Yt(a)πt−1(a|Xt,Ωt−1) ∣∣∣. Here, because the convergence rate of the estimation error ‖πt−1(a|Xt,Ωt−1) − ĝt−1(a|Xt)‖2 will not exceed Op(1/ √ T ), the bias does not vanish with op(1/ √ T ), which implies that we cannot ignore the bias when deriving the asymptotic normality. Similarly, the DM estimator also suffers from the estimation error ‖f∗(a,Xt) − f̂t−1(a,Xt)‖2. On the other hand, when using the DR estimator, the bias depends on ‖πt−1(a|Xt,Ωt−1)− ĝt−1(a|Xt)‖2‖f∗(a,Xt)− f̂t−1(a,Xt)‖2, which can be op(1/ √ T ) and ignored to derive the asymptotic normality. Note that when the samples are i.i.d., by using a specific estimator for πt, we can show the asymptotic normality for the EIPW estimator. See Hirano et al. (2003) and Hahn et al. (2011) for details.

heading: 6 Paradox concerning logging policy
text: 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.

heading: 6.1 Instability of the AIPW estimator
text: Hadad et al. (2021) pointed out that the AIPW estimator tends to be unstable, and the statistical inference becomes difficult when the nuisance parameter πt−1 is close to or converges to 0. To prevent this instability and make statistical inference possible, Hadad et al. (2021) and Zhan et al. (2021) proposed the Adaptively Weighted AIPW (AW-AIPW) estimator by adding evaluation weights. The purpose of these methods is twofold: to stabilize the estimator and expand the algorithm class whose policy value can be evaluated. In our paper, we focus more on the former stabilization problem.
The ADR estimator replaces the true logging policy πt−1 with its estimator. We find that by replacing the true logging policy with its estimator, we can control the instability caused from πt−1 by constructing well-formed ĝt−1. For example, if we know that the range of π̃ is (ε, 1 − ε) for 0 < ε < 1− ε < 1, we can add the clipping technique when estimating ĝt−1. For example, in early periods, we can set ĝt−1 as 0.5. Such techniques is greatly beneficial. Note that if the range of π̃ is truly (ε, 1− ε), the clipping of ĝt−1 does not cause clipping bias; that is, the estimator correctly converges to the asymptotic distribution shown in Theorem 1.
The main difference between the AW-AIPW estimator and the ADR estimator is that the former requires information of the true logging policy πt−1, while the latter does not by replacing it with its estimator. Besides, in addition to the stabilization, the AW-AIPW has another purpose: to evaluate the regret minimization algorithms, in which the logging policy converges to 0, but our proposed method does not solve the problem because we put an assumption on the bounded support (Assumption 1). Our finding also shares motivation with weight clipping for i.i.d. samples, such as Bottou et al. (2013). We can regard the AW-AIPW estimator as a variant of this method, where the weight clipping can decay as π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.

heading: 6.2 Simulation studies for OPVE estimators
text: For reasons given in the previous section, the ADR estimator may empirically perform better than the AIPW estimator because the estimator ĝt−1 stabilizes the ADR estimator by absorbing the instability of πt−1. We empirically show this paradox using a synthetic dataset. We generate an artificial pair of covariate and potential outcome, (Xt, Yt(1), Yt(2), Yt(3)). The covariate Xt is a 10 dimensional vector generated from the standard normal distribution. For a ∈ {1, 2, 3}, Yt(a) = 1 if a is chosen with probability q(a|x) = exp(g(a,x))∑3
a′=1 exp(g(a ′,x))
, where g(1, x) = ∑10 d=1Xt,d, g(2, x) = ∑10 d=1WdX 2 t,d,
g(3, x) = ∑10 d=1Wd|Xt,d|, and Wd is uniform randomly chosen from {−1, 1}. We generate three datasets, S(1)T(1) , S (2) T(2) , and S(3)T(3) , where 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 πe by solving a prediction problem between X(1)t and Y
(1) t (1), Y (1) t (2), Y (1) t (3) using S (1) T(1) . Then, we regard the evaluation function πe as a logging
policy and apply it on the independent dataset 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 = ∑3 a=1 1[A (m) t = a]Y (m) t (a). Then, we
estimate the true value R(πe) as 1T(2) ∑T(2) t=1 Y (m) t . Next, using the datasets S (3) T(3) and an MAB algorithm, we generate a bandit dataset S = {(Xt, At, Yt)} T(3) t=1 . For 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 StableVar weight, proposed in Zhan et al. (2021). 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(πe)− R̂(π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 1 and those with T = 750 are shown in Figure 2. The other results are shown in Appendix D. 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. Although the AW-AIPW estimator enables us to evaluate regret minimization algorithms, we cannot observe that the AW-AIPW estimator improves the empirical performance of the AIPW estimator in our setting. The EIPW estimator suffers from the dependency problem.
Remark 5 (Paradox for i.i.d. samples). This paradox is similar to the well-known property that the IPW estimator using an estimated propensity score shows a smaller asymptotic variance than the IPW using the true one (Hirano et al., 2003; Henmi & Eguchi, 2004; Henmi et al., 2007). However, as discussed above, we consider this to be a different phenomenon. In these studies, the paradox is mainly explained by differences in the asymptotic variance between IPW estimators with the true and estimated propensity score. On the other hand, for our case, AIPW and ADR estimators have the same asymptotic variance, unlike IPW-type estimators. Therefore, we cannot resolve the paradox by the aforementioned explanations. The instability of the AIPW estimator is consistent with the empirical findings of Hadad et al. (2021), but, in our paper, we suggest using the ADR estimator as another solution.

heading: 7 Experiments
text: Following Dudík et al. (2011), we evaluate the estimators using classification datasets by transforming them into contextual bandit data. From the LIBSVM repository (Chang & Lin, 2011), we use the mnist, satimage, sensorless, and connect-4 datasets 2. The dataset description is in Table 3 of Appendix D. We construct a logging policy as πt(a|x) = απmt (a|x) + (1− α) 0.1K , where α ∈ (0, 1) is a constant, and πmt (a|x) is a policy such that πmt (a|x) = 1 for an action a ∈ A and πmt (a′|x) = 0 for the other actions (a′ 6= a). The policy πmt (a|x) is determined by logistic regression and MAB
2https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.
algorithms. For MAB algorithms, we use upper confidence bound and Thompson sampling with a linear model, which are denoted as LinUCB (Chu et al., 2011) and LinTS (Agrawal & Goyal, 2013). The evaluation function is fixed at πe(a|x) = 0.9πd(a|x) + 0.1K , where π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 6.2. We omit the AW-AIPW estimator, as we found that the performance depends on the choice of the evaluation weight (see Section 6). 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 α ∈ {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 mnist and satimage with the LinUCB policy and T = 1, 000 are shown in Tables 2. The full results, including the results with the LinTS policy and i.i.d. samples, are shown in Appendix D. As discussed in Section 6, 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 6.2, we consider this to be because the estimator of πt is absorbing the instability of π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.

heading: 8 Conclusion
text: DR-type estimators are crucial in causal inference because they do not assume 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 πt.
In OPVE with dependent samples, to obtain asymptotic normality, we need to put some assumptions on the behavior of πt, such as Assumption 2 and a decay rate condition assumed in Hadad et al. (2021) and Zhan et al. (2021). 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.

heading: Acknowledgments
text: We thank Masatoshi Uehara and Kaito Ariu for insightful comments and discussion.

Review summaries:
In the setting studied in this paper, the analyst has access to data consisting of treatment assignments $A_t \\in \\mathcal{A} = \\{1,...,K\\}$, covariates $X_t$ and responses $Y_t = Y_t(A_t)$, where $(Y_t(a))_{a \\in \\mathcal{A}}$ are potential outcomes. The data are collected at time steps $t=1,...,T$ and the data generation occurs through an adaptive experiment. That is, at the $t$-th time step, the analyst can use all information up to time $t-1$, as well as $X_t$ and can decide with what probabilities $\\pi_t(a \\mid x)$ to assign any of the treatments in $\\mathcal{A}$ to the subject arriving at time $t$.   In other words, $A_t \\sim \\pi_t(\\cdot \\mid X_t)$ and then $Y_t = Y(A_t)$ is revealed.  The consequence of the adaptive experimentation is that the tuples $(X_t, A_t, Y_t)$ are dependent across time-steps $t$ (even though $(X_t, (Y_t(a))_{a \\in \\mathcal{A}})$ are iid and therefore it becomes a challenging task to conduct inference for average treatment effects (and other causal contrasts/estimands of interest).   Existing work for inference has focused on the situation wherein the policies $\\pi_t( \\cdot \\mid x)$, that were used during experimentation, are known to the analyst, while the response functions $f^*(a, x) = E[Y_t(a) \\mid X=x]$ are not known. The present paper develops a doubly robust approach to inference that also works when $\\pi_t( \\cdot \\mid x)$ is also not known to the analyst.   The paper also emphasizes that the new approach can sometimes outperform existing approaches that use additional information (on the true treatment assignment probabilities), without using the additional information (they call it a paradox).  

The paper studies off-policy evaluation from data generated from unknown and adaptive logging policies (logging policy can be updated based on past observations). The paper modified the doubly robust estimator in the non-adaptive and known-logging-policy setting to this setting by using an estimated logging policy and an estimated reward model. The estimation models used at each time step are built only on data collected before. They show the asymptotic normality of this estimator under some assumptions and make the step-wise construction and how it achieves asymptotic normality as a general approach. They empirically evaluated the proposed estimator on some simulation dataset and  discussed why the proposed estimator enjoys smaller mean squared error empirically compared to estimators with known logging policy information, even when they all have asymptotic normality. 

The authors propose and analyze an estimator for off policy value estimation (OPVE) in a Markovian setting where (X_t,A_t,Y_t(A_t)) ~ p(x)p_t(a|x)p(y_a|x) and the logging policy pi_t(a|x,Omega_{t-1}) is unknown. The estimator involves a familiar doubly robust moment function and a new form of cross fitting called adaptive fitting. The authors prove consistency, asymptotic normality, and semiparametric efficiency. Thorough simulations demonstrate low RMSE and correct coverage.