AN ONLINE SEQUENTIAL TEST FOR QUALITATIVE TREATMENT EFFECTS
Authors: Chengchun Shi
Shikai Luo
Rui Song
Hongtu Zhu
Venue:  (2021)
Keywords: sequential testing
A/B testing
qualitative treatment effects
bootstrap

Abstract: Tech companies (e.g., Google or Facebook) often use randomized online experiments and/or A/B testing primarily based on the average treatment effects to compare their new product with an old one. However, it is also critically important to detect qualitative treatment effects such that the new one may significantly outperform the existing one only under some specific circumstances. The aim of this paper is to develop a powerful testing procedure to efficiently detect such qualitative treatment effects. We propose a scalable online updating algorithm to implement our test procedure. It has three novelties including adaptive randomization, sequential monitoring, and online updating with guaranteed type-I error control. We also thoroughly examine the theoretical proper- ties of our testing procedure including the limiting distribution of test statistics and the justification of an efficient bootstrap method. Extensive empirical studies are conducted to examine the finite sample performance of our test procedure. 

Under review as a conference paper at ICLR 2021
AN ONLINE SEQUENTIAL TEST FOR QUALITATIVE TREATMENT EFFECTS
Anonymous authors Paper under double-blind review
ABSTRACT
Tech companies (e.g., Google or Facebook) often use randomized online experi- ments and/or A/B testing primarily based on the average treatment effects to com- pare their new product with an old one. However, it is also critically important to detect qualitative treatment effects such that the new one may significantly out- perform the existing one only under some specific circumstances. The aim of this paper is to develop a powerful testing procedure to efficiently detect such qualita- tive treatment effects. We propose a scalable online updating algorithm to imple- ment our test procedure. It has three novelties including adaptive randomization, sequential monitoring, and online updating with guaranteed type-I error control. We also thoroughly examine the theoretical properties of our testing procedure including the limiting distribution of test statisties and the justification of an effi- cient bootstrap method. Extensive empirical studies are conducted to examine the finite sample performance of our test procedure.
INTRODUCTION
Tech companies use randomized online experiments, or A/B testing to compare their new product with a well-established one, Most works in the literature focus on the average treatment effects (ATE) between the new and existing products (see Kharitonov et al. 2015 Johari al. 2013 2017
Yang et al. 2017 Tu et al., 2019] and the references therein). In addition to ATE, sometimes we are interested in locating the subgroup (if exists) that the new product performs significantly better than the existing one, as early as possible. Consider a ride-hailing company (e.g., Uber). Suppose some passengers are in the recession state (at a high risk of stopping using the companys app) and the company comes up with certain strategy to intervene the recession process. We would like to if there are some subgroups that are sensitive to the strategy and pin-point these subgroups if exists. motivates us consider the null hypothesis that the treatment effect is nonpositive for all passenger.
Such a null hypothesis is closely related to the notion of qualitative treatment effects in medical Gail
studies (ail & Simon 1985 Roth & Simon! [018 (Shi et al., (020a), and conditional moment inequalities in economics (see for example, Andrews & Shi 2013 2014| CChenozzuuoo et al. 2013 Armstrong & Chan 2016, Chang et al. 20155 Huu (017). However, these tests are computed offline and might not be suitable to implement in online settings, Moreover, it is assumed in those papers that observations are independent. In online experiment, one may wish to adaptively allocate the treatment based on the observed data stream in order to maximize the cumulative reward or to detect the alternative more efficiently. The independence assumption is thus violated. In addition, an online experiment is desired to be terminated as early as possible in order to save time and budget. Sequential testing for qualitative treatment effects has been less explored.
In the literature, there is a line of research on estimation and inference of the heterogeneous treatment effects (HTE) (Athey & Imbens, 2016) Taddy et al., 2016, Wager Athey) 2018 Yu et al. 2020). In particular, Yu et al. (2020) proposed an online test for HTE. We remark that HTE and QTE are related yet fundamentally different hypotheses. There are cases where HTE exists whereas QTE does not. See Figure for an illustration. Consequently, applying their test will fail in our setting.
The contributions of this paper are summarized as follows. First, we propose a new testing procedure for treatment comparison based on the notion of QTE. When the null hypothesis is not rejected, the new product is no better than the control for any realization of covariates, and thus it is not useful at all. Otherwise, the company could implement different products according to the auxiliary

---

Under review as a conference paper at ICLR 2021
A=0 A-0
A-1
A-1
02
0.4 0.
0.0
62
0.4
0.
82
0.4
06
08
Figure I: Plots demonstrating QTE. X denotes the observed covariates, A denotes the received treatment and denotes the associated reward. In the ride- hiilhnaling example, of passenger, A is a binary strategy indicator and Y is the passenger's 's number of rides in following two weeks. In the left panel, the treatment effect does not depend on X. Neither HTE nor QTE exists in this case. In the middle panel, HTE exists. However, the treatment effect is always negative. As such, QTE does not exist. In the right penal, both QTE and HTE exist.
feature vector describing characteristics
covariates observed, maximize the average reward obtained. We remark that there are plenty cases where the treatment effects are always nonpositive (see Section 5 of Chang et al. 2015 Shi et al.) 2020at. by-product of our test that it yields a decision rule to implement personalization when the null is rejected (see Section 3.1 for details). Although we primarily focus on QTE in this paper, our procedure can be easily extended to testing ATE as well (see Appendix D for details).
Second, we propose scalable online updating algorithm to implement our test. To allow for se- quential monitoring, our procedure leverages idea from the a spending function approach (Lan & DeMets 1983) originally designed for sequential analysis in clinical trial (see)Jennison & Turnbull 1999 for an overview). Classical sequential tests focus on ATE. The test statistic at each interim stage is asymptotically normal and the stopping boundary can be recursively updated via numerical integration. However, the limiting distribution of the proposed test statistic does not have a tractable analytical form, making the numerical integration method difficult to apply. To resolve this issue, we propose a scalable nootstrap-assiiee procedure to determine the stopping boundary.
Third, adopt theoretical framework that allows the maximum number of interim analyses K to diverge as the number of observations increases, since tech companies might analyze the results every few minutes (or hours) to determine whether stop the experiment or continue collecting more data. It is ultimately different from classical sequential analysis where K is fixed. Moreover, the derivation of the asymptotic property of the proposed test further complicated due to the adaptive randomization procedure, which makes observations dependent of each other. Despite these technical challenges, we establish nonasymptotic upper bound on the type-I error rate by explicitly characterizing the conditions needed on randomization procedure, K and the number of samples observed at the initial decision point to ensure the validity of our test.
BACKGROUND AND PROBLEM FORMULATION
We propose potential outcome framework (Rubin) 2005) to formulate our problem. Suppose that we have two products including the control and the treatment. The observed data at time point t consists of a sequence of triples {(X,, A,, x)) where N(-) counting process that is independent of the data stream {(X,, A,, Y.) = Ai is binary random variable indicating the product executed for the i-th experiment, X; E IP denotes the associated covariates, and Y, stands for the associated reward (the larger the better by convention). We allow A; to depend on X; and past observations {Xx; Aj. Y5) so that the randomization procedure can be adaptively changed. In addition, define Y (0) and (1) to be the potential outcome that would have been observed if the corresponding product executed for the i-th experiment. Suppose that {(X,, Y," (0), (1))) are independently and identically distributed copies of (X, (0), (1)) Let X be the support of X and Qo a) = E(Y = x) for a = 0, 1, we focus on testing the following hypotheses:
Ho Qo(æ, 1) < Qo 0), Vo E X versus Hi Qo(x, > Q6 0), 3r E X.
Notice that when there are covariates, i.e., X = 0. the hypotheses are reduced to Ho To < 0 versus H₁ To > O, where Tu corresponds to ATE, i.e, Tu = E(Y (1) Y-(O)). In general, we require X to be compact set. We consider a large linear approximation space Q for the conditional mean function Qn- Specifically,, let Q = {Q(x, a; 3. 3,) = sp (x)),, 3n B E R') be the approximation space, where (px) is g-dimensional vector composed of basis functions on X. The
2

---

Under review as a conference paper at ICLR 2021
dimension is allowed to diverge with the number of observations in order to alleviate the effects of model misspecification. The use of linear approximation space simplifies the computation of our testing procedure. When Qo is well approximated, it suffices to test
Ho : = (z) ))) - O, Vx E X versus M1 : yp (x) - (6) > 0, X.
(I)
For clarity, here assume Qu(æ, a) = Q( a; S0. 31) for some Bü and 8i. In Appendix B, al- low the approximation error inf Bo.8, ae (0.1) 1Qu(z, a) Q(2, a; So. 31) to be nonzero.
Let Fj denote the sub-dataset [(X,, A,, Yi) Isis; for j 2 1 and Fo = 0. Throughout this paper, assume that the following two assumptions hold.
(AI) Y (L) + -1 (0) for vi 2 1. (A2) A; is independent of of (0), (1), {(X,, (E))), (g given X; and F, for any
Assumption (A1) is referred to be the stable unit treatment value assumption (Rubin) 1974) and As- sumption (A2) is the sequential randomization assumption (Zhang al. 2013) and is automatically satisfied in a randomized study where the treatments are independently generated the observed data. (A2) essentially assumes there is unmeasured confounders. These assumptions guaran- tee that both regression coefficients (defined through potential outcomes) are estimable from the observed dataset as shown in the following lemma.
Lemma 1 Let I(-) denotes the indicator fumction. Under (AI)-A2), we have E|U(A, = aY x T(X.)822 = O, Va E {0, 10,1),22
ONLINE SEQUENTIAL TESTING FOR QTE
3.1 TEST STATISTICS AND THEIR LIMITING DISTRIBUTION
We first present our test statistic for testing Ho. In view of Lemma ordinary least squares estimator
we estimate 8a by using the
N( Σ 1=1
(a(1)=
I(A: = a))=))),
N(t)
each time point t for a 10, where Et(() ~ I(A, a))(X.)p A generalized inverse might be used even if (1) is not invertible. Consider the following test statistic S()) supaex sp (1) - (t)) Under Ho. expect S(t) be small. A large S(() can be interpreted as the evidence against Ho. As such, we reject Ho for large S(1). We remark that when Ho is rejected, we can apply the decision rule d(x) = arg f0.1) 6 (z) for personalized recommendation.
To determine the rejection region, next discuss the limiting distribution of S(t). Under Ho.
5(t) sup pT (x) 31 (t()) (3) sup o (x) -5)
=ex
=Ex < S p (z) - - + $.
(2)
=ex
Both equalities hold when 85 = 3i. Suppose there exists some function x (.,)) defined on {0, 1} X that satisfies | where - = Pr(A,, al Xn, = x, Fn-), and the expectation E is taken with respect to X. This condition implics that the treatment assignment mechanism cannot be arbitrary (see the discussion below Theorem [ for details). Then we will show
Σn n TH (a, x" (a, X)I P Va E f0. 1) as n - co,
B(L) = (3) 87 - (1) + +.)3 4 N(O, aE(O.1)
Σ
ーー as N(I) - 0o,
(3)
where Σ, = Ea, x) x)xx 4 = En (a, X)o x)) (X), and (a x) =
E((Y*(a) - (X))) 2 =z], for any x X. According equation 3 the right-hand-side
3

---

Under review as a conference paper at ICLR 2021
(RHS) of equation 2 is to converge in distribution to the maximum of some Gaussian random vari- ables. This observation forms the basis of our test.
We next discuss the sequential implementation of our test. Assume that the interim analyses conducted at time points f1, f2, f2,...,tx E [0] such that < t < t2 < ... < tx = T. We allow K grow with the number of observations. In the most extreme case, 4 = inf, (t) 2 +1)x,))++), vk 2 2. That is, we make decision regarding the null hypothesis upon the arrival of each observation. addition, we assume that \ is large so that there are enough number of samples ((1) to guarantee the validity of the normal approximation for B(4)). We remark that typical tech companies such as Amazon, Facebook, etc., massive data are collected even within a short time interval. Large sample approximation is validated in these applications.
may set
To guarantee our test controls the type-I error, we reject Ho and terminate the experiment t (N(tt))(tt) 2 24 for some 1,..., ...,, K with some suitably chosen 21,..., 2K > that satisfy
Pr max { (VN((t))((t)) 26) (e)>0) sa+o(1) kE(L....,K)
for a given significance level a > 0 under Hu- In view of equation 2 it suffices to find fz h that satisfy
sup ( (x) - 2k > sa ) FEX
max kE(L.....K
(4)
where the stochastic process B()) is defined in equation
To determine {#x h&s need to derive the asymptotic distribution of the seft-hand-side (LHS) of
equation 4 To this end, define a mean-zero Gaussian process G(l) with covariance function
Cov(G(t),G(t)) = NI (2((')
Σ E.' vo aE{0,1}
In the following, we show that the LHS of equation 4 can be uniformly approximated by G(+), for any {2x Ik...... To establish theoretical results, need some regularity conditions (p(). To save space, we summarize these assumptions in (A3) and put them in Appendix
Theorem Assume (A1)-(A3) hold. For a = 0, 1, assume inf x (a x)) > O and (Y*(a) is bounded almost surely. Assume there exists some as such that for any sequence {in that satisfies jao log in > q², the following event occurs with probability at least O(jn0))
sup (E
T" (a, (
0(1)gh' log k,
Wk jn:
(5)
where O(1) denotes some positive constant. Assume (t))/ log N(tt) > d² and ((t))
log (T) almost surely. Then conditional on the counting process N-), there exists some constant
e > such that
sup (x))G(tk) 2k 0
sup
Pr
max KE
sup (x)B(tk)) 2k >0 Pr
max K)
IzEX
I 3/ 1//8 log 15/8
log (KN((1)) + a003 (tn) log (3+00) (KKN(tt))
Theorem M implies that the approximation error depends on the number of observations obtained up to the first decision point ((t)), the maximum number of interim analyses K, the total number of basis functions q. and ag, which characterizes the convergence rate of the treatment assignment mechanism Σ n -- Clearly, the error will decay to zero when the followings hold with probability tending to
q ((NN*(tt),, for some S a" min(1/6, an/))
(6)
log(K) & min (11), No00033 3/ (11)).
4

---

Under review as a conference paper at ICLR 2021
In Appendix C show that do 1/2, when e-greedy strategy is used for randomization to balance the trade-off between exploration and exploitation. In this case, @ requires q to grow at a slower rate than (t)) This condition is automatically satisfied when q bounded. Condition 7 is satisfied when K grows polynomially fast with respect to N [tt).. In addition to é-greedy, other adaptive allocation procedures (e.g., upper confidence bound or Thompson sampling) could be applied as well.
As discussed in the introduction, the derivation of Theorem | is nontrivial. One way to obtain the magnitude of the approximation error is to apply the strong approximation theorem for multidimen- sional martingales (see Morrow & Philipp/ 1982 /Zhang 2004). However, the rate of approximation typically depends the dimension and decays fast as the dimension increases. To derive Theorem 1 we view {sp (x) (xxx)))=xX, ) as a high-dimensional martingale and adopt the Gaussian
approximation techniques that have been recently developed by Belloni & Oliveira (2018). In view of equation 2 an application of Theorem T yields the following result.
hold, equation 6 and equation 7 hold with probability tending to 1. Then for any ....... 2g. that satisfy
Theorem Assume that the conditions of Theorem !
sup 4 (z)G(tt) - 2x.) o0 = o(1), REE
Pr
max (E(
(8)
as ((1) diverges to infinity, we have under Ho.
Pr max (VN((a))(tt)) - 2x} 20) sat
kE(L
The above equality holds when 85 37.
Theorem 2 suggests that the type-I error rate of the proposed test can be well controlled. It remains to find critical values {=R]ıekk that satisfy equation & the next section, we propose a bootstrap- assisted procedure to determine these critical values.
3.2 BOOTSTRAP STOPPING BOUNDARY
We first outline a method based on the wild bootstrap (Wu 1986) to approximate the limiting dis- tribution of (S(4))) Then diseuss its limitation and present our proposal, scalable bootstrap algorithm to determine the stopping boundary.
The idea is to generate bootstrap samples {B.M (a,) that have asymptotically the same joint dis- tribution (tx) - a,), Then the joint distribution of {S(tz)}x can be well-approximated by the conditional distribution of ([M))(ks) given the data, where (MM = supzex s (x) (3M (t)) } for any t. Specifically, let (E. + be sequence of i..d. standard normal random variables independent of {(X,, A., A.),A,Y)))sss Y.) For {0, 1}. define
N(0
GMH (t) = ---
Σ
I(A, = ()), (xx))
Va E (0,
(()
Both the asymptotic means of 3M and (t( - B3) are zero. In addition, their covariance functions are asymptotically the same. By design, (Prm (tx)t is multivariate nor- mal. Similar to equation we can show { (tx) - Bo, k is asymptotically multivariate normal. Consequently, the limiting distributions of (3AM Ja,) and (3a(kx) ) asymptotically equivalent. As such, the bootstrap approximation is valid.
However, calculating BMB (t&) requires ((N(tx)) operations. The time complexity of the resulting bootstrap algorithm is (BB((t))) up to the k-tth interim stage, where B the total number of bootstrap samples. This can be time consuming when
are large. To facilitate the computation, we observe that in the calculation of BMB the random noise is generated upon the arrival of each observation. This is unnecessary as we aim to approximate the distribution (.).) only at finitely many time points.
5

---

Under review as a conference paper at ICLR 2021
We next present proposal. Let vectors independent of the observed data, where Lg denotes the q x q identity matrix. At the k- th interim stage, compute (ts) supzex 10 (B) Boue (lx)), where Baun (1x) equals
be sequence of iid [ In) random
1/2
N(G) Σ (T)())(A,, a))((x)))) (X.))) (xx;) Ba(t,)) (1z)
((ta)
Cja--
j=1
(=
For any ly and k2, the conditional covariance of (3
Bom (tk, }} and
v (N(t22 ) (a (lx2) -Bo (tk2)) equals
((
ΣΣ Σ
(xX))//1-((((88)))))3 (T)(A = a)p(())) =
(tx, ((tk))
a=Uj=1 (
Under the given conditions in Theorem
it is to converge to
VN((R)
E11 Ea) Cov(G((k,)) G(tz,)).
E
(N((k)) a=0
This means (V /N((t) (6Mm (tx) Byn
(t+)) (tx)) and {G(++)}& have the same asymptotic distribu- tion. Consequently, (vN(tt) (SMB)) (tx) can be used to approximate the joint distribution of (supnex 40 (x))(tt))
To choose { le that satisfies equation 8 we adopt the a-spending approach that allocates the total allowable type error at each interim stage according to an error-spending function. This guarantees our test controls the type-I error. We begin by specifying an a spending function a(l) that is non- increasing and satisfies (0) = 0, aT)) a. Popular choices a(-) include
1 (c 1) )
Φ (1
a a/22VT)
(t) aog
(t) = - 22
Vi
(9)
1 for 0 > 0,
(t 1 - exp(->1/TT for 7 0,
(t(t)
T
exp(-7)
where (-) denotes the cumulative distribution function of a standard normal variable and 4 (-) is
its quantile function. Based on a-)), we iteratively calculate Ên, k L,..., K the solution of
Pr max (VN(C)) (t,) 2n < 0, (tt (tw) E a(tx) - a(tx-1), (10)
SAMBA
(J
and reject Ho when (t(t))((tt) 2g holds for some k.
The validity of the bootstrap test is summarized in Theorems and below.
Theorem Assume the conditions in Theorem I
hold. Assume = O(N" (t1)) for some <
a" < 1/3, almost surely. Then conditional on the counting process N(),, we have
(VIN(E)) SAM (tx)- -
sup T (x))((t) 24 > 0
sup
Pr
max [K
> 0 Pr
max [E([I....K)
KEE
sc 2c (t1) log" 11/6 (1((K((t))) + +NN -a0
log (5+ (KN((())
for some constant with probability at least - O(NN-o where (.) denotes the probability measure conditional on the data stream {X,, A.,AA, Yittt.
Theorem Assume the conditions Theorem 3
holld Then conditional N(),, the critical values
{2x satisfy
(uupTT(x)G(A 2x > 100_0 (E
Pr max KE (I..,,
< e 2/22/2 1/6 log log" 11/6 ([((((((1)) + nN -a033 log) (3+00)/3 (KN(1))) (11)
for some constant c 0.

---

Under review as a conference paper at ICLR 2021
When the RHS of equation 11 is (p(1), it follows from Theorems and 4 that our test is valid. The conditional distribution in equation 10 can be approximated by the empirical distribution of Bootstrap samples.
Finally, we remark that our test can be online updated as batches of observations arrive at the end of each interim stage. A pseudocode summarizing our procedure is given in Algorithm 1 in the appendix. The spatial complexity of the proposed algorithm is O(B,, where is the number of bootstrap samples. The time complexity is O(Bk + ((x)) )) up to the k-th interim stage. Suppose N (()-1)) = n for any S j I K, we have Bk + N (la)) = (B + n)kk & Bnk BN for large n and B. Hence, our procedure much faster compared to the standard wild bootstrap.
NUMERICAL STUDIES
4.1 SIMULATION STUDIES
In this section, we conduct Monte Carlo simulations to examine the finite sample properties of the
proposed test. We generated the potential outcomes Y, (a) = (Xa=X2)/22 a0l/2+aa(XX)) (X,) + 8s. where es's are i.dd (N0 0.5²). The covariates X; Xa,Xx2 Xx) were generated as fol- lows. We first generated X; = (X;, X1a) from a multivariate normal distribution with zero mean and covariance matrix equal to (0.5 Then we set Xij = [x S 2) + 2sgn( 12 TXX;]] > 2). We consider two randomization designs. In the first design, the treatment assignment is nondynamic and completely random. Specifically we set T; x)) = 0.5, for any a, and i. In the second design, we use an e-greedy strategy to generate the treatment with E = 0.3. In addition, we set N(Ti) = 2000 and (T,)) (T) 2n for 2 S j < K and some O. We consider two combinations of (n, K). corresponding to K)) = (200,5) 5) and (20,50),
We set the significance level a = 0.05 and choose B = 10000. We set T T(X)) = øs + x12)/ /2///22233 for some function 6s parameterized by some 5 2 0. We consider two scenarios for Øs. Specifically, we set (x) òx /3 in Scenario and Φs 8 cos( π..) in Scenario For each setting, we further consider four cases by setting d = 0, 0, 0.15. 0.2, 0.25 and 0.3. When 8 = O, Hg holds. Otherwise, H1 holds. For settings, we construct the basis function yr() using additive cubic splines. For each univariate spline, set the number of internal knots to be 4. These knots are equally spaced between 2,
We denote test by BAT, short for bootstrap-assisted test. We run our experiments a single computer instance with 40 Intel(R) Xeon(R) 2.20GHz CPUs. It takes 1-2 seconds on average to compute each test. In Table [ (see Appendix G) report the rejection probabilities and average stopping times (defined as the average number of samples consumed when the experiment is termi- nated) of the proposed test aggregated over 400 simulations when (n)-) is chosen the spending function. In Figure we plot the rejection probabilities of our tests and the average stopping times of the experiments.
can be seen that the type-I error rates are close the nominal level in all
cases. The power of our test increases as 8 increases, demonstrating its consistency. In addition, when 8 > 0, our experiments are stopped early in all cases.
To further evaluate our method, we compare it with a test based on the law of iterated logarithm (denoted by LIL). LIL determines the decision boundary based on an always valid finite error bound (see Appendix F for details about the competing method). It can be seen from Figure 2 that our method has much larger power than the law of iterated logarithm approach.
4.2 REAL DATA ANALYSIS
In this section, we apply the proposed method to Yahoo! Today Module user click log datase ! which contains 45,81 45,811,883 user visits to the Today Module, during the first ten days in May 2009. For the ith visit, the dataset contains ID of the new article recommended to the user, binary response variable Yú indicating whether the user clicked the article or not, and a five dimensional feature vector summarizing information of the user. Due privacy concerns, feature definitions and article names were not included in the data. Each feature vector sums up to 1. Therefore, we took the first three and the fifth elements to form the covariates X,. For illustration, we only consider

---

Under review as a conference paper at ICLR 2021
SpRandom
Syshdlph
BATESWOLS S]
BATIPOLS 2J
BRTIOOO 5J
BATOOL 51
30
LI1230.00
BAT SEI
BATI2O SEI
LL1259.00
00
BATCOLSEI
LA1230.00
UL2200.00 2.5
BAT:0.54 501
20
20
3500
3000
3500
2000
(AT1200.5)
3000
BAT1210.51
3000
BAT1200
3000
BAT1200.51
LL1230.5)
2500
LL1223.5)
LL1200.50
LK173.00
LR173,40
18120,500
18,200000 51000.500
0.00
0:01
6.10
0.15
320
0.5
0.30
0.2
0.50
5:00
5.05
3:10
0.15
0.20
0.25
0.30
0.55
Figure 2: Rejection probabilities and average stopping times of the proposed test when on (-) is chosen as the spending function. From left to right: Scenario I with random design, Scenario with e-greedy design, Scenario 2 with random design and Scenario with e-greedy design.
subset of data that contains visits on May 1st where the recommended article ID is either 109510 or 109520. These two articles were being recommended most on that day. This gives us total of 405888 visits. On the reduced dataset, define A, = if the recommended article is 109510 and A; = 0 otherwise.
We first conduct A/A experiments (which compare these two articles against themselves) examine the validity of our test. The A/A experiments are done when every 2000 more users are available, we randomly assign 1000 users to arm A, and the other 1000 users in arm B. We expect our test will not reject Ho in A/A experiments, since the articles being recommended are the same. Then, conduct A/B experiment to test the QTE of these two articles. The test statistics and their corresponding critical values can be seen that our test is able to be reject Ho after obtaining the first one-third of the observations, in the A/B experiment. In the A/A experiments, fail to reject Hg, expected.
plotted in Figure On average it takes several seconds to implement our test. It
DISCUSSION
In this paper, propose testing procedure for evaluating the performance of technology prod- uets in tech companies based on the notion of qualitative treatment effects. Currently, we only focus on comparing two products. It would be practically useful to develop multiple testing procedure under settings with multiple treatment options. These topics warrant further investigations.
AA
A=
0.4
0.4
0.4
0.3
0.3
0.1
0.1
0.0
0.0
-0.1
50000
100000
150000
200000
150000
15000
20000
crticall valure statedics
0.8
crtiical values statickos
offiical values statinics
0.6
0.6
0.6
0.2
0.2
0.2
0.0
0.0
50000
100000
150000
200030
50000
100000
150000
200000
5000
10000
13000
20000
Figure 3: Critical values and test statistics.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Donald W. K. Andrews and Xiaoxia Shi. Inference based on conditional moment inequali- ties. Econometrica, (1()):609 666, 2013, ISSN 0012-9682. doi: 10.3982/ECTA9370. URL
http://dat doi 3tt.//0.00....//TTT555..
Donald W. K. Andrews and Xiaoxia Shi. Nonparametric inference based on conditional moment
inequalities. J. Econometrics, 179(1)331-4, 2014. ISSN 0304-4076. doi: 10.1016/j.jccooo
2013.10.005. URLhttp: doi wrg. 10t.:/10..1111111 jeconom. 2013. 3 10. 005
Timothy B. Armstrong and Hock Peng Chan. Multiscale adaptive inference on conditional moment inequalities. J. Econometrics, 194(1):24 2016. ISSN 0304-4076. doi: 11100666.eeconon 2016.04.001.
doi
201 201..0mm....0.......0000 04.0001
Susan Athey and Guido Imbens. Recursive partitioning for heterogeneous causal effects. Proc. Natl. Acad. Sei. USA, 113(27):7333-3600 2016. ISSN 1091-6490. doi: http:///aa..1114999111
1510489113
Alexandre Belloni and Roberto Oliveira. A high dimensional central limit theorem for martingales, with applications to context tree models. arXiv preprint
2018.
Bernard Bercu and Abderrahmen Touati. Exponential inequalities for self-normalized martingales with applications. Awn. Appl. Probab., 18(5): 1818-18888--88 2008. ISSN 1050-5164, doi: 10. 10.1214/ 07-AAP506.
Prabir Burman and Keh- Wei Chen. Nonparametric estimation of regression function. Ann. Statist,
176)):567-1596, 1989. ISSN 0090-5364. doi: 0..1214/as//11634773
Minsu Chang, Sokbae Lee, and Yoon-Jae Whang. Nonparametric tests of conditional treatment effects with an application single-sex schooling academic achievements. Econom. J., 18(3): 307-346, 2015. ISSN 1368-4221.
Xiaohong Chen and Timothy M. Christensen. Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions. Econometrics, doi: 10.00166...ccommm.215.......
188(2):447-465, 2015. ISSN 0304-4076.
Victor Chernozhukov, Sokbae Lee, and Adam M. Rosen. Intersection bounds: estimation and ference. Econometrica, 81(2)x667 2013 ISSN 0012-9682. doi: 10.3982/ECTA8718 URL.
Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Empirical and multiplier bootstraps for suprema of empirical processes of increasing complexity, and related Gaussian couplings. Stochastic Process. Appl., 126(12):3332 3651, 2016. ISSN 0304-4149. doi: 10. 10.1016/j.spa.201 04.009.
spa. 2016. 04. 009
Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Detailed proof of nazarov's inequality. arXiv preprint 1rXiv: 2017.
M Gail and R Simon. Testing for qualitative interactions between treatment effects and patient subsets. Biometrics, 41(2):361-37,, 1985.
Yu-Chin Hsu, Consistent tests for conditional treatment effects. The Econometrics Journal, 20(1): 1-22, 2017.
Jianhua Z. Huang. Projection estimation in multiple regression with application functional ANOVA models. Ann. Statist., 26(1):242-272, 1998. ISSN 0090-5364. doi: 10.1214/aos 1030563984.
Christopher Jennison and Bruce W Turnbull. Group sequential methods with applications to clinical trials. Chapman and Hall/CRC, 1999.
Ramesh Johari, Leo Pekelis, and David Walsh. Always valid inference: Bringing sequential anal- ysis to a/b testing. arXiv preprint 152.::5112004922 2015.

---

Under review as a conference paper at ICLR 2021
Ramesh Johari, Pete Koomen, Leonid Pekelis, and David Walsh. Peeking at a/b tests: Why it mat- ters, and what to do about it. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1517-1525. ACM, 2017.
Nianqiao Ju, Diane Hu, Adam Henderson, and Liangjie Hong. sequential test for selecting the better variant: Online a/b testing. adaptive allocation, and continuous monitoring. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 492-500. ACM, 2019.
Eugene Kharitonov, Aleksandr Vorobev, Craig Macdonald, Pavel Serdyukov, and Iadh Ounis. Se- quential testing for early stopping of online experiments. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 473-482.
ACM, 2015.
K. K. Gordon Lan and David L. DeMets. Discrete sequential boundaries for clinical trials. Biometrika, 70(3):659 663, 1983. ISSN 0006-3444. doi: 10.2307/2336502. URL https: //doi. 10. 20..2
Gregory Morrow and Walter Philipp. An almost sure invariance principle for Hilbert space valued
martingales. Trans. Amer. Math. Soc., 273(1)221--51,, 1982. ISSN 0002-9947, doi: 10.2307/ 1999203. URL http:::tt///ttt org. 100 0ttp:///99000/99920000
Jeremy Roth and Noah Simon. A framework for estimating and lesting qualitative interac- tions with applications predictive biomarkers. Biostatisties. 19(3):663-80, 2018. ISSN 1468-4357. doi: 10. 1009/bbosstaissiis//kx0333
URL
1093/
Piostatistics/xxx//
D.B. Rubin. Estimating causal effects of treatments randomized and non-randomized studies. J. Edu. Psychol., 66:688-701. 1974.
Donald B. Rubin. Causal inference using potential outcomes: design, modeling, decisions. J. Amer Statist. Assoc., 100(469):322 331, 2005. ISSN 0162 1459, doi: 1011190011011155000000111100 URL
org 011.1011111111111554000010011000
Chengchun Shi, Wenbin Lu, and Rui Song. sparse random projection-based for overall qual- itative treatment effects. Journal of the American Statistical Association, 1 115(531):120112)) 2020a.
Chengchun Shi, Sheng Zhang, Rui Song, and Wenbin Lu. Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings. Under review, 2020b.
Charles J. Stone. Optimal global rates of convergence for nonparametric regression. Ann. Statist., 10(4):04001153, 1982. ISSN 0090-5364.
Matt Taddy, Matt Gardner, Liyun Chen, and David Draper. A nonparametric bayesian analysis of heterogenous treatment effects in digital experimentation. Journal of Business & Economic Statistics, 34(4):661-672 2016.
Stefan Wager and Susan Athey. Estimation and inference heterogeneous treatment effects us- ing random forests. J. Amer. Starist. Assøc., 1136523); 2018. ISSN 0162-1459. doi: 10. 0221000001221159.2112222
URL httt::::/ddl..og/11...0000
2017.1319633
J.-. Wu. Jackknife, bootstrap and other resampling methods in regression analysis. Ann. Statist, 1414)1121 1986. ISSN 0090-5364. doi: 1//21/////11173333 With discussion and a rejoinder by the author.
URL httpp:://
1214//2..111//00 121.org/10..114/asss//
Fanny Yang, Aaditya Ramdas, Kevin Jamieson, and Martin J Wainwright. framework for multi- (rmed)/b (andit) testing with online fdr control. In Advances in Neural Information Processing Systems, pp. 5957-5966, 2017.
Miao Yu, Wenbin Lu, and Rui Song. A new framework for online testing of heterogeneous treatment effect. In AAAI, pp. 10310-1031 2020.
10

---

Under review as a conference paper at ICLR 2021
Input: Number of bootstrap samples B, an spending function ox.)).
Initialize: n = 0, Σi Σ Optl. 1. to = "1 = Opt1. Bo.b = 31.0 = Opt1, and a set
I = (1..... .3.......... 13..
For = do
Initialize: = 0 and @ = = Opt1.
Step 1: Online update of 3a
For i = (tx+t-1
(ta,) do
n = n + and m m + 1;
Eg = (1 (1- n اΣ + (x
0,1;
to (1- 2a + + , = a) 0,
Compute 3. Sg17a for E {0, 1} and = =suppex P (x)) BBo):
Step 2: Bootstrap
For: = ((4=1)) + 1 ((A)) do
a), L. = 4. + + (x.) - ( = 0,1;
For = l....,, do
Generate two independent NO., Ip+1) Gaussian vectors G1;
Bo.b = (1 mn- 1B,D + - -2 ca: a = 0,1;
Compute S. = supzex EE 10 (z) 30,0):
Step 3: Reject or not
Set to be the upper {a( - Update I as I t I:: z).
percentile of (Bobezz
I' > 2: Reject Hg and terminate the experiment. Algorithm 1: the Pseudocode that summarizing the online bootstrap testing procedure.
Baqun Zhang, Anastasios A Tsiatis, Eric B Laber, and Marie Davidian. Robust estimation of opti- mal dynamic treatment regimes for sequential treatment decisions. Biometrika, 100(3):681-00) 694, 2013.
Li-xin Zhang. Strong approximations of martingale vectors and their applications Markov- chain adaptive designs. Acta Math. Appl. Sin. Engl. Ser, 20(2):337-352, 2004. ISSN 0168-9673. doi: 10.1007/410255:044-013--3
URL htttps://ci.orgg 1ttp///.....01111110.00000..
s10255- 022-55004--173-11
A NOTATIONS
We introduce some general notations used in the appendix. For any matrix Mat, we use Mat|| to denote the matrix norm induced by the corresponding Ép norm of vectors, for S p +oo. For two nonnegative sequences { and {82,) we will use the notation 81,n 3 82,x to represent that $1,m E$2 for some universal constant č >>> 0 whose value is allowed to change from place to place. When matrix Mat is degenerate, Mat denotes the Moore-Penrose inverse of Mat. For any vector v. we use ())) to denote its i-th element.
In Algorithm 1, we use Opt1 to denote (p + 1) x (p + 1) zero matrix and 0p41 to denote (p + 1)-dimensional zero vector.
B MORE ON THE BASIS FUNCTION
B.1 CONDITION (A3)
(A3). Assume Amiu [Ep(( x (X) Amax Ep(X) (X) x 1, sup, ||x())] O2q
lim inf, infaex [1x(z) 2 > 0. In addition, assume
[xx - p())l
sup
y||2 3 1/2
(12)
x.yE%
1
zz
11

---

Under review as a conference paper at ICLR 2021
When tensor-product B-spline is used (see Section of Chen & Christensen 2013 for a brief overview of tenor proouct B-splines), (A3) is automatically satisfied. Specifically, x 1 follow from Theorem 3.3 of (Burman &
Amin (x) (X)] 1, max (Ex)) (X)] 2) follows by noting that the absolute value of each element in (xx) is bounded by some universal constant. lim inf, inf,ex [|<p(x)) [2 > follows from the ar- guments used in the proof of Lemma E.4 of [hh et al. (2020b). The last condition in equation [2 holds by noting that each function in the vector (p-) is Lipschitz continuous when a tensor-product
Chen 1989 sup, [|
B-spline is used.
B.2 ON THE APPROXIMATION ERROR
The proposed test remains valid as long as the approximation error satisfies
inf Bo.PrERs =EX,aE(0,1) (0,1)
sup [Qo(z, a) Qxx, a; So, 31)) = (((N(()3-11/))
(13)
with probability tending to 1. In the following, introduce some sufficient conditions for equa- tion [3
Suppose the Q-function Qo( a) is p-smooth (see the definition of p-smoothness in Stone 1982 for a E [o, 1]. When a tensor-pres massor-rroduct B-spline or Wavelet basis is used for yp()), then there exist some Ø and B that satisfy
inf Eo
sup Q0(2,, a) Q(2, az 3o, 31)1 Ogq w/d). (0,1)
See Section 2.2 of Huang (1998) for detailed discussions on the approximation power of these basis functions. Condition equation 13 is thus automatically satisfied when
q (N(T))
with probability tending to 1.
C ADAPTIVE RANDOMIZATION
In practice, the company might want allocate more traffic better treatment based the observed data stream. The e-gredyy strategy is commonly used to balance the trade-off between ex- ploration and exploitation. For a given 0 < ED < 1, consider the following randomization procedure: for some integer No > 0 and any 2 No. a E 10, E X. we set
Ty T x)) (1 Eo)aT(y (x) Bos-1) 0} + 60 a)T( (0) - -Bo.--) 0),
where
5-1 Bas -2a Σ [I(A, = a))(())) and Eas = 1 a))(())) (Xi).
1=1
is immediate to see that {t) = Ea,((e) and (t) = Banncyy- Define
x² *"(a,z) = (1 - 2 T (3) Bo) 0} + 5o [))l((((()())))) 30) s 0}
for any a E {0, 11 and x E X.
Lemma 2 Assume (A1)-(A3) hold. Assume infzex ग-" (a, x) > 0 and (a) is bounded almost
surely, for a E {0, 1}. Assume Pr(pi" Pr(pPT())) (X)(3 -Bp) Bn) t) < Lge, for some constant Lo 0 and
any > O. Then for any {in]n hn that satisfies Vonl Vlo In > q², the following event occurs with probability least -O
Σ aE(O.1)
E
Σ
m (m-1(a, ()
x (a, X)) 3 14kklogk Vk: 2 jn-
Lemma iimplies that Condition equation 5 in Theorem automatically holds with oxo 1/2, when the epsilon- -rreedy strategy is used, When yp (x)(31 3b)) is a continuous random variable, the assumption Pr[1s² (X)(3, 3o]1 < e) I Lue for any > 0 in Lemma 2 satisfied if yo (x)
3%) has bounded probability density function. When y (x) - 30)) IS discrete, this assumption satisfied if infaex 1yp (8) B6)l 0.
12

---

Under review as a conference paper at ICLR 2021
D TESTING THE AVERAGE TREATMENT EFFECTS
D.1 THE ALGORITHM
We focus on testing the following hypothesis,
Ho (1) (O) versus H1 ::: (I; > (Y)
Under (AI) and (A2), it suffices to test
Ho : (Q, & EQ,X,, versus H1 E), (),
We similarly use basis approximations to model the Q-function. Our proposal is summarized in the following algorithm. We next conduct simulation studies evaluate this algorithm.
Input: Number of hootstrap samples B, spending function ax(-)- Initialize: n = 0, Σ. Σ, Opt 1. To 71 Opt1. Bo.b = 31.6 = Opt1, @ = 0 and a set
I (1..... B). For to do Initialize: = 0, Φ
0 and To Φ Opt1-
For i = ((t-
to (tx do
n = n + 1, m = m + and x= n (n) n (Xx,)
0,1; %a = (1 - n - + 1nn+=ng((iii =
Σn (1 - -
+ + [x]
Compute 8a = E. Ta for E {0, and 6 -:)::::
For i = =N((t-1) ) + to ((t²) do
δ 6t (X,, 5 (8) 10
$ = $ + 1 (X,, )D (Y, - 40 (x =0:4,=4) a)) =0,
For b 1..... B do
Generate two independent N (0,, Ip+1) Gaussian vectors eg. 61. N 1) random variable ez:
Bab (1 mm mn-1) ),,,b - 11 1/2
Ca + 1 1/ =0
0,1;
Compute S. = ; (31, b Bo,o);
Set to be the upper {a(l) - [1/BB)/(1- (09--I/9//--t percentile of (Sp Joz:
Update I as I - {b E I: : z)
I > 2:
Reject Ho and terminate the experiment;
D.2 NUMERICAL STUDIES
In this section, we compare our procedure with the always valid test for testing ATE (Johari al. 2015). We generate the potential outcomes with the same model, except that E,'s are i.i.d N(0, 1). However, we set (TT,) 1000 and N(T,) N(T;-1) = 2n for S j < K and some n > 0. We consider two combinations of (n, K), corresponding to (n, K) (100, 5) and (10, 50). For all settings, we use a linear function to approximate Q.
In Table 2 (see Appendix G and Figure show the rejection probabilities and average stopping times of the proposed test aggregated over 400 simulations, when a (-) is chosen as the spending function. It can be seen that method behaves better than the always valid test when the effect size is small, and comparable when the effect size is large. The always valid test fails in the adaptive randomization settings, the type-I error rates are around 50% under the null hypothesis.
E
PROOFS
Note that require X to be compact set. To simplify the proof, assume X [0, 1jd.
13

---

Under review as a conference paper at ICLR 2021
S,Random
SyAtoppiive
5-Riandom
Sy-teoptive
BAT(200
30
BAT120 SEI
BATIOI SEE
30
BATGOLSE
BAT220
AVT/200L
AUT/20A
AVT1200 551
AVT120,301
00
AVT/20.91
AVT120.301
20
0
0
2000
1000
1000
1900
BAT1200.55
BAT1200.5 51
BAT1200 51
BAT1200 51
1400
1400
BAT120,011
AVT0200.5
1200
A/T1200
AVTC200 51
AVT/2003
1200
AV7120.55 561
1000
4/1120,501
1400
AVT120.311
1200
4/T/20.311
0.15
6:00
0.15
0.30
Figure 4: Rejection probabilities and average stopping times of the proposed test when a, (-) is chosen as the spending function.
E. PROOF OF LEMMA
Set Fu We state the following lemma before proving Lemma]
Lemma 3 For any 2 1, (X3, (7) 1 F3-1-
For any a (0, 1), 1, notice that
EI (Y x (X,) EI(A; = (x)))
Xt.Fi -EEX....
[I(A = o), (x,) EE
where the first equation is due Assumption (A1) and E. denotes the conditional expectation given Fi-1 and X, By Assumption (A2), we have
E X [U(A a) (a) o" (X,)&.)) (Ex
a) (Y," (x.)))
The second term on the RHS equals zero due to Lemma and our model assumption ([Y X.) 4 (X,)3a. The proof is hence completed.
E.2 PROOF THEOREM
Let ra(-) be the realization of the counting process N(). We will show the assertion in Theorem holds for any such realizations that satisfy n(tt) < n(t2) < n(tx). The case where some of the n((2)'s is are the same can be similarly discussed.
For any j 2 1, define (FF) to the o-algebra generated by Fy. For a E {0, 1}, define
Das = Σ I(A, a)x())) (X,) and Bas --11 1=1
Σ I(A = a))())))
is immediate to see that (t) = E Ea and Ba(() Bann())- Define ón = log n. We state the following lemmas before proving Theorem
Lemma 4 There exists some constant < 6u < such that Amin [ > Amax [X)(()) (X)) < Eq sup, [x(())]2 S sup, |{(x)]] S 6 v minae Amin [Ea] 60. max 1|, < 6 max (Y*(a)) S 5 and sup, maxae T (x) cn
-1
Lemma Assume the conditions Theorem I hold. Then for any sequence {ia), that satisfies ja log (ja) & g2, have with probability at least O(j=a0) that for any {0, 1) and
14

---

Under review as a conference paper at ICLR 2021
any k 2 fn.
|1(Eax Ea)ll 1 qôv + v log k; 1 a.k Eot)ll2 goz + v gh- log k.
(14)
(15)
Lemma 6 Assume the conditions in Theorem hold. The for any sequence {ja] that satisfies
Ja/ log(En) > q, have with probability least 1 O that for any {0, 1) and any
2 Im
k (X) = (T()))
1 logklog.
2
For a E {0,1}.
Bakk Ba = 24
5i-1
I( o)))))) -
-
and hence
k
Bajk - 3p -D-1
I(A: = x))) - - (X.)
(16)
T:
1
k:
a,k 1/2
I(A, = ax)(( 4 (x:)
1=1
(gōx + v qg log k)g 1/2 1/2 10g k, Ak 2 jas
with probability at least O(j by Lemma 5 and Lemma
Define
(t) 1 2(0)
ET (X)) - (xx)83) (1,) ANY (xx)))
Vn(l)
It follows that
[BB - B2x) = (1 (23 + q // log (l4))n 11/2(111))))))))))))))))) log' 1/2 1/:1//nnss n((x),, vk 2 1, (17)
with probability at least - O(n (t. (f,)), and hence
supppp (xx) (1x) sup 4p TT (x) B(t+)ll2 S o(g25m(ts) + 3/2 V n (tx) (og)) (tgg((t)) Vn n- (tx) log (fx),, =ex
mex
Wk: 2
with probability at least 1 (n (t))), for some constant ē > 0, by equation 41 Under the given conditions on and n(41), we have
4 n (1x) logn(()))) o(1), 4k > 1,
and hence
y T (x) (lx) sup p (x))(l S E(gôn(e)) + (1a) 4k: 1, zex
xex
Thus, for any given 21, 22. ..... 2k. we obtain
sup o (x) - -k.- 50
O(n (t)
max
kE (L.,,K, K}
sup o (x) - -2k $0
Pr
max kE [,..,, K)
(18)
<
max
sup o B²(((ttt)) 2xi+ {0]
+ On (=(nnooott))
KE (E(,,..,K
JEEK
15

---

Under review as a conference paper at ICLR 2021
where
=k,- = c(g8n(ts) + v Vgg--(ta log n(tx)),
2k,+ = 2k + c(gn((s)) + (qa=)((z)) log (tt))
For any i 1,1 K, define g-dimensional vector
1
S,A Vn(tz)
ET (x)) (x.)3: - E (X))(1 ADDY - (xx)))8o)]Tiii S nn(4)),
or equivalently.
&,, Vn(ls) DT (XX)) - (x.)) NJ ((x)( 2T
A,))(;(0) x0 ('xxx) n(tt))
by Condition (A1). Let &: = (ST.1) S..2. xr, T and Mj Ei=1 E, The sequence (Mi)iz1
forms multivariate martingale with respect the filtration (a :1 1}. since
B(E)+(FF)) [(E |4, [()
by (A2). Let (to)) 0. For any such that n(tx-1) <is n(+)) for some 1 S k S K, we have
|0 S
1
(x. 17
4 1000==x(X))))) (x.)8o))l }|2}
vn(())
$ 4 - 1/2 (tx)3
where the second inequality is due to Lemma 4 Therefore,
g3/2
E & ll =
//a((tt)
It follows that
m(xx
K
(tta)
n2(x) - n(tx-1)
E
3
EliE: 1sc 9/2
(19)
1132((()
k=
im
1)+1
k=1
3/2
K n(tx)) n((x-1) 3t22(tt)
+00
3/2
S 2/2 112 + 1/2
3/2
dx = (12t
x
Vn(t1)
n((s))
2
Define a sequence of independent Gaussian vectors fmi that satisfy n. ~ N(0,E(EEE) (F. for any i 1. Then the distribution of n, is the same
[[i S n((1)) Vn(ti)
ZT. I(i < n((2)) zJ
I(I S (n(nk()) zT Vn(tk)
/n(t2)
where Z is a p-dimensional mean-zero Gaussian vector with covariance matrix
Covl
Σ E (
(20)
aE(0.1)
Σ
Eg (X,](A,)
= a)) ( (
(E(0.1)
Σ (E(u,1)
Σ B('(((()))) (X,I((A =
Σ aE(0.1}
Σー B((((((X)))))) (X) X,)r
Σ
M - (a, X) xx) ((0Xx((TxXX)) (X)==-
(0.1)
16

---

Under review as a conference paper at ICLR 2021
where the second equality follows from (A2) and Lemma of T/-1 and the last equality follows from Lemma 3
3
the third equality is due to the definition
Similar to equation 19
show that
nf(t))
E ni Ise
/2/3n (()
(21)
Using similar arguments in equation 20 we can show that for any
k1 S K2 K,
m(lk)
n(te,)
Σ
-- 1a X) (
Vn(te, )m(tke)
aE{0,1}
Let
m(tkg) ) k2) = Vn(la, )n(lkz)
Σ B- (o (()))))))))))) (X)=
==1
aE(u,1}
Vn((ka
Eg
Σ
Σ & Do
Vnllt, (1((
Vn(lkz)
i=1
aE{0,1)
oE{0,1}
Consider an arbitrary sequence of Re+1 vectors (b: Jissk Under the given conditions, we have
n((x))
Σ
B(E
ET (F-1) ki2 bk2
n(tan)
B (T) (m, -T(,,, ()x())
1|br, (lll1/2 1|2-
n(ta,)
(E(0,1)
Define matrix V
V(1
V(1,2)
V(1. K)
V(2,1)
V(2,2)
K) K)
V
(22)
V(K.1)
V(K,2)
K(K
It follows that
n(tx)
E
(
Fi-1)
sup a (0.1)
(m, - n" (1)
(2n(
Using similar arguments in proving equation 14 we can show the RHS of the above equation is upper bounded by
2 sup of (0.1) 2EX,)2n(1))
; Σ
(m n" (a,x))
and hence by 2 (d with probability at least (oo Therefore, have
n(tx)
Amin
V + dn(en) Kxxxp
B(E FF-i)
0,
(23)
with probability at least - (bn)), where T Kp denotes a Kp Kp identity matrix.
17

---

Under review as a conference paper at ICLR 2021
Moreover, notice that
sup aE eEX.)2n((1)
-h (a,x) - x (a x)3
j
is bounded between 0 and 1. For any E {0, 1 and any > 0, we have
sup (0.1) =EX,)2n(4)
n (a, x)) - x [a)
Σ n 1 x)) - x [a,z))
Σ 2=1
nT (a, - 11 [[a,z)3 S2
sup as (0.1) 2e8()
j 1=1
sup ae (0.1)
(eE.)22((()
+ Pr
sup af (0,1) (EX.j2n(()
- M - xa, >3 {
Under the given conditions, have
Σ T (a, = xaa,))) 3 (0(()) + O (tn=oo(tt)) (tt)))
sup (0.1)
xEXd2n(11)
Therefore, we obtain
E
B(E (Ft-1)
mm smm-o (m + go((t)))
n(tx)
E
E Fi-1)
I gon(tt))
(24)
since n n (t1) < 8nter)- Combining equation 19 with equation 21 equation 23 and equation an application of Theorem 2.1 in Belloni & Oliverra (0188) yields that
24
Egg (eg(MM (N V))I
(25)
cv()) 00 (t1) + c2 (2()) 2n
for any thrice differential function (b)), and
co( sup (+(2) - (>22)l and c;
sup Σ 10,00r....00 ... SERPK
0,,(())),, (..00....... 2, 3,
2.5s
Jir de
where (2g(2) denotes the partial derivative 0g(z)/02()) for any function g(:) and 201 stands for the j-th element of z.
Let X4 be an e-net of X that satisfies the following: for any & E X, there exists some 2o E X such that ||æ rolla < e. Set = vd/n²(ta) Since X [0, 1]d, there exists some X. with
X S (t1):
(26)
where [xp denotes the number of elements Xn. Under Condition (A3), we have
sup inf [|((()) - p(xo) 12 3 /
#e =x
(t,)))
18

---

Under review as a conference paper at ICLR 2021
It follows that
(z)ul 3 V n
sup 1=]|==1 sex
sup op
T (x)
sup yp oc
(27)
Using similar arguments in showing equation 17 can show the following event occurs with probability at least 1 - (t1)),
B (tx)ll2 1 q 122 log" 1/2 n(tx), vk 2 1.
This together with equation 27 yields
max (L....
sup & (tt) max
4 (x)
K} Tex
(L.... K) xEXo
glog (tx)
max kE(
sup 40 (xt) ØEX
sup & (x) xEX
(t1())
with probability at least 1 O( ((n-1(tt)) (t))). Under the given conditions, we have n(ti)
max(q, log n(tx)). It follows that there exists some constant ~² > 0 such that
max s (z) kefl.....) x2xx zEX
max sup & (T)))B((k) sen ((n)) kEfL..., x zedo
(28)
with probability at least On
Define
2. = 2 - E(qōn(te) + v qm (tx) log n(x))) E'n 2(1))
2 2k c(qōm(e)) Vqn - (1x) logn(( + + - (41)
Combining equation 28 with equation 18 yields
Pr
max
sup 4 (x:)B((()) = 50-
O(n (b)))((1)))
kE (k...)..
s (x))(l)) -2x {0]
< Pr
max
(29)
ke (I....... K}
x
< Pr
max
sup 4p T ((:)BB (tx) - -2h.t 0 + (a)))
kE(1....,K)
Notice that M (t) (t2) (Btb
(tx( By equation 26 and Lemma there
exist set of vectors d1, d2, ... dr E RoK with L (t)) max, | 11 S _ " g// and function k(-)) that maps (1,.... L} into (1..... K} such that
sup & T (x)BB (tx) mn ] max {d] Mu(tx)) vk()), x
max kE(l....) K)
(30)
I85S
for any {vx { For any 17 > 0, m E RoK consider the function on (mr)a RoK - R, defined as
Dndeersa (m) log
explold] - meniil
has the following property:
max (dz (x()) S (n.(mrhamm) _ max [d] moiil + -1 log L ISiST.
15,51
< max (d, m =xG)) + + - flog K + 4d n(11)} 1S1SL
max [d] m (MEG) -1 log K 17 -1 n ((1)]]. 1SiSL
19

---

Under review as a conference paper at ICLR 2021
It follows that
Pr
max
sup s (x) =//tt 00
Sr (r((0
(31)
RE k))
sup y (z) (tx) - -2h,- ) {
Pr
max
(32)
(k.()...
=
Pr
max
sup 4 (x)) (tx) - - - -36) S <30 2 Pr Pr(onite de (Ma(ex)) - 36 EE
k)......
where
* + (log K + 4o m(41)} and = - 36.
The value of ó will be specified later. In addition, with some calculations, we have
El= ded exp (vld, m *x(0)))
0.Qnivvaea (m)
Ei= exp (nld, m uR(O)))
Ii afti) dete) exp (nld, m ma(el)
Oj Onivell
E/ exp (pjl} m vwccl))
I Eter did exp (nld? m vncil)
Et exp (vld, m -u(oll) }
E/e dor detz) d(ss) exp (nldf m -k(ci))
230 On. (m) = 17²
El= exp (ni jd m ms(1l)
E/n dft der exp (nld m pe(ol)
3r/²
Eie exp (gld, m - mecol)) }
1= (10)) exp (nid,
m mm(ol))
X
Ete exp (pld, - (x(il)
I1 Ele df exp (nld, m re(a)))
+ 2n²²
E/e exp (nldg m vn(ol)
Since max; ||db|] 5 1/2 obtain that
Σ 10,00. (m)l s t 1/2
Σ
0 Oz Dn (n (m) s 227c0"
(33)
J1:32
Σ
0, 0
2n (mx (m) s 6n 3////
Ja
By Lemma 5.1 chernozuukor et al.
2016), for any 0, there exists some function g.(+) R +
RR with llo < 8-1, |l oooo < Koō lig, 1l S Knd- for some constant K₂ > 0 such that I1(zo S 0) S gg (20) S I(=0 S 36), v8 R.
follows that
(u hu (m) < 0) < g Ir (m) < I(dd )a (m) < <36),
for any m Roc Combining this together with equation 30
equation 31 and equation 32 we
obtain that
Pr max kE(),..,K
sup o (x))B =k.t (xERa
50 < Egs on (Mn(ex)), (34)
max
sup 4 (x) - - 5 x
2 Egg o @n da (Mz(ex)). (35)
AE()...,K)
K}
20

---

Under review as a conference paper at ICLR 2021
Consider the function Sa (unha Apparently, we have
sup colBs (ni(vn)) s 1.
(36)
bv
By equation 33 we can show that
c2(gs o (n.(v)))) 2 79.
sup d
(37)
sup ca(gs (n ).) 3 /0/ + 2////// 3/2 + 8 97/0/2 8
Set 8 = n (log K + Ad we obtain
(gs (m g (log" K + log' n(ta)); 1= 2,3.
sup m.prch
Combining equation 37 together with equation 25 and equation 36 yields
sup Egg An (Mu(ex) - Egg Dn (N(O, V)) (v.)
M n
1/2 (t))q") 2 7f (log" K + log" n(tr)) + g flog* K + log" n(t2)) + n nt)())
This together with equation 34 and equation 35 yieldss
Pr
max ky
sup & (z)BB (tx) 2k,t 1 0 Eg, Pn. Pn (N V)) (38)
3 (ti)g 3 " (log K - log n(t1)) + 22)122220 (log 2 K + log" n((1) n((t)) + = (ti),
sup 4p" Bx) (tx) 2t. ) 50 (39)
Eg o (n (N V)) Pr max kE(l....KKK
= n 1/2 (t1)q" 1 (log* K - log n(tt)) + n²n² (log" K + log" n((1) b(ti))dn(es) (on(es) +n 0o (tz).
Similar to equation 31 equation 35, we can show
Eg, (..( ) (O, V)) s Pr (o (N V)) s 36)
max {d] N(O, V) - - )=0) z0)
< Pr
max {d] ((0, V) - 21())+ } S $36) = PPr
ISiS
Eg, o On. Ja (N V)) N Pr (on.eei la (N V)) s =0)
N(. V) - = z0). >) I4iSL
2 Pr
max
where
2k.t 2/,+ + 17 (log K + 4d log (tt))} + 38 and -ズح 2/_- - -1 --"ooo K + (ddlogn(t)) -35,
for each k. Notice that for any {uxten we have
(sup &p (T))G((()) - ux < =00=
max [d] N(0, V) - mnci) $0) ISISL
Pr
max kE k).
Pr
This together with equation 38 and equation 39 yields
Pr
max ke (. K)
(sup sup (aEX
T (x) - zx,+ 5 0 Pr
max (E((l....)) K}
(uu 4 (z)G((() zx so}
(
In 1/2 "11 (log3 K + log n((1))) + q211² (log² K log n(11)))n((t))) +n aa)
(uu p (x)B* (tx) - $0)
Pr
max kE (E)...))) K)
sup x (a))(((1) - < Pr
max ke k)(
1/2 (log* K log n(11) n2 (log² K + log n (l1)) (m((.)) n a0 (1))
21

---

Under review as a conference paper at ICLR 2021
In view of equation 29 we have shown that
Pr
max Ie(l....
sup n
o T (x)B(tx) 2k
=0 -Pr Pr
max
sup x (x))((t) 2x.t 20
A K) E
nn 1/-1/2 (h )4 flog" K + -log re((11) + (log? K + log n(t1)]00((1) + (1));
Pr
max KE K)
sup T (t) - =2 =0 3 n 1/2 9 "1 flog' 3 K + log n(l1)] }} + /²/1/ flogg K log" n(11) (((11))6, (n((s)) + (4),
sup o m
T (x))((t)) -xk-- - - Pr max kE(l).n))
GEX
(41,
The covariance matrix Cov (G (1+)) ) is given by (o. 2 and is nonsingular by Lemma
In addition, we have ||<(())) 2 E, Vx E Xo. by Condition A3. Thus, there exists some constant
Cs such that
1/2
5 (I)
Σ
Eg D Da
(0(x),
Va Xo.
(E(1)
By Theorem of Chernozhukov et al. (2017), we obtain that
(uu o (z()G((t)) -/:²² so}
Pr
max ()
(x)G((t)) 2kit xE
sup
$ 50 Pr
max Re(
3 7 (log K + logn(tt))332 + gōn(tz) flog K + log logn(tt))) + (ti) logn(t))) K + log (
Thus, we obtain
Pr max kE(L....KK) K} Axc
sup (uppp(xxBB) (x))(tt)= 2b =0 - Pr max ke(l.....k))
sup
sup p (x))(tt)) 2k s =0} lEE
1 n 1/2 (4 " (log* K + log n(ti)) + q217 {log² + log² (ltt) + at
+ 17 - K + log n (t, (tt)) 3/22 + gon(t)) flog K log (21) 22/2 / (t1) log (lo) K + log n(t2))
log Setting 7 min(g n ((1) log 8/8 (Kn(4) (4) n 00 (( log- -003311/8 1/6 (Kog_////1//(K((1))) (Kn(l1))) yields
the desired results. The proof is hence completed.
E.3 PROOF OF LEMMA
The assertion trivially holds for = We prove it holds for any 2 2, by induction. By (A2), we have (X,, YJ (0), (T)) 1 11 Since (X,, Y (0), (1)) L (X,,Y)(0) (O),)))))))) this fur- ther implies (Xg, (0), (1)) 1 Ai and hence (X₃, (X,.Y,(0)) (0), Y (1)) 1 (X1, A1, (0), (1)). By (AI), Y1 is completely determined by A1. ()( and (T)).. Therefore, we obtain
(X,, YJ (0) (1)) 1 F1.
Suppose we have shown that (X,, (O), T F for some k < < To prove (X,, Y,,Y, (2 (0), (0),Y, (1)) 1 Fa+1, it suffices show (X,, (O), By (AI), Ys+1 is determined by Ast1. 1 (0) and (1). Since (X,, (,) 1 (X441, Y (0), (1)),
1 (X4+1, Ye41)-
(1)), it suffices to show ()), (1)))) 1 A This is implied by (X,, (O), (1)) 1 Ast1l Xx+1, F& and that (O), 1 XR.1, The proof is hence completed.
E.4 PROOF OF LEMMA 4
The assertions
cD S Amiu [p(X)pp TX)) S Amax (Bp() (X)] (XX]] s L
(40)
and
sup [|((2))1111 'o'.
Vg.
(41)
22

---

Under review as a conference paper at ICLR 2021
for some co are directly implied by the conditions that Amia (Bp(X) [X)] 1, Amax (Ep(X) (X)] x 1, sup, Ilı(())]ı I co Vg. Since (|x(())2 || we obtain supg || S sup, [|((())] S cu V7.
Under the condition infa, T² (a, > O, we can similarly show that Amin [Ea] 2 co for some eo > 0.
Since (0) and (1) bounded, there exists some constant 0 co < 1 that satisfies m YY (a)l I 6 Notice that (T(())) (x) (a)x z). Boundedness of (Y (a)) implies that the conditional mean E(Y" ({Y"(a) is bounded random variable as well. As result, we obtain suP= (0,1) |sp (a:)3ol 60'
Notice that 3g- Σg1 Bp (x))"(a)) Since Amin [x,] is bounded away from 0, it suffices show || (X)Y* = O(1), or equivalently.
sup
EE T (X)))
= 0(1).
wEBe,II ||
By Cauchy-Schwarz inequality, it suffices to show
sup ElY"(a) x(x)) O()))
MERM, VERt,|peee | 2=1
Since (a)l = (1) almost surely, we have by the condition Aemax (Bo(X) (X)] = 0(1) that
1 x())
sup V ==Ex(X):p (XX)v S Amax (Bp(X)' [())] = 0(1). VERF,||ulla-1
sup
VERV, 12-1
The proof is hence completed.
E.5
PROOF OF LEMMA 5
E.5.1 PROOF OF EQUATION 14
Notice that
15( E1)ll2 =
Σ (A) (X,) - (1.)m-(11.)0000)))) (x)}
(42)
1 /
+i B x()+ (x)
Ti- (1, - x" - x1,
2
By Lemma
we have
1
B x (x)
Σ 1=1
n. 1 (1, - =1,1
(1, x-" (1,
1=1
< En q2
00 log 00 j. Vj N In.
with probability at least - -(jz=aa)
Consider the first term the RHS of equation 42 For any 2 define M, (x)))
(A+
T;-1(1, (1, X.)). Notice that [Mi forms a martingale difference sequence with respect to the filtration (a(F: i 2). since
((x) T
(43)
B [((p(X)))(X) (4, (X,) 0,
where Fi. denotes the conditional expectation given X; and F, Here, the first equality is due to that X; JL Fi-1, implied by 3 Under the given conditions on the basis function (-.), using similar arguments in proving Equation (C.15) Shi et al. (2020b), we can show that the following event occurs with probability at least - 0() 2).
i
Σ i=1
M
1 v qi log(ī).
23

---

Under review as a conference paper at ICLR 2021
Notice that Σxz, 2 + probability least 1 0,
= + +5- KRy kky 1
Thus, the following occurs with
(x; T (X,) - -E TT (T,-1(1,)) [X)}
1 Vj
qj Jog
vj 2 jn. (44)
follows that
|[() E1)[l2 1 qôv + Vgk- log- k, Vk 2 In.
with probability at least - D(j-ao) Similarly, we can show
I(Eu, Eo)ll2 1 qōx + / logk, wk 2 in.
with probability at least 00) The proof is hence completed.
E.5.2 PROOF OF EQUATION
15
When jn satisfies jn. / /log"o" "0 (jx) >> q², it follows from equation 14 and equation 40 that
Amin Ea, 2 Amin [a] [Ea. Ea 2l 2 2 1 Eo. Vk Jn.
(45)
with probability at least 1 - 00) Combining equation 40 with equation 45 and equation 14 we obtain
| 2- (B,, En)Di 1l2 Amin Amin Eu. Da,k k Mall
9ox + Vqk logk, Ak: Jn.
with probability at least 00) The proof is hence completed.
E.6 PROOF OF LEMMA
For any e {1..... 9 and 1, define M,()) (X;),, O (X.)8;) Here, (X,)
corresponds to the 1-th element of (Xx)). Similar to equation 43 we can show {Mi(1) martingale difference sequence with respect to the filtration (o(F+-1) 1}. By equation 43 we have for any 4
forms
B((( Amax S 5.--
(46)
Notice that
< (X)
=
- o - [x]) -
< 4ep "B (x))) <45.
where the first equality is due (A1), the first inequality due to that A is bounded between 0 and 1, the second equality follows from Lemma the second inequality follows from Lemma and the last inequality due to equation 46 It follows that
B(M(O))=L)) S 4ht
(47)
Similarly, by (A1) and Lemma
we have
Mf < 4G
Σ ( (x,))
(48)
Similar to equation 44 we can show with probability at least 1 - 0(j-1) that
[M - ((M / log Vk 2j
24

---

Under review as a conference paper at ICLR 2021
Thus, for any sequence in that satisfies Jn/ log(jn) > q, have by equation 47 that
M2O + Σ B( S ck 4k 2 Jn:
1=1
for some constant ê > 0, with probability at least 1 - "O It follows that
Pr
M101 - 2/ čk log
k25n
(M70) (MP0) S 2t) s })
> Pr
1
Mi(1)| 2 log
k2ja
2m1
125n
[M((1) + (MP 2k) 1) Olin') -065")
O(in') Pr
k2in
1=1
(M() + (M(0)-F11) = ok) !)
Pr
UIΣ
M((1) > 2 Vaklog k
A2Jn t=1
k2 1=1
(M 266 1)
2 1 1- Pr
U
M() e/cklogkt
A23
O
By Bonferroni's inequality and Theorem 2.1 of Bercu & Touati 2008 we have
Pr
Σ
M((1) S 2/ ok log
2 1 - -(1nt)
k2Jn
Σ Pr
M,(I) > log
[M2(1)) + (AP())ELIN
k21
#22n i=1
Σ [M(0+ + (MP())--1) ak #)
2 1 1 1-0(jT')
Σ Pr
M1(1)| > 2/ ok log n
kijn
4ck log k.
M 0(7 2
Σ exp
Σ
2k-
(49)
2ck:
The last term on the RHS of equation
To summarize, we have shown that the following event occurs with probability at least -((in
49 is 0(;=))
M((1) < 22k log
By Bonferroni's inequality, have
n
Σ
$2 log k
12
with probability at least 01j Similarly, we can show
n
Σ (1.)(1-A)))))) (Tx.)800
S cv gki log
k2j
1
for constant e 0, with probability at least 1 O( The proof is hence completed.
25

---

Under review as a conference paper at ICLR 2021
E.7 PROOF OF THEOREM
3
We state the following lemmas before presenting the proof.
Lemma Assume the conditions in Theorem
3
hold. Then for any sequence (aann that satisfies
/n log 00 in 2> g², we have with probability at least 1 - -(7 that
1Ba, Ball2 3 39 k212 /ogk, Va E (0, 10,1), Vk jn.-
Lemma 8 Assume the conditions in Theorem 3 hold. Then for any sequence {Jain that satisfies
Jn / log" t0 In >> q², we have with probability least 1 - 0(j that
II IIA, x))((x))) - (X.))a) Da
3 9 + 9122k=1/ 1/2 /logk, k
k 1=1
Va E 10, 2 in.
Similar to the proof of Theorem we will show the assertion in Theorem 3 holds for any n(-) that correspond to the realizations of N-) that satisfy n((1) < ml(2) ... n(lx). For any
1 S k S l2 I K, define
(k k2) Vn(k,, )n(tka) Cov (3TTh(( (taa) - MMB (tx. 31 (tx2) 3tta(tt)) Pam (txa) ((x)) K))
n(t))
1
(T)( =))(X))) - (xx)))
)n(ke))
a=0
and
(1,1)
((1
K),
((2
V(2,2)
K)
V=
V(K,1) ((K,2)
K(K,K)
We aim to bound the entrywise to norm of V V where V is defined in equation 22
suffices to bound maxisk sups, b2 1, =|===1/=/11=11 167 (K1, k2) - V(k,, 1z) Ybu =
maxigk (K k2) ((k,,, A22 For any kn h2, we decompose ((11,22) V V(ki, k2)
as
(ka, V(ki, k2) = (K1 - (k1, + (k1, p- (k2, k2) + Vir (k2, V A:2).
where
(k(,,, = /n((te))((us a=u j=1 i=n(()-1)+1
Σ I = (xX)VX (()))
1 n(tt,)
(r*(k, k22) Vn(tk, ((tk2))
E I(A =))(())))))))))) T( (x)) - (T)))))5(((X00 ((x))8a)
a=0 ا=1
By Lemma 4 and Lemma 8 we obtain that
max 1 Sky
|
k2) - (2)11,
a(tag
max
Σ
= =))(x))))) (xx.8_, -
Ex 1 D0
ŠK
n((kkn)
a=0
j=1
n(te,)
< max
Σ
[) - - 4a
IShiS
6 a=0
7
n((kat
1=1
x gdn(t.) + -/2 11/2(11/2))))))))))))))))))))1
(l1))To
(50)
26

---

Under review as a conference paper at ICLR 2021
with probability at least O( (non)o(t1)
Notice that
Vnlli, )nlee)
I - ())( (x)) - (x
a=u j=1 i=n 1)+1
ΣΣ
IAA ()) 4 (X:) (x)) + (x.), -0- (xxx))((t))>²
TA' =))((x))) ((x))))((00)'>)))))))) (x.) - (xxx)3((())3
(1)-))++
Σ IT' = x)
- -
(1)111))
+ )ntt (k1,
It follows that
1 (2) - (2*())
max
SkaS
1
Σ
==I(AA))))( = (xx))x - (x)
max
1 SK n(th,)
a=0 j=1 (=n(()1)++1
1 h
2
ΣΣ
Σ
I (x) (xx,) (x.))33 (x,)(Bc-Bactt)))
max ISkISK n(t.,)
j=1 (1)))=1)++1
By Lemma
we obtain that
max
k2), - (ka k2)
(51)
SkoS
(x,))) Σ
3
T(A; a))=()(XX))p) ( (x:)) (x,)) - - (xx))
1sk, SK n(ta)) (0.1)))
(1
A1
R(1))
+
max
I(A: = a))((x) (x))()))))(XXXX)X))))))))))))))) - ( Ba(()))
(x.)
1 1sk ntt,,)
ae (0(1)))
i= 11
22.0.
By Lemmas and 7 we have with probability at least - ((n-(((n)))) that
n((k,)
1
V Vi ll2 I n2t) log(n(tz)}
I(A, a)p((x)) VI s ki S K, a 10.
(52)
n(tk,)
n(tRa)
2
Similar to Lemma
5
we can show there exists some constant c. > 0 that
n(te,)
Σ
[I(A: = a)p(X:) (x.) - F (u(A, = ()p(X,) (X.)) T(
(53)
n((ta))
catoon)(),) + Mog
v1 & ha S K,a (0.1),
27

---

Under review as a conference paper at ICLR 2021
with probability at least 1 O(n (t)). By Lemma 4
we can show with probability at least
1- O(n ((t)) that
[((kg] Σ E - = ()) (x:))
max 1kkis n((t,))
=0(1.
This together with equation 52 and equation 53 yields
n ((,, 1 2 1 x2n (4) log (m(4)))) iI h1 s K,a (0.1),
(54)
with probability at least On (t1)).
Moreover, using similar arguments in proving Equation (C.15) of Shi et al. (2020b), show that for any 1 I l I K, the following event occurs with probability at least -O(n" -tt,=(tts)) )),
n(te,)
1
I(A, = (Xx((())))))))) - ( (x,) Σ
3 -11/ logn(tk,)
(tx,
r((t,)) )
A1 $ l S q.
Since
EmI=1
K
n (11,) n (41) obtain with probability at least 1 - (()) that
n(tez)
1 n((k,))
I(A, = (X)) -x (xx.)3.0) Σ
3 1/2 112 (tgg))loogn(tt))
1A 9 K.
In addition, it follows from Lemma that n (tk, )l k, 1l2 1 97 3/2 (l1) (og(n(t))): AI s S e (0.1).
This together with equation 54 yields that
(ki,, 1z2) - p. (k2,, | 1 (tz)))tttt)))) log n(tr),
max 1
with probability at least On (t1)) Under the given conditions, we have (K1,,22) m2)|| 3 nn (11) log 1/2 n(11),
max 15k Sk
(~ (k1, 1:2) "0*(
(55)
with probability at least On
Moreover, with some calculations, we can show that
((11,))) k2) (k1,k))))
1- -t)(lll
max 1 SkySk
max J21
2
2
I(A: (X) P
X
max
1 IKKSK n(ta,)
j=1 i=n(t=1)++1
n(t))
1
IIA xx
max
Skky K ntt,,)
(1)+))
X max Σ
(t;))l
In view of Lemma 4 and Lemma 5 we have with probability at least 1 - OO (41) that
(ky, k2)
D (kg, kz)
< <0(1)(dbmt))) + vg log (tr))
max
n(ts)
1
Σ
[ -))x))) (
max 1sk Sk K n(ta))
i=n(t]-1)+1
28

---

Under review as a conference paper at ICLR 2021
where ((1) denotes some positive constant. Similar to equation 50 and equation 55 with probability at least - O(n ((n=no(t)) that
show
max (0 SKISK n((ta))
max
V3,ak V/ = =(1)
Similar to Lemma
we can show max.c (0.1) ||aall2 = 0(1). follows that
max 1g
(k), ka) [ki, k2) - V- (ki,
3 gdn((.)) + (tn=
with probability least 1 (n ao (81).. Combining this together with equation 50 equation 55 we obtain with probability at least 1 - (n n an (t1)) that
((k1,))) ((k1, k2) 2 (on(ts) v qn qnn-((t)) (t2) log (tz). SKaKK
max
Consider the function go (n.( defined in the proof of Theorem We fix 8 n7 flog K + 4d log n (t1)). Based on Lemma A2 in Belloni & Oliveira (2018), we have with probability least
1 - On (t))) that
sup E'gs (n(0)) V) Egs (n. (N mna {
I qu (log² K + log" n(t1)) (gdm(t)) + v qn
qo--(ttt (t1 logn(t))
where H" denotes the expectation conditional the observed data. For a given set of thresholds (uk Ja using similar arguments in proving equation 31 equation 32 equation 34 and equation 35
can show with probability least 1- OOnn an (ti))
that
Pr
max k)
(Vn(te)SMB- m/) S 50}
S E'gs o o (N(0,
< Eg, o on (N, V)) + 0(1)gn (log² + log n(ti)) (gōnee)) + v Vqn-1(( (11) log n(t1)
sup v0 (x))((1)) - - {0) (EE
< Pr max k)
+ O(1)qn² (log K + log n(ti)} (gōm(te) + / /qn (tg) log)()))).
and
max k) (Vi(L)Jsmee - v2) 50 2 EEgs Onlu. (N((( F))
Pr*
(4:) Eg, o On.(vx la (N(O, V)) 0(1)m flog² K + log² n(11)} (gonce)) + vqn- log logn(()) v
(uup o (x)G((t) ( 50
2 Pr max (kE(I..,,)))
xxE
((1)q1² (log² K log n(ti)} (g5m(e)) v /qn-1((s) log logn(tz)).
where O(1) denotes some positive constant, and
(4dlogn(ts) - Vk,+ = + 17
+ log K} + E" 2nnn-2(())) (t2), V2,t = Vk,+ + 3n (4d (ti) + log K).
Vk.- Vk -1) (4d (()) log K} e'n -((1) Vi_ UN-- - 1) 34d (( log K}.
By Theorem 2 of Chhrnozzuuko et al. (2017). we obtain that
Pr
max kE(L...,K) K}
sup & (Tx))((t)) v S Pr Arr
max kE.,...,
sup TT (x))((t)) vi.- S
1 "log" 3/2 n(11) + log 3/2 K) + c'n ((1) 1/2 n(11) log
1/2 K}.
29

---

Under review as a conference paper at ICLR 2021
It follows that
(Vi(ta)Smm -ix) -m) =0 -Pr (E(lim)))
(supyT (z) Mk z0}
sup [v
Pr max (E(I..)))
max
3 qm/ (log" K + log n(11)) (gōn(t)) + VQq (1111((1)) log re((1)
+1 "10g" 8/2 n(t1) + log K} e'n (11) n(ti) + log 1/2
log K}.
with probability at least - (tn))) Set
log 7 minly n (10 22000/ {
log 1/3 (Kn(t)))
we obtain the desired result.
E.8 PROOF OF LEMMA
Combining Lemma 6 with Lemma 4 yields that
||
D
Σ I(A (X) (T (xx)).)
1 1x 1/2 //og/ ko, 4k 2 jn. {0,1),
with probability at least -). Combining this together with equation 16 yields that
1Ba, Ball2 = =/ 1//22211// log
Vk: 2 Jns a E {0, 1},
with probability at least 0(7 )) The proof is hence completed.
E.9
PROOF OF LEMMA g
Notice that
I(A: - (x (xx)))))) 2.
T(A a)) -
- (T(x))33) 0² X,)
k
Σ
((A (x.)o²aa X,) $
(56)
h
Similar to the proof of Lemma 5 we can show that the second term on the RHS of equation 56 is of the order Oggōz + / /1 log k), for any {0, and any k 2 Jus with probability at least - O ". ). As for the first term, notice that each element the matrix
I(A. =
- (x.))B..) - o² (a,
(57)
corresponds a martingale with respect to the filtration (F(FF 1}. under (Al) and (A2).
Using similar arguments in proving Equation (C.15) of Shi et al. (2020b). we can show that
I(A: () o (x))8))- - Xi)l
3 1/2 1/2 Vloggloooooo k,
t=1
Va E (0, 1), k: 2 jn.
with probability at least t0 The proof is hence completed.
30

---

Under review as a conference paper at ICLR 2021
E.10
PROOF OF LEMMA 2
We begin by providing an upper bound for maxae(0.1) [| - Ball2. With some calculations, we have
max EE (0.1)
11
Ball2
max (0
D-1 a.k
= (x.)
2
< max ee(U,1)
5-1 0,
max (0,1)
Σ
(X, - 8xx))
i=1
By Lemma 6 obtain with probability at least 0 that
max (E(0),)
Σ
(X,) ( (Xx))))) 3/ 11/ Vogh; A4 2 Jn.
(58)
i=1
Similarly, show with probability at least - 0(5²1) that
Σ ((X)) a) ('xx))8a)
// 11/2 Vlogjn
(59)
(E(0.1) K
41 S k < ju.
Similar to equation 42
have
Amin
Ea,kl 2
min Amin aE(u,1)
(F (x)) Σ T (a,
ac (U,1)
1
(X,) - X)p()) (
max aE(0,1)
Using similar arguments in proving equation
44
show that
max (0.1)
[I(AA (X,) - B - (x, (x)) (X)]
3 qk logk, (60)
2
vk 2 jn:
with probability at least - O(j='). Similarly, show
Σ ( = a))(())) (X,) E (a, (X)) (0(0.1)
max
3 v gk log (61)
V1 < k < In.
with probability at least O(
Without loss of generality, assume En < 1/2. Notice that we have ;; (0, 1), x X and Ng. This together with Lemma equation 4 implies that
15-1(a, (a, x) > Sg. for any a e
Amin (B= (x) (()) Σ (a,
n
No
j No
inf as (0. (0.1).m2..
eu
Eu-
Combining this together with equation 60 and equation 61 yields
Amia E
Vk > L" / glggin.
max a5(0.1)
for some constant L' > 1, with probability at least 1 - O(j,1). This together with equation 58 and equation 59 yields that
[| Ball2 2 1/2 1/2 1/2/Tog max(k; 4k 2 I / login.:
max (E(1)
31

---

Under review as a conference paper at ICLR 2021
with probability at least - O(ix')) ).
By Condition (A3), we have
Ipp (x) Ba,s 31 + B6)1 S Lgk 1/2 max 10001////'//// 1/2
wk 2 L" Volog. (62)
for some constant 0, with probability at least 1 - O(
For any 21, 22 R. we have [(21 > 0) A 1(=2 > 0) only when |2| =2 |22/. Hence, under the event defined in equation 62 the event 1/ (x) x) > 0} + H(p((X)) (bo) 0} occurs only when
10 (X)(81 Bo) s 10 (x) Bo. B1 + Bo)l Lak 1/2 /log max(k,
for any à: 2 jn- Under the given conditions, we have
Pr (10 (x) Bo)1 - -/2-
1/2 log max(k, S LLogk 1/2 102g1///2 max((k Jn). (63)
Notice that when (11) - Bo,k) > 0} = (x))
So) > 0}, we have x² Xa, if 10 (X) Bo)1
Th [a, X) x" X). Thus, we obtain (X)
Lgk- 1/2 Vlog max for any A 2 L'vg Jog Set ko = L U'valoge Voglognn. By equation 62
and equation 63 we have with probability at least 1 - -(rz) that
kp
Σ
Σ
T (a, X) (a, S
Σ
B m (0, X) (a,
aé (0,1)
at aEf0,1) i=1
Σ
B 1 X), X) - x" (a, X)I - 2L' Vg
oE [0.1] (=
Σ
Σ
B 1 (a, X) x" (a. X)/11 ((X))lT(X((B, (X)(31 Bu)l > Lqi 102111111111 log
oE (0,1) i
Σ
B Mi i (a, x >" x)|T(( (X)(8 -B01 s Tqii 10gg 1/2 i}
1og1/2
AE (0,1) i=
< 2L' Jg
Pr (x) - Bb0l s Lqi 1/2 /log 1 9// 1/2 1/2k, k, Vk
Ij.
ae (0.1) k= +1
The proof is hence completed.
F COMPARISON OF THE BASELINE
Consider our test statistic S(t). Under Ho, it can be bounded from above by
sup =ex
(3) T 3 (t))) 96).
(64)
It suffices to provide an upper bound for the above expression. By equation 64 can be upper bounded by
inequality,
sup
(lc(=))la)B - , -Bo(t) + 16 #EX
suffices to provide anytime upper bound for [1)) - -Bo(t) -6
Recall that
(1) 31 -Bo()) + 3 1
N(E)
Σ = = 10)== - T - I(4, = -xx))
= N(t)
i=1
32

---

Under review as a conference paper at ICLR 2021
The above expression is asymptotically equivalent to
N(
Σ -
+x(x))
(t)
By the law of iterated logarithm, the f-th dimension of the above expression can be upper bounded by
N (1) log (N))
where E,07 can be consistently estimated by
1 ((
Σ [[A (0
- I(A, (0)x)(())) -x),()
(
As such, the finite error bound given by
sup sup||>>>>||> V log log (N())
x
=EX VN((t
N( Σ [I(A,
1)Σ, 1) (())((X)) (TAAAA)(----TXAAA) (xx)), 1(4, (t))(()))))) ((x)))Bo(t))1
(()
G ADDITIONAL TABLES AND FIGURES
BAT
LIL
method
Random
Adaptive
Random
Adaptive
(n, K)
rej probs
E[stop]
rej probs
E[stop]
rej probs
E[stop]
rej probs
E[stop]
0.00
5.0(1.1)
3537(14)
6.2(1.2)
3534(15)
0.0(0.0)
3600(0)
0.0(0.0)
3600(0)
0.10
17.2(1.9)
3400(24)
18.5(1.9)
3409(23)
0.0(0.0)
3600(0)
0.0(0.0)
3600(0)
0.15
36.0(2.4)
3184(32)
35.5(2.4)
3189(32)
0,2(0.2)
3599(0)
0.0(0.0)
3600(0)
(200, 5)
0.20
55.8(2.5)
2914(36)
60.0(2.4)
2908(36)
0.5(0.4)
3598(1)
0.8(0.4)
3595(3)
0.25
79.5(2.0)
2545(35)
81.5(1.9)
2528(34)
1.8(0.7)
3590(4)
2.8(0.8)
3585(5)
0.30
93.2(1.3)
2286(27)
95.2(1.1)
2280(26)
7.2(1.3)
3560(10)
7.5(1.3)
3549(11)
S1
0.00
5.2(1.1)
3879(18)
5.5(1.1)
3882(18)
0.0(0.0)
3960(0)
0.0(0.0)
3960(0)
0.10
17.2(1.9)
3716(29)
24.0(2.1)
3651(32)
0.0(0.0)
3960(0)
0.0(0.0)
3960(0)
0.15
39.5(2.4)
3394(40)
41.2(2.5)
3365(40)
0.0(0.0)
3960(0)
0.2(0.2)
3958(1)
(20, 50)
0.20
61.8(2.4)
3021(44)
61.0(2.4)
3013(44)
0,8(0.4)
3949(6)
0.2(0.2)
3956(3)
0.25
84.0(1.8)
2588(39)
83.5(1.9)
2579(39)
4.8(1.1)
3919(11)
3.5(0.9)
3936(8) ()
0.30
95.8(1.0)
2281(28)
95.5(1.0)
2275(28)
12.8(1.7)
3847(18)
14.5(1.8)
3873(15)
0.00
5.0(1.1)
3537(14)
6.2(1.2)
3534(15)
0.0(0.0)
3600(0)
0.0(0.0)
3600(0)
0.10
8.8(1.4)
3511(17)
8.8(1.4)
3515(16)
0.0(0.0)
3600(0)
0.0(0.0)
3600(0)
0.15
25.5(2.2)
3346(26)
26.0(2.2)
3337(27)
0.0(0.0)
3600(0)
0.0(0.0)
3600(0)
(200, 5)
0.20
57.2(2.5)
3004(34)
60.2(2.4)
3000(34)
0.0(0.0)
3600(0)
0.0(0.0)
3600())
0.25
87.2(1.7)
2569(32)
88,2(1.6)
2581(32)
2.0(0.7)
3594(4)
1.5(0.6)
35
0.30
98.0(0.7)
2224(21)
97.8(0.7)
2254(24)
10.2(1.5)
3559(9)
6.2(1.2)
3574(8)
S1
0.00
5.2(1.1)
3879(18)
3.5(1.1)
3882(18)
0.0(0.0)
3960(0)
0.0(0.0)
3960(0)
0.10
8.2(1.4)
3839(21)
7.0(1.3)
3852(21)
0.0(0.0)
3960(0)
0.0(0.0)
3960(0)
0.15
28.0(2.2)
3599(34)
27.8(2.2)
3627(33)
0.0(0.0)
3960(0)
0.2(0.2)
3956(3)
(20, 50)
0.20
64.8(2.4)
3165(41)
62.0(2.4)
3168(41)
1.0(0.5)
3951(5)
0.8(0.4)
3955(4)
0.25
92.2(1.3)
2608(35)
90.2(1.5)
2597(36)
5.0(1.1)
3926(10)
2.8(0.8)
3936(8)
0.30
99.2(0.4)
2238(23)
99.2(0.4)
2250(24)
14.5(1.8)
3854(16)
13.8(1.7)
3868(15)
Table 1: QTE: rejection probabilities (multiplied by 100) and average stopping times under Sce-
narios 1 and 2 when (-) is chosen as the spending function. Standard errors are reported in the parentheses.
33

---

Under review as a conference paper at ICLR 2021
BAT
AVT
method
Random
Adaptive
Random
Adaptive
(m, K)
rej probs
F[stop]
rej probs
F[stop]
rcj probs
E[stop]
rej probs
F[stop]
0.00
5.2(1.1)
1763(8)
6.2(1.2)
1762(8)
0.2(0.2)
1800(0)
51.2(2.5)
1586((1)
0.10
27.5(2.2)
1644(15)
26.0(2.2)
1647(14)
6.8(1.3)
1771(6)
89.0(1.6)
1344(9)
0.15
45.5(2.5)
1511(17)
44.2(2.5)
1527(17)
19.0(2.0)
1718(10)
98.0(0.7)
1250(6)
(200, 5)
0.20
62.5(2.4)
1391(18)
64.2(2.4)
1383(18)
42.8(2.5)
1581(15)
99.5(0.4)
1196(6)
0.25
80.2(2.0)
1263(17)
78.8(200)
1266(17)
72.8(2.2)
1394(17)
99.8(0.2)
1145(5)
0.30
88.2(1.6)
1176(14)
88.8(1.6)
1179(14)
89.2(1.5)
1216(14)
100.0(0.0)
1091(5)
S1
0.00
5.8(1.2)
1933(9)
5.001.1)
1936(9)
0.2(0.2)
1978(1)
S1.3(25)
162I(17)
0.10
27.5(2.2)
1771(18)
27.5(2.2)
1771(18)
8.0(1.4)
1929(9)
89.2(1.5)
1276(13)
0.15
45.5(2.5)
1617(22)
45.8(2.5)
1630(21)
25.2(2.))
1826(15)
97.8(0.7)
1166(7)
(20, 50)
0.20
67.0(2.4)
1446(22)
65,5(2.4)
1459(22)
53.8(2.5)
1617(20)
99.0(0.5)
1105(6)
0.25
83.8(1.8)
1287(19)
82.5(1.9)
1288(19)
79.0(2.0)
1379(19)
99.8(0.2)
1061
0.30
92.0(1.4)
1182(16)
91.5(1.4)
1193(16)
94.0(1.2)
1187(15)
100.0(0.0)
1030(2)
0.00
5,2(1.I)
1763(8)
6,2(1.2)
1762(8)
0.2(0.2)
1800(0)
51.2(2.5)
1586(11)
0.10
18.2(1.9)
1692(12)
16.8(1.9)
1699(12)
3.0(0.9)
1788(3)
82.2(1.9)
1406 10)
0.15
29.0(2.3)
1633(15)
25.2(2.2)
1642(15)
8.5(1.4)
1762(7)
91.8(1.4)
1323(9)
(200, 5)
0.20
40.5(2.5)
1559(17)
42.0(2.5)
1548(17)
17.2(1.9)
1724(10)
97.8(0.))
1257(7)
0.25
50.5(2.5)
1489(18)
49.8(2.5)
1492(18)
33.0(2.4)
1641(14)
99.0(0.5)
1218(6)
0.30
62.5(2.4)
1407(18)
62.5(2.4)
1413(18)
53.5(2.5)
1522(16)
99.5(0.4)
(181(6)
S2
0.00
5.8(1.2)
1933(9)
5.0(1.1)
1936(9)
0.2(0.2)
1978(1)
S1.5(2.5)
162I(17)
0.10
19.02..0)
1839(16)
19.0(2.0)
1837(16)
3.5(0.9)
1961(5)
81.0(2.0)
1360(15)
0.15
28.5(2.3)
1763(19)
28.0(2.2)
1771(18)
11.5(1.6)
1911(10)
90.8(1.4)
1256(12)
(20, 50)
0.20
39.0(2.4)
1680(21)
41.8(2.5)
1685(20)
24.0(2.1)
1830(15)
97.5(0.8)
1171(8)
0.25
50.7(2.5)
1592(22)
52.5(2.5)
1568(22)
44.2(2.5)
1688(19)
99.0(0.5)
I 1124(6)
0.30
65.2(2.4)
1479(22)
63.7(2.4)
1481(22)
63.5(2.4)
1539(20)
99.2(0.4)
1092(5)
Table 2: ATE: rejection probabilities (multiplied by 100) and average stopping times under Sce-
narios and when (-)- is chosen the spending function. Standard parentheses.
reported in the
0.05
o2l)
sal
0.05
0.02
0.0
0.2
0.6
0.8
1.0
Figure 5: Alpha spending functions when 0 = 0.., 1.0.
34


Reviews:
[{"review_id": "xL55g60uoiw", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "=== Contributions ===\n\nThis paper proposes a new framework for A/B testing in the frame of randomized online experiments. This new framework enables testing whether qualitative treatment effects for some specific segment(s) of the tested population can be detected or not. \n\nThe approach relies on a scalable algorithm with:\n- adaptive randomization: in this setting, observations are assumed to be dependent on each other, since treatment can be adjusted by looking at previous rewards;\n- a nonasymptotic upper bound on the type-I error for the online updating,\n- a maximum number of data peeking times that is growing with the number of observations.\n\nMoreover, a bootstrap method is provided in order to determine the stopping boundary. This  circumvents the absence of any tractable analytical form for the limiting distribution of this new test statistic.\n\nFinally, the method is accompanied with experiments on the finite sample performance of the test procedure with simulated and real data from Yahoo!.\n\n=== Strong points ===\n\nThe paper is well written and all results are well introduced with interpretation in words which makes it easy to follow.\nDirect application in practice of the approach can be personalization which is currently a challenge for tech companies. Hence this paper is of great interest for the ML community.\n\n=== Weak points ===\n\nMinor:\nAuthors claim that Figure 3 reports experiment results regarding QTE. However, on this figure, we see only the results for ATE and HTE. Would it be possible to add them? I assume QTE results are better than ATE and HTE ones...\n\n=== Recommendation ===\n\nOverall, I vote for accepting this submission. My acceptance is supported by the strong points stated above. My grade can be further strengthened if the authors can address the points which for me need to be clarified, the biggest one being the correction of Figure 3 to fully support the efficiency of the approach.\n\n=== Additional feedback ===\n\nFor Figure 2, what do S1 and S2 mean? I guess “random” refers to probability 0.5 to be assigned to one or the other treatment and Adaptive to the epsilon-greedy approach.\n\nHow long does it take on average to compute each test for Yahoo data? Do you recommend applying the test for low dimensional data (number of features is 5 for Yahoo)?\n\nMinor details:\n-For readability, I would add in the title of Figure 1 that A is the treatment applied and Y the associated reward, since they have not been yet introduced at the time of the figure’s reference.\n\nFor reproducibility of the results, are the Yahoo data used for the experiment freely available? If yes, would it be possible to add a link to the repository?\n\n=== Questions to help to clarify ===\n\nHow does it relate with Bandits tests that are also online? Would it make sense to add some experiments to show when it is better to use Bandits tests over BAT method for A/B testing?\n\n=== After authors' feedback period ===\n\nI read carefully authors' responses to all reviews. The author's addressed my concerns and I guess the ones of the other reviewers too. One limitation that can be raised now is that the method is better suited for low-dimensional data.\nHence, I keep my accept score.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fJZDfhxUN2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a powerful online sequential test which can efficiently detect qualitative treatment effects (QTE). The test algorithm involves adaptive randomization, sequential monitoring and online updating.  Theoretical guarantee on the Type-I error is presented.\n\nOverall, the paper is well-written, with a clear mathematical definition of the problem, solid theoretical result and experiment results. However, there are some questions that I did not fully understand.\n\n1. In the introduction, the difference of ATE (which is widely used in AB test in tech companies) and QTE is discussed only in words. Is there a more specific case on how QTE can be applied in tech companies where ATE fails? Could you present what are X, Y and A in your specific case, and why this case is specifically important for tech companies? I think this paper will be more interesting to readers in the industry if a detailed case is presented to bridge the introduction and the content.\n\n2.  The author may argue that the experiment on Yahoo! Today Module is an example, but I did not find the point on this experiment. If I understand it correctly, A=0/1 represent two specific article IDs. However, in tech companies, A=0/1 usually represent two algorithms, two sets of hyperparameters or two strategies. The set of article IDs is very huge so it is not very interesting to compare the effect on two article IDs only.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z3lhs-56g-t", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 1, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I am a statistician but I am not an expert in sequential test. My questions and remarks can therefore only be those of a rather naive reader. I understand the motivation behind the paper, but I would clearly have liked to be able to clearly understand the assumptions used. I would also have to work on a  \"real\" algorithm for which one is able to control \"everything\" (in particular, the strategy to choose the . I do not have the impression that this is completely the case here and some aspects need to be clarified.\n\n- I do not understand Eq. (1). The null and the alternative in this case depends on $\\beta_0,\\beta_1$ this is very strange. \n- I do not understand (A2): since $\\{X_k, Y_k^*(0), Y_k^*(1)\\}_{k \\geq 1}$ are independent, it suffices to say that $A_i$ is measurable with respect to $ \\mathcal{F}_i \\vee \\sigma(X_i)$ \n- Theorem~1: the key is to check Eq. (5) which means that you have a strategy to choose the arms with a non trivial regret bound ?  What are the typical values of $\\alpha_0$ ? How this is related to contextual bandits (since there is notion regret), to best arm identification problems in linear bandits ? \n- The meaning of Eqs. (6) and (7) are very difficult to grasp \n- How your results compare to multi-armed bandit testing with online FDR control ? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "01t8mv2r25n", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies online test for qualitative treatment tests. The authors propose a scalable online algorithm for Type 1 error control. I find the paper under-developed that the writing has to be substantially improved, and the presentation, especially in Section 3.2, is not friendly.\n\n1. The authors claim to have an \"Online\" algorithm. However, I don't see that the algorithm addresses any real online challenge. The challenge of online testing is that we are doing testing at each iteration, and it is difficult to adjust all p-values. The authors didn't address this issue at all, which is a fatal flaw.\n\n2. The linear space approximation is very artificial to me. Can the authors give some real motivating applications?\n\n3. I highly suggest the authors to move the theorems 3 and 4 to Section 3.2, and move the derivation (which are standard) to the appendix.\n\nOverall, I don't see much novelty, and the authors are overclaming the contribution. This is a clear rejection.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new framework for online hypothesis testing aimed at detecting causal effects (of treatments on outcomes) within subgroups in online settings where treatments are randomized.  Such settings occur in online advertising where different versions of the same website may be presented to a set of otherwise exchangeable users via A/B testing.

Under the standard causal assumptions of SUTVA, and sequential ignorability, in addition to a set of regularity conditions, the authors derive a result (Theorem 1) leading to an online test (Theorem 2).  Since the resulting test's limiting distribution does not have an exact analytic form, the authors instead propose a bootstrap approach to determine a set of parameters to properly control the error rate.

The author validate their approach by a simulation study, as well as via a user click log data from Yahoo!

The reviewer opinion was somewhat split on this paper, in particular some reviewers raised concern about some (conceptually significant) typos, interpretability of assumptions, and the need for parametric assumptions (the dichotomy between linear models and neural networks is surely a false one -- the semi-parametric literature obtains nice parametric style results, although perhaps not always for tests, without assuming parametric likelihoods all the time).

Decision: Reject