Übersicht

Multi-Armed-Bandit-Experimente

Von Steven L. Scott, PhD, Sr. Economic Analyst

Dieser Artikel beschreibt das Statistikmodul, auf dem die Analytics Content-Tests basieren. Für die Verwaltung von Online-Tests wird in Analytics der Ansatz von "Multi-Armed-Bandit-Experimenten" angewendet. Ein Multi-Armed-Bandit-Experiment ist ein Test, bei dem Folgendes zutrifft:

  • Ziel ist es, die beste oder profitabelste Aktion zu ermitteln.
  • Im Verlauf des Tests kann die willkürliche Verteilung aktualisiert werden.

Der Name Multi-Armed-Bandit-Experiment (zu deutsch "Spielautomatentest") beschreibt einen hypothetischen Test, in dem mehrere "einarmige Banditen" (Spielautomaten) mit unterschiedlichen Auszahlungsmethoden analysiert werden. Sie möchten den Spielautomaten ermitteln, der über die beste Auszahlungsrate verfügt und gleichzeitig Ihre Gewinne maximieren. You want to find the slot machine with the best payout rate, but you also want to maximize your winnings. Dabei werden zum einen Automaten berücksichtigt, die in der Vergangenheit hohe Gewinne erbracht haben und zum anderen neue oder scheinbar schlechtere Automaten, die möglicherweise noch bessere Gewinne erbringen könnten. Für das Multi-Armed-Bandit-Experiment werden komplexe Wahrscheinlichkeitsrechnungen durchgeführt, die ebenfalls in Analytics Content-Tests verwendet werden.

Zunächst erhalten Sie einige allgemeine Hintergrundinformationen zum Einsatz des Multi-Armed-Bandit-Experiments in Analytics. Danach werden anhand von zwei Beispielen simulierte Tests beschrieben, die mit dem Algorithmus des Multi-Armed-Bandit-Experiments durchgeführt werden. Es folgen Antworten auf häufig gestellte Fragen und schließlich ein Anhang mit technischen und theoretischen D details.

Hintergrund

Funktionsweise von Multi-Armed-Bandit-Experimenten

Zweimal täglich sehen wir uns Ihren Test an, um herauszufinden, welche Leistung jede der Varianten erzielt hat. Dann passen wir den Teil der Zugriffe an, der jeder Variante im weiteren Verlauf zugewiesen wird. Einer Variante mit offensichtlich guter Leistung werden mehr Zugriffe zugewiesen, einer Variante mit deutlich geringerer Leistung weniger. Die von uns vorgenommenen Anpassungen basieren auf einer statistischen Formel (weitere Informationen hierzu erhalten Sie im Anhang), die sowohl den Stichprobenumfang als auch die Leistungsmesswerte berücksichtigt. So können wir Anpassungen vornehmen, die auf den tatsächlichen Leistungen basieren und nehmen nicht willkürlich Änderungen vor. Im Laufe des Tests erhalten wir immer mehr Informationen zu den relativen Leistungen und können so besser die leistungsstarken Varianten ermitteln.

Vorteile

Tests, die auf Multi-Armed-Bandit-Experimenten basieren, sind im allgemeinen effizienter als "klassische" A-B-Tests, die auf statistischen Hypothesentests basieren. Die statistischen Ergebnisse von Multi-Armed-Bandit-Experimenten sind genauso aussagekräftig wie Ergebnisse von Hypothesentests. Häufig können mit Multi-Armed-Bandit-Experimenten jedoch schneller Lösungsansätze ermittelt werden. Die Tests sind effizienter, da sie die Zugriffe schrittweise in Richtung der gewinnbringenden Varianten verschieben. Sie müssen nicht auf eine "endgültige Antwort" am Ende eines Tests warten. Multi-Armed-Bandit-Experimente können schneller durchgeführt werden, da die Stichproben, die zu offensichtlich schlechteren Varianten geführt hätten, den potenziell leistungsstärkeren zugewiesen werden können. Die zusätzlichen Daten zu den leistungsstarken Varianten können dabei helfen, die guten Varianten schneller von den besten zu trennen.

Mit Multi-Armed-Bandit-Experimenten können Sie dadurch effizientere und auch eine größere Anzahl an Tests durchführen. Zudem können Sie Ihren Tests einen größeren Teil Ihrer Zugriffe zuweisen, da die Zugriffe automatisch auf Seiten mit höherer Leistung geleitet werden.

Beispiele

Einfacher A-B-Test

Angenommen, die Conversion-Rate für Ihre Website beträgt 4 %. Sie führen einen Test mit einer neuen Version der Website durch, die im Testzeitraum eine Conversion-Rate von 5 % erzielt. Die tatsächlichen Conversion-Rates sind jedoch nicht bekannt; deshalb führen Sie den Test durch. Angenommen, Sie möchten den Test so durchführen, dass eine statistisch signifikante Conversion-Rate von 5 % mit einer Wahrscheinlichkeit von 95 % ermittelt wird. Es wird eine standardmäßige Berechnung der Teststärke1 (Powerrechnung) durchgeführt, die ergibt, dass 22.330 Beobachtungen (11.165 für jede Variante) erforderlich sind, damit eine Wahrscheinlichkeit von 95 % vorliegt, um eine Verschiebung der Conversion-Rate von 4 % auf 5 % zu ermitteln. Angenommen, Sie erzielen während des Tests 100 Besuche pro Tag. Der Test dauert in diesem Fall 223 Tage. Bei einem Standardtest warten Sie also 223 Tage, führen den Hypothesentest durch und erhalten dann Ihre Ergebnisse.

Analysieren Sie die 100 Besuche pro Tag jetzt mit dem Multi-Armed-Bandit-Experiment. Am ersten Tag werden jeder Variante ungefähr 50 Besuche zugewiesen. Die Ergebnisse werden dann analysiert. Mithilfe des Bayestheorem wird die Wahrscheinlichkeit berechnet, dass die Variante bessere Leistungen erzielt als das Original2. Eins abzüglich dieser Zahl ist die Wahrscheinlichkeit, dass das Original bessere Leistungen erzielt. Angenommen, das Original hat am ersten Tag sehr gute Leistungen erzielt. Dadurch ergibt sich eine Wahrscheinlichkeit von 70 %, dass das Original eine leistungsstarke Variante ist. In diesem Fall wird dem Original am zweiten Tag 70 % des Traffics zugewiesen und die Variante erhält 30 %. Am Ende des zweiten Tages werden die an beiden Tagen erzielten Zugriffe akkumuliert. Die Wahrscheinlichkeit, welche Variante am besten ist, wird neu berechnet. So erhalten wir die grundlegenden Zahlen für den dritten Tag. Dieser Prozess wird so lange wiederholt, bis ein Satz von Stoppregeln ermittelt wurde. Weitere Informationen zu Stoppregeln erhalten Sie weiter unten.

Abbildung 1 zeigt eine Simulation des Tests für diese Einrichtung. Es werden Werte für das Original (schwarze Linie) und für die Variante (rote gepunktete Linie) angezeigt. Beide Linien schwanken, bis die Variante schließlich die Schwelle von 95 % Wahrscheinlichkeit erreicht. Die beiden Prozentzahlen müssen zusammen 100 % ergeben. Steigt also der Wert für die eine Linie, wird er für die andere reduziert. Der Test ist nach 66 Tagen abgeschlossen, also 157 Tage schneller als ein Standardtest.

AbbildungFigure 1. Simulation eines einfachen Multi-Armed-Bandit-Experiments mit zwei Varianten zur Ermittlung der Wahrscheinlichkeit für die optimale Variante. Diese Zahlen geben den Teil des Traffics an, der jeder Variante pro Tag zugewiesen wurde.

Dies ist lediglich ein Beispiel. Wir haben die Simulation 500 Mal durchgeführt, um die Leistung der Varianten wiederholt zu prüfen. Die Verteilung der Ergebnisse wird in Abbildung 2 gezeigt. Im Schnitt war der Test 175 Tage früher beendet als der klassische Test, der auf der Powerrechnung basiert. Die durchschnittlichen Einsparungen betragen 97,5 Conversions.

Abbildung 2. Die Verteilungen des eingesparten Zeitraums und die Anzahl der eingesparten Conversions im Vergleich zu einem klassischen Test, bei dem eine Powerrechnung durchgeführt wurde. Angenommen wird ein Original mit einer Conversion-Rate von 4 % und eine Variante mit einer Conversion-Rate von 5 %.

Und was ist mit der statistischen Validität? Erhöht sich bei der Berücksichtigung von weniger Daten nicht die Fehlerrate? Tut sie nicht. Von den 500 oben gezeigten Tests wurde in 482 Tests die korrekte Variante ermittelt. Das sind 96,4 %. Es liegt also ungefähr die gleiche Fehlerrate vor wie beim klassischen Test. In einigen wenigen Tests dauerte die Durchführung der Rechnung länger als von der Poweranalyse angegeben. Dies galt aber nur für ungefähr 1 % der Fälle (5 von 500).

Wir haben auch die Gegenprobe durchgeführt, also einen Test, bei dem das Original eine Erfolgsrate von 5 % aufwies und die Variante eine Erfolgsrate von 4 %. Die Ergebnisse waren im Wesentlichen symmetrisch. Auch hier wurde mit dem Multi-Armed-Bandit-Experiment die korrekte Variante in 482 von 500 Tests ermittelt. Die durchschnittlich eingesparte Zeit im Vergleich zu einem klassischen Test betrug 171,8 Tage und die durchschnittlich eingesparte Anzahl an Conversions 98,7.

Test stoppen

Standardmäßig läuft das Multi-Armed-Bandit-Experiment mindestens zwei Wochen. Danach werden zwei Messwerte erfasst.

Der erste Wert ist die Wahrscheinlichkeit, dass jede Variante das Original übertrifft. Wenn eine Wahrscheinlichkeit von 95 % vorliegt, dass eine Variante besser ist als das Original, wird in Analytics eine Meldung ausgegeben, dass ein Gewinner ermittelt wurde. Sie können sowohl die Mindestdauer von zwei Wochen als auch die Wahrscheinlichkeit von 95 % anpassen.

Der zweite von uns erfasste Messwert ist der "potenziell im Test verbleibende Wert". Dieser ist insbesondere bei Tests mit mehreren Varianten nützlich. Zu jedem Zeitpunkt während des Tests gibt es eine Gewinnervariante, die als die beste Variante gilt. Wenn der Test "jetzt" enden würde, wäre der Gewinner die Variante, die Sie wählen würden. Der im Test "verbleibende Wert" ist der Steigerungswert der Conversion-Rate, die Sie erreichen könnten, wenn Sie eine andere Variante als die Gewinnervariante wählen. Sinn und Zweck eines Tests ist die Ermittlung dieses Wertes. Wenn Sie zu 100 % sicher sind, dass der Gewinner die beste Variante ist, gibt es keinen im Test verbleibenden Wert und ein Test würde keine neuen Erkenntnisse bringen. Wenn Sie jedoch nur zu 70 % sicher sind, dass eine bestimmte Variante optimal ist, besteht eine Wahrscheinlichkeit von 30 %, dass eine andere Variante besser ist. Mithilfe des Bayestheorems können wir die Verteilung ermitteln, um wie viel besser eine andere Variante ist. Im Anhang finden Sie rechnerische Details hierzu.

In Analytics wird der Test beendet, wenn eine Wahrscheinlichkeit von mindestens 95 % vorliegt, dass der im Test verbleibende Wert weniger als 1 % der Conversion-Rate des Gewinners beträgt. Es handelt sich hierbei um eine Verbesserung um 1 %, nicht um eine Verbesserung um einen Prozentpunkt. Wenn also die beste Variante über eine Conversion-Rate von 4 % verfügt, wird der Test beendet, vorausgesetzt, der im Test verbleibende Wert beträgt weniger als 0,04 Prozentpunkte der Conversion-Rate.

Das Beenden eines Tests basierend auf dem potenziell verbleibenden Wert hat Vorteile, da auch gleichwertige Varianten abgedeckt werden. Beispiel: Ein Test mit vielen Varianten kann ergeben, dass mehrere Varianten die gleiche Leistung aufweisen. In diesem Fall ist es unerheblich, welche Variante eingesetzt wird. Der Test muss nicht weiter durchgeführt werden, da mehrere optimale Varianten vorliegen. Der Test muss also nur so lange durchgeführt werden, bis sichergestellt ist, dass ein Variantenwechsel keine großen Auswirkungen hat.

Komplexe Tests

Die Vorteile von Multi-Armed-Bandit-Experimenten im Gegensatz zu klassischen Tests zahlen sich verstärkt bei komplexen Tests aus. Wahrscheinlich haben Sie mehrere Ideen, wie Sie Ihre Webseite verbessern könnten. Also möchten Sie auch mehrere Varianten testen. Angenommen, Sie haben neben dem Original über fünf weitere Varianten erstellt. Sie führen eine Berechnung durch, mit der Sie das Original mit der größten Variante vergleichen. Aus diesem Grund muss eine Anpassung vorgenommen werden, um die Alphafehler-Kumulierung zu berücksichtigen. Eine einfache, wenn auch konservative, Anpassung können Sie mit der Bonferroni-Korrektur vornehmen. Sie können diese implementieren, indem Sie das Signifikanzniveau des Hypothesentests durch die Anzahl der Varianten teilen. Es wird also eine standardmäßige Powerrechnung mit einem Signifikanzniveau von 0,05 / (6 - 1) durchgeführt. Für jede Variante des Tests sind 15.307 Beobachtungen erforderlich. Bei sechs Varianten ergibt dies eine Gesamtsumme von 91.842 Beobachtungen. Bei 100 Besuchen pro Tag müsste der Test 919 Tage, also über 2,5 Jahre lang, laufen. In der Praxis macht die Durchführung eines Tests mit so langer Dauer keinen Sinn. Wir führen anhand dieses Beispiels trotzdem eine Simulation durch.

Jetzt führen wir ein Multi-Armed-Bandit-Experiment mit sechs Varianten durch. Auch hier wird angenommen, dass die Originalvariante über eine Conversion-Rate von 4 % verfügt und die optimale Variante über eine Conversion-Rate von 5 %. Zu den weiteren vier Varianten gehört eine suboptimale Variante, die das Original übertrifft und eine Conversion-Rate von 4,5 % aufweist. Des Weiteren gibt es drei schwächere Varianten mit Conversion-Rates von 3 %, 2 % und 3,5 %. Abbildung 3 zeigt die Verteilung der Ergebnisse. Die durchschnittliche Dauer des Tests beträgt 88 Tage, im Gegensatz zu 919 Tagen bei einem klassischen Test, und die durchschnittliche Anzahl der eingesparten Conversions beträgt 1.173. Die Verteilung der Dauer von Tests ist ein kontroverses Thema. Tests enden nicht immer schnell, aber selbst in den schlimmsten Fällen spart das Multi-Armed-Bandit-Experiment über 800 Conversions im Gegensatz zum klassischen Test.

Abbildung 3. Einsparungen durch ein Multi-Armed-Bandit-Experiment mit sechs Varianten im Verhältnis zu einer Powerrechnung mit Bonferroni-Korrektur für einen klassischen Test. Die linke Seite zeigt die Anzahl der erforderlichen Tage, um den Test zu beenden. Die vertikale Linie zeigt die Zeit an, die für eine klassische Powerrechnung erforderlich ist. Die rechte Seite zeigt die Anzahl an Conversions, die durch das Multi-Armed-Bandit-Experiment eingespart wurde.

Die Kosteneinsparungen sind zum Teil darauf zurückzuführen, dass der Test schneller endet und zum Teil darauf, dass während der Laufzeit des Tests weniger Kosten anfallen. Abbildung 4 zeigt den Verlauf der Leistung für alle Varianten im ersten der 500 Simulationsläufe. Es kann zunächst etwas verwirrend sein, wenn Varianten mit guter und schlechter Leistung durch das Multi-Armed-Bandit-Experiment aussortiert werden. Die Varianten mit schlechter Leistung werden jedoch sehr schnell abgewertet. In diesem Fall erzielt das Original zu Beginn des Tests gute Ergebnisse und bleibt deshalb länger im Rennen als einige der anderen Varianten. Nach ungefähr 50 Tagen kristallisiert sich ein Kopf-an-Kopf-Rennen zwischen dem Original und dem letztendlichen Gewinner heraus. Nachdem die anderen Varianten effektiv ausgeschlossen wurden, werden die 100 Beobachtungen pro Tag auf das Original und den letztendlichen Gewinner aufgeteilt. Das Multi-Armed-Bandit-Experiment ermöglicht eine effektive Zuordnung der Beobachtungen. Wirtschaftlich gesehen werden die Varianten berücksichtigt, die einen guten ROI erzielen. Statistisch gesehen werden die Varianten berücksichtigt, über die Sie die meisten Informationen abrufen möchten.

Abbildung 4. Verlauf der erzielten Leistungen für eine Variante des Multi-Armed-Bandit-Experiments mit sechs Varianten

Abbildung 5 zeigt die täglich anfallenden Kosten bei einem Multi-Armed-Bandit-Experiment im Vergleich zu einer "Orakel"-Strategie, bei der Variante 2 immer als optimale Variante berücksichtigt wird.shows the daily cost of running the multi-armed bandit relative to an "oracle" strategy of always playing arm 2, the optimal arm. Dies ist natürlich nicht gerechtfertigt, da ja tatsächlich nicht bekannt ist, welche Variante die beste ist, als Ausgangspunkt ist diese Vorgehensweise jedoch nützlich. Im Schnitt kostet jede Beobachtung, die dem Original zugewiesen wird, 0,01 einer Conversion, da die Conversion-Rate für das Original um 0,01 kleiner ist als die von Variante 2. Analog kostet jede Beobachtung, die z. B. Variante 5 zugewiesen wurde 0,03 Conversions, da die Conversion-Rate um 0,03 kleiner ist als die von Variante 2. Die Kosten für den jeweiligen Tag des laufenden Tests berechnen sich wie folgt: Zunächst wird die Anzahl der Beobachtungen, die jeder Variante zugewiesen wurden mit den Kosten für jede Variante multipliziert. Danach wird die Summe der Kosten für alle Varianten ermittelt, dies ergibt dann die Kosten für den jeweiligen Tag des laufenden Tests. Im klassischen Test werden jeder Variante 100 / 6 Besuche pro Tag zugewiesen (im Durchschnitt, abhängig davon, wie Teilbeobachtungen zugewiesen werden). Für den klassischen Test ergibt dies Kosten von 1,333 Conversions pro Tag den der Test läuft. Die rote Linie in Abbildung 5 zeigt die Kosten, die für die Ausführung des Multi-Armed-Bandit-Experiments pro Tag anfallen. Im Verlauf des Tests reduzieren sich die Kosten, da Varianten mit geringer Leistung weniger Beobachtungen zugewiesen bekommen.

Abbildung 5. Kosten pro Tag des laufenden Multi-Armed-Bandit-Experiments. Die konstanten Kosten pro Tag für die Ausführung eines klassischen Tests werden durch die horizontale gestrichelte Linie angezeigt.

1Alle Powerrechnungen in diesem Artikel wurden mit der R-Funktion power.prop.test durchgeführt.

2Weitere Informationen zu den Details der Berechnung erhalten Sie im Anhang. Diese Informationen

War das hilfreich?
Wie können wir die Seite verbessern?