🤖 machine learning

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

Diese Arbeit stellt die herkömmliche Ansicht in Frage, dass A/B-Tests immer dem Offline-Evaluation überlegen sind, indem sie aufzeigt, dass A/B-Tests aufgrund eines Mangels an positiver Korrelation höhere Selektionsfehlerraten aufweisen können, und schlägt einen neuartigen Schätzer vor, der diese Korrelation durch einen schrittweisen Vergleich mit einem hypothetischen mittleren Algorithmus gezielt induziert, um die für eine präzise Algorithmenselektion erforderliche Datenmenge signifikant zu reduzieren.

Ursprüngliche Autoren: Koki Konishi, Masataka Ushiku, Yuta Saito

Veröffentlicht 2026-07-03

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Koki Konishi, Masataka Ushiku, Yuta Saito

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Das beste Rezept auswählen

Stellen Sie sich vor, Sie führen ein Restaurant und möchten sich zwischen zwei neuen Rezepten für eine Suppe entscheiden: Rezept A und Rezept B. Sie möchten wissen, welches den Kunden besser schmeckt, damit Sie es allen servieren können.

Normalerweise ist der „Goldstandard“ (die beste Methode dafür) der A/B-Test. Sie servieren Rezept A der Hälfte Ihrer Kunden und Rezept B der anderen Hälfte und zählen dann die Komplimente. Dies gilt als die genaueste Methode, da Sie mit echten, frischen Daten testen.

Es gibt jedoch einen Haken:

Es ist teuer und riskant: Wenn Rezept B schrecklich ist, könnten Sie das Essenserlebnis für die Hälfte Ihrer Kunden ruinieren und Geld verlieren, während Sie das herausfinden.
Es benötigt viele Daten: Um zu 100 % sicher zu sein, müssen Sie tausende Schüsseln servieren.

Aus diesem Grund versuchen viele Restaurants zuerst eine Offline-Evaluierung. Das ist so, als würde man Ihren Chefkoch bitten, die Suppe basierend auf einem Rezeptbuch (historische Daten) zu probieren, ohne sie tatsächlich an Kunden zu servieren. Das ist sicher und günstig, aber normalerweise weniger genau als der echte Geschmackstest.

Die überraschende Entdeckung

Die Autoren dieser Arbeit haben einen Test durchgeführt und etwas sehr Seltsames und Kontraintuitives herausgefunden:

Manchmal ist die „sichere“ Methode (Offline-Evaluierung) tatsächlich besser darin, den Gewinner zu ermitteln, als der „Goldstandard“ (A/B-Testing).

In ihrem Experiment machte die Standard-A/B-Test-Methode (die sie AVG nennen) Fehler in etwa 27 % der Fälle, während die Offline-Methode nur in 9 % der Fälle Fehler machte.

Warum versagte der „Goldstandard“?
Stellen Sie sich vor, Sie bewerten zwei Läufer, Alice und Bob.

Die A/B-Testing-Methode (AVG) schickt Alice auf eine Laufbahn in New York und Bob auf eine Laufbahn in London. Sie laufen getrennt voneinander. Sie messen ihre Zeiten unabhängig voneinander. Da sie an unterschiedlichen Orten sind, haben ihre Zeiten keine Verbindung zueinander. Wenn Alice einen schlechten Tag hat und Bob einen großartigen Tag, könnten Sie fälschlicherweise annehmen, dass Bob schneller ist, obwohl Alice eigentlich die bessere Läuferin ist.
Die Offline-Methode (IPS) lässt sowohl Alice als auch Bob auf der gleichen Laufbahn zur gleichen Zeit laufen. Da sie unter den gleichen Bedingungen laufen (gleiches Wetter, gleiche Qualität der Laufbahn), sind ihre Zeiten korreliert. Wenn die Bahn matschig ist, laufen beide langsamer. Wenn es sonnig ist, laufen beide schneller. Diese „gemeinsame Bedingung“ gleicht das Rauschen aus, was es einfacher macht zu sehen, wer wirklich schneller ist.

Das Papier argumentt, dass A/B-Tests fehlschlagen, weil sie die beiden Algorithmen so behandeln, als befänden sie sich in völlig unterschiedlichen Welten, und dabei den Vorteil eines direkten Seitenvergleichs ignorieren.

Die Lösung: Der „Vermittler“ (MID)

Die Autoren schlagen eine neue Methode namens MID (Middle-In-Difference) vor. Sie wollen die Sicherheit des A/B-Testings (Verwendung von echten Daten) mit der Genauigkeit der Offline-Methode (Seitenvergleich) kombinieren.

So machen sie es, unter Verwendung einer Tauziehen-Analogie:

Der Aufbau: Sie haben Team A (Algorithmus A) und Team B (Algorithmus B). Sie wollen wissen, wer stärker ist.
Das Problem: Wenn Sie sie einfach direkt gegeneinander antreten lassen, könnte das Seil zu lang und wackelig sein (hohe Varianz).
Der Trick (Der mittlere Algorithmus): Die Autoren erfinden ein hypothetisches „Mittleres Team“ (Team M). Dieses Team ist eine perfekte Mischung aus Team A und Team B.
Der schrittweise Ablauf:
- Zuer Sie haben Team A gegen Team M antreten lassen. Sie verwenden die Daten von der Seite des A/B-Tests von Team A. Da sie gegen einen ähnlichen Gegner (Team M) antreten, sind die Ergebnisse stabil.
- Zweitens lassen Sie Team B gegen Team M antreten. Sie verwenden die Daten von der Seite des A/B-Tests von Team B.
- Schließlich addieren Sie die beiden Ergebnisse, um zu sehen, wer zwischen A und B stärker ist.

Warum das funktioniert:
Durch die Einführung des „Mittleren Teams“ zwingen Sie die beiden Vergleiche dazu, einen gemeinsamen Bezugspunkt zu teilen. Genau wie bei der Offline-Methode erzeugt dies eine positive Korrelation. Auch wenn Team A und Team B in unterschiedlichen Gruppen sind, werden beide gegen dasselbe „Mittlere Team“ gemessen. Dies gleicht das zufällige Rauschen aus und macht die endgültige Entscheidung wesentlich genauer.

Die Ergebnisse

Die Autoren testeten dies mit echten Daten aus einer Video-Empfehlungs-App (wie TikTok oder YouTube).

Effizienz: Die neue MID-Methode war in der Lage, den besseren Algorithmus mit der Hälfte (oder sogar einem Viertel) der Datenmenge auszuwählen, die die Standard-A/B-Test-Methode benötigt hätte.
Stabilität: Wenn die beiden Algorithmen sehr unterschiedlich waren (was Offline-Methoden normalerweise zum Scheitern bringt), funktionierte MID dennoch perfekt.
Genauigkeit: Sie machte weniger Fehler als sowohl der Standard-A/B-Test als auch die Offline-Methode.

Zusammenfassung

Das Papier sagt: „Wir haben herausgefunden, dass die Standardmethode der A/B-Tests eigentlich etwas ungeschickt ist, weil sie die beiden Optionen nicht fair im direkten Vergleich betrachtet. Wir haben einen neuen Trick unter Verwendung eines ‚mittleren Algorithmus‘ erfunden, um einen fairen Vergleich zu erzwingen. Dieser neue Trick ermöglicht es uns, den Gewinner schneller, mit weniger Daten und mit weniger Fehlern zu finden.“

Technische Zusammenfassung: Ein präziserer Algorithmenvergleich durch A/B-Tests unter Verwendung von Offline-Evaluationsmethoden

1. Problemstellung

In der Entwicklung von Online-Diensten wie Empfehlungssystemen und Suchmaschinen ist die Auswahl des überlegenen Algorithmus entscheidend. Während A/B-Tests aufgrund ihrer Fähigkeit, Störfaktoren durch Randomisierung zu eliminieren, weithin als der „Goldstandard“ für die Algorithmenauswahl gelten, sind sie oft kostspielig und bergen das Risiko, die Nutzererfahrung oder den Umsatz zu verschlechtern, wenn ein schlechter Algorithmus eingesetzt wird. Umgekehrt ist die Offline-Evaluierung (unter Verwendung historischer Log-Daten) zwar sicherer, wird jedoch traditionell als weniger genau angesehen, da sie eine höhere Schätzvarianz und potenzielle Verzerrungen (Bias) aufweist.

Die Autoren identifizieren ein kontraintuitives Phänomen: In bestimmten Szenarien liefert der Standard-AVG-Schätzer (Average Estimator), der in A/B-Tests verwendet wird, eine höhere Fehlerrate bei der Algorithmenauswahl als Offline-Evaluationsmethoden wie das Inverse Propensity Scoring (IPS). Das Kernproblem liegt in den statistischen Eigenschaften der Schätzer:

AVG-Schätzer: Verwendet unabhängige Daten für Algorithmus A und Algorithmus B. Folglich sind die Leistungsschätzungen unkorreliert. Die Varianz des Differenzschätzers ist einfach die Summe der individuellen Varianzen ( $Var(\hat{V}_A) + Var(\hat{V}_B)$ ), was keinen Mechanismus bietet, um die Varianz durch Korrelation zu reduzieren.
Offline-Schätzer (z. B. IPS): Verwenden gemeinsame historische Daten, um die Leistung mehrerer Algorithmen zu schätzen. Dies induziert unbeabsichtigt eine positive Korrelation zwischen den Schätzern. Gemäß der Varianzzerlegungsformel ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$) reduziert diese positive Kovarianz die Gesamtvarianz des Differenzschätzers, wodurch die Wahrscheinlichkeit kritischer Selektionsfehler (die Unterschätzung des überlegenen Algorithmus oder die Überschätzung des unterlegenen Algorithmus) gesenkt wird.

Das Papier postuliert, dass A/B-Tests diese vorteilhafte Korrelation nicht nutzen, was in spezifischen Prä-Experimenten zu einer suboptimalen Selektionsgenauigkeit im Vergleich zu Offline-Methoden führt.

2. Methodik: Der Middle-In-Difference (MID) Schätzer

Um das Fehlen der Korrelation in A/B-Tests zu adressieren, schlagen die Autoren einen neuartigen Schätzer namens Middle-In-Difference (MID) vor. Die Kernidee besteht darin, durch die Einführung eines hypothetischen mittleren Algorithmus ( $\pi_M$ ) absichtlich eine positive Korrelation innerhalb des A/B-Testing-Frameworks zu induzieren.

Schrittweiser Schätzprozess:
Anstatt Algorithmus A ( $\pi_A$ ) direkt mit Algorithmus B ( $\pi_B$ ) zu vergleichen, zerlegt MID die Leistungsdifferenz in zwei Schritte:

Schätzung der Differenz zwischen $\pi_A$ und $\pi_M$ unter Verwendung der von $\pi_A$ gesammelten Log-Daten ( $D_A$ ).
Schätzung der Differenz zwischen $\pi_M$ und $\pi_B$ unter Verwendung der von $\pi_B$ gesammelten Log-Daten ( $D_B$ ).

Der endgültige Schätzer ist die Summe dieser beiden Differenzen:
$\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))$

Mechanismus der Varianzreduktion:

Induzierte Korrelation: Da der erste Term gemeinsame Daten $D_A$ verwendet, um sowohl $\pi_A$ als auch $\pi_M$ zu schätzen, und der zweite Term gemeinsame Daten $D_B$ für $\pi_M$ und $\pi_B$ verwendet, werden innerhalb jedes Schritts positive Korrelationen induziert. Dies reduziert die Varianz der einzelnen Differenzterme.
Optimaler mittlerer Algorithmus: Die Autoren leiten den optimalen mittleren Algorithmus $\pi_M^*$ ab, der die Varianz des Schätzers minimiert. Die optimale Policy ist definiert als das harmonische Mittel der Logging-Policies:
$\pi_M^*(a|x) = \frac{2\pi_A(a|x)\pi_B(a|x)}{\pi_A(a|x) + \pi_B(a|x)}$
Dieses Design stellt sicher, dass $\pi_M$ den beiden Algorithmen $\pi_A$ und $\pi_B$ sehr ähnlich bleibt, was die oft bei der Offline-Evaluierung beobachtete „Varianzexplosion“ (ein häufiger Ausfallmodus des Standard-IPS beim Vergleich unähnlicher Algorithmen) abmildert.

Theoretische Eigenschaften:

Unverzerrtheit (Unbiasedness): Die Autoren beweisen, dass der Schätzer unverzerrt bleibt, sofern der mittlere Algorithmus die Bedingung erfüllt, dass er nur Aktionen auswählt, bei denen mindestens einer der ursprünglichen Algorithmen eine Wahrscheinlichkeit größer Null hat.
Varianzvergleich: Die theoretische Analyse zeigt, dass der Reward-Term der MID-Varianz strikt kleiner oder gleich dem des Standard-AVG-Schätzers ist. Darüber hinaus vermeidet MID im Gegensatz zum Standard-IPS die $1/\pi_A$ -Varianzexplosion, wenn die Ähnlichkeit der Algorithmen gering ist, da die Zwischenvergleiche ähnliche Policies involvieren.

3. Kernbeiträge

Statistischer Einblick: Das Paper verdeutlicht, dass der Standard-AVG-Schätzer in A/B-Tests nicht notwendigerweise optimal für die Algorithmenauswahl ist, da er die varianzreduzierenden Vorteile der positiven Korrelation zwischen Schätzern nicht nutzt.
Neuartiger Schätzer (MID): Die Autoren schlagen den MID-Schätzer vor, der durch einen hypothetischen mittleren Algorithmus und eine schrittweise Schätzung absichtlich positive Korrelation induziert und so niedrigere Fehlerraten bei der Auswahl als sowohl das Standard-A/B-Testing (AVG) als auch die Offline-Evaluierung (IPS) erreicht.
Theoretische Herleitung: Das Paper leitet den optimalen mittleren Algorithmus zur Minimierung der Varianz ab und liefert eine Bias-Varianz-Analyse, die zeigt, warum MID bestehende Methoden übertrifft.
Empirische Validierung: Unter Verwendung von realen Videorekommandationsdaten (KuaiRec) demonstrieren die Autoren, dass MID konsistent über verschiedene Settings hinweg niedrigere Fehlerraten bei der Algorithmenauswahl erzielt.

4. Experimentelle Ergebnisse

Die Autoren führten Experimente mit dem KuaiRec-Datensatz durch, einem vollständig beobachteten Video-Empfehlungsdatensatz, der die Berechnung der Ground-Truth-Algorithmenleistung ermöglicht. Sie simulierten eine A/B-Testing-Umgebung mit variierenden Stichprobengrößen und Algorithmenähnlichkeiten.

Sampeleffizienz: MID erreichte die gleiche Fehlerrate wie bestehende Methoden (AVG und IPS) mit nur der Hälfte bis einem Viertel der A/B-Testing-Stichprobengröße. Beispielsweise benötigte AVG 350–400 Samples, um eine Fehlerrate von 5 % zu erreichen, während MID dasselbe mit 100–200 Samples erreichte.
Robustheit gegenüber Ähnlichkeit:
- In Szenarien mit hoher Ähnlichkeit übertraf MID (das in Offline-Settings typischerweise mit hoher Varianz zu kämpfen hat) und AVG.
- In Szenarien mit geringer Ähnlichkeit, in denen IPS aufgrund der Importance-Weighting-Problematik unter Varianzexplosion leidet, blieb MID stabil und übertraf sowohl IPS als auch AVG.
Verifizierung des Mechanismus: Streudiagramme der Schätzungen bestätigten, dass MID erfolgreich eine positive Korrelation zwischen den schrittweisen Schätzern induziert, was in einer engeren Verteilung der finalen Differenzschätzung im Vergleich zur kreisförmigen (unkorrelierten) Verteilung von AVG resultiert. Diese engere Streuung korreliert direkt mit einer Redukktion kritischer Selektionsfehler.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass der vorgeschlagene MID-Schätzer die Effizienz und Genauigkeit von A/B-Tests für die Algorithmenauswahl grundlegend verbessert. Indem er den statistischen Mechanismus der Offline-Evaluierung (gemeinsame Daten induzieren Korrelation) entlehnt und diesen über einen hypothetischen mittleren Algorithmus in das A/B-Testing-Framework integriert, überwindet MID die Grenzen sowohl des traditionellen A/B-Testings (hohe Varianz durch Unabhängigkeit) als auch der Offline-Evaluierung (Instabilität durch geringe Ähnlichkeit oder fehlende neue Daten).

Die Autoren betonen, dass dieser Ansatz es Organisationen ermöglicht, präzisere Entscheidungen bei der Algorithmenauswahl mit signifikant weniger Nutzern oder kürzeren Experimentdauern zu treffen, wodurch die mit Online-Experimenten verbundenen Kosten und Risiken reduziert werden. Die Arbeit legt nahe, dass der „Goldstandard“ des A/B-Testings nicht durch dessen Aufgabe, sondern durch die Verfeinerung der Schätzungstechniken verbessert werden kann, um statistische Korrelationen zu nutzen, die zuvor in Online-Settings ungenutzt blieben.