Mehrarmiger Bandit

Was ist das Mehrarmige Banditen-Problem?

In der Marketingsprache ist eine Mehrarmige Banditen-Lösung eine „intelligentere“ oder komplexere Version des A/B-Testings, die Algorithmen des maschinellen Lernens verwendet, um dynamisch Webtraffic jenen Variationen zuleiten, die gute Leistung zeigen, während Variationen mit schlechterer Leistung weniger Traffic erhalten. Theoretisch sollten Mehrarmige Banditen schneller Ergebnisse liefern, weil es nicht erforderlich ist, auf eine einzelne Sieger-Variation zu warten.

Der Begriff „Mehrarmiger Bandit“ rührt von einem hypothetischen Experiment her, in dem eine Person zwischen mehreren Aktionen wählen muss, z. B. Münzspielautomaten, den „Einarmigen Banditen“, jeder mit unbekannter Auszahlung. Das Ziel ist, das beste oder profitabelste Ergebnis im Verlauf einer Reihe von Wahlmöglichkeiten zu bestimmen. Am Anfang des Experiments, wenn Wahrscheinlichkeiten und Belohnungen unbekannt sind, muss der Spieler bestimmten, welche Hebel er zieht, in welcher Reihenfolge und wie oft. Dies ist das „Mehrarmige Banditen-Problem“.

Mehrarmige Banditen-Beispiele

Ein Beispiel für ein Mehrarmiges Banditen-Problem aus der Realität ist eine News-Website, die eine Entscheidung treffen muss, welcher Artikel einem Besucher angezeigt werden soll. Ohne Informationen über den Besucher sind alle Klick-Resultate unbekannt. Die erste Frage ist, welcher der Artikel bekommt die meisten Klicks? Und in welcher Reihenfolge sollten sie erscheinen? Das Ziel der Website ist, das Engagement zu maximieren, aber es sind viele Content-Bausteine vorhanden, unter denen ausgewählt werden muss und es fehlt an Daten, die dabei helfen würden eine spezifische Strategie zu verfolgen.

Die News-Website hat ein ähnliches Problem bei der Auswahl der dem Besucher anzuzeigenden Anzeigen. In diesem Fall sollen die Anzeigeneinnahmen maximiert werden, aber es könnte an genügend Informationen über den Besucher mangeln, um eine spezifische Anzeigenstrategie zu verfolgen. Ähnlich zum Problem der News-Artikel liegt eine große Anzahl von Anzeigen vor, aus denen zu wählen ist. Welche Anzeigen werden das maximale Einkommen für die News-Website erzeugen?

Die Website muss eine Reihe von Entscheidungen treffen, jede einzelne mit unbekanntem Ergebnis und unterschiedlicher „Belohnung“.

Mehrarmige Banditen-Lösungen

Es gibt viele unterschiedliche Lösungen, die Computerforscher entwickelt haben, um das Mehrarmige Banditen-Problem zu bewältigen. Nachfolgend sind einige der am häufigsten verwendeten Mehrarmige Banditen-Lösungen aufgeführt:

Epsilon-Greedy Dies ist ein Algorithmus, der fortwährend zwischen Erkundung und Verwertung ausbalanciert. (Bei ‘greedy’-Experimenten wird immer der Hebel mit der höchsten bekannten Belohnung gezogen, außer wenn eine zufällige Aktion durchgeführt wird). Mit einem zeitlichen Anteil ε wird ein zufällig gewählter Arm gezogen. Die restliche Zeit 1-ε wird der Arm mit der höchsten bekannten Belohnung gezogen.

Oberes Konfidenzniveau Diese Strategie basiert auf Optimismus angesichts des Unsicherheitsprinzips und nimmt an, dass die unbekannten mittleren Belohnungen jedes Arms, basierend auf beobachtbaren Daten, so hoch wie möglich sein werden.

Thompson-Probe (Bayesianisch)

Mit dieser randomisierten Wahrscheinlichkeitsanpassungsstrategie sollte die Anzahl, wie oft ein bestimmter Hebel gezogen wird, der tatsächlichen Wahrscheinlichkeit entsprechen, dass dieser der optimale Hebel ist.

Was ist ein kontextabhängiger Bandit?

In einem realen Szenario liegen manchmal Daten vor, die beim Treffen informierter Entscheidungen bei der Auswahl zwischen unterschiedlichen Aktionen eines Mehrarmige Bandit-Situation helfen können. Diese Information ist der „kontextabhängige Bandit“, mit Kontext und Umgebung, innerhalb derer das Experiment stattfindet.

Bei Website-Optimierung verlässt sich ein kontextabhängiger Bandit auf eintreffende Nutzerkontextdaten, denn diese können verwendet werden, um in Echtzeit bessere algorithmische Entscheidungen zu treffen.

Beispielsweise können Sie einen kontextabhängigen Banditen zur Auswahl eines Content-Bausteins oder einer auf der Website anzuzeigenden Anzeige nutzen, um nach Durchklickrate oder Click-Through Rate zu optimieren. Der Kontext ist jede historische oder aktuelle Information, die Sie über den Nutzer haben, wie zuvor besuchte Seiten, Informationen zu letzten Einkäufen, Geräteinformationen oder Geostandort.

Wenn Sie ein News-Portal sind und wissen, dass eine zu Ihrer Website kommende Person in der Vergangenheit Entertainment-Artikel gelesen hat, können Sie Ihren besten Entertainment-Artikel auswählen und diesen für den Besucher oben auf der Seite anzeigen. Wenn Sie sehen, dass ein Nutzer in Miami ist, können Sie das örtliche Wetter oder andere relevante Informationen anzeigen.

Mehrarmige Banditen & A/B-Testing

Für die Entscheidung, ob Mehrarmige Banditen anstelle von A/B-Testing verwendet werden, müssen Sie den Kompromiss zwischen Verwertung und Erkundung (manchmal als „earn or learn“ bezeichnet) abwägen.

Mit A/B-Testing haben Sie eine begrenzte Zeit reiner Erkundung, bei der Sie Traffic gleichmäßig auf Version A und Version B aufteilen. Nachdem Sie einen Gewinner ermittelt haben, wechseln Sie zu einer langen Phase der Verwertung, in der 100 % der Nutzer zur Sieger-Variation geschickt werden. Ein Problem bei diesem Ansatz ist, dass Sie Ressourcen auf die nicht siegreiche Variation verschwenden, während Sie Daten zu sammeln und zu ermitteln versuchen, wer der Gewinner ist.

Mit Mehrarmige Banditen-Testing sind die Tests adaptiv und beinhalten gleichzeitig Perioden der Erkundung und der Verwertung. Traffic wird dort stufenweise zu den Sieger-Varianten verschoben, statt Sie warten zu lassen, bis Sie einen Sieger am Ende des Experiments verkünden. Dieser Prozess ist schneller und effizienter, weil Traffic weniger lang an offensichtlich unterlegene Variationen gesandt wird.

Einer der Hauptnachteile des Mehrarmigen Banditen-Testings ist die Berechnungskomplexität. Einfach gesagt ist es schlicht schwieriger und braucht mehr Ressourcen, einen Mehrarmigen Banditen-Test durchzuführen.

Es gibt einige bekannte Situationen, in denen Mehrarmige Bandit-Testing typischerweise am besten funktioniert:

Überschriften und Kurzzeit-Kampagnen

Die Alternativkosten für das Warten auf das Ergebnis eines A/B-Tests machen Banditen-Algorithmen zur besseren Wahl für kurzlebige Content-Bausteine wie Überschriften-Tests für neue Artikel oder Urlaubswerbung.

Langfristig dynamische Änderungen

Wenn das getestete Element signifikanten starken Änderungen unterliegt, die einen A/B-Test mit der Zeit annullieren, bietet Mehrarmige Banditen durch fortgesetzte Exploration eine Alternative zum wiederholten Testen.

Targeting

Targeting (also Zielen auf etwas) ist ein weiteres Beispiel einer langfristigen Nutzung von Banditen-Algorithmen. Wenn bestimmte Arten von Nutzern häufiger als andere sind, kann der Mehrarmige Bandit erlerntes Targeting früher für häufigere Nutzer anwenden, während das Experiment bei weniger häufigen Nutzern weitergeht.

Automatisierung für Skalierung

Wenn Sie mehrere Komponenten haben, die kontinuierlich optimiert werden sollen, liefert der Mehrarmige Banditen-Ansatz Ihnen einen Rahmen zur teilweisen Automatisierung des Optimierungsprozesses für Probleme mit niedrigem Risiko, für die eine individuelle Analyse zu teuer sein kann.

Wie Optimizely Mehrarmige Banditen verwendet

Optimizely verwendet einige mehrarmige Banditen-Algorithmen, um die Verkehrsaufteilung in den verschiedenen Varianten intelligent zu ändern, um ein Ziel zu erreichen. Abhängig von Ihrem Ziel wählen Sie zwischen den Zielen:

• So schnell wie möglich statistisch signifikante Variationen finden – Stats Accelerator
  • Verkürzt die Dauer des Experiments, indem es mehr Besuchern die Variante zeigt, die eine bessere Chance hat, statistische Signifikanz zu erreichen..
  • Maximiert die Anzahl der Erkenntnisse aus Experimenten in einem bestimmten Zeitrahmen, so dass Sie weniger Zeit mit dem Warten auf Ergebnisse verbringen.
  • Versucht, so viele signifikante Variationen wie möglich zu entdecken.
• Maximierung der Belohnung und Minimierung des Bedauerns – Multi-armed Bandit (MAB)
  • Ermöglicht es Ihnen, so viel Wert wie möglich aus der führenden Variation während des Lebenszyklus des Experiments zu schöpfen, so dass Sie die Kosten für die Darstellung suboptimaler Erfahrungen vermeiden.
  • Erzeugt keine statistische Signifikanz.
  • Verwendet den Thompson Sampling Algorithmus für binäre Metriken.
  • Verwendet den Epsilon-Greedy-Algorithmus für numerische Metriken.