🤖 machine learning

A More Accurate Algorithm Comparison through A/B Testing using Offline Evaluation Methods

This paper challenges the conventional view that A/B testing is always superior to offline evaluation by revealing that A/B testing can suffer from higher selection error rates due to a lack of positive correlation, and proposes a novel estimator that intentionally induces this correlation through a stepwise comparison with a hypothetical middle algorithm to significantly reduce the data required for accurate algorithm selection.

Original authors: Koki Konishi, Masataka Ushiku, Yuta Saito

Published 2026-07-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Koki Konishi, Masataka Ushiku, Yuta Saito

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Choosing the Best Recipe

Imagine you run a restaurant and you want to decide between two new recipes for a soup: Recipe A and Recipe B. You want to know which one customers like better so you can serve it to everyone.

Usually, the "Gold Standard" (the best way to do this) is A/B Testing. You serve Recipe A to half your customers and Recipe B to the other half, then count the compliments. This is considered the most accurate method because you are testing on real, fresh data.

However, there is a catch:

It's expensive and risky: If Recipe B is terrible, you might ruin the dining experience for half your customers and lose money while you find out.
It needs a lot of data: To be 100% sure, you need to serve thousands of bowls.

Because of this, many restaurants try Offline Evaluation first. This is like asking your head chef to taste the soup based on a recipe book (historical data) without actually serving it to customers. It's safe and cheap, but usually, it's less accurate than the real tasting test.

The Surprise Discovery

The authors of this paper ran a test and found something very strange and counterintuitive:

Sometimes, the "safe" method (Offline Evaluation) is actually better at picking the winner than the "Gold Standard" (A/B Testing).

In their experiment, the standard A/B testing method (which they call AVG) made mistakes about 27% of the time, while the offline method made mistakes only 9% of the time.

Why did the "Gold Standard" fail?
Imagine you are judging two runners, Alice and Bob.

The A/B Testing method (AVG) sends Alice to a track in New York and Bob to a track in London. They run separately. You measure their times independently. Because they are in different places, their times have no connection to each other. If Alice has a bad day and Bob has a great day, you might wrongly think Bob is faster, even if Alice is actually the better runner.
The Offline method (IPS) makes both Alice and Bob run on the same track at the same time. Because they are running under the same conditions (same weather, same track quality), their times are correlated. If the track is muddy, both run slower. If it's sunny, both run faster. This "shared condition" cancels out the noise, making it easier to see who is truly faster.

The paper argues that A/B testing fails because it treats the two algorithms as if they are in completely separate worlds, missing out on the benefit of comparing them side-by-side.

The Solution: The "Middle Man" (MID)

The authors propose a new method called MID (Middle-In-Difference). They want to get the safety of A/B testing (using real data) but the accuracy of the offline method (comparing things side-by-side).

Here is how they do it, using a Tug-of-War analogy:

The Setup: You have Team A (Algorithm A) and Team B (Algorithm B). You want to know who is stronger.
The Problem: If you just pull them against each other directly, the rope might be too long and wobbly (high variance).
The Trick (The Middle Algorithm): The authors invent a hypothetical "Middle Team" (Team M). This team is a perfect mix of Team A and Team B.
The Step-by-Step Race:
- First, you have Team A race against Team M. You use the data from Team A's side of the A/B test. Because they are racing against a similar opponent (Team M), the results are stable.
- Second, you have Team B race against Team M. You use the data from Team B's side of the A/B test.
- Finally, you add the two results together to see who is stronger between A and B.

Why this works:
By introducing the "Middle Team," you force the two comparisons to share a common reference point. Just like the offline method, this creates a positive correlation. Even though Team A and Team B are in different groups, they are both being measured against the same "Middle Team." This cancels out the random noise and makes the final decision much more accurate.

The Results

The authors tested this on real data from a video recommendation app (like TikTok or YouTube).

Efficiency: The new MID method was able to pick the better algorithm with half (or even one-quarter) the amount of data required by the standard A/B testing method.
Stability: When the two algorithms were very different from each other (which usually breaks offline methods), MID still worked perfectly.
Accuracy: It made fewer mistakes than both the standard A/B test and the offline method.

Summary

The paper says: "We found that the standard way of doing A/B tests is actually a bit clumsy because it doesn't compare the two options fairly side-by-side. We invented a new trick using a 'Middle Algorithm' to force a fair comparison. This new trick lets us find the winner faster, with less data, and with fewer mistakes."

Technical Summary: A More Accurate Algorithm Comparison through A/B Testing using Offline Evaluation Methods

1. Problem Statement

In the development of online services such as recommender systems and search engines, selecting the superior algorithm is critical. While A/B testing is widely regarded as the "gold standard" for algorithm selection due to its ability to eliminate confounding factors through randomization, it is often costly and carries risks of degrading user experience or revenue if a poor algorithm is deployed. Conversely, offline evaluation (using historical log data) is safer but traditionally considered less accurate due to higher estimation variance and potential bias.

The authors identify a counterintuitive phenomenon: in certain scenarios, the standard Average (AVG) estimator used in A/B testing yields a higher algorithm selection error rate than offline evaluation methods like Inverse Propensity Scoring (IPS). The core issue lies in the statistical properties of the estimators:

AVG Estimator: Uses independent data for Algorithm A and Algorithm B. Consequently, the performance estimates are uncorrelated. The variance of the difference estimator is simply the sum of individual variances ( $Var(\hat{V}_A) + Var(\hat{V}_B)$ ), offering no mechanism to reduce variance through correlation.
Offline Estimators (e.g., IPS): Use shared historical data to estimate the performance of multiple algorithms. This unintentionally induces a positive correlation between the estimators. According to the variance decomposition formula ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$), this positive covariance reduces the total variance of the difference estimator, thereby lowering the probability of critical selection errors (underestimating the superior algorithm or overestimating the inferior one).

The paper posits that A/B testing fails to leverage this beneficial correlation, leading to suboptimal selection accuracy compared to offline methods in specific pre-experiments.

2. Methodology: The Middle-In-Difference (MID) Estimator

To address the lack of correlation in A/B testing, the authors propose a novel estimator called Middle-In-Difference (MID). The core idea is to intentionally induce positive correlation within the A/B testing framework by introducing a hypothetical middle algorithm ( $\pi_M$ ).

Stepwise Estimation Process:
Instead of directly comparing Algorithm A ( $\pi_A$ ) and Algorithm B ( $\pi_B$ ), MID decomposes the performance difference into two steps:

Estimate the difference between $\pi_A$ and $\pi_M$ using the log data collected from $\pi_A$ ( $D_A$ ).
Estimate the difference between $\pi_M$ and $\pi_B$ using the log data collected from $\pi_B$ ( $D_B$ ).

The final estimator is the sum of these two differences:
$\Delta \hat{V}_{MID} = (\hat{V}_{IPS}(\pi_A; D_A) - \hat{V}_{IPS}(\pi_M; D_A)) + (\hat{V}_{IPS}(\pi_M; D_B) - \hat{V}_{IPS}(\pi_B; D_B))$

Mechanism of Variance Reduction:

Induced Correlation: Because the first term uses shared data $D_A$ to estimate both $\pi_A$ and $\pi_M$ , and the second term uses shared data $D_B$ for $\pi_M$ and $\pi_B$ , positive correlations are induced within each step. This reduces the variance of the individual difference terms.
Optimal Middle Algorithm: The authors derive the optimal middle algorithm $\pi_M^*$ that minimizes the variance of the estimator. The optimal policy is defined as the harmonic mean of the logging policies:
$\pi_M^*(a|x) = \frac{2\pi_A(a|x)\pi_B(a|x)}{\pi_A(a|x) + \pi_B(a|x)}$
This design ensures that $\pi_M$ remains highly similar to both $\pi_A$ and $\pi_B$ , mitigating the "variance explosion" often seen in offline evaluation when comparing dissimilar algorithms (a common failure mode of standard IPS).

Theoretical Properties:

Unbiasedness: The authors prove that if the middle algorithm satisfies the condition that it only selects actions where at least one of the original algorithms has non-zero probability, the estimator remains unbiased.
Variance Comparison: Theoretical analysis demonstrates that the reward term of the MID variance is strictly less than or equal to that of the standard AVG estimator. Furthermore, unlike standard IPS, MID avoids the $1/\pi_A$ variance explosion when algorithm similarity is low because the intermediate comparisons involve similar policies.

3. Key Contributions

Statistical Insight: The paper clarifies that the standard AVG estimator in A/B testing is not necessarily optimal for algorithm selection because it fails to exploit the variance-reducing benefits of positive correlation between estimators.
Novel Estimator (MID): The authors propose the MID estimator, which intentionally induces positive correlation via a hypothetical middle algorithm and stepwise estimation, achieving lower selection error rates than both standard A/B testing (AVG) and offline evaluation (IPS).
Theoretical Derivation: The paper derives the optimal middle algorithm to minimize variance and provides a bias-variance analysis showing why MID outperforms existing methods.
Empirical Validation: Using real-world video recommendation data (KuaiRec), the authors demonstrate that MID consistently achieves lower selection error rates across various settings.

4. Experimental Results

The authors conducted experiments using the KuaiRec dataset, a fully-observed video recommendation dataset that allows for the calculation of ground-truth algorithm performance. They simulated an A/B testing environment with varying sample sizes and algorithm similarities.

Sample Efficiency: MID achieved the same selection error rate as existing methods (AVG and IPS) using only one-half to one-quarter of the A/B testing sample size. For instance, while AVG required 350–400 samples to reach a 5% error rate, MID achieved the same with 100–200 samples.
Robustness to Similarity:
- In high-similarity scenarios, MID outperformed IPS (which typically struggles with variance in offline settings) and AVG.
- In low-similarity scenarios, where IPS suffers from variance explosion due to importance weighting, MID remained stable and outperformed both IPS and AVG.
Mechanism Verification: Scatter plots of the estimates confirmed that MID successfully induces positive correlation between the stepwise estimators, resulting in a tighter distribution of the final difference estimate compared to the circular (uncorrelated) distribution of AVG. This tighter spread directly correlates with a reduction in critical selection errors.

5. Significance and Claims

The paper claims that the proposed MID estimator fundamentally improves the efficiency and accuracy of A/B testing for algorithm selection. By borrowing the statistical mechanism of offline evaluation (shared data inducing correlation) and applying it within the A/B testing framework via a hypothetical middle algorithm, MID overcomes the limitations of both traditional A/B testing (high variance due to independence) and offline evaluation (instability due to low similarity or lack of new data).

The authors emphasize that this approach allows organizations to make more accurate algorithm selection decisions with significantly fewer users or shorter experiment durations, reducing the cost and risk associated with online experimentation. The work suggests that the "gold standard" of A/B testing can be enhanced not by abandoning it, but by refining the estimation technique to leverage statistical correlations that were previously unexploited in online settings.