Bojinov, Simchi-Levi, and Zhao

Switchback Experiments

Design and Analysis of Switchback Experiments

Iavor Bojinov Technology and Operations Management Unit, Harvard Business
School, Boston, MA 02163<EMAIL_ADDRESS>David Simchi-Levi Institute for
Data, Systems, and Society, Department of Civil and Environmental Engineering,
and Operations Research Center, Massachusetts Institute of Technology,
Cambridge, MA 02139<EMAIL_ADDRESS>Jinglong Zhao Institute for Data, Systems,
and Society, Massachusetts Institute of Technology, Cambridge, MA 02139,
<EMAIL_ADDRESS>
In switchback experiments, a firm sequentially exposes an experimental unit to
a random treatment, measures its response, and repeats the procedure for
several periods to determine which treatment leads to the best outcome.
Although practitioners have widely adopted this experimental design technique,
the development of its theoretical properties and the derivation of optimal
design procedures have been, to the best of our knowledge, elusive. In this
paper, we address these limitations by establishing the necessary results to
ensure that practitioners can apply this powerful class of experiments with
minimal assumptions. Our main result is the derivation of the optimal design
of switchback experiments under a range of different assumptions on the order
of carryover effect — that is, the length of time a treatment persists in
impacting the outcome. We cast the experimental design problem as a minimax
discrete robust optimization problem, identify the worst-case adversarial
strategy, establish structural results for the optimal design, and finally
solve the problem via a continuous relaxation. For the optimal design, we
derive two approaches for performing inference after running the experiment.
The first provides exact randomization based $p$-values and the second uses a
finite population central limit theorem to conduct conservative hypothesis
tests and build confidence intervals. We further provide theoretical results
for our inferential procedures when the order of carryover effect is
misspecified. For firms that possess the capability to run multiple switchback
experiments, we also provide a data-driven strategy to identify the likely
order of carryover effect. To study the empirical properties of our results,
we conduct extensive simulations. We conclude the paper by providing some
practical suggestions.

##  1 Introduction

Academic scholars have appreciated the benefits that experimentation brings to
firms for many decades (March 1991, Sitkin 1992, Sarasvathy 2001, Thomke 2001,
Kohavi and Thomke 2017). However, widespread adoption of the practice has only
taken off in the last decade, partly fueled by the rapid cost reductions
achieved by firms in the technology sector (Kohavi et al. 2007, 2009, Azevedo
et al. 2019, Kohavi et al. 2020). Most large firms now possess internal tools
for experimentation, and a growing number of smaller and more conventional
companies are purchasing the capabilities from third-party sellers that offer
full-stack integration (Thomke 2020). These tools typically allow simple “A/B”
tests that compare the standard offering “A” to a new or improved version “B”.
The comparisons are made across a range of different business outcomes, and
the tests are usually conducted for at least a week. This simple practice has
provided tremendous value to firms (Koning et al. 2019). Some firms and
authors, however, have recognized the limitations of these simple A/B tests
(Bojinov et al. 2020b). Principle amongst these is adequately handling
interference111Many online platforms and retail marketplaces have observed
different levels of interference when the assignment of one subject impacts
another. See Kastelman and Ramesh (2018), Farronato et al. (2018), Glynn et
al. (2020) for online platforms (_e.g._ , DoorDash, Lyft, Uber), and Caro and
Gallien (2012), Ferreira et al. (2016), Ma et al. (2020) for retail markets
(_e.g.,_ AB InBev, Rue la la, Zara). (the scenario where the assignment of one
subject impacts another) or estimating heterogeneous (or personalized)
effects222See Nie et al. (2018), Deshpande et al. (2018), Hadad et al. (2019)
for estimating heterogeneous effects..

In this paper, we simultaneously tackle both of these challenges by developing
a theoretical framework for the optimal design and analysis of switchback (or
time series) experiments. In switchback experiments, we sequentially expose a
unit to a random treatment, measure its response, and repeat the procedure for
a fixed period of time (Robins 1986, Bojinov and Shephard 2019). By
administering alternate treatments to the same unit, we can directly estimate
an individual level causal effect and alleviate the challenges posed by
interference.

There are two classes of applications were switchback experiments are widely
used in practice. The first arises when units interfere with each other either
through a network or some more complicated unknown structure. For example,
consider a ride-hailing platform that wants to test a new fare pricing
algorithm’s effectiveness in a large city (Farronato et al. 2018).
Administering the test version to a subset of drivers can impact their
behavior, which, in turn, could change the behavior of drivers that are
receiving the old version. Directly comparing the revenue generated by the
drivers across the two groups will likely provide a biased estimate of what
would happen if everyone were assigned to the new version compared to the old.
Instead, practitioners consider the city a single aggregated unit and use a
switchback experiment to estimate the intervention’s effectiveness, thereby
alleviating the problem caused by interference. A similar issue often arises
in marketing when, for example, a retailer wants to test the effectiveness of
a new promotion planning algorithm (Ferreira et al. 2016). Administering the
new version to a subset of stock keeping units (SKU’s) cannibalizes the sales
from the other SKU’s. Again comparing the generated revenue across the two
groups is unlikely to provide an accurate measure of the promotion’s
effectiveness. Instead, practitioners can treat all the SKU’s as a single
aggregated unit and use a switchback experiment to obtain accurate estimates
of the promotion’s effectiveness. The second application arises when we have a
limited number of experimental units, and we believe the effects are likely to
be heterogeneous. For example, Bojinov and Shephard (2019) used switchback
experiments to make causal claims about the relative effectiveness of
algorithms compared with humans at executing large financial trades across a
range of financial markets. More generally, psychologists and biostatisticians
regularly use switchback experiments whenever studying the effectiveness of an
intervention on a single unit (_e.g._ , Lillie et al. (2011) and Boruvka et
al. (2018)).

There are three significant challenges to using switchback experiments. The
first is that causal estimators from switchback experiments have large
variances as the precision is a function of the total number of assignments.
The second is that past interventions are likely to impact future outcomes;
this is often referred to as a carryover effect. Typically, many authors
assume that there are no carryover effects, _e.g._ , Chamberlain (1982), Athey
and Imbens (2018), and Imai and Kim (2019), although some recent work has
relaxed this assumption (Sobel 2012, Bojinov et al. 2020a). The third is that
standard super population inference—where we either assume a model for the
outcome333For example, Wager and Xu (2019), Johari et al. (2020) assume that
the market they are experimenting on is in an equilibrium state, Glynn et al.
(2020) assumes an underlying Markovian model for the outcomes, and Athey et
al. (2018), Eckles et al. (2016), Sussman and Airoldi (2017), Puelz et al.
(2019) make assumptions on the structure of the interference.. or that the
units are sampled from an infinitely large population—requires unrealistic
assumptions that fail to capture the problem’s personalized nature (Bojinov
and Shephard 2019).

This paper’s main contributions are to address these three challenges and
present a framework that allows firms and researchers to run reliable
switchback experiments. First, we derive optimal designs for switchback
experiments, ensuring that we can select a design that leads to the lowest
variance among the most popular class assignment mechanisms. Second, we assume
the presence of a carryover effect and show that our estimation and inference
are valid both when the order of carryover effect is correctly specified and
misspecified, the later leading to a minor increase in the variance. For
practitioners and managers, we also propose a method to identify the order of
carryover effect by running a series of carefully designed switchback
experiments. Finally, we take a purely design-based perspective on
uncertainty; that is, we treat the outcomes as unknown but fixed (or
equivalently, we condition on the set of potential outcomes) and assume that
the assignment mechanism is the only source of randomness (Abadie et al.
2020). The main benefit of a design-based perspective is that the inference,
and in turn the causal conclusions, do not depend on our ability to correctly
specify a model describing the phenomena we are studying, ensuring that our
findings are wholly non-parametric and robust to model misspecification
(Imbens and Rubin 2015, Chapter 5).

The paper is structured as follows. In Section 2 we define the notations, the
assumptions, and the assignment mechanism that we focus on, which is referred
to as the _regular switchback experiments_. In Section 3, we discuss how to
design an effective regular switchback experiment under the minimax rule. We
cast the design problem as a minimax robust optimization problem. We identify
the worst-case adversarial strategy, establish structural results, and then
explicitly find the optimal design. In Section 4, we discuss how to perform
inference and conduct statistical testing based on the results obtained from
an optimally designed switchback experiments. We propose an exact test for
sharp null hypotheses, and an asymptotic test for testing the average
treatment effect. We provide $p$-values and construct confidence intervals
based on such two hypotheses tests. In Section 5, we discuss cases when
carryover effects are misspecified. We show that our estimation and inference
still remain valid, with only a little more variance. In Section 6, we run
simulations to test the correctness and effectiveness of our proposed
experiments under various simulation setups. In Section 7, we discuss how to
conduct hypothesis testing to identify the true order of carryover effects. We
give empirical illustrations on how to conduct a switchback experiment in
practice. All the proofs can be found in the Appendix.

##  2 Notations, Assumptions, and Regular Switchback Experiments

###  2.1 Assignment Paths and Potential Outcomes

We focus our discussion on a single experimental unit. For example, this unit
could be a ride-hailing platform testing the effectiveness of a new fare
pricing algorithm in a large city, or a retailer testing the effectiveness of
a new promotion planning algorithm over all its SKU’s. At each time point
$t\in[T]=\\{1,2,...,T\\}$, we assign the unit to receive an intervention
$W_{t}\in\\{0,1\\}$. For example, one experimental period could be several
minutes to one hour for a ride-hailing platform or one to two days for a
retailer; the intervention could be a new pricing or promotion planning
algorithm. In some applications, external factors determine the time horizon,
$T$; however, when $T$ is not fixed, Section 7.2, provides details for how the
manager can determine an appropriate $T$.

Following convention, we say that the unit is assigned to treatment if
$W_{t}=1$ and control when $W_{t}=0$; in A/B testing terminology, “A” is
control and “B” is treatment. The assignment path is then the collection of
assignments and is denoted using a vector notation whose dimensions are
specified in the subscript,
$\bm{W}_{1:T}=(W_{1},W_{2},...,W_{T})\in\\{0,1\\}^{T}$. We adopt the
convention that $\bm{W}_{1:t}$ stands for a random assignment path, while
$\bm{w}_{1:t}$ stands for one realization of the random assignment path.
Though we focus on binary assignments, our results easily extend to more
complex settings.

After administering the assigned intervention, we observed a corresponding
outcome. For example, this could be total traffic or total revenue generated
during each experimental period. Let
$\\{t:t^{\prime}\\}=\\{t,t+1,...,t^{\prime}\\}$. Following the extended
potential outcomes framework, at time $t\in[T]$, we posit that for each
possible assignment path $\bm{w}_{1:T}$ there exists a corresponding potential
outcome denoted by $Y_{t}(\bm{w}_{1:T})$. The set of all potential outcomes
will then be written as
$\mathbb{Y}=\\{Y_{i}(\bm{w}_{1:T})\\}_{t\in[T],\bm{w}_{1:T}\in\\{0,1\\}^{T}}$.

Figure 1: Illustrator of assignment paths and potential outcomes when $T=4$.
The green path stands for one assignment path $\bm{w}_{1:4}=(1,1,0,0)$. The
two red dots stand for two potential outcomes that are equal in Example 1.

When $T=4$, there are $16$ assignment paths as shown in Figure 1. Associated
with each assignment path $\bm{w}_{1:4}$ are potential outcomes
$Y_{1}(\bm{w}_{1:4}),Y_{2}(\bm{w}_{1:4}),Y_{3}(\bm{w}_{1:4}),Y_{4}(\bm{w}_{1:4})$.

Throughout this paper, we do not directly model the potential outcomes or
impose a parametric relationship with the assignment path; instead, we treat
them as unknown but fixed quantities, or, equivalently, we will implicitly
condition on $\mathbb{Y}$ (Imbens and Rubin 2015, Chapter 5). The benefit of
this approach is that we can be completely agnostic to the outcome process,
allowing us to make nonparametric causal claims. To make inference possible,
we rely on the variation introduced by the random assignment path; this is
commonly referred to as finite-sample or design-based perspective. Unlike
traditional sampling-based inference, our approach does not require a
hypothetical population from which we sampled our experimental units (Abadie
et al. 2020).

Since the potential outcomes are fixed but unknown, we can assume that their
absolute values are bounded from above (Robins et al. 1999, Bai 2019, Li et
al. 2020). Assumption 1 is almost always satisfied, since it only assumes that
the potential outcomes are bounded by the same constant $B$, _e.g._ , the
total traffic or revenue generated from each experimental period is some
finite amount.

[Bounded Potential Outcomes] Assume that the potential outcomes are bounded by
some constant, i.e., $\exists B>0,s.t.\forall
t\in[T],\forall\bm{w}\in\\{0,1\\}^{T}$,

$\left|Y_{t}(\bm{w})\right|\leq B$

and denote $\mathbb{Y}\in[-B,B]^{T}:=\mathcal{Y}$. In particular, knowledge
about the magnitude of $B$ is not required.

We further make the following two assumptions that limit the dependence of the
potential outcomes on assignment paths. [Non-anticipating Potential Outcomes]
Assume for any $t\in[T]$, $\bm{w}_{1:t}\in\\{0,1\\}^{T}$, and for any
$\bm{w}^{\prime}_{t+1:T},\bm{w}^{\prime\prime}_{t+1:T}\in\\{0,1\\}^{T-t}$,

$Y_{t}(\bm{w}_{1:t},\bm{w}^{\prime}_{t+1:T})=Y_{t}(\bm{w}_{1:t},\bm{w}^{\prime\prime}_{t+1:T}).$

Assumption 1 states that the potential outcomes at time $t$ do not depend on
future treatments (Bojinov and Shephard 2019, Basse et al. 2019, Rambachan and
Shephard 2019). Since we control the assignment mechanism, the design ensures
that this assumption is satisfied.

[Example 2.1 Continued] Under Assumption 1, $Y_{3}(1,1,1,1)=Y_{3}(1,1,1,0)$.
So we use the red dot at $Y_{3}(1,1,1)$ to stand for both $Y_{3}(1,1,1,1)$ and
$Y_{3}(1,1,1,0)$.

[No $m$-Carryover Effects] Assume there exists a fixed and given $m$, such
that for any $t\in\\{m+1,m+2,...,T\\},\bm{w}_{t-m:T}\in\\{0,1\\}^{T-t+m+1}$,
and for any
$\bm{w}^{\prime}_{1:t-m-1},\bm{w}^{\prime\prime}_{1:t-m-1}\in\\{0,1\\}^{t-m-1}$,

$Y_{t}(\bm{w}^{\prime}_{1:t-m-1},\bm{w}_{t-m:T})=Y_{t}(\bm{w}^{\prime\prime}_{1:t-m-1},\bm{w}_{t-m:T}).$

Assumption 1 restricts the order of carryover effect (Laird et al. 1992, Senn
and Lambrou 1998, Bojinov and Shephard 2019, Basse et al. 2019). In many
applications, Assumption 1 is satisfied; however, practitioners must rely on
their domain knowledge to choose an appropriate $m$. For example, surge
pricing on a ride-hailing platform is typically known not to carry over for
more than $1\sim 2$ hours, depending on the city size (Garg and Nazerzadeh
2019). Stockpiling of beverage drinks induced by a promotion is typically
consumed within a few days, due to the “pantry effect” (Ailawadi and Neslin
1998, Bell et al. 1999). Assuming an incorrect $m$ will not invalidate the
subsequent inference, but will lead to a little increase in variance. See
Section 5 and 6.5 for discussions. Moreover, we can always correctly identify
$m$ with a little more experimental budget. See Section 7.1 for discussions.

Under both Assumptions 1 and 1, we simplify notations as follows. For any
$t\in\\{m+1,...,T\\}$, $\bm{w}_{t-m:t}\in\\{0,1\\}^{m+1}$, and for any
$\bm{w}^{\prime}_{1:t-m-1},\bm{w}^{\prime\prime}_{1:t-m-1}\in\\{0,1\\}^{t-m-1}$,
any $\bm{w}^{\prime}_{t+1:T},\bm{w}^{\prime\prime}_{t+1:T}\in\\{0,1\\}^{T-t}$,

$Y_{t}(\bm{w}^{\prime}_{1:t-m-1},\bm{w}_{t-m:t},\bm{w}^{\prime}_{t+1:T})=Y_{t}(\bm{w}^{\prime\prime}_{1:t-m-1},\bm{w}_{t-m:t},\bm{w}^{\prime\prime}_{t+1:T}).$

In the remainder of this paper, we will write
$Y_{t}(\bm{w}_{1:t-m-1},\bm{w}_{t-m:t},\bm{w}_{t+1:T})=Y_{t}(\bm{w}_{t-m:t})$.

[Example 1 Continued] Suppose $m=1$. Under Assumptions 1 and 1, the potential
outcomes at the 2 red dots in Figure 1 are equal, i.e.,
$Y_{3}(1,1,1)=Y_{3}(0,1,1)$.

###  2.2 Causal Effects

In the potential outcomes approach to causal inference, any comparison of
potential outcomes has a causal interpretation. For any $p\in\mathbb{N}$, let
$\bm{1}_{p+1}=(1,1,...,1)$ be a vector of $p+1$ ones; let
$\bm{0}_{p+1}=(0,0,...,0)$ be a vector of $p+1$ zeros. In this paper, we focus
on the average lag-$p$ causal effect of consecutive treatments on the outcome,
defined for any $p\in[T-1]$,

$\displaystyle\tau_{p}(\mathbb{Y})=\frac{1}{T-p}\sum_{t=p+1}^{T}[Y_{t}(\bm{1}_{p+1})-Y_{t}(\bm{0}_{p+1})].$
(1)

This estimand captures the effects of permanently deploying a new
policy444What is typical in companies is that after the switchback experiment
is finished, managers decide to permanently deploy (or not to deploy) a new
policy. So the unit is always exposed to treatment (or control) hereon., and
has been widely studied in the longitudinal experiments since the early work
of Robins (1986).

Although we focus on an average causal effect, all of our results and analysis
trivially extend to the total causal effect, which does not divide the sum by
the number of estimands, i.e., $(T-p)\tau_{p}(\mathbb{Y})$. The optimal design
as we will show in Section 3 will not be changed. We mainly focus on the $p=m$
case in this section. We refer to Section 5 when $m$ is misspecified, and
Section 7.1 to identify $m$.

The challenge of causal inference on switchback experiments is that we only
observe one assignment path. So in each period $t$, we observe at most either
$Y_{t}(\bm{1}_{p+1})$ or $Y_{t}(\bm{0}_{p+1})$ (and sometimes neither). To
link the observed and potential outcomes, we assume there is only one version
of the treatment, and there is no non-compliance. Let
$\bm{w}^{\mathsf{obs}}_{1:T}$ be the realized assignment path. Let
$Y_{t}^{\mathsf{obs}}=Y_{t}(\bm{w}^{\mathsf{obs}}_{1:T})$ be the observed
outcome at time $t$, under the realized assignment path
$\bm{w}^{\mathsf{obs}}_{1:T}$.

###  2.3 Regular Switchback Experiments

It is the manager’s decision to decide the design of switchback experiments.
In this paper, we narrow our scope to the family of regular switchback
experiments. This family of experiments are parameterized by

$\mathbb{T}=\\{t_{0}=1<t_{1}<t_{2}<...<t_{K}\\}\subseteq[T],$

where $K\in\mathbb{N}$ belongs to the set of all positive integers, and
$\mathbb{T}$ contains a total of $K+1$ integers. For the ease of notations
also let $t_{K+1}=T+1$.

######  Definition 2.1 (Regular Switchback Experiments)

For any $K\in\mathbb{N}$ and any
$\mathbb{T}=\\{t_{0}=1<t_{1}<t_{2}<...<t_{K}\\}\subseteq[T]$, a regular
switchback experiment $\mathbb{T}$ administers a probabilistic treatment at
any time $t$, given by:

$\Pr(W_{t}=1)=\left\\{\begin{aligned} &1/2,&&\text{ \ if \ }t\in\mathbb{T}\\\
&\text{1}\\{W_{t-1}=1\\},&&\text{ \ if \
}t\notin\mathbb{T}\end{aligned}\right.$ (2)

In words, the manager decides on a collection of randomization points, which
consists of flipping a fair coin at each period $t\in\\{t_{0},...,t_{K}\\}$.
If the resulting flip at period $t_{k}$ is heads, then the manager assigns the
unit to treatment during periods $(t_{k},t_{k}+1,...,t_{k+1}-1)$; otherwise,
if tails, then the manager assign the unit to control during periods
$(t_{k},t_{k}+1,...,t_{k+1}-1)$. The reason behind fair coin flips are the
inherent symmetry and ignorance of the manager. When $t\in\mathbb{T}$, the
treatment probability that leads to the smallest variance is $1/2$.

###### Example 2.2

When $T=4$, $\mathbb{T}=\\{t_{0}=1,t_{1}=3\\}$ corresponds to the following
design: with probability $1/4$, $\bm{W}_{1:4}=(1,1,1,1)$; with probability
$1/4$, $\bm{W}_{1:4}=(1,1,0,0)$; with probability $1/4$,
$\bm{W}_{1:4}=(0,0,1,1)$; with probability $1/4$, $\bm{W}_{1:4}=(0,0,0,0)$.
See Figure 2 (left figure).

###### Example 2.3

Not all switchback experiments are regular. For example, when $T=4$: with
probability $1/4$, $\bm{W}_{1:4}=(1,1,1,0)$; with probability $1/4$,
$\bm{W}_{1:4}=(1,0,0,0)$; with probability $1/4$, $\bm{W}_{1:4}=(0,1,1,1)$;
with probability $1/4$, $\bm{W}_{1:4}=(0,0,0,1)$. See Figure 2 (right figure).

Figure 2: Two designs. The blue lines stand for the possible treatment
assignments that a design could administer. Left: regular switchback
experiment (Example 2.2); Right: irregular switchback experiment (Example
2.3).

Any design of switchback experiment induces a probabilistic distribution over
assignment paths $\bm{w}_{1:T}\in\\{0,1\\}^{T}$. Define a design of switchback
experiment to be any $\eta:\\{0,1\\}^{N}\to[0,1]$ such that

$\displaystyle\sum_{\bm{w}_{1:T}\in\\{0,1\\}^{T}}\eta(\bm{w}_{1:T})=1,$
$\displaystyle\eta(\bm{w}_{1:T})\geq 0,\ \forall\bm{w}_{1:T}\in\\{0,1\\}^{T}.$

Explicitly, $\eta(\cdot)$ is the underlying discrete distribution of the
random assignment path $\bm{W}_{1:T}$. For any regular switchback experiment
$\mathbb{T}$, we refer to the probability distribution using
$\eta_{\mathbb{T}}(\cdot)$.

For any $\mathbb{T}$, there are a total of $2^{K+1}$ many assignment paths,
which are uniquely determined by the values of
$W_{t_{0}},W_{t_{1}},...,W_{t_{K}}$. The assignment path is random, and
follows the probability distribution $\eta_{\mathbb{T}}(\cdot)$:

$\eta_{\mathbb{T}}(\bm{w}_{1:T})=\left\\{\begin{aligned} &1/2^{K+1},&&\text{ \
if \ }\forall k\in\\{0,1,...,K\\},w_{t_{k}}=w_{t_{k}+1}=...=w_{t_{k+1}-1},\\\
&0,&&\text{ \ otherwise. \ }\end{aligned}\right.$ (3)

In the remainder of this paper, unless explicitly noted, all probabilities and
expectations are taken with respect to this probability distribution
$\eta_{\mathbb{T}}(\cdot)$.

###  2.4 Estimation

Now that $\eta_{\mathbb{T}}(\cdot)$ is determined, following any realization
of the assignment path $\bm{W}_{1:T}=\bm{w}_{1:T}$, we use the Horvitz-
Thompson estimator to estimate the lag-$p$ effect:

$\displaystyle\hat{\tau}_{p}(\eta_{\mathbb{T}},\bm{w}_{1:T},\mathbb{Y})$
$\displaystyle=\frac{1}{T-p}\sum_{t=p+1}^{T}\left\\{Y_{t}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{w}_{t-p:t}=\bm{1}_{p+1}\\}}}{\Pr(\bm{W}_{t-p:t}=\bm{1}_{p+1})}-Y_{t}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{w}_{t-p:t}=\bm{0}_{p+1}\\}}}{{\Pr(\bm{W}_{t-p:t}=\bm{0}_{p+1})}}\right\\}$
(4)

Since the assignment path $\bm{W}_{1:T}$ is random, this Horvitz-Thompson
estimator is random, as well. We emphasize that estimator depends on (i) the
probability distribution behind the random assignment path, (ii) the
realization of the assignment path, and (iii) the potential outcomes.

###### Example 2.4

Suppose $T=4,p=m=1$. See Figure 1. Suppose the assignments are probabilistic
and $\Pr(W_{t}=1)=\Pr(W_{t}=0)=1/2,\forall t\in[4].$ With probability $1/16$
the green assignment path is administered, $\bm{W}_{1:4}=(1,1,0,0)$. The
estimator is
$\hat{\tau}_{1}=\frac{1}{3}\left\\{4Y_{2}(1,1)+0-4Y_{4}(0,0)\right\\}.$

It is well-known that the Horvitz-Thompson estimator is unbiased under the
probabilistic treatment assignment assumption, which is satisfied by regular
switchback experiments.

[Probabilistic Treatment Assignment] Assume for any $t\in\\{p+1:T\\}$, both
$0<\Pr(\bm{W}_{t-p:t}=\bm{1}_{p+1}),\Pr(\bm{W}_{t-p:t}=\bm{0}_{p+1})<1$.

It is easy to verify that regular switchback experiments satisfy Assumption
2.4, since the assignment on the firs period is random, i.e.
$\Pr(W_{1}=1)=1/2$.

######  Theorem 2.5 (Unbiasedness of the Horvitz-Thompson Estimator)

In a regular switchback experiment, under Assumptions 1 and 1, the Horvitz-
Thompson estimator is unbiased for the average lag-$p$ causal effect of
consecutive treatments on outcome, i.e.,

$\mathbb{E}_{\bm{W}_{1:T}\sim\eta_{\mathbb{T}}}[\hat{\tau}_{p}(\eta_{\mathbb{T}},\bm{W}_{1:T},\mathbb{Y})]=\tau_{p}(\mathbb{Y}).$

The proof to Theorem 2.5 is standard, by checking the expectations. We defer
its proof to Section 11 in the Appendix. When $m$ is misspecified, the above
estimator is still meaningful with causal interpretations. See Section 5 for a
discussion.

###  2.5 Evaluation of Experiments: the Decision-Theoretic Framework

To evaluate the quality of a design of experiment, we adopt the decision-
theoretic framework (Berger 2013, Bickel and Doksum 2015). When the random
design is $\eta_{\mathbb{T}}(\cdot)$, the assignment path $\bm{W}_{1:T}$ is
random. For any realization of the assignment path $\bm{w}_{1:T}$ and any set
of potential outcomes $\mathbb{Y}$, we define the loss function

$\displaystyle
L(\eta_{\mathbb{T}},\bm{w}_{1:T},\mathbb{Y})=\left(\hat{\tau}_{p}(\eta_{\mathbb{T}},\bm{w}_{1:T},\mathbb{Y})-\tau_{p}(\mathbb{Y})\right)^{2}$

and the risk function

$\displaystyle r(\eta_{\mathbb{T}},\mathbb{Y})$
$\displaystyle=\mathbb{E}_{\bm{W}_{1:T}\sim\eta_{\mathbb{T}}(\cdot)}\left[L(\eta_{\mathbb{T}},\bm{W}_{1:T},\mathbb{Y})\right]$
$\displaystyle=\sum_{\bm{w}_{1:T}\in\\{0,1\\}^{T}}\eta_{\mathbb{T}}(\bm{w}_{1:T})\cdot\left(\hat{\tau}_{p}(\eta_{\mathbb{T}},\bm{w}_{1:T},\mathbb{Y})-\tau_{p}(\mathbb{Y})\right)^{2}$
(5)

Such a risk function quantifies the expected loss incurred by one design of
experiment. Since the estimator is unbiased, the risk function also has a
second interpretation: the variance of the estimator. A design with lower risk
is also a design whose estimator has a lower variance.

######  Example 2.6 (Examples 2.2 and 2.4 Revisited)

Suppose $T=4$ and $p=m=1$. As in Example 2.2, the experiment is
$\mathbb{T}=\\{1,3\\}$. With probability $1/4$, $\bm{W}_{1:4}=(1,1,0,0)$, and
$\hat{\tau}_{1}(\mathbb{T})=\frac{1}{3}\\{2Y_{2}(1,1)-2Y_{4}(0,0)\\}$. So
$L(\eta_{\tilde{\mathbb{T}}},\bm{w}_{1:T},\mathbb{Y})=\frac{1}{9}\left(Y_{2}(1,1)+Y_{2}(0,0)-Y_{3}(1,1)+Y_{3}(0,0)-Y_{4}(1,1)-Y_{4}(0,0)\right)^{2}.$
As in Example 2.4, $\tilde{\mathbb{T}}=\\{1,2,3,4\\}$. With probability
$1/16$, $\bm{W}_{1:4}=(1,1,0,0)$, and
$\hat{\tau}_{1}(\tilde{\mathbb{T}})=\frac{1}{3}\\{4Y_{2}(1,1)-4Y_{4}(0,0)\\}$.
So
$L(\eta_{\mathbb{T}},\bm{w}_{1:T},\mathbb{Y})=\frac{1}{9}\left(3Y_{2}(1,1)+Y_{2}(0,0)-Y_{3}(1,1)+Y_{3}(0,0)-Y_{4}(1,1)-3Y_{4}(0,0)\right)^{2}.$

Example 2.6 suggests that, even if the two realizations of the assignment path
are the same and the potential outcomes are the same, since the probability
distributions $\mathbb{T},\tilde{\mathbb{T}}$ are different, the corresponding
loss functions could be different. This motivates us to find a probability
distribution with a smaller expected loss against some $\mathbb{Y}$, which we
will detail in Section 3.

##  3 Design of Regular Switchback Experiments under Minimax Rule

The minimax decision rule (Berger 2013, Wu 1981) finds an optimal design of
experiment, such that the worst-case risk against an adversarial selection of
potential outcomes is minimized,

$\displaystyle\min_{\mathbb{T}\in[T]}\max_{\mathbb{Y}\in\mathcal{Y}}\
r(\eta_{\mathbb{T}},\mathbb{Y})=\min_{\mathbb{T}\in[T]}\max_{\mathbb{Y}\in\mathcal{Y}}\
\sum_{\bm{w}_{1:T}\in\\{0,1\\}^{T}}\eta_{\mathbb{T}}(\bm{w}_{1:T})\cdot\left(\hat{\tau}_{p}(\bm{w}_{1:T},\mathbb{Y})-\tau_{p}(\mathbb{Y})\right)^{2}.$
(6)

The goal of this section is to find the optimal $\mathbb{T}^{*}\subseteq[T]$.
Throughout this section we assume perfect knowledge of $m$ and assume $p=m$.

In practice, there is a trade-off between having too few randomization points
( corresponding to small $K$) and too many (corresponding to large $K$).
Intuitively, too many decreases the probability of observing an assignment
path $\bm{1}_{m+1}$ or $\bm{0}_{m+1}$, which, in turn, decreases the amount of
useful data. On the other hand, too few decreases the number of independent
observations and reduces our ability to produce reliable results. Both of
these scenarios reduce our ability to draw valid causal claims. To make
switchback experiments useful in practice, we need to find the optimal number
of randomization points that allows us to draw valid inference while
minimizing the variance. We formalize this goal through the minimax framework,
where we try to derive the best possible design for the worse possible set of
potential outcomes.

To solve the minimax problem, we start by focusing on the inner maximization
part of (6). We characterize the worst-case potential outcomes by identifying
two dominating strategies for the adversarial selection of potential outcomes.
Denote
$\mathbb{Y}^{+}=\left\\{Y_{t}(\bm{1}_{m+1})=Y_{t}(\bm{0}_{m+1})=B\right\\}_{t\in\\{m+1:T\\}}$
and
$\mathbb{Y}^{-}=\left\\{Y_{t}(\bm{1}_{m+1})=Y_{t}(\bm{0}_{m+1})=-B\right\\}_{t\in\\{m+1:T\\}}$

###### Lemma 3.1

Under Assumptions 1–1, $\mathbb{Y}^{+}$ and $\mathbb{Y}^{-}$ are the only two
dominating strategies for the adversarial selection of potential outcomes.
That is, for any $\mathbb{T}\subseteq[T]$ and for any
$\mathbb{Y}\in\mathcal{Y}$,

$\displaystyle r(\eta_{\mathbb{T}},\mathbb{Y}^{+})\geq
r(\eta_{\mathbb{T}},\mathbb{Y});$ $\displaystyle
r(\eta_{\mathbb{T}},\mathbb{Y}^{-})\geq r(\eta_{\mathbb{T}},\mathbb{Y}).$

Moreover, for any $\mathbb{Y}\in\mathcal{Y}$ such that
$\mathbb{Y}\neq\mathbb{Y}^{+}$ or $\mathbb{Y}^{-}$, the above two inequalities
are strict.

The proof of Lemma 3.1 and an implication of Lemma 3.1 can be found in
Sections 12.2.2 and 12.2.3, respectively.

######  Example 3.2 (Example 2.2 Continued)

Suppose $T=4$, $p=m=1$, and $\mathbb{T}=\\{1,3\\}$. The risk function can be
calculated by
$r(\eta_{\mathbb{T}},\mathbb{Y})=\sum_{t=2}^{4}\left[(Y_{t}(1,1)+Y_{t}(0,0))^{2}\right]+2Y_{3}(1,1)^{2}+2Y_{3}(0,0)^{2}+2\sum_{t=2}^{3}\left[(Y_{t}(1,1)+Y_{t}(0,0))(Y_{t+1}(1,1)+Y_{t+1}(0,0))\right]$.
The risk function is maximized by $\mathbb{Y}$ (only) at
$Y_{t}(1,1)=Y_{t}(0,0)=\pm B,\forall t\in\\{2:4\\}.$ This is what Lemma 3.1
says.

Lemma 3.1 simplifies the minimax problem in (6). Instead of directly solving
the minimax problem, we can now replace $\mathbb{Y}$ by either
$\mathbb{Y}^{+}$ or $\mathbb{Y}^{-}$, and solve only a minimization problem.

Using Lemma 3.1, we now establish two structural results that limit the class
of optimal designs of regular switchback experiments. Lemma 3.3 states the
optimal starting and ending structure; Lemma 3.4 states the optimal middle-
case structure. The proofs to Lemma 3.3 and Lemma 3.4 are deferred to Sections
12.3.1 and 12.3.2, respectively.

###### Lemma 3.3

When $\mathbb{Y}=\mathbb{Y}^{+}$ or $\mathbb{Y}=\mathbb{Y}^{-}$, under
Assumptions 1–1, any optimal design of experiment $\mathbb{T}$ must satisfy

$\displaystyle t_{1}\geq m+2,$ and $\displaystyle t_{K}\leq T-m.$

Lemma 3.3 suggests that the first coin flip on period $1$ should be followed
by at least $m$ periods that do not flip a coin, and that the last coin flip
should be followed by at least $m$ periods that do not flip a coin. It
guarantees that the assignment path during $\\{1:m+1\\}$ and during
$\\{T-m:T\\}$ are both useful, i.e., $\bm{1}_{m+1}$ or $\bm{0}_{m+1}$.

###### Lemma 3.4

When $\mathbb{Y}=\mathbb{Y}^{+}$ or $\mathbb{Y}=\mathbb{Y}^{-}$, under
Assumptions 1–1, any optimal design of experiment $\mathbb{T}$ must satisfy

$\displaystyle t_{k+1}-t_{k-1}\geq m,\ \forall k\in[K].$

Lemma 3.4 suggests that in every consecutive $m+1$ periods, there could be at
most $3$ randomization points. This is because too many randomization points
in every consecutive $m+1$ periods decreases the chance of observing an useful
assignment path of $\bm{1}_{m+1}$ or $\bm{0}_{m+1}$. Lemma 3.4 formalizes such
intuition, and suggests that when $m$ grows large, the optimal design
randomizes less often.

Lemmas 3.3 and 3.4 restrict the space of possible optimal regular switchback
experiment to a smaller class of switchback experiments, which we define
below.

######  Definition 3.5 (Persistent Switchback Experiments)

We say a regular switchback experiment $\mathbb{T}$ is persistent, if it
satisfies the following three conditions,

$\displaystyle t_{1}\geq m+2;$ $\displaystyle t_{K}\leq T-m;$ $\displaystyle
t_{k+1}-t_{k-1}\geq m,\ \forall k\in[K].$

For persistent switchback experiments, we can explicitly calculate the risk
function $r(\eta_{\mathbb{T}},\mathbb{Y})$.

######  Theorem 3.6 (Risk Function)

When $\mathbb{Y}=\mathbb{Y}^{+}$ or $\mathbb{Y}=\mathbb{Y}^{-}$, under
Assumptions 1–1, the risk function for any persistent switchback experiment is
given by

$\displaystyle
r(\eta_{\mathbb{T}},\mathbb{Y})=\frac{1}{(T-m)^{2}}\left\\{4\sum_{k=1}^{K+1}(t_{k}-t_{k-1})^{2}+8m(t_{K}-t_{1})+4m^{2}K-4m^{2}+4\sum_{k=2}^{K}[(m-t_{k}+t_{k-1})^{+}]^{2}\right\\}B^{2}$
(7)

Theorem 3.6 explicitly describes the risk function of any optimal design of
regular switchback experiments, which lies in the class of persistent
switchback experiments. The proof of Theorem 3.6 is deferred to Section 12.4
in the appendix.

To understand the risk function in (7), note that the first summation of the
squares $\sum_{k=1}^{K+1}(t_{k}-t_{k-1})^{2}$ suggests that the gap between
two consecutive randomization points should not be too big; while the last
summation of the squares $\sum_{k=2}^{K}[(m-t_{k}+t_{k-1})^{+}]^{2}$ suggests
that the gap should not be too small. Such a contrast formalized the trade-off
that we have described earlier in this section.

Based on the risk function in (7), we are able to describe the optimal design,
as we state in the next Theorem.

######  Theorem 3.7 (Optimal Design)

Under Assumptions 1–1, the optimal solution to the design of regular
switchback experiment as we have introduced in (6) is equivalent to the
optimal solution to the following subset selection problem.

$\displaystyle\min_{\mathbb{T}\subset[T]}\left\\{4\sum_{k=0}^{K}(t_{k+1}-t_{k})^{2}+8m(t_{K}-t_{1})+4m^{2}K-4m^{2}+4\sum_{k=1}^{K-1}[(m-t_{k+1}+t_{k})^{+}]^{2}\right\\}$
(8)

In particular, when $m=0$ then $\mathbb{T}^{*}=\\{1,2,3,...,T\\}$; when $m>0$,
and if there exists $n\geq 4\in\mathbb{N}$, s.t. $T=nm$, then
$\mathbb{T}^{*}=\\{1,2m+1,3m+1,...,(n-2)m+1\\}$.

The optimal design under two remarkable special cases are, when $m=0$,
$\mathbb{T}^{*}=\\{1,2,3,...,T\\}$; and when $m=1$,
$\mathbb{T}^{*}=\\{1,3,4,...,T-1\\}$. When managers believe there to be very
little carryover effect, the optimal designs are almost the same. Moreover,
Theorem 3.7 presents the optimal design in a class of perfect cases when the
time horizon split into several epochs. In practice, selecting $T$ is part of
the design of the experiment; our recommendation is to pick a $T$ that
satisfies the conditions in Theorem 3.7. See Section 7.2.

We can also find the optimal design for other imperfect cases by solving (8);
however, since there are integrality issues in the subset selection problem,
the discussion of optimal design in such imperfect cases are rather technical.
We defer to Section 12.5 in the appendix to discuss such details. The proof of
Theorem 3.7 is deferred to Section 12.5.1 in the appendix.

######  Example 3.8 (An Optimal Design)

When $T=12$, $p=m=2$, the optimal design of regular switchback experiment is
$\mathbb{T}^{*}=\\{1,5,7,9\\}$. See Table 3.8.

An example of the optimal design $\mathbb{T}^{*}$ versus an arbitrary design
$\tilde{\mathbb{T}}$ when $T=12$ and $p=m=2$.  1 2 3 4 5 6 7 8 9 10 11 12
$\mathbb{T}^{*}$ $\checkmark$ $-$ $-$ $-$ $\checkmark$ $-$ $\checkmark$ $-$
$\checkmark$ $-$ $-$ $-$ $\tilde{\mathbb{T}}$ $\checkmark$ $-$ $-$
$\checkmark$ $-$ $-$ $\checkmark$ $-$ $-$ $\checkmark$ $-$ $-$ Each checkmark
beneath a time period $t$ indicates that $t$ is a randomization point.

It is worth noting that both the causal estimand and the Horvitz-Thompson
estimator involve consecutive treatments or controls for $m+1$ periods. By
contrast, Theorem 3.7 suggests that the optimal design have epochs of equal
length $m$ (ignoring the first and last epoch).

At a first sight this is counter-intuitive. Intuitively, each epoch should
contain at least $m+1$ periods so there exist periods that always have
consecutive treatments $\bm{1}_{m+1}$ or $\bm{0}_{m+1}$ and always generate
useful data; _e.g._ , periods $\tilde{t}=4,7,10$ in the third row of Table
3.8. However, even if each epoch had $m+1$ periods, there are still many
periods that do not always generate useful data (_e.g._ , periods
$\tilde{t}=5,6,8,9$); invalidating this intuition.

To understand the implications of Theorem 3.7, the correct intuition is the
there is a trade-off between too many and too few randomization points. Due to
the inherent underlying discrete convexity nature behind the minimax problem
(6), the optimum balances randomization frequency between the two extremes.
Theorem 3.7, quantifies this balance.

##  4 Inference and Statistical Testing

After designing and running the experiment, we obtain two time series. The
first is the observed assignment path $\bm{w}_{1:T}^{\mathsf{obs}}$, and the
second is the corresponding observed outcomes $\bm{Y}_{p+1:T}^{\mathsf{obs}}$.
See Figure 3. To draw inference from this data we propose two methods, the
exact inference and the asymptotic inference, as we detail below.

Figure 3: Illustrator of the observed assignment path
$\bm{w}_{1:T}^{\mathsf{obs}}$ (blue and red dots) and the observed outcomes
$\bm{Y}_{p+1:T}^{\mathsf{obs}}$ (black curve). The dashed lines are the
potential outcomes under consecutive treatments / controls.

Throughout this section we assume perfect knowledge of $m$, i.e., $p=m$, and
we will write $\tau_{m}$ and $\hat{\tau}_{m}$ to stand for $\tau_{p}$ and
$\hat{\tau}_{p}$, respectively. When $m\neq p$, our inference methods are
still valid. See Section 5 for a discussion, and see Section 6.5 for a
numerical example.

###  4.1 Exact Inference

We propose an exact non-parametric test for the sharp null of no causal effect
at every time point

$H_{0}:Y_{t}(\bm{1}_{m+1})-Y_{t}(\bm{0}_{m+1})=0\quad\text{for all
}t=1,2,...,T.$ (9)

This will be tested against a portmanteau alternative. The sharp null
hypothesis implies that
$Y_{t}(\bm{w}_{t-m:t}^{\mathsf{obs}})=Y_{t}(\bm{w}_{t-m:t}^{\prime})$ for all
$\bm{w}_{t-m:t}^{\prime}\in\\{0,1\\}^{t}$; that is, regardless of the
assignment path $\bm{w}_{t-m:t}^{\prime}$ we would have observed the same
outcomes.

We can conduct exact tests by using the known assignment mechanism to simulate
new assignment paths. Algorithm 1 provides the details of how to implement it.
In particular, under the sharp null hypothesis of no treatment effect (9), any
assignment path $\bm{w}^{[i]}_{1:T}$ leads to the same observed outcomes. So
in Step 3, we always plug in the same observed outcomes
$Y^{\mathsf{obs}}_{p+1:T}$. To obtain a confidence interval, we propose
inverting a sequence of exact hypothesis tests to identify the region outside
of which (9) is violated at the prespecified nominal level (Imbens and Rubin
2015, Chapter 5).

0: Fix $I$, total number of samples drawn.

1: for i in $1:I$ do

2: Sample a new assignment path $\bm{w}_{1:T}^{[i]}$ according to the
assignment mechanism.

3: Hold $Y^{\mathsf{obs}}_{p+1:T}$ unchanged. Compute $\hat{\tau}^{[i]}$
according to (4),  $\displaystyle\hat{\tau}^{[i]}$
$\displaystyle=\frac{1}{T-m}\sum_{t=m+1}^{T}\left\\{Y_{t}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{w}^{[i]}_{t-m:t}=\bm{1}_{m+1}\\}}}{\Pr(\bm{W}_{t-m:t}=\bm{1}_{m+1})}-Y_{t}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{w}^{[i]}_{t-m:t}=\bm{0}_{m+1}\\}}}{{\Pr(\bm{W}_{t-m:t}=\bm{0}_{m+1})}}\right\\}.$

4: end for

5: Compute
$\hat{p}_{\mathsf{F}}=I^{-1}\sum_{i=1}^{I}\text{1}\left\\{\left|\hat{\tau}^{[i]}\right|>\left|\hat{\tau}\right|\right\\}$

6: return $\hat{p}_{\mathsf{F}}$, the estimated $p$-value. For large $I$, this
is exact.

Algorithm 1 Algorithm for performing a sharp-null hypothesis test

###  4.2 Asymptotic Inference

Now we introduce the asymptotic inference method, which tests the following
null hypothesis

$H_{0}:\tau_{m}=\frac{1}{T-m}\sum_{t=m+1}^{T}[Y_{t}(\bm{1}_{m+1})-Y_{t}(\bm{0}_{m+1})]=0.$
(10)

The testing of such null hypothesis is based on the Horvitz-Thompson estimator
in (4) being asymptotically Gaussian. Below we introduce how to conduct
asymptotic inference.

Assume $n=T/,\geq 4$ is an integer, then under the optimal design as shown in
Theorem 3.7, the assignment path is determined by the realizations at
$W_{1},W_{2m+1},...,W_{(n-2)m+1}$. To make the dependence on randomization
clear, denote the following notations. Let $\mathbb{N}_{0}$ be the set of all
non-negative integers. For any $k\in\mathbb{N}_{0}$, let
$\bar{Y}_{k}(\bm{1}_{m+1})=\sum_{t=(k+1)m+1}^{(k+2)m}Y_{t}(\bm{1}_{m+1})$ and
$\bar{Y}_{k}(\bm{0}_{m+1})=\sum_{t=(k+1)m+1}^{(k+2)m}Y_{t}(\bm{0}_{m+1})$.
Moreover, let
$\bar{Y}_{k}^{\mathsf{obs}}=\sum_{t=(k+1)m+1}^{(k+2)m}Y_{t}^{\mathsf{obs}}$ be
the summation of observed outcomes.

######  Theorem 4.1 (Variance of the Horvitz-Thompson Estimator)

Under Assumptions 1–1, if $n=T/m\geq 4$ is an integer, then under the optimal
design as shown in Theorem 3.7, the variance of the Horvitz-Thompson
estimator, $\mathsf{Var}(\hat{\tau}_{m})$, is

$\displaystyle\mathsf{Var}(\hat{\tau}_{m})=\frac{1}{(T-m)^{2}}$
$\displaystyle\left\\{\bar{Y}_{0}(\bm{1}_{m+1})^{2}+\bar{Y}_{0}(\bm{0}_{m+1})^{2}+2\bar{Y}_{0}(\bm{1}_{m+1})\bar{Y}_{0}(\bm{0}_{m+1})\vphantom{\sum_{k=0}^{n-3}2\left[\bar{Y}_{k}(\bm{1}_{m+1})\right]}\right.$
$\displaystyle+\sum_{k=1}^{n-3}\left[3\bar{Y}_{k}(\bm{1}_{m+1})^{2}+3\bar{Y}_{k}(\bm{0}_{m+1})^{2}+2\bar{Y}_{k}(\bm{1}_{m+1})\bar{Y}_{k}(\bm{0}_{m+1})\right]$
$\displaystyle+\bar{Y}_{n-2}(\bm{1}_{m+1})^{2}+\bar{Y}_{n-2}(\bm{0}_{m+1})^{2}+2\bar{Y}_{n-2}(\bm{1}_{m+1})\bar{Y}_{n-2}(\bm{0}_{m+1})$
$\displaystyle+\left.\sum_{k=0}^{n-3}2\left[\bar{Y}_{k}(\bm{1}_{m+1})+\bar{Y}_{k}(\bm{0}_{m+1})\right]\cdot\left[\bar{Y}_{k+1}(\bm{1}_{m+1})+\bar{Y}_{k+1}(\bm{0}_{m+1})\right]\right\\}$
(11)

Theorem 4.1 provides the variance of the estimator. Since we never observe all
the potential outcomes, many of the cross-product terms from the variance can
never be estimated. As an alternative, we provide the following two upper
bounds, and detail two unbiased estimators of such two upper bounds,
respectively.

###### Corollary 4.2

Under the conditions in Theorem 4.1, there exist two upper bounds for the
variance of the Horvitz-Thompson estimator,
$\mathsf{Var}(\hat{\tau}_{m})\leq\mathsf{Var}^{\mathsf{U1}}(\hat{\tau}_{m})\leq\mathsf{Var}^{\mathsf{U2}}(\hat{\tau}_{m})$.
These two upper bounds $\mathsf{Var}^{\mathsf{U1}}(\hat{\tau}_{m})$ and
$\mathsf{Var}^{\mathsf{U2}}(\hat{\tau}_{m})$ can be estimated by
$\hat{\sigma}^{2}_{\mathsf{U1}}$ and $\hat{\sigma}^{2}_{\mathsf{U2}}$,
respectively, where

$\hat{\sigma}^{2}_{\mathsf{U1}}=\frac{1}{(T-m)^{2}}\left\\{6(\bar{Y}_{0}^{\mathsf{obs}})^{2}+\sum_{k=1}^{n-3}24(\bar{Y}_{k}^{\mathsf{obs}})^{2}\text{1}\\{W_{km+1}=W_{(k+1)m+1}\\}+6(\bar{Y}_{n-2}^{\mathsf{obs}})^{2}\right.\\\
+\left.\sum_{k=0}^{n-3}16\bar{Y}_{k}^{\mathsf{obs}}\bar{Y}_{k+1}^{\mathsf{obs}}\text{1}\\{W_{km+1}=W_{(k+1)m+1}=W_{(k+2)m+1}\\}\right\\},$

and

$\displaystyle\hat{\sigma}^{2}_{\mathsf{U2}}=\frac{1}{(T-m)^{2}}\left\\{8(\bar{Y}_{0}^{\mathsf{obs}})^{2}+\sum_{k=1}^{n-3}32(\bar{Y}_{k}^{\mathsf{obs}})^{2}\text{1}\\{W_{km+1}=W_{(k+1)m+1}\\}+8(\bar{Y}_{n-2}^{\mathsf{obs}})^{2}\right\\}.$

Moreover, $\hat{\sigma}^{2}_{\mathsf{U1}}$ and
$\hat{\sigma}^{2}_{\mathsf{U2}}$ are unbiased, i.e.,
$\mathbb{E}[\hat{\sigma}^{2}_{\mathsf{U1}}]=\mathsf{Var}^{\mathsf{U1}}(\hat{\tau}_{m})$,
and
$\mathbb{E}[\hat{\sigma}^{2}_{\mathsf{U2}}]=\mathsf{Var}^{\mathsf{U2}}(\hat{\tau}_{m})$.

Corollary 4.2 provides the foundation to make conservative inference. We make
the following technical assumption for the asymptotic normal distribution to
hold.

[Non-negligible Variance] Assume that the randomization distribution has a
non-negligible variance, i.e.,

$\displaystyle\mathsf{Var}(\hat{\tau}_{m})\geq\Omega(n^{-1})$ (12)

In particular, one sufficient condition for (12) is to assume that all the
potential outcomes are positive, i.e., there exists some constant $b>0$, such
that $\forall t\in[T],\forall\bm{w}_{1:T}\in\\{0,1\\}^{T}$,
$Y_{t}(\bm{w}_{1:T})\geq b$.

Intuitively, the key to Central Limit Theorem is that all the variables
roughly have the same order of variance, i.e., there cannot be a small number
of variables such that their variances make the majority of the sum.
Assumption 4.2 suggests that the variance is large enough, such that it cannot
come from only a few of the time periods.

######  Theorem 4.3 (Asymptotic Normality)

Let $m$ be fixed. For any $n\geq 4\in\mathbb{N}$, define an $n$-replica
experiment such that there are $T=nm$ time periods. We take the optimal design
as in Theorem 3.7 whose randomization points are at
$\mathbb{T}^{*}=\\{1,2m+1,3m+1,...,(n-2)m+1\\}$. Under Assumptions 1–1, and
under Assumption 4.2, the limiting distribution of the Horvitz-Thompson
estimator in the $n$-replica experiment has an asymptotic normal distribution.
That is, let $\mathsf{Var}(\hat{\tau}_{m})$ be defined in Theorem 4.1. As
$n\to+\infty$,

$\displaystyle\frac{\hat{\tau}_{m}-\tau_{m}}{\sqrt{\mathsf{Var}(\hat{\tau}_{m})}}\xrightarrow[]{D}\mathcal{N}(0,1).$

In particular, Theorem 4.3 does not require $\mathsf{Var}(\hat{\tau}_{m})$ to
converge as $n\to+\infty$.

To conduct inference, we replace $\mathsf{Var}(\hat{\tau}_{m})$ by
$\hat{\sigma}^{2}$, one of the two bounds provided in Corollary 4.2. Define
the test statistic to be
$z=\left|\hat{\tau}_{m}\right|/\sqrt{\hat{\sigma}^{2}}$. When the alternative
hypothesis is two-sided, the estimated $p$-value is given by
$\hat{p}_{\mathsf{N}}=2-2\Phi(z)$, where $\Phi$ is the CDF of a standard
normal distribution.

The proofs of Theorem 4.1, Corollary 4.2, and Theorem 4.3 are deferred to
Sections 13.2, 13.3, and 13.4 in the Appendix, respectively.

##  5 A Discussion about Misspecified $m$

So far we have discussed cases when $m$ is correctly specified. When $m$ is
misspecified, the estimation and inference are still valid and meaningful. We
will detail below cases when $m$ is either overestimated $m<p$, or
underestimated $m>p$.

###  5.1 Causal Effects

When $m$ is overestimated, $m<p$. Due to Assumption 1,
$Y_{t}(\bm{1}_{p+1})=Y_{t}(\bm{1}_{m+1}),\forall t\in\\{p+1:T\\}$, so the
lag-$p$ causal effect is essentially the lag-$m$ causal effect.

When $m$ is underestimated, $m>p$. The lag-$p$ effect in (1) is not well
defined. Instead, we define the $m$-misspecified lag-$p$ causal effect that
pads the $p+1$ assignments with the earlier observed treatments.

$\tau_{p}^{(m)}(\mathbb{Y})=\frac{1}{T-p}\left\\{\sum_{t=p+1}^{m}\left[Y_{t}(\bm{w}^{\mathsf{obs}}_{1:t-p-1},\bm{1}_{p+1})-Y_{t}(\bm{w}^{\mathsf{obs}}_{1:t-p-1},\bm{0}_{p+1})\right]+\right.\\\
\left.\sum_{t=m+1}^{T}\left[Y_{t}(\bm{w}_{t-m:t-p-1}^{\mathsf{obs}},\bm{1}_{p+1})-Y_{t}(\bm{w}_{t-m:t-p-1}^{\mathsf{obs}},\bm{0}_{p+1})\right]\right\\}.$
(13)

This is a special case of the weighted lag-$p$ causal effect introduced in
Bojinov and Shephard (2019). Similarly to the average lag-$p$ causal effect,
$\tau_{p}^{(m)}(\mathbb{Y})$ captures how administering $p+1$ consecutive
treatments as opposed to $p+1$ consecutive controls impact the outcomes at
time $t$, conditional on the observed assignment path up to time $t-p-1$. See
Section 6.5 for numerical results.

###  5.2 Estimator

When $m$ is overestimated ($m<p$) Theorem 2.5 still holds, i.e.,
$\mathbb{E}[\hat{\tau}_{p}]=\tau_{p}(\mathbb{Y})=\tau_{m}(\mathbb{Y})$. When
$m$ is underestimated ($m>p$), sometimes we have to slightly augment the
results and study the conditional expectation.

Define $f_{\mathbb{T}}:[T]\to\mathbb{T}$ to be the “determining randomization
point of period $t$,”

$f_{\mathbb{T}}(t)=\max\left\\{j\left|j\in\mathbb{T},j\leq t\right.\right\\}$

such that, it is the realization at time $f_{\mathbb{T}}(t)$ that uniquely
determines the assignment at time $t$, _i.e._
$W_{t}=W_{f_{\mathbb{T}}(t)},\forall t\in[T]$. See Example 5.2 for an
illustration of $f_{\mathbb{T}}(\cdot)$. When $\mathbb{T}$ is clear from the
context we drop the subscript and use $f(\cdot)=f_{\mathbb{T}}(\cdot)$.
Depending on if $f(t-p)\leq t-m$, we establish an analogy of Theorem 2.5 for
the $m$-underestimated case.

######  Theorem 5.1 (Unbiasedness of the Estimator when $m$ is Misspecified)

Under Assumptions 1 and 1, for $m>p$, at each time $t\geq m+1$, the Horvitz-
Thompson estimator is either unbiased for the lag-$m$ causal effect when
$f(t-p)\leq t-m$, or conditionally unbiased for the $m$-misspecified lag-$p$
causal effect when $f(t-p)>t-m$. When $p+1\leq t\leq m$, the Horvitz-Thompson
estimator is either unbiased for the lag-$t$ causal effect when $f(t-p)=1$, or
conditionally unbiased for the $m$-misspecified lag-$t$ causal effect when
$f(t-p)>1$.

To remove the conditional expectation, we can further take an outer loop of
expectation averaged over the past assignment paths. Although this is somewhat
different from the average lag-$p$ effect introduced earlier in (1), it does
capture the impact of a sequence of treatment relative to a sequence of
controls.

All the mathematical expressions of Theorem 5.1, as well its proof, are all
stated in Section 14.1 in the Appendix. See Example 5.2 below for a specific
illustration of Theorem 5.1. For a numerical illustration of the estimand and
estimator in more general setups, see Section 6.5.

######  Example 5.2 (Misspecified $m$)

Suppose $T=4,m=2,p=1,\mathbb{T}=\\{1,3\\}$. Then the determining randomization
points are
$f_{\mathbb{T}}(1)=1,f_{\mathbb{T}}(2)=1,f_{\mathbb{T}}(3)=3,f_{\mathbb{T}}(4)=3$,
and

$\displaystyle\mathbb{E}\left[Y_{2}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{1:2}=(1,1)\\}}}{\Pr(\bm{W}_{1:2}=(1,1))}-Y_{2}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{1:2}=(0,0)\\}}}{{\Pr(\bm{W}_{1:2}=(0,0))}}\right]$
$\displaystyle=Y_{2}(1,1)-Y_{2}(0,0)$
$\displaystyle\mathbb{E}\left[Y_{3}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{2:3}=(1,1)\\}}}{\Pr(\bm{W}_{2:3}=(1,1))}-Y_{3}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{2:3}=(0,0)\\}}}{{\Pr(\bm{W}_{2:3}=(0,0))}}\right]$
$\displaystyle=Y_{3}(1,1,1)-Y_{3}(0,0,0)$
$\displaystyle\mathbb{E}\left[Y_{4}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{3:4}=(1,1)\\}}}{\Pr(\bm{W}_{3:4}=(1,1))}-Y_{4}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{3:4}=(0,0)\\}}}{{\Pr(\bm{W}_{3:4}=(0,0))}}\right]$
$\displaystyle=\frac{1}{2}\left[Y_{4}(1,1,1)+Y_{4}(0,1,1)-Y_{4}(0,0,0)-Y_{4}(1,0,0)\right]$

Note that this is the $2$-misspecified lag-$1$ causal effect.

###  5.3 Inference

The exact inference procedure as in Section 4.1 remains valid when $m$ is
misspecified. For the asymptotic inference procedure as in Section 4.2,
Theorem 4.3 still holds when $m$ is misspecified, as we state in Corollary
5.3. The proof is deferred to Section 14.2 in the Appendix.

######  Corollary 5.3 (Asymptotic Normality when $m$ is Misspecified)

For any $n\geq 4\in\mathbb{N}$, define an $n$-replica experiment such that
there are $T=np$ time periods. Take the optimal design as in Theorem 3.7 whose
randomization points are at $\mathbb{T}^{*}=\\{1,2p+1,3p+1,...,(n-2)p+1\\}$.
We have the following two observations.

  1. i

When $m<p$, under Assumptions 1–1, the variance of the Horvitz-Thompson
estimator, $\mathsf{Var}(\hat{\tau}_{p})$, is explicitly given by (11).

  2. ii

Furthermore, no matter if $m<p$ or $m>p$, under Assumptions 1–1 and assume
$\mathsf{Var}(\hat{\tau}_{p})\geq\Omega(n^{-1})$, the limiting distribution of
the Horvitz-Thompson estimator in the $n$-replica experiment has an asymptotic
normal distribution. That is, as $n\to+\infty$,

$\displaystyle\frac{\hat{\tau}_{p}-\tau_{p}}{\sqrt{\mathsf{Var}(\hat{\tau}_{p})}}\xrightarrow[]{D}\mathcal{N}(0,1).$

Corollary 5.3, together with Theorem 4.3, is the key to identify $m$, the
order of the carryover effect. In Section 7.1, we will provide methods to
identify $m$.

###  5.4 Robustness to Misspecifications

So far we have discussed estimation and inference when the order of carryover
effects are misspecified. We conclude with a short discussion on the
robustness of our method.

First, the optimal design between $m=0$ and $m=1$ are almost the same. This
suggests that when there is very little carryover effect, our proposed optimal
design is robust. Second, as we will see in Section 6, when the order of
carryover effect is slightly overestimated the variance is only a little
larger. This adds an extra layer of robustness that a slight misspecification
is often acceptable.

##  6 Simulation Study and Empirical Illustration

There are 5 goals for this simulation study. First, to illustrate how to
conduct a switchback experiment for various outcome models. Second, to show
that our proposed optimal design has the smallest risk, compared with two
benchmarks. There are two dimensions for our comparison: the worst-case risk
and the risk under a specific outcome model. Third, to verify the asymptotic
normal distribution under a non-asymptotic setup, and to study the quality of
the upper bound proposed in Corollary 4.2. Fourth, to understand the rejection
rate and its dependence on the length of time horizon. Fifth, under randomly
generated cases, to study the performance of the optimal design under a
misspecified $m$, and to compare the difference of the two inference methods
proposed in Section 4.

###  6.1 Outcome Models

The potential outcome framework is flexible. As we will see below, it is easy
to use the potential outcome framework to describe many complex relationships
between assignments and outcomes.

We start with a simple model which originates from Oman and Seiden (1988):

$\displaystyle Y_{t}(\bm{w}_{1:t})=\mu+\alpha_{t}+\delta w_{t}+\gamma
w_{t-1}+\epsilon_{t}$ (14)

where $\mu$ is a fixed effect; $\alpha_{t}$ is a fixed effect associated to
period $t$; $\delta w_{t}$ is the contemporaneous effect, and $\gamma w_{t-1}$
is the carryover effect from period $t-1$; $\epsilon_{t}$ is the random noise
in period $t$. Such a model as well as a few very similar ones are widely used
in the literature (Hedayat et al. 1978, Jones and Kenward 2014).

A more general variant from the above model is to consider carryover effects
of any arbitrary order:

$\displaystyle
Y_{t}(\bm{w}_{1:t})=\mu+\alpha_{t}+\delta^{(1)}w_{t}+\delta^{(2)}w_{t-1}+...+\delta^{(t)}w_{1}+\epsilon_{t}$
(15)

where $\delta^{(1)},\delta^{(2)},...,\delta^{(t)}$ are non-stochastic
coefficients. The dotted terms are carryover effects of higher orders. And all
the other parameters are as defined in (14). We will run simulations based on
this more general model, which enables us to test the performance of our
proposed optimal design under a misspecified $m$.

The autoregressive model (Arellano 2003) is even more general:
$Y_{1}(w_{1})=\delta_{1,1}w_{1}+\epsilon_{1}$ and $\forall t>1$

$Y_{t}(\bm{w}_{1:t})=\phi_{t,t-1}Y_{t-1}(\bm{w}_{1:t-1})+\phi_{t,t-2}Y_{t-2}(\bm{w}_{1:t-2})+...+\phi_{t,1}Y_{1}(w_{1})+\\\
\delta_{t,t}w_{t}+\delta_{t,t-1}w_{t-1}+...+\delta_{t,1}w_{1}+\epsilon_{t}$
(16)

where $\phi_{t,\tilde{t}}$ and $\delta_{t,\tilde{t}}$ are non-stochastic
coefficients; the dotted terms are carryover effects of higher orders;
$\epsilon_{t}$ is the random noise in period $t$. We can iteratively replace
$Y_{t}(w_{t})$ using a linear combination of $w_{t},w_{t-1},...,w_{1}$. So the
autoregressive model in (16) can be written in a similar form of (15). The
only difference is that the coefficients are different and dependent on $t$.

For all these models, we first decide what is the order of carryover effects,
namely $m$. Then we use Theorem 3.7 to find the optimal design of experiment.
Finally, we use the exact randomization test in Section 4 to conduct
hypothesis test.

###  6.2 Comparison of the Risk Functions

####  6.2.1 Simulation setup.

We consider two setups. The first setup is for the worst-case risk. We
consider $T=120,p=m=2$ where $m$ is correctly identified, and
$Y_{t}(\bm{1}_{3})=Y_{t}(\bm{0}_{3})=10$. We compare three different designs
of switchback experiments. The first one is our proposed optimal design as in
Theorem 3.7, such that $\mathbb{T}^{*}=\\{1,5,7,...,117\\}$. The second one is
the most common and naive switchback experiment, which independently assign
treatment/control in every period with half-half probability. It is
parameterized by $\mathbb{T}^{\mathsf{H1}}=\\{1,2,3,...,120\\}$. The third one
is the “intuitive” experiment discussed in Example 3.8, which divides the time
horizon into several epochs each with length $m+1=3$. It is parameterized by
$\mathbb{T}^{\mathsf{H2}}=\\{1,4,7,...,118\\}$.

Second, we run simulations based on the outcome model as in (15). We consider
$T=120,p=m=2$ where $m$ is correctly identified. For the outcome model, we
consider $\mu=0$, $\alpha_{t}=\log{(t)}$, and $\epsilon_{t}\sim N(0,1)$ are
i.i.d. standard normal distributions. For any $t>3$, let $\delta^{(t)}=0$. We
will vary the values of $\delta^{(1)},\delta^{(2)},\delta^{(3)}\in\\{1,2\\}$
and conduct experiments under $2^{3}=8$ different scenarios. Again we compare
the same three different designs of switchback experiments.
$\mathbb{T}^{*}=\\{1,5,7,...,117\\},\mathbb{T}^{\mathsf{H1}}=\\{1,2,3,...,120\\},\mathbb{T}^{\mathsf{H2}}=\\{1,4,7,...,118\\}$.

We simulate one assignment path at a time, and conduct experiment following
this assignment path. Since the outcome model is prescribed, we can calculate
both the causal estimand and and the observed outcomes (along the simulated
assignment path). Then we calculate the Horvitz-Thompson estimator based on
the simulated assignment path and the simulated observed outcomes. With both
the estimand and estimator, we can calculate the loss function. By repeating
the above procedure enough (in this simulation, $100000$) times we
approximately have the risk function.

####  6.2.2 Simulation results.

We calculate the worst-case risk functions via simulation. Notice that even
though we could calculate the worst-case risk function explicitly via Theorem
3.6, we still run the simulation to confirm this result. See Table 6.2.2 for
results.

The causal effect is $\tau_{2}=0$ because
$Y_{t}(\bm{1}_{3})=Y_{t}(\bm{0}_{3})=10$. The simulated estimator is
$\mathbb{E}[\hat{\tau}^{*}_{2}]=-0.0291$ for our proposed optimal design, and
$\mathbb{E}[\hat{\tau}^{\mathsf{H1}}_{2}]=0.0104$ and
$\mathbb{E}[\hat{\tau}^{\mathsf{H2}}_{2}]=-0.0478$ for the two benchmarks,
respectively. It is worth noting that such estimation errors are quite small
for all three designs, because the reported numbers are for total effects, not
average effects. If we further divide them by $T-p$ then the errors are very
clode to zero. The risk function is $r(\eta_{\mathbb{T}^{*}})=26.78$ for our
proposed optimal design, and $r(\eta_{\mathbb{T}^{\mathsf{H1}}})=33.67$ and
$r(\eta_{\mathbb{T}^{\mathsf{H1}}})=27.85$ for the two benchmarks,
respectively. Such simulation results suggest that our proposed optimal design
have the smallest risk, under the worst case outcome model.

Simulation results for the worst-case risk function.  $\tau_{2}$
$\mathbb{E}[\hat{\tau}^{*}_{2}]$ $\mathbb{E}[\hat{\tau}^{\mathsf{H1}}_{2}]$
$\mathbb{E}[\hat{\tau}^{\mathsf{H2}}_{2}]$ $r(\eta_{\mathbb{T}^{*}})$
$r(\eta_{\mathbb{T}^{\mathsf{H1}}})$ $r(\eta_{\mathbb{T}^{\mathsf{H2}}})$ $0$
$0.0250$ $0.0200$ $0.0059$ $26.78$ $33.67$ $27.85$ The optimal design
$\mathbb{T}^{*}$ as suggested in Theorem 3.7 yields the smallest risk.

We also calculate the risk functions based on the outcome model in (15). See
Table 6.2.2. As we vary the values of $\delta^{(1)}$, $\delta^{(2)}$ and
$\delta^{(3)}$, the total lag-$2$ causal effect is being changed. All three
estimators are able to reflect the change as the estimand changes. The risk
function can be simulated and we see that the risk function associated with
the first benchmark $\mathbb{T}^{\mathsf{H1}}$ is $28\%\sim 32\%$ larger than
the optimal design; and the second benchmark $\mathbb{T}^{\mathsf{H2}}$ is
$1\%\sim 2\%$ larger. Such simulation results suggest again that our proposed
optimal design have the smallest risk.

Simulation results for the risk function based on the outcome model in (15).
$\delta^{(1)}$ $\delta^{(2)}$ $\delta^{(3)}$ $\tau_{2}$
$\mathbb{E}[\hat{\tau}^{*}_{2}]$ $\mathbb{E}[\hat{\tau}^{\mathsf{H1}}_{2}]$
$\mathbb{E}[\hat{\tau}^{\mathsf{H2}}_{2}]$ $r(\eta_{\mathbb{T}^{*}})$
$r(\eta_{\mathbb{T}^{\mathsf{H1}}})$ $r(\eta_{\mathbb{T}^{\mathsf{H2}}})$ 1 1
1 3 3.016 3.012 3.002 7.96 10.22 8.11 1 1 2 4 4.018 4.013 4.002 9.57 12.39
9.74 1 2 1 4 4.018 4.013 4.002 9.57 12.39 9.74 2 1 1 4 4.018 4.013 4.002 9.57
12.39 9.74 1 2 2 5 5.020 5.015 5.003 11.34 14.81 11.52 2 1 2 5 5.020 5.015
5.003 11.34 14.81 11.52 2 2 1 5 5.020 5.015 5.003 11.34 14.81 11.52 2 2 2 6
6.022 6.016 6.003 13.28 17.48 13.47 For each row, the random seed that
generates the simulation setup is fixed. The optimal design $\mathbb{T}^{*}$
as suggested in Theorem 3.7, though solved from a minimax program, still
yields the smallest risk for the outcome model in (15).

Moreover, based on the fact that $r(\eta_{\mathbb{T}^{\mathsf{H2}}})$ is
rather close to $r(\eta_{\mathbb{T}^{*}})$ and much smaller than
$r(\eta_{\mathbb{T}^{\mathsf{H1}}})$, we suggest that a slight overestimate of
$m$ is more desirable than an underestimate.

As the magnitude of treatment effects increase, the associated risk functions
also increase. The relative difference between risk functions of
$r(\eta_{\mathbb{T}^{\mathsf{H1}}})$ and $r(\eta_{\mathbb{T}^{*}})$ increases,
while the relative difference between $r(\eta_{\mathbb{T}^{\mathsf{H1}}})$ and
$r(\eta_{\mathbb{T}^{*}})$ decreases. This coincides with the intuitions
discussed in Section 3.

###  6.3 Asymptotic Normality

####  6.3.1 Simulation setup.

We run simulations based on the outcome model as in (15). We consider
$T=120,m=2$. We will consider three cases: (i) $m$ is correctly specified so
$p=2$; (ii) $m$ is overestimated to be $3$ so $p=3$, and we estimate lag-$3$
causal estimand as in (1); (iii) $m$ is underestimated to be $1$ so $p=1$, and
we pretend as if we estimated the lag-$1$ causal estimand. However, the
lag-$1$ causal estimand is not well defined – and we instead estimate the
$2$-misspecified lag-$1$ causal estimand as in (13).

For the outcome model, we consider $\mu=0$, $\alpha_{t}=\log{(t)}$, and
$\epsilon_{t}\sim N(0,1)$ are i.i.d. standard normal distributions. For any
$t>3$, let $\delta^{(t)}=0$. For simplicity, let
$\delta^{(1)}=\delta^{(2)}=\delta^{(3)}=\delta$. We vary
$\delta\in\\{1,2,3\\}$ and conduct experiments under $3$ different scenarios.

We simulate one assignment path at a time, and conduct experiment following
this assignment path. Since the outcome model is prescribed, we calculate the
observed outcomes based on the simulated assignment path. Then we calculate
the Horvitz-Thompson estimator, and two conservative estimators of the
randomization variance (Corollary 4.2), both based on the simulated assignment
path and the simulated observed outcomes. On the other hand, the lag-$p$
causal estimand is easy to calculate once the outcome model is prescribed. Yet
the $m$-misspecified lag-$p$ causal estimand has to be calculated in
conjunction with the simulated assignment path. By repeating the above
procedure enough (in this simulation, 100000) times we obtain a distribution
of the estimator, and we calculate the mean value of the estimator (and the
$m$-misspecified lag-$p$ causal estimand).

####  6.3.2 Simulation results.

Figure 4 shows approximate normality of the randomization distribution, under
all 9 cases. There are three specifications of $m$: correctly specified when
$p=2$; overestimated when $p=3$; underestimated when $p=1$. There are three
specifications of $\delta=1,2,3$. In all 9 cases, the distributions are all
centered around the red vertical lines, which are the mean values of the
randomization distributions. Specifically, Figures (a) – (c) validates Theorem
4.3, and Figures (d) – (i) validates Corollary 5.3.

(a) m correctly specified, $\delta=1$.

(b) m correctly specified, $\delta=2$.

(c) m correctly specified, $\delta=3$.

(d) m overestimated, $\delta=1$.

(e) m overestimated, $\delta=2$.

(f) m overestimated, $\delta=3$.

(g) m underestimated, $\delta=1$.

(h) m underestimated, $\delta=2$.

(i) m underestimated, $\delta=3$.

Figure 4: Approximate normality of the randomization distributions in all 9
cases. The red vertical lines are the expected values of the randomization
distributions.

For all the above cases, see Table 6.3.2 for the expected values and the
variances of the randomization distributions, as well two conservative
estimators of the randomization variances. Note that the three cases all have
the same underlying outcome model. It is the different knowledge of $m$ that
leads to three different designs.

Simulation results for the randomization distribution.  $\tau_{p}$
$\tau^{[m]}_{p}$ $\mathbb{E}[\hat{\tau}_{p}]$ $\mathsf{Var}(\hat{\tau}_{p})$
$\mathbb{E}[\hat{\sigma}^{2}_{\mathsf{U1}}]$
$\mathbb{E}[\hat{\sigma}^{2}_{\mathsf{U2}}]$ correct $m$ $\delta=1$ 3 $-$
3.016 7.96 8.50 8.48 $\delta=2$ 6 $-$ 6.022 13.28 15.24 15.16 $\delta=3$ 9 $-$
9.028 20.10 24.40 24.25 overestimated $m$ $\delta=1$ 3 $-$ 3.006 11.92 12.77
12.67 $\delta=2$ 6 $-$ 6.009 19.89 22.91 22.70 $\delta=3$ 9 $-$ 9.012 30.10
36.69 36.32 underestimated $m$ $\delta=1$ $-$ 2 2.016 4.00 4.13 4.13
$\delta=2$ $-$ 4 4.026 6.69 7.09 7.06 $\delta=3$ $-$ 6 6.037 10.14 11.01 10.92
The randomization distributions in all 9 cases are unbiased. The conservative
estimation of the variance upper bounds from Corollary 4.2 are close to the
true variance.

From Table 6.3.2, we make the following two observations. (i) Unbiasedness of
the Horvitz-Thompson estimator. When $m$ is correctly specified,
$\mathbb{R}[\hat{\tau}_{p}]$ is very close to $\tau_{p}$, verifying the
unbiasedness of the estimator. When $m$ is overestimated, the estimand remains
unchanged, and the estimator remains unbiased. But the variance of the
estimator is larger. When $m$ is underestimated, the estimand is the
$m$-misspecified estimand, and the estimator is unbiased for this
$m$-misspecified estimand.

(ii) Quality of Corollary 4.2. As we increase $\delta$, the variance of the
randomization distribution also increases. The two conservative estimators of
the randomization variance are very close to the true variance, which suggests
that Corollary 4.2 approximates the true variance quite well. Even though the
second upper bound $\mathsf{Var}^{\mathsf{U2}}(\hat{\tau}_{p})$ is larger than
the first one $\mathsf{Var}^{\mathsf{U1}}(\hat{\tau}_{p})$, its estimator
$\hat{\sigma}^{2}_{\mathsf{U2}}$ turns out to be smaller than
$\hat{\sigma}^{2}_{\mathsf{U1}}$ in most cases.

###  6.4 Rejection Rates

####  6.4.1 Simulation setup.

We run simulations based on the outcome model as in (15). We very
$T\in\\{60,120,180,...,600\\}$. We consider $p=m=2$ where $m$ is correctly
specified. Similar to Section 6.3, we consider the same parameterization and
conduct experiments under $3$ different scenarios $\delta\in\\{1,2,3\\}$.

We simulate one assignment path at a time, and conduct experiment following
this assignment path. We first calculate the observed outcomes and the
Horvitz-Thompson estimator. Then we conduct the two inference methods as
proposed in Section 4 (for the asymptotic inference method, we plug in the
second upper bound $\hat{\sigma}^{2}_{\mathsf{U2}}$) and obtain two estimated
$p$-values. We reject the corresponding null hypothesis when the $p$-value is
smaller than $0.1$. By repeating the above procedure enough (in this
simulation, 1000) times we obtain the frequency of a null hypothesis being
rejected, which we refer to as the rejection rate.

####  6.4.2 Simulation Results.

We calculate the rejection rates via simulation, and plot Figure 5. In all the
simulations, $\delta\neq 0,\tau_{p}\neq 0$, so ideally we would wish to reject
the null hypothesis (whether if it is (9) or (10)).

Figure 5: Rejection rates and their dependence on $T/m$. The blue dots are
rejection rates under exact inference; the red dots are under asymptotic
inference. Left: $\delta=1$; Middle: $\delta=2$; Right: $\delta=3$

From Figure 5 we make the following three observations. (i) Dependence on
$T/m$. The rejection rates increase as the length of the horizon increases –
more specifically, as $T/m$ the total number of epochs increases. In practice,
when firms have choose the length of $T$ and decide how much experimental
budgets to allocate, they can refer to Figure 5 to choose $T$ properly. Also
see discussion in Section 7.2.

(ii) Between two inference methods. In all three cases, the rejection rate
from testing a sharp null hypothesis (9) is slightly higher than that from
testing the Neyman’s null (10). This coincides with our intuition that a sharp
null is more likely to be rejected. We discuss this in Section 6.5.2 together
with the associated $p$-values.

(iii) Dependence on the signal-to-noise ratio. The rejection rates all
increase as $\delta$ increases from 1 to 3 (while holding the noise from the
model fixed). This suggests that when the treatment effect is relatively
larger, we do not require a long experimental horizon to achieve a desired
rejection rate.

###  6.5 Estimation under a Misspecified $m$

####  6.5.1 Simulation setup.

We run simulations based on the outcome model as in (15). We consider
$T=120,m=2$. We consider three cases: (i) $m$ correctly specified $p=2$; (ii)
$m$ is overestimated $p=3$, and we estimate the lag-$3$ causal estimand as in
(1); (iii) $m$ is underestimated $p=1$, and we pretend as if we estimated the
lag-$1$ causal estimand. However, the lag-$1$ causal estimand is not well
defined. Instead, we estimate the $2$-misspecified lag-$1$ causal estimand as
in (13).

For the outcome model, we consider the same parameterization as in Section
6.3, and conduct experiments under $3$ different scenarios
$\delta\in\\{1,2,3\\}$.

We only simulate one assignment path. Since the outcome model is prescribed,
we calculate the observed outcomes. There is only one time series of such
observed outcomes. We calculate the Horvitz-Thompson estimator based on the
simulated assignment path and the simulated observed outcomes. We calculate
the lag-$p$ causal estimand directly, and also the $m$-misspecified lag-$p$
causal estimand in conjunction with the simulated assignment path. Finally, we
perform the two inference methods from Section 4, and report their associated
estimated $p$-values. The conservative sampling variance we take is
$\hat{\sigma}^{2}_{\mathsf{U2}}$. We choose $I=100000$ to be the number of
samples drawn in the exact inference method as shown in Algorithm 1.

####  6.5.2 Simulation results.

Notice this is only one experiment under one simulated experimental setup from
one simulated assignment path. So the estimators $\hat{\tau}_{p}$ we derive
are different from $\tau_{p}$. But they are still roughly following the true
causal effects which they estimate. See Table 6.5.2.

Simulation results for correctly specified $m$, overestimated $m$, and
underestimated $m$.  $\tau_{p}$ $\tau^{[m]}_{p}$ $\hat{\tau}_{p}$
$\hat{\sigma}^{2}_{\mathsf{U2}}$ $\hat{p}_{\mathsf{F}}$ $\hat{p}_{\mathsf{N}}$
correct $m$ $\delta=1$ 3 $-$ 1.35 8.81 0.626 0.648 $\delta=2$ 6 $-$ 4.30 15.16
0.231 0.269 $\delta=3$ 9 $-$ 7.25 23.88 0.101 0.138 overestimated $m$
$\delta=1$ 3 $-$ 1.77 14.26 0.606 0.639 $\delta=2$ 6 $-$ 5.00 24.69 0.262
0.314 $\delta=3$ 9 $-$ 8.23 39.00 0.136 0.188 underestimated $m$ $\delta=1$
$-$ 2 -1.03 3.87 0.590 0.599 $\delta=2$ $-$ 4 0.41 6.28 0.866 0.870 $\delta=3$
$-$ 6 1.86 9.47 0.530 0.547 The simulation setup for the three $\delta=1$
cases is the same; so are the $\delta=2$ cases and $\delta=3$ cases. The
estimated $p$-values derived from the exact inference is slightly smaller than
the $p$-values derived from the asymptotic inference.

From Table 6.5.2 we see that both our estimator and the estimated variance are
well defined in all the cases when $m$ is correctly specified, is
overestimated, and is underestimated. In each case, as $delta$ increases from
1 to 3, the associated $p$-values exhibit decreasing trends, suggesting a
stronger rejection rate against the null hypothesis. Moreover, the $p$-values
suggested by the exact inference is always slightly smaller than the
$p$-values suggested by the asymptotic inference. This coincides with our
intuition that: (i) the exact inference method possesses a stronger null
hypothesis (9) which implies the null hypothesis of (10); (ii) in the
asymptotic inference we replaced the true randomization variance by its
conservative upper bound, which further leads to a larger $p$-value.

##  7 Practical Implications

We recap what would a manager do to practically run a switchback experiment.
First, the granularity and the length of horizon are sometimes given to a
manager; when the manager has more flexibility to choose the granularity and
the length of horizon, see discussions in Section 7.2. Second, the manager
either consults domain knowledge to decide what is the order of carryover
effect, or when such knowledge is not perfect, run a first phase experiment to
identify such an order. See discussions in Section 7.1. Third, the manager
decides on a collection of randomization points, and draws one sample from the
randomization distribution to be the assignment path. We recommend the optimal
design as we discussed in Section 3. Finally, the manager collects data from
the experiment, and draws causal conclusions using the methods in Section 4.

###  7.1 Identifying the Order of Carryover Effect

We borrow Theorem 4.3 and Corollary 5.3 to define a sub-routine, which,
combined with searching method, identifies the order of carryover effect.

Suppose we have access to two i.i.d. experimental units. Such two experimental
units could be two identical units. They can also be two time spans on one
single experimental unit, such that the two spans are well separated and the
carryover effect from one does not affect the outcomes of the other.

On the first experimental unit, we design an optimal experiment under
$p=p_{1}$; while on the second unit, $p=p_{2}$. Without loss of generality let
$p_{1}<p_{2}$. We observe the outcomes, collect the data, and find the
following statistics from the two experiments. In the first one, calculate
$\hat{\tau}_{p_{1}}$, the sampling average, and $\hat{\sigma}^{2}_{p_{1}}$,
the conservative sampling variance as suggested by Corollary 4.2. In the
second one, calculate $\hat{\tau}_{p_{2}}$ and $\hat{\sigma}^{2}_{p_{2}}$.

Define a sub-routine that tests the following null hypothesis:

$\displaystyle H_{0}:\ m\leq p_{1}$ (17)

Under the null hypothesis (17), $\tau_{p_{1}}=\tau_{p_{2}}$. Furthermore,
given that the two experimental units are independent, the difference between
the two sample means should be a normal distribution centered around zero,
i.e.,
$(\hat{\tau}_{p_{1}}-\hat{\tau}_{p_{2}})/\sqrt{\mathsf{Var}(\tau_{p_{1}})+\mathsf{Var}(\tau_{p_{2}})}\xrightarrow[]{D}\mathcal{N}(0,1)$.
To test the null hypothesis (17), define the test statistic to be
$z=\left|\hat{\tau}_{p_{1}}-\hat{\tau}_{p_{2}}\right|/\sqrt{\hat{\sigma}^{2}_{p_{1}}+\hat{\sigma}^{2}_{p_{2}}}$.
The estimated $p$-value is given by $\hat{p}=2-2\Phi(z)$, where $\Phi$ is the
CDF of a standard normal distribution.

Such a sub-routine enables us to test the null hypothesis (17). We can combine
such a sub-routine with any searching method to identify $m$.

To take an example, suppose we are running an experiment whose setup is in
Section 6.5, and that $\delta=3$. Suppose we have narrowed down the range of
the order of carryover effect to be $m\leq 3$. In the first round, we consult
the sub-routine to test a null hypothesis $m\leq 2$. Then we would observe row
3 and 6 from Table 6.5.2, with
$\hat{\tau}_{2}=7.25,\hat{\sigma}^{2}_{2}=23.88;\hat{\tau}_{3}=8.23,\hat{\sigma}^{2}_{3}=39.00$.
So the estimated $p$-value for the null hypothesis $m\leq 2$ is estimated to
be $\hat{p}=0.902$, which is quite big to reject the null hypothesis. In the
second round, we consult the sub-routine to test a null hypothesis $m\leq 1$.
Then we would observe row 3 and 9 from Table 6.5.2, with
$\hat{\tau}_{1}=1.86,\hat{\sigma}^{2}_{3}=9.47;\hat{\tau}_{2}=7.25,\hat{\sigma}^{2}_{2}=23.88$.
The estimated $p$-value for the null hypothesis $m\leq 1$ is estimated to be
$\hat{p}=0.350$. This is still rather big, yet a significant difference from
the previous $0.902$. In practice, we suggest to increase the length of the
horizon to a degree such that $T/p\approx 100$.

###  7.2 Choosing the Granularity and the Length of Horizon

The selection of $T$ depends on the following two components: first, the
granularity of one single time period; and second, the number of total epochs
$T/p$ included in the time horizon.

The granularity of each time period refers to how long in the physical world a
single time period corresponds to. As long as each time period is granular
enough such that its length is smaller than the length of the carryover
effect, and that the length of the carryover effect is some multiple times of
the length of one time unit, then the selection of granularity makes no
difference to the optimal design and analysis of switchback experiments. See
Example 7.1.

######  Example 7.1 (Two Granularity Levels)

In the ride-sharing application, suppose the firms have two options to either
treat one single time period as 15 minutes, or as 30 minutes. See Figure 6.
Each smallest time period stands for 15 minutes, and the carryover effect
lasts for 1 hour. In the time granularity as shown in blue, each time period
lasts for 15 minutes, and the carryover effect lasts for $m=4$ time periods.
In the time granularity as shown in red, each time period lasts for 30
minutes, and the carryover effect lasts for $m=2$ time periods.

Figure 6: Illustrator of two granularity levels. Blue: each period is 15
minutes; Red: each period is 30 minutes.

From Theorem 3.7, the optimal design exhibits an optimal structure that
randomizes once every $m$ time periods (except for the first and last epoch,
which lasts for $2m$ time periods each). In both cases, the optimal design
would randomize once every 1 hour. Furthermore, from Theorem 2.5 we know that
under both cases the mean value of the Horvitz-Thompson estimator remains
unchanged. From Theorem 4.1, the variance consists of terms like
$\bar{Y}_{k}(\bm{1}_{m+1})=\sum_{t=(k+1)m+1}^{(k+2)m}Y_{t}(\bm{1}_{m+1})$,
which are the sum across all the outcomes within 1 hour. So under both cases
the variance of the estimator remains unchanged.

On the other hand, when the length of each time period is longer than the
length of the carryover effect, this will cause unnecessary overestimation of
the length of the carryover effect. In an extreme case, the length of
carryover effect is 1 minute while each period is selected to be 1 hour. Then
the minimum order of carryover effect would be 1, which overestimates the
length of the carryover effect to be 1 hour. So we suggest that the length of
each time period should be smaller than the length of the carryover effect.

Second, after we have decided about the granularity of each time period, we
can consult the procedures from Section 7.1 to identify $m$. The next to
choose is how long the experiment should last, $n=T/m$. We choose $n$ by
referring to the rejection rate curve as shown in Section 6.4. We first
prescribe which inference method to use (exact inference or asymptotic
inference). Then we borrow our domain knowledge to get a sense of the signal-
to-noise ratio. Finally, we choose any desired rejection rate and find out the
length of horizon required.

##  8 Concluding Remarks, Limitations and Future Work

We studied the design and analysis of switchback experiments. We formulated
and solved a minimax problem for the design of optimal switchback experiments.
We then analyzed our proposed optimal design and proposed two inferential
methods. In particular, we showed asymptotic normality of the randomization
distribution. We discussed cases when the order of carryover effect, $m$, is
misspecified, and detailed a method to identify the order of carryover effect.
We gave empirical suggestions that a slight overestimate of $m$ is acceptable
and better than an underestimate.

We point out two limitations of our paper. First, when $m$ the order of
carryover effect is as large as comparable to $T$ the length of horizon, our
method, though still unbiased in theory, incurs a huge variance that typically
prohibits the experimental designer to make any inference. This is due to the
fact that our method is general and requires the minimum amount of modeling
assumptions. When the outcome model has some structures, for example the
equilibrium effects as in Wager and Xu (2019), utilizing such structures will
lead to difference designs. Second, our method does not take advantage of
covariate information to further reduce the randomization variance. This could
lead to future work.

Finally, we do encourage empirical researchers who apply our method to use
domain knowledge to narrow down $m$ first, before using the procedure in
Section 7.1 to identify $m$. This is because, empirically, each sub-routine to
identify (17) needs to consume experimental resources at the scale of
$T/p\approx 100$ to well distinguish two candidate values, which could be
luxurious when the resource is scarce.

## References

  * Abadie et al. (2020) Abadie A, Athey S, Imbens GW, Wooldridge JM (2020) Sampling-based versus design-based uncertainty in regression analysis. _Econometrica_ 88(1):265–296.
  * Ailawadi and Neslin (1998) Ailawadi KL, Neslin SA (1998) The effect of promotion on consumption: Buying more and consuming it faster. _Journal of Marketing Research_ 35(3):390–398.
  * Arellano (2003) Arellano M (2003) _Panel data econometrics_ (Oxford university press).
  * Athey et al. (2018) Athey S, Eckles D, Imbens GW (2018) Exact p-values for network interference. _Journal of the American Statistical Association_ 113(521):230–240.
  * Athey and Imbens (2018) Athey S, Imbens GW (2018) Design-based analysis in difference-in-differences settings with staggered adoption. Technical report, National Bureau of Economic Research.
  * Azevedo et al. (2019) Azevedo EM, Alex D, Montiel Olea J, Rao JM, Weyl EG (2019) A/b testing with fat tails. _Available at SSRN 3171224_ .
  * Bai (2019) Bai Y (2019) Optimality of matched-pair designs in randomized control trials. _Available at SSRN 3483834_ .
  * Basse et al. (2019) Basse G, Ding Y, Toulis P (2019) Minimax crossover designs. _arXiv preprint arXiv:1908.03531_ .
  * Bell et al. (1999) Bell DR, Chiang J, Padmanabhan V (1999) The decomposition of promotional response: An empirical generalization. _Marketing Science_ 18(4):504–526.
  * Berger (2013) Berger JO (2013) _Statistical decision theory and Bayesian analysis_ (Springer Science & Business Media).
  * Bickel and Doksum (2015) Bickel PJ, Doksum KA (2015) _Mathematical statistics: basic ideas and selected topics, volume I_ , volume 117 (CRC Press).
  * Bojinov et al. (2020a) Bojinov I, Rambachan A, Shephard N (2020a) Panel experiments and dynamic causal effects: A finite population perspective. _arXiv preprint arXiv:2003.09915_ .
  * Bojinov et al. (2020b) Bojinov I, Saint-Jacques G, Tingley M (2020b) Avoid the pitfalls of a/b testing make sure your experiments recognize customers’ varying needs. _Harvard Business Review_ 98(2):48–53.
  * Bojinov and Shephard (2019) Bojinov I, Shephard N (2019) Time series experiments and causal estimands: exact randomization tests and trading. _Journal of the American Statistical Association_ 114(528):1665–1682.
  * Boruvka et al. (2018) Boruvka A, Almirall D, Witkiewitz K, Murphy SA (2018) Assessing time-varying causal effect moderation in mobile health. _Journal of the American Statistical Association_ 113(523):1112–1121.
  * Caro and Gallien (2012) Caro F, Gallien J (2012) Clearance pricing optimization for a fast-fashion retailer. _Operations Research_ 60(6):1404–1422.
  * Chamberlain (1982) Chamberlain G (1982) Multivariate regression models for panel data. _Journal of econometrics_ 18(1):5–46.
  * Deshpande et al. (2018) Deshpande Y, Mackey L, Syrgkanis V, Taddy M (2018) Accurate inference for adaptive linear models. _International Conference on Machine Learning_ , 1194–1203 (PMLR).
  * Eckles et al. (2016) Eckles D, Karrer B, Ugander J (2016) Design and analysis of experiments in networks: Reducing bias from interference. _Journal of Causal Inference_ 5(1).
  * Farronato et al. (2018) Farronato C, MacCormack A, Mehta S (2018) Innovation at uber: The launch of express pool. _Harvard Business School Case_ 620(062).
  * Ferreira et al. (2016) Ferreira KJ, Lee BHA, Simchi-Levi D (2016) Analytics for an online retailer: Demand forecasting and price optimization. _Manufacturing & Service Operations Management_ 18(1):69–88.
  * Garg and Nazerzadeh (2019) Garg N, Nazerzadeh H (2019) Driver surge pricing. _arXiv preprint arXiv:1905.07544_ .
  * Glynn et al. (2020) Glynn P, Johari R, Rasouli M (2020) Adaptive experimental design with temporal interference: A maximum likelihood approach. _arXiv preprint arXiv:2006.05591_ .
  * Hadad et al. (2019) Hadad V, Hirshberg DA, Zhan R, Wager S, Athey S (2019) Confidence intervals for policy evaluation in adaptive experiments. _arXiv preprint arXiv:1911.02768_ .
  * Hedayat et al. (1978) Hedayat A, Afsarinejad K, et al. (1978) Repeated measurements designs, ii. _The Annals of Statistics_ 6(3):619–628.
  * Hoeffding and Robbins (1948) Hoeffding W, Robbins H (1948) The central limit theorem for dependent random variables. _Duke Mathematical Journal_ 15(3):773–780.
  * Imai and Kim (2019) Imai K, Kim IS (2019) When Should We Use Unit Fixed Effects Regression Models for Causal Inference with Longitudinal Data? _American Journal of Political Science_ 63(2):467–490, URL http://dx.doi.org/10.1111/ajps.12417.
  * Imbens and Rubin (2015) Imbens GW, Rubin DB (2015) _Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction_ (Cambridge University Press), URL http://dx.doi.org/10.1017/CBO9781139025751.
  * Johari et al. (2020) Johari R, Li H, Weintraub G (2020) Experimental design in two-sided platforms: An analysis of bias. _arXiv preprint arXiv:2002.05670_ .
  * Jones and Kenward (2014) Jones B, Kenward MG (2014) _Design and analysis of cross-over trials_ (CRC press).
  * Kastelman and Ramesh (2018) Kastelman D, Ramesh R (2018) Switchback tests and randomized experimentation under network effects at doordash. _URL: https://medium.com/@DoorDash/switchback-tests-and-randomized-experimentation-under-network-effects-at-doordash-f1d938ab7c2a_ .
  * Kohavi et al. (2009) Kohavi R, Crook T, Longbotham R, Frasca B, Henne R, Ferres JL, Melamed T (2009) Online experimentation at microsoft. _Data Mining Case Studies_ 11(2009):39.
  * Kohavi et al. (2007) Kohavi R, Henne RM, Sommerfield D (2007) Practical guide to controlled experiments on the web: listen to your customers not to the hippo. _Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 959–967.
  * Kohavi et al. (2020) Kohavi R, Tang D, Xu Y (2020) _Trustworthy Online Controlled Experiments: A Practical Guide to A/B Testing_ (Cambridge University Press), URL http://dx.doi.org/10.1017/9781108653985.
  * Kohavi and Thomke (2017) Kohavi R, Thomke S (2017) The surprising power of online experiments. _Harvard Business Review_ 95:74–82.
  * Koning et al. (2019) Koning R, Hasan S, Chatterji A (2019) Experimentation and startup performance: Evidence from a/b testing. Technical report, National Bureau of Economic Research.
  * Laird et al. (1992) Laird NM, Skinner J, Kenward M (1992) An analysis of two-period crossover designs with carry-over effects. _Statistics in Medicine_ 11(14-15):1967–1979.
  * Li et al. (2020) Li X, Ding P, Rubin DB, et al. (2020) Rerandomization in $2^{k}$ factorial experiments. _The Annals of Statistics_ 48(1):43–63.
  * Lillie et al. (2011) Lillie EO, Patay B, Diamant J, Issell B, Topol EJ, Schork NJ (2011) The n-of-1 clinical trial: the ultimate strategy for individualizing medicine? _Personalized medicine_ 8(2):161–173.
  * Ma et al. (2020) Ma W, Simchi-Levi D, Zhao J (2020) Dynamic pricing under a static calendar. _Forthcoming at Management Science_ .
  * March (1991) March JG (1991) Exploration and exploitation in organizational learning. _Organization science_ 2(1):71–87.
  * Nie et al. (2018) Nie X, Tian X, Taylor J, Zou J (2018) Why adaptively collected data have negative bias and how to correct for it. _International Conference on Artificial Intelligence and Statistics_ , 1261–1269.
  * Oman and Seiden (1988) Oman SD, Seiden E (1988) Switch-back designs. _Biometrika_ 75(1):81–89.
  * Puelz et al. (2019) Puelz D, Basse G, Feller A, Toulis P (2019) A graph-theoretic approach to randomization tests of causal effects under general interference. _arXiv preprint arXiv:1910.10862_ .
  * Rambachan and Shephard (2019) Rambachan A, Shephard N (2019) Econometric analysis of potential outcomes time series: instruments, shocks, linearity and the causal response function. _arXiv preprint arXiv:1903.01637_ .
  * Robins (1986) Robins J (1986) A new approach to causal inference in mortality studies with a sustained exposure period—application to control of the healthy worker survivor effect. _Mathematical Modelling_ 7(9-12):1393–1512.
  * Robins et al. (1999) Robins JM, Greenland S, Hu FC (1999) Estimation of the causal effect of a time-varying exposure on the marginal mean of a repeated binary outcome. _Journal of the American Statistical Association_ 94(447):687–700.
  * Romano and Wolf (2000) Romano JP, Wolf M (2000) A more general central limit theorem for m-dependent random variables with unbounded m. _Statistics & probability letters_ 47(2):115–124.
  * Sarasvathy (2001) Sarasvathy SD (2001) Causation and effectuation: Toward a theoretical shift from economic inevitability to entrepreneurial contingency. _Academy of management Review_ 26(2):243–263.
  * Senn and Lambrou (1998) Senn S, Lambrou D (1998) Robust and realistic approaches to carry-over. _Statistics in Medicine_ 17(24):2849–2864.
  * Sitkin (1992) Sitkin SB (1992) Learning through failure: The strategy of small losses. _Research in organizational behavior_ 14:231–266.
  * Sobel (2012) Sobel ME (2012) Does Marriage Boost Men’s Wages?: Identification of Treatment Effects in Fixed Effects Regression Models for Panel Data. _Journal of the American Statistical Association_ 107(498):521–529, URL http://dx.doi.org/10.1080/01621459.2011.646917.
  * Sussman and Airoldi (2017) Sussman DL, Airoldi EM (2017) Elements of estimation theory for causal effects in the presence of network interference. _arXiv preprint arXiv:1702.03578_ .
  * Thomke (2001) Thomke S (2001) Enlightened experimentation. the new imperative for innovation. _Harvard Business Review_ 79(2):66–75.
  * Thomke (2020) Thomke SH (2020) _Experimentation Works: The Surprising Power of Business Experiments_ (Harvard Business Press).
  * Wager and Xu (2019) Wager S, Xu K (2019) Experimenting in equilibrium. _arXiv preprint arXiv:1903.02124_ .
  * Wu (1981) Wu CF (1981) On the robustness and efficiency of some randomized designs. _The Annals of Statistics_ 1168–1177.

Online Appendix

##  9 Recap of Notations

Within this paper, let $\mathbb{N},\mathbb{N}_{0}$ be the set of positive
integers and non-negative integers, respectively. For any $T\in\mathbb{N}$,
let $[T]=\\{1,...,T\\}$ be the set of positive integers no larger than $T$.
For any $t<t^{\prime}\in\mathbb{N}$, let
$\\{t:t^{\prime}\\}=\\{t,t+1,...,t^{\prime}\\}$ be the set of integers between
(including) $t$ and $t^{\prime}$. For any $m\in\mathbb{N}$, let
$\bm{1}_{m}=(1,1,...,1)$ be a vector of $m$ ones; let $\bm{0}_{m}=(0,0,...,0)$
be a vector of $m$ zeros. We use parentheses for probabilities, i.e.,
$\Pr(\cdot)$; brackets for expectations, i.e., $\mathbb{E}[\cdot]$; and curly
brackets for indicators, i.e., $\text{1}\\{\cdot\\}$. For any
$a\in\mathbb{R}$, let $(a)^{+}=\max\\{a,0\\}$.

##  10 Theorems Used

We summarize here the preliminaries that we have directly used in our proof.

######  Definition 10.1 ($\phi$-Dependent Random Variables, Hoeffding and
Robbins (1948))

For any sequence $\\{X_{1},X_{2},...\\}$, if there exists $\phi$ such that for
any $s-r>\phi$, the two sets

$(X_{1},X_{2},...,X_{r}),\quad(X_{s},X_{s+1},...,X_{n})$

are independent, then the sequence is said to be $\phi$-dependent.

######  Lemma 10.2 (Romano and Wolf (2000), Theorem 2.1)

Let $\left\\{X_{n,i}\right\\}$ be a triangular array of zero-mean random
variables. Let $\phi\in\mathbb{N}$ be a fixed constant. For each $n=1,2,...$,
let $d=d_{n}$, and suppose that $X_{n,1},X_{n,2},...,X_{n,d}$ is an
$\phi$-dependent sequence of random variables. Define

$\displaystyle
B^{2}_{n,k,a}=\mathsf{Var}\left(\sum_{i=a}^{a+k-1}X_{n,i}\right),$
$\displaystyle
B^{2}_{n}=B^{2}_{n,d,1}=\mathsf{Var}\left(\sum_{i=1}^{d}X_{n,i}\right)$

For some $\delta>0$ and $-1\leq\gamma\leq 1$, if the following conditions
hold:

  1. 1.

$\mathbb{E}\left|X_{n,i}\right|^{2+\delta}\leq\Delta_{n}$, for all $i$;

  2. 2.

$B^{2}_{n,k,a}/k^{1+\gamma}\leq K_{n}$, for all $a$ and $k\geq\phi$;

  3. 3.

$B^{2}_{n}/(d\phi^{\gamma})\geq L_{n}$;

  4. 4.

$K_{n}/L_{n}=O(1)$;

  5. 5.

$\Delta/L_{n}^{(2+\delta)/2}=O(1)$,

then

$\displaystyle\frac{\sum_{i=1}^{d}X_{n,i}}{B_{n}}\xrightarrow{D}\mathcal{N}(0,1).$

We explain Lemma 10.2. The $\xrightarrow{D}$ notation stands for convergence
in distribution. The definition of a sequence of $\phi$-dependent random
variables is given in Definition 10.1. To check if the conditions in Lemma
10.2 hold, we will first calculate $B^{2}_{n,k,a}$ for any $k$ and $a$, and
then construct some proper $\Delta_{n},K_{n},$ and $L_{n}$.

##  11 Proof of Unbiasedness of the Horvitz-Thompson Estimator

###### Proof 11.1

Proof of Theorem 2.5. First observe that for regular switchback experiments,
both $0<\Pr(\bm{W}_{t-p:t}=\bm{1}_{p+1}),\Pr(\bm{W}_{t-p:t}=\bm{0}_{p+1})<1$.
So Assumption 2.4 is naturally satisfied.

So for any $t\in\\{p+1:T\\}$, with probability
$\Pr(\bm{W}_{t-p:t}=\bm{1}_{p+1})\neq 0$,
$\text{1}{\\{\bm{W}_{t-p:t}=\bm{1}_{p+1}\\}}=1$, and
$Y_{t}^{\mathsf{obs}}=Y_{t}(\bm{1}_{p+1})$. So
$\mathbb{E}\left[Y_{t}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{t-p:t}=\bm{1}_{p+1}\\}}}{\Pr(\bm{W}_{t-p:t}=\bm{1}_{p+1})}\right]=Y_{t}(\bm{1}_{m+1})$.
Similarly
$\mathbb{E}\left[Y_{t}^{\mathsf{obs}}\frac{\text{1}{\\{\bm{W}_{t-p:t}=\bm{0}_{p+1}\\}}}{\Pr(\bm{W}_{t-p:t}=\bm{0}_{p+1})}\right]=Y_{t}(\bm{0}_{p+1})$.
Sum them up for any $t\in\\{p+1:T\\}$ we finish the proof.

##  12 Proofs and Discussions from Section 3

In Section 3 we focus on the case when $p=m$. Throughout this section in the
appendix, we use only $m$ instead of $p$.

###  12.1 Extra Notations Used in the Proofs from Section 3

For any $t\in\\{m+1:T\\}$, denote

$\text{1}_{t}(\mathbb{T},\mathbb{Y})=Y_{t}(\bm{1}_{m+1})\left[\text{1}\\{\bm{W}_{t-m:t}=(\bm{1}_{m+1})\\}\cdot
2\cdot\prod_{l=1}^{m}2^{\text{1}\\{t-l+1\in\mathbb{T}\\}}-1\right]\\\
-Y_{t}(\bm{0}_{m+1})\left[\text{1}\\{\bm{W}_{t-m:t}=(\bm{0}_{m+1})\\}\cdot
2\cdot\prod_{l=1}^{m}2^{\text{1}\\{t-l+1\in\mathbb{T}\\}}-1\right]$ (18)

where we use $2\prod_{l=1}^{m}2^{\text{1}\\{t-l+1\in\mathbb{T}\\}}$ to
calculate the inverse propensity score. When $\mathbb{T}$ and $\mathbb{Y}$ are
clear from the context we omit them and use $\text{1}_{t}$ for
$\text{1}_{t}(\mathbb{T},\mathbb{Y})$.

Using the above notation, we could re-write

$\displaystyle\hat{\tau}_{m}-\tau_{m}=\frac{1}{T-m}\sum_{t=m+1}^{T}\text{1}_{t}(\mathbb{T},\mathbb{Y})$

Note that $\forall t\in\\{m+1,m+2,...,T\\}$,

$\displaystyle\mathbb{E}[\text{1}_{t}(\mathbb{T},\mathbb{Y})]=0.$ (19)

Recall that any regular switchback experiment can be represented by
$\mathbb{T}=\\{t_{0},t_{1},...,t_{K}\\}\subseteq[T]$. Define
$f_{\mathbb{T}}:[T]\to\mathbb{T}$ to be the “determining randomization point
of period $t$”, i.e.

$f_{\mathbb{T}}(t)=\max\left\\{j\left|j\in\mathbb{T},j\leq t\right.\right\\}$

such that $W_{f_{\mathbb{T}}(t)}$ uniquely determines the distribution of
$W_{t}$, i.e. $W_{t}=W_{f_{\mathbb{T}}(t)}$. When $\mathbb{T}$ is clear from
the context we also omit the subscript and use $f(t)$ for $f_{\mathbb{T}}(t)$.

Similarly, we define $f^{m}_{\mathbb{T}}(t):[T]\to\\{0,1\\}^{\mathbb{T}}$,
which maps a time period to a subset of the set $\mathbb{T}$, to be the
“determining randomization points of periods $\\{t-m,t-m+1,...,t\\}$”, i.e.

$f^{m}_{\mathbb{T}}(t)=\left\\{j\left|\exists
i\in\\{t-m,...,t\\},s.t.j=f_{\mathbb{T}}(i)\right.\right\\}$

such that $f^{m}_{\mathbb{T}}(t)\subseteq\mathbb{T}\subseteq[T]$. And
$f^{m}_{\mathbb{T}}(t)$ contains all the time periods whose coin flips
determine the distributions of $W_{t-m},W_{t-m+1},...,W_{t}$. Denote
$\left|f^{m}_{\mathbb{T}}(t)\right|=J$. We keep in mind that $J$ depends on
$m,t$ and $\mathbb{T}$, yet they are all omitted for brevity. Since
$W_{t-m},W_{t-m+1},...,W_{t}$ are determined by at least one randomization
point $f(t-m)$, we know that $f^{m}_{\mathbb{T}}(t)\neq\emptyset$ is non-
empty, i.e.,

$\displaystyle\left|f^{m}_{\mathbb{T}}(t)\right|=J\geq 1.$ (20)

Finally, define “overlapping randomization points of periods
$\\{t-m,t-m+1,...,t\\}$ and
$\\{t^{\prime}-m,t^{\prime}-m+1,...,t^{\prime}\\}$” to be

$O_{\mathbb{T}}(t,t^{\prime})=f^{m}_{\mathbb{T}}(t)\cap
f^{m}_{\mathbb{T}}(t^{\prime})$

Denote $\left|O_{\mathbb{T}}(t,t^{\prime})\right|=J^{\mathsf{o}}$. We keep in
mind that $J^{\mathsf{o}}$ depends on $m,t,t^{\prime}$ and $\mathbb{T}$, yet
they are all omitted for brevity.

###  12.2 Lemma 3.1: Adversarial Selection of Potential Outcomes

####  12.2.1 Preliminaries.

We first introduce two Lemmas for the proof of Lemma 3.1.

###### Lemma 12.1

Under Assumptions 1–1, for any $t\in[T]$, let
$\left|f^{m}_{\mathbb{T}}(t)\right|=J$.

$\displaystyle\mathbb{E}[\text{1}_{t}^{2}]=$
$\displaystyle(2^{J}-1)Y_{t}(\bm{1}_{m+1})^{2}+2Y_{t}(\bm{1}_{m+1})Y_{t}(\bm{0}_{m+1})+(2^{J}-1)Y_{t}(\bm{0}_{m+1})^{2}.$
(21)

###### Proof 12.2

Proof of Lemma 12.1.

Denote $\left|f^{m}_{\mathbb{T}}(t)\right|=J$. Let the elements be
$f^{m}_{\mathbb{T}}(t)=\\{u_{1},u_{2},...,u_{J}\\}$. Let
$u_{1}<u_{2}<...<u_{J}$.

Using the notations defined earlier in Section 12,

$\displaystyle\mathbb{E}[\text{1}_{t}^{2}]=$
$\displaystyle\Pr\left(W_{t-m:t}=\bm{1}_{m+1}\right)\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}\cdot
1-1)-Y_{t}(\bm{0}_{m+1})(2^{J}\cdot 0-1)\right\\}^{2}$
$\displaystyle+\Pr\left(W_{t-m:t}=\bm{0}_{m+1}\right)\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}\cdot
0-1)-Y_{t}(\bm{0}_{m+1})(2^{J}\cdot 1-1)\right\\}^{2}$
$\displaystyle+\Pr\left(W_{t-m:t}\neq\bm{1}_{J}\text{ \ or \
}\bm{0}_{J}\right)\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}\cdot
0-1)-Y_{t}(\bm{0}_{m+1})(2^{J}\cdot 0-1)\right\\}^{2}$ $\displaystyle=$
$\displaystyle\Pr\left((W_{u_{1}},...,W_{u_{J}})=\bm{1}_{J}\right)\cdot\left\\{(2^{J}-1)Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}^{2}$
$\displaystyle+\Pr\left((W_{u_{1}},...,W_{u_{J}})=\bm{0}_{J}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})-(2^{J}-1)Y_{t}(\bm{0}_{m+1})\right\\}^{2}$
$\displaystyle+\Pr\left((W_{u_{1}},...,W_{u_{J}})\neq\bm{1}_{J}\text{ \ or \
}\bm{0}_{J}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}^{2}$
$\displaystyle=$
$\displaystyle(2^{J}-1)Y_{t}(\bm{1}_{m+1})^{2}+2Y_{t}(\bm{1}_{m+1})Y_{t}(\bm{0}_{m+1})+(2^{J}-1)Y_{t}(\bm{0}_{m+1})^{2}$

which finishes the proof.

###### Lemma 12.3

Under Assumptions 1–1, for any $t<t^{\prime}\in[T]$, when
$\left|O_{\mathbb{T}}(t,t^{\prime})\right|=J^{\mathsf{o}}=0$,

$\displaystyle\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=$ $\displaystyle
0.$ (22)

When $\left|O_{\mathbb{T}}(t,t^{\prime})\right|=J^{\mathsf{o}}\geq 1$,

$\displaystyle\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=$
$\displaystyle(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{1}_{m+1})Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t}(\bm{1}_{m+1})Y_{t^{\prime}}(\bm{0}_{m+1})$
$\displaystyle+Y_{t}(\bm{0}_{m+1})Y_{t^{\prime}}(\bm{1}_{m+1})+(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{0}_{m+1})Y_{t^{\prime}}(\bm{0}_{m+1}).$
(23)

###### Proof 12.4

Proof of Lemma 12.3.

Denote $\left|f^{m}_{\mathbb{T}}(t)\right|=J$,
$\left|f^{m}_{\mathbb{T}}(t^{\prime})\right|=J^{\prime}$, and
$\left|O_{\mathbb{T}}(t,t^{\prime})\right|=J^{\mathsf{o}}$. Let the elements
be $f^{m}_{\mathbb{T}}(t)=\\{u_{1},u_{2},...,u_{J}\\}$,
$f^{m}_{\mathbb{T}}(t^{\prime})=\\{u^{\prime}_{1},u^{\prime}_{2},...,u^{\prime}_{J^{\prime}}\\}$,
and
$O_{\mathbb{T}}(t,t^{\prime})=\\{u^{\mathsf{o}}_{1},u^{\mathsf{o}}_{2},...,u^{\mathsf{o}}_{J^{\mathsf{o}}}\\}$.
Let $u_{1}<u_{2}<...<u_{J}$,
$u^{\prime}_{1}<u^{\prime}_{2}<...<u^{\prime}_{J^{\prime}}$, and
$u^{\mathsf{o}}_{1}<u^{\mathsf{o}}_{2}<...<u^{\mathsf{o}}_{J^{\mathsf{o}}}$.

One time period could have different numberings in $f_{\mathbb{T}}^{m}(t)$,
$f_{\mathbb{T}}^{m}(t^{\prime})$, and $O_{\mathbb{T}}(t,t^{\prime})$. For
example, $u_{J-J^{\mathsf{o}}+1}=u^{\prime}_{1}=u^{\mathsf{o}}_{1}$, and
$u_{J}=u^{\prime}_{J^{\mathsf{o}}}=u^{\mathsf{o}}_{J^{\mathsf{o}}}$. See Table
12.4 for an illustrator of the determining randomization points and the
overlapping randomization points.

Illustrator of the determining randomization points and the overlapping
randomization points.  $u_{1}$ $u_{2}$ … $u_{J-J^{\mathsf{o}}+1}$ … $u_{J}$
$u^{\mathsf{o}}_{1}$ … $u^{\mathsf{o}}_{J^{\mathsf{o}}}$ $u^{\prime}_{1}$ …
$u^{\prime}_{J^{\mathsf{o}}}$ $u^{\prime}_{J^{\mathsf{o}}+1}$ …
$u^{\prime}_{J^{\prime}}$ Each columns stands for one time period. The first
row stands for the determining randomization points of
$f_{\mathbb{T}}^{m}(t)$; the second row for the overlapping randomization
points of $O_{\mathbb{T}}(t,t^{\prime})$; and the third row for the
determining randomization points of $f_{\mathbb{T}}^{m}(t^{\prime})$.

First, when $J^{\mathsf{o}}=0$, this implies that $\text{1}_{t}$ and
$\text{1}_{t^{\prime}}$ are independent. Then
$\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=\mathbb{E}[\text{1}_{t}]\mathbb{E}[\text{1}_{t^{\prime}}]=0$,
where the second equality is due to (19).

When $J^{\mathsf{o}}\geq 1$, this implies that $\text{1}_{t}$ and
$\text{1}_{t^{\prime}}$ are correlated. Using the notations defined above,

$\displaystyle\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=$
$\displaystyle\mathbb{E}_{W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}}\left[\mathbb{E}\left[\text{1}_{t}\text{1}_{t^{\prime}}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]\right]$
(24) $\displaystyle=$
$\displaystyle\Pr\left((W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})=\bm{1}_{J^{\mathsf{o}}}\right)\mathbb{E}\left[\text{1}_{t}\text{1}_{t^{\prime}}\left|(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})=\bm{1}_{J^{\mathsf{o}}}\right.\right]$
$\displaystyle+\Pr\left((W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})=\bm{0}_{J^{\mathsf{o}}}\right)\mathbb{E}\left[\text{1}_{t}\text{1}_{t^{\prime}}\left|(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})=\bm{0}_{J^{\mathsf{o}}}\right.\right]$
$\displaystyle+\Pr\left((W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})\neq\bm{1}_{J^{\mathsf{o}}}\text{\
or \
}\bm{0}_{J^{\mathsf{o}}}\right)\mathbb{E}\left[\text{1}_{t}\text{1}_{t^{\prime}}\left|(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})\neq\bm{1}_{J^{\mathsf{o}}}\text{\
or \ }\bm{0}_{J^{\mathsf{o}}}\right.\right]$

Next we go over the three cases of
$(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})$ as
decomposed above. Note that conditional on
$(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})$,
$\text{1}_{t}$ and $\text{1}_{t^{\prime}}$ are independent, i.e.,

$\displaystyle\mathbb{E}\left[\text{1}_{t}\text{1}_{t^{\prime}}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=\mathbb{E}\left[\text{1}_{t}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]\mathbb{E}\left[\text{1}_{t^{\prime}}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]$

(1) With probability $1/2^{J^{\mathsf{o}}}$,
$(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})=\bm{1}_{J^{\mathsf{o}}}$,
in which case

$\displaystyle\mathbb{E}\left[\text{1}_{t}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=$
$\displaystyle\Pr\left(W_{t-m:t}=\bm{1}_{m+1}\right)\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}\cdot
1-1)+Y_{t}(\bm{0}_{m+1})\right\\}$
$\displaystyle+\Pr\left(W_{t-m:t}\neq\bm{1}_{m+1}\right)\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}\cdot
0-1)+Y_{t}(\bm{0}_{m+1})\right\\}$ $\displaystyle=$
$\displaystyle\Pr\left((W_{u_{1}},W_{u_{2}},...,W_{u_{J-J^{\mathsf{o}}}})=\bm{1}_{J-J^{\mathsf{o}}}\right)\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}-1)+Y_{t}(\bm{0}_{m+1})\right\\}$
$\displaystyle+\Pr\left((W_{u_{1}},W_{u_{2}},...,W_{u_{J-J^{\mathsf{o}}}})\neq\bm{1}_{J-J^{\mathsf{o}}}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{J-J^{\mathsf{o}}}}\cdot\left\\{Y_{t}(\bm{1}_{m+1})(2^{J}-1)+Y_{t}(\bm{0}_{m+1})\right\\}+\left(1-\frac{1}{2^{J-J^{\mathsf{o}}}}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$
$\displaystyle(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})$

where the third equality is due to (2). Similarly,

$\displaystyle\mathbb{E}\left[\text{1}_{t^{\prime}}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=$
$\displaystyle\Pr\left(W_{t^{\prime}-m:t^{\prime}}=\bm{1}_{m+1}\right)\cdot\left\\{Y_{t^{\prime}}(\bm{1}_{m+1})(2^{J^{\prime}}\cdot
1-1)+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle+\Pr\left(W_{t^{\prime}-m:t^{\prime}}\neq\bm{1}_{m+1}\right)\cdot\left\\{Y_{t^{\prime}}(\bm{1}_{m+1})(2^{J^{\prime}}\cdot
0-1)+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$ $\displaystyle=$
$\displaystyle\Pr\left((W_{u^{\prime}_{J^{\mathsf{o}}+1}},W_{u^{\prime}_{J^{\mathsf{o}}+2}},...,W_{u^{\prime}_{J^{\prime}}})=\bm{1}_{J^{\prime}-J^{\mathsf{o}}}\right)\cdot\left\\{Y_{t^{\prime}}(\bm{1}_{m+1})(2^{J^{\prime}}-1)+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle+\Pr\left((W_{u^{\prime}_{J^{\mathsf{o}}+1}},W_{u^{\prime}_{J^{\mathsf{o}}+2}},...,W_{u^{\prime}_{J^{\prime}}})\neq\bm{1}_{J^{\prime}-J^{\mathsf{o}}}\right)\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$
$\displaystyle\frac{1}{2^{J^{\prime}-J^{\mathsf{o}}}}\cdot\left\\{Y_{t^{\prime}}(\bm{1}_{m+1})(2^{J^{\prime}}-1)+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}+\left(1-\frac{1}{2^{J^{\prime}-J^{\mathsf{o}}}}\right)\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$
$\displaystyle(2^{J^{\mathsf{o}}}-1)Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})$

(2) With probability $1/2^{J^{\mathsf{o}}}$,
$(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})=\bm{0}_{J^{\mathsf{o}}}$,
in which case

$\displaystyle\mathbb{E}\left[\text{1}_{t}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=$
$\displaystyle\Pr\left(W_{t-m:t}=\bm{0}_{m+1}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})-Y_{t}(\bm{0}_{m+1})(2^{J}\cdot
1-1)\right\\}$
$\displaystyle+\Pr\left(W_{t-m:t}\neq\bm{1}_{m+1}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})-Y_{t}(\bm{0}_{m+1})(2^{J}\cdot
0-1)\right\\}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{J-J^{\mathsf{o}}}}\cdot\left\\{-Y_{t}(\bm{1}_{m+1})-Y_{t}(\bm{0}_{m+1})(2^{J}-1)\right\\}+\left(1-\frac{1}{2^{J-J^{\mathsf{o}}}}\right)\cdot\left\\{-Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$ $\displaystyle-
Y_{t}(\bm{1}_{m+1})-(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{0}_{m+1})$
$\displaystyle\mathbb{E}\left[\text{1}_{t^{\prime}}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=$
$\displaystyle\Pr\left(W_{t^{\prime}-m:t^{\prime}}=\bm{0}_{m+1}\right)\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})-Y_{t^{\prime}}(\bm{0}_{m+1})(2^{J^{\prime}}\cdot
1-1)\right\\}$
$\displaystyle+\Pr\left(W_{t^{\prime}-m:t^{\prime}}\neq\bm{1}_{m+1}\right)\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})-Y_{t^{\prime}}(\bm{0}_{m+1})(2^{J^{\prime}}\cdot
0-1)\right\\}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{J^{\prime}-J^{\mathsf{o}}}}\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})-Y_{t^{\prime}}(\bm{0}_{m+1})(2^{J^{\prime}}-1)\right\\}+\left(1-\frac{1}{2^{J^{\prime}-J^{\mathsf{o}}}}\right)\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$ $\displaystyle-
Y_{t^{\prime}}(\bm{1}_{m+1})-(2^{J^{\mathsf{o}}}-1)Y_{t^{\prime}}(\bm{0}_{m+1})$

(3) With probability $1-2\cdot(1/2^{J^{\mathsf{o}}})$,
$(W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}})\neq\bm{1}_{J^{\mathsf{o}}}$
or $\bm{0}_{J^{\mathsf{o}}}$, in which case

$\displaystyle\mathbb{E}\left[\text{1}_{t}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=$
$\displaystyle-Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})$
$\displaystyle\mathbb{E}\left[\text{1}_{t^{\prime}}\left|W_{u_{1}^{\mathsf{o}}},...,W_{u_{J^{\mathsf{o}}}^{\mathsf{o}}}\right.\right]=$
$\displaystyle-Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})$

Finally, putting all above together into (24), we have

$\displaystyle\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=$
$\displaystyle\frac{1}{2^{J^{\mathsf{o}}}}\cdot\left\\{(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}\cdot\left\\{(2^{J^{\mathsf{o}}}-1)Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle+\frac{1}{2^{J^{\mathsf{o}}}}\cdot\left\\{-Y_{t}(\bm{1}_{m+1})-(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{0}_{m+1})\right\\}\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})-(2^{J^{\mathsf{o}}}-1)Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle+\left\\{1-\frac{2}{2^{J^{\mathsf{o}}}}\right\\}\cdot\left\\{-Y_{t}(\bm{1}_{m+1})+Y_{t}(\bm{0}_{m+1})\right\\}\cdot\left\\{-Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$
$\displaystyle=$
$\displaystyle(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{1}_{m+1})Y_{t^{\prime}}(\bm{1}_{m+1})+Y_{t}(\bm{1}_{m+1})Y_{t^{\prime}}(\bm{0}_{m+1})+Y_{t}(\bm{0}_{m+1})Y_{t^{\prime}}(\bm{1}_{m+1})+(2^{J^{\mathsf{o}}}-1)Y_{t}(\bm{0}_{m+1})Y_{t^{\prime}}(\bm{0}_{m+1})$

which finishes the proof.

####  12.2.2 Proof of Lemma 3.1.

The proof of Lemma 3.1 is through careful expansion of the risk function, the
expected square loss.

###### Proof 12.5

Proof of Lemma 3.1. From Lemma 12.1 and Lemma 12.3, all the terms are
quadratic, and all the coefficients are non-negative. That is, after
multiplying the constant $(T-m)^{2}$, for any
$\mathbb{T}\in[T],\mathbb{Y}\in\mathcal{Y}$ we can express in canonical form
the following:

$\displaystyle(T-m)^{2}\cdot\mathbb{E}_{\bm{W}_{1:T}\sim\eta(\cdot)}\left[\left(\hat{\tau}_{m}(\bm{W}_{1:T},\mathbb{Y})-\tau_{m}(\mathbb{Y})\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\sum_{t=m+1}^{T}\left\\{a_{t}(11)Y_{t}(\bm{1}_{m+1})^{2}+a_{t}(10)Y_{t}(\bm{1}_{m+1})Y_{t}(\bm{0}_{m+1})+a_{t}(00)Y_{t}(\bm{0}_{m+1})^{2}\right\\}$
$\displaystyle+\sum_{m+1\leq t<t^{\prime}\leq
T}\left\\{b_{tt^{\prime}}(11)Y_{t}(\bm{1}_{m+1})Y_{t^{\prime}}(\bm{1}_{m+1})+b_{tt^{\prime}}(10)Y_{t}(\bm{1}_{m+1})Y_{t^{\prime}}(\bm{0}_{m+1})\right.$
$\displaystyle\qquad\qquad\quad+\left.b_{tt^{\prime}}(01)Y_{t}(\bm{0}_{m+1})Y_{t^{\prime}}(\bm{1}_{m+1})+b_{tt^{\prime}}(00)Y_{t}(\bm{0}_{m+1})Y_{t^{\prime}}(\bm{0}_{m+1})\right\\}$

Combining Lemma 12.1 and inequality (20), $a_{t}(11),a_{t}(10),a_{t}(00)$ are
all strictly positive. From Lemma 12.3
$b_{tt^{\prime}}(11),b_{tt^{\prime}}(10),b_{tt^{\prime}}(01),b_{tt^{\prime}}(00)$
are all non-negative.

For the squared terms, $y^{2}\leq B^{2}$, where the inequality is due to
convexity. For the cross-product terms, $y_{1}\cdot
y_{2}\leq(y_{1}^{2}+y_{2}^{2})/2\leq B^{2}$ where the first inequality is due
to Cauchy-Schwarz, and the second inequality is due to convexity. Combining
that fact that all coefficients are non-negative,
$r(\eta_{\mathbb{T}},\mathbb{Y})\leq
r(\eta_{\mathbb{T}},\mathbb{Y}^{+})=r(\eta_{\mathbb{T}},\mathbb{Y}^{-})$.

Moreover, for any $\mathbb{Y}\in\mathcal{Y}$ such that
$\mathbb{Y}\neq\mathbb{Y}^{+}$ or $\mathbb{Y}^{-}$, if $\exists
t\in\\{m+1,...,T\\}$ such that $-B<Y_{t}(\bm{1}_{m+1})<B$. Then from
inequality (20), $a_{t}(11)>0$, so the inequality is strict. Similarly, if
$\exists t\in\\{m+1,...,T\\}$ such that $-B<Y_{t}(\bm{0}_{m+1})<B$, then
combine $a_{t}(00)>0$, so the inequality is strict.

####  12.2.3 Implications of Lemma 3.1.

Lemma 3.1 simplifies the minimax problem in (6). Instead of thinking it as a
minimax problem, we can now replace $\mathbb{Y}$ by either $\mathbb{Y}^{+}$ or
$\mathbb{Y}^{-}$, and solve only a minimization problem.

Here we state Lemma 12.6 that is a direct implication of Lemma 3.1. It will be
frequently used later on.

###### Lemma 12.6

When $\mathbb{Y}=\mathbb{Y}^{+}$ or $\mathbb{Y}=\mathbb{Y}^{-}$, under
Assumptions 1–1, for any $t\in[T]$,

$\displaystyle\mathbb{E}[\text{1}_{t}^{2}]=$ $\displaystyle 2^{J+1}B^{2}.$

For any $t<t^{\prime}\in[T]$, when
$\left|O_{\mathbb{T}}(t,t^{\prime})\right|=J^{\mathsf{o}}=0$,

$\displaystyle\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=$ $\displaystyle
0$

When $\left|O_{\mathbb{T}}(t,t^{\prime})\right|=J^{\mathsf{o}}\geq 1$,

$\displaystyle\mathbb{E}[\text{1}_{t}\text{1}_{t^{\prime}}]=$ $\displaystyle
2^{J^{\mathsf{o}}+1}B^{2}$

###### Proof 12.7

Proof of Lemma 12.6. Replace $Y_{t}(\bm{1}_{m+1})=Y_{t}(\bm{0}_{m+1})$ by $B$
or $-B$, into the expressions in Lemmas 12.1 and 12.3.

###  12.3 Structural Results of the Optimal Design

First note that when we focus on the optimal design, we treat $T$ and $m$ both
as constants. So the constant of $1/(T-m)$ in the expression of the risk
function does not affect the optimal design.

####  12.3.1 Proof of Lemma 3.3.

###### Proof 12.8

Proof of Lemma 3.3.

We prove the two parts separately, both by contradiction.

(1) Suppose there exists an optimal design
$\mathbb{T}=\\{t_{0}=1,t_{1},t_{2},...,t_{K}\\}$ such that $t_{1}\leq m+1$.
Then we try to construct another design $\tilde{\mathbb{T}}$, such that
$\left|\tilde{\mathbb{T}}\right|=K=\left|\mathbb{T}\right|-1$. And the $K$
elements are
$\tilde{\mathbb{T}}=\\{\tilde{t}_{0}=1,\tilde{t}_{1}=t_{2},\tilde{t}_{2}=t_{3},...,\tilde{t}_{K-1}=t_{K}\\}$.

An example of two regular switchback experiments $\mathbb{T}$ and
$\tilde{\mathbb{T}}$ when $m=4$ and $t_{1}=3$.  1 2 3 4 5 6 … $\mathbb{T}$
$\checkmark$ $-$ $\checkmark$ $-$ $-$ $\checkmark$ … $\tilde{\mathbb{T}}$
$\checkmark$ $-$ $-$ $-$ $-$ $\checkmark$ … Each checkmark beneath a number
indicates that this number is within that set; and each dash beneath a number
indicates that this number is not within that set. For example, the checkmark
$\checkmark$ beneath number $3$ indicates that $3\in\mathbb{T}$; and the dash
$-$ beneath number $3$ indicates that $3\neq\tilde{\mathbb{T}}$.

Next we argue that when $\mathbb{Y}=\mathbb{Y}^{+}$ or
$\mathbb{Y}=\mathbb{Y}^{-}$,

$r(\mathbb{T},\mathbb{Y})>r(\tilde{\mathbb{T}},\mathbb{Y}),$

which suggests that $\mathbb{T}$ is not the optimal design.

First, focus on the squared terms. For any $m+1\leq t\leq t_{1}+m-1$,
$t_{1}\in f^{m}_{\mathbb{T}}(t),t_{1}\neq f^{m}_{\tilde{\mathbb{T}}}(t)$.
Moreover, $t-m\leq t_{1}-1$, so that $t_{0}\in f^{m}_{\tilde{\mathbb{T}}}(t)$.
So $f^{m}_{\mathbb{T}}(t)-\\{t_{1}\\}=f^{m}_{\tilde{\mathbb{T}}}(t)$, and
$\left|f^{m}_{\tilde{\mathbb{T}}}(t)\right|\geq 1$. As a result,

$\mathbb{E}[\text{1}_{t}(\mathbb{T})^{2}]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})^{2}]\geq(2^{2+1}-2^{1+1})B^{2}=4B^{2}.$

For any $t\geq t_{1}+m$, either (i) $f_{\mathbb{T}}(t-m)=t_{1}$, in which case
$f_{\tilde{\mathbb{T}}}(t-m)=t_{0}$. This is the only difference between
$f^{m}_{\mathbb{T}}(t)$ and $f^{m}_{\tilde{\mathbb{T}}}(t)$, i.e.,
$f^{m}_{\mathbb{T}}(t)-\\{t_{1}\\}=f^{m}_{\tilde{\mathbb{T}}}(t)-\\{t_{0}\\}$.
So
$\left|f^{m}_{\mathbb{T}}(t)\right|=\left|f^{m}_{\tilde{\mathbb{T}}}(t)\right|$.
The second case is (ii) $f_{\mathbb{T}}(t-m)\geq t_{2}$, in which case
$f^{m}_{\mathbb{T}}(t)=f^{m}_{\tilde{\mathbb{T}}}(t)$. Both cases suggest that

$\mathbb{E}[\text{1}_{t}(\mathbb{T})^{2}]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})^{2}]=0.$

So we have

$\displaystyle\sum_{t=m+1}^{T}\mathbb{E}\left[\text{1}_{t}(\mathbb{T})^{2}\right]-\sum_{t=m+1}^{T}\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})^{2}\right]=$
$\displaystyle\sum_{t=m+1}^{t_{1}+m-1}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})^{2}\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})^{2}\right]\right)+\sum_{t=t_{1}+m}^{T}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})^{2}\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})^{2}\right]\right)$
$\displaystyle\geq$ $\displaystyle\sum_{t=m+1}^{t_{1}+m-1}(4B^{2})+0$
$\displaystyle=$ $\displaystyle 4(t_{1}-1)B^{2}$ $\displaystyle>$
$\displaystyle 0$

Second, focus on the cross product terms. For any $t$ and $t^{\prime}$ such
that $m+1\leq t<t^{\prime}\leq t_{1}+m-1$, $t_{1}\in
O_{\mathbb{T}}(t,t^{\prime}),t_{1}\neq O_{\tilde{\mathbb{T}}}(t,t^{\prime})$.
Moreover, $t-m\leq t_{1}-1$, so that $t_{0}\in O_{\mathbb{T}}(t,t^{\prime})$.
So
$O_{\mathbb{T}}(t,t^{\prime})-\\{t_{1}\\}=O_{\tilde{\mathbb{T}}}(t,t^{\prime})$,
and $\left|O_{\tilde{\mathbb{T}}}(t,t^{\prime})\right|\geq 1$. As a result,

$\mathbb{E}[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})]\geq(2^{2+1}-2^{1+1})B^{2}=4B^{2}>0.$

For any $m+1\leq t<t^{\prime}\leq T$ such that $t^{\prime}\geq t_{1}+m$,
either (i) $f_{\mathbb{T}}(t^{\prime}-m)=t_{1}$, in which case
$f_{\tilde{\mathbb{T}}}(t^{\prime}-m)=t_{0}$. So
$O_{\mathbb{T}}(t,t^{\prime})-\\{t_{1}\\}=O_{\tilde{\mathbb{T}}}(t,t^{\prime})-\\{t_{0}\\}$.
So
$\left|O_{\mathbb{T}}(t,t^{\prime})\right|=\left|O_{\tilde{\mathbb{T}}}(t,t^{\prime})\right|$.
The second case is (ii) $f_{\mathbb{T}}(t^{\prime}-m)\geq t_{2}$, in which
case $O_{\mathbb{T}}(t,t^{\prime})=O_{\tilde{\mathbb{T}}}(t,t^{\prime})$. Both
cases suggest that

$\mathbb{E}[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})]=0.$

So we have

$\displaystyle\sum_{m+1\leq t<t^{\prime}\leq
T}\mathbb{E}\left[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})\right]-\sum_{m+1\leq
t<t^{\prime}\leq
T}\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})\right]$
$\displaystyle=$ $\displaystyle\sum_{m+1\leq t<t^{\prime}\leq
t_{1}+m-1}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})\right]\right)+\sum_{\begin{subarray}{c}m+1\leq
t<t^{\prime}\leq T\\\ t^{\prime}\geq
t_{1}+m\end{subarray}}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})\right]\right)$
$\displaystyle\geq$ $\displaystyle 0$

Combine both square terms and cross-product terms we know that

$r(\mathbb{T},\mathbb{Y})>r(\tilde{\mathbb{T}},\mathbb{Y}).$

(2) Suppose there exists an optimal design
$\mathbb{T}=\\{t_{0}=1,t_{1},t_{2},...,t_{K}\\}$ such that $t_{K}\geq T-m+1$.
Then we try to construct another design $\tilde{\mathbb{T}}$, such that
$\left|\tilde{\mathbb{T}}\right|=K=\left|\mathbb{T}\right|-1$. And the $K$
elements are
$\tilde{\mathbb{T}}=\\{\tilde{t}_{0}=1,\tilde{t}_{1}=t_{1},\tilde{t}_{2}=t_{2},...,\tilde{t}_{K-1}=t_{K-1}\\}$.

An example of two regular switchback experiments $\mathbb{T}$ and
$\tilde{\mathbb{T}}$ when $m=4$ and $t_{K}=T-2$.  … $T-5$ $T-4$ $T-3$ $T-2$
$T-1$ $T$ $\mathbb{T}$ … $\checkmark$ $-$ $\checkmark$ $\checkmark$ $-$ $-$
$\tilde{\mathbb{T}}$ … $\checkmark$ $-$ $\checkmark$ $-$ $-$ $-$ Each
checkmark beneath a number indicates that this number is within that set; and
each dash beneath a number indicates that this number is not within that set.
For example, the checkmark $\checkmark$ beneath number $T-2$ indicates that
$T-2\in\mathbb{T}$; and the dash $-$ beneath number $T-2$ indicates that
$T-2\neq\tilde{\mathbb{T}}$.

Next we argue that when $\mathbb{Y}=\mathbb{Y}^{+}$ or
$\mathbb{Y}=\mathbb{Y}^{-}$,

$r(\mathbb{T},\mathbb{Y})>r(\tilde{\mathbb{T}},\mathbb{Y}),$

which suggests that $\mathbb{T}$ is not the optimal design.

First focus on the squared terms. For any $m+1\leq t\leq t_{K}-1$,
$f^{m}_{\mathbb{T}}(t)=f^{m}_{\tilde{\mathbb{T}}}(t)$ is totally unchanged.

$\mathbb{E}[\text{1}_{t}(\mathbb{T})^{2}]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})^{2}]=0.$

For any $t_{K}\leq t\leq T$, $t_{K}\notin
f^{m}_{\tilde{\mathbb{T}}}(t),t_{K}\in f^{m}_{\mathbb{T}}(t)$. And all the
other determining randomization points are unchanged. So
$f^{m}_{\tilde{\mathbb{T}}}(t)\subset f^{m}_{\mathbb{T}}(t)$ and
$f^{m}_{\mathbb{T}}(t)-\\{t_{K}\\}=f^{m}_{\tilde{\mathbb{T}}}(t)$ and
$\left|f^{m}_{\tilde{\mathbb{T}}}(t)\right|\geq 1$.

$\mathbb{E}[\text{1}_{t}(\mathbb{T})^{2}]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})^{2}]\geq(2^{2+1}-2^{1+1})B^{2}=4B^{2}.$

So we have

$\displaystyle\sum_{t=m+1}^{T}\mathbb{E}\left[\text{1}_{t}(\mathbb{T})^{2}\right]-\sum_{t=m+1}^{T}\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})^{2}\right]=$
$\displaystyle\sum_{t=m+1}^{t_{K}-1}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})^{2}\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})^{2}\right]\right)+\sum_{t=t_{K}}^{T}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})^{2}\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})^{2}\right]\right)$
$\displaystyle\geq$ $\displaystyle\sum_{t=t_{K}}^{T}(4B^{2})+0$
$\displaystyle=$ $\displaystyle 4(T-t_{K}+1)B^{2}$ $\displaystyle>$
$\displaystyle 0$

Next we focus on the cross-product terms. For any $m+1\leq t<t^{\prime}\leq T$
such that $t\leq t_{K}-1$,
$O_{\mathbb{T}}(t,t^{\prime})=O_{\tilde{\mathbb{T}}}(t,t^{\prime})$ is totally
unchanged.

$\mathbb{E}[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})]=0.$

For any $t_{K}\leq t<t^{\prime}\leq T$, since $t^{\prime}-m\leq T-m\leq
t_{K}-1$, so $f_{\tilde{\mathbb{T}}}(t^{\prime}-m)<t_{K}$ and
$\left|O_{\tilde{\mathbb{T}}}(t,t^{\prime})\right|\geq 1$ must contain an
element. Moreover, $O_{\tilde{\mathbb{T}}}(t,t^{\prime})\subset
O_{\mathbb{T}}(t,t^{\prime})$. So

$\mathbb{E}[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})]\geq(2^{2+1}-2^{1+1})B^{2}\geq
4B^{2}>0.$

So we have

$\displaystyle\sum_{m+1\leq t<t^{\prime}\leq
T}\mathbb{E}\left[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})\right]-\sum_{m+1\leq
t<t^{\prime}\leq
T}\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})\right]$
$\displaystyle=$ $\displaystyle\sum_{\begin{subarray}{c}m+1\leq
t<t^{\prime}\leq T\\\ t\leq
t_{K}-1\end{subarray}}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})\right]\right)+\sum_{t_{K}\leq
t<t^{\prime}\leq
T}\left(\mathbb{E}\left[\text{1}_{t}(\mathbb{T})\text{1}_{t^{\prime}}(\mathbb{T})\right]-\mathbb{E}\left[\text{1}_{t}(\tilde{\mathbb{T}})\text{1}_{t^{\prime}}(\tilde{\mathbb{T}})\right]\right)$
$\displaystyle\geq$ $\displaystyle 0$

Combine both square terms and cross-product terms we know that

$r(\mathbb{T},\mathbb{Y})>r(\tilde{\mathbb{T}},\mathbb{Y}).$

####  12.3.2 Proof of Lemma 3.4.

###### Proof 12.9

Proof of Lemma 3.4.

Recall that we denote $t_{0}=1$ and $t_{K+1}=T+1$. First, from Lemma 3.3,
$t_{1}\geq m+2,t_{K}\leq T-m$. So $k=1$ and $k=K$ cases both hold. Next, when
$2\leq k\leq K-1$, we prove by contradiction.

Suppose there exists some optimal design $\mathbb{T}$, such that $\exists
2\leq k\leq K-1,s.t.\ t_{k+1}-t_{k-1}\leq m-1.$ Denote

$\mathbb{K}=\\{k\in\\{2:K-1\\}\left|t_{k+1}-t_{k-1}\leq m-1\right.\\}.$

Since $\mathbb{K}\neq\emptyset$, pick $j=\max\mathbb{K}$ to be the largest
element in $\mathbb{K}$. Apparently $j\leq K-1$ since $j\in\\{2:K-1\\}$. We
also know that $t_{j+2}\geq t_{j}+m,$ because otherwise $j+1\in\mathbb{K}$,
which contradicts the maximality of $j$.

We now construct another design $\tilde{\mathbb{T}}$ such that
$\left|\tilde{\mathbb{T}}\right|=K=\left|\mathbb{T}\right|-1$, and the $K$
elements are
$\tilde{\mathbb{T}}=\\{\tilde{t}_{0}=1,\tilde{t}_{1}=t_{1},...,\tilde{t}_{j-1}=t_{j-1},\tilde{t}_{j}=t_{j+1},...,\tilde{t}_{K-1}=t_{K}\\}$.

An example of two regular switchback experiments $\mathbb{T}$ and
$\tilde{\mathbb{T}}$ when $m=4$ and $t_{j}=t_{j+1}-1=t_{j-1}+2$.  … $t_{j-1}$
$t_{j-1}+1$ $t_{j}$ $t_{j+1}$ $t_{j+1}+1$ $t_{j+1}+2$ $t_{j+2}$ … $\mathbb{T}$
… $\checkmark$ $-$ $\checkmark$ $\checkmark$ $-$ $-$ $\checkmark$ …
$\tilde{\mathbb{T}}$ … $\checkmark$ $-$ $-$ $\checkmark$ $-$ $-$ $\checkmark$
… Each checkmark beneath a number indicates that this number is within that
set; and each dash beneath a number indicates that this number is not within
that set. For example, the checkmark $\checkmark$ beneath number $t_{j}$
indicates that $t_{j}\in\mathbb{T}$; and the dash $-$ beneath number $t_{j}$
indicates that $t_{j}\neq\tilde{\mathbb{T}}$.

Next we argue that when $\mathbb{Y}=\mathbb{Y}^{+}$ or
$\mathbb{Y}=\mathbb{Y}^{-}$,

$r(\mathbb{T},\mathbb{Y})>r(\tilde{\mathbb{T}},\mathbb{Y}),$

which suggests that $\mathbb{T}$ is not the optimal design.

First focus on the squared terms. When $t\leq t_{j}-1$,
$f^{m}_{\mathbb{T}}(t)=f^{m}_{\tilde{\mathbb{T}}}(t)$ is totally unchanged.

$\mathbb{E}[\text{1}_{t}(\mathbb{T})^{2}]-\mathbb{E}[\text{1}_{t}(\tilde{\mathbb{T}})^{2}]=0.$

When $t_{j}\leq t\leq t_{j}+m-1$, this suggests that $t-m\leq t_{J}-1$ so that
$f_{\tilde{\mathbb{T}}}\leq t_{j}-1$. So $t_{j}\notin
f^{m}_{\tilde{\mathbb{T}}}(t),t_{j}\in f^{m}_{\mathbb{T}}(t)$. And all the
other determining randomization points are unchanged. So
$f^{m}_{\tilde{\mathbb{T}}}(t)\subset f^{m}_{\mathbb{T}}(t)$ and
$f^{m}_{\mathbb{T}}(t)-\\{t_{j}\\}=f^{m}_{\tilde{\mathbb{T}}}(t)$ and
$\left|f^{m}_{\tilde{\mathbb{T}}}(t)\right|\geq 1$.