Übersicht

Anhang (Multi-Armed-Bandit-Experiment)

Rechnerische und theoretische Details

Beachten Sie zunächst, dass der Name "Multi-Armed-Bandit-Experiment" ein Problem beschreibt, für das mehrere Lösungen verfügbar sind. In Büchern zu "Bestärkendem Lernen" finden Sie in der Einführung zu "Multi-Armed-Bandit-Experimenten" mehrere Ansätze. Die angewendete Mathematik hinter dem Multi-Armed-Bandit-Experiment ist so komplex, dass in der Praxis heuristische Lösungsverfahren verwendet werden. Ein Zitat von Peter Whittle (Whittle, 1979) fasst die mathematischen Probleme anschaulich zusammen:

[Das Multi-Armed-Bandit-Problem] wurde während des [Zweiten Welt]kriegs ausformuliert. Die Anstrengungen, dieses Problem zu lösen, zehrte so sehr an den alliierten Analysten, dass vorgeschlagen wurde, das Problem als ultimatives Instrument der intellektuellen Sabotage über Deutschland "auszuschütten".

Wir verwenden die als "Thompson Sampling" oder "Wahrscheinlichkeitsverteilung mit Zufallsgröße" bekannte Heuristik, da diese viele Vorteile dieser Heuristiken vereint. Weitere Informationen zu diesem Verfahren erhalten Sie in [5]. Ausführliche Informationen zu den mathematischen Fragestellungen erhalten Sie in [2], [3] und [4].

Wahrscheinlichkeit für optimale Variante

Mit dem Thompson Sampling werden Besuche zu Varianten zugewiesen im Verhältnis zur Wahrscheinlichkeit, dass jede Variante optimal ist. Dies ist eine Bayessche Berechnung. Es bezeichne θ = (θ1, θ2,..., θk) den Vektor von Conversion-Rates für die Varianten 1, …, k. Es bezeichne zudem y die bisher beobachteten Daten des Tests. y wird als ein Vektor von unabhängigen Binomialverteilungen modelliert. Dabei werden unabhängige nicht-informative A-priori-Verteilungen auf θ angenommen. Es bezeichne Ia(θ) den Indikator des Falls, dass Variante a optimal ist. Daraus ergibt sich folgende Formel:

P(Ia) = ∫Ia(θ) p(θ|y) dθ

Dieses Integral kann geschlossen gelöst werden, obwohl die geschlossene Lösung komplexe spezielle Funktionen (z. B. die unvollständige Betafunktion) enthält, oder durch numerische Integration. In beiden Fällen wird die Berechnung schnell instabil, auch für relativ kleine Werte von y. Die Wahrscheinlichkeiten für optimale Varianten können Sie jedoch stabil mithilfe von Simulationen berechnen. Jedes Element von θ ist eine unabhängige Zufallsvariable aus der Betaverteilung. Simulieren Sie eine große Matrix mit Stichproben von θ aus den relevanten Betaverteilungen, wobei die Zeilen der Matrix zufällige Stichproben repräsentieren und die Spalten die k Varianten des Tests. In einer Monte-Carlo-Simulation ist die Wahrscheinlichkeit, dass Variante a optimal ist, der empirische Teil der Zeilen, für die Variante a den größten simulierten Wert hatte. Die Wahrscheinlichkeit, dass jede Variante das Original übertrifft, kann ähnlich berechnet werden.

Verbleibender Wert

Mit der Simulation, die die Wahrscheinlichkeiten für die optimale Variante berechnet, kann ebenfalls die Verteilung des verbleibenden Werts im Test ermittelt werden. Der verbleibende Wert ist die A-posteriori-Wahrscheinlichkeit von (θmax-θ*)/θ*, wobei θmax der größte Wert von θ ist und θ* der Wert von θ für die Variante ist, die wahrscheinlich die optimale Variante ist. Um die Berechnung zu veranschaulichen, wird angenommen, dass drei Varianten mit 20, 30 und 40 Besuchen 12, 20 und 30 Conversions generiert haben. Die Wahrscheinlichkeiten für die optimale Variante belaufen sich auf ungefähr 0,09, 0,20 und 0,71. Die ersten sechs Stichproben der Monte-Carlo-Simulation von θ können also wie folgt lauten:

[,1] [,2] [,3]
[1,] 0,54 0,73 0,74
[2,] 0,55 0,66 0,73
[3,] 0,53 0,81 0,80
4. 0,57 0,50 0,65
5. 0,52 0,67 0,83
[6,] 0,65 0,84 0,63

Die Berechnung des Werts erfolgt Zeile für Zeile. Dabei wird das größte Element dieser Zeile vom Element in Spalte 3 subtrahiert (weil für Variante 3 die größte Wahrscheinlichkeit vorliegt, dass dies die optimale Variante ist). In den ersten beiden Zeilen lautet der Wert Null, da die größte Stichprobe in Spalte 3 vorhanden ist. In der dritten Zeile lautet der Wert 0,01/0,80, da Spalte 2 um 0,01 größer ist als Spalte 3. Wenn dieser Vorgang für jede Zeile durchgeführt wird, ergibt dies eine Werteverteilung, die in einem Histogramm wie dem linken Bereich in Abbildung A1 dargestellt werden kann. Variante 3 verfügt über eine Wahrscheinlichkeit von 71 %, die beste Variante zu sein. Deshalb lautet der Wert für einen Wechsel weg von Variante 3 in 71 % der Fälle null. Das 95. Perzentil der Werteverteilung ist der "potenziell verbleibende Wert" im Test. In diesem Fall beläuft sich dieser Wert auf ungefähr 0,16. Sie können diesen Wert wie folgt auslegen: Wir sind noch unsicher, was die Conversion-Rate für Variante 3 angeht, aber unabhängig davon, wie hoch die Conversion-Rate für diese Variante ist, besteht eine Wahrscheinlichkeit von 16 %, dass eine der anderen Varianten eine bessere Leistung erzielt.

Im rechten Bereich in Abbildung A1 wird gezeigt, wie sich die Verteilung des verbleibenden Werts im Verlauf des Tests entwickelt. Angenommen, jede Variante verfügt über die fünffache Stichprobengröße (also 100, 150 und 200 Besuche) mit der fünffachen Anzahl von Conversions (60, 100, 150). Größere Stichprobengrößen liefern genauere Ergebnisse in Bezug auf die Conversion-Rates der Varianten. Die Wahrscheinlichkeit, dass Variante 3 die optimale Variante ist, liegt jetzt bei 95 %. Das 95. Perzentil der Verteilung des verbleibenden Werts lautet also null.

Abbildung A1. Die Verteilung des verbleibenden Werts in einem Test. Die vertikale Linie für jeden Fall ist das 95. Perzentil oder der potenziell verbleibende Wert.
War dieser Artikel hilfreich?
Wie können wir die Seite verbessern?