Exchangeability in AB Testing

Earlier this year, I worked on our cumulative impact feature; an implementation of the hierarchical normal normal model to enable customers to estimate the cumulative impact of past experiments while adjusting for the Winner’s Curse.

In my opinion, the largest difficulty with using this feature is going to be defining an exchangeable set of experiments, and so I thought I would collect my thoughts (for all to see) on exchangeability in AB tests so that I can be prepared to answer inevitable questions on the topic.

What is Exchangeability?

A sequence of random variables \(\theta_1, \cdots, \theta_K\) is said to be exchangeable if their joint distribution, \(p\), is invariant to permutations of the indices:

\[ p(\theta_1, \cdots, \theta_K)= p(\theta_{\pi(1)}, \cdots, \theta_{\pi(K)}). \]

Practically, exchangeability means that whatever you know about the experiments does not give you reason to believe that one experiment should systematically receive a larger or smaller treatment effect than another. Equivalently, if you were to hypothetically reshuffle the treatment effects among the experiments, each reassignment would remain just as plausible under your prior model as the one in front of you.

It may be easier to see what exchangeability is not. Suppose \(K=5\), and \(\theta_k\) is the true relative lift in revenue per user from experiment \(k\). Further suppose the treatment effects are ordered from smallest to largest, so that

\[ \theta_1 < \theta_2 < \theta_3 < \theta_4 < \theta_5. \]

Now suppose I assign those effects to experiments as follows:

Experiment	Treatment Effect
Pricing Experiment	\(\theta_1\)
Checkout Experiment	\(\theta_2\)
Site Redesign	\(\theta_3\)
Copy Change Experiment	\(\theta_4\)
Button Color Experiment	\(\theta_5\)

If it is surprising to you that a button-color or copy-change experiment in truth produces a larger effect on revenue than a pricing or checkout experiment, then the experiment labels are carrying information about the plausible sizes of the treatment effects. In that case, treating the effects as exchangeable is probably not defensible.

Exchangeability requires that, before seeing the experimental results, you would be just as comfortable with the assignment above as with one in which \(\theta_5\) belonged to the pricing experiment and \(\theta_1\) belonged to the button-color experiment.

Gelman and co-authors offer another way to think about exchangeability, describing exchangeability as follows in Bayesian Data Analysis 3ed:

If no information – other than the data \(y\) – is available to distinguish any of the \(\theta_j\)’s from any of the others, and no ordering or grouping of the parameters can be made, one must assume symmetry among the parameters in their prior distribution.

The symmetry point is, in a way, referring to the definition of exchangeability in terms of permutations (group theorists will know).

In this passage, Gelman and co-authors are giving us a useful way to think about exhgangeabulity in practice; Can the experiments be put in a meaningful order? Can they be sorted into groups? Either one is a way of saying the labels are informative, and either one is enough to make us think twice. That gives us a useful check we can use to determine how justifiable exchangeability may be. If you find that you can group experiment results, exchangeability may not be justifiable.

It may be useful to state here that exchangeability is different from being independent and identically distributed (IID). In fact,

\[\mbox{IID} \Rightarrow \mbox{Exchangeability} \>,\] however

\[\mbox{Exchangeability} \nRightarrow \mbox{IID}\]

For an example of a sequence of exchangeable but non IID random variables, see the section below.

Example: \(\mbox{Exchangeability} \nRightarrow \mbox{IID}\)

Let \(\Theta \sim \mbox{Uniform}(0, 1)\) and let \(X_1, X_2 \mid \Theta \overset{\mbox{IID}}{\sim} \mbox{Bernoulli}(\Theta)\).

Conditional on \(\Theta\), the \(X_1, X_2\) are IID by construction. However, if we look only at their joint distribution having integrated out \(\Theta\) (that is \(X_1, X_2\) and not \(X_1, X_2 \mid \Theta\)) then we can show they are not IID.

It is straightforward to show \(P(X_1=1)=P(X_2=1)=E[\Theta]=\frac{1}{2}\): Let \(f(\Theta) = 1\) be the probability density of \(\Theta\). Therefore

\[ \begin{align}P(X_j=1) = E_\Theta[P(X_j=1 \mid \Theta)] &= \int_{0}^1 P(X_j=1\mid \Theta=u)f(u) \, du \\ &= \int_0^1 u \, du \\ &= \dfrac{1}{2} \end{align} \]

If \(X_1, X_2\) were independent, then \(P(X_1=1, X_2=1) = P(X_1=1)P(X_2=1) = \frac{1}{4}\). Alas, this is false and quite easy to simulate in R

set.seed(123)

x <- t(replicate(1e6, {
  theta <- runif(1, 0, 1)
  rbinom(2, 1, theta)
}))

p_1_1 <- mean((x[, 1] == 1) & (x[, 2] == 1))
p_1_1
#> [1] 0.332823

In truth

\[\begin{align}P(X_1=1, X_2=1) &= \int_0^1 u^2 f(u) \, du \\ &= \dfrac{1}{3}\end{align}\]

Which is pretty close to our simulated estimate. So we’ve shown these random variables are not IID, but are they exchangeable? Their joint mass function is

\[ p(X_1=x_1, X_2=x_2) = \int_0^1 u^{x_1 + x_2} (1-u)^{2 - (x_1 + x_2)} f(u) \,du \>. \] The mass function relies only on the sum \(x_1 + x_2\), and since sums commute the joint mass function is invariant to permutations of the indices, hence these are exchangeable.

Why Is Exchangeability Important for Cumulative Impact?

To begin, let’s write down the model for cumulative impact. Let \(\theta\) be a true treatment effect in an AB test, \(\hat \theta\) be an estimate of \(\theta\), and let \(s\) be the standard error for said estimate. In AB testing, the distribution of \(\hat \theta \mid \theta\) is justified via the Central Limit Theorem, and it is typical to assume \(s\) is measured with enough precision to be assumed known. We use empirical Bayes to fit

\[\begin{align} \hat \theta_k \mid \theta_k &\sim \mbox{Normal}(\theta_k, s_k^2) \\ \theta_k \mid \mu, \tau &\sim \mbox{Normal}(\mu, \tau^2) \\ \end{align}\]

Conditional on \(\mu\) and \(\tau\), the treatment effects \(\theta_1,\cdots,\theta_K\) are IID. When \(\mu\) and \(\tau\) are unknown, the \(\theta_k\) are no longer independent after we account for our uncertainty about those shared parameters. They do, however, remain exchangeable. Permuting the experiment indices leaves their joint distribution unchanged.

Cumulative impact is intended to adjust for the bias one would incur when naively adding up treatment effects from winning experiments – i.e. the bias from the Winner’s Curse. The model powering cumulative impact achieves this through partial pooling: the estimate for each \(\theta_k\) is pulled toward the shared mean \(\mu\), allowing information from the collection of experiments to inform inference about the true effect of each individual experiment.

The amount of shrinkage depends on both \(s_k\) and \(\tau\). Experiments with noisier estimates are generally shrunk more heavily toward \(\mu\), while experiments estimated with greater precision are allowed to remain closer to their observed \(\hat\theta_k\).

Exchangeability is what licenses this sharing of information across experiments. If experiment identity itself tells us something about the plausible size of \(\theta_k\), then treating every experiment symmetrically under the same \(\mu\) and \(\tau\) may be inappropriate. Exchangeability is therefore a vital assumption of the model underlying the feature.

However, we don’t ever get to see \(\theta\), only their estimates. In what sense can we assess the plausibility of the assumption of exchangeability if we only have access to the noisy \(\hat \theta\) and not the \(\theta\)? This gives us our first takeaway: exchangeability is less an assumption that can be validated from the data and more a judgement about whether experiment identity contains information about the treatment effect, after accounting for the information we believe matters.

Making that judgement is partly an art. The remainder of this post discusses several common situations in which exchangeability may be more or less defensible, moving from stronger to weaker forms of the assumption.

What Cost Do We Pay For Non-Exchangeable Experiments?

Mathematically, a collection of random variables is either exchangeable or it is not. What is a matter of degree is how justifiable we believe exchangeability to be.

In practice, we may be willing to treat a collection of treatment effects as exchangeable even when there is a little nagging voice in our heads raising arguments to the contrary. In such cases, what costs do we pay if that judgement is wrong? The main cost is bad pooling.

The empirical Bayes model allows experiments to provide information about one another by shrinking their estimates toward a shared \(\mu\). If the experiments are not exchangeable, that shared mean may be an inappropriate shrinkage target. Some experiments may be shrunk too much, others not enough.

How much this costs a given experiment depends on its own standard error, \(s_k\), not just on how different the groups turn out to be. A noisy experiment is shrunk heavily anyway, so borrowing across a group boundary changes little about where it lands. A precise experiment (small \(s_k\)) barely shrinks toward \(\mu\) regardless, but it can end up disproportionately influencing \(\mu\) and \(\tau\) themselves, quietly distorting the shrinkage target for everyone else in the pool. So the real question is how different they are relative to what your data can actually resolve.

Similarly, \(\tau\) is intended to describe heterogeneity in treatment effects among experiments we are willing to treat symmetrically. If systematic differences between experiments are ignored, then \(\tau\) may end up absorbing structure that should have been modeled explicitly. Both problems ultimately affect the cumulative impact estimate.

How fast and loose we are willing to play with the exchangeability assumption can therefore depend partly on how important the resulting cumulative impact estimate is. If we need a ballpark number, we may tolerate a weaker argument for exchangeability. If we need a highly defensible estimate, then the composition of the experiment set becomes much more important (personally, I might even suggest a different method altogether, such as a holdout).

Small Note on Terminology

Going forward, I’m going to use the term “Treatment Class” to refer to the comparability of two treatments in terms of potential scope, effectiveness, and mechanism. For example, a copy change and a site re-design are in different treatment classes – different scope, effectiveness, and mechanism with which to modulate some metric.

How Can Non-Exchangeability Manifest in AB Testing?

In the words of Gelman, exchangeability must be assumed when no ordering or grouping of the experiments can be made. Additionally, when all permutations of the true treatment effects across experiments are equally preferable, exchangeability is more justifiable. We can use this to think about scenarios under which exchangeability may not be justifiable.

One scenario where exchangeability may be more easily justified is as follows: a team which targets a single metric, on a single surface, in a short time span (e.g. the checkout team running experiments across 4 weeks with revenue per user as their primary metric) may be the easiest case for exchangeability. Since the experiments were run in a reasonably short time and across homogeneous circumstances, and in the absence of any other information, we can’t group experiments, and it seems reasonable that – whatever their true treatment effects – there should be no reason to prefer one permutation among any other.

In AB testing, we can order or group experiments in a variety of ways. Below is a non-exhaustive set of criteria one may consider when trying to determine if exchangeability is justifiable:

• Time: If experiments are selected so that the “low hanging fruit” are picked first and the less certain experiments are last, then exchangeability is potentially unjustifiable. The selection indicates a preference for ordering (highly probable winners first), hence undermining exchangeability.

• Treatment Class: Copy and button colors are not in the same treatment class as free shipping or providing a steep discount because they differ in scope and mechanism. This may result in a certain preference for permutations of treatment effects among those experiments in the same treatment class.

• Metric Types: Experiments typically have some sort of mechanism by which they could plausibly move the primary metric. Secondary metrics and guardrail metrics are brought along to check if the treatment moves (or in the case of guardrails, doesn’t move) another metric. As such, we could group experiments by the status of the metric for which we are trying to estimate the cumulative impact.

• Surface: Interventions far up in the funnel may not affect down-funnel metrics in the same way as an intervention which is farther down the funnel. Hence, we can group experiments by their location in the user journey, or surface, and this may undermine exchangeability.

• Team we can, and often do, group experiments by team. Team is often a proxy for surface, treatment class, population, mechanism, and even psychology of experimenting. As such, between-team experiments can undermine exchangeability.

How To Justify Exchangeability

How can exchangeability ever be justified? It seems the examples covered in the previous section rule out exchangeability in a lot of cases. These examples are not intended to be laws. Rather, I want to be clear on possible dimensions on which exchangeability could fail. My perspective is that if you know the rules, then you will also know when to break them.

When considering treating a set of experiments as exchangeable, even if you suspect they may not be, you pay a cost with respect to their pooling – by how much, and to where, the experiments are shrunk. This directly affects the cumulative impact estimate. So consider the following questions:

• How much does it matter if I’m wrong? A cumulative impact number you’re using to sanity-check your own intuition about a quarter can tolerate a less rigorous exchangeability argument than one going into a leadership review or a customer-facing report. Raise your bar for the latter — or reach for a different method, like a holdout, if the number needs to hold up to scrutiny.

• What do I give up by not pooling? The alternative to tolerating a less rigorous exchangeability argument is usually splitting the pool — running cumulative impact separately by group. That’s not free: a smaller pool means fewer experiments informing \(\mu\) and \(\tau\), so the group-level shrinkage target itself gets noisier. Pooling more experiments together, even somewhat mismatched ones, can sometimes produce a better-estimated \(\mu\) and \(\tau\) than a smaller, purer pool would. The bias variance tradeoff applies.

If both answers point toward tolerance, pool and move on. If either one doesn’t — the number needs to be defensible, or splitting the pool wouldn’t cost you much — split the pool, run cumulative impact separately per group, or reach for a method built to handle the structure explicitly, like a holdout.