Optimal Treatment Allocation for Efficient Policy Evaluation in Sequential Decision Making
Authors: Ting Li
Chengchun Shi
Jianing Wang
Fan Zhou
Hongtu Zhu
Venue: NeurIPS 2023 poster (2023)
Keywords: Average treatment effect
Experimental design
Off-policy evaluation
Optimal treatment allocation

Abstract: A/B testing is critical for modern technological companies to evaluate the effectiveness of newly developed products against standard baselines. This paper studies optimal designs that aim to maximize the amount of information obtained from online experiments to estimate treatment effects accurately. We propose three optimal allocation strategies in a dynamic setting where treatments are sequentially assigned over time. These strategies are designed to minimize the variance of the treatment effect estimator when data follow a non Markov decision process or a (time-varying) Markov decision process. We further develop estimation procedures based on existing off-policy evaluation (OPE) methods and conduct extensive experiments in various environments to demonstrate the effectiveness of the proposed methodologies. In theory, we prove the optimality of the proposed treatment allocation design and establish upper bounds for the mean squared errors of the resulting treatment effect estimators.

Optimal Treatment Allocation for Efficient Policy Evaluation in Sequential Decision Making
Ting Li
Chengchun Shi? Jianing Wang' Fan Zhou'
Hongtu Zhu
School of Statistics and Management, Shanghai University of Finance and Economics
Department of Statistics, London School of Economics and Political Science
Department of Biostatistics, University of North Carolina at Chapel Hill
tingl 1eaii0mall..... shufe. edu. c. shi70lse ac uk, jianing. wang@163 sufe. edu..cdu.mm cn zhoufan@mail 1. shufe. edu. cn, htzzhuemaill unc.
Abstract
A/B testing is critical for modern technological companies evaluate the effective- ness of newly developed products against standard baselines. This paper studies optimal designs that aim maximize the amount of information obtained from online experiments to estimate treatment effects accurately. We propose three optimal allocation strategies dynamic setting where treatments are sequentially assigned over time. These strategies are designed to minimize the variance of the treatment effect estimator when data follow a non-Markov decision process or a (tme--varying Markov decision process. We further develop estimation procedures based on existing off-policy evaluation (OPE) methods and conduct extensive experiments in various environments to demonstrate the effectiveness of the pro- posed methodologies. In theory, we prove the optimality of the proposed treatment allocation design and establish upper bounds for the mean squared errors of the resulting treatment effect estimators.
1 Introduction
Motivation. Prior to the full-scale deployment of any product practical applications, an accurate evaluation of its potential impact is crucial. Modern technology companies, including Amazon, Google, Netflix, Uber, and Didi, commonly employ online experimentation or A/B testing as a means of evaluating the effectiveness of products or policies (treatment) in comparison to their existing counterparts (control). Often, in these experiments, policies are assigned sequentially over time, impacting both current and future responses. Such dynamic can invalidate the Stable Unit Treatment Value Assumption (SUTVA), as outlined by (Imbens and Rubin 2015). Failure to consider these temporal carryover effects lead to biased estimation of the treatment effect. Additionally, the limited duration of the experiment and the typically small size of the treatment effect pose significant challenges to consistently detecting the treatment effect.
substantial body of literature has been dedicated to developing policy evaluation or A/B testing algorithms using data from online experiments. However, there has been limited focus the generation of the experimental dataset itself. This factor is critical as can substantially influence the precision of the subsequent treatment effect estimator. This paper's primary focus is to study optimal experimental designs in the context of sequential decision making. In clinical trials, a carefully designed experiment can significantly improve the accuracy of the treatment effect estimator and the statistical power of the associated test, as noted by (Sverdlov et al. 2020). However, most existing
'The first authors contribute equally this paper. Address for correspondence: Hongtu Zhu, Ph.D.,
E-mail: htzhu email.unc.dde
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) NMDP
01
A1
R1
02
A2
R2
03
(b) TMDP
0₃
A1
R1
Q2
A2
R2
0
(c) MDP
02
A
//
R1
O2
A2
//
R2
O₃
Figure 1: Data structure of NMDP, TMDP, and MDP. (a) In the NMDP, the reward and future observations determined by all past observation-action pairs. (b) In the TMDP, the reward and future observations depend solely on current observation-aation pairs. (c) In the MDP, reward and future observations also rely on the current observation action pairs, with the same-colored slashes indicating identical conditional distributions.
designs consider the classic identically and independently distributed (i.id.) setting, failing to account for temporal carryover effects.
Contributions. We make three important contributions below. Firstly, we propose three optimal dynamic treatment allocation strategies in sequential decision making, while accounting for carryover effects over time. The proposed designs are built upon the A-optimality criterion developed in non-dynamic settings (Atkinson al. 2007). and effectively minimize the variance the average treatment effect estimator when data follow (time-invarian Markov decision process (MDP), time-varying MDP (TMDP) or a non-Markov decision process (NMDP), Figure offerrs a visual illustration of these data generating processes. To our knowledge, this represents the first piece of work to provide an analytical form of optimal allocation strategies within these dynamic contexts.
Secondly, by leveraging insights from the established field off-policy evaluation (OPE, see, for instance, Dudík al.] 2014]] [ehhara et al. 2022] for reviews), we devise subsequent estimation methodologies that learn the treatment effect estimator using log data produced in accordance with our proposed design. We employ real datasets gathered from globally recognized ride-sharing company to create a city-scale synthetic environment that mimics the opatio-temporg dynamics of the order dispatching problem. Our findings indicate that the proposed estimators deliver significantly superior accuracy compared to conventional baseline estimators.
Thirdly, establish the theoretical properties of the proposed designs and estimators. Specifically, establish that in NMDPs, the optimal design distributes the initial policy randomly, with probabilities corresponding the standard deviations of the cumulative rewards, and subsequently implements the same policy. However, such a design may not necessarily be optimal in (T)MDPs. To address this, focus category of restricted designs and identify sufficient conditions that ascertain their asymptotic optimalities in (T)MDPs. Moreover, we derive an upper limit for the mean squared error (MSE) of the resulting treatment effect estimator. Extensive simulation studies have been conducted to assess the finite sample performance of the proposed algorithms. Python code implementing the proposed algorithms available at
www.coo//ooo/o. htmm/iinnstat/MDD. desigg
1.1 Related work
Experimental designs. There an extensive body of literature on experimental design for clinical trials, with multitude of optimal designs proposed. These include the global treatment balance design (Efron, 1971 Wei 1977). designs that regulate the marginal covariate distribution across
various treatment groups (Pocock and Simon 1975; Heritier et al. 2005 Liu and Hu 2022). and criteria-based design anchored on variance minimization (Begg and Iglewicz 1980 Wong and Zhu 2008 Chandereng et al., (2020). Other noteworthy designs are the D D-opumality and its generalization
DA optimality (Jones and Goos, 2009 Atkinson and Pedrosa, 2017 Loux 2013 Liu al. 2022).
alongside the A-optimality and its extension AA optimality (Atkinson et al. 2007 Sverdlov and Rosenberger 2013), Yin and Zhou 7). Moreover, numerous sequential adaptive designs for
clinical trials have been developed, including covariate-adaptive designs (Zhu and Hu 2019 Wang

---

and Ma 202T). J response-adaptive designs (Zhu et al. 2020 Yu et al. 2022), and avvariate-djussee aaponse-adaptiin designs (Zhang et al., 2007 Villar and Rosenberger, 2018). However, these methods were designed for i.i.d. data and thus are not directly applicable to our settings.
Recently, several papers have studied experimental designs with spatial/network spillover effects
(Ugander et al. 2013; Baird et al. 2018 Li et al. 2019| Jagadeesan et al. 2020 Nandy et al. 2020
Viviano 2020 Zhou et al. 2020 Kong et al. 202 Leung 2022). Additionally, a few designs have
been developed for modern technological companies, such as e-commerce (Bajari et al. [202] Nandy
al. 2021 and ride-sharing (Johari et al. 2022). However, these studies differ from ours that they did not utilize NMDP or TMDP models for experimental designs.
Bojinov et al. (2023) explored optimal regular switchback design in the presence of single ex-
perimental unit. Their approach relies on the assumption that the carryover effects last for a fixed duration. However, this assumption is not consistent with our NMDP and (T)MDP models, where the carryover effects, due to state transitions, can potentially last indefinitely.
Finally, Bayesian Optimal Experimental Design (BOED) presents powerful tool for numerically determining the optimal design (see e.g., Ryan et al. 2016 Rainforth et al. 2023). Recently, works such as Foster et al. (202T) Lim et al. (2022), and Blau al. (2022) have proposed leveraging deep reinforcement learning to compute the BOED. In contrast, our paper employs frequentist approach, analytically deriving optimal designs for sequential decision making.
Off-policy evaluation. Our work is closely related to OPE, which seeks to estimate the mean outcome of new target policy using logged data collected by a different policy. It has been applied in range
of domains including healthcare (Murphy 2003), education (Mandel et al., 2014), ride-sharing (Shi
et al. (022) and video-sharing (Xu et al. 2023). Recently, it has been employed to conduct A/B
testing and mediation analysis in the presence of temporal carryover effects (Hu and Wager 2022
Farias et al. 2022] (Shi et al. 2022; Tang et al. 2022 Ge et al. 2023 Shi et al. (023). Existing
algorithms include value-based methods (Mannor et al. 2007| Antos et al. 2008 Le et al. 2019
Feng et al.
2020 Luckett et al. 2020 Hao et al. [021] Liao et al. 202 Chen and (1/[2022 Shi
ct al. [022 Bian et al. 2023). importance (re)sampling) hatpssammlin--seeee based methods (S (Swaminathan and Joachims
2015 Liu al. [2018] Schlegel et al. 2019 Yin and Wang. 2020; Thams et al.] /20////aag et al.
2021
Hu and Wager| (023), and doubly robust or more robust methods (Zhang et al. 2013)/iang and
|
and Brunskill 20166] Farajtabar et al. 2018 Kallus and Uehara [2020 Uehara et al.
2020][Shi (Shi et al. [022]] Kallus and Uehara 2022 Liao et al.
2022 Xie et al.] 2023). In particular, Kallus and Uehara (2022) and Liao et al. (2022) established the efficiency bounds for OPE, which
we leverage to construct optimal designs. However, none of the previous work considered how to design the behavior policy that generates high-quality data improve the efficiency of the policy value estimator.
Recently, Wan et al. (022)) studied safe experimental designs for efficient policy evaluation under certain safety constraints in a non-dynamic setting without temporal carryover effects. However, remains unclear how to generalize their methodologies to sequential decision making.
A/B testing. Lastly, our proposal aligns with body of literature that develops A/B testing algorithms for randomized online experiments (see e.g.. Kharitonov et al. 2015 Johari et al.] [017]] Yang et al.
2017
Bojinov and Shephard 2019; Ju et al. 2019 Zhou et al. 2020 Shi et al. [202] Maharaj et al.,
Wan et al. 2023). However, most works focus on the sequential monitoring problem, which involves partitioning the significance level at each interim stage to control the overall type-I error.
2023
This is distinct from our goal, which is to generate high-quality experimental data to enhance the efficiency of estimation and inference.
2 Models and Problem Formulation
Data. We consider an experiment spanning days and each day is divided into T time intervals. On the i-th day (i ===1, 1,..., n) and time interval (t = "....,,T) the decision maker observes certain time-varying market features, denoted as O.(²) (c.g., the numbers of incoming orders and available
drivers in ride-sharing platform) and chooses to implement one of the two policies. This action is denoted as A {0, 1}. By convention, A! 1 indicates the implementation of new policy, while A = signifies the use of the control policy. Afterwards, the decision maker receives an immediate reward f and subsequently observes the next observation (41- This process is
3

---

repeated until we reach the termination time T. The observed data can thus be summarized as {O(", A ref",, , 1...1...,77
Model. We consider three models for the aforementioned data generating process: an NMDP, a TMDP, and (time-invariant) MDP. As depicted in Figure 1, an NMDP is versatile model that doesn't impose Markovian or stationarity assumptions. The immediate reward (R₂) and future observation (0t+1) depend on the entire history of observations and actions, not merely the current observation-action pair (O, and A₁). This kind of model has been extensively used in research on learning optimal dynamic treatment regimes (Kosorok and Laber 2019 Tsiatis et al., 2019). Conversely, a TMDP a special case of NMDP, with a stronger structural assumption that satisfies Markovanity. It assumes that the current observation-actinn immediate reward and future observation, while allowing this conditional distribution function to vary with time. This type of data generating process also known as episodic MDP and has been widely studied in the reinforcement learning literature (see e.g., JJin et al. [0118] 2021 Li et al. 2023).
pair is sufficient determine the
Finally, an MDP special TMDP with an additional stationarity assumption.
Objective. A rule, Ne( H.), uses the observed data history H2 up time i as input and provides probability distribution as output. This output determines the likelihood of choosing each action A, at time t. The primary objective here is to estimate the Average Treatment Effect (ATE), which is defined as:
policy, denoted as π, is a sequence of decision rules { (T) Each
ATE = T
E (R.) E (R.)..
where E. (or E2) signifies the expected value when the system follows the new (or control) policy.
Moreover, for any in the set (0, }. let's define (h) as the value function, Σ1- k= E (Rx H,, = h), when a certain action is followed. It's evident from this that the ATE equals [V (()
Let R denote the behavior policy that generates the experimental data, i.e., 7 H., = P(A, H.) for any and I. Our objective lies in the design of an optimal behavior policy to generate high-quality data so that the mean squared error of the subsequent ATE estimator is minimized.
3 Design, Implementation and Evaluation in NMDPs
We focus NDMPs in this section. We begin by proposing the optimal dynamic treatment allocation strategy to generate the experimental data. We next discuss some implementation details to implement the proposed design. Finally, construct the ATE estimator from the data collected.
Design. Diang and Li (206)) and Kallus and Uehara (2020) established the semiparametric efficiency bound, which is a nonparametric extension of the Cramer-Rao lower bound in parametric models (Bickel et al.) 1993). for offline estimation of the average return under a general target policy in NMDPs. In essence, the efficiency bound corresponds to the smallest mean squared error (MSF) among a broad class of regular off-policy estimators. They further developed semiparametrically efficient estimators whose asymptotic MSEs reach this lower bound. Based their results, one can easily show that the efficiency bound (EB) for the ATE equals:
I(A+ I(A==a) 2 Vark) (a
EB (-² | -T Σ
Σ
(He, a) II
(I)
(E(0.
where of a) denotes the conditional variance of the temporal difference error R.+ f4-1 (H++1) (H,) given H, and that A, = a, and I[+) denotes the indicator function. Note that the second term on the lighthhand-side (RHS) is independent of the behavior policy. However, the first term is a function of " in that: (i) the ratio in the first term explicitly involves n²; (ii) the expectation E=* is taken with respect to the data generated by nb_
The proposed design identifies the optimal T that minimizes II. Before delving into the details of the proposed design, we first present the main idea behind A key observation that the cumulative ratio II [I[ A a)/mī m (al Hx)] appears on the RHS of (T) due to the use of sequential importance sampling (see e.g.. Jiang and Li 2016 Equation (4)) to account for the distributional shift between n and the global policy that assigns action a each time. general, the value of the cumulative ratio grows with the discrepancy between the target and behavior policy. Hence, it is plausible to

---

Algorithm I Treatment allocation algorithm for NMDPs
Input: The burn-in period my for each global policy and the termination day
1: Run each global policy for mi days and obtain {O!²) A R(()) 2mo.
2: while 2mo < S do
3: Using the collected data to estimate Vi and o. (., a) via 3 Obtain a.(O :0).
4: Assign ATT according to The 11m-- [a| (al()m)) = (0(0m a) ,1) + (0,m) .0]]
5: Set Amm) ..... 1 (m))
m
6: end while
Output: (0, (1) A, R pm
Ji=1'
expect that an on-policy estimator, where all actions are determined according to the target policy, could potentially minimize the MSE.
We show in Theorem I below that the optimal design corresponds to slight modification of the aforementioned on-policy design. Specifically, it randomly allocates the initial action with probabilities proportional to the standard deviations of the cumulative rewards (see Equation (2). and assigns the same action afterwards.
Theorem 1. In NMDPs, Te that minimizes
satisfies: (i) any a E {0, 1}
(0,,
" (a(OO)
(2)
00,
where of (R, n (A1 H = almost surely, equivalently, A1 = A
a): (ii) n22- (A1 Ar under π h"
ba #3 (1(Ha))
Implementation. It remains to estimate the standard deviation a. to implement the proposed design. use it to estimate d,, Otherwise, we can use data collected from
If historical data is available, the experiment to adaptively update this parameter. Initially, we run each global policy for me days to generate the data. Next, the mth day (2mg < S n.), we estimate a. using the experimental data collected so far. To this end, we begin by applying existing supervised learning algorithm to estimate the value function V/5 by regressing the cumulative rewards {E, Ee(" A( a, i < m)
on the initial observations {0{²) : A = 0, i < m] where the superscript indicates that the data are collected on the ith day. Let Vi, m1,m-1 denote the resulting estimator. We next employ supervised learning again to regress the squared residuals on the initial observations to estimate a. a) as
m-
I(A = a){ > R - (()) 1.m- (o -()
T_ (_ arg min a(-)
(3)
1=1
Finally, we plug (0(m) a) into the RHS of 2 to obtain - assign ((T)) according to bb x1,m-1
and set A(r)) =... A (mm) (m))
(m)) We summarize our procedure in Algorithm
Evaluation. Finally, we compute the ATE estimator using the experimental data. Several OPE algorithms, including value-based importance sampling (IS), and doubly robust (DR) methods, are applicable for this purpose. DR estimators are known for achieving the efficiency bound (Kallus and Uehara 2020). In our context, we suggest using the following online DR estimator for ATE,
ATE: Σ (-1)a-1
I(A a)
Σ
RS
Dr. (0 (4)
a=0 T(n 2mp) 2m
+br (1)
Note that both the estimated value function V V1,11 and behavior policy 7/. "1,-1 in are com- puted during the data collection process. These nuisance functions are independent of the data (0(") ( R(O0} used to construct the policy value. This cross-fittins procedure enables us to cireumvent the need to impose certain metric entropy conditions (Díaz, 2020) and has been widely employed in the statistics and machine learning literature (Luedtke and Van Der Laan 2016 Bibaut jet al. 202T: Shi et al., (02T). By design, 4 can be caleulated an online manner, eliminating the need store historical data. Moreover, implement burn-in procedure that discards the first 2mo
5

---

samples to construct ATE. This ensures the consistencies of VT, and .., Concurrently, value-based and IS-based methods are also suitable for estimating ATE. Provided that the nuisance functions are properly modeled, these estimators can achieve the efficiency bound as well (Uehara et al., 2020
Liao al. 2021; Wang et al., 2021 bound for the MSE of the proposed ATE estimator.
| Shi et al. 2023). The following theorem provides an upper
by Theorem 2. Suppose that min; 7 1, 2 e and Ví, S Rmuxx for some constants > and Rmax
0O, m, E, 1 (a, 11m (a, 01)12 ) S Ci-2os and maxa,
Ci 202 for some constants < oc, 0 < 01, 02 < 1/2. Then we have
(TT + O(E C - -mo) -1-20) B(ATE; - ATE) S 2mo
) + O max VC 2mo) -1-a) -1-a)
In this case, the exponents a1 and 02 denote the convergence rates of the estimated behavior policy and value function, respectively. Note that the first term the leading term, while the last two terms represent the estimation errors of the nuisance function estimators and converge at rate much faster than (n 2mp) The error bound above minimized when mg zero. In such a scenario, the bound asymptotically equal to n 'EB1 (a (m""), which is equivalent the MSE of an oracle ATE estimator. Specifically, the oracle estimator is version of the DR estimator with correctly specified value function and behavior policy, and is constructed based on data collected over n days from the optimal design x"" Thus, the proposed estimator is asymptotically optimal.
Next, show how to construct the confidence interval of the ATE estimator. A key observation that, under certain regularity conditions, the proposed estimator is asymptotically normal. More specifically, similar to Kallus and Uehara (2020), have
2m ATE,
ATE) (
This motivates us to consider the following Wald-type confidence interval
[ATE] 16 (1- v EB (B1(T*)) - 2mo), ATE; + + '0-0(111 ((1-a/2) / ( 2mo)],
where 4- is the inverse cumulative distribution function of standard normal random variable. It then suffices to estimate the asymptotic variance EB, (I²*) to construct asymptotically valid confidence intervals. Notice that ATE, can be represented as an average of martingale differences ATE; = Ei=2mo+1 w//(n- -2m) where
a11 T
I(A = a) # (a
1 Σ
(0
R
v (o.
We propose using the sample variance of {w:] 1 to estimate EB, (T²*). Similar to Theorem 15 of Kallus and Uehara (022), establish the consistency of the sampling variance estimator.
4 Design, Implementation and Evaluation in TMDPs and MDPs
We proceed to study the optimal design and the subsequent ATE estimation in TMDPs.
Design. According to Theorem 2 of Kallus and Uchara 2020). the efficiency bound for the ATE estimator equals
Ea* T(A a)pf()) (1(O), a) + T2 -O)) (5) (),,))))
EB2(TT) Σ
Σ aE/0011
where p (o)) denotes the probability mass/density function of O under the new policy (con-
trol), pft denotes the probability mass/density function of the observation-ace time under the behavior policy, and of (O,, a) is the conditional variance of the temporal difference error R + (0++) (O.) given the current observation O, and that A,
pair (O,, A,)
The efficiency bound in (5) bears a striking resemblance to that in ① The sole difference lies in the replacement of the sequential IS ratio in (I) with the ratio of the marginal observation-action pair

---

under the Markov assumption. However, in contrast to NMDPs, the marginal distribution function p in TMDPs cannot be represented in closed-form as a function of T². This intricate dependence of p on x" makes it exceptionally challenging to identify the optimal ~h* that minimizes (5). To elaborate, let II represent the class of behavior policies that randomly assign the initial action, and set II = (x" x (A | = 5 (A)) = (A1 Hr) = 1}. In Theorem | we show that the optimal behavior policy R"~ belongs to II in NMDPs. However, this is not the case in TMDPs without additional assumptions.
Proposition 1 (Informal Statement). There exists a TMDP such that xh" &f II
Identifying the exact optimal design remains challenging. Motivated by the simplicity of the policy class I7", we shift our focus to finding the optimal in-class behavior policy within IT that minimizes (5). We restrict the treatment assignment policies to IT for two primary reasons. First, the optimal design for NMDP resides in class ITo, leveraging this result allows us to anticipate that in-class behavior policies from IT will perform well in TMDPs/MDPs, which are subclasses of NMDP: Second, freguently alternating treatments can introduce significant carryover bias in policy evaluation (Hu and Wager, 2022). By focusing on 11", we avoid distributional shifts between the behavior policy and the target policy, effectively mitigating carryover bias. To further simplify the analysis, we consider scenarios where the number of decision stages T approaches infinity. The following theorem provides the form of an optimal T"" E II that asymptotically minimizes (5) under mild 3-mixing condition. Additionally, it shows that Th is optimal among all deeendedd policies under certain constancy conditions.
Theorem 3. Suppose the B-mixing condition holds such that lim, E Esup a. -pp( +
o where p (+ (O2) denotes the probability mass function of On given O₂ following the action a. Then an asymptotically optimal in-class behavior policy b satisfies (i) for any E {0, 1}.
T
(al00) = -T" T1+ Jo+
On- where oa. = Σ 1=1
E 18% (0,, 1)1:
(6)
(ii) T3" H2) (An (A1 =... nt ()) = 1 almost surely. In other words, for Th
that satisfies (i) and (ii), we have limr TEEB2(T"*) EB2(1")] S ffr any x² E 11., Additionally, suppose both (o, 1) and af (o, 0) are constant as functions of o and t. Then limr EB2(7")] < foror any n².
The B-mixing condition essentially requires the Markov chain be ergodic. Similar conditions have been imposed in the literature (Bhandari et al.) 2018 /oo et al. 2019; Luckett et al. 2020 Kallus and Uehara 2022 Li et al. 2022; et al. [022] (023). It also weaker than the independence assumption that requires the transition tuples to be independent over time and has been frequently imposed in the literature. The constancy condition
automatically satisfied when the temporal difference error is independent of the current observation and the time step. Different from the optimal design in NMDPs, the initial policy in (6) is independent of the initial observation, thanks to the mixing condition.
Implementation. We summarize the procedure in Algorithm 2
Evaluation. Similar to Section 3 we can apply value-based, IS-based, or doubly robust estimator to learn the ATE from the collected data. Consider the double reinforcement learning estimator (DRL,, Kallus and Uchara 2020) as an example. A key observation is that the marginal observation- action probability distribution function pf(O,, At) under t cquals क| (At)p, (Ot). As such, the resulting marginal ratio ((A, = a)p; (O.)/p²
///////(Oa (O,, a) is equal to I(A, = a)/mī (At), or equivalently [[(A, = a)/ कं (A1), independent of O,, Consequently, one can show the resulting DRL is reduced to
(-1)a+1
(V))-(0(0)+ I(A =a)
ATE2-
Σ a=u T(n 2mo) 2=2m0+1
Σ
(1) R
V (o{)))
Tb. (a)
where Vi, and न| (a) denotes the estimated value function and estimated initial allocation probability using data from the first ith days; see Step 3 of Algorithm@ the estimation procedure. Similar to ATE, in 44, ATE, can be updated in an online manner without storing historical data. We provide an upper bound for the MSE of ATE, below.
7

---

Algorithm 2 Treatment allocation algorithm for TMDPs
Input: The burn-in period my for each global policy and the termination day
1: Run each global policy for mi days and obtain {0! Al R((1) 2mo.
2: while 2mo < S do
3: Obtain 1,m by regressing {Ej= R : m, A = on 10 :1 m, Al a].
4: For {0, 13. set
6a- Eiem Σ T
21=1 [
+
Va 141, (0 (1) )| =a)
Σxmm I(A) = a)
5:
Assign (²) according to a/e A (m))
f1,m
11,m-1(a) = 0 + Ōv-).
6: Set (
(m)
7: end while
Output: {0,) AA R pm
1i-1
Theorem 4. Suppose that min; मो. 2 e and VI, S Tmmax for some constants > 0 and Riax <
00, maxa,i (a) (a)13 v Ci-2as and maxa;;
< Ci Ci-20z
for some constants C < 00, 0 < 01, 02 < 1/2. Then we have
E(ATE2 ATE)² < n 2mo
O(C -mm) (amo)-1-200 202) + O(VOO(CCRCC R (n ma) -1-a1).
Similar to Theorem 2 the MSE of the proposed ATE estimator relies on mo, the estimated behavior policy and value function. The first term is asymptotically equal to n "EB2( when mg is much smaller than This suggests that the proposed estimator is asymptotically optimal in TDMPs.
Analogous to the procedures in Section 3 we can similarly establish the asymptotic normality of
ATE2, i.e., vn (ATE ATE) N(0, (Br(")), The corresponding 1 confidence interval can be constructed by
[ATE2- + 5- a/2)/
a1-22) (B2(t / 2mo), ATE2 + $ 5- a/2) (B2(Tb))/0 2m,)],
where the unknown asymptotic variance EB2(x"") can be similarly estimated via the sampling variance estimator.
MDPs. Finally, we consider MDPs. To save space, we briefly introduce our proposal here and relegate the technical details the supplementary article. The proposed design is built upon the efficiency bound developed by Liao et al. (2022) in the average reward infinite horizon setting. To simplify the analysis, similar our proposal in TMDPs, we focus on in-class optimal designs and consider an asymptotic regime where 7 + oc. The following theorem summarizes the properties of the proposed behavior policy f E II
Theorem 5 (Information Statement). Suppose the B-mixing condition holds. Then Th* asymptotically minimizes the efficiency bound among all x² E II In addition, under a constancy condition, it is asymptotically optimal among all policies.
To learn the ATE, we construct online doubly robust estimator in the supplementary article based on the estimated relative value functions (Puterman 2014) and the designed behavior policy.
5 Experiment
This section presents four experiments designed to evaluate different designs. The environments include a tabular example with binary observation variables, an example with continuous observations, small-scale synthetic dispatch example, and city-scale real data-based dispatch simulator. We investigate the proposed treatment allocation strategies designed for NMDPs and MDPs. We also implement the following three allocation designs for comparison:

---

0.00
0.
5:15
0-12
0.00
0:45
8-1
Random Haah MMCC
NDP
Greddy Random Leaf
HDP
Greny Randon Hoatra KUDP
1200
Grady Randon retoal MEP
NEP
Figure 2: Boxplots of the MSEs of the allocation methods for p. = 0.8 and T = 50 in Example 5.1 the four panels correspond to 6 0,3, 6, and 9, respectively.
(i) Random: This uniform random treatment allocation design assumes P(Ar, = 1) = 1/2. All A are independent.
(ii) Half-half:: This design applies the global treatment for the first n/22 days and the global control for the remaining days.
(iii) Greedy: This design uses the e-greedy algorithms that select the current-best treatment, which maximizes the Q-function, with probability - and employs uniform random policy with probability
We note that (iii) is widely used in the RL literature for online regret minimization. We compare the mean squared errors (MSEs) of the estimates of the average treatment effect based on 200 replicates, and present the results subsequently We set the burn-in period mo to n/4 in all the experiments. Detailed information on the data generating processes can be found in Section S2 of the supplementary material.
Example 5.1 (Binary Observations). In this example, we consider binary observation variables. To better understand the results, we introduce some syper-parametess that describe the system dynamics. Let p. denote the marginal probability that the future observation O++1 equals 1 if A, 1, and it is conditional variance of the reward between the treatment and the control. A larger value of 8 indicates a greater difference.
Ps if A, O. Additionally, we use 5 E {0, 3. 6, 9} to characterize the difference of the
Figure 2 presents boxplots of the MSEs for the allocation methods when p. = 0.8, T = 50, and 50. It is evident that the proposed treatment allocation methods generally outperform the alternatives, offering lower median MSE and smaller variability in most scenarios. However, when 5 the half-half design outperforms ours. This outcome expected since in this case, the optimal allocation rule assigns the initial action with equal probability, i.e., b² 0.5. As å increases, our proposed estimator surpasses the others terms of achieving a smaller MSE. Table I in the supplementary material presents the means and standard deviations of the MSEs for T E {10. 30, 50} and P. E (0.5, 0.8). In these scenarios, our proposed designs consistently outperform the alternatives. Example 5.2 (Continuous Observations). In this example, we use 8, to denote the difference in the conditional variance of the observation variable between the treatment and the control, and to describe the difference of the conditional variance of the reward.
Figure 3 presents the boxplots of all MSEs for 6, = and T 50 with of the supplementary material includes the Monte Carlo averages and standard errors of MSES for T' (10, 30, 50} and 8, {0, These results are comparable demonstrating the superior performance of the proposed design when ò is moderately large. This expected, the proposed method takes into account the conditional variance of the temporal difference error.
50. Table
those in Example 5.1
Example 5.3 (Synthetic Dispatch). Following Xu et al. (2018), we construct small-scale synthetic dispatch environment to estimate the treatment effect of different order dispatch policies. Specifically, we simulate drivers and orders in 9 x spatial grid with a duration of 20 time steps per day. Orders will be canceled if not being responded for a long time. We compare the MDP order dispatch strategy (Xu al., (018)) against the distance-ber based dispatch method which minimizes the total distance between drivers and passengers. The reward of interest is given by the total revenue. The observation variables are set to the number orders and the number of drivers at each time. The number of days is set to be (30, 50, 100). All the methods are tested using 100 orders with the number of drivers being either generated from the uniform distribution (25, 30), or being fixed to 25, 50. A detailed description of the environment can be found in the supplementary document.

---

037
0076
0.12
0.00
0.05
8:5
Random Hagf
MBCC
Iaakbal
1MCC
Greny Randon Hodfaal NUD
1200
Gmedy Randon lntaaa MMP
MEP
Figure 3: Boxplots of the MSEs of the allocation methods corresponding to 6, = and T = 50 in Example the four panels correspond å 0 3, 9, respectively.
U325.30)
Drivenn
Drtear
0.5
ATE
Figure 4: Boxplots of the MSEs of the allocation methods in Example 5.3 with 50: the three pancls correspond drivers generated from (25, 30) or fixed 25 and 50, respectively.
Figure 4 presents the boxplots of MSEs for = 50 with different numbers of drivers. Table of the supplementary material reports the values of MSEs of the four methods. As expected, the MSEs of all the methods decrease as the increase of the number of days n. The proposed method achieves the best performance in almost all scenarios.
Example 5.4 (Real-Data Based Dispateh). We evaluate the proposed treatment allocation method on a dispatch simulator based on city-scale order-driver historical dataset from a world-leading ride-sharing platform. The dataset consists of temporal spatial information of orders drivers and numerical features of them. We adopt the simulator in Tang et al.) (2019) to generate data based on the historical dataset. The distributions of drivers and orders are of historical data. Similar to Example 5.3 the two policies being compared are the MDP strategy and the distance-based dispatch method. The reward interest is the total Gross Merchandise Volume (GMV), and the observation variables include the number of drivers and the number of orders.
be identical to the distributions
Since the ground truth of the average treatment effect large, calculate the relative MSE of the estimated average treatment effect for each method. RMSEs ATE estimates for distinct allocation designs reported in Figure 5 with the number of days 7 and n 10. It can be seen that the proposed method outperforms all its counterparts. Meanwhile, as the episode n gets larger, the RMSES of most allocation designs become smaller.
Acknowledgement
Li's research is partially supported by the National Science Foundation of China 12101388, CCF- DiDi GAIA Collaborative Research Funds for Young Scholars and Program for Innovative Research Team of Shanghai University of Finance and Economics. Shi's research partially supported by an EPSRC grant 4P/W014971/1. Zhou's 's work is partially supported by National Natural Science Foun- "Chenguang Program" supported by Shanghai Education Development
dation of China 12001355
0.3
Figure 5: Boxplots RMSES of allocation methods Example 5.4 with re and v
10

---

Foundation and Shanghai Municipal Education Commission, Open Research Projects of Zhejiang Lab NO.2022RCOAB06, Shanghai Research Center for Data Science and Decision Technology. We thank the anonymous referees and the meta reviewer for their constructive comments, which have led to significant improvement of the earlier version of this article.
References
Antos, A., C. Szepesvári, and R. Munos (2008). Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning 71, 89-129.
Atkinson, A., A. Donev, and R. Tobias (2007). Optimum experimental designs, with SAS, Volume 34. OUP Oxford.
Atkinson, A. and D. Pedrosa (2017). Optimum design and sequential treatment allocation in exper- iment in deep brain stimulation with sets treatment combinations. Statistics in Medicine 36(30), 4804 4815.
Baird, S., J. A. Bohren, C. McIntosh, and B. Özler (2018). Optimal design of experiments in the presence of interference. Review of Economics and Statistics 100(5), 844-860.
Bajari, P., B. Burdick, G. W. Imbens, L. Masoero, McQueen, Richardson, and M. Rosen (2021). Multiple randomization designs. arXiv preprint arXiv:2112.13499
Begg, C. B. and B. Iglewicz (1980). A treatment allocation procedure for sequential clinical trials. Biometrics 36(1), 81-90.
Bhandari, J., D. Russo, and R. Singal (2018). A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, pp. 1691-1692. PMIR.
Bian, Z., C. Shi, Z. Qi, and L. Wang (2023). Off-policy evaluation in doubly inhomogeneous environments. urXiv preprini arXiv:2306.08719
Bibaut, A., M. Dimakopoulou, N. Kallus, A. Chambaz, and M. van Der Laan (2021). Post-contextual-
bandit inference. Advances in Neural Information Processing Systems 34,
Bickel, P. J., C. A. Klaassen, P. Bickel, Y. Ritov. J. Klaassen, J. A. Wellner, and Y. Ritov (1993).
Efficient and adaptive estimation for semiparametric models, Volume 4. Springer.
Blau, T., E. V. Bonilla, I. Chades, and A. Dezfouli (2022). Optimizing sequential experimental design with deep reinforeement learning. In International Conference on Machine Learning, pp. 2107-2128. PMLR.
Bojinov, I. and N. Shephard (2019). Time series experiments and causal estimands: exact randomiza- tion tests and trading. Journal of the American Statistical Association 114(528), 1665-1682.
Bojinov, I., D. Simchi-Leevi, and J. Zhao (2023). Design and analysis of switchback experiments. Management Science 69(7), 3759-3777.
Chandereng, T., X. Wei, and R. Chappell (2020). Imbalanced randomization in clinical trials.
Statistics in Medicine 39(16), 2185-2196.
Chen, X. and Z. Qi (2022). On well-posedned and minimax optimal rates of nonparametric q- function estimation in off- off-policy evaluation. In International Conference Machine Learning, pp. 3558-3582 PMLR.
Díaz, I. (2020). Machine learning in the estimation of causal effects: targeted minimum loss-based estimation and double/debiased machine learning. Biostatistics 2/(2), 353-358.
Dudík, M., D. Erhan, J. Langford, and L. Li (2014). Doubly robust policy evaluation and optimization. Statistical Science 24),,, 511.
Efron, B. (1971), Forcing a sequential experiment to be balanced. Biometrika 58(3), 403-417.
Farajtabar, M., Y. Chow, and M. Ghavamzadeh (2018). More robust doubly robust off-policy evaluation. In International Conference Machine Learning, pp. 1447-1456. PMLR.

---

Farias, V., A. Li, T. Peng, and A. Zheng (2022). Markovian interference in experiments. Advances in Neural Information Processing Systems 35, 535-549.
Feng. Y. T. Ren, Z. Tang, and Q. Liu (2020). Accountable off-policy evaluation with kernel bellman statistics. In International Conference on Machine Learning, pp.
Foster, A., D. R. Ivanova, I. Malik, and T. Rainforth (2021). Deep adaptive design: Amortizing sequential bayesian experimental design. In International Conference on Machine Learning, pp. 3384-3395. PMLR.
Ge, J. Wang, C. Shi, Z. Wu, and R. Song (2023). A reinforcement learning framework for dynamic mediation analysis. In International Conference on Machine Learning. PMLR.
Hao, B., X. Ji, Y. Duan, H. Lu, C. Szepesvári, and M. Wang (2021). Bootstrapping fitted q-evaluation for off ooficy inference. In International Conference on Machine Learning. pp- 4074-4088 PMLR.
Heritier, S., V. Gebski, and A. Pillai (2005). Dynamic balancing randomization in controlled clinical trials. Statistics in Medicine 24(24), 3729-3741.
Hu, Y. and S. Wager (2022). Switchback experiments under geometric mixing. arXiv preprint 220900970
Hu, Y. and S. Wager (2023). Off-policy evaluation in partially observed markov decision processes under sequential ignorability.
Imbens, G. W. and D. B. Rubin (2015). Causal inference in statistics, social, and biomedical sciences. Cambridge University Press.
Jagadeesan, R., N. S. Pillai, and A. Volfovsky (2020). Designs for estimating the treatment effect in networks with interference. The Annals of Statistics 48(2), 679-712.
Jiang, N. and L. Li (2016). Doubly robust off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, pp. 552-661. PMLR.
Jin, C., Z. Allen-Zhu, S. Bubeck, and M. I. Jordan (2018). Is Q-lcarning provably efficient? Advances in Neural Information Processing Systems 31.
Jin, Y., Z. Yang, and Z. Wang (2021). pessimism provably efficient for offlin RL. In International Conference on Machine Learning, pp. 5084-5096. PMLR.
Johari, R., Koomen, L. Pekelis, and D. Walsh (2017). Peeking at A/B tests: Why it matters, and what to do about it. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1517-1525.
Johari, R.. H. Li, I. Liskovich, and G. Y. Weintraub (2022). Experimental design in two-sided platforms: An analysis of bias. Management Science 68(10), 7065-7791.
Jones, B. and P. Goos (2009). D-optimal design of split-split-plot experiments. Biometrika 96(1), 67-82.
Ju, N., D. Hu, A. Henderson, and I.. Hong (2019). A sequential test for selecting the better variant: Online A/B testing, adaptive allocation, and continuous monitoring. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 492-500.
Kallus, N. and M. Uchara (2020). Double reinforcement learning for efficient off off-policy evaluation in markov decision processes. The Journal of Machine Learning Research 2/(1), 6742-6804.
Kallus, N. and M. Uchara (2022). Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. Operations Research 70(6), 3282-3302.
Kharitonov, E., A. Vorobev, C. Macdonald, P. Serdyukov, and I. Ounis (2015). Sequential 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.
12

---

Kong, X., M. Yuan, and W. Zheng (2021). Approximate and exact designs for total effects. The Annals of Statistics 49(3). 1694-1625.
Kosorok, M. R. and E. B. Laber (2019). Precision medicine. Annual Review of Statistics and its Application 6, 263-286.
Le. H., C. Voloshin, and Y. Yue (2019). Batch policy learning under constraints. In International Conference on Machine Learning, pp. 3703-3712. PMLR.
Leung, M. P. (2022). Rate-optimal cluster-randomized designs for spatial interference. The Annals of Statistics 50(5), 3064-3087.
Li, G., Y. Yan, Y. Chen, and J. Fan (2023). Minimax-optimal reward-agnostic exploration in reinforcement learning. arXiv preprint arXiv:2304.07278
Li, M., C. Shi, Z. Wu, and P. Fryzlewicz (2022). Testing stationarity and change point detection in reinforcement learning. arXiv preprint arXiv:2203.01707.
Li, X., P. Ding, Q. Lin, D. Yang, and S. Liu (2019). Randomization inference for peer effects. Journal of the American Statistical Association 114(528), 1651-1664.
Liao, P., P. Klasnja, and S. Murphy (2021). Off-policy estimation of long-term average outcomes with applications to mobile health. Journal of the American Statistical Association 116(533), 382-391.
Liao, P., Z. Qi. R. Wan, P. Klasnja, and S. A. Murphy (2022). Batch policy learning in average reward markov decision processes. The Annals of Statistics 50(6), 3364-3387.
Lim, V., E. Novoseller, J. Ichnowski, H. Huang, and K. Goldberg (2022). Policy-based bayesian experimental design for non-differentiable implicit models. arXiv preprint arXiv:2203.0422 042772.
Liu, Q. L. Li, Z. Tang, and D. Zhou (2018). Breaking the curse of horizon: Infinite-horize off-policy estimation. Advances Neural Information Processing Systems 31.
Liu, X., R.-X. Yue, and Kee Wong (2022). Equivalence theorems for and da-optimality for linear mixed effects models with applications to multitreatment group assignments in health care. Scandinavian Journal of Statistics 49(4), 1842-1859.
Liu, Y. and F. Hu (2022). Balancing unobserved covariates with covariate adaptive randomized experiments. Journal of the American Statistical Association 117(538), 875-888
Loux, M. (2013). A simple, flexible, and effective covariate-adaptive treatment allocation procedure. Statistics in Medicine 32(22), 3775-3787.
Luckett, D. J., E. B. Laber, A. R. Kahkoska, D. M. Maahs, E. Mayer-Davis, and M. R. Kosorok (2020). Estimating dynamic treatment regimes in mobile health using v-learning. Journal of the American Statistical Association / //5(500), 692-706.
Luedtke, A. R. and M. J. Van Der Laan (2016). Statistical inference for the mean outcome under possibly non-unique optimal treatment strategy. The Annals of Statistics 44(2), 713.
Maharaj, A., R. Sinha, D. Arbour, Waudby-Smith S. Z. Liu, M. Sinha, R. Addanki, A. Ramdas, M. Garg, and V. Swaminathan (2023). Anytime-valic valid confidence sequences in an enterprise A/B testing platform. In Companion P Proceedings of the ACM Web Conference 2023, pp. 396-400.
Mandel, T., Y.-E. Liu, S. Levine, E. Brunskill, and Z. Popovic (2014). Offline policy evaluation across representations with applications to educational games. In AAMAS, Volume 1077.
Mannor, S., D. Simester, P. Sun, and J. N. Tsitsiklis (2007). Bias and variance approximation in value function estimates. Management Science 53(2), 308-322.
Murphy, S. A. (2003). Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series (Statistical Methodology) 65(2), 331-355.
Nandy, P., Basu, Chatterjee, and Y. (2020). A/B testing dense large-scale networks: design and inference. Advances in Neural Information Processing Systems 33, 2870-2880.
13

---

Nandy, P., D. Venugopalan, C. Lo, and S. Chatterjee (2021). A/B testing for recommender systems in two-sided marketplace. Advances Neural Information Processing Systems 34, 6466-6477.
Pocock, S. J. and R. Simon (1975). Sequential treatment assigmment with balancing for prognostic factors in the controlled clinical trial. Biometrics 31(1), 103-115.
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Rainforth, T., A. Foster, D. Ivanova, and F. B. Smith (2023). Modern bayesian experimental design. arXiv preprint arXiv: 14545.
Ryan, E. G., C. C. Drovandi, J. M. McGree, and A. N. Pettitt (2016). A review of modern computa- tional algorithms for bayesian optimal design. International Statistical Review 84(1). 128-154.
Schlegel, M., W. Chung, D. Graves, J. Qian, and M. White (2019). Importance resampling for off-policy prediction. Advances in Neural Information Processing Systems 32.
Shi, C., S. Luo, H. Zhu, and R. Song (2021). An online sequential test for qualitative treatment effects. The Journal of Machine Learning Research 22(1), 13061-13111.
Shi, C., Z. Q. Wang, and F. Zhou (2023). Value enhancement of reinforcement learning via efficient and robust trust region optimization. Journal of the American Statistical Association accepted.
Shi, C., R. Song, W. Lu, and R. Li (2021). Statistical inference for high-dimensional models via recursive online-score estimation. Journal of the American Statistical Association 116(535), 1307-1318.
Shi, C., R. Wan, V. Chemozhukov, and R. Song (2021). Deeply-debiased off-policy interval estimation. In International Conference on Machine Learning, pp. 9580-9591, PMLR.
Shi, C., R. Wan, G. Song, S. Luo, H. Zhu, and R. Song (2022). A multi-agent reinforcement learning framework for off-policy evaluation in two-sided markets. Annals of Applied Statistics accepted.
Shi, C., X. Wang, S. Luo, H. Zhu, Ye, and R. Song (2023). Dynamic causal effects evaluation in A/B testing with reinforcement learning framework. Journal of the American Statistical Association 118(543), 2059-2071.
Shi, C., S. Zhang, W. Lu, and R. Song (2022). Statistical inference of the value function for reinforcement learning in infinite-horizon settings. Journal of the Royal Statistical Society Series B: Statistical Methodology 84(3), 765-793.
Shi, C., J. Zhu, S. Ye, S. Luo, H. Zhu, and R. Song (2022). Off-policy confidence interval estimation with confounded markov decision process. Journal of the American Statistical Association (ac- cepted).
Sverdlov, O. and W. F. Rosenberger (2013). On recent advances in optimal allocation designs in clinical trials. Journal of Statistical Theory and Practice 7, 753-773.
Sverdlov, O., Y. Ryeznik, and W. K. Wong (2020). On optimal designs for clinical trials: an updated review. Journal of Statistical Theory and Practice 14(1), 10.
Swaminathan, A. and T. Joachims (2015). The self-normalized estimator for counterfactual learning. Advances in Neural Information Processing Systems 28.
Tang, X., Z. Qin, F. Zhang. Z. Wang, Xu, Y. Ma, H. Zhu, and Ye (2019). deep value-network based approach for multi-driver order dispatching. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1780-1790.
Tang, 7., Y. Duan, S. Zhang, and I.. Li (2022). A reinforcement learning approach to estimating long-term treatment effects. arXiv preprint arxiv:2210.07536.
Thams, N. S. Saengkyongam, Pfister, and J. Peters (2021). Statistical testing under distributional shifts. arXiv preprint arXiv:2105.10821.
14

---

Thomas, P. and E. Brunskill (2016). Data-efficient off off-policy policy evaluation for reinforcement learning, In International Conference on Machine Learning, pp. 2139-2148. PMLR.
Tsiatis, A. A., M. Davidian, S. T. Holloway, and E. B. Laber (2019). Dynamic trealment regimes: Statistical methods for precision medicine. CRC press.
Uehara, M., J. Huang, and N. Jiang (2020). Minimax weight and q-function learning for off- off-policy evaluation. In International Conference Machine Learning, pp. 9659-966966 PMLR.
Uchara, M., C. Shi, and N. Kallus (2022), A review of off-policy evaluation reinforcement learning. arXiv preprint arXiv:2212.06335
Ugander, J., B. Karrer, L.. Backstrom, and J. Kleinberg (2013). Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 329-337.
Villar, S. S. and W. F. Rosenberger (2018), Covariate-adjusted response-adaptive randomization for multi-arm clinical trials using modified forward looking gittins index rule. Biometrics 74(1), 49-57.
Viviano, D. (2020). arXiv:2003.08421.
Experimental design under network interference.
arXiv preprint
Wan, R., B. Kveton, and R. Song (2022). Safe exploration for efficient policy evaluation and comparison. In International Conference on Machine Learning, pp. 22491-225111 PMLR.
Wan, R., Y. Liu, J. McQueen, D. Hains, and R. Song (2023). Experimentation platforms meet reinforcement learning: Bayesian sequential decision-making for continuous monitoring. arXiv preprint Xix::3344.00420
Wang. J., Z. Qi, and R. K. Wong (2021). Projected state-action balancing weights for offline reinforcement learning. arXiv preprint arXiv:2109.0400
Wang, Т. and W. Ma (2021). The impact of misclassification on covariate-adaptive randomized clinical trials. Biometrics 77(2), 451-464.
Wei, L.-J. (1977). A class of designs for sequential clinical trials. Journal of the American Statistical Association 72(358), 382-386.
Wong, W. K. and W. Zhu (2008). Optimum treatment allocation rules under variance heterogeneity model. Statistics in Medicine 27(22), 4581-4595.
Xie, C., W. Yang. and 7. Zhang (2023). Semiparametrically efficient off-policy evaluation in linear markov decision processes. International Conference on Machine Learning. PMIRR
Xu, Y. J. Zhu, C. Shi, S. Luo, and R. Song (2023). An instrumental variable approach to confounded off-policy evaluation. In International Conference on Machine Learning, pp. 38848-38888 38880. PMLR.
Xu, Z., Z. Li, Q. Guan, D. Zhang, Q. Li, J. Nan, C. Liu, W. Bian, and J. Ye (2018). Large-scale order dispatch in on-demand ride-hailing platforms: A learning and planning approach. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 905-913.
Yang, F., A. Ramdas, K. G. Jamieson, and M. J. Wainwright (2017). A framework for multi- A(rmed)/Bandit testing with online FDR control. Advances in Neural Information Processing Systems 30.
Yin, M. and Y.X.. Wang (2020). Asymptotically efficient off-policy evaluation for tabular reinforce- ment learning. In International Conference on Artificial Intelligence and Statistics, pp. 3948-394 3958. PMLR.
Yin, and Zhou (2017). Optimal designs for regression models using the second-order least squares estimator. Statistica Sinica 27(4), 1841-1856.
15

---

Yu, Y., C. Xu, J. Zhong, and S. H. Cheung (2022). Comparison of treatments with ordinal re- sponses in trials with sequential monitoring and response-adaptive randomization. Statistics in Medicine 41(5), 5061-5083.
Zhang. B., A. A. Tsiatis, E. B. Laber, and M. Davidian (2013). Robust estimation of optimal dynamic treatment regimes for sequential treatment decisions. Biometrika 100(3), 681-694.
Zhang, L.-X., F. Hu, S. H. Cheung, and W. S. Chan (2007). Asymptotic properties of covariate- adjusted response-adaptive designs. The Annals of Statistics 35(3), 1166-1182.
Zhou, Y., Liu, Li, and F. Hu (2020). Cluster-adaptive network A/B testing: From randomization to estimation. arXiv preprint arXiv:2008. 08648.
Zhu, H. and F. Hu (2019). Sequential monitoring of devariaee-daapiive randomized clinical trials.
Statistica Sinica 29(1), 265-282.
Zhu, H., Piao, J. Lee, E. Hu, and L. Zhang (2020). Response adaptive randomization procedures in seamless phase ii/iii clinical trials. Journal of Biopharmaceutical Statistics 30(1), 3-17.
Zou, S., T. Xu, and Y. Liang (2019). Finite-sample analysis for sarsa with linear function approxima- tion. Advances in Neural Information Processing Systems 32.
16


Reviews:
[{"review_id": "bbictHBgTP", "reviewer": "Reviewer_tKDd", "summary": "This paper considers A/B tests which are often employed for evaluating new products/treatments/policies against existing baselines. The goal is to study the optimal design of such A/B tests to maximize the information obtained and estimate treatment effect more accurately. The paper considers three possible settings governing how the data is generated: whether it follows an MDP or if it follows a time-varying MDP or a non-Markov process and presents an optimal allocation strategy for each. The paper tests these policies on a real-world sourced dataset pertaining to a ride-sharing company and shows that these approaches achieve better accuracy. Finally, the paper also establishes nice theoretical properties of these methods and derive an upper boudn for the MSE of the proposed estimator. \n", "questions": "– Please see concerns about potential weakness mentioned in above section. Additional question below: \n\n– While the results look good in Fig 4, etc. could there be cases where errors on some of the points in proposed algorithms are really large, even though for most points they are lower than the baselines? For example, are there cases where these estimates become unstable leading to exploding errors?\n", "limitations": "No negative social impact (other than pointed out in questions section)", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "– The paper studies an interesting problem that can be very useful in improving the efficiency of A/B tests that are commonly employed everywhere.\n\n– Paper is well-written. It also sufficiently talks about existing related work and distinguishes itself. \n\n– The key results in the paper are strongly grounded in theory and are supported by good results in the empirical section.  \n", "weaknesses": "– Could there be some imbalance in allocation of treatment leading to fairness issues? For example, to optimize sample efficiency, could the algorithm withhold treatment unnecessarily if the placebo group has high variance? That way it could put most of the people in placebo and almost none in treatment? Or similarly, if there is a negative treatment but with high variance, it could opt to allocate that treatment more often?  It is unclear if the algorithm guards against these issues. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* **Imbalance in Allocation.** This is an excellent comment. Indeed, a significant variance disparity between the two groups would inevitably lead to a marked imbalance in the treatment allocation. This is because in the design we proposed, the probabilities of treatment assignment are dictated by the ratio of the standard deviations of the two groups.\n  - **Imbalance unlikely to occur under weak signals**. However, in many real-world scenarios, the oracle treatment effect is relatively small. For example, in ridesharing platforms, the size of the treatment effect typically falls within a range of 0.5% to 2% (Tang et al., 2019, https://dl.acm.org/doi/pdf/10.1145/3292500.3330724). Given this modest treatment effect, it is reasonable to anticipate that introducing a new treatment will not drastically disrupt the system dynamics, resulting in outcomes with exceedingly high or low variances.\n  - **Burn-in diminishes the impact of imbalance**. Nevertheless, we understand the importance of tackling the issue of imbalance. To mitigate this problem, notice that our proposed algorithms consists of a burn-in period. During this period, both global policies are executed alternately over $2m_0$ days, independent of the variance ratio between the outcomes of the two groups. The impact of the imbalance is diminished as $m_0$ increases.\n  - **Additional approaches to address imbalance**. Meanwhile, there are other possible approaches to guard against the imbalance problem. One possible approach is to introduce a cutoff value for treatment allocation probabilities, avoiding extreme values and maintaining better balance. Specifically, truncation could be conducted when the estimated probability exceeds a certain threshold $p_1$ (e.g., $0.95$) or falls below another threshold $p_2$ (e.g., $0.05$). Furthermore, designating a minimum sample size, $\\tilde{n}$, for each group beforehand can foster better balance. Should the sample size for one group exceed $n-\\tilde{n}$, the subsequent days could be exclusively allocated to the other group, further reducing the risk of imbalance.\n* **Exploding Errors.**\n  - **Standard errors**. We greatly appreciate this helpful comment. In Tables 1-3 of the supplementary material, we have presented the MSEs of the estimated average treatment effect derived from our numerical studies along with their standard errors. By nature, a handful of significantly high MSEs can elevate the associated standard error. It can be seen from Tables 1-3 that our proposed method not only yield lower average MSEs, but also consistently produces smaller, or at the very least, comparable standard errors.\n  - **5-number summary statistics**. To provide a more comprehensive view, in Table 1 of the attached pdf file, we further give the 5-number summary statistics of the MSEs of the proposed estimators reported in Figure 4 of the main text. The findings from this table further reinforce that our proposed algorithms do not experience issues with exploding errors."}, {"review_id": "r3sBs5o54H", "reviewer": "Reviewer_WpTu", "summary": "The paper studies optimal treatment allocation aiming to maximize the obtained information from online experiments to estimate treatment effects accurately. The authors propose optimal allocation strategies in a dynamic setting. These strategies are designed to minimize the variance of the treatment effect estimator when data follow a NMDP or TMDP. ", "questions": "I have another minor question on the word “dynamic” in the title. Since the optimal allocation rule is $A_1=A_2=\\cdots=A_T$, I am not pretty sure whether it is still suitable to call it a \"dynamic\" allocation.", "limitations": "See previous comments.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem that the paper investigates is important, in my opinion. The paper provides an insightful paradigm that how reinforcement learning techniques can be effectively applied in experimental design/causal inference. The authors also did a great job on giving credits to RL literature.", "weaknesses": "1.\tThere are several very relevant papers in experimental design literature that needs to be discussed carefully, for example, Bojinov et al. (2022) and Farias et al. (2022). I think some insights and the designs in this paper are closely related to these two papers.\n2.\tFrom experimental design/causal inference literature, we may not only want to know an estimator of ATE, but also the corresponding confidence intervals for the estimators. I am wondering that whether the authors could have some comments on how to construct confidence intervals.\n3.\tThe definitions and relationships between $n$ and $T$ are a little bit confusing, especially when reading Section 2. I think some more descriptions on the relationship them will be helpful. From my understanding, the data structure looks very similar to “panel data” in the literature.\n\nReference:\n\nBojinov, I., Simchi-Levi, D., & Zhao, J. (2022). Design and analysis of switchback experiments. Management Science.\n\nFarias, V., Li, A., Peng, T., & Zheng, A. (2022). Markovian interference in experiments. Advances in Neural Information Processing Systems, 35, 535-549.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* **Related Work on Experimental Design.**  Thank you for highlighting these pertinent references! Regrettably, they were overlooked in our initial manuscript submission. Should our paper be accepted, we will certainly incorporate and discuss these references. Specifically:\n\n  - Bojinov et al. (https://doi.org/10.1287/mnsc.2022.4583) delved into optimal design in the context of regular switchback experiments, operating under the assumption of a singular experimental unit. Their method employed the Horvitz-Thompson estimator, more widely recognized as the importance sampling estimator, to estimate causal effects. This technique presumes the presence of carryover effects in a fixed chronological sequence. Contrarily, our suggested experimental designs cater to NMDP and (T)MDP models incorporating multiple experimental units. Moreover, we investigate doubly robust estimators, which not only exhibit semiparametric efficiency but also offer greater resilience compared to the importance sampling estimator. \n\n  -Farias et al. (https://proceedings.neurips.cc/paper_files/paper/2022/hash/03a9a9c1e15850439653bb971a4ad4b3-Abstract-Conference.html) presented an on-policy estimator, specifically designed for off-policy evaluation in dynamical systems experiencing Markovian interference. Their main focus was the effective estimation of the average treatment effect (ATE) using a predefined set of offline data. In contrast, our research pursues a unique angle. We delve into the optimal experimental design, aiming to curate offline data that reduces the variance of the ATE estimator.\n\n* **Confidence Intervals of the ATE Estimator.**\n\n  - This is an excellent comment! We totally agree that establishing confidence intervals for the ATE estimators holds significant importance. As elaborated further below, the derivation of a confidence interval for the proposed estimator is quite straightforward. Should our paper be accepted, we will make sure to include these discussions.\n\n  - First, let us consider the settings under NMDPs in Section 3. Recall that after generating data through the proposed experimental design, we utilize the online doubly robust estimator $\\widehat{\\textrm{ATE}}_1$ to estimate the ATE. A key observation is that, under certain regularity conditions, the proposed estimator is asymptotically normal. More specifically, we have\n        $$\\sqrt{n - 2m_0} (\\widehat{\\textrm{ATE}}_1 - \\textrm{ATE}) \\overset{d}{\\rightarrow} N(0, \\textrm{EB}_1(\\pi^{b*})).$$  This motivates us to consider the following Wald-type confidence interval\n    $$ [\\widehat{\\textrm{ATE}}_1- \\Phi^{-1} (1-\\alpha/2) \\sqrt{ \\textrm{EB}_1(\\pi^{b*})/(n - 2 m_0) },  \\widehat{\\textrm{ATE}}_1+ \\Phi^{-1} (1-\\alpha/2) \\sqrt{ \\textrm{EB}_1(\\pi^{b*})/(n - 2 m_0) }],$$\n    where $\\Phi^{-1}$ is the inverse cumulative distribution function of a standard normal random variable. It then suffices to estimate the asymptotic variance ${\\textrm{EB}}\\_1(\\pi^{b*})$ to construct asymptotically valid confidence intervals. Notice that the estimate  can be represented as an average of martingale differences $\\widehat{\\textrm{ATE}}\\_1= \\sum_{i=2m_0 +1}^n \\psi^1_i /(n - 2m_0)$  where $$ \\psi\\_i^1=\\sum_{a=0}^1\\frac{(-1)^{a+1}}{T} \\Big[ \\widehat{V}\\_{1,i-1}^a(O_1^{(i)})+ \\frac{\\mathbb{I}(A\\_1^{(i)}=a)}{\\widehat{\\pi}^{b*}\\_{1,i-1}(a|O\\_1^{(i)})}[\\sum\\_t R\\_t^{(i)}-\\widehat{V}\\_{1,i-1}^a(O\\_1^{(i)})]\\Big]. $$ We propose using the sample variance of $\\{\\psi^1\\_i\\}\\_i$ to estimate $\\textrm{EB}\\_1(\\pi^{b*})$. Similar to Theorem 15 of Kallus and Uehara (2022) (https://dl.acm.org/doi/abs/10.5555/3455716.3455883), we can establish the consistency of the resulting sampling variance estimator. \n\n\n   - For TMDPs, we can similarly establish the asymptotic normality of $\\widehat{\\textrm{ATE}}_2$, i.e., \n    $\\sqrt{n - 2 m_0} ( \\widehat{\\textrm{ATE}}_2 -  \\textrm{ATE} ) \\overset{d}{\\rightarrow} N(0, \\textrm{EB}_2(\\pi^{b*}) ) $. The corresponding $1 - \\alpha $ confidence interval can be constructed by\t\n    $$\n    \t[\\widehat{\\textrm{ATE}}_2- \\Phi^{-1} (1-\\alpha/2) \\sqrt{ \\textrm{EB}_2(\\pi^{b*})/(n - 2 m_0) },  \\widehat{\\textrm{ATE}}_2+ \\Phi^{-1} (1-\\alpha/2) \\sqrt{ \\textrm{EB}_2(\\pi^{b*})/(n - 2 m_0) }],\n    $$\n    where the unknown asymptotic variance $\\textrm{EB}_2(\\pi^{b*})$ can be similarly estimated via the sampling variance estimator. \n\n\n* **Definition and relationships between $n$ and $T$.**  We apologize for any potential confusions. You are correct! The data structure is similar to the panel data. We consider an experiment spanning $n$ days and each day is divided into $T$ time intervals. On the $i$-th day (i=1, $\\dots$ , n) and time interval $t$ $(t=1, \\dots, T)$,  the decision maker observes certain time-varying market features, denoted as $O_t^{(i)}$ (e.g., the numbers of incoming orders and available drivers in a ride-sharing platform) and chooses to implement one of the two policies. This action is denoted as $A_t^{(i)}\\in \\{0,1\\}$. By convention, $A_t^{(i)}=1$ indicates the implementation of a new policy, while $A_t^{(i)}=0$ signifies the use of the control policy. Afterwards, the decision maker receives an immediate reward $R_t^{(i)}$ and subsequently observes the next observation $O_{t+1}^{(i)}$. The observed data can thus be summarized as $\\{O_t^{(i)}, A_t^{(i)},  R_t^{(i)}, t=1, \\dots, T\\}_{i=1}^n$. We will add the related discussions, and make the definitions of $n$ and $T$ clearer shall our paper be accepted. \n\n* **Question about the title:** Thanks for your valuable suggestion! We will remove ``dynamic'' from our title shall the paper be accepted."}, {"review_id": "9IGrAaihML", "reviewer": "Reviewer_NJNM", "summary": "This paper studies optimal designs for allocating treatments so that treatment effects can be accurately estimated in online experiments. The focus of the paper is designing behavior policies for data generation to minimize the MSE of the ATE estimator when we know that dynamics may evolve through an NMDP, TMDP, or MDP.", "questions": "1. Can the authors discuss the choice to restrict the treatment assignment policies to class $\\Pi^{b}$? \n2. Is it possible to obtain good estimates of the ATE without requiring any burn-in period? (If not, it would be helpful to add a short comment on this to the paper.)\n3. Is a burn-in period used in the experiments? If so, how long was the burn-in period? (Can this be added to the main text?)\n", "limitations": "Yes.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "1. The paper studies the challenging and important problem of SUTVA violations in online experiments. Without accounting for these violations, the temporal carryover effects that occur due to sequential allocation of treatment in online experiments can yield biased treatment effect estimates.\n2. The authors consider an ambitious problem of designing optimal behavior policies when data generation evolves via NMDP, TMDP, or MDP.\n3. Although there are many works that focus on off-policy evaluation and estimation of treatment effects, not many of these focus on how to design the behavior policy to improve the efficiency of the policy value estimator (it is more common to assume that a fixed dataset, generated according to some prespecified or unknown behavior policy, already exists). \n4. The paper has a thorough and comprehensive related work section.\n5. The paper is clear and well-written.\n", "weaknesses": "1. In Section 4, when analyzing the optimal designs for the TMDP and MDP models, the choice to restrict the treatment assignment policies that are considered to the class $\\Pi^{b}$, the class of policies that randomly assign the first action and sticks with the same action for the rest of the trajectory, seems quite restrictive. In some sense, this removes some of the “dynamic” aspects of the original problem and greatly reduces the complexity of the problem.\n\n2. It seems like the burn-in period is quite essential to estimating the ATE with the proposed designs because proposed behavior policies randomly selects an action $A_{1}$ in the first time step and then sticks with it for the remaining time steps. As a result, if we didn’t have the burn-in period, we wouldn’t be able to estimate both $V_{1}^{0}$ and $V_{1}^{1}$. The importance of the burn-in period isn’t emphasized in the text and is worth commenting on (or at least citing references that burn-in periods are necessary for consistent estimation).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* **Choice of class $\\Pi^b$.**\n\n  - Many thanks for this constructive comment! First, we would like to clarify that it is an exceptionally challenging task to directly identify the optimal behavior policy $\\{   \\pi^b\\_t \\}\\_t$ in TMDPs/MDPs that minimizes the following efficiency bound for estimating the ATE,\n    $$\n    \\textrm{EB}\\_2(\\pi^b) = \n    \t\t{1 \\over T^2}\n    \t\t\\sum\\_{t=1}^T \\sum\\_{a \\in \\{0, 1\\} } \\mathbb{E}^{\\pi^b} \\Big[ { \\mathbb{I}(A\\_t=a) p^a\\_t ( O\\_{t} )  \\over p^b\\_t ( O\\_t,a )   } \\sigma\\_t( O\\_t, a) \\Big]^2+\\frac{1}{T^2}\\textrm{Var}[V\\_1^1(O\\_1)-V\\_1^0(O\\_1)],\n    $$\n    without any restrictions. The main challenge lies in that the marginal distribution function  $p^b_t ( O_t,a )$ cannot be conveniently expressed in a closed-form  function of $ \\pi^b_t$ because it  depends on $\\pi_t^b$ through a very complex mechanism. This introduces considerable difficulty in  obtaining the optimal behavior policy in a closed-form manner. \n\n  - Second, we clarify that we restrict the treatment assignment policies to $\\Pi^b$ for several reasons: \n    (i) The optimal design for NMDP resides in class $\\Pi^b$, and since both TMDP and MDP are subclasses of NMDP, we take advantage of this result and expect that the optimal in-class behavior policy that belongs to $\\Pi^b$ performs well in TMDPs/MDPs as well; (ii) Theorem 3 demonstrates that under certain conditions, the optimal design does belong to $\\Pi^b$, making the optimal in-class behavior policy globally optimal; (iii) Frequently alternating treatments can introduce significant carryover bias in policy evaluation, as noted in Hu and Wager, (2022) (https://arxiv.org/abs/2209.00197). Consequently, restricting our attentions to $\\Pi^b$ allows us to avoid distributional shifts between the behavior policy and the target policy, effectively mitigating the carryover bias.\n\n  - Third, while it may not be possible to express the globally optimal behavior policy in closed-form, it can still be computed numerically, even without restricting to $\\Pi^b$. For example, modern Bayesian optimal experimental design provides a powerful computational framework for optimizing the design of experiments (Blau et al., 2022, https://proceedings.mlr.press/v162/blau22a.html). However, this Bayesian approach is beyond the scope of our current proposal, which adopts a frequentist approach to derive the optimal design analytically. We will consider exploring the Bayesian direction in future work. We will add the related discussions shall our paper be accepted. \n\n* **The importance of burn-in period.**  This is an excellent suggestion! We totally agree that it would be undoubtedly helpful to discuss this point. During the rebuttal, we also conducted additional numerical experiments to empirically investigate the importance of the burn-in period. We will incorporate the related discussions, references and results shall our paper be accepted. \n\n  -  As you have commented, the burn-in period is used to derive reasonable initial estimators for the value function $V$ and the variance $\\sigma^2$. If there is available historical data, these parameters could be estimated from that data, potentially bypassing the need for a burn-in period in a new experiment. However, in the absence of any prior information, the burn-in period becomes crucial for beginning the experiment with reliable initial estimates, as shown in our numerical experiments below. We also remark that such a burn-in procedure is widely used in experimental designs where the treatment assignment mechanism is initially unknown (Zhu et al. 2020, https://doi.org/10.1080/10543406.2019.1657439). \n  -  To empirically explore the impact of the burn-in period, we have conducted additional experiments under the settings described in Example 5.2 of the current paper. \n     We set $n=50$ and $T=10$. Table 2 of the attached pdf illustrates the Monte Carlo averages of the MSEs for the estimated ATE. Standard errors are provided in parentheses. Various burn-in periods are denoted by  $2m_0$. As the table indicates, smaller burn-in periods (e.g., $2m_0=4$) result in larger MSEs for the estimated ATE. This suggests that inaccurate initial estimators of $V$ and $\\sigma^2$  can lead to unstable ATE estimators.  To the contrary, when the burn-in period is moderately large (e.g., $2m_0=16$ or $20$), the estimated ATE becomes more stable, with much smaller MSEs and standard errors. This experiment underscores the significance and influence of the initial burn-in duration.  \n\n* **The burn-in period in the experiments.** Thanks for this question! In the supplementary material, we present  more details about the experiments. In particular, we set $m_0$ to $n /4 $ in all the experiments. We will mention this in Section 5 of the main text shall our paper be accepted. "}, {"review_id": "V4aro9Rii6", "reviewer": "Reviewer_bgAF", "summary": "The paper designs methods for taking actions in multiple sequential settings (Markovian, time-varying Markovian, non-Markovian) to generate high-quality data for the estimation of average treatment effect.", "questions": "1. Theorem 1 and the implementation seems like an \"explore then commit\" type of a strategy seen in bandits. Is there any connection/parallels?\n2. No need for the number of days in Sec 2.\n3. It is not clear why running the two fixed policies sequentially one after the other cannot estimate ATE well. \n4. Maybe this is easy to see, but Theorem 1's pi* is not taking one of the actions at all (e.g., if A1 happens to be 1, then A2=A1... etc). If so, why would ATE be estimated well?\n5. If you are already able to estimate V_1^a in step 3 of Algo 1, can't you estimate ATE well at this point itself?\n6. Clarification question: From Theorem 1, it seems like we are picking one of the actions to run for T periods (or \"after burn-in\" in Alg 1) that has a higher estimated variance in the rewards it obtains. This seems like a natural thing to do to estimate ATE better. Please correct me if I am wrong here.", "limitations": "1. Hard to appreciate the optimal treatment strategy introduced in Sec 3, likely because the treatment is a bit terse and skips some useful discussion.\n2. The data collection strategy is agnostic to the estimator used later. Is there any further improvement to be had? It would be good to see comments on this, as the estimators are already known in the literature.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Focuses on improving ATE estimation by improving the data collection process, as opposed to improving estimators etc, which is a nice take on this problem.", "weaknesses": "None identified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* **Connections with bandits.** This is an excellent comment! In the following, we discuss the similarities and differences between  the \"explore than commit\" strategy  in the bandits literature and our proposal.\n\n  - **Similarities**: In the \"explore then commit\" strategy, a system initially navigates through a spectrum of alternatives in an exploration phase. Subsequently, based on the data gathered, it commits to the seemingly most promising option during the commitment phase. For reference, see Garivier et al. (2016, https://proceedings.neurips.cc/paper/2016/hash/ef575e8837d065a1683c022d2077d342-Abstract.html). Our proposed experimental design resonates with this approach. The burn-in period can be likened to the \"exploration\" phase where treatments are alternately assigned to accumulate preliminary data. Post this period, the algorithm decisively adopts the optimal design, aiming to reduce the MSE of the ATE estimator.\n\n  - **Differences**: While both strategies share conceptual similarities, their specific objectives and implementation nuances vary considerably. The \"explore then commit\" strategy is tailored to maximize the cumulative expected reward over a period, whereas our method is centered on achieving the most precise ATE estimation.\n\nSection 2 - Number of Days: Your insightful recommendation is appreciated! We intend to omit this detail from Section 2 and introduce it within the Implementation subsection of Section 3. \n\n* **Estimate ATE based on two fixed policies running sequentially.** Thank you for highlighting that! Indeed, executing the two fixed policies in sequence can produce consistent ATE estimators. Nonetheless, this resulting estimator might be vulnerable to carryover bias as described by Hu and Wager (2022, https://arxiv.org/abs/2209.00197). Furthermore, it's less efficient compared to the estimator derived from our proposed design, which is crafted to minimize the MSE of the ATE estimator.\n\n* **Reason for well ATE estimates under Theorem 1.** Apologize for the confusion! Although the proposed optimal behavior policy $\\pi_1^{b*}$ selects the same action within each day, the experiment extends over a total of $n$ days and the first action is randomly chosen from $\\{0,1\\}$ according to $\\sigma_*$ (see Equation 2). Hence, the two policies will be implemented over approximately $\\Omega(n)$ days on average, ensuring consistent estimation of the ATE.\n\n* **Estimate ATE in step 3 of Algo 1.** Many thanks for the valuable comment! Although we can estimate $V\\_1^a$ and ATE in step 3 of Algorithm 1, it only uses data collected from the first $2 m\\_0 $ days. Since the experiments last for $n > 2 m\\_0$ days, our proposal uses all  the data to estimate ATE, which is more efficient.\n\n* **Clarification on Theorem 1.** You've hit the nail on the head! In Theorem 1, we allocate the action with a greater estimated variance a higher likelihood. This concept is inspired by similar strategies found in the design of clinical trials, as exemplified by Yin and Zhou (2017, https://www.jstor.org/stable/26384103). Yet, as mentioned in the introduction, the majority of current literature focuses on single-stage studies. Our proposed work broadens this concept to a dynamic context, where treatments are sequentially assigned over time. \n\n* **Optimal treatment strategy in Sec 3.** We sincerely apologize for any confusion and the lack of clarity. To address your concerns, we provide a non-technical summary of our proposal.\n\n  - **Objective:** Our focus is to explore the optimal dynamic treatment allocation strategy for collecting experimental data spanning $n$ days, each containing $T$ time intervals. The goal is to maximize the information (i.e., to minimize the MSE) of the ATE estimator derived from this collected dataset. \n  - **Optimality Criterion:**  To maximize the estimation accuracy, we focus on the class of semiparametrically efficient estimators, whose MSEs attain the semiparametric efficiency bounds.  Hence, it suffices to identify the optimal behavior policy based on which the generated experimental dataset yields the smallest semiparametric efficiency bound. \n  - **Optimal Design:** Theorem 1 derives the optimal behavior policy $\\pi^{b*}$. For each day, $\\pi^{b*}$ randomly allocates the initial action with probabilities proportional to $\\sigma_*$,  the standard deviations of the cumulative rewards, and the same action is repeatedly assigned afterwards. \n  - **Implementation.** In real practice, $\\sigma_*$ under the two global policies are unknown. We propose to use data collected so far to adaptively estimate $\\sigma_*$. Specifically, we run each global policy for $m_0$ days to generate the data. Then we estimate $\\sigma_*$ using the data collected so far and plug-in these estimators into $\\pi^{b*}$ to generate the experimental data. \n\n* **Further improvement on the estimator.** Thank you for this insightful comment! The proposed ATE estimator and the doubly robust estimator by Kallus and Uehara (2020, https://dl.acm.org/doi/abs/10.5555/3455716.3455883) do exhibit differences. \n  - **Methodologically**, we estimate the ATE in an online manner (see Equation 4). One notable distinction is that the nuisance functions are computed during the data collection process using the data collected so far, and are independent of the data used to construct the policy value. Such a forward type cross-fitting procedure enables us to circumvent the need to impose certain metric entropy conditions (Diaz, 2020, https://academic.oup.com/biostatistics/article/21/2/353/5631845).  Meanwhile, it improves upon the doubly robust estimator in that our estimator's inherent design allows for online computations, negating the necessity to store all historical data.\n\n  - **Theoretically**, we delve into the statistical properties of the proposed online ATE estimator, establishing finite sample error bounds for its MSE. "}]

Author rebuttal:
* We greatly appreciate all the reviewers' critical assessments of our work, many of which will lead to a more readable and self-contained version of our paper. We have worked very hard to address all comments and concerns, all discussions will be incorporated if our paper gets accepted.

* Rebuttals to specific comments are given in separate rebuttals to each review point by point. The attached pdf file contains two tables. Table 1 gives the 5-number summary statistics of the MSEs of the proposed estimators reported in Figure 4 of the main text. Table 2 reports the Monte Carlo averages of the MSEs with the estimated ATE, along with the corresponding standard errors in parentheses, with different burn-in periods.

* Thanks again for all the reviewers' insightful questions and feedback, which have helped us clarify and strengthen the foundations of our work. We hope our response clarified/addressed your questions about our paper. 

Meta-review: All reviewers recommend to accept this paper due to the following strengths:
* relevant and challenging problem
* clarity of the presentation 

Despite initial concerns on the impact of the contributions, the reviewers believe they are significant after rebuttal and discussions. We encourage the authors to update their paper to reflect these discussions in their final version.
Decision: Accept (poster)