A REINFORCEMENT LEARNING FRAMEWORK FOR TIME DEPENDENT CAUSAL EFFECTS EVALUATION IN A/B TESTING
Authors: Chengchun Shi
Xiaoyu Wang
Shikai Luo
Rui Song
Hongtu Zhu
Jieping Ye
Venue:  (2021)
Keywords: reinforcement learning
A/B testing
causal inference
sequential testing

Abstract: A/B testing, or online experiment is a standard business strategy to compare a new product with an old one in pharmaceutical, technological, and traditional industries. The aim of this paper is to introduce a reinforcement learn- ing framework for carrying A/B testing in two-sided marketplace platforms, while characterizing the long-term treatment effects. Our proposed testing procedure allows for sequential monitoring and online updating. It is generally applicable to a variety of treatment designs in different industries. In addition, we systematically investigate the theoretical properties (e.g., size and power) of our testing procedure. Finally, we apply our framework to both synthetic data and a real-world data example obtained from a technological company to illustrate its advantage over the current practice. 


Under review as a conference paper at ICLR 2021
A REINFORCEMENT LEARNING FRAMEWORK FOR TIME DEPENDENT CAUSAL EFFECTS EVALUATION IN A/B TESTING
Anonymous authors Paper under double-bling blind review
ABSTRACT
A/B testing, online experiment is a standard business strategy to compare new product with an old one in pharmaceutical, technological, and traditional indus- tries. The aim of this paper is introduce reinforcement learning framework for carrying A/B testing in two-sided marketplace platforms, while characterizing the long-term treatment effects. Our proposed testing procedure allows for sequential monitoring and online updating. is generally applicable to a variety of treatment designs in different industries. In addition, we systematically investigate the theo- retical properties (c.g., size and power) of our testing procedure. Finally, we apply our framework to both synthetic data and real- world data example obtained from a technological company to illustrate its advantage over the current practice.
INTRODUCTION
A/B testing, online experiment is business strategy compare new product with old one in pharmaceutical, technological, and traditional industries (e.g.. Google, Amazon, or Facebook). Most works in the literature focus on the setting, in which observations are independent across time (see e.g. Johari et al., [2015] 2017 and the references therein). The treatment at given time can impact future outcomes. For instance, in ride-sharing company (e.g., Uber), an order dispatching strategy not only affects its immediate income, but also impacts the spatial distribution of drivers in the future, thus affecting its future income. In medicine, usually takes time for drugs to distribute to the site of action. The independence assumption is thus violated.
The focus this paper is to test the difference in long-term treatment effects between two products in online experiments. There are three major challenges as follows. (i) The first one lies in modelling the temporal dependence between treatments and outcomes. (ii) Running each experiment takes a considerable time. The company wishes to terminate the experiment as early as possible in order to save both time and budget. (iii) Treatments are desired to be allocated in a manner to maximize the cumulative outcomes and detect the alternative more efficiently. The testing procedure shall allow the treatment to be adaptively assigned.
We summarize our contributions as follows. First, introduce reinforcement learning (RI., e.g., & Barto 2018 for an overview) framework for A/B testing. In addition to the treatment- outcome pairs, it is assumed that there is a set of time-varying state confounding variables. We model the paate-trettment-outtooe 1994) characterize the association between treatments and outcomes across time. Specifically, at each time point, the decision maker selects a treatment based on the observed state. The system responds by giving the decision maker corresponding outcome and moving into a new state the next time step. In this way. past treatments will have an indirect influence on future rewards through its effect on future state variables. In addition, the long-term treatment effects can be characterized by the value functions (see Section 3.1 for details) that measure the discounted cumulative gain from a given initial state. Under this framework, it suffices to evaluate the difference between two value functions compare different treatments. This addresses the challenge mentioned in (i).
triplet by using the Markov decision process (MDP, see e.g. Puterman]
Second, we propose a novel sequential testing procedure for detecting the difference between two value functions. To the best of our knowledge, this is the first work developing valid sequential tests in the RL framework. Our proposed test integrates temporal difference learning (see e.g., Pre- cup et al., 2001: Sutton et al. 2008), the a-spending approach (Lan & DeMets 1983) and bootstrap

---

Under review as a conference paper at ICLR 2021
(Efron & Tibshirani [994] to allow for sequential monitoring and online updating. is generally ap- plicable to a variety of treatment designs, including the Markov design, the alternating time-interval design and the adaptive design (see Section 4.4). This addresses the challenges in (ii) and (iii).
Third, we systematically investigate the asymptotic properties of our testing procedure. We show that our test not only maintains the nominal type I error rate, but also has non-negligible powers against local alternatives. To our knowledge, these results have not been established in RL.
Finally, we introduce a potential outcome framework for MDP. We state all necessary conditions that guarantee that the value functions are estimable from the observed data.
2 RELATED WORK
There is a huge literature on RL. such that various algorithms are proposed for an agent to learn an optimal policy and interact with an environment. Our work is closely related the literature on off- policy evaluation, whose objective is to estimate the value of a new policy based on data collected by different policy. Popular methods include Thomas et al. (0155) Jiang & Li (2016): Thomas & Brunskill (2016): Liu et al. (2018); Farajtabar et al. (2018); Kallus & Uehara (2019). Those methods required the treatment assignment probability (propensity score) to be bounded away from O and 1. As such, they are inapplicable to the alternating-time-nntere design, which is the treatment allocation strategy in our real data application.
Our work is related to the lemporal-differencc learning method based function approximation. Convergence guarantees of the value function estimators have been derived by [Suttnn et al. (2008) under the setting of independent noise and by Bhandari et al. (2018) for Markovian noise. However, uncertainty quantification of the resulting value function estimators have been less studied. Such results are critical for carrying out A/B testing. [Luckett et al. (2019) outlined procedure for timating the value under a given policy. Shi et al. (2020b) developed a confidence interval for the value. However, these methods do not allow for sequential monitoring or online updating.
In addition to the literature on RI., our work is also related to a line of research on evaluating time- varying causal effects (see e.g. Robinns 1986. Boruvka et al. [2018 Ning et al.] 2019; Rambachan
& Shephard 2019 Viviano & Bradic 2019; Bojinov & Shephard 2020). However, none of the above cited works used an RL framework to characterize treatment effects, In particular, Bojinov & Shephard (2020) proposed to use importance sampling (IS) based methods to test the null hypothesis of no (average) temporal causal effects in time series experiments, Their causal estimand is different from ours since they focused characterized by the value function. Moreover, their method requires the propensity score to be bounded away from O and 1, and thus is not valid for our applications.
p lag treatment effects, whereas we consider the long-term effects
Furthermore, our work is also related to the literature on sequential analysis (see e.g. Jennison & Turnbull 1999] and the references therein), in particular, the a-spending function approach that allocates the total allowable type I error rate at each interim stage according to an error-spending function. Most test statistics in classical sequential analysis have the canonical joint distribution (see Equation 13. [Jennison & Turnbull 1999) and their associated stopping boundary can be recursively updated via numerical integration. However, in our setup, test statistics no longer have the canonical joint distribution when adaptive design is used. This is due to the existence of the carryover effects in time. We discuss this detail in Appendix C To resolve this issue. we propose a scalable pootstrap-assister procedure to determine the stopping boundary (see Section 4.3
Recently, there is a growing literature on bringing classical sequential analysis to A/B testing. In particular, et al. (2015) proposed an always valid test based on the classical mixture sequential probability ratio tests (mSPRT). Kharitonov et al. (2015) propose modified versions of the O' O'Bienn & Fleming and MaXSPRT sequential tests. Deng et al. (2016) studied A/B testing under Bayesian framework. Abhishek Mannor (2017) developed bootstrap mSPRT. These tests cannot detect the carryover effects in time, leading to low statistical power in setup. See the toy examples in Section Section[4.]]oor for detailed illustration.
In addition, we note that there is line of research on bandit/RL with causal graphs (see e.g., Lee & Bareinboim| 2018 2019). We remark that the problems considered and the solutions developed in this article different from these works. Specifically, these works considered applying causal inference methods to deal with unmeasured confounders in bandit/RL settings whereas we apply the RL. framework to evaluate time-dependant causal effects.
2

---

Under review as a conference paper at ICLR 2021
Finally, we relax several key conditions used in Ertefaie (014)) and Luckett et al. (2019) that pre- sented a potential outcome framework for MDP (see Section 3.1 for details). Specifically, Ertefaie the observed data rather than
(2014) and Luckett et al. (2019) imposed the Markov conditions the potential outcomes, while assuming that the outcome at time t a deterministic function of the state variables at time i, + 1 and the treatment at time t.
PROBLEM FORMULATION
3.1 A POTENTIAL OUTCOME FRAMEWORK FOR MDP
For simplicity, we assume that there are only two treatments (actions, products), coded and 1, respectively, For any t 2 0, let ãr (Ao. 01,' a.) E {0, 13 denote a treatment history vector up time t. Let S denote the support state variables and So denote the initial state variable. We assume S is a compact subset of IR For any (ãt-1. āz). let S (ā and Y," (āt) be the counterfactual state and counterfactual outcome, respectively, that would occur at time had the agent followed the treatment history âe. The set of potential outcomes up to time /. is given by
(octicss,productss),
W (a+) (So, Yo (an), Si (ao), ... St (a+-1), Y ( (a.)).
Let W = e/ W (āz) be the set of all potential outcomes.
A deterministic policy actions. For any such æ, let fy denote the treatment history up to time I,, assigned according to m. We use S7 (T) and + denote the associated potential state and outcome that would occur at time t had the agent followed π. The goodness of a policy π is measured by its value function.
function that maps the space of state variables the of available
V(T;s) Σ ( (S. s),
t20
where 0 < < 1 is discounted factor that reflects the trade-off between immediate and future outcomes. Note that our definition of the value function is slightly different from those in the existing literature (see Sutton& & Barto 2018 for example). Specifically, ((T;; 8) is defined through potential outcomes rather than the observed data. Similarly, we define the Q function by
(T;a,,8) Σ (TE = =s],
120
where (a)(a)) denotes the treatment history where the initial action equals and all other actions are assigned according to ..
In our setup, we focus on two nondynamic policies that assign the same treatment at each time point. We use their value functions (denote by V(1;-) and -): to measure their long-term treatment effects. Meanwhile, our proposed method equally applicable as well. See Section B.I for details. To quantitatively compare the two policies, we introduce the Average Treatment Effect (ATE) based on their value functions which relates RL to causal inference.
the dynamic policy scenario
Definition. For given reference distribution function G, ATE is defined by the integrated difference between two value function, i.e., ATE [ (V(;s) VO; (dss)
The focus of this paper is to test the following hypotheses:
Ho To ATE < 0 v.s H1 To ATE 0.
When Hg holds, the new product is no better than the old one.
3.2 IDENTIFIABILITY OF ATE
One of the most important question in causal inference is the identifiability of causal effects. this section, we present sufficient conditions that guarantee the identifiability of the value function.
In practice, with the exception of Sg, the set W cannot be observed, whereas at time t, we observe the state-action-outcomee triplet (S., A,, Yt). For any 0. let A, (Au, A1. , A,) denote the observed treatment history. We first introduce two conditions that are commonly assumed in multi-stage decision making problems (see e.g. Murphy 20033 Zhang et al. 2013 Kennedy 2019).
(CA) Consistency assumption: S Si+r(A,) and Y, Y; (Ar) for all 2 O. almost surely.
(SRA) Sequential randomization: A, is independent of W given S, and (Sj, A,, YjJosjst-
3

---

Under review as a conference paper at ICLR 2021
The SRA implies that there are unmeasured confounders and it automatically holds in online experiments, which the treatment assignment mechanism is pre-specified. A, to depend on the observed data history St. A,, Y3 tosj<t and thus, the treatments can be adaptively chosen. We next introduce two conditions that are unique to the RL setting.
SRA, we allow
(MA) Markov assumption: there exists Markov transition kernel P such that for any 2 O, a E (0,1) and S C Rdd we have Pr(S; (ā,) E SIW, (a,)) = P(S; a, S7 (āz-1))-
(CMIA) Conditional mean independence assumption: there exists function r such that for any 1 2 0, ag & {0,1)--1 we have E{Y," (at) (a+-1), (2-1 = S (a+-1)).
These conditions central to the empirical validity of reinforcement learning (RL... Specifi- cally, under these two conditions, there exists an optimal policy x' such that ;(= 2 V(T;:) for any π and s. We observe that Ertefaie (2014) and Luckett et al. (2019) imposed the Markov conditions on the observed data rather than the potential outcomes. When CA and SRA hold, these assumptions are equivalent. When SRA is violated, their Markov assumptions could be violated as the treatment depends on unobserved confounders and the observed data process is no longer Markovian. CMIA requires past treatments to affect (ā+) only through its impact on S7 (ā;-1). In other words, the state variables shall be chosen to include those that serve as important mediators between past treatments and current outcomes. Under MA, CMIA automatically satisfied when Y (ā+) is deterministic function of (Si+1 (āe), ac, St (ā,-1)) that measures the system's 's status at time + 1. The latter condition is commonly imposed in the reinforcement learning literature.
To conclude this section, we derive version of Bellman equation for the Q function under the potential outcome framework. Specifically, for a' E {0. 1}. let Q(a':.,)) denote the Q function where treatment a' is repeatedly assigned after the initial decision.
Lemma Under MA, CMIA, CA and SRA, for any t S x {0,1) IR, we have E[[Q(a'; At, Si) - Y, ~Q a', S4t))p(SS, At) = 0.
d' E {0, and any function up :
Sketch of Proof: Under MA, CMIA, CA, SRA, the defined Q-function under the potential outcome framework is the same as that defined on the observed data. Lemmal followw from the classical Bellman equation (see Equation (4.6) in Sutton & Barto 2018
Lemma I implies that the Q-function is estimable from the observed data. Specifically, an estimating equation can be constructed based on Lemma D and the Q-function can be learned by solving this estimating equation. Note that (a s) = (( a, s) and To is completely determined by the value function V. As result, To is estimable from the observed data as well. We remark that the positivity assumption is not needed in Lemma [ Our procedure can thus handle the case where treatments are deterministically assigned, i.e., the behavior policy is deterministic, This is due to MA and CMIA that assume the system dynamics are invariant across time. To elaborate this, note that the discounted value function is completely determined by the transition kernel P and the reward function r. We remark that these quantities can be consistently estimated under certain conditions (see C1-C3 in Appendix regardless of whether b is deterministic or not.
TESTING PROCEDURE
We first introduce toy example to illustrate the limitations of existing A/B testing methods. We next present our method and prove its consistency under variety of different treatment designs.
4.1 TOY EXAMPLES
Existing A/B testing methods can only detect short-term treatment effects, but fail identify any long-term effects. To elaborate this, we introduce two examples below.
Example S. = 0.5c, Y, = S. + 5A, for any 2 1 and 5g- = 0.55o
Example 2. S: 0.5S, + 5.A, + 0.55,, Y, S, for any | 2 and So = 0.5ep-
In both examples, the random errors {Er)c2 follow independent standard normal distributions and the parameter 8 describes the degree of treatment effects. Suppose 5 > O. Then Hi holds. In Example 1, the observations are independent and there are no carryover effects at all. In this case, both the existing A/B tests and the proposed test able to discriminate H₁ from Hg. In Example 2, however, treatments have delayed effects on the outcomes. Specifically, Y, does not depend on A,, but is affected by A through S.. Existing tests will fail to detect H1 as the short-term conditional
4

---

Under review as a conference paper at ICLR 2021
Example |
Example
1-test 0.76
DML-based test test 0.98
(-test 0.04
DML-based test 0.06 test 0.73
Table 1: Powers of t-test, DML-based test and the proposed test under Examples 1 and 2, with 7' = 500, 5 = 0.1. (Ar) follow ii.d. Bermoulli distribution with success probability 0.5.
average treatment effects A(Y; L, St) E(Y, illustration, we conduct a small experiment by assuming the decision is made once at T 500, and report the empirical rejection probability of the classical two-sample t-test that is commonly used in online experiments, a more complicated test based on the double machine learning method (DML, Chernozhukov al. (017) that is widely employed for inferring causal effects, and the proposed test. It can be seen the competing methods do not have any power under Example 2.
0, S:) 0 in this example. As an
4.2 AN OVERVIEW OF THE PROPOSAL
First, we estimate To based on a version of temporal difference learning. The idea to apply basis function approximations solve an estimating equation derived from Lemma [ Specifically, let
Q = (v (s) Ba',a E IR9 be a large linear approximation space for Q(a"; a, 8). where (.) a vector containing y basis functions on S. The dimension q is allowed depend the number of samples T to alleviate the effects of model misspecification. Let us suppose Q Q for moment. By Lemma there exists some 3 ( $1,0 (t,1) such that
B[(V (S. Y, - > 15 (S,) = a)] = O, Va, E (0,
where I(.) denotes the indicator function. Let E(s, a) ( (s) 0), v (s) 1)BT. The above equations can be rewritten as E( = En,, where E, is a block diagonal matrix given by E, E(St, A.S,, Ar) 0))
((S), A.) 1))
and 7) = (E(S,, A.) E(,, A.) TY.
Let -()= Σy and 7(t) === ng It follows that E ((())()) = [[(())))=B(((()) This motivates to estimate 3 by ((t) (T, (T)) (T) = =)-((1)((). ATE can thus be estimated by the plug-in in estimator f(t) = S, v (311 (o.)))))G((ss)
Second, use f(t) to construct our test statistic time t. We will show vf(F(t)- is asymptot ically normal. Its variance can be consistently estimated by (t) ()))
as grows to infinity, where U = {- Saes (s) G(ds), 0, 0 J.es (ss) 0g2 denotes
zero vector of length and (t) corresponds to some consistent covariance estimator of nr based
on the data observed at time (see equation 3 for the explicit form). This yields our test statistic (t) at time t.
Third, we integrate the a-spending approach with bootstrap to sequentially implement our test (see Section 4.3) The idea is to generate bootstrap samples that mimic the distribution of our test statis- ties, to specify the stopping boundary at each interim stage. Suppose that the interim analyses are < K, we assume T + C for
conducted at time points Ti < <... Tk T. For each some constants 0 < C1 < < CK- < 1.
4.3 SEQUENTIAL MONITORING AND ONLINE UPDATING
Let (Z,,... ,2x} denote the sequence of our test statistics, where 7 = (TT)) To sequentially monitor test, need to specify the stopping boundary (bw) such that the experiment is terminated and Ho is rejected when Z by for some k.
First, we use the a spending function approach guarantee the validity of our test. requires to specify a monotonically increasing function a--) that satisfies a()) 0 and (T") a. Some popular choices of the a spending function include
a1 (t) = 2 2 ( 2 a T/2)/ and az(() (t/T)) for 0 0, where (--) denotes the normal cumulative distribution function. Adopting the spending approach, we require by 's to satisfy
Pr(u > b,)) = (Tx)) + +0(), 4i K.
(2)
5

---

Under review as a conference paper at ICLR 2021
As commented in the introduction, the numerical integration method is not applicable to determine the stopping boundary. Our method is built upon the wild bootstrap (Wu al. 1986). The idea is to generate bootstrap samples that have asymptotically the same joint distribution as the test statisties. However, we note that directly applying the wild bootstrap algorithms is time consuming. See Section
[ for details. To facilitate the computation, we present a scalable bootstrap algorithm to determine {bx 3.. Let {e*}x be a sequence of i.ddd (0,, Lag) random vectors, where L stands for J x J identity matrix for any J. Let (2(Th) be 4g 4q zero matrix. At the k-th stage, we compute
2 = U U (T))
E(THE) - T -,)00)))))
(Tk) j=1
key observation that, conditional on the observed dataset, the covariance of 2 and Zi, equals that of Zk, and Zkz See Theorem 3 for details. In addition, the limiting distributions of {Zx} and {Zk} ) are multivariate normal. As such, the joint distribution of (7k} Ja can be well approximated by that of {Zī]a conditional on the data. This forms the basis of our bootstrap algorithm. By the requirement on {bx} in 2
we obtain Pr (r(maxxss<*(22 6,) - 0, Zμ > bu) a a(T)) a(Tx-1)+ o(1). To implement our test, we recursively calculate the threshold by as follows,
Pr'
max [2) - b,) = 0, 2 bx = a(T)) - (TT--1),
where Pr" denotes the conditional probability given on the data, and reject Ho when Z > by for some k. In practice, the left-hand-side be approximated via Monte carlo simulations.
4.4 CONSISTENCY UNDER DIFFERENT TREATMENT DESIGNS
We consider three treatment allocation designs that can be handled by our procedure as follows:
DI. Markov design: Pr(A, 1[St, {Sj, Aj, YsJosser) = (S.) for some function (.)))) uni- formly bounded away from and
D2. Allernating-timm--nteeee design: A2; = 0, A2i+1 1 for all 2 O.
D3. Adaptive design (e.g., e-greedy): For Th S 1 < Tx+1 for some 2 O, Pr(A, = 1 JS,, {S}; Aj, Y)Josi<:) = (S.) for some (-) that depends on {S}, Aj; YiJosieTt
Here, D2 is deterministic design and is widely used in industry (see our real data example). D1 and D3 are random designs. D1 commonly assumed in the literature on off-policy evaluation (see e.g.,
Jiang & Li 2016). D3 is widely employed in the contextual bandit setting balance the trade-off' between exploration and exploitation. These three settings cover a variety of scenarios in practice.
Theorem (Type-I error) Suppose ax(-) is continuous, CI-C3 (see Appendix E hold and q
of o(VT/ (o/logT). Then Pr(U,=1(2, > b,)) S (Txx) + for, all S k S K under Ho-
Sketch of Proof: We consider the case where To 0 only. The general case is proven in Section As discussed in Section 4.3 the conditional distribution of {Zū) ) given the data is equivalent as the distribution of {Zx}k. Since {bx hx is continuous function of {ZZ) k. follows from the continuous mapping theorem that (bx Ju are consistent. The proof is hence completed.
Theorem I jimplies that the type-I error rate of the proposed test is well controlled. When ATE- 0. the equality in Theorem [ hoolds. The rejection probability achieves the nominal level under Ho-
Theorem (Power) Under the conditions of Theorem 1 assume To >> T- 1/2, then Pr(Zi > b,) - 1. Assume To T for some h > 0. Then limi (Pr(U ( > b,}) ax [T+) > 0.
Sketch of Proof: Under H1, similar to Theorem we have Pr(U aTT)) + o(1) The follooo by that Zi is stochastically larger than Z, TT for all j.
/Tyoo/ > bi}
The second assertion in Theorem 2 implies that our test has non-negligible powers against local alternatives converging to Ho at the 1/2 rate. When the signal decays to zero faster than this rate, our test is not able to detect H,. When the signal decays at slower rate, the power of our test approaches 1. Combining Theorems yields the consistency of our test.
Finally, it is worth mentioning that test can be online updated batches of observations arrive at the end of each interim stage. We summarize our procedure in Algorithm (see Appendix A). Its time complexity is dominated by O(Bq² + T

---

Under review as a conference paper at ICLR 2021
1.0
0.0
2-141
04
012
0.0
1.3
Ohservation Times
Obvarvatin
0.06
0.7
0.06
042
810
300
600
300
439
500
600
400
300
1.0
1.3
0.5
Bed11
046
01
040
0.00
810
300
505
600
300
400
500
600
300
-00
360
600
(a) The proposed test under 17, (left) and No (right)
(h) Two-sample t-test under H4 (left) and Wo (right)
Figure 1: Empirical rejection probabilities of our test and the two-sample t-test with a(-) on (-). Settings correspond to the alternating- tieemating-timeiiiie tintriervaliiiiierllll... adaptive and Markov design, from top plots to bottom plots.
NUMERICAL STUDIES
5.1 SYNTHETIC DATA
Simulated data of states and rewards was generated as follows,
S = (2 1as--1--551,11 () S2,(1-1)44444 8 + $1,6
S2 (2A - 010--) 6A, E2,1, Y= (S1, S2,) + E3.
where the random errors ( are i.idd N 0.55) and (53.c)osesT are i.i.d NO, 0.3²). The initial states S1,0 and S2,0 are independent N (O, 0.5²) as well. Let S, = (Si,,, S2,) denote the state at time l. Under this model, treatments have delayed effects on the outcomes, as in Example 2. The parameter ō characterizes the degree of such carryover effects. When 8 0. 0 and Ho holds. When > 0, H1 holds. Moreover, To increases as ò increases.
We set K = 5 and (Ti, T2, T3, T22 Tb) (300, 375, 450, 525, 600). The discounted factor y is set to 0.6 and G is chosen as the initial state distribution. We consider three behavior policies, according to the designs DI-D3, respectively. For the behavior policy in DI, we set b(0) (s) = 0.5 for any s S. For the behavior policy D3, we use an e-greedy policy and set (s)) c/2 + (1
(33), - (T.))T))) > 0), with e = 0.1, for any k 2 1 and EES E.
For each design, we further consider five choices of 6, corresponding The significance level a is set to 0.05 in all cases. To implement our test, we choose two a-spending The hyperparameter 0 in a2(-) is
0, 0.05, 0.1, 0.15 and 0.2.
functions, corresponding to ai (-) and (x2()) given in equation
set to 3. The number of bootstrap sample is set to 1000. In addition, we consider the following polynomial basis function, (s) = (s),82)
(1, 81, s² ... .s 82, 22. ...... s5) with J 4.
We also tried some other values of J by setting J to 3 and 5. Results are reported in Figure 6 (see Appendix G.. It can seen that the resulting tests not sensitive to the choice of J.
All experiments run on a macbook pro with dual-core 2.7 GHz processor. Implementing a single test takes one second. Figures ① (a) and (5 (see Appendix G depict the empirical rejection proba- bilities of our test statistics at different interim stages under Ho and H₁ with different combinations of 8, a-)) and the designs. These rejection probabilities are aggregated over 500 simulations. We also plot on az(-) and (-2(-) under Hy- Based on the results, it can be seen that under Ho, the type-I error rate of our test is well-controlled and close to the nominal level at each interim stage. Under H,, the power of our test increases 8 increases, showing the consistency of our test procedure.
To further evaluate our method, we compare with the classical two-sample t-test and the sequential test developed by Kharitonov et al. (2015). To apply the t-test, for each Tk. we apply the t-test the
7

---

Under review as a conference paper at ICLR 2021
23
24-
14-
14-
32-
300
200
450
580
700
300
300
400
Figure 2: Our test statistic (the orange line) and the rejection boundary (the black line) in the A/A (left plot) and A/B (right plot) experiments.
data {A,, Josesn, and plot the corresponding empirical rejection probabilities in Figures I (b) and b) (Appendix G). Results for Kharitonov et al. (2013)'s test are reported in Figure A (Appendix Both competing methods fail to detect any carryover effects and do not have any power.
We next explain why several other methods mentioned the introduction cannot be used for com- parison. First, a lot of causal effects evaluation methods did not consider early termination. Conse- quently, they are unsuitable to apply in our numerical studies. Second, standard temporal difference learning method did not study the asymptotic distribution of the resulting value estimators. These results are critical for carrying out A/B testing. Finally, many methods proposed to use inverse propensity-sooe score weighting. These methods not valid for the alternating- cetmmating-iieeeae diie--nterval design.
5.2 REAL DATA APPLICATION
We apply the proposed test to a real dataset from a ride-sharing platform. Order dispatching is one of the most critical problems in online ride-hailing platforms to adapt the operation and manage- ment strategy to the dynamics in demand and supply. The purpose of this study is to compare the performance of newly developed strategy with a standard control strategy used in the platform. The new strategy is expected to reduce the answer time of passengers and increase drivers income. For given order, the new strategy will dispatch it to a nearby driver that has not yet finished their previous ride request, but almost. In comparison, the standard control assigns orders to drivers that have completed their ride requests.
The experiment is conducted at a given city from December 3rd to December 16th. Dispatch strate- gies are executed based on alternating half-hourly time intervals. We also apply our test data from an A/A experiment (which compares the baseline strategy against itself), conducted from November 12th November 25th. We expect that our test will not reject Ho when applied to the data from the A/A experiment, since the two strategies used are essentially the same.
Both experiments last for two weeks. Thirty- 48(k: + 6) for k = 1.....8. 8. That is, the first interim analysis is performed at the end of the first week, followed by seven more at the end of each day during the second week. We choose the overall drivers' income in each time unit as the response. The new strategy is expected to reduce the answer time of passengers and increase drivers' income. Three time-varying variables are used to construct the state. The first two correspond to the number of requests (demand) and drivers' online time (supply) during each 30-minutes time interval. These factors are known to have large impact drivers' income. The last one is the supply and demand equilibrium metric. This variable characterizes the degree that supply meets the demand and serves as an important mediator between past treatments and future outcomes.
defined as one time unit. We set Tg
To implement our test, we set = 0.6, B = 1000 and use a fourth-degree polynomial basis for (-). as in simulations. We use ar (.) as the spending function for interim analysis and set 0.05. The test statistic and its corresponding rejection boundary at each interim stage are plotted in Figure 2 can be seen that our test able to conclude, at the end of the 12th day, that the new order dispatch strategy can significantly increase drivers' income, and meet more order requests. In addition, based on the dataset from the A/B experiment, we found that the new strategy reduces the answer time of orders by 2%, leading to almost 2% increment of drivers income. When applied to the data from the A/A experiment, we fail to reject Ho, as expected. For comparison, we also apply the two-sample t- test to the data collected from the A/B experiment. The corresponding p-value is 0818. This result is consistent with our findings. Specifically, the treatment effect at a given time affects the distribution of drivers in the future, inducing interference in time. As shown in the toy example (see Section 4.1, the t-test cannot detect such carryover effects, leading to a low power. Our procedure, according to Theorem 2 has enough powers to discriminate H, from Ho-
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Vineet Abhishek and Shie Mannor. A nonparametric sequential test for online randomized experi- ments. In Proceedings of the 26th International Conference World Wide Web Companion, pp- 610-616. International World Wide Web Conferences Steering Committee, 2017.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. arXiv preprint arXiv:1806.0244 000.000000004, 2018.
lavor Bojinov and Neil Shephard. Time series experiments and causal estimands: exact randomiza- tion tests and trading, volume accepted. Taylor & Francis, 2020.
Audrey Boruvka, Daniel Almirall, Katie Witkiewitz, and Susan A. Murphy. Assessing time-varying causal effect moderation in mobile health. J. Amer. Statist. Assoc., 113(523):1112-11221 2018. ISSN 0162 1459. doi: 10. 10.100001621459 211.445991..155222
Prabir Burman and Keh-Wei Chen. Nonparametric estimation of regression function. Ann. Statist., 17(4):1567-156, 1989. ISSN 0090-5364. doi: 10. 1211/1//ass// 176347382.
Xiaohong Chen and Timothy M. Christensen. Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions. J. Econometrics, doi: 1..0016f..cconomm2015..533
188(2):447-465, 2015. ISSN 0304-4076.
Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, and Whit- ney Newey, Doubbl//debiassedheemman machine learning of treatment effects. American Economic Review, 107(5):261-65, 2017.
Alex Deng, Jiannan Lu, and Shouyuan Chen. Continuous monitoring of a/b tests without pain: Optional stopping in bayesian testing. In 2016 IEEE International Conference Data Science and Advanced Analytics (DSAA), pp. 243-252. IEEE, 2016.
Bradley Efron and Robert J Tibshirani. An introduction to the bootstrap. CRC press, 1994.
Ashkan Ertefaie. Constructing dynamic treatment regimes in infinite-horizon settings. arXiv preprint arXiv: 1406.0764, 2014.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off pol-cy evaluation. In International Conference Machine Learning, 2018.
Jianhua Z. Huang. Projection estimation in multiple regression with application to functional ANOVA models. Ann. Statist., 26(1):242-272, 1998. ISSN 00900-3664. doi: 10.1214/aos
1030563984.
Christopher Jennison and Bruce W Turnbull. Group sequential methods with applications to clinical trials. Chapman and Hall/CRC, 1999.
Nan Jiang and Lihong Li. Doubly robust off off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661, 2016.
Ramesh Johari, Leo Pekelis, and David Walsh. Always valid inference: Bringing sequential anal- ysis to a/b testing. arXiv preprint XrXiv:1512.04922, 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.
Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon: Double reinforce- ment learning infinite infinite-horizon processes. arXiv preprint arXiv: 05850, 2019.
Edward H Kennedy. Nonparametric causal effects based incremental propensity score interven- tions. Journal of the American Statistical Association, 114(526):645-533 6556, 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.

---

Under review as a conference paper at ICLR 2021
K. K. Gordon Lan and David L. DeMets. Discrete sequential boundaries for clinical trials. Biometrika, 70(3):659-660 663, 1983. ISSN 0006- 34443444. doi: 10.2307/2336502.
Sanghack Lee and Elias Bareinboim. Structural causal bandits: where to intervene? In Advances in Neural Information Processing Systems, pp. 2568-2578, 2018.
Sanghack Lee and Elias Bareinboim. Structural causal bandits with con-manipulable variables. In
Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4164-4172, 2019.
Qiang Liu, Lihong Li. Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018.
Daniel Luckett, Eric Laber, Anna R Kahkoska, David M Maahs, Elizabeth Mayer-Dave Davis, and Michael R Kosorok. Estimating dynamic treatment regimes in mobile health using v-learning. Journal of the American Statistical Association, accepted, 2019.
D. L. McLeish. Dependent central limit theorems and invariance principles. Ann. Probability. 2: 620-628, 1974. ISSN 0091-1798, doi: 10.1214/aop/ 176996608.
S. A. Murphy. Optimal dynamic treatment regimes. J. Stat. Soc. Ser. B Stat. Methodol., 65(2): 331-366, 2003. ISSN 1369-7412. doi: 10.11 111117766998 000899.
Bo Ning, Subhashis Ghosal, and Jewell Thomas. Bayesian method for causal inference in spatially- correlated multivariate time series. Bayesian Anal., 14(1):1-28, 2019. ISSN 1936-0975, doi: 10. 1
Doina Precup, Richard S Sutton, and Sanjoy Dasgupta. Off-policy temporal-difference learning with function approximation. In ICML, pp. 417 124,4444,7 2001.
Martin L. Puterman. Markov decision processes: discrete stochastic dynamic programming. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Inc., New York, 1994. ISBN 0-471-61977-9. A Wiley- Intersenteeeeeecee Publication.
B. Rabta and D. Aissani. Perturbation bounds for Markov chains with general state space. J. Math.
Sci. (N.Y.), 228(5):500-521 2018. ISSN 1072-3374. doi: 11110077/10958-07--3366
Ashesh Rambachan and Neil Shephard. A nonparametric dynamic causal model for macroecono- metrics. Available SSRN 3345325, 2019.
James Robins. A new approach causal inference in mortality studies with a sustained exposure aprrid--appiiatiion to control of the healthy worker survivor effect. volume 7, pp. 1393-1512. 1986. doi: 10. 1L1116662220002588889000033 epidemics, Part 2.
Mathematical models in medicine: diseases and
Chengchun Shi, Sheng Zhang, Wenbin Lu, and Rui Rong. Statistical inference of the value function for reinforcement learning in infinite horizon settings. arXiv preprint urXiv:2001.045/1 2020a.
Chengehun Shi, Sheng Zhang, Wenbin Lu, and Rui Song. Statistical inference of the value function for reinforcement learning infinite horizon settings. arXiv preprint arXiv:2001.0455 050555,,,,.,5,,,, 2020b.
Charles J. Stone. Optimal global rates of convergence for nonparametric regression. Ann. Statist., 10(4):1000-1033, 1982. ISSN 0090-5364.
Richard S. Sutton and Andrew G. Barto. Reinforcement learning: introduction. Adaptive Com- putation and Machine Learning. MIT Press, Cambridge, MA, second edition, 2018. ISBN 978-0- 262-03924-6.
Richard Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent o(n) algorithm for off- policy temporal-difference learning with linear function approximation. Advances in neural in- formation processing systems, (1(21)1660--1116 2008
Philip Thomas and Emma Brunskill. Dfta-efficient off off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning, pp. 2139-2148, 2016.
10

---

Under review as a conference paper at ICLR 2021
Philip S Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-
policy evaluation. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Davide Viviano and Jelena Bradic. Synthetic learner: model-free inference on treatments over time. 2019.
arXiv preprint
Chien-Fu Jeff Wu et al. Jackknife, bootstrap and other resampling methods in regression analysis. the Annals of Statistics, 14(4):1211-1295, 1986.
Baqun Zhang, Anastasios A. Tsiatis, Eric B. Laber, and Marie Davidian. Robust estimation of optimal dynamic treatment regimes for sequential treatment decisions. Biometrika, 100(3):681- 694, 2013.

---

Under review as a conference paper at ICLR 2021
Input: no, of basis functions q. no. of bootstrap samples B, an spending function a(-).
Initialize: I {1..... B}. Set S2 Eu, En to zero matreies, and î, Si. SB zero vectors.
Compute U (see Section 4.2 using either Monte Carlo methods or numerical integration.
For k = to K:
Step 1. Online update of ATE.
For T to
1: Σ = (1 (1-1--10 1- En + E(S,, (5(S, Ar) 7E(S,41, a)} T 0,00=0,,0 0,
(1-t -t 1--t))n t
A.),,
Set (3% )T, Σg n for E [0,1] and 7 -
Step 2. Online update of the variance estimator.
Initialize 92" to zero matrix. For = Tk- to T3 1:
Ét.a = Yú + " (S V (S.) for a = 0,
'2' 02" + (E(Se, Ac) A E(,,, A.) G.,1) (E(S), A.) (
Er, E(S,, &r.1).
Set Σ to a block diagonal matrix by aligning En and Σ, along the diagonal of Σ;
(2") and the variance estimator 72 = U 52 T.. Step 3. Bootstrap test statistic.
Set f = (2'-'
U.
For b = to B:
Generate ( ~ N(0, 14,): S, - S, + 1/2 (0) 23 = 1-111---11 So:
Set 2 to be the upper {a(t) - | (00//B/// /1 /T1 percentile of { [ bEE..
Update I and f2 as I (b E I % =}
Step 4. Reject or not?
Reject the null if VTăō
1 2, Algorithm 1: The testing procedure
A MORE ON THE ALGORITHM
A pseudo algorithm summarizing our procedure is given in Algorithm I notations. The matrix 2t() is defined by
We next introduce some
itt)
-
1 [-1
Σ
)
)
(3)
t j=0
where εno and E are the temporal difference errors defined in Algorithm !
B EXTENSIONS
B. EXTENSIONS TO DYNAMIC POLICIES
In this paper, we focus on comparing the long-term treatment effects between two nondynamic poli- cies. The proposed method can be easily extended to handle dynamic policies as well. Specifically, consider two tame-homogeneou policies क, and 22 where each (s( measures the treatment as- signment probability Pr(A, = S s). Note that the integrated value difference function can be represented by
J. -V(g)))) (TT2i (itidd))=(((((0m)::))))) [[(Q(m1;.s))) /1000//00000000/1111111111000000 -(Q(Tz; - Q(T2; 1() T2))) + (, (,
The Q-estimators can be similarly computed via temporal difference learning. More specifically, for given policy let
Σ E(S), A(S),AA)), ( (.
a)( = = (Ts)S_,1(H)
(4)
t<L
12

---

Under review as a conference paper at ICLR 2021
0.08
09
Raject hrbihill
0.08
Markor
0.27
02-
61
0.0
0.02
300
373
400
525
000
300
373
450
525
600
Diservaiion Timeo
Obuervation Timeo
Obsorvation Times
Otoorvation Times
(a) The proposed test under H1 (left) and Ho (right)
(b) DRL-based under Hi (left) and Ho (right)
Figure 3: Empirical rejection probabilities of and the DRL-based test.
be the Q-estimator given the data ((S). where (t(() -- EE Ej where E, defined by
V (1 --I (5,)) (S)+1) (S,
- -)
V -
We can plug-in in the Q-estimator in equation 4 to estimate The corresponding variance estimator and the resulting test statistic can be similarly derived. A bootstrap procedure can be similarly developed as in Section 4.3 for sequential testing. We omit the details for brevity.
B.2 EXTENSIONS TO OTHER NONPARAMETRIC ESTIMATORS
In addition to temporal difference learning, other existing OPE methods could be potentially coupled with the proposed bootstrap procedure for online sequential testing. We use the double reinforce- ment learning method (DRL,, Kallus & Uehara
2019) as an example.
First, remark that DRL requires the system be ergodic and weighted method to construct the value estimator. As such, it might not be applicable to the allernating-tim--nteeee interval design and the adaptive design.
inverse propensity-scone
Second, in the Markov design, it could be coupled with our bootstrap procedure for sequential testing. We compare such a procedure with our proposed method using the simulation setting in Section[3.]] and report the rejection probabilities in Figure 3 It can be seen that DRL-based test has some inflated type-I errors under Ho and is less powerful than our procedure under H1.
We next outline the procedure. Specifically, at the kth interim stage, we compute the test statistic
Tk-1
Z = VTrōn
1
Σ
1/
T
where
whe -100(1;1,))-0 (c(0,,,,)) -0001,,,)--((00..11111
At (1; (1;1,, S.)
+7 ((S)))
1 A,
Wy (0; S: + (0,0,,, A0,
1 1 b(S))
Q and W denote the estimated Q- and marginal density ratio functions based on the data collected at the ktth stage, and
Th - + -Tr-
Tk
The bootstrapped sample can be constructed as
z VT 1 Gx-1 TT To.
Then similar to Algorithm [ we can decide whether to reject Ho or not based on the test statistic Zu and the bootstrap samples. This algorithm can be implemented online provided that Q and & can be computed online.
13

---

Under review as a conference paper at ICLR 2021
C MORE ON THE WILD BOOTSTRAP ALGORITHM
We first provide an example to show that our test statistics do not have the canonical joint distribu- tion. This motivates propose wild bootstrap algorithm. We next present some details on the bootstrap algorithm.
Let {Zx}a be the sequence of test statistics conducted at each interim stage. These statisties said to have canonical joint distribution with information levels {Zx Js for the parameter if:
(i) Z2..... xx)]
T asymptotically normal,
(ii EZ₁ = = + o(1),
(iii) Cov (Z. Zkg) VIn, Ikg + o(1)
See also Equation (3.1) in Jennison & Turnbull 1999).
Unlike the settings where observations are independent across time, (iii) is likely be violated in our setup when adaptive design used. This is due to the existence of carryover effects in time. Specifically, when treatment effects are adaptively generated, the behavior policy at difference stages are likely to vary. Due to the carryover effects in time, the state vectors at difference stages have different distribution functions.
According to Part 3 of the proof of Theorem
3 we have for any l S 22 that
The
Cov Zkz)) = V The
x U
+o(1).
92
The matrices (kk and (kk depend the distributions of state vectors and are likely to differ for different Consequently, the second term k2, on the right-hand-side depends on both kı and kg. As such, (iii) is violated.
The idea of our bootstrap algorithm is to generate bootstrap samples { (2MB(L) that have asymptot- ically the same joint distribution as (vtā- (t)(F() - h- Specifically, let {Geheso be a sequence of i.i.d. random variables independent of the observed data. Define
( }
BMB (1) (1)==-1- --)(())
Σ
E(S,, A, JCL
Eg,0 ES11
(5)
where Gr the temporal difference error defined Algorithm the bootstrap sample MMB (t) = V MM (t).
Based on GMB (t), one can define
We remark that although the wild bootstrap method is developed under the i.i.d. settings, it is valid under our setup as well. This is due to that under CMIA, (tt) 3 forms a martingale sequence with respect to the filtration {(S,, A,, Yý) j < t). This guarantees that the covariance matrices of @MB (t) and (t)) are asymptotically equivalent. As such, the bootstrap approximation valid.
However, calculating 3MB(Ti) requires O(Ts) operations. The time complexity of the resulting bootstrap algorithm O(BT;) up to the k-th interim stage, where B is the total number of bootstrap samples. This can be time consuming when {TA Tk-1 K
1==1 k are large.
D MORE ON THE DESIGNS
In D3, we require ((k) to be strictly bounded between 0 and 1. Suppose an e-greedy policy is used, i.e. (s) = c/2 + (1 e)²(k) (s), where ?(k) denotes some estimated optimal policy. It follows
that c/2 & (s) < c/2 for any s. Such a requirement is automatically satisfied.
For any behaviour policy 5 in DI-D3, define (b,-)) and Y; (6.) the potential outcomes at time t. where b, denotes the action history assigned according to b. When b a random policy in DI or D3,, definitions of these potential outcomes more complicated than those under
14

---

Under review as a conference paper at ICLR 2021
deterministic policy (see Luckett al. 2019). When b is stationary policy, it follows from MA that 1 h2) forms a hume-homogeneous Markov chain. When b follows the alternating- time-interval design, both (524 and (S2:41 (b2)))2 form time-homogeneous Markov
chains.
We next show that (Z,, Zx) is asymptotically multivariate normal and provide a consistent covariance estimator.
Theorem (Limiting distributions) Assume CI-C3 hold. Assume all immediate rewards are uni- formly bounded variables. the density function of Su is uniformly bounded S and q satisfies
q o TT/ log T). Then under either D1, D2 or D3, we have
iZkiS are jointly asymptotically normal;
their asymptotic means are non non-positive under Ho;
their covariance matrix can be consistently estimated by some _, whose (K1, k2)- element Eki,k equals VTn, (T U E - (TT))((TT)) (U))))TU/((UU) (TT)))
E TECHNICAL CONDITIONS
To simplify the presentation, we assume all state variables are continuous. The immediate reward and the density function of Sg are bounded.
E.I CONDITION CI
CI Suppose (i) holds. Assume (ii) holds under DI, (iii) holds under D2 and (ii), (iv) hold under D3.
(i) The transition kernel is absolutely continuous and satisfies P(ds; a, a, = p(s; a, s')ds for some transition density function In addition, assume is uniformly bounded away from 0 and co. (ii) The Markov chain {S; (b, )220 formed under the behaviour policy ((0) is geometrically er- godic, i.e. there exists some function M on S, some constant 0 density function such that Sres M (s)s(dss) < too and
I < and some probability
(r() E S/S0 s) II(S)
- M(s)p', AA 0, S SESSSS
where || ||zv denotes the total variation norm.
(iii) The Markov chains {Sy, (b2))e Je20 and {S (b2+1) 1220 are geometrically ergodic.
(iv) For any h 1, K 1, the following events occur with probability tending to 1: the Markov
chain { (8( h220 is geometrically ergodic; sup.es (b(()(s) 6* (s)l & for some b* (-); the stationary distribution of {St (5,")) will converge to some IT total variation.
Remark: By Cl(i)) IT the stationary distribution of (5t (1,2 follows that II(S)
Σ
P(S: a, sabb + (1 a)6 (s))))
(0(1)
for any S C S. By CI(i,, we obtain
ITS) Σ
la(1 [a(1-b(0ss) + +1 (s)p((s)) (d)
a0(0.1) J'ES
Σ
Jaft - ((0) (s)) + (1 - ()) (s)lp(s';a, (ds) ds'
(6)
JES (E(0,))
SEB
m(*')
This implies that ua()) is the density function of II. Since p is uniformly bounded away from 0 and 00, so is ft.
Under Cl(iv), for any k {1, K 1), there exist some (())). (-), (.))(.) and (*) that satisfy Joes ( (s) (ds) < too and
Pr(St (6 E S|S, 8) - -S) S (S)
VI W20,,,,,,SC.
(7)
15

---

Under review as a conference paper at ICLR 2021
with probability tending to 1. Since b(R) is function of the observe data history, are M (.), (1))())
(+) and ((k).
Suppose e-greedy policy is used, i.e. (s) e/2 (1 c) (s) where ((k) denotes some estimated optimal policy. Then the condition su
& 0 requires 7(k) to converge. The total variation distance between the one-step transition kernel under T(()) and that under by can be bounded by sup (b(()) E|S 5) Pr(Si (b") E S|S. = a)1 S sup (s) (s)) sup p(s': a, 8), 8,
and converges to zero in probability. When the markov chain {S) (02-11 }220 is uniformly ergodic, it follows from Theorems 2 and 3 of Rabta & Aïssani 2018 that || 11 + 0 where II corresponds the stationary distribution of (57 satisfied.
The last condition in CI(iv) is thus
E.2 CONDITION C2
C2( Assume there exists some 3 such that
(Q(a'aa,)) V (s) 112-1
sup (o, ,E
(ii) Assume there exists some constant en 2 such that
(0))-1 Amin { SES
(() (s)))())) s Amax {s ((s) (s)dds sc,
(8)
and sup, (s) - O( ((V)).
(iii) Assume lim inf, Sses (ss)G(ds)]l > 0.
For any o, a' E 1). suppose Q(a'; 8) is p-smooth as a function of s (see e.g. Stone 1982 for the definition of p-smoothness). When tensor product B-splines wavelet basis functions (see Section 6 of Chen & Christensen 2015 for an overview of these bases) are used for V (-), we have
Remark:
((d';a,s) - V (s)88 = olg-0((/)))) -P/)),
sup (0.1)_8))
under certain mild conditions. See Section 2.2 of Huang 1998) for details. It follows that Condition C2(i) automatically holds when the number of basis functions satisfies q > (dd(2p),
Condition C2(ii) is satisfied when tensor product B-splines or wavelet basis used. For B-spline basis, the assertion in equation 8 follows from the arguments used in the proof of Theorem 3.3, Burman & Chen 1989). For wavelet basis, the assertion in equation 8 follows from the arguments used in the proof of Theorem 5.1, Chen & Christensen (2015). For both bases, the number of nonzero elements in (T()) is bounded by some constant. Moreover, each basis function is uniformly bounded by (Vvi). The condition sup, [s)]2 O(vi) thus holds.
Condition C2(ii) automatically holds for tensor product B-splines basis. Notice that 1 TT(ss) = q for any E S where 1 denotes a vector of ones. It follows from Cauchy-Schwarz inequality that
V
(ss)G(ds)
> 1/ee
1 1T (s)
= Vq.
2
C2(ii) is thus satisfied.
E.3 CONDITION C3
Let s"'s"" = (o) +(Q'') a
C3 Assume inf, inf (E(00)). where
se and sup, supaela..)) <
(0, (1,a)]So = te
(c s) = Varr(= a) = s) Var(=* (I, a)SS -= = =)
Here, Pe corresponds to the partial correlation of ex s0(0 a) and ex *1,,a) given So-
16

---

Under review as a conference paper at ICLR 2021
F TECHNICAL PROOFS
F.1 PROOF OF LEMMA T
To prove Lemma 1 state the following lemma.
Lemma Under MA and CMIA, a(a';a,s) r(a,s) + r s')(''' a) for any (s.
Proof of Lemma 2 For any a, a' (0. 1), define the potential outcome Y, a) and (a', a) as the reward and state variables that would occur at time & had the agent assigned Treatment at the initial time point and Treatment a' afterwards.
Let Pa (a, a, 8) = Pr[S5 a) E S s} for any & C S, a, E 1.. E and > 0. We break the proof into two parts. In Part 1, we show Lemma holds when the following is satisfied:
Pr( e ()) 8, So) (S,
In Part2, show equation equationOholds.
Part I: Under CMIA, we have
= (d) =s} =) ad) a),5, = S) =
(d)
(10)
(4)) = s}.
It follows that
Q(d':a,s) Σ
= s).
(11)
Similar to equation 10
we can show
(d' 8) E(r (l
(dd (d.. 8) Su = =s]
and hence
Σ E''B(V2idd = = Σ E(r( a)), (a', (la',))) a))) (1), 120
120
the conditional distribution of S (a', a) given St s and S. are the same as the conditional distribution of Sa' a) given So 8. It follows that from equation 11 that
By equation 9
(dE s) =
s).
This together with the definition of Q function and CMIA yields
Q(d':a, r(a,s) +
Σ
EE(Y (d', s) + ((((d =). (12)
100
Under MA, we have
J ad; s')(d':
Combining this together with equation yields the desired result.
Part 2: We use induction to prove equation When & = 0, it trivially holds.
Suppose equation 9 holds for = In the following, we show equation holds for k + Under MA, we have
Pr[Sp E (a) s, S.) ((Pr(St E3S (al, (d',),)
8, s 8, S.
E[P(S: d', St (ud =s
17

---

Under review as a conference paper at ICLR 2021
Since have shown equation holds for t k. it follows that
e)) 8, So} ff S'EB
P(
Similarly, we can show
p (S,d's) = Pr(Si+ Pr((i (d', E S =3 /.es (dP
The proof is hence completed.
Proof of Lemmal 7 By CA, is equivalent to show
E[Q(d'; A,, S; (A+-1)) YJ" (At) - (4))
=0.
Let So denote the support of Su- For any so So. it suffices show
E[QQ(a;; Ac, (A,,))) (7 (A.) - :Q(a'; (4 = oo} = 0.
This is equivalent to show
[[Q(a'; Ar, S7, 1)) Y( (4410
ao))|So sol 0,
for any so Sp. 00 {0.1}.
Let Ao(so) {a E {0,1} Pr(Ao = also = =s > 0}. It suffices to show for any so E So, E
Ao(so).
E[Q(d': A.. St (A,-1)) - - 1Q(d'd' (1cc::......(4))4444444441111101
on) So =os = 0,
or equivalently,
E(Q(d': A,, S7 - (A,) - 7Q(''a'' St+1 5
so, Ao = oo) = 0. (13)
Let 8j = (80. 8..... ,,)) Dj
(vo, ..)) S; S.. and 8,
(Y, Y,, ... Ty) We can recursively define the sets () a. ;)-1), S āg. Fj),
a,, to be the supports of S,+1, Aj+1 conditional on (S₁ ر,, A, = āj. Y,-1 1j-1), (Sj = 8j. A, aj. Y, ūj). (5j+1 = 85t1, = a, = 7j) respectively, for j 2 0.
Similar to equation 13 suffices to show
E(Q(d': A., (Ar-))) - (A,) - Q(a''a', St+ (()))(A,, St ())1))) = 8c. A = āU Y-- = Th-13 = 0,
for any so So. E Ao(su), E Vo(so. on), ..)..... E S, a. E1 1),
As,s, 4-1. 1) E[Q(a': az St (a+-1)) Y," (ax) - 'Q(a':'', a' (ā.) S, = $, A = ãe, Y-- = 3. 0. (14)
This is equivalent to show
By construction, we have Pr(A, a, SS, 3, 8,- It-11 A, ã,- 1) 0. Under SRA, the left-hand-side (LHS) of equation 14 equals
E[Q(a'; de, (). (ā.) - QQ'''a'' Si+1 (a:)) 3z A|-1 dc-1, Yr- Dt-1) (15)
Notice that the conditioning event is the same as 1S (0r-1) St, Yi- (0t-1) 1/-11 -1
A, A 2,-1, Ø.-2). Under SRA, equation 15 equals
B{Q(a': a, (ot-1)) - YY, Q(a':a', (t) (ā.-1) = St, Y,- (ūg-1) -/-11
S 3,-1, A = a.-2, Y--2 = T1-
By recuisvely applying SRA, we can show the left-hand-side of equation 14 equals
E[Q(a': (ā.-1)) - (ā.) QQ(''a'' (4.)) = s, hsss (V)(a)) = Vj vihssge-)
This is equal to zero by MA, CMIA and Lemma 2 The proof is hence completed.
18

---

Under review as a conference paper at ICLR 2021
F.2 PROOF OF THEOREM 3
F.2.1 PROOF UNDER DI
We begin by providing an outline of the proof. The proof is divided into three steps. In the first step, show for any Ti S < Tk. the estimator (it)) satisfies the following linear representation,
)
Σ
E E5Ey1
+0p(1-2/2))
(16)
(()))
where Ett) (t) and Ej,a Y, + +Q a, SJ+1) representation, in the second step, we show the asymptotic normality of F(t). Specifically, we show
Q(a; S,) for = 0. Based on this
vi(f(() mo. $ 10,,1)
a(t)
In the last step, we prove Theorem
Part I: By definition, we have
@(t) - 3 = -1)
) Ett } -8--(()
1-1
{
53Y,
)
Egy,
j=0
j=0
}
(1)
Σ
E VT (T())) +7V (8
E,t,, T (T(S)) +/ (S)+))8811
where the last equality is due to the definition of Σj. Let
Ta = V T (S,))2.A. 7 (S)+1) Q(a; A,, S,) + +Qa(; Sz+1).
follows that
}}
((1) -1)--8----1
55E EyEya
1-1(1) }
1
ESTJ, EgTJa
t ==
and hence
)
1 ス
3(1) - -0-
-0--
1=0
(2(1)
-
1
Σ
EST,,0
7
EsT3.1
==u
(a(
We first consider (1)). It can be upper bounded by
)
1 1-1
Σ -0'(2
Σ
= 1 -1)(l) max sup
T
t Σ Egras
a'
(0 ||l|==1
2
1=0
1 t-1
1-1 t-1
< Σ 1-1(1)]2 max sup
Σ j=0
(a (, 2r,
S max Ira.] a.j
Σ -t)(()
Amax
Σ E3E] )
oE (E(1,1) ||a]|==
1=
19

---

Under review as a conference paper at ICLR 2021
where the second follows from Sauchy-Schwart inequality. Under Condition C2(i), we have for any j s 1 S Th, max; |raj] =o o(t=1/2). Suppose for now, we have shown
1 i 1=0
Σ (1)ll2 Op(1) and Amax
+
[5]
Op(1).
(17)
It follows that
(x(t) (t-111))
(18)
To bound (2))), notice that for any {0, 1}.
E
Σ 1=
S
Σ
BCJ
EJ9 + & 21312
Σ
ECJ Stz E f
1=
Similar to Lemma
we can show for any (-)) that is function of A,, St. Y that
B[Q(a'; As, Y, (a' of S S411))((S,, A,, Y,-1) 0.
(19)
This implies that BC EJz e hna 0 for any J1 j2- It follows that
t-1 3,
[-1 EC
E
REJ G5 S qmmax
Σ
1=
Since all immediate rewards are uniformly bounded, so is the Q function. As a result, | are uniformly bounded. Suppose for now, we have shown
1 6-1
Amax
t 5=0
Σ
EEJE]
O(1)
(20)
follows that E||(-|
E5= Es E O(g) and hence
Σ
1-1
E5E300 ) Op((-1/22/)) E5
0=0
Suppose
(1- - E -1)(2) 1/2).
(21)
It follows that
) = =0p(t-1/2)
(1)())) <
15-1 - (1)l -
1 Σ
Eje500 &Æj
This together with equation 18
yields equation 16
It remains to show equation Lemma
equation 20 and equation 21 hold. We summarize these results in
Lemma' Under the given conditions, we have equation 17 equation 20 and equation 21 hold.
20
Part 2: By definition, we have F(() - T = UT (ā(1) - 33) + +UT B - Tp. Define
Gεj00
)
5500 &
(t(t) E
Geg,1
1=
20

---

Under review as a conference paper at ICLR 2021
The asymptotic variance of vi(F(t) -u) is given begin by providing a lower bound for (t). Notice that
We
(t) 2 Amin (2()))UTT Σ- (t) 2 Amin (S((t)
(2-10---0000101 (22)
Under Cl(ii), we have lim inf, | 0.
In addition, notice that Σ (t))" (8) is positive semi-definite. It follows that Amin Σ (t) (t))
1/Xmax [
({)))
Using similar arguments in showing
2 2,2 (0)ll2 = O(1) in the proof of Lemma we can show sup/21 [E(t)]la = O(1) and hence
(0)+
suP/21
Amax (t) (E({)) = O(1). This further yields
inf Amin E ())-)))))))) 0.
(23)
Suppose ltt satisfies
lim inf Amin (S(t)} 0.
(24)
It follows that (f) is bounded away from zero, for sufficiently large t. Under Condition C2(i),
have UT B - = o(Tx" 1/2] o((-1/2). It follows that
(f(((t) To} Viu (B(t) - 3 VilU B To) (t)
To) (tt)
VIU (δ(t) (3) + o()).
ott)
(t)
Moreover, it follows from equation 22 equation 23 and equation 24 that ((t)/|Ull is uniformly bounded away from zero, for sufficiently large t. Combining this together with equation [6 yields
Vt(F(t) - To}
VIU (i(t) ViUTRe Rs
(i(t)
(1)
o())
o(1)
where the remainder term satisfies | = (/-2) follows that the second term on the right-
hand-side (RHS) of the above expression is bounded from above by \i]lB((lallUlbbb(((( = (1) and hence
Vi(F(1)- -o) (t)
(1(T((1))
a(t) + (1)
(25)
Similar to the proof of Lemma we can show for any j 2 0, a E {0,1}.
By the definition of (t),,, E(Ey=)al(S A,, Yike)) = 0.
forms a martingle with respect to the filtration ((S), A,, Y,),), ie. the o-algebra generated by AS, Yjbe By the martingale central limit theorem, we can show VUU (t) 4 (0, 1) (see Lemma 4 for details).
To complete the proof of Part 2, need to show equation 24 holds and that @(t)/o(t) 4 1.
The assertion (t)) 5 can be similarly proven using arguments from Step 3 of the proof of Theorem 1, Shi et al. (2000a). We show the asymptotic normality of VIUT (t)/ao() and that equation 24 holds the following lemma.
Lemma Under the given conditions, we have equation 24 holds and that ViuT (1(t//(()) $ (0.
Part 3: Results in Part 2 yield that (T((f(Tk- To)/o(TT) 4 N 1) for each 1 < S K. In addition, for any K K-dimensiioal vector a = (a1,"..,,.) follows from equation 25 that
K ax (T(TT) - To) K a VAVTTU ((T))) + O,). ((T.)
a (Th))
The leading term on the RHS can be rewritten as a weighted sum of {EjE E Josjer. Sim- ilar the proof in Part 2, can show it forms martingale with respect to the filtration
21

---

Under review as a conference paper at ICLR 2021
o(S), Ay, (,)e))) We now derive its asymptotic normality for any using the martingale central limit theorem for triangular arrays.
By Corollary 2 of McLeish 1974), need to verify the following two conditions:
(a) maxosjet Σ "x 1/2 T - a... (oo
< <Ta) & 0;
(b) D Σ Tx 1/2 U (T:((E S.. 5J (a) (o(T))))) < Tx)l converges to some constant in probability.
Since K is fixed, to verify (a), it suffices show
1-11/210 T Σ (TT)(E 8,00 Ej es,)) (o.))(((TT)) S
max ISJELISKCK
TK
In Lemma we have shown |Σ (t)ll O(1). In Part and Part 2 of the proof, have shown
|sy.a 's are uniformly bounded and that (t)/llUU is bounded away from zero. Therefore, it suffices
to show 7/2 maxosi<t IKS 3 Under Condition C2(ii), we have sup, (s) (g2 and hence maxugj<t 15yl|2 = Ogg The assertion thus follows by noting that T1 = 7 and
q o(T).
Using similar arguments in Step of the proof of Shi et al. (202aa), we can show
[EJ e,,, EJ Ex1) TE)] 53o E) s,,) 22(t)
4 0,
(26)
.=0
as f + co. This together with the facts (1)(()) = 0(1) and (t)/||UUl is bounded away from zero implies that
Tey ATz
akgy akg Thy o Aha.)
Σ j=0
U (Th)
S.0. S.00 (5e))) (E] e,,0 E] (x))) TU
ak, ako (Tk, A Tkx)
UT (TH, ([w))=
The Tke 0² (Tk, Tka)
Th, ATx2
S 0² (Tx, A Tx.)
Ok, 0kk
U max || Σ (Tx)
Σ
(T] (5TT,,,,5]T5,.) [5,1) 22)
The A Tkz
5=0
E 0,
where a A b = min(a, b). It follows that
Σ
T 1/2 1/2 T (TWW(E E..0. Eo))) <[])
(27)
ake akg (Th, Th2)
U E (TT, A (E TU = (1)
The The o² (Th, A Tka)
In the proofs of Lemmas 3 and 4 show that Σ - 1100))-122=
and ||
(2 O(2- for some matrices (0)+ and 0) that invariant to t. Definitions of
these two matrices can be found in Sections F5 and F.6 Under C2(ii) and the condition that g
of o(vT/ log T), can show ||U|| O(g /2) and hence o²( 2 (0))) where (0)))
U ( (000)))11220 11)(0) (()()))) -11 U. Similar equation 27
we have
asy akg (Th, Thp)
M (Tk, ) A (E
(28)
k k Tha (Tk,, A Tha))
P
aky akg (Tk, A Tx2)
Oky Olg (CR, A Cka)
U
Te, Th (0())))
Ck, Cka
k1
22

---

Under review as a conference paper at ICLR 2021
where 's are defined in Section 4.4 This together with equation 27 yields that
T 1/2 TTTT
- (Tx)(E) ego, e5,1) ( (o(T)))~H1 < Ts) 4
ake ahe (Ck, A ck2)
/Cky Ck2
j=0 k=1
Conditions (a) and (b) are thus verified. By Lemma we can show
K
ak (T(T)
To}
K
ak (TVTT To) + op(),,
(Tx))
((Ti)
for any (a1, ax) This yields the joint asymptotic normality of our test statistics.
By equation 28 its covariance matrix is given by Eo whose k24, entry is equal to
(Ck, Cka) 1/2 1/2 ck. Cke Using similar arguments in proving equation 27 equation 28 and Step
of the proof in Theorem 1, Shi et al. (2020a), we can show a consistent estimator for Ep. This completes the proof of Theorem under DI.
F.2.2 PROOF UNDER D2
The proof is very similar to that under DI. Suppose show equation 17 equation 20 equa- tion 21 and equation 24 hold. Then similar to the proof under D1, we have
A(f(t)- -o) VEU (t))
op()).
(t)
o(t)
The following lemma shows these assertions hold under D2 well.
Lemma Under the given conditions, we have equation 17 equation
20 equation 27 and equa-
tion 24 hold.
It follows that for any K K-dimensional vector (a1,," ,ax)
a V (T(T(((T) - To}
Σ on VNTTUU (TT)) +Op(1).
(Tx))
o(Ta)
In the proof of Lemma 5 show ||{E(t) - 0(1), [E()) - E" l2 (12) for some
lime-invariant matrix Σ that satisfies |E*) 0(1). . follows that
(KE -("))~1-("")1111 ||( (E(t) - --) (E)
Σ" "|a""""""""" 0
Similarly, we can show [tt(tt 12" 10(t-1//) for some matrix 02'
In addition, using similar arguments in the proof of Lemma 5 we can show equation 26 holds under D2 as well. Now, the joint asymptotic normality of our test statistics follow using arguments from Part of the proof under D1. Similarly, we can show S is consistent. This completes the proof under D2.
F.2.3 PROOF UNDER D3
The proof under DI indicates that equation 17 equation 20 equation 21 and equation 24 hold with t = Ti. It follows that
(F -
(TTUT((TT)) o(Ti) + (1)
(29)
(Tr)
The rest of the proof is divided into two parts. In the first part, we show for k 2...., .,
(TT(F(T)) -
To.
VTU (Tx)
+ (1),
(30)
o² (Ti))
o² (Tk)
23

---

Under review as a conference paper at ICLR 2021
for some Çi (T&) and o² (Tis) defined below. In the second part, we show the assertion in Theorem holds under D3.
Part 1: For any S k K, consider the matrices
T
T--1
(k)
Σ
E|E,|((S,, YJ) toster and 5(k) 1
Σ
Σj
Ta T Tx-1
TB T j=
Tk-1
We show in Lemma beloow that for io = -,,... K,
|Σ (()) 1| 0pl9 1112),
(31)
and
} - = O,(1).
(32)
where Σ (k) = -T=
Lemma 6 Under the given conditions, we have equation 31 and equation 32 hold.
Notice that (T: 1 Ti-i)/T + (c: C- //er and H Σ (a: --)) Op(1)
where Co = 0. follows from equation 31 that l Eim (ci - 12
and hence
(T. (T-))
= =0p
Ak- 2.... K.
Similar to the proof under DI, we can show
{
h Σ (T. - (0))
= (1) and
Σ ( - (T-1)
1 (K)
= 1p(a 1/2))
Th 1=1
Th
for 2, K. Thus, equation 21 and the first assertion in equation hold with t T2, Ts, , under D3.
In addition, similar to Lemma 6
show
T--1
Amax
Σ
.]
Op((),
(33)
Tk
T
T=Th
and
Th
(5E] E[E,E]] (S.,, AG, Yi) .1)
= =0p(0-113)
Tk Tk j=
12
for k = 2, K. This yields [I(T;: - Tk-1) Tx-1 j
EGE] 112 =0p(1) As result, the second
assertion in equation 17 holds with t T2, T3.
Tk.
Moreover, using similar arguments in showing t - [S] E e, (J (TTT)TTTT--T)..(()))))) = Op(t v un-
der DI, we have by equation 33 that (TA Tk-1) D (E) Ey.0 [T,), Op((T: Th 11/2 1/2 /q). for k 1,... K. Under the given conditions (Te)a, obtain
1 EH (,,0. (To.ETea))"" = (,(1-1/2 /q) for 1. = T2, T3. ... T
Based on these results, using similar arguments Part of the proof under DI, we can show
VT((((T)) B = = VTssi(TT + (1),,, Vk E (2..... K},
(34)
where
1 Σ
(Tt)
Σ
Th
E
24

---

Under review as a conference paper at ICLR 2021
For < k K, define
Tk
(2(h)
Ells E0o, Ex EJ e5,1) (c) Es,o E,a))((S, An, Yi) JostsTtii
Tk T Tx-
j=Tb
and 57 (h(h)
Ei= (Ti - Ti 1)-1) For any - h: v K, we have Amin 2
Amin Amin (isii.)) Since T + Ck x > and Amin (22 = Amin (SI(Ti) is bounded
away from zero, Amin (5T is bounded away from zero for k 2, ... K
K as well. Define
(T=())))² U (T 'n
(K)
U.
be shown that o² (TTs |||)/ bounded away from zero, for 2. K. Using similar arguments in Part of the proof under DI, we can show equation 30 holds. This completes the proof for Part 1.
Part 2: Let (Ti) = (Ti). By equation 29 and equation 30 we have for any K K-dimensional
vector a (01, .. .ak) that
K
Ox (T(T) - To}
K
On DAVII AAVTUU (T&)))
Σ
+ o1))
(35)
(Tk)
(Tx)
In the following, show the leading term on the RHS of equation 35 is asymptotically normal. Similar to the proof under D1, it suffices to verify the following conditions:
(a) maxpsieT EK T 1/2 U -- S, E] (,2) 1(j Thl 0: (b) D EK T.T, U (5(h) (EJ Ej To (Tx( < Tx)l converges to
some constant in probability.
Condition (a) can be proven in similar manner as in Part 3 of the proof under DI. Notice that for k = 2, ... K, {A,,, n2 (8) and o (Ti) are random variables and depend on the observed data history. In the proof of Lemma we show ( (5()))-
(Σ**)-1l2 Op for some
,.),, Similarly, we can show || (k) -2" 1|2 = 1/2)
deterministic matrix E" and all k E (2, ... K). (T-1)/ and (TT)) (o**)?ll2 = (T-122) for some E', o and all t E (2, .. K). Moreover, using similar arguments in the proof of Lemma 6 we can show
Tx-1 Σ
)
)
(2)
Vk ... K. =
Th Tx-1
This further implies that
T--1 Σ Tb 2=0
Ejeú E
( (
E5eū,0 Ejey,1
)²
2 = 0p -1/2),
2,
Based on these results, using similar arguments in Part 3 of the proof of Lemma we obtain (b).
The joint asymptotic normality of (TT(F(T)) - -o0/oo / (Ti), (FT((( T ////a/(22/ (Tk) ( thus follows.
Consistency of = can be similarly proven. We omit the details for brevity.
F.3 PROOF OF THEOREM
As discussed Section 4.3 [Zi, Zz.... .... ,T jointly normal with mean zero and covariance
matrix E. conditional on the observed data. By Theorem I, have _ P = where E, is the asymptotic covariance matrix of (Z,, Zz. .... Zx)T. Let a (t)() (x(TT) for any 0 < S 1, we have (Tx)) + a" (cx) for any < k < K. Notice that (be) is continuous function of S
25

---

Under review as a conference paper at ICLR 2021
and {a((Tk HIRSK, it follows that by & 6y,o for 1 $ & K, where (bu,0]ISASK are recursively
defined as follows:
Pr
max (Z5.0 - 05,0) - 0, Zx,0 > bu, a² (cx) a² (cR-1), ISick
where (Z1.0, Z2 ... [x,0) asymptotically normal with mean zero and covariance matrix S
Theorem
immlies that (21 1 (T Z2 V225o/O(T2), .M. Zx (TxTo/O(TK)) 4
1Z Z2 xx,0) It follows that
h
Pr -UIZ--TT,o0B0 U
+ Ú1220 > b20t = = (36)
Ulzz>bj)
b/) - Pr
0,1
Pr
j=1
The proof is hence completed by noting that (TTs) + a (cx). When 0, we have EZn = o(1). The rejection probability thus converges the nominal level.
F.4 PROOF OF THEOREM
Suppose To = T for some h > 0. Based on the proof of Theorem 3 we can show ((T.) 5 o
for some of > 0. It follows from equation 36 that
Pr Uiz, > b,1 Pr (ÜIZ)-VTTuin VTTT/O((T) b, -h/O(TT)
112,0>>0000 63.0
+
- Pr
b1,0 h/03} (cx)))
j=l
The second assertion in Theorem thus holds by noting that a<Ti)s + (cx).
Let + co, we obtain
Pr Ú125> Pr Ü0
-,,00 - n//33/ + +o(1) +1. 1.
The proof is hence completed.
F.5 PROOF OF LEMMA 3
Under the given conditions in C1(i,, Ci and C2(ii,, equation 20 and the second assertion in equation 17 can be proven using similar arguments the proof of Lemma E.2 and E.3 of et al.) 2020a). We omit the proof for brevity.
remains to show equation 21 and the first assertion equation 17 hold. Recall that j is the density function of the stationary distribution II (see the remark below Condition C1). In addition, is uniformly bounded away from 0 and oo under Cl(i). For a' E (0, 1}. define the matrix
> (aa) =
Σ ((s,a)(E(s,a) 7E(s', ((){))))))(s)((( - (s) a(1 - 100 (s)))p('' s)ddd'''' eE(0.1)
Define
(0)
x1) ]
0)))
The matrix (0)) is the population limit of (() under DI. To prove the first assertion in equation
17
we first show
[ (0000))) O())
(37)
26

---

Under review as a conference paper at ICLR 2021
By definition, this is equivalent to show
|E 10 (a) 112 = O(1),
for a E {0, 17. The matrix (0))((0) can be written as
(0) = Σ (0) (0)
Σ 00 (0) 2, (0)
(0)
where
E1, (0) J.
- [v
s)dsds',
2g1 (0) -7 JSNEES V() CONT((81) (6) (s)) s)dads',
Σ2 (0) = / V( (s) (s)
It follows that
{ [0))) (0))-1
(0))
=
2,2 2,2 (0)) -200 |g,
(0)
(0)
(0)
(0) (0)) {E22 (0)
and hence
{ (0)
|E (0))=1)
sup
a
222 -
(0)
(0)
(0)
(0)
(0))-1
( (0)+ (0))
02
||o |=11||a2|||--
2,1
1,1
sup
|a [Σ (0) (0)) a1 |..|==1|||00
sup
|a (- (0))
(0)
01
[asl2==1, |./12=
lag 2 (1))0) (0)} - (0) (0) (0) (0)) 04
sup
[
< (1 (10) + 11 (0) (0))~ + || (0)+ (0))
20) 00
10) (0)
(0) (0))
Thus, to prove (0))) O(1), it suffices to show
|| (0) (0)) (0))) || (0) (0)) 0(1)
0(1)
(38)
(39)
| (0)1l2 O(1).
(40)
We first consider equation 38 et al. (2020a), it suffices to show
Using similar arguments in Part I of the proof of Lemma E.2, Shi
a (0) (0)a 2 E Va,
for some ē > 0. Under DI, ((0) is strictly positive. Since is strictly positive, it suffices to show
{
a
(s)) >V((s)) dsds' a 2 o2 2211a
Va.
(41)
s.S'E
for some 02 O. Notice that LHS equation 41 equal to
/
X(S)
(a T (()
(a v(s))aa (dd))ddods'
-
+EB
J
where X(3) is the Lebesgue measure S. Since $ is compact, we have A(S) < t00. By Cauchy- Schwarz inequality. LHS of equation 41 is greater than or equal to
A(3) / (a dss) A(S)
/
[a T (s)) X(3)
7 (a (vs')dds
SES
SES
2
WEB
2 (1 (1-7)A(3)
(a (v)
27

---

Under review as a conference paper at ICLR 2021
This is directly implied by Condition C2(ii.. The proof of equation 38 hence completed. Similarly, we can prove equation 39 In addition, notice that
a (s))laa ( (1 (s) sdsdds
sup
aa 2 |a 2=
s
a (a)) sddadd'. 3
sup
a
02
Since the density function 4 is uniformly bounded, we have 21 (O)lla S ((1)
|a v())laa) (ss'lddsds,
sup
||a|||==1,| a2 2= S.S
where ((1) denotes the universal constant. By Sauchy-Schwarz inequality, obtain
U ((s) (s)ds SEB
(0) 21 (0)l2 & ((1) sup la (s) ((1))
[el==1.ssE
In view of Ciiii,, we obtain equation 40
To summarize, have shown || (0)) 2 0(1) Similarly,
prove O()) Assertion equation 37 thus holds. Similar to Lemma E.5 of Shi
(1)-
et al. (2020a), can show [E( 100)=||2 Ot 1/2). (t-)) Using similar arguments in Part
of the proof of Lemma E.2. Shi et al. (2020a), this yields -t) (200)=)~112
11/)) and | (t)]l2 = O1). Under the given conditions, equation 21 and the first assertion in equation 17
now follow from the arguments used in Part and 3 of the proof of Lemma E.2, [Shi et al. (2020a).
F.6 PROOF OF LEMMA 4
The asymptotic normality of (i(((t) - /o/o/(t) can be proven using similar arguments in Part of the proof of Theorem 3 In the following, we focus on equation 24 Define the matrix
Σ
F
(
EnEo.o Eooo,1
)
E Eo
)
So 8, Ao a
u ((s)(a))))))) + (1 a)(1 (b(0)
+EB (0.1)
Similar to Lemma E.5 of Shi al. suffices to show inf, Amin
2020a
show [| s2(t)ll2 1/2). Thus, it
> O. Under CA and SRA, we have
E{
( E05u,1
fosu,o
)
Eoço. Eo
E
= s,
E (0,
) (
(o(a)e"(O,a)
)
So = A,
Cola)e (1,
(1,a))"(L,a)
=E
(o(a)s*(0,a) So(a)s
)
(o(a)s*(0,a) a)
) )
So
(o(a)s((1, (1,a)
For any 2g-dimensional vectors a1, a2 that satisfy ||a 11 + ||a ||
it follows that
(aT ([,aT)E
{
Euco.p
)
tooo,0
)
A,
(a (aT,aT)
Eoco.1
Eo0o.1
| (1, (1,a)) s]
+ 2aaE
2p 22ae
= (1 - [=1_0aaeeeeeer000011144441aa11a0
+ P= +=l.
> (1 -- (1, *).
28

---

Under review as a conference paper at ICLR 2021
where Pe
supysupees (e. Pe(a,
Under C3
we
have
Pe
1 and
inf, infa'a, a,s Bl(E"(dd (a', a))3(s s) > It follows that
So s, Ao = (0) a2) 2 2d(faE(s, a)) (a){(s)))))) )
$05o,0 1
fooo,o E
(ai a E
for some constant > 0. Therefore,
Amin (S2 ())
inf ||a 11++llag 11t 11=1
(a a (aT ,a)) .T))T
z
03
inf
Σ E(s. + la ((s. ((s.,)) (1 a) bl0) (s))
|| 11
| 13
JEB
aff0,1)
The strict positivity of uu-) and the condition that (.) is uniformly bounded away from and yields
Amin (I2
2 E4
inf
Σ Hai a)) + { {(,
(42)
a
8
JEB (E
for constant é 0. With calculation, we can show the RHS of equation 42 is equal
{ V(S)
E4mmin
By Condition C2(ii), it is strictly positive. This yields inf, Amiu Amin (S2(0)))
Thus, we obtain
equation 24
F.7 PROOF OF LEMMA
We begin by proving
ΣΣ |00121 0(1)
(43)
under D2. For any matrices M1 and M2, denote by diag[ M, M2] the block diagonal matrix
M1
M2
By MA and Condition Ci(i),, the two Markov chains {S2-1he2) {Sulizu are geometrically er- godic. Let μn and #l denote the density function of their stationary distributions, respectively. Under CI()), we can similarly show that they are uniformly bounded away from 0 and co. Define
Σj
diag]E(s, 1){E(s, 1) - -E(s', 0)) TO.TT)......... EE(s, 1)E(ss 1) -5(5, 1)
Σ
diaglE 0){((s 7E(5', 0))
0) ()((,11) (p2()))))))))
The matrix
[ + Σ /2 corresponds the population limit of E(t). Similar Lemma E.5 2020a). we can show ||j (2t) Σラ E2 ott-1/2) and ||
of Shi et al.
(2t)
Σj= E2 112 o(t 1/2).. This further yields
Σ + Σ 2
I(1)
1/2
2
Similar to the proof of Lemma in order to show equation 43
it suffices to show
||E| + -12 0(1).
(44)
Notice that Σj + Σ3 = diag 20 (0) (0). [1)] where
Ex (a)a)= = J.
((((ss))))2(()))) ()))))()))((()))0) E(s, ()(((s)) 1) (s))))))))(())0( 1,)1 dads'.
dsdd
29

---

Under review as a conference paper at ICLR 2021
The matrix (0) can be further decomposed into
(0)
20 ( (0)
where
I JASES (Vs) - paasss)))s s)dsds',
(0)
()) -7 JNEES V(s) (s)))))))
(0) = / (s)
Similar to the proof of Lemma 3 we can show [[ (0)) = 0(1) |1 =
0(1) and (0)1l2 0(1) It follows that
[ (0)) 0(1). Similarly, we can show
- 12 (1)
(1). This proves equation 44 Thus, obtain equation 43
Using similar arguments in Part 2 of the proof Lemma E.2, Shi et al. (2020a), we can show Op 1/2 log t).
E/= Eg 1212 = (t-1// 1og t) and ||t- -E= Eaj+1 Eille
1/2
This further implies [E((t - (E; + Σ3)/211 = Op log t) and hence [t(t)= Ett)l =
(t-1/2 t) Combining these results together with equation 43 we can show equation 21 and the first assertion in equation [1nation[77holle hold. equation 20 and the second assertion in equation 17 hold can be proven in a similar manner.
Finally, using similar arguments in the proof of Lemma the details to save space.
show equation 24 holds. We omit
F.8 PROOF OF LEMMA 6
Under Civiv), we have equation holds. Similar to equation 7 we can show (T(k) has a probability density function (k) given by
(5')
Σ (E(1)))
(af1 - (x)) + (1 - (s)((sss
(45)
SES
For a' E (0, 1), define
(())((a)= 8, eE(0,1)
Σ - (s) (1- o)blk) (1-
;a s)dads'.
Condition on {(S}, Yihskr the matrix (a) is deterministic. Let (k) = (+) (0), (*)) (1)). Similar to the proof of Lemma
show - - o(1),
conditional on {[S), Aj, Yy)hs with probability tending to 1. This implies for any suffi- ciently small
Pr[ x 112 > A, 3o.
The above conditional probability bounded between 0 and Using bounded convergence theo- rem, we have
Pr[ (k(] (x) >) = =(1),
(46)
and hence (k)+ [()) (1).
Notice that sup, (b( - bO6 (s)] 3 0 and || - 11' P O. Define
(x))) = Σ ia(1 bz (s)) + (1 a)b² (s))((s';a
aE(0.1)
30

---

Under review as a conference paper at ICLR 2021
It follows that
-s)))
Σ
{alb"(s) - bb)))sssss))))))) +1- a1-a))b(ss) b (s) sI
a {0,1) SE8
Σ
laf1 - (0()) + (1 a)) (s)lp(s' s) (ds)),
ae ae(0,]] 2E6
and hence sup, (s) - 1 (s)l & 0. With some calculations, we can show [E(())(a)
(a)all & where
(a) / 3. (E(u,1)
Σ ((s,a)(E(ssd) -
a') (a(l ( (s) sdsdd'
Let E diag E (0), (1), we obtain |Σ
E' 2 = (1()). Combining this together with
equation 46 we obtain || |X(|] 12 = op(1) The proof of Lemma yields |Σ 100
(11). Thus, we have for any 2 < k S K that
Σ (k)
T TT -T--TTE- T T1) op.)
(47)
Similar to the proof of Lemma 3 we can show (x())'s are uniformly bounded away from 0 and cc.
It follows that 2² uniformly bounded away from and oc. Using similar arguments in Lemma 3
can show [| -TTT=TT,Y00
+T. (T Ti E-} ll O(1). Using similar arguments in Part
of the proof of Lemma E.2, Shi et al. (2020a). have by equation 47 that || (>=()))111 0(1).
with probability tending to 1. equutionn i2 thus proven.
Assertion equation 31 follows using similar arguments in Part 2 and Part of the proof of
Lemma E.2, Shi et al. (2020a).
G ADDITIONAL FIGURES
We present some additional figures to report the simulation results in this section. Figure depicts the empirical rejection probabilities of the modified version of the O'Brien & Fleming sequential test developed by Kharitonov et al. (2015). It can been seen that such a test has no power at all. In addition, we remark that Kharitonov for k = 2, ... K and is not directly applicable to our setting with unequal sample size. To apply such a test, we modify the decision time and set (Ti, T2, T3, T4, T5) = (120, 240,360, 480, 600).
(2015)'s 's test requires equal sample size Ti T₃ Tx-1
Figure 5 depicts the empirical rejection probabilities of our test and two-sample t-test with the error spending function given by 0r2. Figure the empirical rejection probabilities of our test with different combinations of the number of basis and the error spending function.
31

---

Under review as a conference paper at ICLR 2021
120
243
300
600
322
240
300
590
10
0.5
216
565-
0.03
04-
Cbveradoo
Oosoridton
03-
4-32
543
3.00
243
502
Figure 4: Empirical rejection probabilities of the modified version of the O'Brien & Fleming sequen- tial test developed by Kharitonov et al. (0115). The left panels depicts the empirical type-I error and the right panels depicts the empirical power. Settings correspond to the illemating-time-intee adaptive and Markov design, from top plots bottom plots.
0.5
Zed
0.5
0.0
5.00
1.0
Oiservation Times
Observation Tires
103
Obsonaaiion
400
100
(60
300
Observation
853
500
600
0.08
0.04
03
62
8.00
372
490
300
600
300
402
X0I
990
300
400
300
400
506
090
1.0
Obserration Tires
Observation Times
2x011
02
0.0
01
00
Observation Times
Observation Times
Observatin
Oisorvtion times
(a) The proposed under and Ho (from left plots to right plots)
(b) Two-sample t-test under Hi and Hn (from left plots to right plots)
Figure 5: Empirical rejection probabilities of our test and the two-sample t-test with a(-) az(-). Settings correspond to the allernating-iime-interwas time-interval, adaptive and Markov design, from top plots to bottom plots.
32

---

Under review as a conference paper at ICLR 2021
1.5
0.9
008
0.01
002
0.0
Ex330
Observation Times
Diservatio lires
03-
1.0
0.0
10
0.11
0.04
002
0.0
60
300
400
300
600
300
600
300
600
300
400
HIgh: Hignt-ee HEBLAA
0.3
800
042
0.52
0.33
02
60
Olservation Times
Diservaton 1ines
302
300
420
500
(a) The proposed test under Hi and Ho (from
(h) The proposed test under 1T and Ho (from
left plots right plots). a(-) (-).
left plots to right plots).
ox (<)
8 8
Tegett tepec//mbaattt
0.2
0.07
0.02
300
400
300
000
300
400
305
900
300
420
500
600
300
400
506
000
0.7
C.6
06
0.00
0.02
000
300
400
506
600
400
500
600
300
420
500
000
300
400
566
600
Time
Observation
Osservatio
055
0/0
010
0.00
400
500
600
500
300
450
500
600
Osservation
(c) The proposed test under Hi and Hg (from left plots to right plots). J = 5, an
(d) The proposed test under Hi and Ho (from left plots to right plots). = 5, ax.)) (x2())
Figure 6: Empirical rejection probabilities of our test. Settings correspond the alternating-time- interval, adaptive and Markov design, from top plots to bottom plots.
33


Reviews:
[{"review_id": "zzMqOBw0dc", "reviewer": "AnonReviewer4", "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": "*Summary*\n\nThis paper introduces a reinforcement learning framework for testing the difference in long-term treatment effects between treatment and control in online experiments. The proposed testing procedure allows for sequential monitoring and online update, has good control of the type I error rate at interim time points, and has non-negligible powers against local alternatives. Its performance is tested on both synthetic data sets and a real-world ride-sharing data set.\n\n*Assessment*\n\nI'm not too familiar with literature but slightly leaning towards acceptance since I find the subject somewhat interesting. But still I want more information regarding novelty to make the final decision. Also the technical proofs are quite long and unfortunately I do not have time to go through all of them.\n\n*Pros*\n\n- The problem considered in the paper seems relevant in practice.\n\n- The algorithm is generally clear and intuitive.\n\n- Empirical performance of the algorithm looks overall good.\n\n*Cons and Questions*\n\n- The proposed $\\hat{\\tau}(t)$ looks like the difference between two OPE estimators using direct method that requires $o(T^{-1/2})$ approximation accuracy. There are other OPE estimators that have asymptotic distribution guarantees, e.g., Kallus and Uehara (2019) as is cited in the paper (though they require the propensity to be bounded away from 0 and 1). If we consider a Markov design setting where the bounded propensity assumption does hold true, can these estimators be directly applied to do sequential online testing? It would be desirable to also compare with them in synthetic studies. \n\n- Several key notations are delayed to the appendix, which makes the reading experience not very smooth. \n\n\n*Minor Comments and Typos*\n\n- The initial value for $S_0$ in synthetic analysis seems to be missing.\n\n- Page 2 Line 5: \"to allows\" $\\rightarrow$ \"to allow\"\n\n- Last line, 2nd paragraph in section 2: \"these method\" $\\rightarrow$ \"these methods\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "i5jwUf7qqxk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper considers the A/B testing scenario where there are a sequence of actions that would change the environment state and the reward, such as the ride-sharing dispatching. Moreover, the authors formulate the RL framework in terms of the potential outcome rather than by observed data, since they want to model the off-policy evaluation scenario where only the observed data are collected. The authors propose the conditions for the indentifiability of the hypothesis testing, propose a testing procedure, provide its theoretical analysis on type-I error and power, and conduct experiments on both synthetic data and real-world data.\n\nThe writing of the paper is too dense, and thus it severely impacts the understanding of the technical content of the paper. One issue is that the main text of the paper intensely refer to contents in the appendix, including the actual testing procedure pseudocode, the discussions on many aspects of their study, and many additional results. The appendix is not required to be read by the reviewers, but the current text without these appendix is not self-contained. Another issue is that intuitive explanation and discussion are not enough. For example, Lemma 1 is the key lemma for the identifiability result, but how to interpret it? Why does it mean identifiability? How does it depend on the four assumptions? There is lack of conceptual explanation of this lemma. Theorem 3 (type-I error) and Theorem 4 (power) also lack discussions. Moreover, three treatment designs D1, D2, and D3 in Section 4.2 also lack discussions. Why do we consider these three cases? Are they general enough to cover many application scenarios? What about other cases? Overall, I feel that the main issue of the paper is that its technical part is too dense, lacking many needed explanations. As a result, it is hard to appreciate the novelty of the paper, and it is unclear what is the exact new contribution of the paper.\n\nIn contrast, the rea-world data evaluation from the ride-sharing dispatching is the most informative part I found in the paper. Through this test, the authors demonstrate that the standard t-test fails to discover the carry over effect and cannot distinguish the two policies, while the test proposed by the authors could detect the long-term effect and show the advantage of the new policy. I hope that the authors could elaborate more on this real-world test, and connect it with their theoretical analysis to explain how their test could improve upon the standard t-test.\n\nMinor comments:\n\n- P15, Lemma 2\nThe second Q(a',a',s'). Should it be Q(a', a, s')?", "extra_scores": {}, "extra_text": {}}, {"review_id": "KCyZHYeL8F", "reviewer": "AnonReviewer3", "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": "Summary: the paper is motivated by the problem of sequential experimentation as found in online experiments; more precisely the authors propose to use an RL framework to measure performance while optimizing each treatment policy during experiment. The proposal gives rises to a sequential statistical test procedure to decide at the earliest which treatment policy is significantly better than the others. Theoretically, the power and precision of the sequential decision process are studied and proven to be non trivially efficient. Experiments showcase the method on synthetic and private datasets, including influence of the true effect size on test trigger.\n\nGood points:\n- [novelty] the rewriting of Q/V functions as counterfactuals seems quite original\n- [impact] the problem of early termination and optimization of online experiment decision is important for many industries\n- [scientific rigor] detailed and rigorous statement of setting and assumptions\n- [impact] proofs of the test precision and power give important guarantees\n\nQuestions:\n- is the treatment policy $\\pi$ deterministic ? I'm confused as it is in Sec. 3.1 but not in the comment after Lemma 1 (also \"certain conditions\" remains mysterious to me)\n- Why \"in our setup, test statistics no longer have the canonical joint distribution\" (Sec. 2) - could you elaborate on that ?\n\n Points currently limiting the relevance of the paper:\n- Current write-up falls short in convincing me that an RL framework is indeed necessary to solve sequential testing / early stopping of experiments. I would have appreciated a simple example showcasing the shortcomings of existing approaches (beyond simple t-test) to fix ideas and identify critical properties of a testing strategy that solves the problem.\n- I would have expected more discussion of early stopping methods for sequential testing, e.g. https://dl.acm.org/doi/abs/10.1145/2766462.2767729 . As the problem is pervasive for tech companies it would be very surprising that no competing methods exist. Even if they don't have all the theoretical properties of the one proposed I suspect they would still be interesting to compare in experiments. Oftentimes even invalid methods show competitive behavior in practice.\n- I'm in doubt whether the most relevant baselines were used in the experiments. Especially for the ride-sharing system I believe using other baselines than just t-test would highlight the benefits of the proposed test. Regarding the t-test that is used: I believe using it at different times in the experiment as seen in Fig. 2 jeopardizes any guarantees without adjustment for multiple testing. If Bonferroni was used to correct it it is thus quite understandable why it fails dramatically. The work of Abhishek & Manor 2017 cited as related works would have been a much better baseline in that respect (but other alternatives exist). Moreover, I would have expected to see more advanced techniques that optimize the decision time as baselines as this problem is quite old and pervasive now for many tech industries such as search, advertising and so on.\n- I would be interested in the point of view of authors whether the bandit literature on sequential A/B testing could be relevant here, e.g. https://arxiv.org/abs/1905.11797 or https://arxiv.org/abs/1905.11797\n- Propositions would have benefited to have a sketch of the proof inline\n- Some dependent concepts (e.g. $\\alpha$-spending) are used without a self-contained definition or reader friendly introduction\n\nPoints that could improve the paper (and my score):\n- add an example showcasing the shortcomings of existing approaches; starting probably with the t-test and ending with more advanced baselines (see below)\n- add discussion of more \"early stopping\" baselines (e.g. https://ieeexplore.ieee.org/abstract/document/7796910 + refs above)\n- add more relevant baselines in experiments to clarify impact of the contribution w.r.t. existing practice\n\nOverall my feeling for now is that the proposed technique is quite original and promising but that it lacks strong arguments to show that it is the simplest solution giving as good performance. I'm quite inclined to review my score based on the forthcoming discussion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a testing procedure to determine whether a policy is better than another policy with respect to long-term treatment effects. The reviewers found the problem interesting and saw a lot of value in this work. One of the key concerns was the lack of clarity throughout the paper. The reviews helped the authors actively revise the paper, improving the paper's overall readability throughout the discussion phase. However, the reviewers did not change their ratings. While I agree that this work has merits, since there are many legibility issues, I cannot recommend its acceptance at this stage. 


Decision: Reject