The Adaptive Doubly Robust Estimator and a Paradox Concerning Logging Policy
Authors: Masahiro Kato
Kenichiro McAlinn
Shota Yasui
Venue: NeurIPS 2021 Poster (2021)
Keywords: Doubly robust estimator
Double/debiased machine learning
Causal inference
Semiparametric efficiency
Dependent samples
Adaptive experiments

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 without 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.

The Adaptive Doubly Robust Estimator and a Paradox Concerning Logging Policy
Masahiro Kato* CyberAgent, Inc.
Kenichiro McAlinn
Shota Yasui CyberAgent, Inc.
Temple University
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 DR estimator for dependent samples obtained from adaptive experiments. To obtain an asymptoti- cally normal semiparametric estimator from dependent samples with non-Donsker nuisance estimators, we propose udaptive-fitting as 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 similar phenomenon is known for estimators with i.id. samples, traditional explanations based on asymptotic efficiency cannot elucidate our case with dependent samples. We confirm this hypothesis through simulation studies.
1 Introduction
Adaptive experiments, including efficient treatment effect estimation (van der Laan 2008; Hahn et al. 2011), treatment regimes (Zhang et al. 201 Zhao et al., 2012), and multi-armed bandit (MAB) problems (Gittins) 1989 Lattimore & Szepesvári 2020), are widely y accepted and used in real- world
applications, for example, in social experiments (Hahn al. 2011). online advertisement Zhang jtt 2012bb) clinical trials (Chow & Chang 2011 Villar 2018). j. website optimization (White) 2012 and recommendation systems (Li et al. 2010). In those various applications, there is significant interest in off-line counterfactual inference using samples obtained from past trials generated by logging policy (the probability of choosing an action: Li al. 2010 2011). Among several off-line evaluation criteria, this paper focuses on off-policy value estimation (OPVE: [i et al. (2015). The
goal of OPVE is 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 sample average of the outcomes weighted by the true logging policy. DM-type estimators refer to 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-rype 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 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 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 past observations, under which the generated samples non-i.i.d.
masahiro_ herrshhrro_kttoccyybrrgggtt.c.c
35th Conference on Neural Information Processing Systems (NcurIPS 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. yan der Laan (2008) proposed an asympiotically normal AIPW estimator under dependent samples, with several follow-up up studies, including Luedtke & van der Laan (2016) 2018), Hadad et al. (202T). |Kato et al. (2020).
and Zhan al. (2021). However, 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 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 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 [Tompson 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 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, no analytical solution is available. This is difficult task in terms of both computational volume and computational resource. Morcover, in adaptive experiments in industry (c.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, 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 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 (CL.T) for i.i.d. or martingale difference sequences directly, as done in van der Laan (2008), Hadad et al. (202T), and Kato et al. (020). 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 our proposed ADR estimator. In this paper, to solve these problems, we propose adaptive-fittie 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 follows.
(I) Asymptotic normality of the ADR estimator. We show the asymptotic normality of our pro- posed 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-splitinng method called adaptive-fitinng to show the asymptotic normality of the ADR estimator. We generalize this technique as variant of sample- splitting (Chernozhukov et al. 2018)) for semiparametric inference with dependent samples without the Donsker condition. Unlike existing sample-splitiin methods, which assume that samples are i...d,, the proposed adaptive- fitting is applicable to non-i.i.d. samples.
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 IPWttype 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).
(III) Empirical paradox on using estimated logging policy.

---

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 1PW-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 propose the ADR estimator, which is our main contribution. We call the method used for the ADR estimator adaptive-fitting, and generalize in Section 5 In S we report paradox through simulation studies and explain the cause of this phenomenon. In Section 7 we conduct experiments using benchmark datasets.
2 Problem setting
Suppose that there a time series 2,,,..., and denote the set as (7] = (I...., T}. For E [T).
let A, be an action in A = (1. (1.2.... K. X, be covariate observed by decision maker when choosing an action, and X' be its space. Following the Neyman- Rubin causal model (Rubin) 1974).
let a reward at period be Y, = > [A, = aa), where Y,(a): A + R is a potential (random) outcome. In summary, we have a dataset {Xx, A,, 12) with the following data-generating process (DGP):
Step 1:
we observe a covariate X, ~ p(z);
Step we choose A, with probability pe(alz);
Step 3: we observe an outcome Y; = E.= 1[A alYi(a), where Yi(a) Pa(ulz),
where p(z) denotes the density of the covariate Xx, (alaz)) denotes the probability of choosing an action a conditional on a covariate z at period t. and Pa (y/2z) denotes the density of a reward Yi conditional on covariate x. We assume that p(z) and Pa Pa(y]2) (z) are invariant actoss periods, and X; and (a) are drawn from these densities independently of the other period random variables; that is, {(X,, (1))), ((KK)) i.i.d., but pe (alar) can take different values across periods based on past observations. In this case, the samples (X,, A,, Y.) 1=11 are correlated over time, that is, the X1 A1. Y1} be the history and M,-1 be
samples not ii.d. Let f2-1 {X,-1, A Yi. a set of possible histories until the t-th period. The probability pe(a(z) is determined by a logging policy A x X' M,-1 + (0. 1), such that Σ Te(a|z, [z) 24,1) = 1, which is a function of covariate X₁, an action A,, and history Q4-1. We also assume that क., is conditionally independent of Ya(a) to satisfy unconfoundedness (Remark Z
Remark (Stable unit treatment value assumption (SUTVA)). The DGP implies SUTVA; that is, Pa(yla) (z) invariant to random assignments in other periods (Angrist et al. 1996).
Remark 2 (Unconfoundedness)) In this paper, unconfoundedness refers to independence between (Y1(1)..... (.(K.) and As, conditional on Xt and Q4-1, which required for identtficattin.
2.1 OPVE
The goal of OPVE is to estimate the expected value of the sum of the outcomes Ya(a) weighted by an evaluation function n" AAX X I;; that is,
K
R( = (X.. M(K))
Σ n (alx)))(aa)
where the expectation Bxx, B,,,,,, (1)........ Y.KK)) is taken over (X,, Y2(1)....... ((()),..)((())). We denote it as E, when there is no ambiguity. As with Dudik et al. (201T), the evaluation function is usually referred to as evaluation policy, where n² (a(a)) [0, and the sum is 1. However, to not restrict it so can include other forms, such as the ATE, we refer to it differently. The ATE also a special case of OPVE for A {1, 2). where π² overlap in the distributions of policies, convergence of T and the boundedness of reward.
and x² -1 To identify R(r*), we assume the
Assumption 1. For all t [T]. a E A, x X, and Ω M there exists a constant C, <a(aax) Cr. such that ==(a
Assumption equivalently means that n7, (alz) 0 for all E and x X.
3

---

Assumption 2. For all X and a E A, Te(a) -((=)) B O. where म A X - (0. Assumption 3. For all & E [T] and E A, there exists constant Cy > O, such that [Y(a)) S Cy.
Q4-1)
Although the reader may feel that Assumption T2 and the SUTVA I are strong, we adopt as 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 the structure of batches when the average of logging policy converges (Kato 2021
2.2 Notations
We denote [x] and (a)() as fa x)) and en (a, z), respectively. Let fi(a, x) be an estimator of (a, constructed from S4. Let Mu, var) be the normal distribution with the mean μ and the variance var. For a random variable with density p(z) and function μ., let
11 -0 (Jl)(=))P(())d)) be the L
3 Preliminaries of OPVE
3.1 Existing estimators
For estimating R(x*) from dependent samples, existing studies propose various estimators. An adap- tive version of the IPW estimator defined as (T*) = + Et Σ "" X.) If the model specification is correct, the direct method (DM) estimator (**)
1 11A, (x,0,
T Σ 1 (ra))) X.) known to be consistent to R(TT). As an adaptive version of the AIPW estimator, van der Laan 2008) proposed an estimator RAIIPW (T*) defined
T
K
T (a = a] (Ys fL--faila,
T (a,
T
T 1 (a
[=1
Using the martingale property. van der Laan (0088 showed asymptotic normality under Assumption 2
3.2 Asymptotic efficiency
We are often interested the asymptotic efficiency 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 pl (a|z)
pr pr(aa) = p(a (() is given as follows (Hahn 1998: Narita et al. 2019):
K (Tr (a(x)) 2 (a, X.)
K Σ
T (a(xx))) 1(xx)) ))
2
V (TT", p) =
+
X,)
The asymptotic variance of the asymptotic distribution is also known as the asymptotic mean squared error (MSE); that is, an OPVE estimator fir achieving the semiparametric lower bound also minimizes the MSE to the true value R(TT),, E ( n((5)) I not just obtaining tight confidence interval.
3.3 Related work
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 Dudik et al.) 2011 Wang et al.) 2017b] Narita
et al., 2019 Bibaut 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
I Luedtke & van der Laan| 2016
2018: Hadad et al. 2021 Kato et al.) 2020 /hang et al. 2020
2021
Zhan et al. 2021
Bibaut al.
2021

---

The AIPW estimator for dependent samples are proposed by van der Laan 2008 van der Laan Lendle (2014) and [uedike & van der Laan (2016) proposed an OPVE method without the convergence of the logging policies by using batches and standardization, respectively. Hadad et al. (202T) and /hha et al. ) 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 O 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. 201 Su et al. 2019 2020). Howard et al. (2021) and Kato et al. (2020) showed non-asymptotie confidence interval of the AIPW estimator. [Zhang al. (2020)
proposed an estimator of linear regression model for samples with batches. Estimators proposed by
van der Laan (2008), [uedtke & van der Laan 2016), Hadad et al. (202I). 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-spliting typical approach (Klaassen 1987. Zheng & van der Laan| [001]] Chernozhukov et al. 2018).
Chernozhukoy et al. (2018) referred to sample-spliting as cross-fitting and the semiparametric inference using cross-fitting double-debiased machine learning (DML). The DML has been extended for several settings (Chiang et al., [019)] Chang 2020, Jung et al. (021). For off-policy evaluation of reinforcement learning from dependent samples, Kallus & Uchara (2019) proposed mixing- based sample-splitiing 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 xe (=(a(z) converges to 0 for sub-optimal arms a E A. In this case, Assumption 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, HHadad 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. (202T) 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 vTT 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 very important problem, but in industry, uniformly random arm selection and regret minimization algorithm are often used together for sanity checks, in which Assumption [ 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 the instability caused by the time-varying logging policy.
4
The ADR estimator
For OPVE with dependent samples, this paper proposes the ADR estimator RADR(T)) defined as T (a)x = Y:: fr fi-1(a, + H (alx)))f- Xx)
T
(aai()
where فt-1 is an estimator of πt-1, constructed only from Ω4-1- We can use standard regression methods for constructing fi-1 and -1 1 if they satisfy the following assumptions.
Assumption 4. For p. > 0 such that p p q = 1/2. ( X,) - - (a, 1)122 = o, P), and [ (a, X.) (a, X,)l12 = (t where the expectation of the norm is taken over X.. Assumption 5. There exists constant Cj such that (fc-1 (a, x)1 Cj Va E A
Assumption 6. There exist constant Cg such that 0 <
x [aaa] 8 [a
Cg
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 (Asymptotic distribution of an ADR estimator). Under Assumptions
VT [RADR (T R(**)) 3 N (0, ((T",))).
5

---

Let us put forward the following assumption.
Assumption 7. For all x E X and a A. fi-1(a,)) fa x) 2 O.
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 I. Kato et al. 2020 ).).
Under Assumptions
3 and
vT (ReIP (x*) -R(7)) S N (0, ());
Remark 3 (Consistency and double robustness). The ADR estimator has double robustness, with standard DR estimators; that is, if either or is consistent, the ADR estimator also consistent.
Theorem (Consistency), Under Assumptions and 5 if either fe-1 or 9t-1 is consistent, RADR Ps R(T*).
We can prove this by the law of large numbers for martingales (Proposition 3 Appendix A
Donsker condition. The main reason for using step-wise estimators (f-1)²= and { )= is to regard them constants in the expectation conditioned on Ω The motivation is shared with DML. For asymptotic normality shown in Theorem [ we do not impose the Donsker condition on the nuisance estimators, fi-1 and - but only require the convergence rate conditions. We call this sample-splitting method, using fi-1 and 9c-1, adaptive-fitiie and discuss again in Section 5 In the nouparametric regression. such
nearest-neighbor regression (Yang& & Zhu 2002). Nadaraya- Mattarayyaaatonnnno Watson regression (Qian & Yang 2016), random forest (Féraud et al. 2016), kernelized linear models (Chowdhury & Gopalan 201 7 and neural networks (Dongruo Zhou 20200, 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.
MAB problem, convergence rate conditions
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 1 (a)
(a,, 14-1) la = (t P). [|(()) Tr-1 (4,X,, 22 Op 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 J and fr-1. For the AIPW estimator, only the uniform convergence in probability is required, but the ADR estimator requires specific convergence rates on --11 and fi 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 ग. is (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, imposes specific convergence rates the nuisance estimators. From another perspective, standard DML for ii.d. samples and Theorem require ( (a|X,) - ( 2,-1) l)lla = o, ()f=-((, - (a, (t and p q = 1/2.
Asymptotic efficiencies. As shown in Theorem [ and Proposition] 1 ADR and AIPW estimators achieve the semiparametric lower bound under the DGP defined in Section 2 with p1 (a|x)
Pr = p(a[z)) On the other hand, the asymptotic variance of the IPW estimator using the true logging policy π, 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 al. 2003), the asymptotic property under dependent samples is still unknown.
5 Adaptive-fitting: DML for dependent samples
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 6g that satisfies E[b;WW;; 6o. mu)) = 0, where (WITT are observations, 7Jo a nuisance parameter, and 1 is score function. We consider obtaining an asymptotic normal estimator of G when using complex and data-adaptive regression methods, such as random forests, neural networks, and Lasso, to estimate the nuisance parameter 7Jo- Under such a situation, the Donsker condition does not hold, in general. Sample-splittng is typical approach to

---

control the complexities of semiparametric inference without the Donsker condition (Klaassen 1987
Zheng & van der Laan| 2011; Chernozhukv et al., 2018). In DML of Cherrozzuuuo et al. (2018) 8). the dataset with i.i.d. samples {W.)i=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 nuisance estimators suffice to show the asymptotic normality of the semiparametric estimator. CChrnoohukkv et al. (2018) called the method cross-fitting.
However, cross-fitting of Chernozhukov et al. (2018) cannot be applied when samples [W.JE= are dependent. Therefore, the ADR es-
T/K ox 1)//K
2
T/K
timator uses step-wise nuisance estimators based on past observations 12-11 This construction inspired by yan der Laan Lendle (2014), which proposed a sample-splitting for batched dependent samples. The nuisance estimators are independent in the expectation over the i-th samples conditioned on f4-1- Thus, we can re- gard our sumple-splitting as another approach for DML. We call this step-wise construction adaptive-fitting in contrast to cross-fitting. We briefly summarize the procedure follows: (i) at each step t = 1.,,...,,T, we estimate no only using {Wo)== and denote the estimators as { |T=1 i (ii) then, we substitute W, and π4-1 into & and (We, OW, 1--1) = Under this construction, if (a) an estimator dr obtained by solving T === (W,, (....rm)))))))))) no) 0 has the asymptotically normal distribution and (b) the asymptotic bias decays with the rate faster than (-1V/t can obtain the asymptotically normal estimator of 0g. In Figure we illustrate the difference between cross-fiie 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 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 = 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
7/K
7/K
T/K
Figure 1: The difference between cross cross-fitting (left) and adaptive-fittie (right).
obtain an estimator or of 0g by solving #
1
Remark 4 (The EIPW and DM estimator). To obtain asymptotic normality via DML, we need doubly robust structure the estimator to reduce the asymptotic bias caused by the esti- mation 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 exam- ple, let define the EPW estimator as + Et DK x =((aXx)11A,=aa((l) Then, the bias is - I HE Ek ="(a)x:)[[A=al/ik - - Er= EK ("(alx.)1AA,=)]) (r-i(a(X.)
(a-i(a(X.)
Here, because the convergence rate of the estimation error (ul_, P4-1) - ( will not exceed Op(I/VT), the bias does not vanish with (1(T/TT), which implies that we cannot ignore the bias when deriving the asymptotic normality. Similarly, the DM estimator also suffers from the estimation error [l," X.) ft-1 X.)122 On the other hand, when using the DR estimator, the bias depends on [ 24-1) 9 (a)x(al)
T
11-1(
X.) fo- Xt) 12, which can be 0,(1/VT)) and ignored to derive the asymptotic normality. Note that when the samples are i.i.d., by using a specific estimator for no can show the asymptotic normality for the EIPW estimator. See Hirano et al. (2003) and Hahn et al. al. (20IT) for details.
6 Paradox concerning logging policy
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
7

---

Table 1: The results of Section 6.1 with sample sizes T 250, 500, 750. We show the RMSE, SD, and coverage ratio of the confidence interval (CR). We highlight in red bold two estimatios with the lowest RMSE. Estimators with asymptotic normality are marked with f, and estimators that do not require the true logging policy are marked with *,
LinU'B policy
ADR
T
IPW
AIPW
AW-AIPW
DM
EIPW
RMSE
SD
CR
RMSE
5D
CK
RMSE
SD
CR
RMSE
5D
CR
RMSE
3D
CR
RMSE
5D
CR
250
03661
01004
0333
0.305
0.295
0.89
0.158
0.129
0334
0.175
0.180
0.64
01073
07815
0.17
0.097
0:012
0.81
0.039
0.97
0.078
0.92
00.11
0.61
0.134
0.014
0.34
0.095
0.050
0.134
0.013
LEETS poicy
ADR 1+
1PW
ATPW
AW-AIPW
FIP
RMSE
CR
CR
519
CRR
51>
0.660
033
0:110
0.026
0:126
15038
07073
0.14
0.088
0:010
500
0.038
0.001
0.96
0.087
0.010
0.94
0.065
0.006
0.97
0.070
0.008
0.63
0,046
0.002
0.10
0.103
0.010
0.46
750
0.030
0.001
0.97
0.059
0.006
0.96
0.060
0.009
0.94
0.062
0.009
0.68
0.038
0.002
0.17
0.116
0.011
0.22
ADR T
ADR 1
AIPW T
AIPW
AW-AIPW
AWV-APPW
Density
DM
Density
EIPW
EIP
-0.1
0.0 Error
0.1
-0.1
0.0
0.1
Error
Figure 2: This figure illustrates the error distributions of estimators for OPVE from dependent samples generated with the LinUcB(left) and LSright) with the sample size 750. We smoothed the error distributions using kernel density estimation. Estimators with asymptotic normality are marked with f. and estimators that do not require a true logging policy are marked with *.
AIPW estimator, which requires the true logging policy. We refer to this phenomenon as paradox concerning logging policy.
6.1 Instability of the AIPW estimator
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- is close to or converges to 0. To prevent this instability and make statistical inference possible, Hadad et al. (202T) and Zhan et al. (202T) proposed the Adaptively Weighted AIPW (AW-AIPW) estimator by adding evaluation weights. The purpose of these methods is twofold: 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 mz-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 -t-1- For example, if we know that the range of ø is (c. 1 e) for 1, we can add the clipping technique when estimating 9t-1. For example, in early periods, we can set -t-1 as 0.5. Such techniques is greatly beneficial. Note that if the range of π truly (e, - e), the clipping of ği-1 does not cause clipping bias; that is, the estimator correctly converges to the asymptotic distribution shown in Theorem [
0<E <<<<> 1
The main difference between the AW-AIPW estimator and the ADR estimator 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 the stabilization, the AW-AIPW has another purpose: evaluate the regret minimization algorithms, in which the logging policy converges to O, but our proposed method does not solve the problem because we put an assumption on the bounded support (Assumption IT. 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 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.
8

---

6.2 Simulation studies for OPVE estimators
For reasons given in the previous section, the ADR estimator may empirically perform better than the AIPW estimator because the estimator -t-1 stabilizes the ADR estimator by absorbing the instability of mt-1- We empirically show this paradox using a synthetic dataset. We generate an artificial pair of covariate and potential outcome, (X,, (1),,, (2)), (3))).. The covariate X, is 10 dimensional vec- tor generated from the standard normal distribution. For a E (1,,,3), Y((a) = 1 if is chosen with where .(1,,) = 10 Xt,d, g(2, = Ed= WaX2,a
probability ((alx)) = Ln'=1 xx)])
exp(g(a.x))
g(3,x) x) = Ed= WalX and Wa is uniform randomly chosen from {-1,1}. We generate three datasets, STay" " Tea) and st3) T(a) where S/m {(x,-') yx("' (m( (2), (m)
((2)
(3)) Tim.
First, we train an evaluation function x" by solving a prediction problem between x.") and (1), y, (2), (3) using TTa) Then, we regard the evaluation function xe as logging Tia:
policy and apply it on the independent dataset S/p to obtain {(X,, A/, x where A₁ is an action chosen from the evaluation function and y:(m) -Ea= 1[4!T)) (m) =],,, a)y,(T))( (a). Then, we estimate the true value I((=)) as T(a
T(a) t= (m), Next, using the datasets s(3) and an MAB ST())
algorithm, we generate a bandit dataset S = {(X,, A,. "a 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, respec- tively. We use a Gaussian kernel, and both syper-parametert of the Ridge and kernel are chosen from {0.01, 131 We define the estimation error as R(**)= - R(T*). We conduct ten experiments by changing sample sizes and MAB algorithms. For the sample size T(a). 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 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 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 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.
Tea
Remark (Paradox for i.i.d. samples). This paradox 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 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 usymptotic 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. (0027) but, in our paper, we suggest using the ADR estimator as another solution.
7 Experiments
Following Dudik et al. (201T), 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 ?
The dataset description
Table 3 of
Appendix D We construct a logging policy as Te (a(a)) = aut."" (alaz) + (1 - a) 0.1. K. where a E (0, 1)
is a constant, and ,.;" (a |z)) is a policy such that ा." (a|z) = for an action a E A and n. (a' (z) = 0
for the other actions (a' A a). The policy n."" nzm (a|z) is determined by logistic regression and MAB
https://www.cst cwwe. edu. http:///aa///bboooo///aaaaaaaaaa

---

Table 2: The results of benchmark datasets with the LinUCB policy. We highlight in red bold the estimator with the lowest RMSE and highlight in under line the estimator with the lowest RMSE among estimators that do not use the true logging policy. Estimators with asymptotic normality are marked with f, and estimators that do not require the true logging policy are marked with *.
moiet
ADR f
IPW
AIPW
1
DM
EIPW
RMSE
SD
RMSE
SD
RMSE
SD
RMSE
SD
RMSE
SD
0.7
0.0446
0.002
0.100
0.011
0.162
0.027
0.232
0.013
0.148
0.014
0.4
0.028
0.001
0.068
0.005
0.112
0.009
0.249
0.010
0,080
0.004
0.1
0.086
0.006
0.078
0.006
0.085
0.008
0.299
0.024
0.091
0.008
setinage
ADR TM
IPW
AIPWT
DM
HIPW
RMSE
SD
RMSE
SD
RMSE
SD
RMSE
SD
RMSE
SD
0.7
0.013
0.000
0.098
0.011
0.060
0.04
0,037
0.001
0.056
0,002
0.4
0.022
0.000
0.078
0.008
0.019
0.000
0,043
0.001
0.060
0.002
0.1
0.029
0.001
0.078
0.005
0.061
0.008
0.041
0.002
0.041
0.002
algorithms. For MAB algorithms, use upper confidence bound and Thompson sampling with linear model, which are denoted as LinUCB (Chu et al.
(011) and LinTS (Agrawal & Goyal (013))
The evaluation function is fixed at x² (a|z) 0.97 (a 2
+ 0.l
K where Ta is prediction of 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 πe is absorbing the instability of Te.
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 the dependency and the Donsker condition.
8 Conclusion
DR-type estimators 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-fitii fitting as a variant of DML 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 because the ADR estimator absorbs the instability of the true logging policy n.
In OPVE with dependent samples, to obtain asymptotic normality, we need to put some assumptions on the behavior of We, such as Assumption 2 and decay rate condition assumed in Hadad al. (202T) 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, consider understanding these limitations critical.
Acknowledgments
We thank Masatoshi Uehara and Kaito Ariu for insightful comments and discussion.
10

---

References
Agrawal, S. and Goyal, N. Thompson sampling for contextual bandits with linear payoffs. In ICML, 2013.
Angrist, J. D., Imbens, G. W., and Rubin, D. B. Identification of causal effects using instrumental variables. Journal of the American Statistical Association, 914434):444455 1996.
Bang. H. and Robins, J. M. Doubly robust estimation in missing data and causal inference models. Biometricx, 61(4):962-973, 2005.
Bembom, O. and van der Laan, M. J. Data-adaptive selection of the truncation level for inverse- probabillity-ole -ofellity--o-trrammetttte weeightee estimators, 2008.
Bibaut, A., Malenica, I., Vlassis, N., and Van Der Laan, M. More efficient off-policy evaluation through regularized targeted learning. In ICML, 2019.
Bibaut, A., Chambaz, A., Dimakopoulou, M., Kallus, N., and van der Laan, M. Cost-contextual-bandee inference, 2021.
Bickel, J., Klaassen, C. A. Ritov, Y., and Wellner, A. Efficient and Adaptive Estimation for Semiparametric Models. Springer, 1998.
Bottou, L., Peters, J., Quinonero-Candela, J., Charles, D. X., Chickering, D. M., Portugaly, E., Ray, D., Simard, P., and Snelson, E. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(65):3207-3260, 2013.
Chang, C.-C. and Lin, C.-J. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http: //www csie. ntu. edu. ttttt///i//////////ettt/ttltiltt ailii/liibnivv
Chang, N.-. Double/debiased machine learning for differrenee-in-difffeeness models. The Econo- metrics Jourmal, 23(2):777-191, 02 2020.
Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W., and Robins,
J. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 2018.
Chiang, H. D., Kato, K., Ma, Y., and Sasaki, Multiway cluster robust double/debiased machine learning, 2019.
Chow, S.-C. and Chang, M. Adaptive Design Methods in Clinical Trials. Chapman and Hall/CRC, edition, 2011.
Chowdhury, S. R. and Gopalan, A. On kernelized multi-armed bandits. In ICML, 2017.
Chu, W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In AISTATS, 201
Dongruo Zhou, Lihong Li, Q G. Neural contextual bandits with ueb-based exploration. In ICML, 2020.
Dudík. M. Langford. J., and Li, L. Doubly Robust Policy Evaluation and Learning. In JCML, 2011.
Féraud, R., Allesiardo, R., Urvoy, T., and Clérot, F. Random forest for the contextual bandit problem. In ICML, 2016.
Gittins, J. C. Multi-armed Bandit Allocation Indices. Wiley, Chichester, NY, 1989.
Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S., and Athey, Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the National Academy of Sciences, 118(15), 2021.
Hahn, On the role of the propensity score in efficient semiparametric estimation of average treatment effects. Econometrica, 66-3),3 1998.

---

Hahn, J., Hirano, K., and Karlan, D. Adaptive experimental design using the propensity score. Journal of Business and Economic Statistics, 2011.
Hall, P., Heyde, C., Birnbaum, Z., and Lukacs, E. Martingale Limit Theory and Its Application. Communication and Behavior. Elsevier Science, 2014.
Hamilton, J. Time series analysis. Princeton Univ. Press, 1994.
Henmi, M. and Eguchi, S. A paradox concerning nuisance parameters and projected estimating functions. Biometrika, 2004.
Henmi, M., Yoshida, R., and Eguchi, S. Importance Sampling Via the Estimated Sampler. Biometrika, 2007.
Hirano, K., Imbens, G., and Ridder, G. Efficient estimation of average treatment effects using the estimated propensity score. Econometrica, 2003.
Horvitz, D. G. and Thompson, D. A generalization of sampling without replacement from finite universe. Journal of the American Statistical Association, 1952.
Howard, S. R., Ramdas, A., McAuliffe, J. D., and Sekhon, J. S. Time-uniform, nonparametric, nonasymptotic confidence sequences. Annals of Statistics, 2021.
Jung. Y., Tian, J., and Bareinboim, E. Estimating identifiable causal effects through double machine
learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13):12113-2212, May 2021.
Kallus, N. and Uehara, M. Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizon processes, 2019.
Kato, M. Adaptive doubly robust estimator from non-stationary logging policy under a convergence of average probability, 2021.
Kato, M., Ishihara, T., Honda, J., and Narita, Y. Adaptive experimental design for efficient treatment effect estimation: Randomized allocation via contextual bandit algorithm. 30Xi::2002.05338, 2020.
Klaassen, C. A. Consistent estimation of the influence function of locally asymptotically linear estimators. Ann. Statist., 1987.
Lattimore, T. and Szepesvári. C. Bandit Algorithms. Cambridge University Press, 2020.
Li, L., Chu, W., Langford, J., and Schapire, E. A contextual-bandit approach to personalized news article recommendation. In WWW, 2010.
Li, L.. Chu, W., Langford, J.. and Wang, X. Unbiased offline evaluation of contextual-bain bandit-basee news article recommendation algorithms. In WSDM, 2011.
Li, L., Munos, R., and Szepesvari, C. Toward minimax off-policy value estimation. AISTATS, pp. 608-616, 2015.
Loeve, M. Probability Theory. Graduate Texts in Mathematics. Springer, 1977.
Luedtke, A. R. and van der Laan, M. J. Statistical inference for the mean outcome under possibly non-unique optimal treatment strategy. Annals of Statistics, 2016.
Luedtke, A. R. and van der Laan, M. J. Parametric-rate inference for one-sided differentiable parameters. Journal of the American Statistical Association, 113(522):780-788, 2018.
Narita, Y., Yasui, S., and Yata, K. Efficient counterfactual learning from bandit feedback. In AAAI, 2019.
Oberst, M. and Sontag, D. Counterfactual off-policy evaluation with gumbel-max structural causal models. In ICML, 2019.
12

---

Qian, W. and Yang. Y. Kernel estimation and model combination in bandit problem with covariates. Journal of Machine Learning Research, 2016.
Rubin, D. B. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of Educational Psychology, 66(5):688770, 1974.
Su, Y., Wang, L.., Santacatterina, M., and Joachims, T. CAB: Continuous adaptive blending for policy evaluation and learning. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6005-6014, PMLR, 09-15 Jun 2019.
Su, Y., Dimakopoulou, M., Krishnamurthy, A., and Dudik, M. Doubly robust off-policy evaluation with shrinkage. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 9167-9176. PMLR, 13 18 Jul 2020.
Thompson, W. R. On the Likelihood that on Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3-4):285-294, 12 1933.
van der Laan, M. J. The construction and analysis of adaptive group sequential designs, 2008
van der Laan, M. J. and Lendle, S. D. Online targeted learning, 2014.
Villar, S. Bandit strategies evaluated in the context of clinical trials in rare life-threatening diseases. Probability in the engineering and informational sciences, 32(2):229-245, Apr 2018.
Wang, Y.-X., Agarwal, A., and Dudík, M. Optimal and adaptive off-policy evaluation in contextual bandits. In Precup, D. and Teh, W. (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3589-3597. PMLR, 06-11 Aug 2017a.
Wang, Y.-X., Agarwal, A., and Dudik, M. Optimal and adaptive off-policy evaluation in contextual bandits. In ICML, 2017b.
White, J. Bandit Algorithms for Website Optimization: Developing, Deploying, and Debugging. O'Reilly Media, 2012.
Yang, Y. and Zhu, D. Randomized allocation with nonparametric estimation for multi-armed bandit problem with covariates. Annals of Statistics, 30(1):100-12) 02 2002.
Zhan, R., Hadad, V., Hirshberg, D. A., and Athey, Off Off-policy evaluation via adaptive weighting with data from contextual bandits, 2021.
Zhang, B., Tsiatis, A. A., Davidian, M., Zhang, M. and Laber, E. Estimating optimal treatment regimes from a classification perspective. Stat,
11, Jan 2012a.
Zhang, K., Janson, L.,, and Murphy, S. Inference for batched bandits. In NeurlPS, 2020.
Zhang, K. W., Janson, L., and Murphy, S. A. Statistical inference with m-estimators on adaptively collected data, 2021.
Zhang, W., Zhang, Y., Gao, B., Yu, Y., Yuan, X., and Liu, T.-Y. Joint optimization of bid and budget allocation in sponsored search. KDD, 08 2012b.
Zhao, Y., Zeng. D., Rush, A., and Kosorok, M. Estimating individualized treatment rules using outcome weighted learning, Journal of the American Statistical Association, 107: 1118, 09 2012.
Zheng, W. and van der Laan, M. J. Cross-validated targeted minimum-loss-base estimation. In Targeted Learning: Causal inference for Observational and Experimental Data, Springer Series in Statistics. Springer-Vertte New York, 2011.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] See abstract, and Section especially the list of contributions.
(b) Did you describe the limitations of your work? [Yes] Please refer the conclusion for the limitation of this paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work mostly theoretical and experiments are based on synthetic data. We believe it does not have any potential negative societal impacts in short period of time.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Since the most ethical concern is about the dataset and this paper uses synthetic data in the experiment, this paper conforms to the guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yss] We have the
instructions to reproduce the result in the appendix and readme file of the supplementary material (we included source code and requirements).
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6.2 and Appendix
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We reported the value of standard deviation for each result and other information in Appendix D We also show the distributions of estimation errors smoothed by kernel density estimation. We did not conduct hypothesis test because for deciding the best performing method, is not obvious how to set the null and alternative hypothesis and conduct statistical hypothesis test. The t-test is sometimes used in machine learning, but considering the multiplicity of the test, it may lead to inaccurate inferences. Therefore, we have tried show information such as mean, standard deviation, and distribution as much as possible.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] We described the numbers of trials of experiments. The computations are very simple and could be done on personal laptop, so resource information not included.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] We used open datasets from LIBSVM
repositories.
(c) Did you include any assets either in the supplemental material See supplementary material. We included source code.
URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] We used only synthetic data in this paper.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We only have experiments using synthetic data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing service.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] We did not use a crowdsourcing service.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We did not use a crowdsourcing service.
14


Reviews:
[{"review_id": "mup5z2JydvU", "reviewer": "Reviewer_sEtk", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Off-policy evaluation with unknown and adaptive logging policies is pretty realistic setting in real-world applications. \n\nThe paper propose an off-policy evaluation estimator in this setting and characterize the conditions under which it can achieve asymptotic normality, which provides theoretical groundings for using this estimator. \n\nOne question I have is, if we apply adaptive-fitting to DM and EIPW estimators, do we achieve asymptotic normality. And it would be great to also include the experiments comparing with these two baselines as reference. \n\n\nMinor issues:\n\nThe acronym AIPW is very confusing. I do not know what 'A' stands for and I always thought it was adaptive when I saw it. But it was not. \n\nline 226 satisfies what? \n\nline 360 as section 6.3 -> as discussed in Section 6.3\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "erERNNk7BY", "reviewer": "Reviewer_Qkbm", "summary": "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.\n\nThe 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).\n\n\nExisting 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. \n\nThe 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).\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper is well-written and the assumptions are clearly stated. Adaptive experimentation is bound to become more popular, and most traditional statistical approaches break down in that setting. Instead new approaches are needed. Hence it is an important area of research, and this paper further contributes to this area.\n\n1) The main aspect that is missing from the paper, in my opinion, is some motivation for the statistical setting. I find it hard to imagine that someone has access to data from an adaptive experiment (and e.g., the temporal succession of treatment assignments $t=1,...,T$ is known), but does not know how the experiment was actually implemented (i.e., how the treatment assignments were sequentially randomized). When would this occur? This is in contrast to e.g., the typical setting for doubly robust estimators for estimating average treatment effects in observational data. There, the treatment assignment is clearly not known and one estimates propensities and potential outcome regression functions to deal with confounding (under weaker conditions compared to both the IPW approach and the outcome modeling approach).\n\n2) I wonder whether the novelty of the \"adaptive fitting\" procedure introduced by the authors may be overstated. For example, Hadad et al. also fit the outcome models $f^*(a, x)$ based on data up to the previous time point (similar to the adaptive fitting in this paper), so that I am not convinced of the novelty of this methodological contribution. I do agree however with the authors, that it appears that from a technical perspective, also having an estimated $\\\\hat{\\\\pi}_t(\\\\cdot \\\\mid X_t)$ based on past data (and not just response function) would make the theoretical analysis more challenging.\n\n3) What is the take home message from the \"paradox\"? Can the authors provide practical recommendations about what to do in case the treatment assignment probabilities are actually known?\n\n\nSome minor remarks: On Page 6 there is typo \"wit\" instead of \"with\". I also wanted to let the authors know that  Zhan et al. (2021) have a follow-up on the paper of Hadad et al. that accounts for context covariates (https://arxiv.org/pdf/2106.02029.pdf). (Of course the reviewed manuscript precedes the preprint I linked above, so I just provided the above reference in case it is useful, the authors do not need to cite it or compare to it.)\n\n**Update:** Based on the author response, one take-away is that the proof techniques and technical results are a key contribution of this paper. I have therefore increased my score from 5 to 6. I am still not entirely convinced however about the practicality of the statistical setting (i.e., I am not convinced that a tech company doing adaptive experimentation would have trouble storing the experimental protocol).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some limitations (but not all, see review above). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "CrkB3i9ggS", "reviewer": "Reviewer_goA7", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall assessment\n\nOriginality: The innovation is to allow the logging policy to be unknown. For the theory to extend to this case, adaptive fitting is introduced as an elegant solution that appears to be new. Please also compare with Kallus and Uehara’s mixingale sample splitting to shed light on originality.\n\nQuality: The estimator and analysis are interesting. I am concerned about whether the Hadad et al estimator (2019) was given a good faith implementation since its coverage is zero (when it should be 95). \n\nClarity: This paper is unusually well written. See comments below about specific points to clarify or assumptions to further explain.\n\nSignificance: The contribution is clearly explained and not overstated. It is a natural progression of existing results that is relevant to empirical practice.\n\nSuggestions to improve the paper\n\n5: with non-Donsker\n\n54: Nicely written\n\n57: Nicely written\n\n67: Nicely written\n\n90: Crystal clear. The Markov property is a major simplification relative to dynamic treatment effects.\n\n116: Please give further interpretation of Assumption 2.2. Unlike the other assumptions, it is not obvious. What cases are being ruled out?\n\n145: the MSE to the true R(pi^e)? What does this mean given that R(pi^e) is a scalar for a given pi^e?\n\n153: Impressively thorough\n\n169: What is mixingale based sample splitting? How does it compare?\n\n170: It would be nice to additionally mention the sample splitting of Chiang et al [arXiv:1909.03489]\n\n180: please define MAB\n\n264: What does this sentence mean?\n\nTable 1: I am happy to see RMSE, SD, and CR\n\n303: Please summarize the DGP in a clearer way, perhaps as an offset algorithm\n\n328: It does not seem that the Hadad et al (2019) approach was given a good faith implementation. If their proposed weights do not include covariates, what would be a reasonable extension with covariates? Indeed, in Table 1, the coverage of AW-AIPW is even zero, which suggests this was not a reasonable implementation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "What assumptions could be violated, and how would that impact conclusions and policy recommendations?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies off policy estimation using data collected by a changing (adaptive) and unknown logging policy. This is an important and under-explored setting, since adaptive experimentation is increasingly common in many application domains (e.g., online platforms). The paper gives an adaptive doubly-robust estimator, establishes semiparametric efficiency of the estimator, and also provides some nice simulation studies that showcase how fitting propensities may be beneficial even when the true ones are known. 

Overall, all of the reviewers were quite positive about the paper, and so we are recommending acceptance. Please incorporate comments from the discussion section into the final version, as this will clear up some confusions and improve the manuscript. 
Decision: Accept (Poster)