Mehrarmiger Bandit

Was ist das Problem des Mehrarmigen Banditen?

Im Marketing ist eine Lösung mit mehrarmigen Banditen eine "intelligentere" oder komplexere Version von A/B-Testing, bei der Machine Learning Algorithmen eingesetzt werden, um den Traffic dynamisch den Varianten zuzuweisen, die gut abschneiden, während den Varianten, die weniger gut abschneiden, weniger Traffic zugewiesen wird.

Der Begriff "Mehrarmiger Bandit" stammt aus einem hypothetischen Experiment, bei dem eine Person zwischen mehreren Aktionen (d.h. Spielautomaten, den "einarmigen Banditen") wählen muss, wobei jede Aktion eine unbekannte Auszahlung hat. Das Ziel ist es, durch eine Reihe von Entscheidungen das beste oder profitabelste Ergebnis zu ermitteln. Zu Beginn des Experiments, wenn die Gewinnchancen und Auszahlungen noch unbekannt sind, muss der Spieler entscheiden, welchen Automaten er in welcher Reihenfolge und wie oft er zieht. Dies ist das "Problem des Mehrarmigen Banditen".

Beispiele für Mehrarmige Banditen

Ein praktisches Beispiel für ein Problem mit mehrarmigen Banditen ist eine Nachrichten-Website, die entscheiden muss, welche Artikel einem Besucher angezeigt werden sollen. Da es keine Informationen über den Besucher gibt, sind alle Klick-Ergebnisse unbekannt. Die erste Frage lautet: Welche Artikel werden die meisten Klicks erhalten? Und in welcher Reihenfolge sollen sie erscheinen? Das Ziel der Website ist es, das Engagement zu maximieren, aber sie hat viele Inhalte, aus denen sie auswählen kann, und es fehlen ihr Daten, die ihr helfen würden, eine bestimmte Strategie zu verfolgen.

Die Nachrichten-Website hat ein ähnliches Problem bei der Auswahl der Anzeigen, die ihren Besuchern angezeigt werden sollen. In diesem Fall möchten sie die Werbeeinnahmen maximieren, aber es fehlen ihnen möglicherweise genügend Informationen über die Besucher, um eine bestimmte Werbestrategie zu verfolgen. Ähnlich wie bei Nachrichtenartikeln haben sie in der Regel eine große Anzahl von Anzeigen, aus denen sie auswählen können. Welche Anzeigen bringen den größten Umsatz für ihre Site?

Die Website muss eine Reihe von Entscheidungen treffen, bei denen das Ergebnis und die "Auszahlung" jeweils unbekannt sind.

Mehrarmige Banditen-Lösungen

Es gibt viele verschiedene Lösungen, die Informatiker entwickelt haben, um das Problem des Mehrarmigen Banditen zu lösen. Im Folgenden finden Sie eine Liste der am häufigsten verwendeten Lösungen für Mehrarmige Banditen:

1. Epsilon-Greedy

   Dies ist ein Algorithmus, der einen ständigen Ausgleich zwischen Erkundung und Ausbeutung herstellt. (Bei 'gierigen' Experimenten wird immer der Hebel mit der höchsten bekannten Auszahlung gezogen, außer wenn eine zufällige Aktion durchgeführt wird). Ein zufällig ausgewählter Arm wird in einem Bruchteil der Zeit gezogen. In den übrigen 1-ε der Zeit wird der Arm mit der höchsten bekannten Auszahlung gezogen.

2. Obere Konfidenzgrenze

   Diese Strategie basiert auf dem Prinzip des Optimismus im Angesicht der Ungewissheit und geht davon aus, dass die unbekannten mittleren Auszahlungen jedes Arms so hoch wie möglich sind, basierend auf beobachtbaren Daten.

3. Thompson Stichprobenverfahren (Bayesianisch)

   Bei dieser Strategie des zufälligen Wahrscheinlichkeitsabgleichs sollte die Anzahl der Ziehungen für einen bestimmten Hebel mit seiner tatsächlichen Wahrscheinlichkeit übereinstimmen, der optimale Hebel zu sein.

Was ist ein kontextabhängiger Bandit?

In einem realen Szenario verfügen wir manchmal über Daten, die uns bei der Entscheidungsfindung helfen können, wenn wir zwischen den verschiedenen Aktionen in einer Situation mit einem Mehrarmigen Banditen wählen. Diese Informationen sind der "kontextuelle Bandit", also der Kontext und die Umgebung, in der das Experiment stattfindet.

Bei der Website-Optimierung sind kontextuelle Banditen auf eingehende Daten aus dem Benutzerkontext angewiesen, denn sie können dazu verwendet werden, bessere algorithmische Entscheidungen in Echtzeit zu treffen.

So können Sie beispielsweise einen kontextuellen Bandit verwenden, um einen Inhalt oder eine Anzeige auf Ihrer Website auszuwählen, um die Klickrate zu optimieren. Der Kontext ist jede historische oder aktuelle Information, die Sie über den Benutzer haben, wie z.B. zuvor besuchte Seiten, Informationen über frühere Käufe, Geräteinformationen oder Geolocation.

Wenn Sie ein Nachrichtenportal sind und wissen, dass eine Person, die auf Ihre Site kommt, in der Vergangenheit Unterhaltungsartikel gelesen hat, können Sie Ihren Top-Unterhaltungsartikel auswählen, der oben auf der Seite angezeigt werden soll, damit die Person ihn sieht. Wenn Sie sehen, dass sich Ihr Nutzer in Miami aufhält, können Sie das lokale Wetter oder andere relevante Informationen anzeigen.

Mehrarmige Banditen und A/B-Testing

Bei der Entscheidung, ob Sie mehrarmige Banditen anstelle von A/B-Testing einsetzen sollten, müssen Sie abwägen zwischen Ausbeutung und Erkundung (manchmal auch als "verdienen oder lernen" bekannt).

Beim A/B-Testing haben Sie eine begrenzte Zeit der reinen Erkundung, in der Sie den Datenverkehr zu gleichen Teilen auf Version A und Version B verteilen. Sobald Sie einen Gewinner ermittelt haben, gehen Sie zu einer langen Phase der Ausbeutung über, in der 100 % der Nutzer auf die Gewinner-Variante gehen. Ein Problem bei diesem Ansatz ist, dass Sie Ressourcen für die Verlierervariante verschwenden, während Sie versuchen, Daten zu sammeln und herauszufinden, wer der Gewinner ist.

Beim Mehrarmigen Bandit-Testing sind die Tests adaptiv und umfassen gleichzeitig Phasen der Erkundung und der Ausbeutung. Sie lenken den Verkehr allmählich zu den Gewinnervarianten, anstatt Sie zu zwingen, zu warten, bis am Ende eines Experiments ein Gewinner feststeht. Dieser Prozess ist schneller und effizienter, da weniger Zeit darauf verwendet wird, den Datenverkehr zu offensichtlich schlechteren Varianten zu leiten.

Einer der größten Nachteile des Mehrarmigen Bandit-Tests ist die Komplexität der Berechnungen. Einfach ausgedrückt: Es ist schwieriger und ressourcenintensiver, mehrarmige Bandit-Tests durchzuführen.

Es gibt einige bekannte Situationen, in denen mehrarmige Bandit-Tests am besten funktionieren:

1. Schlagzeilen und kurzfristige Kampagnen

   Die Opportunitätskosten für das Warten auf die Ergebnisse von A/B-Tests machen Bandit-Algorithmen zu einer besseren Wahl für kurzlebige Inhalte wie Überschriften-Testing für neue Artikel oder Urlaubsangebote.

2. Langfristige dynamische Änderungen

   Wenn sich der getestete Artikel so stark verändert, dass die Ergebnisse eines A/B-Tests im Laufe der Zeit ungültig werden, bieten mehrarmige Bandits eine Alternative zu wiederholten Tests, indem sie kontinuierlich erforscht werden.

3. Targeting

   Targeting ist ein weiteres Beispiel für einen langfristigen Einsatz von Bandit-Algorithmen. Wenn bestimmte Nutzertypen häufiger vorkommen als andere, kann der Mehrarmige Bandit gelernte Targeting-Regeln früher auf häufigere Nutzer anwenden, während er bei weniger häufigen Nutzern weiter experimentiert.

4. Automatisierung für Skalierung

   Wenn Sie mehrere Komponenten kontinuierlich optimieren müssen, bietet Ihnen der Ansatz des Mehrarmigen Banditen einen Rahmen zur teilweisen Automatisierung des Optimierungsprozesses für risikoarme Probleme, deren individuelle Analyse zu kostspielig sein kann.

Wie Optimizely mehrarmige Banditen einsetzt

Optimizely Web Experimentation und Optimizely Feature Experimentation verwenden einige mehrarmige Bandit-Algorithmen, um die Verteilung des Datenverkehrs 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 mehr Besuchern die Variation gezeigt wird, 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 damit verbringen, auf Ergebnisse zu warten.
  • Versucht, so viele signifikante Variationen wie möglich zu entdecken.

• Maximieren Sie die Belohnung und minimieren Sie das Bedauern - Mehrarmiger Bandit (MAB)

  • Ermöglicht es Ihnen, während des Lebenszyklus des Experiments so viel Wert aus der führenden Variation zu schöpfen wie möglich, so dass Sie die Kosten für die Darstellung suboptimaler Erlebnisse vermeiden.
  • Erzeugt keine statistische Signifikanz.
  • Verwendet den Thompson Sampling-Algorithmus für binäre Metriken.
  • Verwendet den Epsilon-Greedy-Algorithmus für numerische Metriken.