Online Testing of Subgroup Treatment Effects Based on Value Difference
Authors: Miao Yu
Wenbin Lu
Rui Song
Venue:  (2021)
Keywords: online A/B testing
subgroup treatment effects testing
continuous monitoring
supervised representation learning
classification

Abstract: Online A/B testing plays a critical role in high-tech industry to guide product development and accelerate innovation. It performs a null hypothesis statistical test to determine which variant is better. However, a typical A/B test presents two problems: (i) a fixed-horizon framework inflates the false positive errors under continuous monitoring; (ii) the homogeneous effects assumption fails to identify a subgroup with a beneficial treatment effect. In this paper, we propose a sequential test for subgroup treatment effects based on value difference, named SUBTLE, to address these two problems simultaneously. The SUBTLE allows the experimenters to "peek" the results during the experiment without harming the statistical guarantees. It assumes heterogeneous treatment effects and aims to test if some subgroup of the population will benefit from the investigative treatment. If the testing result indicates the existence of such subgroup, a subgroup will be identified using a readily available estimated optimal treatment rule. We examine the empirical performance of our proposed test on both simulations and a real data set. The results show that the SUBTLE has high detection power with controlled type I error at any time, is more robust to noise covariates, and can achieve early stopping compared with the corresponding fixed-horizon test.

Under review as a conference paper at ICLR 2021
ONLINE TESTING OF SUBGROUP TREATMENT EF- FECTS BASED ON VALUE DIFFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
Online A/B testing plays critical role in high-tech industry to guide product de- velopment and accelerate innovation. It performs null hypothesis statistical test to determine which variant is better. However, typical A/B test presents two problems: (i) fixed-horizon framework inflates the false positive errors under continuous monitoring: (ii) the homogeneous effects assumption fails to identify a subgroup with a beneficial treatment effect. In this paper, we propose a sequen- tial test for subgroup treatment effects based value difference, named SUBTLE, to address these two problems simultaneously. The SUBTLE allows the experi- menters to "peek" the results during the experiment without harming the statistical guarantees. It assumes heterogeneous treatment effects and aims to test if some subgroup of the population will benefit from the investigative treatment. If the testing result indicates the existence of such subgroup, subgroup will be iden- tified using a readily available estimated optimal treatment rule. We examine the empirical performance of our proposed test on both simulations and real data set. The results show that the SUBTLE has high detection power with controlled type I error at any time, is more robust to noise covariates, and can achieve early stopping compared with the corresponding fixed-horizon test.
INTRODUCTION
Online A/B testing, kind of randomized control experiments, is widely used in high-tech indus- try to assess the value of ideas in scientific manner (Kohavi et al.) 2009). It randomly exposes users to one of the two variants: control (A), the currently-used version, or treatment (B), a new version being evaluated, and collects the metric of interest, such as conversion rate, revenue, etc. Then, a null hypothesis statistical test is performed to evaluate whether there is a statistically significant difference between the two variants on the metric of interest. This scientific design helps to control for the external variations and thus establish the causality between the variants and the outcome. However, the current A/B testing has its limitations in terms of framework and model assumptions.
First of all, most A/B tests employ a fixed-horizon framework. whose validity requires that the sample size should be fixed and determined before the experiment starts. However, experimenters, driven by a fast-paced product evolution in practice, often "peek" the experiment and hope to find the significance as quickly as possible to avoid large (i) time cost: an A/B test may take prohibitively long time to collect the determined size of samples; and (ii) opportunity cost: the users who have been assigned to a suboptimal variant will be stuck in a bad experience for a long time (Ju et al. 2019) The behaviors of continuously monitoring and concluding the experiment prematurely will be favorably biased towards getting sigmificant results and lead to very high false positive proba- bilities, well in excess of the nominal significance level (Goodson) 2014: Simmons et al.) 2011). Another limitation of A/B tests is that they assume homogeneous treatment effects among the popu- lation and mainly focus testing the average treatment effect. However, is common that treatment effects vary across sub-populateo tobppouulations. Testing the subgroup treatment effects will help decision mak- distinguish the cobp-ooulttion that may benefit from particular treatment from those who may not, and thereby guide companies' marketing strategies in promoting new products.
The first problem can be addressed by applying the sequential testing framework. Sequential testing, contrast to the classic fixed-horizer test, is a statistical testing procedure that continuously checks for significance at every new sample and stops the test as as significant result is detected,

---

Under review as a conference paper at ICLR 2021
while controlling the type I error at any time. It generally gives significant decrease in the required sample size compared to the and thus is able to end an experiment much earlier. This field first introduced by Wald (145), who proposed sequenfial probability ratio test (SPRT) for simple hypotheses using likelihood ratio as the test statistics, and then was extended composite hypotheses by many following literature [Schwarz, 1962; Armitage et al., 1969; Cox 1963; Robbins 1970 Lai 1988). A thorough review is given in Lai 2.01). However, the advantage of sequential testing in online A/B testing has been recognized until recently Johari et al. (0155) brought the mSPRT, a variant of SPRT to A/B tests.
test with the same type I error and type II error control,
The second problem shows a demand for a test on subgroup treatment effects. Although sequential testing is rapidly developing in online A/B test, few work focuses on subgroup treatment effect testing. Yu al. (2020) proposed a sequential score test (SST) based on score statisties under a generalized linear model, which aims to test if there is difference between treatment and control groups among any subjects. However, this test is based on restrictive parametric assumption on treatment-covariatte interaction and can't be used to test the subgroup treatment effects.
In this paper, we consider a flexible model, and propose a sequential test for SUBgroup Treatment effects based on vaLuE difference (SUBTLE), which aims to test if some group of the population would benefit from the investigative treatment. Our method does not require to specify any para- metric form of covariate- covariate-specific treatment effects. If the null hypothesis is rejected, a beneficial subgroup can be easily obtained based on the estimated optimal treatment rule.
The remainder of this paper is structured as follows. In Section 2, review the idea of the mSPRT and SST, and discuss how they are related to our test. Then in Section 3, we introduce our proposed method SUBTLE and provide the theoretical guarantee for its validity. We conduct simulations in Section 4 and real data experiments in Section 5 to demonstrate the validity, detection power, robustness and efficiency of our proposed test. Finally, in Section 6, we conclude the paper and present future directions.
RELATED WORK
2.1 MIXTURE SEQUENTIAL PROBABILITY RATIO TEST
The mixture sequential probability ratio test (mSPRT) (Robbins dent and identically distributed (i.i.d.) random variables Y1, Y2, have a probability density func- tion fz) induced by parameter 0, and aims to test
1970) supposes that the indepen-
Ho 0 = Oo U.8. H1 0 + 0u-
(1)
Its test statistics AA at sample size n is mixture of likelihood ratios below:
/ II
[o((.) (Y,)
A
ग (0))d,
i=1
with a mixture density TT-) over the parameter space O The mSPRT stops the sampling at the stage
N inf 2 1 A : 2 1/a}
(3)
and rejects the null hypothesis Ho in favor of Hi If no such time exists, it continues the sampling indefinitely and accept the Hy. Since the likelihood ratio under H, is nonnegative martingale with initial value equal to 1. and so is the mixture of such likelihood ratios AZ the type I error of mSPRT can be proved to be always controlled at a by an application of Markov's inequality and optional stopping theorem: PH. (Ag 2 a a=1)== < lAgl En, [Aā]
Besides, mSPRT is a test of power one (Robbins & Siegmund 1974), which means that any small deviation from Og can be detected as long as waiting long enough. It is also shown that mSPRT is almost optimal for data from an exponential family of distributions, with respect to the expected stopping time (Pollak 1978).
a
The mSPRT was brought to A/B test by Johari et al. (2015) 2017). who assume that the observa- tions in control (A = 0) and treatment (A = 1) groups arrive in pairs (X,(") x,()), (x,"",,((") They restricted their data model the two most common cases in practice: normal distribution
= 1,2,
2

---

Under review as a conference paper at ICLR 2021
and Bernoulli distribution, with μл and jæ denoting the mean for control and treatment group, respectively. They test the hypothesis as below
Ho B PB pA=0 v.8. H1 01:07 0,
(4)
by directly applying mSPRT to the distribution of the differences Z, y1 - y, (normal), or the joint distribution of data pairs (x;"); .r()) (Bermoulli), i = 1.2..... After making some approximations the likelihood ratio and choosing normal mixture density x (0) ~ (O, 7²), the
test statistic A is able to have a closed form for both normal and Bernoulli observations.
However, the mSPRT does not work well testing heterogeneous treatment effects due to the com- plexity of likelihood induced by individual covariates. Specifically, a conjugate prior π(-) for the likelihood ratio may not exist anymore that the computation for the test statistic is challenging. The unknown baseline covariates effect also increases the difficulty in constructing and approximat- ing the likelihood ratios (Yu al. 2020).
2.2
SEQUENTIAL SCORE TEST
The sequential score test (SST) (Yu et al. 2020) assumes generalized linear model with link function g(-) for the outcome
(B ( x (0 X)A,
(5)
where A and X denote the binary treatment indicator and user covariates vector, and tests the multi- dimensional treatment-covariatss interaction effect:
Ho 0= us. 01:000
while accounting for the linear bascline covariates effect 4² X. For the test statistics A,, instead of using a mixture likelihood ratios as mSPRT, SST employed a mixture asymptotic probability ratios of score statistics. Since the probability ratio has the same martingale structure the likelihood ratio, the type I error can still be controlled with the same decision rule as mSPRT (3). The asymptotic normality of the score statistics also guarantees a closed form of A with multivariate normal mixture density T--). However, the considered parametric model (5) can only be used to test there are linear coauiate-trrettert interaction effects, and may fail detect the existence of subgroup with enhanced treatment effects. In addition, the subgroup estimated based on the index x"X, may be biased if the assumed linear model (5) is misspecified. Therefore in this paper, we propose subgroup treatment effect test, which is able to test the existence of beneficial subgroup and does not require to specify the form of treatment effects.
SUBGROUP TREATMENT EFFECTS TEST BASED ON VALUE DIFFERENCE
3.1
PROBLEM SETUP
Suppose we have i.i.d. data O, (Y, A, i= 1,2, where Y,, A, X, respectively denote the observed outcome, binary treatment indicator, and p-dimensional user covariates vector. Here, consider flexible generalized linear model:
g g(E x.)) ((X.) + 0(X,)A,
where baseline covariates effect sa(-) and cerattent-covariin interaction effect 0(-) are completely unspecified functions, and g(-) is prespecified link function. For example, we use the identity link g(n)= = yu for normal response and the logit link 5(4) = log r- for binary data.
Assuming Y is coded such that larger values indicate better outcome, we consider the following test of subgroup treatment effects:
Ho Vx E X, 0(x) S O us. H1 3%0 X' such that 0(x) for all x E Xo.
where Xo is the beneficial subgroup with P(X E Xx) > 0. Note that the above subgroup test is very different from the covariate-treatmet interaction test considered in (6) and is much more chal- lenging due several aspects. First, both y(-)) and 0(-) nonparametric and need to be estimated.
3

---

Under review as a conference paper at ICLR 2021
Second, the considered hypotheses are moment inequalities which nonstandard. Third, it allows the nonregular setting, i.e. P(@(X) = 0} > O, which makes associated inference difficult. Here, we propose test based value difference between the optimal treatment rule and a fixed treatment rule.
Let V(d) = (o))x) (d)(()))) denote value function for a treatment decision rule, where (d(())) is the potential outcome if treatment were allocated according to the fixed treatment deci- sion rule d(X), which maps the information in to treatment {0. 1). Consider the value difference A -V(d")--1 (0) between the optimal treatment rule d' (0(X) 0} and the treatment rule that assigns control to everyone = O, where 1 {(-} is an indicator function. If the null hypothesis is true, no one would benefit from the treatment and the optimal treatment rule assigns everyone to control, and therefore the value difference is zero. However, if the alternative hypothesis is true, some people would have higher outcomes being assigned treatment and thus the value difference is positive. In this way the testing hypotheses (8) can be equivalently transformed into the following pair:
Ho A 0 U.. H1:44 A 0.
We make the following standard causal inference assumptions: (i) consistency, which states that the observed outcome is equal to the potential outcome under the actual treatment received, i.e. 0): (ii) unmeasured confounders, i.e. Y*(a) TL A[X, which means the potential outcome is independent of treatment given covariates; (iii) positivity, i.e.
Y Y (1) 1) + Y (O)
P(A = x x) > for = 0, 1 and all x X' such that PPX x) >> 0. Under these assumptions, it can be shown that
V(d) = Ex
3.2 ALGORITHM AND IMPLEMENTATION
We take the augmented inverse probability weighted (AIPW) estimator (Robins et al., 1994 Zhang ct al. 2012) for the value function given treatment rule d:
1
Y
1fA, = d}
(14 d} PA (X.) -1) E|Y,A d, d.x.I}
VAIW(() (d)
TI
PA. (X,)
where PA (X) = A p(X) (1- A) (1 p(X)) and p(X) = P(A 1|X) is the propensity Vdd.. Moreover, the most important property of AIPW estimator is the double robustness, that is, the estimator remains consistent if either the estimator of E A d, X] or the estimator of the propensity score p(X) is consistent, which gives much flexibility. Then the value difference A is unbiased estimated by
score. This estimator is unbiased, i.e., E(y,A.))|VAn (AIP(()) (d)
1 (A: = 1(0(X.) > 0)}
1 fA, = 1()(X,) > 0)} -1)
D(OGHH,,p))
# +Y,
PA (X.)
PA,
(A = 0) 1 p(X))
1(A, = 0)
* *9-1 +
(
0))
Y,
* *g- (a(x.)) 1 1- p(X.) -1
(10)
where g -1) is the inverse of the link function. That is,
(1O =
Since uu(-). (() and p(-) are usually unknown, we let data come in batches and estimate them based on previous batches of data. Algorithm [ shows our complete testing procedures.
we estimate ju(-) and 0(-) by respectively building a random for- est on control observations and treatment observations in previous batches. The propensity score p(-) is estimated by computing the proportion of treatment observations (A = 1) in previ-
In step (ii) of Algorithm 1
ous batches. In step (iv) we estimate og with ōz - where of is the sample variance of D(O;; fمp- 0,- 1)-1), VO; E CR-1- Note that Rs 144 is multiplier of an asymptotic unbi- ased estimator for A, which is defined as below:
A Σ o7 (C,CC.C.-1)
(1I)
Σ 07
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Subgroup treatment effects sequential test based on value difference
Initialize k: = O, A O. Choose significance level ar < 1, a batch size m, an initial batch size 1, and failure time M.
Sample I observations formulate initial batch Co.
while True do
(i) k=k+l;
(ii) Let Ck-1 Cz Estimate ya-), (() and p(-) based on data in CR-1 to get fi=1
8x-1 and pk-1:
(iii) Sample another observations to formulate batch Cg. For each O Ck. calculate
D(O 11 11... Let
Cx(Cs;
Σ
(13)
O:EC2
(iv) Estimate the conditional standard deviation ox = sd data in Ck-1 and denote it as ok:
based on
(v) Calculate
1
(14)
Vk j=1
and
1 (E:-, 8, 1),))))) A -
Rk T TAjdA,
(15)
(0, 1) (Rx)
where (-) denotes the probability density function of normal distribution with mean μ and variance o2:
if A > 1/a or & x m + M then
break;
end end
Ag 1/a then
Reject Hg. Estimate ((-) using all the data up to now and identify a subgroup 1(0(X) > 0):
else
Accept Ho:
end
In section 3.3 we will show that R₂ has asymptotic normal distribution with same variance but different means under null and local alternatives, so that our test statistics AE (I5) is a mixture asymptotic probability ratios of RG. Since the value difference always non-negative,
choose a truncated normal T(A) : exp 2, 1(A > 0) as the mixture density, where 7
2
estimated based on historical data. The simulation result in Appendix A.2.1 shows considerable robustness in choosing 72, Our test statistic now has closed form:
k k (T E 12
1/2
(T E5= R2)
Ag 2
exp
[1 F(O),, (12)
2 [t 1 +
where F(-) is the cumulative distribution function of normal distribution with mean Vh. VA 07 RR and variance 7 0, F44
[E)- 244
the null hypothesis rejected, we can employ random forests to estimate 0(-) based on all the data up to the time that the experiment ends. Then the optimal treatment rule 0(x) naturally gives the beneficial subgroup Xn {x 0(x) 0).
5

---

Under review as a conference paper at ICLR 2021
3.3 VALIDITY
In this section, we will show that our proposed test SUBTLE is able to control type I eπror at any time, that is, Ir,, (Ag 1/a) < a for any E N. As we discussed Section 2.1, if we can show that the ratio term in Ag (15) has martingale structure under Ho. it follows easily that the type error is always controlled at a. Theorem 3.1 gives the respective asymptotic distributions of R2 under null and local alternative, which demonstrates that the test statistics AI is mixture asymptotic probability ratios weighted by sT().. Proposition shows that this asymptotic probability ratio martingale when the sample size is large enough. Combining these two results with the demonstration in Section 2.1, we can conclude that the type error of SUBTLE is always controlled a.
We assume the following conditions hold:
(C1) & diverges to infinity as sample size n diverges to infinity.
(C2) Lindeburg- like condition:
(D.(C:C,-1))+ 2 .1 (1DDI(C;)))))) > eVTi 2--1 = =p((1
Σ
ōj
/=1
for all >>
(C3) E E 2 1.
(C4)
& ビΣソ /5¹ (EDD,(CGCC.--NCCC-----1G....... jopt -, =
0p(k-
sopt (C5) & Eー=1ō 14
= o
Theorem 3.1 For D defined in
11
under conditions (CI)CC5)
1
Σ
4 N(. as + 00;
(16)
Vi
where $ represents convergence in distribution. In particular, as k co, Rs Ho
4 N(O. under
null hypothesis A = 0. while Rs 1
A d, N(0, under local alternative A H1
V where 8 > 0 is fixed.
(tte (x:t-1 27 )a)) (Rx)
Proposition! 1 Let A
and Fx denote a filtration that contains all the
Vio. (a))
historical information in the first (k + 1) batches Cx. Then under null hypothesis Ho : A = 0.
[[A++1]Fi]] is approximately equal to d (1)(
The proofs of above results are given in the Appendix A.I.
SIMULATED EXPERIMENTS
In this section, we evaluate the test SUBTLE on three metrics: type error, power and sample size. We first compare SUBTLE with SST in terms of type I error and power under five models in Section 4.1. Then Section 4.2, we present the impact of noise covariates on their powers. Finally in Section 4.3, compare the stopping time of SUBTLE
the required sample size of fixed- horizon value difference test. The significance level a = 0.05, initial batch size = 300, failure time M 2300 and variance of mixture distribution ?2 1 are fixed for all simulation settings.

---

Under review as a conference paper at ICLR 2021
4.1 TYPE I ERROR & POWER
We consider five data generation models in the form of ( with logistic link g(-). Data are generated in batches with batch size m 20 and are randomly assigned two groups with fixed propensity score p(X) = 0.5. Each experiment is repeated 1000 times to estimate the type error and power. For the first four models, we choose
Five covariates: X1 Hid Ber(0.5), X2 sid Unif(-1,1], X3, X4, X5 äd N(O,1)
Two baseline effect: /1 -1 X3 (2( -13 + X1 + 0.5X2 X3
Two treatment-covariate interaction effect: (X) = c 1(X, 2X, 0), (2
c. 1X2 > 0 or Xs < -0.5).
Table 1: The first four models
Model
Input covariates
[x()
((X)
I
X1,X,
M4 XX)
0, (X)
II
X1, X2, X3, X4, X6
112 X
(2(X)
III
X1, X2, X3, X4, X3
141 X
02 (X)
IV
X1, X2, X3, X4, X5
442 X
01 (X)
Table displays which covariates, (xX) and ((X) are employed in each model. For model V, we consider the following high-dimensional setting:
X, rid N(0.2r 0.6, 1), r == 3,,45,
X14 add Unif[[005, 1.5]
X, vid N(0.2r 1.6, r -= 6, 9,
X15 idd Unif[[1.5,005] 0.5]
X, udd Unif( + 5, 0.5r - 5), r= 11, 12, 13
X, idd Ber(0.2r - 3.1), r 16, 17, 18, 19, 20 8(X) = c. 1[(X1 --l:i>~001111 -0.1)& & (X20 = 1)};
(X) = 0.8 + X + 0.5X -
where varies among {-1.0. 0,6,, 0.8, } indicating the intensity of the value difference. When c= 11 and 0, the null hypothesis is true and the type error is estimated, while when c 0.6, 0.8, 1,
the alternative is true and the power is estimated.
Table shows that the SUBTLE is able to control type I error and achieve competing detection power, especially under high-dimensional setting (Model V); however, SST couldn't control type I error especially when c = -1. This can be explained by two things: (i) the linearity of model (5) is violated; (ii) SST is testing if there is difference between treatment and control groups among any subjects, instead of the existence of a beneficial subgroup. Specifically, SST is testing the least false parameter 0* which the MILE of 0 under model misspecificatioo converges, zero not. We also perform experiments with batch size m = 40, and the results (shown in Appendix 1.2.1) do have much difference.
Table 2: Estimated type I error power for SUBTLE and SST with batch size 20
Model
III
IV
V
SUBTLE
SST
SUBTLE
SST
SUBTLE
SST
SUBTLE
SST
SUBTLE
SST
-1 0.009
0.695
0.002
0.589
0.003
0.224
0.004
0.411
0.002
0.008
0.015
0.134
0.010
0.023
0.006
0.095
0.010
0.023
0.006
0.038
0.6
0.323
0.564
0.491
0.513
0.269
0.389
0.424
0.425
0.559
0.170
0.8
0.623
0.845
0.878
0.900
0.719
0.723
0.822
0.824
0.925
0.390
0.911
0.974
0.988
0.996
0.952
0.943
0.985
0.982
0.997
0.742
4.2
NOISE COVARIATES
is common in practice that a large number of covariates are incorporated in the experiment whereas the actual outcome only depends few of them. Some covariates do not have any effect
7

---

Under review as a conference paper at ICLR 2021
the response, like X4 in Model II, III, IV, and we call them noise covariates. In the following simulation, we explore the impact of noise covariates to the detection power. We choose Model I with 0.8 the base model, and at each time add three noise covariates which are respectively from normal (0,, 1), uniform Uni f|- 1 1]. and Bernoulli (er(0.5) distributions. The batch size set m 40 for computation efficiency. Figure shows that SST has continuously decreasing powers as the number of noise covariates increases, while the power of SUBTLE is more robust to the noise covariates
29
20
20:611 Lt
201T
100
27
30
2.8
8.6
0.4
12
Shopping 1ime
Number notte coxtrittes
Figure 2: Histogram of stopping time for
Figure/ Estimated power v.s. the number of noise covariates
1000 replicates of experiments under Model V with c=1
4.3 STOPPING TIME
key feature for sequential test is that it has an expected smaller sample size than fixed-horizon test. For comparison, we consider a fixed-horizon version of SUBTLE, which leverages the Theorem 3.1 and rejects the null hypothesis Ho A = when R2 > Za for some predetermined k. where Za de- notes the (1 a.) quantile of standard normal distribution. We assume o = -imm F ビ== 071
then the required number of batches h can be calculated as k o² + yoma)? and thus the quired sample size is n = * m + 1. The true value difference A can directly estimated from data generated under true model and two treatment rules, while o² estimated by the sample vari- ance of Âg (11) times k' for some fixed large k. Here, we choose Model V with c and batch size m = 20. The stopping sample size of our sequential SUBTLE over 1000 replicates are shown in Figure 2 and the dashed vertical line indicates the required sample size for the fixed-horizon SUBTLE with the same power 0.997 (seen from Table 2 under the same setting. We can find that most of the time our sequential SUBTLE arrives the decision early than the fixed-horizon version, but occasionally it can take longer. The distribution of the stopping time for sequential SUBTLE is right-skewed, which line with the findings in Johari et al. (2015) and Ju et (0019).
A²
5 REAL DATA EXPERIMENTS
We use Yahoo real data to examine the performance of our SUBTLE, which contains user click events on articles over 10 days. Each event has timestamps. unique article id (variants), binary click indicator (response), and four independent user features (covariates). We choose two articles (id=109520 and 109510) with the highest click through rates as control and treatment, respectively. We set the significance level a 0.05, initial batch size and batch size I = m 200, and the failure time M 50000.
To demonstrate the false positive control of our method, we conduct A/A test and permutation test. For A/A test, we only use data on article 109510 and randomly generate fake treatment indicator. Our method accepts the null hypothesis. For permutation test, we use combined data from article 109510 and 109520, and permute their response 1000 times while leaving treatment indicator and covariates unchanged. The estimated false positive rate is below the significance level.
Then we test if there is any subgroup of users who would have higher click rate on article 109510. In this experiment, SUBTLE rejects the null hypothesis with sample size 12400. We identify the beneficial subgroup (() 0} by estimating (XX) with random forest the first 12400
8

---

Under review as a conference paper at ICLR 2021
observations. To get a structured optimal treatment rule, then build a classification tree the same 12400 samples with random forest estimator ((( 0} true labels. The resulting decision tree (shown in Appendix A.2.2) suggests that the users in the subgroup defined by (X3 < 0.7094 (X3 2 0.7094, X Z 0.0318 and X4 < 0.0003)) benefit from treatment.
We then use the 50000 samples after the first 12400 samples as test data set, and then compute the difference of click through rates between article 109510 and 109520 on the test data (overall treatment effect), and the same difference in the subgroup of the test data (subgroup treatment effect). We found that the subgroup treatment effect 0.009 is larger than the overall treatment effect 0.006, which shows that the identified subgroup has enhanced treatment effects than the overall population.
We further compute the inverse probability weighted (IPW) estimator + E i=1 I(A, ([A,=((X)))) ))X. using PA, (X.)
the test data for the values of two treatment rules: di (X) = 0 that assigns everyone to control and the optimal treatment rule d2 (X) = 1(((X)= > 0} estimated by random forest. Their IPW estimates are respectively 0.043 and 0.049, which suggests that the estimated optimal treatment rule is better than the fixed rule that assigns all users to the control group. This implies there exists subgroup of
the population that does benefit from the article 109510.
6 CONCLUSION
In this paper, we propose SUBTLE, which is able to sequentially test if some subgroup of the population will benefit from the investigative treatment. If the null hypothesis rejected, beneficial subgroup can be easily identified based on the estimated optimal treatment rule. The validity of the test has been proved by both theoretical and simulation results. The experiments also show that SUBTLE has high detection power especially under high-dimensional setting, is robust to noise covariates, and allows quick inference most of time compared with fixed-horizon test.
Same as mSPRT and SST, the rejection condition of SUBTLE may never be reached under some cases, especially when the true effect size negligible. Thus, a failure time is needed to terminate the test externally and accept the null hypothesis if we ever reach it. How to choose a failure time to trade off between waiting time and power need to be studied the future. Another future direction is the application of our test under adaptive allocation, where users will have higher probabilities of being assigned to a beneficial variant based on previous observations. However, the validity may not be guaranteed anymore under adaptive allocation and more theoretical investigations are needed.
REFERENCES
Peter Armitage, CK McPherson, and BC Rowe. Repeated significance tests on accumulating data. Journal of the Royal Statistical Society: Series A (General), 132(():235-244, 1969.
David Roxbee Cox. Large sample sequential tests for composite hypotheses. Sankhyā: The Indian Journal of Statistics, Series A, pp. 5-12, 1963.
Martin Goodson. Most winning a/b test results are illusory. Whitepaper, Qubit, Jan, 2014.
Ramesh Johari, Leo Pekelis, and David J Walsh. Always valid inference: Bringing sequential anal- ysis to a/b testing. arXiv preprint arXiv: 152.0492, 2015.
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.
Ron Kohavi, Roger Longbotham, Dan Sommerfield, and Randal M Henne. Controlled experiments on the web: survey and practical guide. Data mining and knowledge discovery, 18(1):140-18) 2009.

---

Under review as a conference paper at ICLR 2021
Tze Leung Lai. Nearly optimal sequential tests of composite hypotheses. The Annals of Statisties, pp. 356-886, 1988.
Tze Leung Lai. Sequential analysis: some classical problems and new challenges. Statistica Sinica, pp. 303-351, 2001.
Moshe Pollak. Optimality and almost optimality of mixture stopping rules. The Annals of Statistics, pp. 910-916, 1978.
H Robbins and D Siegmund. The expected sample size of some tests of power one. The Annals of Statistics, pp. 415 436, 1974.
Herbert Robbins. Statistical methods related to the law of the iterated logarithm. The Annals of Mathematical Statistics, 41(5): 1970.
James M Robins, Andrea Rotnitzky, and Lue Ping Zhao. Estimation of regression coefficients when some regressors are not always observed. Journal of the American statistical Association, 89 (427):8468866, 1994.
Gideon Schwarz. Asymptotic shapes of bayes sequential testing regions. The Annals of mathemati- cal statistics, pp. 224-236, 1962.
Joseph P Simmons, Leif D Nelson, and Uri Simonsohn. solse-positive psychology: Undisclosed flexibility in data collection and analysis allows presenting anything as significant. Psychological science, 22(1 13:119)33993666 2011.
Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 1136523); 2018.
Abraham Wald. Sequential tests of statistical hypotheses. The annals of mathematical statistics, 16 (2):117-186, 1945.
Miao Yu, Wenbin Lu, and Rui Song. A new framework for online testing of heterogeneous treatment effect. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence. AAAI, 2020.
Baqun Zhang, Anastasios A Tsiatis, Eric B Laber, and Marie Davidian. robust method for esti- mating optimal treatment regimes. Biometrics, 101001000- 2012.
A APPENDIX
A.1 PROOFS
A.1.1 PROOF OF THEOREM 3.1
Among the conditions for Theorem 3.1 (C1) holds by nature. We suppose that (C2) and (C3) hold. (C4) and (C5) depends on the convergence rate of estimators of μ,, 0,p. Wager Athey (2018) showed that under certain constraints on the subsampling rate, random forest predictions converge at the rate n 1-1/2 where is chosen to satisfy some conditions. We assume that under this rate, (C4) and (C5) also hold.
Let Fy. 0 S S k. denote filtration generated by observations in first (j+1) batches C3 U/= H.HH., 0, p) denote an AIPW estimator for A with only optimal decision rule estimated
and (C,C; d 1, by previous batches:
A; = (X.) > 0)}
1 [1 1(0)-1(X))
-xx > 0) -1)
jopt d 14 0,P) m
1
Σ O,EC,
YY;
(X,)
PA:
1 (M(X,) + +((X.)
> =0)}}}
1(Ai = 0) *Y; 1(A, = 0)
(1-p(X.) (1-p(X.) -1) *g *g- *5=1(((X)))
(17)
10

---

Under review as a conference paper at ICLR 2021
Then
Σ 0j
(Ac-
-2)
(18)
1 h
-1)
(19)
k
j=l
1 k
o
2opt
A)
k j=1
(20)
1
Σ
popt [, + (1-111122
(21)
h:
J=1
1
Σ
(D, - -[D, +pp()
(22)
1:
Above 21 follows by condition (C5) and 22
follows by condition (C4). For = 1,2,",,, let Dy(C;; TID,
MR.j Vk
(23)
8j
It is obvious that for each h, Ma.j 1 S j < k, is martingale with respect to the filtration Fj. In particular, for all j 2 1, [[ -1 0 and Σ 1 Σ 2 1 as
k + do by (C3). The conditional Lindeberg condition holds in (C2), so the martingale central limit theory for triangular arrays gives
MR.s 4 1).
(24)
Plugging it back into
22
we can get
1
(Ax - 2) $ 1).
(25)
V
A.1.2 PROOF OF PROPOSITION
We first simplify the formula of Å to:
$ 1 (E)=, 07 17)) (Rs)
(26)
1(00 (R()))
exp
A Rs
1)2
A
(27)
2k
j=1
j=1
exp
1
Σ ,
A
Σ
(oj
D3)
0j 1/2
(28)
2h
j=1
1=1
where we denote D,(C;; with D, for simplicity. Let
カー= 07 D
(29)
Σ 0j
11

---

Under review as a conference paper at ICLR 2021
and remember that Theorem 3.1 gives
Eog (As -2) 4 NO.. 1),
(30)
where og is estimated from the first j batches ビ 1, ... Since the true value difference A is not very large in practice, we assume local alternative A Op 1/2)) here as in Theorem 3.1
Then,
ER 16+11 FF]
(31)
R+1
I+1
R+1
Es.
exp
A
1oj D2)
22
FR
(32)
k
2(k + 1)
==1
==1
j=1
k+1 6
k+1
k+1
Delta Method Rd
exp
EH
A
Σ
10 (
07 1)2 A
Fr
++1
2(k + 1)
2
j=1
5m1
(33)
k+1
k EOT +
k+1
1
exp
A
o.
EnO ID FR
1-1
A2
+
2(k + 1)
j
(34)
1 k+1
k
k+1
1
exp
0
A
(ō) DD)
)2 A
(35)
+
2(k + 1)
j=1
/=1
j=1
k+1
exp
1
Σ
A
Σ
(o
k+1 Σ
0
1
Σ f
A
>
D₂)
K
K
j=1
1
jj
-
1/2 2
1
1
0
1
A
(36)
2k
2 11)
2k
j=1
j=1
k+1
k+1
1
1
1
A exp
k+ Σ
1
01
A
1
2(k + 1)
1-1
2k
0j
1112
12
|=1
j=1
J=1
j=1
(37)
k+1
k
k+1
k
29
AE exp
h: ++ j=1
1
Σ
Σ
A
Σ
j
- 1 A -
2(k+1)
1
2h
à 1
A
j=1
j=1
j=1
(38)
1 k+1
1
d exp
k XA
k
To
f=1
j=1
Op(k-1)
Or (xt1222)by by
30
k+1
1
122
03 1)2
xA=
(39)
2(k: + 1)
2h
2₂(1)
du exp(op(1))
(40)
12

---

Under review as a conference paper at ICLR 2021
Table 3: Estimated type error power for SUBTLE and SST with batch size 40
Model
III
IV
V
SUBTLE
SST
SUBTLE
SST
SUBTLE
SST
SUBTLE
SST
SUBTLE
SST
0.003
0.662
0.000
0.588
0.000
0.006
0.012
0.126
0.002
0.023
0.003
0.077
0.002
0.023
0.006
0.034
0.297
0.552
0.465
0.549
0.326
0.397
0,414
0,451
0.216
0.633
0.837
0.868
0.896
0.680
0,703
0.373
0.901
0.969
0.993
0.995
0.947
0.933
0.985
0.978
0.999
0.715
Table 4: Estimated type error and power for SUBTLE and SST with varying mixture density variance
0.0001
0.001
0.01
10
Type error
0.003
0.024
0.021
0.016
0.005
0.002
Power
0.887
0.976
0.956
0.932
0.892
0.825
A.2 ADDITIONAL RESULTS
A.2.1 HYPERPARAMETERS
There are three hyperparameters in our algorithm: batch size m, variance of mixture density 7², and failure time M. We did tune these hyperparameters in our experiments, but used the same value for SST and SUBTLE, In the following, we will expound the effects of these hyperparameters on the performance of our tests and provide additional simulation results.
Apart from batch size 20 in Section 4.1, we also conduct experiments with batch size 40 under the same setting. The results are shown Table It seems that there is considerable robustness in choosing batch size.
In theory the choice of mixture density variance 72 will not have any effect on the type error control. Johari et al. (2055) proved that an optimal 72 in terms of stopping time is the prior variance times a correction for truncating. It is the reason that we suggest using historical data estimate the variance of value difference A. Besides, we conduct simulations with varying 72. The data is generated from Model TT while when I we estimate the power. The results in Table show that the type error is always controlled below significance level 0.05 and the power has considerable robustness to the choice of ?
or e 1. When c we estimate the type I error,
As we mentioned in future work, how to choose the optimal failure time M still a problem. The larger the failure time, the higher power have to detect the difference since we collect more samples. However, large failure time also means long waiting time and high opportunity cost. Thus, there is trade off between waiting time and power.
A.2.2 OPTIMAL TREATMENT RULE FOR YAHOO DATA
Figure gives the decision tree of the estimated optimal treatment rule. Each left branch contains subpopulation whose covariates satisfy conditions on its parent node. The classification 0/1 on each leaf node indicates the optimal treatment rule for corresponding subpopulation, and the two values separated by slash gives the number of users who "truly" (estimated by random forest) benefit from control and treatment.
13

---

Under review as a conference paper at ICLR 2021
X3>=0.7094
X1< 0,03178
X4>=0:0003095
3606/7586
538/210
119/93
101/147
Figure 3: The decision tree of optimal treatment rule for Yahoo data
14


Reviews:
[{"review_id": "fEDvI5RuLbM", "reviewer": "AnonReviewer1", "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": "Summary:\nThis paper provides a statistical test that checks whether a subgroup would benefit from a certain intervention, even if on average the entire population does not benefit from that intervention. This test is developed for the online setting where we have a stream of data coming in and we want to terminate the trial (here, A/B testing) as soon as possible in order to limit the possible adverse effects that the trial might have.\n\nPros:\n- The paper is well-written and easy to read / understand.\n- According to the paper’s literature review, this work seems to be original.\n\nCons:\n- There are many design choices that the authors do not discuss the reasons behind making those choices; an example is: employing the augmented inverse probability weighted (AIPW) estimators. \n- It is unclear why $\\Delta$ should be defined as that in Eq. (11).\n- There is no step-by-step discussion on how the test statistic is derived as that in Eq. (12) or (15). By the way, are these two equations equivalent? If so, how?\n- Most importantly, I think the scope of this paper does not match with that of the ICLR conference, as there is no representation learning aspect in this work. Perhaps AISTATS, or even IJCAI or AAAI would be a better fit to publish this paper.\n\nMinor comments:\n- Sec. 3.1: $g(\\mu)=\\log(\\frac{\\mu}{1-\\mu})$ is undefined for a binary $\\mu$.\n- Item (4) in Algorithm 1: $\\overline{D}_k$ is a scalar and has no standard deviation.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FYu0UZ_p6K4", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors propose SUBTLE, which performs sequential A/B test with heterogeneous treatment effect. Compared to prior work, SUBTLE does not require specification of the parametric from of the treatment effect on some covariates.\n\nI believe the paper is original and could be useful for practitioners. The paper could be improved in clarity. See my detailed comments below. I believe most of the my comments could be easily addressed, and a few of them may require some more substantial work. \n\nOn page 2, the authors state \"it generally gives a significant decrease in the required sample size compared to the fixed-horizon test...\" I don't think this statement is true. The confidence level required to terminate the experiment early is usually required to be higher than the nominal alpha level. Furthermore, because we peek the experiment multiple times, the required confidence level at the final analysis point is also higher than the nominal alpha level. Thus, the required sample size for sequential testing is usually higher than that with classical fixed-horizon test. \n\nOn page 3, is there any constraint on \\mathcal{X}_0? It seems from (8) that it could theoretically be possible that \\mathcal{X}_0 is a set of disjoint points. In this case, even if the null hypothesis is rejected, we cannot practically launch the treatment. A more practical alternative hypothesis is either to constrain that \\mathcal{X}_0 is convex, or that for all x in \\mathcal{X}_0, theta(x) > 0 AND theta(x) >= 0 for all x (non-inferiority). \n\nOn page 4, I am confused by the big X notation. Is the probability/expectation on X taken with respect to the distribution of an individual observation X_i, a subgroup of observations \\mathcal{X}_0, or the distribution of all the observations \\mathcal{X}? On a related question, is Delta an observation-dependent value, a subgroup-dependent value, or a fixed value common for the population? Based on the formulation of (9), I suppose Delta is a population level value, but this will imply that V(d^opt) and V(0) are the same across subgroups with heterogeneous treatment effect. Is this reasonable? Am I missing anything?\n\nOn page 7, if I read Table 2 correctly, the rows with c=0/c=-1 show the type-I error rates of SUBTLE and SST. Why is SUBTLE so conservative given that alpha = 0.05 and the Type-I error rate are all greatly below 0.05?\n\nOn page 7, it will be good to include another simulated experiment to use random forest to estimate \\mathcal{X}_0. The authors did this on the real (private) dataset on page 8, but it would be good to do the same on a dataset where it is publicly available and the ground truth is known.\n\nOn page 10, what is the meaning of C4? How likely are C4 and C5 to hold? It would be good for authors to give an intuitive explanation, and, given that these two conditions are not standard in literature, run some numerical studies to directly validate these two conditions. Also, since the conditions are important, I suggest the writer to move the conditions to the main paper from appendix.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2VCXC5IR5Nf", "reviewer": "AnonReviewer4", "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": "*Summary*\n\nThis paper proposes a new algorithm (SUBTLE) to conduct online A/B testing that 1) allows for continuous monitoring, and 2) detects subgroups with enhanced treatment effect (if such subgroups exist). The authors formalize the problem into a clean hypothesis testing problem (9) that tests if the value gap between the optimal policy and the all-control policy is 0, propose the algorithm SUBTLE, and prove that it is able to control type I error at any time. Experiment results compare SUBTLE with the existing baseline SST, and show that SUBTLE is able to control type I error (while SST fails when the treatment has clear negative impact) and achieves competing detection power. \n\n*Overall Assessment*\n\nOverall I vote for acceptance.  This paper focuses on an important real-world problem that many ICLR readers care about, and is easy to follow in general.\n\n*Pros*\n- The problem considered in this paper looks real and relevant to me. I like the idea of \"testing the existence of a beneficial subgroup\", which should be more useful in practice than \"testing whether there's difference between treated and untreated\" as SST does. The testing hypotheses (9) look clean and reasonable to me.\n- The proposed algorithm (SUBTLE) adapts mSPRT to address the current problem, which is easy to understand and achieves provable type I error guarantees. It also enjoys relatively good performance in both simulated and real data experiments.\n- The paper is clearly written and easy to follow.\n\n*Cons and Questions*\n- SUBTLE performs extremely well in model V (the high-dimensional model), achieving lower type I error and higher power than in model I-IV.  I'm kind of doubtful about this result, since model V is essentially like model I-IV with more noise covariates, and as shown in section 4.2 adding more noise covariates lowers the estimated power. Is there any good explanation for this? Is it because the treatment effect structure in model V makes random forest a more favorable method? If so, how does SUBTLE perform when we have different $\\theta$ structures (like linear)?\n- SUBTLE looks relatively more conservative than SST when $c$ is small.  In many real-world applications, treatment effect $\\theta(X)$ is often smaller in magnitude than $\\mu(X)$, which is like small a $c$ in experiments. I am curious about how will the results look like when $c$ is smaller than $0.6$. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-4AFs0uPe2F", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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 is to propose a sequential test for subgroup treatment effects based on value difference, named SUBTLE,\nto address these two problems including  a fixed-horizon framework and  identifying a subgroup with a beneficial treatment effect。 \nAlthough there are several interesting results, this paper is full of many typos and small errors. Here are some detailed comments. \n\n1. Please not use (1)-(?) to itemize different things, since you also use them for equations. \n\n2. The estimator in (10) still suffers from the instability of the estimated propensity score. \n\n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a test for subgroup treatment effects in settings where data is obtained online, via a method they call SUBTLE.  The authors adopt a semi-parametric (generalized linear model) approach to modeling nuisance functions.  The authors derive the form of the distribution of their test statistic in (12), which is based on asymptotic normality the influence function based estimator.

The authors evaluate their methods via simulation studies, and on a dataset of user clicks from Yahoo!

The opinion of the reviewers was somewhat split on this paper.  One reviewer felt the paper was out of scope for ICLR, although this did not influence the overall evaluation of the paper -- since ICLR's scope has now broadened and solicits work on all areas of machine learning and related areas of data science (as the ICLR website makes clear).

However, reviewers raised a number of concerns about the paper (in particular, see reviewer 2) that on balance did not persuade them that the paper is ready for publication in the current state.
Decision: Reject