A/B testing a recommender

The estimator#

For a binary outcome with $n_A, n_B$ users per arm and observed rates $\hat{p}_A, \hat{p}_B$, the pooled two-proportion $z$ statistic is

$$ z = \frac{\hat{p}_B - \hat{p}_A}{\sqrt{\hat{p}\,(1-\hat{p})\left(\frac{1}{n_A} + \frac{1}{n_B}\right)}}, \qquad \hat{p} = \frac{c_A + c_B}{n_A + n_B} $$

with $c_A, c_B$ the click counts. Required sample size per arm for a two-sided test at level $\alpha$ with power $1-\beta$:

$$ n = \frac{\left(z_{1-\alpha/2} + z_{1-\beta}\right)^2 \left[p_1(1-p_1) + p_2(1-p_2)\right]}{(p_2 - p_1)^2} $$

The inverse-square dependence on the effect size is the governing fact of the whole discipline. Halving the detectable effect quadruples the cost.

The ratio metric caveat. Click-through rate is a ratio of two random quantities, and the randomisation unit is the user while the denominator counts impressions. Treating each impression as independent understates the variance badly, because impressions from one user are correlated. Use the delta method for the variance of a ratio, or bootstrap over users. Reporting a naive binomial standard error on a per-impression CTR is one of the most common errors in industrial experiment reports.

Variance reduction#

CUPED (Deng, Xu, Kohavi and Walker, 2013), Improving the Sensitivity of Online Controlled Experiments by Utilizing Pre-Experiment Data:

$$ Y^{\text{cuped}} = Y - \theta (X - \mathbb{E}[X]), \qquad \theta = \frac{\operatorname{Cov}(Y, X)}{\operatorname{Var}(X)} $$

$X$ is a pre-experiment covariate — most usefully the same metric measured on the same users before the test began. The adjusted estimator is unbiased because $X$ is independent of assignment, and its variance is reduced by a factor $(1 - \rho^2)$ with $\rho = \operatorname{Corr}(Y, X)$.

For engagement metrics $\rho$ of 0.5 to 0.8 is common, which cuts required sample size by 25 to 64 percent. It is the highest-return change available to most experimentation platforms, and it costs one extra column in the data.

Triggered analysis. Restrict the analysis to users who could have been affected — those who actually saw a recommendation slot. Diluting the effect across users who never reached the surface reduces power for no gain. The trigger condition must be computable identically in both arms, or the comparison is broken.

Sequential testing#

The peeking inflation in the developer block is the classical multiple-testing problem under correlated looks. Two principled remedies:

Group sequential designs (O'Brien-Fleming, Pocock boundaries) fix the number of interim analyses in advance and spend the type-I error budget across them via an alpha-spending function.

Always-valid inference gives a $p$-value that is valid at every sample size. Johari, Koomen, Pekelis and Walsh (2017), Peeking at A/B Tests, construct a mixture sequential probability ratio test whose $p$-value process satisfies

$$ P\left( \exists\, t : p_t \le \alpha \mid H_0 \right) \le \alpha $$

so continuous monitoring is legitimate. The cost is a larger expected sample size when the effect is small — the guarantee is bought with power, not created from nothing.

Interleaving#

For ranking changes specifically, interleaving is dramatically more sensitive than an A/B test. Team-draft interleaving (Radlinski, Kurup and Joachims, 2008) merges the two rankings into one list shown to each user, attributing each click to the ranker that contributed the item. Each user is their own control, so between-user variance vanishes.

Chapelle et al. (2012), Large-Scale Validation and Analysis of Interleaved Search Evaluation, report sensitivity gains of one to two orders of magnitude in required traffic relative to A/B testing, with rankings that agree with A/B conclusions.

The limits are real: interleaving compares two rankings over the same candidate pool and cannot measure changes to the interface, to latency, or to anything session-level. Use it to choose between rankers, then A/B test the winner against the incumbent for the value metrics.

Interference#

User-level randomisation assumes the stable unit treatment value assumption: one user's outcome does not depend on another user's assignment. Recommenders violate it routinely.

• Marketplaces: finite inventory means promoting an item to treatment users removes it from control users.
• Two-sided platforms: creator-side effects propagate to consumers in both arms.
• Shared model state: online learning updated by both arms couples them directly.

Standard remedies are cluster randomisation (by region, by supply pool, by time block) and switchback designs alternating the whole system between arms across time intervals. Both raise variance considerably, since the effective sample size drops to the number of clusters or intervals. Estimating the bias from ignoring interference is generally harder than accepting the variance cost.

The long-term problem#

Two-week experiments measure two-week outcomes. Hohnhold, O'Brien and Tang (2015), Focusing on the Long-term, describe long-term holdback groups kept on the old system for months, and cohort-based analyses that estimate the accumulated effect of a sequence of shipped changes.

This is the only rigorous answer to the diversity trade-off from diversity and filter bubbles. A diversity change that costs 1 percent of clicks this fortnight and improves retention over six months is undetectable in the short experiment and visible in the holdback. Organisations without a long-term holdback are structurally unable to make that trade correctly, however good their statistics are.

Papers#

• Radlinski, Kurup and Joachims (2008), How Does Clickthrough Data Reflect Retrieval Quality?, CIKM — team-draft interleaving.
• Chapelle et al. (2012), Large-Scale Validation and Analysis of Interleaved Search Evaluation, ACM TOIS.
• Deng, Xu, Kohavi and Walker (2013), Improving the Sensitivity of Online Controlled Experiments by Utilizing Pre-Experiment Data (CUPED), WSDM.
• Kohavi, Deng, Frasca, Walker, Xu and Pohlmann (2013), Online Controlled Experiments at Large Scale, KDD.
• Hohnhold, O'Brien and Tang (2015), Focusing on the Long-term: It's Good for Users and Business, KDD.
• Johari, Koomen, Pekelis and Walsh (2017), Peeking at A/B Tests: Why it matters, and what to do about it, KDD.
• Kohavi, Tang and Xu (2020), Trustworthy Online Controlled Experiments — the standard book-length treatment.

What to learn next#

• Ranking metrics — the offline estimators this replaces.
• Monitoring and model drift — the measurement that continues after the experiment ends.
• What is a recommender system — back to the start, with the whole pipeline in view.