Composition-Adjusted Empirical Bayes Leaderboards for Living Labs

A living lab sends real user traffic from a production search engine or news site to research systems and scores them by the clicks they earn. These benchmarks keep failing in the same way: clicks are so rare that the leaderboard is mostly noise. In TREC OpenSearch 2017, three teams each received only 30 to 44 clicks across more than 3,000 impressions. Their outcome scores ranged from 0.400 to 0.600 with p-values between 0.61 and 0.99, and the organizers estimated that nine months of traffic would be needed to separate them (Overview of TREC OpenSearch 2017). A second, less discussed problem compounds the first. In news labs such as CLEF NewsREEL, systems do not receive the same traffic. The broker drops any answer that misses a 100 ms deadline, and systems join and leave at different times. Each system's raw click-through rate therefore mixes its own quality with the publishers and hours it happened to serve (Benchmarking News Recommendations, CLEF NewsREEL 2016).

We propose to score living-lab systems with a structured empirical Bayes model. Empirical Bayes estimates a prior from all the data and then pulls each noisy estimate toward it, by an amount set by how little data that estimate rests on. Our model treats clicks in each cell (system × publisher × time slice) as binomial, separates a system's own effect from where and when it was served, and shrinks the sparse interaction cells. It reports each system's click rate on a common reference mix of traffic. The claim is testable without ground-truth labels: a leaderboard estimated from early weeks should predict which systems lead in later weeks better than raw click rates do. It should also reach a given level of ranking accuracy with fewer impressions.

Core Claim

The closest prior work is Shrinkage Estimators in Online Experiments. It applies positive-part James–Stein shrinkage to multi-arm Facebook A/B tests, cutting mean squared error by 10–50% in all 17 experiments. In Thompson-sampling simulations it raises the probability of finding the best arm by 30–40%. That paper supplies the motivation, namely that leaderboards with many arms suffer a winner's curse, and the basic tool. Its own stated limits are exactly the conditions of a living lab:

  • It assumes Gaussian sampling, which the authors say degrades for rare events, and click rates of around 1% are rare events.
  • It shrinks all arms into one flat pool and ignores structure.
  • It assumes randomized, balanced assignment of users to arms.
  • It never touches interleaving.

We claim that a binomial, crossed-effects shrinkage model with traffic-mix adjustment gives more reliable living-lab rankings than flat shrinkage. A second constraint shapes the design. Empirical Bayes Approach to Truth Discovery Problems shows that shrinking toward one grand mean raises error when the population has distinct clusters, which is why it partitions before shrinking. News publishers are such clusters, so our model shrinks within structure rather than toward a single mean.

Concretely, let $p_{a,s,t}$ be the click probability of system $a$ on publisher $s$ in time slice $t$. We model

$$\mathrm{logit}\, p_{a,s,t} = \mu + \alpha_a + \gamma_s + \tau_t + \delta_{a,s}, \qquad \alpha_a \sim N(0,\sigma_\alpha^2),\ \delta_{a,s} \sim N(0,\sigma_\delta^2).$$

Here $\mu$ is the overall rate, $\alpha_a$ the system effect, $\gamma_s$ and $\tau_t$ publisher and time effects, and $\delta_{a,s}$ a system-by-publisher interaction. The variances $\sigma_\alpha^2$ and $\sigma_\delta^2$ are estimated from the pooled data. The reported score for system $a$ is its predicted click rate averaged over a fixed reference distribution of publishers and times, so every system is judged on the same traffic mix.

Research Program

The work has three parts. The first is the estimator. We fit the model above by marginal likelihood using a Laplace approximation, which is cheap enough to refit nightly. Fitting happens at evaluation time, not serving time, so the 100 ms deadline does not constrain it. We also fit a nonparametric variant of the interaction prior, a discrete mixture, so that heavy-tailed or multimodal system-by-publisher effects are not forced to be Gaussian.

The second is the extension to interleaving and multileaving, where several rankers' results are blended into one list and clicks are credited to the ranker that contributed the clicked item. Following An Improved Multileaving Algorithm for Online Ranker Evaluation, we use Sample-only Scored Multileave (SOSM). SOSM credits rankers only on the documents actually shown and was built to fix two problems: Team Draft Multileave gives too little feedback per ranker, and Probabilistic Multileave rewards similar mediocre rankers for "teaming up". We keep SOSM's per-impression credit. Instead of averaging it independently per ranker, we shrink per-ranker × query-cluster credit with the same crossed structure, with query clusters playing the role of publishers.

The third is an honest map of where shrinkage cannot help. With three systems and about 15 decisive interleaving comparisons, as in OpenSearch 2017, no estimator recovers significance. The gains should appear in labs with many systems, such as NewsREEL 2016 with 73 services and NewsREEL 2017 with 18 algorithms, and in multileaving with dozens to hundreds of rankers. We will report the number of systems and impressions at which the benefit appears.

PEBS shrinks per-rater calibration maps and reports that it needs as few as 5 ratings per rater, against 20 for unshrunk fits. It also documents the main risk of shrinkage: genuine minority raters get pulled toward the majority. The analogue here is a system that is truly excellent only on a niche publisher. We will measure that attenuation directly rather than assume it away.

Baselines

The naive reference is raw click-through rate per system, or the raw wins/(wins+losses) outcome for interleaving. This is the scoring actually used in TREC OpenSearch 2017 and NewsREEL 2016–17. It is unbiased under balanced traffic and is what organizers publish, so any proposal must beat it on held-out prediction.

The second baseline is additive pseudo-count smoothing, clicks divided by impressions plus K. This is the heuristic practitioners use. A Probabilistic Perspective on Nearest Neighbor for Implicit Recommendation shows that principled Beta-prior intervals beat such ad hoc constants in item-based recommenders, reaching NDCG@50 of 0.2812 against 0.2724 for Item-KNN on MovieLens 1M, but that was offline and in a different task. We tune K on the same early-period data used to fit our model.

The third, and strongest, baseline is flat empirical Bayes shrinkage across systems in the spirit of Dimmery et al. We run it in two forms: their Gaussian positive-part James–Stein estimator, and a beta-binomial version with method-of-moments hyperparameters. Both see the same cells and the same time windows. If this baseline matches our model, the structure is not worth having and we will say so.

The fourth baseline is a mixed-effects logistic regression with system and publisher effects but no shrunk interaction cells. This is the generalized linear mixed model that Regularized Target Encoding Outperforms found consistently best among encoding schemes for high-cardinality categories.

For multileaving, the strongest existing method is SOSM itself. Brost et al. report an error rate of 16% (down from 32% for Probabilistic Multileave) with 100 rankers on MSLR-WEB30k under the informational click model after 10,000 iterations. Beating it means either lower pairwise ranking error at 10,000 iterations, or 16% error reached in materially fewer iterations, with the same click simulator and seeds. For NewsREEL leaderboard prediction there is no reported result found on Lacuna for held-out rank stability; the published figures are raw click rates, with a highest average of 1.23% in 2016 and up to 2.71% in 2017.

Two ablations isolate the key ingredients. The first removes the traffic-mix adjustment while keeping shrinkage. The second keeps the adjustment while setting $\sigma_\delta^2$ to zero, which tests whether shrinking the interaction cells matters.

Why not just…?

Why not just collect more traffic? The OpenSearch organizers estimate nine months for three systems (Overview of TREC OpenSearch 2017), and campaigns of that length are fragile: NewsREEL 2016 had to extend its window after stream disconnects (CLEF NewsREEL 2016). More data also does nothing about the traffic-mix confound, which does not shrink as impressions grow. Our impressions-to-accuracy curves quantify how much traffic the estimator saves.

Why not just apply flat James–Stein or beta-binomial shrinkage, as in Dimmery et al.? This is the real threat. On balanced, homogeneous traffic it may perform as well as our model. The evidence that it can fail comes from clustered populations, where flat shrinkage raised error in the truth-discovery Buildings data (Empirical Bayes Approach to Truth Discovery Problems), and from the Gaussian assumption at rare-event rates. The head-to-head temporal holdout settles it. We will also report the regimes, by traffic imbalance and number of publishers, where flat shrinkage suffices.

Why not just fit a standard mixed-effects logistic regression? Our model is a mixed-effects regression. The contributions are the choice of crossed structure, the shrunk interaction cells, the scoring on a reference traffic mix, the interleaving-credit extension, and the validation protocol. We include the plain mixed model as a baseline so the reader can see exactly what each addition buys. If the additions buy nothing, the useful finding is simply that living labs should report mixed-model scores, which would still change practice.

Why not just evaluate offline on replayed streams? NewsREEL found no direct correlation between offline replay metrics and live click rates (CLEF NewsREEL 2016). We use replay only to generate realistic traffic composition for simulation, never as the ranking criterion.

Proposed Experiments

The first experiment is a semi-synthetic multileaving study with known ground truth. We use MSLR-WEB30k with the Perfect, Navigational and Informational click models of Brost et al., 10 to 100 rankers, and query clusters taken from feature-space k-means. True ranker order comes from relevance labels. We measure pairwise ranking error as a function of iterations, comparing SOSM against SOSM plus flat shrinkage against SOSM plus structured shrinkage. As robustness checks, we inject periodic single-query bot traffic like the five-minute ssoar-q1 queries, and we plant one niche ranker that is best on a single cluster to measure minority attenuation.

The second experiment is a traffic-composition simulation on plista data. We replay the NewsREEL plista stream through Idomaar to obtain real publisher, hour and article-lifetime composition. We then simulate systems with planted effects and allocate impressions unevenly, imitating timeouts and staggered entry. This yields known truth under realistic imbalance. The metrics are error in each system's click rate on the reference mix, Kendall's tau against the true order, and per-publisher calibration for the niche system.

The third experiment is the decisive real-data check, a temporal holdout. On whatever per-system live logs the NewsREEL and OpenSearch organizers can share, we fit every estimator on the first part of a campaign. We then score held-out log-likelihood of later-period clicks per cell, and rank agreement with later-period raw click rates restricted to high-traffic cells, where raw rates are reliable. The proposal succeeds if structured shrinkage beats flat shrinkage and the plain mixed model on held-out likelihood and later-period rank agreement in the many-system campaigns. It fails, and we will report that it fails, if flat beta-binomial shrinkage matches it there. On the three-team OpenSearch data we expect and will report no separation from any method.