Non-stationary Experimental Design under Linear Trends
Authors: David Simchi-Levi
Chonghuan Wang
Zeyu Zheng
Venue: NeurIPS 2023 poster (2023)
Keywords: Adaptive Experimental Design
Non-stationary
Online Learning
Treatment Effect

Abstract: Experimentation has been critical and increasingly popular  across various domains, such as clinical trials and online platforms, due to its widely recognized benefits. One of the primary objectives of classical experiments is to estimate the average treatment effect (ATE) to inform future decision-making. However, in healthcare and many other settings, treatment effects may be non-stationary, meaning that they can change over time, rendering the traditional experimental design inadequate and the classical static ATE uninformative. In this work, we address the problem of non-stationary experimental design under linear trends by considering two objectives: estimating the dynamic treatment effect and minimizing welfare loss within the experiment. We propose an efficient design that can be customized for optimal estimation error rate, optimal regret rate, or the Pareto optimal trade-off between the two objectives. We establish information-theoretical lower bounds that highlight the inherent challenge in estimating dynamic treatment effects and minimizing welfare loss, and also statistically reveal the fundamental trade-off between them.

Non-stationary Experimental Design under Linear Trends
David Simchi-Levi 18, Chonghuan Wang 8, Zeyu Zheng
8 Institute for Data, Systems, and Society, Department of Civil and Environmental Engineering, Operations Research Center, MIT
Laboratory for Information and Decision Systems, MIT
Department of Industrial Engineering and Operations Research, University of California, Berkeley dslevi @mit. edu, chwang9 amit. edu, zyaheng@berkelle..eer
Abstract
Experimentation has been critical and increasingly popular across various domains, such as clinical trials and online platforms, due its widely recognized benefits. One of the primary objectives of classical experiments is to estimate the average treatment effect (ATE) to inform future pocisiin-makinng and many other settings, treatment effects may be non-stationary, meaning that they can change over time, rendering the traditional experimental design inadequate and the classical static ATE uninformative. In this work, address the problem of non- stationary experimental design under linear trends by considering two objectives: estimating the dynamic treatment effect and minimizing welfare loss within the experiment. We propose an efficient design that can be customized for optimal estimation error rate, optimal regret rate, the Pareto optimal trade-off between the two objectives. We establish informmtiionthhorreee the inherent challenge in estimating dynamic treatment effects and minimizing welfare loss, and also statistically reveal the fundamental trade-off between them.
However, healthcare
lower bounds that highlight
Introduction
Experimental design plays a critical role in conducting research across various fields including clinical trials (see, e.g., (75), 14, (69) and online platforms (see, e.g., [52] T. 44 2T)). It enables the evaluation of the effectiveness of treatments. interventions, or policies in a rigorous and systematic manner, protecting the safety and well-being of participants and the wider population. Typically, one of the primary objectives of conducting experiments is to estimate the average treatment effect (ATE), which represents the difference outcomes between different treatments or controls. The outcomes of each treatment are assumed to be stationary by default (see, e.g., [48] ) ensuring that the information collected and conclusions drawn from in-experiment periods are informative for future decision-making However, in some situations, ATE may be non-stationary, meaning that it evolves over time. Here, we present one illustrative example from clinical trials to highlight the importance of considering non-stationarity in ATE estimation.
Malaria has been one the world's deadliest diseases, with approximately 247 million cases and 618 thousand deaths reported in 2021 according to the World Health Organization (WHO). Antimalarial drug resistance in Africa has been highlighted by the world malaria report (see, [86] as one the global key events of malaria control and elimination efforts in 2021-2022. P. falciparum, the deadliest species of Plasmodium that causes malaria in humans, has shown resistance to first-line treatments (AS-AQ), artesunate- pyruuatrt--yonnidiiiee
such as artemether- lumerfarrinum (AL., irresunate-amodiagee (AS-PY), and dihydroartemisinin pawprrmmiiiiiiiippppauuuee piperaquine (DHA-PPQ) Africa recently. Alarmingly, least four recent studies have reported treatment failure rates greater than 10% after treatment with AL
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in Burkina Faso (see, [35] and Uganda (see, 19I).. Two study sites in Burkina Faso also reported treatment failure rates greater than 10% after treatment with DHA-PPQ. These alarming findings underscore the importance of understanding and estimating how the treatment effects evolve over time, i.e., how rapidly drug resistance escalates. Failure to account for non-stationarity in treatment effect may lead to suboptimal treatment plans, harming social welfare.
Given the ubiquity of non-stationarity, ignoring such a structure can lead to mis- leading information and poor decision- making. Figure [ provides an illustrative example where statiiotton can be well captured by linear models. If we use traditional randomized control trials and classical estimators based on sam-
Treatment
Control
Expocted reward
ATE estimalor without considering the stalionarity
ple averages without considering non- stationarity, we may conclude that the treatment is always better than the con- trol. However, the linear non-stationarity implies that we need to pay more atten- tion since the treatment outcomes de- crease much faster than the control. This means that the treatment does not always outperform the control during the after-experimental periods. In the context of the drug resistance example, this phenomenon can be interpreted as follows: new treatment may have significant positive effect during the experiment, but drug resistance develops much faster than the control. Therefore, we cannot always rely on the treatment after the experiment. Understanding how treatment effects evolve over time is thus crucial for making informed decisions.
Allas AllsExxciinntal Peins
Time
Figure 1: An illustrating example of the non-stationarity.
In this paper, we focus the challenge of designing experiments in non-stationary environments. To tackle this problem, we first need to answer the question of how to formulate non non-stationarity. there is underlying structure to the non-stationarity, such when outcomes malicious adversary, then it is not justifiable to conduct experiments because there is little information that we can infer for future decision-making In this work, we limit attention scenarios where potential outcomes follow structured trends. Specifically, we consider situations where outcomes linear with time, which provides suitable starting point for research experimental design under non-stationarity. Such structures also help us to determine meaningful metrics to use instead of the traditional static ATE, since it is longer informative enough in non-stationary environments. While other ways to formulate non-stationarity can be found in the literature (e.g.. [15). [16], [24).
determined by
10 (6)). we carefully argue in Section that these traditional formulations may not suffice for our purposes.
In addition to metrics related to the treatment effect, non-stationarity can also increase attention to the welfare loss issue during experiments. Specifically, every time a suboptimal treatment is assigned, there is welfare loss the unit could have been treated better with the optimal treatment. In stationary environment, this welfare loss remains constant over time. However, non-stationarity can lead to an increasing welfare loss over time. Thus, it might not be ideal ignore the welfare loss during the experiment, particularly when the in-experiment periods are not negligible compared the after-experiment periods. In this work, also aim address how to control welfare loss during experiments and explore the relationship between minimizing welfare loss and maximizing the statistical power of estimating the dynamic treatment effect.
1.1 Main results and contribution
The primary contribution of this work is the presentation of a framework that enables experimenters and researchers to design reliable, efficient, and flexible experiments in structured non -ta-ttationary environments. To the best of our knowledge, this is the first study of the dynamic treatment effect in the experimental design literature, extending the classical static ATE. We believe that this work could serve as a starting point for further research designing experiments in non-stationary environments.
We examine what is arguably the most foundational scenario, where the expected potential outcomes of each treatment are represented by linear functions of time In this context, the dynamic treatment

---

effect can be described by linear function as well. We introduce flexible experimental design framework that draws upon the well esllbestablished principle of Optimism the Face of Uncertainty from the online learning literature [29 [2] Our design can be readily customized to suit various notions of optimality. Specifically, this work, we systematically explore optimality from three distinct perspectives: optimal estimation error rate, optimal regret rate, and Pareto optimality.
The optimal estimation error rate design maximizes statistical power for inferring dynamic treatment effects. We establish a lower bound of _ for the error rate of any estimator, where vT
T is the total experimental horizon length. Our design achieves this lower bound by selecting appropriate input parameters. The optimal regret rate design minimizes in-experiment welfare loss (regret) in the worst case scenario. Traditional regret analysis techniques not applicable due to unbounded outcomes. Our design achieves an vT upper bound for regret rate by selecting input parameters, matching the worst-case lower bound. Linear non-stationarity in our problem may result in regret rate of T without careful design, unlike the stationary setting where regret is bounded by T. The Pareto optimal design strikes an optimal and flexible balance between the two objectives of maximizing statistical power and minimizing regret. We reveal the inherent and fundamental trade-off between these objectives statistically. Specifically, among all designs that can ensure a regret upper bound of T the smallest error any estimator can achieve is T 4 in the worst case. Conversely, among all designs that can guarantee an error bound of T 4, a regret of order T is unavoidable. Our design achieves different levels of trade-off by flexibly selecting input parameters.
1.2 Literature Review
Inference under non-stationarity. Considerable literature focuses on inference and picisionnmaking under statttattinnrtty.... One area is the inference for non-stationary Poisson processes [3] [3]. [39] is relevant as they establish statistical inference models for non-stationary arrival models with linear trends. [8] shows that ignoring -on-stationarity can lead inefficient or invalid A/B tests. They propose a new framework for statistical analysis of non-stationary A/B tests.
Decision-making under non-stationarity. This work relates to adaptive decision-making in non- stationary environments. Existing literature has two main streams. The first stream focuses on budget-based drifting environments, where changes are dynamically and adversarially made within a (17
[7] [4]66]] (24] (0). The second stream considers piecewise station- ary/switching environments, with adaptive assignment policies designed for various bandit settings 61
variation budget [T5]
89 I8) However, these formulations lack the knowledge transferability to exprrmexpeii periods, which is essential for our purpose. Recent studies address bandit experiments with non- non-stationary contexts (70). provide information -theoretic analysis [65], pro- pose improved algorithms (59), and define non-stationary bandits more rigorously (60). Moreover, various bandit models consider specific non-stationary reward structures, such as recharging ban-
10 36 58 22
47
dits [5T 190 (66), restless bandits (85) 8T (4). blocking bandits [13 [2] 20 [] rotting bandits
[56] 71) and rising bandits [64] In operations, assortment decisions under non non-stationarity
are studied (34), as well as pricing with evolving demands [50] [99]. [89] study the recommenda-
tion problem. Recent work extends bandit analysis to reinforcement learning 62 97 25
Some
works focus on optimizing with full feedback 226 16 43
Adaptive Experimental Design. Multi-armed bandit is an efficient paradigm for adaptive experi- ments 77 9 78 and 3 apply diffusion asspiiootttmm analysis to study randomized experiments, including bandit problems. (88 consider experimental design for choosing the best arm with arriving units in waves. (30 integrate adaptively weighted doubly robust estimator into Thompson sampling. incorporate synthetic control into MAB for interference scenarios. [73] also investigate the trade-off between regret and causal inference using Pareto optimality. Non-stationarity that we consider here greatly impacts Pareto optimality structure and reveals stochastic bandit as special case. 41 design a two-stage experiment for ATE estimation.
32
[6] model adaptive assignment as a Markov decision process, highlighting suboptimality of RCTs. (49) propose sequential testing framework with finite and infinite sample analysis. (87 consider an optimization problem in adaptive experiments. [8 transform experimental design with temporal interference into Markov decision problem.
experimente [99 optimize subject allocation for ATE estimation precision. [95] address adaptive
experimental design for sequential unit assignment with heterogeneous covariates.
Post-experiment Inference. There is substantial literature on post-experiment inference from logged adaptively collected data where adaptive experiment data is a typical example. One of
3

---

the central tasks along this line is the evaluation of a new policy given historic data (see, e.g., [T] 76 [7
92 (98). [23] provide procedure to adopt bootstrap on the data collected by bandit to debias the sample means. [40] construct confidence intervals for policy evaluation, including ATE, adaptive experiments, Works along this line usually impose some "overlapping" assumptions on the data collection process. Since we are jointly considering the experimentation and the inference, such an overlapping assumption may harm the welfare gained within the experiment.
83 46
Finally, we remark that the full version of this paper (containing additional theoretical results, extensions, and missing proofs) is available at ittpps://sstt http:/sssscccmaaaaaeese abttract
Experimental Design with Linear Trends
2.1 Formulation
We establish the formulation of our non non-stationary experiments with a finite set of arms A. Without loss of generality, we focus on A {1. 2} representing treatment and a control. The total length of the experiment is denoted as T. At each time t E [T the environment generates potential outcomes (a) for each arm A. The chosen arm a determines the observed outcome r; = (a())). Our study focuses on non-stationary experiments with linear trends, specifically considering the follows,
Tt (a) = 0a.0 + 0a,1 + Ea, == 0% ((t) + Ca.t.
(1)
where (1) = (1.1)T, O, E IR is fixed throughout the experimental horizon T but unknown to the decision maker. For specific arm a, (Ee,ch21 are independent and identically distributed (i.i.d.)
mero d..-su--Gann --suu--aaussinn random variables (I.v's) i.c., B[e I exp(X2o for any X E IR For simplicity, we also assume for dn 00 oo for all a. Note that while 0, remains fixed, the distribution of the reward of arm a, Tr(a), evolves over time, thereby satisfying the definition of non-stationarity outlined in [60]. Another mild assumption we make is the boundedness of 0z, i.e. ||@a]| < S for all a E A. which is commonly used (see, e.g., (27). 22. and (55). A non-stationary experiment instance with linear trends can be denoted by (P1, P2), where P. is the distribution of the rewards of arm i. The optimal arm at time is the one with the maximum expected reward, which is denoted by a arg A A 0,,0 + 1,,14, 1,, and thus is also unknown and may even change over time. The dynamic treatment effect can be fully captured by the column vector 02 == 01 02 E R². Denote all non-stationary experiment instances with linear trends to constitute a feasible set E₁.
At every time t, the decision maker observes the history H4-1 (a1, ri. (4-1. An admis- sible design π [ J1>1 maps the history H4-1 an action ag- We use the traditional accumulative regret to measure the efficiency of online learning, defined as the difference between the expected re- ward under the clairvoyant optimal policy and the policy π, i... (T) = Σ Poz o(t) -la, e(t) Note that R5 (T) is still a random variable because {ax ho21 1 are still random. Similarly, an admissible estimator 0, of the treatment effect at time maps H4 an estimate of 6,. The quality of the estimator can be measured by the norm of the difference between 0 and 9,, for example, the l nnrm ||0, - 0./l1. The design of experiment includes designing n (i.e., how to make an adaptive assignment decision) and 0. (i.., how to conduct causal inference).
Remark 1: Linear trends, admittedly, is a strong assumption, but they have proven to be highly useful for understanding and predicting certain phenomena across various fields. 82 observe a linear trend in the prevalence of obesity and overweight among US adults, based on national survey data collected between 1970s and 2004. This linear trend served as a benchmark for predicting the prevalence from 2004 to 2050, influencing numerous epidemiology studies. (37] conduct a study
monitoring and predicting the California sea otter population using linear trends observed in acrial surveys, showeasing the usefulness of linear trends in ecological studies. [68] reveal linear trend in the integrated water vapor content based on a 10-year ground-basse -bseed GPS data, highlighting the application of linear trends in atmospheric research
Remark 2: The traditional multi-armed bandit problems are primarily focused on designing л to have minimal regrets (see, e.g., (55).. However, in our design, we have an equally important task of designing lr. Furthermore, we outline the unique challenges and opportunities we face compared to the stochastic bandits and contextual bandits studied in the current literature.
'Throughout this paper, define [n] f1,-.- n), a b max(a, bj for a, b E IR and ||lll := Vu V u for the positive definite matrix V.

---

(Ere[[T=]) ((T))(t)T) Exe[[r-]] rio(t), where [[TC] denotes the of all the odd numbers that are no larger than T The final estimate of O2 is as we Our problem encompasses the well-studied stationary stochastic multi aumti--rmmed bandit problem (e.g.. [4] 9 by setting fa,1 0 in Eq. ① for all .A. The non-stationary structure introduces new challenges, such as the possibility of the optimal action varying over time, requiring additional in Eq. ( can be seen as a special kind of context connecting our problem to the contextual bandit problem (e.g., (27)) the first difference lies in that the context (1,t) is fixed and known at each time period. However, a challenge arises as we can no longer assume the context (1,t)T to be bounded, as commonly done in the literature. Some works assume the 22-norm to be no larger than a universal constant, say 1 (see, e.g., [27] and (24).. straightforward solution address this issue may involve relaxing the bound of the context to VT² +1 if the experimental horizon T known in advance. However, such a relaxation might be too loose, particularly when analyzing regret upper bounds. A more thorough discussion on this relaxation is deferred to the next subsection when we analyze the regret of our new design.
efforts to control the regret. Second, while (1, t) TT
2.2 Design of Experiments with Linear Trends
We present our design called Linear Exploration and OFU (L-EOFU) design in Algorithm [| The term OFU refers to the well-known principle of Optimism in the Face of Uncertainty, which arises from and has been widely adopted in the multi-armer bandit literature (see, e.g., [29] [ and their
follow-ups). For brevity, we use the notation L-EOFU (x) to emphasize the crucial input parameter a, whose role will become evident in the subsequent discussion. Our design operates manner: the exploration phase and the OFU phase. We now elaborate on each phase in detail.
two-phase
The exploration phase is the first steps of our design, which lasts for approximately T periods. The parameter a plays a crucial role in controlling the length of this phase. During this phase, our L-EOFU algorithm deterministically alternates between playing arms 1 and 2. In Algorithm choose to play arm when the time index 1 is odd and arm 2 when is even. This deterministic approach preserves the independence between the collected data. By the end of this phase, the decision-maker obtains approximately I independent samples for each arm, although these samples may not be identically distributed. L-EOFU will utilize the data collected during this initial phase to produce an estimator for the treatment effect, denoted 8/. (l--20PU(a)) in line of of the algorithm. Specifically, we estimate 02 and 02 separately by regressing the rewards against the time t using the data collected up to time T i.e., (1-EOF((a)
01. (L--0OP((a) 01 (L-UU))((a) 02. BDFU(a) While the estimator we use may be sample-inefficin
do not utilize the T - T samples in the second phase, we will show in the next subsection that the data collected in the first stage is sufficient achieve rate-optimal estimator of the treatment effect. Intuitively, if one arm consistently outperforms the other, most of the data in the second phase comes from the optimal arm, with fewer observations from the suboptimal arm. Thus, observations from the suboptimal arm are mostly obtained during the first stage. Moreover, the bottleneck for estimating the treatment effect very likely determined by the arm with the fewest observations, which is typically the suboptimal arm. Although we discard much data from the optimal arm when conducting inference, the bottleneck is still the suboptimal arm whose most information will be collected through the first phase. Additionally, we choose not to use all the data since adaptively collected data in the second stage can harm the independence of the data, leading to undesirable statistical properties such as bias. This issue has been pointed out in a large body of recent work [67] 993 23 Formally, we have the following Theorem @arremm@chaaac characterizing the properties of the estimator we choose.
Theorem Assuming T 2 4, for any V E E,, there exists a constant e1 > O such for any > 0.
with probability at least 1 e, 0/. ()--0000(n)) 0u|| S TT-8 Vlog 8, where e1 = 128 (a1 V oz).
03- 0, 9T-
Moreover, we have maxveE; E.
Our assumption that T 2 4 aligns with our intuition that a minimum of two samples per arm is required to identify linear structure. Theorem 1 demonstrates that the bound 7 decreases as increases, indicating that a longer exploration period leads to better estimation of the dynamic treatment effect. When a is set to 1, we conduct pure exploration throughout the entire experimental horizon, similar to the well-known switchback experiments [2I]. In this case, the estimation error can be controlled to the order of 0 O(1/VT), which aligns with traditional statistical results of linear regression (79]. Moreover, our analysis can be extended to any 4p norm, with only slight variations
5

---

Algorithm 1: Linear Exploration and OFU (L-EOFU)
Input: Controlling parameter o, instance parameters: da for all a (1,2), 7,8,6
Initialization: À = 1, D1.0 D2.0 Di. D1,r 0. o()) = (1,-)
for 1,,,-1, [1=] do // Phase
Exploration
Select A, if is odd: otherwise select Ar 2;
Observe reward r+;
DA.. +- D U {(o(tt) and DA.TT DA,T ((o(t),
end for
for
[T + [ + 2.... T do Phase 2: OFU
Va. E(SO).NER.. (1))(11) + a (1,2):
Na. 0ay² 2log( Vdde/Ve,,) " + X for a {1,2}
10
11
dar = Val E(OEE) ri((i) for a E {1,2]:
Re(a) =d, + Na )a (1)l for E {1,2);
12
13
Select A: arg max.c (1,2) Re(a):
14
Observe reward rt;
15 DA..I + DALT {(o(t),re))
end for
J (- = (( ((1)p(1) "EEEOO) ro((1) for (1,2);
Output: 02 EOFU() ()ppor(()) (L-00)()))
2.T
in the constant C1. Additionally, note that the high probability bound can be used for constructing confidence intervals and conduct hypothesis testing.
The second phase of our L-EOFU follows the OFU prin- ciple. Specifically, at each time period f, L-EOFU calcu- lates an optimistic estimate of the rewards for each arm, denoted as (a) in line 12 This estimate is referred as optimistic because, with probability at least 6, for all [T] and
Amn 1
Arn
Expocted swoad
(1,2), (a) (lt) Ya.e (t.))l<(t)lll= 2 0 ((t) (a)), where Ya,t S oa(v12 112 (T) - 2 log 1og(4.5X0) + x) and by de- fault, À is the standard techniques outlined in Theorem 2 of (2]. Based the optimistic estimation, L-EOFU selects the arm with the highest optimistic estimated value. The OFU principle has been shown strike delicate bal- ance between exploration and exploitation in the bandit literature [ one of the challenges in our problem is the possibility of the optimal arm changing over time. The OFU principle has an additional advantage in that it can automatically and implicitly detect when the optimal arm switches from one to another. To illustrate this, Figure ] an example of how OFU behaves when the optimal arm switches. Initially (before (3), arm outperforms arm According to L-EOFU, we continue to play arm 1, resulting in a relatively fast shrinkage of the confidence interval for the estimated values of arm 1. Conversely, for arm 2, the confidence interval even expands as (() increases magnitude. As time approaches (3, the difference between arm and arm 2 gradually diminishes. At time period t3, the optimistic estimation of arm 2 surpasses that of arm 1, prompting L-EOFU to start playing arm This addresses the challenge mentioned earlier. The following theorem presents the regret upper bound.
be 1. The proof of this claim follows
Time
Figure 2: An illustrative example on OFU,
As mentioned carlier,
Theorem For any & and 0 < a S with probability at least
41+2
R.. RL-F (T) +A(0 voo
- 2 blog(4.58)) \
In In(2)),, (2) 2 VT).
where X is initialized as I. Furthermore, 5 = 1/T leads to E(R 1-
(T)
Equation (2 can be decomposed into two terms: 2 term and a (I)(TT term. The first term arises from the exploration stage, Σ (a) intuitively. The second term is result of the

---

OFU phase. Only when 2 1 does the first term dominate the second term. In fact, there is little motivation for decision maker choose 7. will discuss in detail in the next subsection. For pure theoretical interest, the regret behavior in the region around a = 0 could be studied by choosing a 1/In (n))), given that there is an in the denominator. For those familiar with the bandit literature, similar ((VTIn(T) bound be obtained in the stochastic contextual bandit setting 2 As we mentioned before, one possible approach to reduce our problem to the one in 2 is by treating e(t) as a special kind of context. However, a key difference is that the context in is assumed to be bounded by a constant, whereas in our setting, the bound should be v1 + T if we know T in advance. Consequently, to apply all the techniques from (2). X in Equation 2 should be chosen as ( instead of 1. However, such a choice of À would yield a regret bound of (T)) which is significantly weaker than the (VV)) regret we derived. Furthermore, in the stochastic contextual bandit setting, where everything is assumed to be bounded, the regret can always be upper bounded by O(T) for any policy, and thus only sublinear regrets are meaningful. However, here, with the linear trend, the largest possible regret for policy without careful design can be on the order of (TT)) Thus, the O(T²2) regret bound is still informative even if 1/2 < a < 1.
Another important point to emphasize is that although the regret can be decomposed into two terms, does not mean that we can analyze each phase independently of the other. The T samples we collect from the first stage play a crucial role in our analysis for the second phase. This is evidenced by the fact that a not only appears in the first term, but also takes effect in the second term by a non-trivial way. Specifically, the regret of the second phase can be upper bounded by the sum of the length of the confidence interval at each time, i.e., the regret at time & can be bounded by 2x [1()(()) TA + 27 [l)())lv TA where Va, is defined to be E (i))((t))TTTa + Al. The 7 samples collected in the first stage are efficient in controlling the minimum eigenvalue of Va,t and thus be useful in controlling the magnitude of the regret.
In addition, we would like to compare our two-stage design with the traditional exploration- -thnn exploitation design (55) The similarity between the two lies the fact that the first exploration phase provides valuable information for future decision-making, as we discussed earlier. However, the key ppplooationnthee-xxllieeeee then-exploitation typically only exploits the information gathered during the first exploration phase and does not continue to learn new information during the second phase. In contrast, our L-EOFU algorithm continues to and has to learn throughout the entire learning period, since the environment may rapidly evolve over time. Moreover, the exploration phase in L-EOFU also plays an important role in conducting causal inference. Therefore, when designing the length of the first phase, must consider not only the regret but also the quality of causal inference. One reason why we move away from the exploration then-exploitation method is that may not always guarantee the optimal regret rate. Another important motivation for conducting pure exploration first is that the cost of exploration may increase linearly with time.
difference is that exploration-
2.3 Optimality of The Design
In this subsection, we will examine the optimality of our L-EOFU design from three different perspec- tives. Firstly, we will consider two extremes where the decision maker is solely concerned about either the estimation error of the dynamic treatment effect or the regret. Subsequently, when jointly considering the two objectives, we will introduce the concept of Pareto optimality, which describes scenario where neither the statistical power of estimating the treatment effect the regret can be improved without compromising the other. First, we focus on the best achievable quality of the inference of 0.. regardless of the regret incurred during the experiment. The following lemma deseribes the intrinsic difficulty of conducting inference for the dynamic treatment effect.
Lemma 1 For any constant C2 > 0, infa suPvee, Pp (1o 00/1, > 2 2VZ0200
N
C2. Moreover,
VT
inf, suPres, E, 1| 0, 11]]
Viea SVT
This lemma establishes an information -theoreticc lower bound on the best achievable quality of inference for 0,, It indicates that, for any estimator θ, there will always exist challenging instance that results in the estimator being at least ((1/VT) away from the true value. Our proof idea is to reduce the two-dimensional estimation problem to a one-dimensional problem. Specifically, we consider subset of all the problem instances & == {u E & 0,,1 = O, Va E (1,2)), which includes all the stationary instances (i.c., without time trends), and this provides natural lower
7

---

bound that inf, suPvEE, P., (10- 8.
22/0z0n info suPveE Pv (16- 8.1, 2v/2caau vT
vT
For the instance class Eg, the problem is reduced to estimating only the intercept terms. By choosing a = 1, Theorem indicates | [(T--DPP((1) Ozl1i can be upper bounded by ((1/VT), which matches with the lower bound we derive in Lemma I in terms of the dependence of the order of T' Therefore, we can state the following theorem.
Theorem (Optimal Error Rate Design) 07 (1-20PD(1) achieves the optimal 1/vT error rale, which
can not be improved up a constant factor. Moreover, inf, suppes, EE [|| 0. |1.] 0(1/T)).
Theorem 3 further establishes that the existence of 07 (L-EEOF((1) confirms the tightness of the 1 I/VT lower bound derived in Lemma As mentioned earlier, setting = 1 corresponds to the simple switchback experimental design. Theorem 3 implies that even in the presence of linear trends, switchback experiments can still maintain strong statistical power. However, there is free lunch. Choosing a = results in a regret upper bound of ((T"). which can be highly undesirable minimizing regret is also of the objectives. Now, turn discuss about the other extreme that the regret minimization is the only objective. We present the minimax regret lower bound as follows.
Lemma (Regret Lower Bound) inf, SuppeE, (R](T)
To 32e
This lemma describes that any admissible policy will face some hard instance such that the expected regret could be no less than 12( (((TT). Similar before, we can bridge our problem with the tradition stochastic bandit problem by noticing that Eg C & It is widely recognized that the stochastic bandit problem has a well-established minimax regret lower bound of ((VT)) [55]. Intuitively, given that the traditional stochastic bandit problem is a special case within
framework, this lower bound naturally extends to our setting. Formally, by Theorem 2 we have the following theorem, which
states that the vT lower bound is indeed possible to achieve and is optimal.
Theorem (Optimal Regret Rate Design) For any < a S 4. L-EOFU(a) can guarantee a regret of (( which can not be further improved up to logarithmic factors. Furthermore, inf, supuee, E [R) = G(VT).
Theorem reveals that any E (0. 11 yields a homogeneous regret rate dependence on T. However, the estimation error, as shown in Theorem ! decreases with increasing a. Consequently, increasing a from nearly 0 to 1/ does not significantly increase the regret rate, which remains at Õ Ö(VT). However, it significantly reduces the estimation error bound. Therefore, there is limited motivation for decision makers to select a < }- Nevertheless, there is no free lunch. Even we choose a = 1. the estimation can only be bounded by O(T-)) )) which is much larger than the optimal bound of / While the optimal regret rate in this case aligns with that of the traditional stochastic bandit, the optimal design for linear trends faces additional challenges. Intuitively, a regret rate optimal design for linear trends needs to improve from naive design's S 2 regret to the VT order. In contrast, the regret rate optimal design for traditional multi-armes bandits only needs to improve from T regret to VT.
From the two cases discussed above, we have uncovered a fundamental rrfde-off between regret and the statistical power. The design that achieves the optimal regret rate suffers from a large estimation error, while the design that achieves the optimal error rate incurs a large regret. To address this trade-off, we now employ the concept of Pareto optimality from multi-objective optimization theory. This concept allows us to characterize the circumstances where neither regret nor estimation error of the treatment effect can be improved without worsening the other. In other words, we aim to statistically determine the type of optimality that can be achieved between these two extremes.
Formally, we first define the policy class II as II == { 3ay > 0, Vv E E and T, E ER (T) S $) where co in this context can depend on universal constants or logarithmic terms of T. but cannot include any polynomial terms of T. The set IIg encompasses all policies that can achieve regret of ( It is evident that L-EOFU(()) belongs to II [lvv Our aim is to investigate the best achievable estimation error when the decision maker incurs a regret at most (TT)). The following lemma reveals the inherent difficulty of conducting inference under limited regret budget.
8

---

For any π E. HRg there exists a constant c* only dependent of numerical constants and logarithm terms of,, such thatfor any & > 0, inf, maxves, Pt (1) 0u]1 2 c² oo & )) 2 1 --
Lemma 3
Moreover, infg max Ey 6 e. z T
Lemma 3 demonstrates that when employing an assignment policy т with a regret of Ö(T*), any estimator, regardless of its sophistication, will encounter challenging instances where the estimation error at least ((T- ). This finding distinguishes our study, which incorporates linear trends, from the work of (74) that investigates multi-armed bandit experimental design without linear trends. In the absence of linear trends, 774 reveals that under an assignment policy with regret of O O(T)).
the estimation error has a minimax lower bound of Ā(T +). The key distinction arises from the fact that linear trends can significantly increase the cost of exploration, resulting in higher regret during the exploration phase. Consequently, with the same regret budget, the information collected in our case may be substantially less than in the absence of linear trends. The proof follows this intuition by constructing two similar instances with the same optimal arm but slightly different suboptimal arms. The only way to obtain useful information distinguish the two is by playing the suboptimal arm. Given a regret budget of T at most approximately T samples can be obtained from the suboptimal arm, leading to lower bound of T
Theorem 5 (Pareto Optimal Design) If 2 1.2 L-EOFU(a) E I2z. and thus, the T 3 error rate in Theorem Saneemmaaaa can not be further improved in terms of the dependence on T. Furthermore, for a fixed
3 2' inf myl, maX Ey 0r 0 1.11 6
The theorem establishes that the regret bound of 7 & achieved by L-EDFU(()) ((x) cannot improved by a constant factor, given that the decision-making making policy belongs to 22 This implies that L-EOFU(a)) is Pareto optimal for any a 2 7. The reasons are as follows: on the one hand, if one desires a better guarantee on the estimation error than T 9, the only option is to accept a higher regret rate by adopting larger decision-making policy class TTz for some 0. On the other hand, if regret of ( aimed for, the estimation error will inevitably increase to the order of T- te In other words, improving either the statistical power of causal inference or the efficiency of online decision-making necessitates a degradation in the other. Intuitively, Theorem captures a statistical Pareto frontier for the trade-off between conducting causal inference and minimizing regret, which can be expressed Estimation Error O (Regret )). In Theorem 3 we reveal that = 1 leads to the optimal design in terms of error rate. By combining Theorem [ we further conclude that the large 2 regret incurred by a 1 is necessary for any estimator achieving the optimal error rate of VT Moreover, the T 8 error rate achieved by a 1. although relatively large, is the best that any regret-optimal policy can achieve Figure 3 illlusraates the Pareto frontier under linear trends, alongside the Pareto frontier for standard multi-armed bandit experimental design studied in 774).
From Figure 33 we can observe the sig- nificant impact of the non-stationary structure on optimal experimental de- sign. First, in standard bandit exper- iments, the maximum possible regret is of the order 7 since all parameters are assumed to be bounded. However, with the presence of linear trends, tra- ditional designs such as switchback ex- periments are likely to incur regret of the order T Furthermore, under the same regret budget, the best achievable estimation error bounds differ substan- tially. For instance, given assignment policies with regret of the order T' the optimal design for standard bandit experiments can attain an error bound of T 1/2 whereas in the presence of linear trends, the best achievable bound T-1/1, Intuitively, this is because linear trends make gathering information from the suboptimal arm increasingly costly in terms of regret. Similarly,
Westiche intaehle
Stowded maaiormme bandt experiment design
Nor cuaionayy expe aeperireesl Touer rord (this work)
Edtination Emmor
L-
Thomerr
7-1/6
L- Thenren
y-1/2
y²
Regret
Figure 3: The Pareto Frontier.

---

when linear trends exist, the decision maker will always have to pay additional regret to obtain an estimator with the same level of precision. Additionally, there is worst-case infeasible region as indicated by Lemma 2 that no policy can achieve a regret smaller than vT order in the worst case.
3 Discussion
In this section, we'll discuss the limitations and future directions of our work. Firstly, the assumption of prior knowledge about -on-stationarity following linear form strong. While it provides starting point for understanding experiment design under structured non-stationarity, practical approaches are needed. One option is to use historical data for prior information, if there exists some. Alternatively, we can use data collected during the first phase of our L-OFUE algorithms to verify trends. Another question model misspecification. What if the true underlying model is non-parametric, but the decision maker prefers using interpretable linear functions? Understanding how our design performs such scenarios will provide valuable insights into its practical applicability. Furthermore, our framework and results are formulated based on a specific notion of von-stationarity. Exploring whether our framework can be adapted to different formulations of non non-stationarity is another area of interest for future research. Another important direction for our future research is the exploration instance-dependent regret bounds under linear and polynomial trends. In this paper, focus on studying the worst-case optimal regret. However, in the field of classical stochastic bandits, there has been increasing attention on instanceddependen regret bounds (e.g.. [I]] 33 (5). It would be valuable to extend our analysis to incorporate mnstance-depender parameters. Defining suitable instance-dependee gaps may not be directly applicable in our setting, where the parameters themselves change over time. Another more practical question that people may be of interest is how to choose a. One possible approach is to adaptively end the first phase of the experiment. Ideally, continuous monitoring during Phase 1 would allow for the experiment to halt as soon as certain criteria are met, eliminating the need manually select a. However, reliable and efficient continuous monitoring of the switchback experiment poses significant challenges. Even in basic A/B testing without a linear trend, designing continuous monitoring requires substantial effort and delicate power analysis, as demonstrated in
parameters is not a trivial task, as the classical parameters such as arm
45
4 Conclusion
In this work, we present a comprehensive investigation into the problem of non-stationary experi- mental design with linear trends. Our focus is on two objectives: accurate estimation of dynamic treatment effects and minimizing welfare loss within the experiment. For scenarios involving linear trends, we propose an efficient design called L-EOFU. This design can be customized to achieve optimal estimation error rates, optimal regret rates, or strike Pareto optimal trade-off between the two objectives. To establish the efficacy of our approach, we provide bounds that highlight the inherent challenges in estimating dynamic treatment effects and minimizing welfare loss. Additionally, we unveil the fundamental trade-off between the two objectives.
-therrtiinnhooreticall lower
References
[1] Alberto Abadie and Jinglong Zhao. Synthetic controls for experimental design. arXiv preprint arXiv:2108.02196, 2021.
[2] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[3] Karun Adusumilli. Risk and optimal policies in bandit experiments. arXiv preprint 1121v:2112.06363, 2021.
[4] Volkan E Akman and Adrian E Raftery. Asymptotic inference for change-poit poisson process. the Annals of Statistics, pages 5583-1590, 1986.
[5] Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Corralling stochastic bandit algorithms. In International Conference on Artificial Intelligence and Statistics, pages 21 16- 1224. PMLR, 2021.
10

---

[6] Onur Atan, William R Zame, and Mihaela Schaar. Sequential patient recruitment and allocation for adaptive clinical trials. In The 22nd International Conference on Artificcal Intelligence and Statistics, pages 1891-1900. PMLR, 2019.
[7] Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1):133-161 2021.
[8] Alexia Atsidakou, Orestis Papadigenopoulos, Soumya Basu, Constantine Caramanis, and Sanjay Shakkottai. Combinatorial blocking bandits with stochastic delays. In International Conference on Machine Learning, pages 404-413. PMLR, 2021.
[9] Peter Auer, Nicolo Cesa- Desa-BBanchhi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
[10] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1):48-77, 2002.
[11] Akshay Balsubramani, Zohar Karnin, Robert E Schapire, and Masrour Zoghi. Instance- dependent regret bounds for dueling bandits. In Conference on Learning Theory, pages 336-360. PMLR, 2016.
[12] Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. Contextual blocking bandits. In International Conference Artificial Intelligence and Statistics, pages 271-279, PMLR, 2021.
[13] Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. Blocking bandits, Advances in Neural Information Processing Systems, 32, 2019.
[14] Donald A Berry. Bayesian clinical trials. Nature reviews Drug discovery, 5(1):27-36, 2006.
[15] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armes armed-bandit problem with non-stationary rewards. In Advances in neural information processing systems, pages 199-207, 2014.
[16] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- tions research, 63(5): 1244, 2015.
[17] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Optimal exploration-exxlloiieee in a multi-armed bandit problem with non-stationary rewards. Stochastic Systems, (4):3199337,, 2019.
[18] Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, and Julien Seznec. Efficient change-point detection for tackling piecewise-stationary bandits. The Journal of Machine Learning Research, 23(1):3337-3376 2022.
[19] Nikhil Bhat, Vivek F Farias, Ciamac C Moallemi, and Deeksha Sinha. Near-optimal ab testing. Management Science, 66(10):447744495, 2020.
[20] Nicholas Bishop, Hau Chan, Debmalya Mandal, and Long Tran-Thanh Adversarial blocking bandits. Advances in Neural Information Processing Systems, 33:8139-811 8149, 2020.
[21] Lavor Bojinov, David Simchi-Levi, and Jinglong Zhao. Design and analysis of switchback experiments. Management Science, 2022.
[22] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationaay bandit. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 418-427. PMIR, 2019.
[23] Ningyuan Chen, Xuefeng Gao, and Yi Xiong. Debiasing samples from online learning using bootstrap. In International Conference on Artificial Intelligence and Statistics, pages 8514-8533, PMLR, 2022.
[24] Wang Chi Cheung, David Simchi-Leevi, and Ruihao Zhu. Hedging the drift: Learning to optimize under nonstationarity. Management Science, 1893 2022.
11

---

[25] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Nonstationary reinforcement learning: The blessing of (more) optimism. Management Science, 2023.
[26] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, pages JMLR Workshop and Conference Proceedings, 2012.
[27] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
[28] Giulia Clerici, Pierre Laforgue, and Nicolo Cesa Bisnchia Linear bandits with memory: from rotting to rising. arXiv preprint arXiv2332..88345 2023.
[29] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 2 st Conference on Learning Theory, 2008
[30] Maria Dimakopoulou, Zhimei Ren, and Zhengyuan Zhou. Online multi-armed bandits with adaptive inference. Advances in Neural Information Processing Systems, 34, 2021.
[31] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 2954)1485-511, 2014.
[32] Vivek Farias, Ciamac Moallemi. Tianyi Peng, and Andrew Zheng. Synthetically controlled bandits. arXiv preprint arXiv:2202.07079, 2022.
[33] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement- -base perspective. arXiv preprint arXiv:2010.03104, 2020.
[34] Ayoub Foussoul, Vineet Goyal, and Varun Gupta. Mnl-bandit in non-stationary environments. arXiv preprint arXiv:2333.02555 2023.
[35] Adama Gansané, Leah F Moriarty, Didier Ménard, Isidore Yerbanga, Esperance Ouedraogo, Paul Sondo, Rene Kinda, Casimir Tarama, Edwige Soulama, Madou Tapsoba, et al. Anti- malarial efficacy and resistance monitoring of artemethher-lmeefantee and dihydroartemisiiinn piperaquine shows inadequate efficacy in children in burkina faso, 2017-2018. Malaria Journal, 20:1-12, 2021.
[36] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International Conference on Algorithmic Learning Theory, pages 174-188. Springer, 2011.
[37] TIM Gerrodette. A power analysis for detecting trends. Ecology, 68(5): 1372, 1987.
[38] Peter W Glynn, Ramesh Johari, and Mohammad Rasouli. Adaptive experimental design with temporal interference: maximum likelihood approach. Advances in Neural Information Processing Systems, 50544-5064, 2020.
[39] Peter W Glynn and Zeyu Zheng. Estimation and inference for non-stationary arrival models with a linear trend. In 2019 Winter Simulation Conference (WSC), pages 3764-3773. IEEE, 2019.
[40] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the National Academy of Sciences, 118(15), 2021.
[41] Jinyong Hahn, Keisuke Hirano, and Dean Karlan. Adaptive experimental design using the propensity score. Journal of Business & Economic Statistics, 29(1):96-108, 2011.
[42] Peter I. Jackson, John A Muckstadt, and Yuexing Li. Multiperiod stock allocation via robust optimization. Management Science, 65(2):794-818, 2019.
12

---

[43] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406. PMLR, 2015.
[44] Ramesh Johari, Hannah Li, Inessa Liskovich, and Gabriel Y Weintraub. Experimental design in two-sided platforms: An analysis of bias. Management Science, 2022.
[45] Ramesh Johari, Leo Pekelis, and David J Walsh. Always valid inference: Bringing sequential analysis to a/b testing. arXiv preprint arXiv: 1rXiv:1512.04992,, 2015.
[46] Nathan Kallus and Angela Zhou. Confounding-robuss policy improvement. Advances in neural information processing systems, 31, 2018.
[47] Zohar S Karnin and Oren Anava. Multi-armed bandits: Competing with optimal sequences. Advances in Neural Information Processing Systems, 29, 2016.
[48] Maximilian Kasy and Anja Sautmann, Adaptive treatment assignment in experiments for policy choice. Econometrica, 89(1):113-13) 2021.
[49] Masahiro Kato. Takuya Ishihara, Junya Honda, Yusuke Narita, et al. Efficient adaptive ex- perimental design for average treatment effect estimation. arXiv preprint arXiv:2002.055: 05008 2020.
[50] N Bora Keskin and Assaf Zeevi. Chasing demand: Learning and earning in changing environment. Mathematics of Operations Research, 42(2):277-307, 2017
[51] Robert Kleinberg and Nicole Immorlica. Recharging bandits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 309-319, IEEE, 2018.
[52] Ron Kohavi, Randal M Henne, and Dan Sommerfield. Practical guide to controlled experiments on the web: listen to your customers not to the hippo. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 959-967, 2007.
[53] Michael E Kuhl, Halim Damerdji, and James R Wilson. Estimating and simulating poisson processes with trends asymmetric cyclic effects. In Proceedings of the 29th conference on Winter simulation, pages 287-295, 1997.
[54] Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics,
1985.
[55] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[56] Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. Advances in neural information processing systems, 30, 2017.
[57] Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pages 608-616. PMLR, 2015.
[58] Fang Liu, Joohyun Lee, and Ness Shroff. A change-detection based framework for piecewise- stationary multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
[59] Yueyang Liu, Benjamin Van Roy, and Kuang Xu. Nonstationary bandit learning via predictive sampling, arXiv preprint arXiv:2205.01970 2022.
[60] Yueyang Liu, Benjamin Van Roy, and Kuang Xu. definition of non-stationary bandits. arXiv preprint 220.. 2023.
[61] Haipeng Luo, Chen-Yu Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pages 1739-1776. PMLR, 2018.
[62] Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar. Model-free non-stationary rl: Near-optimal regret and applications in multi-agent rl and inventory control. arXiv preprint 2:Xhv:201000311),2200 2020.
13

---

[63] William A Massey, Geraldine A Parker, and Ward Whitt. Estimating the parameters of nonhomogeneous poisson process with linear rate. Telecommunication systems, 5:361-388. 1996.
[64] Alberto Maria Metelli, Francesco Trovo, Matteo Pirola, and Marcello Restelli. Stochastic rising bandits. In International Conference on Machine Learning, pages
PMLR, 2022.
[65] Seungki Min and Daniel Russo. An conmmattooo-thoorttii analysis of nonstationary bandit learning. arXiv preprint (rXii:2302.04452,, 2023.
[66] Yonatan Mintz, Anil Aswani, Philip Kaminsky, Elena Flowers, and Yoshimi Fukuoka. Nonsta- tionary bandits with habituation and recovery dynamics. Operations Research, 193311669 2020.
[67] Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. Why adaptively collected data have negative bias and how to correct for it. International Conference on Artificial Intelligence and Statistics, pages 1261-1269. PMLR, 2018.
[68] Tobias Nilsson and Gunnar Elgered. Long-term trends in the atmospheric water vapor con- tent estimated from ground-based gps data. Journal of Geophysical Research: Atmospheres, 113(D19), 2008.
[69] Steven Piantadosi. Clinical trials: a methodologic perspective. John Wiley & Sons, 2017.
[70] Chao Qin and Daniel Russo. Adaptivity and confounding in multi-armed bandit experiments. arXiv preprint arXiv:2202.0900. 0.906, 2022.
[71] Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Stutittccs, pages 2572- PMLR, 2019.
[72] Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. single algorithm for both restless and rested rotting bandits. In International Conference on Artificial Intelligence and Statistics, pages 3784-3794. PMLR, 2020.
[73] David Simchi-Levi and Chonghuan Wang. Multi-armed bandit experimental design: Online decision-making and adaptive inference. Available at SSRN 4224969, 2022.
[74] David Simchi-Levi and Chonghuan Wang. Multi-armed bandit experimental design: Online decision-making and adaptive inference. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, pages 3086-3097. PMLR, 25-27 Apr 2023.
[75] Richard Simon. Adaptive treatment assignment methods and clinical trials. Biometrics, pages 743-749, 1977.
[76] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16()):733-1755, 2015.
[77] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):255-294 1933.
[78] Stefan Wager and Kuang Xu. Diffusion asymptotics for sequential experiments. arXiv preprint arXiv:2101.09855, 2021.
[79] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[80] Jing Wang, Peng Zhao, and Zhi-Hua Zhou. Revisiting weighted strategy for non-stationary parametric bandits. arXiv preprint 2xXi:2303..0691, 2023.
[81] Siwei Wang, Longbo Huang, and John Lui. Restless-ucb, an efficient and low-complexity algorithm for online restless bandits. Advances in Neural Information Processing Systems, 33:11878-1188 11889, 2020.
14

---

[82] Youfa Wang, May A Beydoun, Lan Liang, Benjamin Caballero, and Shiriki K Kumanyika. Will all americans become overweight or obese? estimating the progression and cost of the us obesity epidemic. Obesity, 16(10):2323-23M0 2008.
[83] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evalua- tion in contextual bandits. In International Conference on Machine Learning, pages 3589-3597. PMLR, 2017.
[84] Chen- Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Tracking the best expert in con-stationary stochastic environments. Advances in neural information processing systems, 29, 2016.
[85] Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25(A):287-298, 1988.
[86] WHO. World malaria report 2022. World Health Organization, 2022.
[87] Yuhang Wu, Zeyu Zheng, Guangyu Zhang, Zuohua Zhang, and Chu Wang. Adaptive a/b tests and simultaneous treatment parameter optimization. arXiv preprint arXiv:2210.067377 2022.
[88] Yuhang Wu, Zeyu Zheng, Guangyu Zhang, Zuohua Zhang, and Chu Wang. Non-stationary a/b tests. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 2079-2089, New York, NY, USA, 2022. Association for Computing Machinery.
[89] Xiao Xu, Fang Dong, Yanghua Li, Shaojian Hc, and Xin Li. Contextual-bandi based personal- ized recommendation with varring user interests. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6518-6525, 2020.
[90] Kevin P Yancey and Burr Settles. A sleeping, recovering bandit algorithm for optimizing recurring notifications. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3008-3016, 2020.
[91] Adoke Yeka, Erika Wallender, Ronald Mulebeke, Afizi Kibuuka, Ruth Kigozi, Agaba Bosco, Paul Kyambadde, Jimmy Opigo, Simeon Kalyesubula, Joseph Senzoga, et al. Comparative efficacy of lumeffatrrre and dihydroartemissinnn panardraatteiisnnnnippppppigggg for the treatment of uncomplicated malaria in ugandan children. The Journal of infectious diseases, 219(7):1112- 1 1120, 2019.
[92] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125-2131 2021.
[93] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in neural information processing systems, 33:9818 18-9829, 2020.
[94] Xiangyu Zhang and Peter Frazier. Restless bandits with many arms: Beating the central limit theorem. arXiv preprint arXiv:2107.11911, 2021.
[95] Jinglong Zhao and Zijie Zhou. Pigeonhole design: Balancing sequential experiments from an online matching perspective, 2022.
[96] Zeyu Zheng and Peter W Glynn. Fitting continuous piecewise linear poisson intensities via maximum likelihood and least squares. In 2017 Winter Simulation Conference (WSC), pages 1740 1749. IEEE, 2017.
[97] Xiang Zhou, Xiong, Ningyuan Chen, and Xuefeng Gao. Regime switching bandits. Advances in Neural Information Processing Systems, 34:4542-4554, 2021.
[98] Zhengyuan Zhou, Susan Athey, and Stefan Wager. Offline multi-action policy learning: Gener- alization and optimization. Operations Research, 2022.
[99] Feng Zhu and Zeyu Zheng. When demands evolve larger and noisier: Learning and earning in a growing environment. In International Conference on Machine Learning, pages 11629-11638. PMLR, 2020.
15


Reviews:
[{"review_id": "3m897MNWb4", "reviewer": "Reviewer_EcQ7", "summary": "This paper studied the problem of non-stationary experimental design. The authors adopt a linear model assumption, where the reward associated with each arm exhibits a linear relationship with time. They concern two objectives: accurate estimation of dynamic treatment effects and regret. They propose a two-stage Exploration and OFU design algorithm that can be customized for optimal estimation error rate, optimal regret rate or the Pareto optimal trade-off between the two objectives. The paper also provides information-theoretic lower bounds to illustrate the challenge of achieving two objectives simultaneously. The experimental results on synthetic data demonstrate is consistent with theoretical results.", "questions": "Please consider addressing questions in Weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper is well-written and the overall idea of the paper was clear and easy to understand.\n\n2. The theoretical results on the information-theoretical lower of causal estimation and regret seem technically sound.", "weaknesses": "1. The author mentions that [1] also investigates the trade-off between regret and causal inference using Pareto optimality. It seems that [1] already introduce the concept of Pareto optimality to characterize the trade-off between estimation error and regret, which might show the lack of technical novelty in the problem formulation. Therefore, additional elaborations are necessary to elucidate the connection and difference between the present work and [1].\n\n2. Moreover, it is worth noting that [1] does not impose any assumptions on the reward model. In contrast, the current paper introduces a linear structure, which constitutes a rather strong assumption. While I acknowledge that this work extends the analysis to a non-stationary setting, it would be valuable to explore the possibility of devising a more general model class that can accommodate diverse reward specifications. By doing so, the research would not only enhance its applicability but also contribute to the advancement of the field by providing a broader framework for analysis.\n\n3. Additional numerical experiments would greatly enhance the paper‘s empirical evaluation. As it stands, the paper solely encompasses a single scenario, which limits the scope of its findings. To address this concern, I recommend the authors incorporate multiple scenarios in their analysis, thereby demonstrating the robustness of the proposed algorithm across various settings. For instance, investigating the impact of varying $\\sigma_a^2$ on the results could provide valuable insights into the algorithm’s performance under different conditions.\n\n4. While the current paper provides a thorough analysis focusing on two arms, it is necessary to discuss the extension of the proposed framework to accommodate settings of more than 2 arms.\n\n\n[1] Simchi-Levi, David, and Chonghuan Wang. “Multi-armed bandit experimental design: Online decision-making and adaptive inference.” In International Conference on Artificial Intelligence and Statistics, pp. 3086-3097. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your helpful comments and careful read of our work. Thank you for providing us with an opportunity to address your concerns.\n\n1.\tComparing with [A].\n\nWe completely agree that [A] was the first to introduce Pareto optimality to characterize a similar trade-off. Allow us to clarify that we do not claim, nor will we plan to claim, that our contribution includes the introduction of Pareto optimality. Instead, we like to highlight the technical novelty and several significant points that differentiate our work as follows. The Pareto trade-off, serves as a metric, instead of a result, to illustrate our work’s contribution.\n\nFirstly, in terms of formulation, our main contribution lies in capturing non-stationarity with linear trends, which, to the best of our knowledge, is a novel concept in the related literature on experimental design. It is essential to note that [A] assumes stationarity of the outcomes, and when the linear trend is zero, the outcome structure we consider encompasses the structure examined by [A]. Therefore, from a formulation perspective, [A] can be seen as a special case of our work, which did not consider non-stationarity. \n\nSecondly, in the algorithm design, our problem formulation is new both in the experimental design literature and within the bandit literature. As a consequence, traditional algorithms and proof techniques for bandit problems may not be directly applicable. As discussed in the paper, the main technical challenges stem from the fact that outcomes can no longer be assumed to be bounded by a universal constant (independent of time horizon $T$), as is common in much of the bandit literature. This unboundedness necessitates the development of novel techniques to ensure the performance of the regret bound of our algorithm. To be more precise, the unboundedness issue renders the regret of several traditional MAB algorithms to be in the order of $T$ and fall short of achieving the optimal regret rate of $\\sqrt{T}$ (see lines 261 to 270 in the paper). In contrast, [A] studies the fundamental MAB experiment case, where traditional MAB algorithms and analysis can be applied.\n\nThirdly, in terms of results, Figure 3 in the paper illustrates the differences between our work and [A]. While [A] establishes that the trade-off can be approximately captured by $error \\simeq regret^{-1/2}$, our findings reveal that with a linear trend, the trade-off becomes $error \\simeq regret^{-1/4}$. This means that given the same regret budget, estimating the model with a linear trend is more challenging. Additionally, due to the unbounded issue, the regret incurred by a naive algorithm could even be in the order of $T^2$, as opposed to the order of $T$ in [A]. Further elaboration on the distinctions between [A] and our work can be found in the paper from lines 391 to 411.\n\nIn the revised version, we plan to emphasize these points more explicitly to distinguish ourselves from [A]. We sincerely hope that this response alleviates potential concerns you may have had.\n\n2.\tGeneralization to higher order polynomial trends.\n\nOur L-EOFU algorithm and the associated lower bounds can indeed be extended to accommodate cases where the trend is formulated by a higher order polynomial function. Specifically, when the trend follows a $k$th order polynomial, we can establish a general result that provides the best estimation error one can expect for any design with a regret bound of $T^\\beta$ to be $T^{-\\beta/(2k+2)}$. It is noteworthy that when $k=1$, this result aligns precisely with what we presented in the paper. Therefore, the generalized formulation covers and extends the findings in the submitted work. Moreover, during the Phase 1 in our design, it is possible to observe and determine the optimal choice of $k$ for a given setting. This allows for a data-driven approach to decide which polynomial order best fits the underlying trend.\n\nTo address more complex functions beyond polynomial trends, we can leverage Taylor expansion. By selecting a sufficiently large value of $k$, we can effectively approximate and handle a broader range of functions, thereby increasing the versatility of our approach. \n\nIn conclusion, we are excited about the potential of solving higher order polynomial trends under our framework, as it presents an avenue to expand the scope of applications.\n\n3.\tGeneralization to $K$ arms.\n\nWe agree that extending our approach to settings with more than 2 arms, such as $K$ arms, would be beneficial. Our current framework allows generalization to $K$ arms. Allow us to outline the necessary modifications and improvements for this generalization. In the context of more than 2 arms, we introduce the gap between arm $i$ and arm $j$ as $\\theta_\\nu^{(i,j)}$. To address the estimation error, we simply replace the original $\\left|\\hat{\\theta}-\\theta_\\nu\\right|$ with $\\max_{i<j\\le K} \\left|\\hat{\\theta}^{(i,j)}-\\theta_\\nu^{(i,j)}\\right|$, which considers the maximum deviation between the estimated and true values across all pairs of arms. Fortunately, all the theoretical results follow a similar structure, allowing for a seamless adaptation to this extended setting.\n\nFurthermore, the L-EOFU design showcases flexibility in coping with more than 2 arms. For Phase 1, the algorithm efficiently explores all $K$ arms sequentially, ensuring a comprehensive initial exploration. In Phase 2, the approach remains largely unchanged, with the only difference being the need for estimations for all $K$ arms. As a result, the generalization to multiple arms does not impose additional technical challenges.\n\nWe agree with your suggestion to incorporate additional numerical experiments in the revised version. We genuinely appreciate your insightful comments. We will diligently incorporate these enhancements and extensions into the revised version.\n\nReference:\n\n[A] Simchi-Levi D, Wang C. “Multi-armed bandit experimental design: Online decision-making and adaptive inference.” AISTATS 2023."}, {"review_id": "w1IJbtwkaU", "reviewer": "Reviewer_GLy4", "summary": "This work is concerned with designing an adaptive experiment in the presence of a linear or polynomial trend in the potential outcome. The authors describe the natural tension between estimation estimation error and regret and describe the Pareto optimal objective. They then introduce an optimistic procedure that seeks to optimize for each of the three objectives depending on the value of a free parameter. It is then shown that the procedure achieves the optimal error rate and optimal regret. Both of which are dependent on the choice of the free parameter $\\alpha$. Finally, the authors show that the proposed procedure is Pareto optimal. ", "questions": "* Can the authors give a sense of guidance for setting $\\alpha$ in practice? \n* Is it possible to provide a set of simple simulation results that show the empirical behavior of the proposed algorithm?\n", "limitations": "Yes, the authors do a very nice job of describing the limitations. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* This is a well motivated, and to my eyes, novel task. \n* The authors do a nice job of both describing the problem and clearly laying out the inherent difficulty in addressing the problem (the tradeoff between estimation error and regret). \n* The proposed algorithm is intuitive, and the properties are appealing. \n* The technical results are well written, and should be fairly accessible to readers. \n* I can envision this work having impact on practice, where it is common for practitioners to encounter the phenomenon of potential outcomes that change over time. ", "weaknesses": "The largest concerns here are: \n1. The authors require the selection of $\\alpha$ for all of the analyses. This is reasonable, given the tradeoff. However, in practice it would seem that it is going to be difficult for experimenters to choose this a priori. \n2. The authors assume a well-specified model, i.e. the underlying trend is truly linear or polynomial. This seems to my eyes to be very simplified. While likely out of scope of the paper to provide robustness properties of the proposed procedure, it would seem important to have a discussion of this within the text. \n3. Given (1) and (2), it would have been nice to see some kind of empirical evaluation that shows both the performance of the algorithm against naive alternatives and the relative robustness\n4. (minor) The author references in supplement C are broken. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and helpful comments on our work. We sincerely appreciate your careful read of our paper, and we are grateful for the opportunity to address your questions and concerns. Below, we provide our detailed response:\n\n1.\tThe Selection of $\\alpha$.\n\nWe agree with your suggestion, and we recognize the importance of discussing the selection of $\\alpha$ more thoroughly. While choosing the optimal value of $\\alpha$ may be a challenging task, we acknowledge several practical and intuitive approaches that could be employed.\n\nOne option is for the experimenter to determine the largest tolerable estimation error, for instance, in the order of 0.1, and with $T$ experimental units available, select $\\alpha$ as $2\\log_{T}10$. This approach leverages prior information on the acceptable level of estimation error, providing a basis for the selection of $\\alpha$. Similarly, if the primary objective is to strictly control the loss of welfare, the choice of $\\alpha$ can be made accordingly. These practical approaches, while not without their limitations, offer feasible methods to decide on an appropriate value for $\\alpha$, taking into account specific requirements and constraints.\n\nAnother approach we considered is to adaptively end the first phase of the experiment. Ideally, continuous monitoring during Phase 1 would allow for the experiment to halt as soon as certain criteria are met, eliminating the need to manually select $\\alpha$. However, reliable and efficient continuous monitoring of the switchback experiment poses significant challenges. Even in basic A/B testing without a linear trend, designing continuous monitoring requires substantial effort and delicate power analysis, as demonstrated in [A]. While we recognize the potential benefits of this adaptive approach, we consider it an essential future direction, and we aim to explore this avenue in our future work.\n\n2.\tGeneralization to higher order polynomial trends.\n\nWe appreciate your positive assessment of the generalization of our L-EOFU algorithm and the associated lower bounds to accommodate higher order polynomial trends. The established result, where the trend follows a $k$th order polynomial, indicating a best estimation error of $T^{-\\beta/(2k+2)}$ for any design with a regret bound of $T^\\beta$, allows for enhanced flexibility and adaptability. Specifically, Phase 1 can now serve the additional purpose of observing the optimal choice of $k$, providing data-driven insights for decision-making.\n\nAdditionally, leveraging Taylor expansion enables us to handle more general functions by choosing a sufficiently large value of $k$. This approach represents a potential solution to address the misspecification issue, and we will incorporate a thorough discussion of the model misspecification within the text.\n\nRegarding the simulation provided in Appendix A, it serves the purpose of illustrating the trade-off between minimizing the estimation error and maximizing statistical power. We will fix the reference issue in Supplement C to ensure the accuracy and reliability of our work. Once again, we extend our gratitude for your valuable time and insightful comments. Your feedback has been instrumental in enhancing the quality and clarity of our paper.\n\nReference:\n\n[A] Johari, R., Koomen, P., Pekelis, L., & Walsh, D. (2022). Always valid inference: Continuous monitoring of a/b tests. Operations Research, 70(3), 1806-1821.\n"}, {"review_id": "ISor9ss9Sk", "reviewer": "Reviewer_sYAZ", "summary": "The paper introduces a new experimental design for non-stationary experiments under the assumption that the expected potential outcomes are linear in time.\n\nThe proposed design consists of two phases: a switchback experiment that alternates at each time point and a UCB-type algorithm for multi-armed bandits. Phase 2 incorporates information learned from Phase 1, but the inference is solely based on Phase 1 data.\n\nThe authors also discuss the following theoretical properties of the experiment:\n - an upper bound on estimation error,\n - an upper bound on regret,\n - an optimal design that demonstrates Pareto optimality within the considered design class.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper explores a scenario that hasn't been studied before, and the proposed design is also novel.\n\nAs far as I know, the regret bound in the paper has not been derived before under this specific set of assumptions.\n\nThe observation that there is not a strict tradeoff for choosing $\\alpha$ in $(0,1/4]$ is interesting and insightful.\n\nThe paper is well-written and easily understandable.\n\nThe design and inference presented in the paper are simple and practical.", "weaknesses": "The assumption of a linear trend is not compelling enough to me:\n - The authors have not provided any realistic example under which such a linear trend might occur\n - The authors mentioned that a drawback of current works on decision-making under non-stationarity is the lack of knowledge transferability to future, but it is not clear to me whether the treatment effect can really be extrapolated through a linear function.\n\nThe class of designs considered in the paper appears to be quite specific. It might benefit from additional motivation for this particular set of designs:\n - Why use a switchback for the first phase? Under the given assumption, it seems that it doesn’t matter when we assign treatment and control, as long as there are $T^\\alpha/2$ periods assigned to each group. While a switchback design may offer robustness in certain scenarios where the assumption might not hold, the authors have not adequately explained this aspect in the current version of the paper (Please also refer to the comments below for robustness concerns).\n - One important contribution of the paper is the observation in Theorem 5 regarding the Pareto optimal design, but it is only optimal contingent on the specific class of designs and estimation strategy considered. For instance, although post-bandit inference is challenging, there is certainly information in the data that can be utilized and there are works on it. Would the same conclusion still hold if the inference were not solely based on data collected in Phase 1?\n - Under which circumstances would the practitioners find such an experiment to be of interest? Why couldn’t they simply keep running a bandit algorithm? If they want to do inference, it is still possible to do post-bandit inference, or they may just pause the algorithm and run a randomized experiment.\n\nRobustness concerns:\n - It seems that the inference could be misleading if the linear assumption is off. This is especially concerning since the insight into the post-experiment period is solely based on information from the first part of the experiment, which can be a very strong statement under nonstationarity.\n - How would a practitioner know if the linearity assumption is reasonable? What if, during Phase 1, they observe that there is actually not such a linear trend?\n - Related to the motivation for the switchback, what is the reason for implementing a one-coin flip (i.e., having a deterministic sequence of actions) instead of opting for a completely randomized experiment (which is in general more robust in an adversarial environment)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedbacks! We refer our response to the linear assumptions, the extension to higher order polynomial trends, and the switchback design to the \"global response\" on top of page. We detail responses to the other comments as follows.\n\na.\tAbout the Pareto optimality.\n\nSorry that we may have not fully digested the comment “it is only optimal contingent on the specific class of designs and estimation strategy considered.” In the follows, we are responding according to our understanding. Kindly correct us if we have misinterpreted the comment.\n\nFirst, we may want to repeat ourselves a bit that when we refer to a design as Pareto optimal, it signifies that there exists no other design that can strictly outperform it on both objectives (i.e., regret and estimation error). Pareto optimality is an intrinsic property of a design and is not confined to a specific class of designs and estimation strategies. It necessitates comparing all potential sophisticated designs to determine their optimality. Our design represents a series of Pareto optimal designs. One of the main technical challenges we faced was ensuring that our design cannot be strictly outperformed by any other possible policy.\n\nSecond, with regard to the post-bandit inference, there may be valuable information in the data that can be utilized. However, our lower bound in Lemma 3 indicates that the information we \"waste\" does not fundamentally alter the essential outcome. Specifically, Lemma 3 establishes a lower bound for all admissible estimators by taking the infimum over all possible $\\hat{\\theta}_T$. This means that for any estimators, regardless of whether they utilize all the data (including those based on post-bandit inference), the estimation errors are lower bounded by a constant in the order of $T^{-\\frac{\\beta}{4}}$, given that the data are generated from an assignment policy with regret bounded by $T^\\beta$. In essence, the unused information may marginally reduce the estimation error concerning the constant term, but not the $T$ dependence. For instance, the estimation error may decrease from $T^{-\\frac{\\beta}{4}}$ to $0.8T^{-\\frac{\\beta}{4}}$.  Exploring ways to further reduce the constant by utilizing data collected in Phase 2 is a crucial aspect of our future work. As you astutely pointed out, addressing this task is likely to be quite challenging, as evidenced by the extensive work conducted by pioneers Zhang et al. [D] in solving the task for the batched bandit. Hence, we humbly request to defer this aspect to our future work.\n\nWe should have used $\\hat{\\theta}$ instead of $\\hat{\\theta}_T$ in both Lemma 3 and Theorem 5. We hope that this inconsistency did not cause any confusion in understanding.\n\nb. Alternatives to our current design.\n\nWe appreciate your proposal of a post-bandit inference and the idea of pausing a bandit algorithm to run a randomized experiment. Both are indeed inspiring and worthy of consideration. Meanwhile, we like to highlight several essential reasons that deterred us from pursuing these alternative routes.\n\nWe have explained a bit in our response c above that post-bandit inference may not make a huge difference. Specifically, if we run the rate optimal bandit algorithm, we will obtain $T^{1/4}$ samples from the suboptimal arm. Even employing several different techniques including bootstrap or others, it is unreasonable to expect that the estimators based on $T^{1/4}$ samples could enjoy the same inference quality as those based on $T$ samples. Additionally, the assumptions commonly made in post-bandit inference literature, such as lower-bounded probabilities of arm selection, may not hold when we adopt OFU-type algorithms. Consequently, traditional post-bandit inference techniques may not be easily applicable to our setting.\n\nAs for pausing a bandit algorithm to run a randomized experiment, defining the stopping time presents a significant challenge. Continuous monitoring throughout the entire experiment is required to determine when to pause the algorithm, making the process complex. Achieving continuous monitoring is already difficult in basic A/B testing without adaptivity, as highlighted in a recent work [G]. It would be even more challenging in our setting. Furthermore, the total regret incurred by the proposed method with the randomized experiment lasting for $T^{\\alpha}$ periods may become very large. For instance, when the expected outcomes for the two arms at time $t$ are $\\mathbb{E}[r_t(1)]=t$ and $\\mathbb{E}[r_t(2)]=2t$, the regret incurred during the randomized experiment would be in the order of $T^{1+\\alpha}$. In contrast, our design incurs a regret of only $T^{2\\alpha}$ during the exploration phase, which is always smaller since $\\alpha \\leq 1$. Thus, obtaining the same amount of information would result in different incurred regrets. Additionally, designing a bandit algorithm under the linear trend poses its own set of challenges. Our analysis heavily relies on the data collected from the first phase. Since the rewards cannot be bounded by a constant independent of $T$, which we have emphasized in the paper, many traditional algorithms and techniques may not work, and this has been a significant technical challenge for us to address.\n\nIn conclusion, while we acknowledge the appeal of the alternative ideas that you proposed, we have thoroughly considered the inherent difficulties and limitations associated with them. We will ensure to provide a more comprehensive discussion of these alternative ideas, along with a thorough explanation of why our current approach was chosen.\n\nReferences:\n\n[D] Zhang et al. (2020). Inference for batched bandits. NeurIPS 2020.\n\n[E] Bibaut et al. (2021). Post-contextual-bandit inference. NeurIPS 2021.\n\n[F] Hadad et al. (2021). Confidence intervals for policy evaluation in adaptive experiments. PNAS.\n\n[G] Johari et al. (2022). Always valid inference: Continuous monitoring of a/b tests. Operations Research, 70(3), 1806-1821.\n"}]

Author rebuttal:
We thank all the reviewers for your time, valuable feedback, and insightful comments. In addition to the responses to each reviewer, we would like to use this part to provide clarifications on three specific comments.

a.	Assumption on linear trends.

Linear trends are indeed a strong assumption, and they may not always fully represent the complexities of real-world treatment effects. That said, we consider linear trends to be a crucial starting point in understanding structured non-stationary trends when conducting experiments. As the first work to explore non-stationary trends in experiments, upon the standard practice of viewing experiments as stationary, we think that focusing on linear trends offers a fundamental perspective to understand how non-stationary trends affect experiments in various aspects.

While linear trends might not be the most sophisticated model, they have proven to be highly useful for understanding and predicting certain phenomena across various fields. Allow us to provide several illustrative examples to support this claim:

1.	(Epidemiology) Wang et al. [A] observed a linear trend in the prevalence of obesity and overweight among US adults, based on national survey data collected between 1970s and 2004. This linear trend served as a benchmark for predicting the prevalence from 2004 to 2050, influencing numerous epidemiology studies.
2.	(Ecology) [B] conducted a study on monitoring and predicting the California sea otter population using linear trends observed in aerial surveys, showcasing the usefulness of linear trends in ecological studies.
3.	(Atmospheres) Nilsson and Elgered [C] revealed a linear trend in the integrated water vapor content based on a 10-year ground-based GPS data, highlighting the application of linear trends in atmospheric research.

In these examples, linear trends are not only used to understand immediate changes but also to predict and assess the long-term implications of various policies and interventions. While we acknowledge that linear trends may not capture all nuances, they do provide valuable insights, especially when prior information suggests approximate linearity. Linear trends, admittedly, are not able to capture all kinds of non-stationary trends, but can serve as a first step toward more complicated non-stationary trends. We hope that our work's consideration on linear non-stationary trends complements the previous literature on experimental design with no non-stationarity, and builds some useful tools for the consideration of other non-stationary trends.

We understand the importance of providing realistic examples to support our claims, and we apologize for the oversight in not including specific real-world scenarios in our initial submission. In the revised manuscript, we will diligently address this concern by incorporating the mentioned scenarios where linear trends play a significant role. Additionally, we will emphasize the applicability of our framework in situations where linear models are preferred due to their strong interpretability.

b.	Generalization to higher order polynomial trends.

We agree with your suggestion, and we are delighted to confirm that our L-EOFU algorithm and the associated lower bounds can indeed be generalized to accommodate higher order polynomial trends. Specifically, when the trend follows a $k$th order polynomial, we have established a general result that provides the best estimation error one can expect for any design with a regret bound of $T^\beta$ to be $T^{-\beta/(2k+2)}$.

It is important to note that when $k=1$, this result aligns precisely with what we presented in the main paper. Thus, the generalized formulation encompasses and extends the findings we reported earlier. Given this generalization, Phase 1 can be effectively utilized to observe and determine the optimal choice of $k$. Through this approach, the experimenter can assess which polynomial order best fits the underlying trend and make informed decisions accordingly. This flexibility allows for a data-driven selection of the appropriate polynomial order, which can significantly alleviate concerns about the possibility of observing a non-linear trend during Phase 1.

Furthermore, we acknowledge the significance of Taylor expansion in dealing with more complex functions beyond simple polynomial trends. By choosing a large enough value of $k$, the Taylor expansion enables us to effectively approximate and handle a broader range of functions, thereby enhancing the applicability of our approach.

In conclusion, we are thrilled about the generalization to higher order polynomial trends. It not only addresses your concern about the linearity assumption but also allows for a data-driven and flexible selection of the polynomial order.

c. The switchback design in the first phase.

We appreciate that some reviewer points out as long as predetermined $T^\alpha/2$ periods are assigned to each group, our design would be effective. We acknowledge that the switchback design is just one of the possible approaches and, indeed, we opted for it primarily to facilitate the theoretical analysis. Specifically, in the proof to Theorem 1 in Appendix B, the switchback design offers advantages by enabling us to explicitly derive expressions for $V_{1,0}$, $V_{2,0}$, and their inverses. This explicit representation brings significant convenience to the analysis and helps in drawing insightful conclusions. We acknowledge that other designs could be equally valid in practice.

References:

[A] Wang et al. (2008). Will all Americans become overweight or obese? Estimating the progression and cost of the US obesity epidemic. Obesity, 16(10), 2323-2330.

[B] Gerrodette, T. I. M. (1987). A power analysis for detecting trends. Ecology, 68(5), 1364-1372.

[C] Nilsson, T., & Elgered, G. (2008). Long‐term trends in the atmospheric water vapor content estimated from ground‐based GPS data. Journal of Geophysical Research: Atmospheres, 113(D19).



Meta-review: The paper studies an adaptive experimental design to handle the case of non-stationary outcomes but subject to a linear trend. Both the problem and the approach are new and nicely formulated/executed, as recognized by the reviewers. The authors should implement their responses into the text in preparing a camera ready. For example, additional literature on inference after adaptive experimentation and always valid inference was brought up during discussion and should be discussed in the paper.
Decision: Accept (poster)