Doordash 如何透過 Switchback Experiment 處理 Network Effect

Doordash 是一家總部位在舊金山的外送平台，如同在台灣的 Uber Eats 或 Foodpanda，Doordash 作為一個平台負責媒合消費者與店家，並透過外送師（Dasher）協助完成每筆訂單。假設今天 Doordash 想要在某個地區發放折扣並檢視其成效，於是他們隨機地將一個地區裡面的消費者分為實驗組 (Treatment Group) 與對照組 (Control Group)，可想而知實驗組的消費者可能會更傾向去訂購，於是那一個地區的外送師會為了處理實驗組的訂單而疲於奔命。最後當我們檢視實驗效果的時候，其實很難說實驗組與對照組下訂的數量差異，到底是來自於優惠券的發放？還是因為外送師被實驗組大量佔據，導致根本就沒有 Supply 可以去處理對照組的 Demand？這個時候透過 A/B testing 估計的處置效果就會有 bias。

這樣的情形常見於雙邊市場（two-sided marketplace）的應用環境中，也就是說供需可能會互相影響，違反了傳統 A/B testing 的假設：每一個樣本都是獨立的，一些類似或相關的說法包括 SUTVA 的違反、Network Effect、Cluster Data、Interference。此時可以考慮 Switchback Experiment，透過不一樣的 randomization unit 來降低 network effect 在估計上的影響。

如其名，Switchback Experiment 會隨著時間轉換用戶們此時處於對照組還是實驗組，而為了要盡可能地利用流量，Doordash 考慮 region-time 為不同的觀測單位，如圖一所示，在同一個地點不同時間，用戶可能會被分到實驗組或對照組，而我們將不同地區視為不同的 cluster，想想應該也是挺合理的吧，畢竟台北跟高雄的外送師應該不會互相影響到。

Cluster Robust Standard Error

Background

我們先從迴歸分析的角度看一下 A/B testing 以及其相對應的 t-test：
$$Y = \alpha + \beta T + \epsilon,$$
其中 $Y$ 是 outcome，$T = 1$ 表示這個樣本是實驗組；反之，$T = 0$ 則是對照組，而 $\epsilon \stackrel{\text{iid}}{\sim} N(0, \sigma^2)$ 就是誤差項，在迴歸分析裡面我們對誤差的重要假設其實就體現在這，包括均值為零、獨立、同變異數、常態分佈。而如果從 A/B test 的方向來看的話，我們想比較的就是實驗組 $\mu_1 = \mathbb{E}[Y \mid T = 1]$ 與對照組 $\mu_0 = \mathbb{E}[Y \mid T = 0]$ 是否有顯著差異，而這兩組的假設檢定如下：

相信大家對於 A/B testing 裡面檢定均值的 t-test 都很熟悉，但事實上這與迴歸裡面的係數是否顯著是一致的，OLS 底下對於係數的假設檢定其實也就是 t-test，甚至這也與 ANOVA F-test 裡面的假設檢定是一致的，畢竟 $F_{1, \nu} = t^2_{\nu}$，（如果你想做 A/B/n testing 的話）。好的，我們終於可以用迴歸的角度來看實驗效果了。

在傳統的 A/B testing 裡面 $\epsilon$ 的假設應該是相當合理的，但如果今天的實驗是 Switchback Experiment 呢？我們先考慮矩陣寫法的迴歸，並以 OLS 估計，其中 $X_{N \times K} $就是一個有 $K$ 個自變數的矩陣：
$$\begin{aligned}
\mathbf{Y} &= \mathbf{X} \boldsymbol{\beta} + \boldsymbol{\epsilon} \\
\hat{\boldsymbol{\beta}} &= \mathbf{(X^\intercal X)^{-1} X^{\intercal} Y} \\
\text{Var}(\hat{\boldsymbol{\beta}}) &= \mathbf{(X^\intercal X)^{-1}X^\intercal}\Omega \mathbf{X (X^\intercal X)}^{-1}, \text{where }
\Omega = \text{Cov}( \boldsymbol{\epsilon}) = \mathbb{E}[\boldsymbol{\epsilon} \boldsymbol{\epsilon} ^\intercal]
\end{aligned}
$$
在一般的 OLS 裡面，因為我們有 $\epsilon \stackrel{\text{iid}}{\sim} N(0, \sigma^2)$，所以 $\Omega = \text{diag}\{\sigma^2\} = \sigma^2 \mathbf{I}_{n}$，一個 $n \times n $的對角矩陣， 此時：
$$\begin{aligned}
\text{Var}(\hat{\boldsymbol{\beta}}) &= \sigma^2\mathbf{(X^\intercal X)}^{-1} \\
\hat{\text{Var}}(\hat{\boldsymbol{\beta}}) &= \frac{\hat{\boldsymbol{\epsilon}}^\intercal \hat{\boldsymbol{\epsilon}} }{N-K}\mathbf{(X^\intercal X)}^{-1}, \text{ where }
\hat{\boldsymbol{\epsilon}} = \mathbf{Y} – \mathbf{X}\hat{\boldsymbol{\beta}}
\end{aligned}
$$
$\hat{\boldsymbol{\epsilon}}$ 就是預測的殘差啦，以上就是大家熟悉的模樣了，希望有一切都串起來的感覺（？）

Estimation

但是在 Switchback Experiment，資料是有不同 cluster 的，如圖二所示，我們考慮每一個 region-time 為不同的 cluster，且總共有 $G$ 個 cluster：
$$\mathbf{Y}_g = \mathbf{X}_g \boldsymbol{\beta}_g + \boldsymbol{\epsilon}_g, \quad g = 1, \ldots, G $$
$\{ \mathbf{X}_g , \mathbf{Y}_g \}$ 表示在第 $g$ 個 cluster 裡面的資料，其中 $\mathbf{X}_g$ 是一個 $N_g \times K$ 的矩陣，也就是在這個 cluster 裡面有 $N_g$ 個樣本。接著再進一步把所有 cluster 的資料堆疊起來：
$$ \mathbf{Y} = \mathbf{X} \boldsymbol{\beta} + \boldsymbol{\epsilon},$$
我們可以直接套用 OLS 的結果：
$$
\begin{aligned}
\hat{\boldsymbol{\beta}} &= (\mathbf{X}^\intercal \mathbf{X})^{-1} \mathbf{X}^\intercal \mathbf{Y} \\
\text{Var}(\hat{\boldsymbol{\beta}}) &= \mathbf{(X^\intercal X)}^{-1} \mathbf{B} \mathbf{ (X^\intercal X)}^{-1}\\
\mathbf{B} &= \mathbf{ X^\intercal \boldsymbol{\Omega} X }
\end{aligned}
$$
接下來要處理 $\mathbf{B}$ 這一項，因為我們沒有 equal variance 這個假設了，所以不能跟前面一樣化簡，但是從定義下手的話，我們仍可以得到 $\mathbf{\Omega}$ 是一個 block diagonl matrix（中文是分塊對角矩陣嗎？），畢竟不同 cluster 之間沒有關係 （$\text{COV}(\boldsymbol{\epsilon}_g, \boldsymbol{\epsilon}_h) = \mathbf{0}, \text{ wherer } g \neq h$），此時 $\boldsymbol{\Omega}$ 會長得如圖三所示。

那麼 $\mathbf{B}$ 也就可以簡化成：
$$\begin{aligned}
\mathbf{B} &= \mathbf{X}^\intercal \boldsymbol{\Omega} \mathbf{X} \\
&= \begin{bmatrix} \mathbf{X}_1^\intercal & \mathbf{X}_2^\intercal & \cdots & \mathbf{X}_G^\intercal \end{bmatrix}
\begin{bmatrix}
\mathbb{E}[\boldsymbol{\epsilon}_1 \boldsymbol{\epsilon}_1^\intercal ] & \cdots & \mathbf{0} \\
\vdots & \ddots & \vdots \\
\mathbf{0} & \cdots & \mathbb{E}[\boldsymbol{\epsilon}_G \boldsymbol{\epsilon}_G^\intercal]
\end{bmatrix}
\begin{bmatrix} \mathbf{X}_1 \\ \mathbf{X}_2 \\ \vdots \\ \mathbf{X}_G \end{bmatrix} \\
&= \sum_{g=1}^G \mathbf{X}_g^\intercal \mathbb{E}[\boldsymbol{\epsilon}_g \boldsymbol{\epsilon}_g^\intercal] \mathbf{X}_g
\end{aligned}
$$
而我們對於 $\mathbb{E}[\boldsymbol{\epsilon}_g \boldsymbol{\epsilon}_g^\intercal]$ 的估計最直接的就是考慮 plug-in estimator，會得到 $\hat{B}$ 與相對應的 $\hat{\text{Var}}(\hat{\boldsymbol{\beta}})$：
$$\begin{aligned}
\hat{\mathbf{B}} &= \sum_{g=1}^G \mathbf{X}_g^\intercal \hat{\boldsymbol{\epsilon}}_g \hat{\boldsymbol{\epsilon}}_g^\intercal \mathbf{X}_g, \quad \hat{\boldsymbol{\epsilon}}_g = \mathbf{Y}_g – \mathbf{X}_g \hat{\boldsymbol{\beta}}_g \\
\hat{\text{Var}}(\hat{\boldsymbol{\beta}}) &= \mathbf{(X^\intercal X)}^{-1} \hat{\mathbf{B}} \mathbf{ (X^\intercal X)}^{-1}
\end{aligned}
$$

不過很不幸的是，當 $G \to \infty$，$\hat{\text{Var}}(\hat{\boldsymbol{\beta}})$ 才是一個 consistent estimator，因此我們可以針對有限樣本的變異數估計進行校正，這就是 Cluster Robust Standard Error (CRSE)：
$$ \hat{\text{Var}}(\hat{\boldsymbol{\beta}}) _{\text{clu}}= \mathbf{(X^\intercal X)}^{-1} \hat{\mathbf{B}} \mathbf{ (X^\intercal X)}^{-1} \underbrace{\frac{G}{G-1}\frac{N-1}{N-K}}_{c} $$
這邊用來校正的 $c$ 目前並沒有一個很公認的值， 市面上的 package 對於 $c$ 的選擇也有所不同，見 。另外當每個個體的誤差都有不同的變異數時（i.e. 每個個體都是一個群體，$G=N$），那麼這時的標準誤就是 Heteroskedasticity-consistent (HC) standard errors，常見的 HC0- HC3 就是這個東西。

Bootstrap Method

誠如上段所說，CRSE 的估計並沒有一定的標準，Doordash 也透過 Bootstrap 的方法建立共變異數矩陣的估計，如此就可以比較他們算出來的 CRSE 與透過 Bootstrap 建構的 CRSE 是否相近，理論上來說會非常類似。

步驟（重複 $B$ 次）:
1. Form $G$ clusters $\{(\mathbf{Y}_g^*, \mathbf{X}^*_g)\}_{g=1}^G$ by resampling with replacement G times from the original sample of clusters.
2. Compute the estimate of $\boldsymbol{\beta}$ denoted $\hat{\boldsymbol{\beta}}_b$ in the $b$-th bootstrap sample.
$$ \hat{\text{Var}}(\hat{\boldsymbol{\beta}})_{clu; boot} = \frac{c}{B-1}\sum_{b=1}^B (\hat{\boldsymbol{\beta}}_b – \bar{\hat{\boldsymbol{\beta}}})(\hat{\boldsymbol{\beta}}_b – \bar{\hat{\boldsymbol{\beta}}})^\intercal, \text{ where } \bar{\hat{\boldsymbol{\beta}}} = B^{-1}\sum_b \hat{\boldsymbol{\beta}}_b$$

Inference

為了要檢驗 $H_0: \beta = 0$，我們考慮 t-statistic：
$$ t = \frac{\hat{\beta}}{s_{\hat{\beta}}},$$
這邊的 $s_{\hat{\beta}}$ 就是 $\hat{\text{Var}}(\hat{\boldsymbol{\beta}}) _{\text{clu}}$ 相對應的元素，也就是說我們透過 CRSE 去建構係數的標準誤。雖然當 $G \to \infty$ 時，$t \sim N(0, 1)$，但實務上 cluster 的數量是有限的，此時 $t$ 的分布是未知的，但一般來說會用 $G-1$ 自由度的 t 分佈, $t_{G-1}$ 。

此外，我們可以透過 Bootstrap 建構 empirical 的拒絕域與 p-value（Percentile- t bootstrap）：

步驟（重複 $B$ 次）：
1. Form $G$ clusters $\{(\mathbf{Y}_g^*, \mathbf{X}^*_g)\}_{g=1}^G$ by resampling with replacement G times from the original sample of clusters.
2. Compute the OLS estimate $\hat{\beta}^*$ in this resample.
3. Calculate the test statistic $t_b^* = (\hat{\beta}^* – \hat{\beta}) / s_{\hat{\beta}^*}$, where $s_{\hat{\beta}^*}$ is the cluster-robust standard error of $\hat{\beta}^*$ and $\hat{\beta}$ is the OLS estimate of $\beta$ from the original sample.

那麼 95% 信心水準的 $t$ 的拒絕域可以透過 $\{t_b^* \}_{b=1}^B$ 的 2.5 與 97.5 百分位數建立， 而其 p-value 也就是 $|t| > |t_b^*|, b = 1, \ldots, B$ 的比例。

Simulation

Doordash 也用模擬資料來看 CRSE 的校正是否能夠更正確地檢視 Switchback experiment 的成效，他們考慮不同的方法：

A. Delivery level regression （直接對所有資料做 OLS）
B. Regional-time unit level regression （以 cluster 為單位做 OLS）
C. Delivery level with CRSE on regional-time unit （A. 加上 CRSE 校正）
D. Delivery level with CRSE on regional-time unit and added market as fixed effects （C. 加上 Fixed effect）
E. Log transformation with outcome variable with D. (D. 加上對 Y 取 log)

$$
\begin{array}{c l c c }
\hline
& \textbf{Method} & \textbf{WithinCI} & \textbf{Power} \\ \hline
\textbf{A.} &Y_{u,d} \sim T_u & 0.66 & 0.89 \\ \hline
\textbf{B.} & Y_u \sim T_u & 0.96 & 0.26 \\ \hline
\textbf{C.} & Y_{u,d} \sim T_u ~ (\text{cluster} = u) & 0.95 & 0.52 \\ \hline
\textbf{D.} & Y_{u,d} \sim T_u + M_{u,d} ~ (\text{cluster} = u) & 0.95 & 0.64 \\ \hline
\textbf{E.} & \log(Y_{u,d}) \sim T_u + M_{u,d} ~ (\text{cluster} = u) & 0.94 & 0.55 \\ \hline
\end{array}$$

• $Y_{u,d}$: 在 cluster u 裡面第 d 筆訂單的運送時間
• $Y_u$: 在 cluster u 裡面的 d 筆訂單的平均運送時間
• $T_u$: cluster 是實驗組還是控制組？（$T_u = 1$ 即是實驗組）
• $M_{u,d}$: 在 cluster u 裡面第 d 筆訂單的 market effect，可以視之為每一個 cluster 有一個 intercept (Fixed effect)

首先，A 忽略了 network effect，並把所有的 cluster 當作一個群體看待，可以看到此時 power 特別高，主要是因為 A 低估了 standard error，致使 CI 相對較小，t 檢定量很高，也就更容易去拒絕 $H_0$，但同時 CI 能夠涵蓋到實際效果的比例是很低的。而 B 雖然 withinCI 提高許多，但 Power 卻是最低的，可以猜想原因之一是樣本數大量減少 ($N \to G$)。而再加入 CRSE 的校正之後，可以發現 C、D、E 實驗都能夠比較正確的去衡量係數的標準誤。

雖然 Doordash 在原本的文章沒有描述整個實驗過程，但我大膽猜測跟另外一篇 Doordash 的文章中是一致的，可以參考 。

另外，Bolt（歐洲的 Uber）也針對這個議題做了實驗，他們進行了數個 A/A test 來比較「忽視誤差之間的相關性」與「使用 CRSE 校正之後的結果」，理論上 A/A test 會無法拒絕 $H_0$，畢竟實驗組與對照組之間沒有差別，且如果進行多個 A/A test，其 p-value 會是一個 [0, 1] 的均勻分布（Unifrom Distribution ），可以想像 $\Pr(\text{p-value} \leq \alpha) = \alpha$ 且 $\text{p-value} \in [0, 1]$ 。如圖四所示，要是我們對於標準誤沒有進行相關性的校正，p-value 會是一個右偏的分佈，但此時 A/A 是沒有差異的，所以要是我們就 $\text{p-value} < \alpha$ 去拒絕 $H_0$，False Positive Rate 會很高，這個現象也跟 Doordash 的模擬一致，忽略資料之間的相關性會使得我們對於實驗的結果有錯誤解讀。

Conclusion

對於 Switchback Experiment，Doordash 採用 CRSE 來考慮樣本之間的相關性，並藉此對於係數的標準誤進行校正，如此就能得到比傳統 A/B testing 更加正確的結果。而我們也從 A/B test的 t 檢定，走到迴歸分析的模型，並解釋為什麼誤差的假設是重要的，最後在 cluster data 的情境底下提出如何估計 CRSE，並就 CRSE 進行處置效果的推論。以上的流程稍嫌複雜， 則是直接在他們的產品當中實作 Bootstrap 的信賴區間，並以此進行假設檢定，直接給 Switchback Experiment 一個暴力且直觀的解讀 XDD
啊我自己也在文章當中提及許多 Bootstrap 的估計方法，也沒有什麼特別的原因，就只是因為我也很喜歡 Bootstrap lol

Takeaway

1. 如果產品當中有 Network Effect，採用傳統的 A/B testing 有很大的可能會錯誤解讀實驗結果，此時可以考慮使用 Switchback Experiment，對不同的觀測單位進行 Randomization。
2. 在 Switchback Experiment 中，因為在同個 cluster 之間的樣本有相關性，因此可以使用 CRSE 對變異數的估計進行校正。
3. 無論如何都可以透過 A/A test 檢視不同的實驗方法是否合理，也可以透過模擬 A/B testing 估計 Type 1, Type 2 error。再次強調 A/A test 真的很重要！

References