Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen

Um beim Spiel am mehrarmigen Banditen einen möglichst hohen Gewinn zu erzielen, benötigt man eine Strategie, die einen Kompromiss zwischen Exploration und Exploitation herstellt. Es werden einfache Algorithmen vorgestellt, die dieses Problem lösen und ihre Eigenschaften werden mit Hilfe von Simulationen untersucht.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

Die Vorbereitungen aus Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation werden hier als bekannt vorausgesetzt, um die Algorithmen und Simulationen diskutieren zu können.

An Mathematik wird wieder nur die Vertrautheit mit diskreten Zufallsvariablen vorausgesetzt.

EinfĂŒhrung

Im Kapitel Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation wurden sÀmtliche Vorbereitungen getroffen, um Algorithmen zu entwickeln, die versuchen am k-armigen Banditen bei N Spielen einen möglichst hohen Gewinn zu erzielen. Diese Vorbereitungen sind:

  • Es wurden die Zufallsvariablen festgelegt, die in den Simulationen die Gewinne der Banditen bestimmen.
  • Die Zufallsvariablen haben unterschiedliche Erwartungswerte; diese betragen 0.0, 0.2, ..., 1.8. Allgemein berechnet sich der Mittelwert des i-ten Banditen durch (i - 1) · 0.2, mit i = 1, 2, ..., 9.
  • Die Zufallsvariablen sind so skaliert, dass sie die Standardabweichung σ = 1 besitzen.
  • Es wurde ein GrundgerĂŒst fĂŒr einen derartigen Algorithmus vorgestellt; in Abbildung 1 wird versucht, dies graphisch darzustellen.

Abbildung 1: Bildliche Darstellung des Algorithmus zur Simulation von N Spielen an k Banditen. 1. Zuerst mĂŒssen Initialisierungen vorgenommen werden (Zufallsvariable fĂŒr die k Banditen; Datenelemente vorbereiten, die die Ergebnisse speichern). 2. Schleife ĂŒber die N Spiele: Bei jeder Iteration wird ein Bandit ausgewĂ€hlt (A), gespielt (B) und das Ergebnis abgespeichert (C). Je nach Auswahl-Kriterium fĂŒr den Banditen mĂŒssen weitere Datenelemente vorbereitet und gesetzt werden. 3. Nach Ende der Schleife werden die Ergebnisse ausgegeben.Abbildung 1: Bildliche Darstellung des Algorithmus zur Simulation von N Spielen an k Banditen. 1. Zuerst mĂŒssen Initialisierungen vorgenommen werden (Zufallsvariable fĂŒr die k Banditen; Datenelemente vorbereiten, die die Ergebnisse speichern). 2. Schleife ĂŒber die N Spiele: Bei jeder Iteration wird ein Bandit ausgewĂ€hlt (A), gespielt (B) und das Ergebnis abgespeichert (C). Je nach Auswahl-Kriterium fĂŒr den Banditen mĂŒssen weitere Datenelemente vorbereitet und gesetzt werden. 3. Nach Ende der Schleife werden die Ergebnisse ausgegeben.

Bei den Simulationen werden – sofern nichts anderes gesagt wird – folgende Rahmenbedingungen verwendet:

  1. Es gibt k = 9 Banditen (entsprechend Abbildung 5 in Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation).
  2. Es werden N = 2700 Spiele durchgefĂŒhrt.

Übersicht ĂŒber die Algorithmen

Die folgende Tabelle zeigt Algorithmen, die weiter unten beschrieben werden. Die Algorithmen werden zunÀchst nur umgangssprachlich beschrieben; eine Implementierung in der Sprache R erfolgt in einem weiteren Kapitel.

Algorithmus Kriterium fĂŒr die Auswahl des nĂ€chsten Banditen
random Der nÀchste Bandit wird immer zufÀllig ausgewÀhlt.
greedy Es wird derjenige Bandit ausgewÀhlt, der bisher den höchsten Gewinn pro Spiel geliefert hat.
Δ-first Zuerst wird bei einem Bruchteil Δ an Spielen der nÀchste Bandit zufÀllig ausgewÀhlt, danach wird der greedy-Algorithmus eingesetzt.
Δ-greedy Bei jeder Selektion wird eine Zufalls-Entscheidung getroffen: mit Wahrscheinlichkeit Δ wird der random-Algorithmus eingesetzt und mit Wahrscheinlichkeit 1 - Δ der greedy-Algorithmus.
Δ-decreasing Wie bei Δ-greedy wird eine Zufalls-Entscheidung getroffen, ob der random oder der greedy-Algorithmus eingesetzt wird; aber es wird eine Funktion vorgegeben, die den Verlauf der Wahrscheinlichkeit bestimmt.

Auswertung von Simulationen

Die Problemstellung

Es ist klar, dass die Algorithmen spÀter untereinander verglichen werden sollen, um herauszufinden, welcher Algorithmus dem Ziel, einen möglichst hohen Gewinn zu erzielen, besonders nahe kommt. Dazu muss man aber zuerst klÀren:

An welchen KenngrĂ¶ĂŸen lĂ€sst sich die QualitĂ€t eines Algorithmus ablesen?

Und:

Gibt es weitere GrĂ¶ĂŸen, die Aufschluss ĂŒber die Algorithmen liefern und die vielleicht zu einer Verbesserung der Algorithmen beitragen können?

Umgekehrt sollte auch klar sein: Diese Fragen sollte man so weit wie möglich vor der Implementierung der Algorithmen klÀren, damit man die entsprechenden Informationen wÀhrend des Ablaufs der N Spiele speichern kann, um sie spÀter geeignet aufzubereiten.

Die Auswertung von N Spielen

Im Folgenden werden diejenigen GrĂ¶ĂŸen beschrieben, die sich sofort aufdrĂ€ngen, wenn man die Simulationen vergleichen möchte – zuerst eine kurze Übersicht:

  1. Wie ist die zeitliche Abfolge der Auswahl des nÀchsten Banditen?
  2. Wie oft wird jeder der k Banditen bei den N Spielen ausgewÀhlt?
  3. Wie ist der zeitliche Verlauf des Gesamtgewinnes der N Spiele (also summiert ĂŒber alle Banditen)?
  4. Wie ist der zeitliche Verlauf dieses Gewinnes an den einzelnen Banditen?
  5. Wie ist der zeitliche Verlauf des Gesamtgewinns pro Spiel, wenn man ĂŒber alle Banditen summiert?
  6. Wie ist der zeitliche Verlauf des Gesamtgewinns pro Spiel, wenn man diese GrĂ¶ĂŸe fĂŒr jeden Einzelnen der k Banditen angibt?

Die ersten zwei GrĂ¶ĂŸen bedĂŒrfen keiner weiteren ErklĂ€rung, sie tragen aber nichts dazu bei, den Gewinn wĂ€hrend der Folge der N Spiele zu beschreiben. Dies geschieht mit Hilfe der anderen vier GrĂ¶ĂŸe, die kurz erklĂ€rt werden sollen.

Wenn Ri den Gewinn beim i-ten Spiel beschreibt (R steht hier fĂŒr reward), dann ist

R(N) = R1 + R2 + ... + RN

der Gesamtgewinn nach N Spielen. Summiert man nur bis zu einem t, das zwischen 1 und N liegt, erhÀlt man den Gesamtgewinn nach t Spielen:

R(t) = R1 + R2 + ... + Rt, t = 1, 2, ..., N.

Beispiel: Die Ergebnisse bei N = 10 Spielen an k = 2 Banditen

Die folgende Tabelle 1 zeigt die Einzelgewinne, die bei N = 10 Spielen an k = 2 Banditen erzielt wurden:

t 1 2 3 4 5 6 7 8 9 10
Bandit 1 -1 - 1 - - 1 -1 -1 - 1
Bandit 2 - 1 - -1 -1 - - - -1 -

Tabelle 1: Die Rohdaten fĂŒr N = 10 Spiele an k = 2 Banditen.

Man erkennt an Tabelle 1:

  1. Welcher Bandit wurde zu welcher Zeit t gespielt. (In jeder Spalte darf nur ein Eintrag stehen.)
  2. Welcher Gewinn (Verlust) wurde dabei erzielt. (Dass hier nur die Zahlen +1 und -1 vorkommen, hat keine spezielle Bedeutung: das Beispiel soll möglichst einfach sein.)
  3. Ob insgesamt ein Gewinn oder Verlust erzielt wurde, muss man mĂŒhsam durch Addition der Einzelgewinne berechnen.

Ob dabei eine bestimmte Strategie eingesetzt wurde, soll jetzt nicht diskutiert werden. ZunÀchst soll gezeigt werden, wie man diese Rohdaten weiterverarbeitet.

Zuvor noch kurz die ErklĂ€rung fĂŒr die Bezeichnung Rohdaten: Damit ist gemeint, dass man bei jedem Auszahlungsbetrag nachvollziehen kann, welcher der Banditen gespielt wurde und zu welchem Zeitpunkt t dies geschehen ist. SpĂ€ter werden dann Summen und Mittelwerte gebildet, wobei diese Informationen (teilweise) verloren gehen.

Den Gesamtgewinn nach t Spielen R(t) bildet man, indem man die AuszahlungsbetrÀge bis zu t addiert; das Ergebnis zeigt die folgende Tabelle 2:

t 1 2 3 4 5 6 7 8 9 10
R(t) -1 0 1 0 -1 0 -1 -2 -3 -2

Tabelle 2: Der Gesamtgewinn R(t) nach t Spielen. Nach N Spielen hat sich ein Verlust -2 ergeben.

Jetzt ist zwar die Information verloren gegangen, welcher Bandit wann gespielt wurde, aber man erkennt leichter den Fortschritt des Gewinns (verglichen mit der Tabelle der Rohdaten).

Möchte man die detailliertere Information erhalten, welcher Gesamtgewinn an welchem Banditen erzielt wurde, kann man die Summenbildung auch in den einzelnen Zeilen von Tabelle 1 vornehmen, es entsteht Tabelle 3:

t 1 2 3 4 5 6 7 8 9 10
Bandit 1: R1(t) -1 -1 0 0 0 1 0 -1 -1 0
Bandit 2: R2(t) 0 1 1 0 -1 -1 -1 -1 -2 -2

Tabelle 3: Der Gesamtgewinn aufgeschlĂŒsselt nach den einzelnen Banditen.

Man erkennt in Tabelle 3 zusÀtzlich zu Tabelle 2:

  1. An Bandit 1 wurde insgesamt weder ein Gewinn noch ein Verlust erzielt.
  2. Der Gesamtverlust von -2 nach N Spielen, resultiert allein aus den Spielen an Bandit 2.

Um die Ergebnisse verschiedener Simulationen besser untereinander zu vergleichen, die eventuell unterschiedliche N besitzen, bietet es sich an, die GrĂ¶ĂŸe R(t) durch die Anzahl der Spiele zu teilen: man erhĂ€lt den mittleren Gewinn pro Spiel r(t):

r(t) = R(t)/t, t = 1, 2, ..., N.

Wie in R(t) ist in der GrĂ¶ĂŸe r(t) nicht mehr erkennbar, welche Banditen im Lauf der Zeit gespielt wurden; dies ist nur bei speziellen Strategien der Fall. Spielt man zum Beispiel immer nur einen Banditen j, so sollte sich die GrĂ¶ĂŸe r(t) immer mehr dem Erwartungswert ÎŒj dieses Banditen annĂ€hern:

r(t) → ÎŒj fĂŒr große t.

Und hat man einen "sehr guten" Algorithmus, sollte sich r(t) dem grĂ¶ĂŸten der Erwartungswerte ÎŒ1, ..., ÎŒk annĂ€hern:

r(t) → ÎŒmax fĂŒr große t, mit ÎŒmax = max(ÎŒ1, ..., ÎŒk).

Tabelle 4 zeigt den zeitlichen Verlauf des mittleren Gewinns pro Spiel fĂŒr die Beispieldaten; zur besseren Nachvollziehbarkeit wird R(t) nochmals gezeigt:

t 1 2 3 4 5 6 7 8 9 10
R(t) -1 0 1 0 -1 0 -1 -2 -3 -2
r(t) -1 0 1/3 0 -1/5 0 -1/7 -1/4 -1/3 -1/5

Tabelle 4: Der zeitliche Verlauf des Gesamtgewinns R(t) und des Gesamtgewinns pro Spiel r(t).

Möchte man wieder das zeitliche Verhalten der einzelnen Banditen verfolgen, wird man die zu r(t) analogen GrĂ¶ĂŸen fĂŒr jeden einzelnen Banditen j, j = 1, ..., k, definieren: der mittlere Gewinn pro Spiel bezogen auf jeden Banditen 1, ..., k.

Allerdings ergibt sich jetzt ein Problem. Die Variable t besitzt in einer Gleichung wie r(t) = R(t)/t zwei unterschiedliche Bedeutungen:

  1. Die Variable t als Argument von R beschreibt den zeitlichen Verlauf wÀhrend der N Spiele, lÀuft also von 1 bis N.
  2. Die Variable t im Nenner von R(t)/t zĂ€hlt wie viele Spiele bis zur Zeit t durchgefĂŒhrt wurden; nur wenn man alle Spiele betrachtet, stimmt dies mit dem ersten t ĂŒberein.

Betrachtet man jetzt die Banditen einzeln, um einen mittleren Gewinn pro Spiel zu berechnen, muss man auch fĂŒr jeden Banditen einzeln zĂ€hlen, wie viele Spiele an ihm ausgefĂŒhrt wurden. Die zweite Bedeutung von t erfordert daher eine neue Variable, die mit Nj (t), j = 1, ..., k, bezeichnet wird. Sie gibt an, wie oft der Bandit j bis zur Zeit t gespielt wurde.

Und mit den Nj wird der mittlere Gewinn pro Spiel bezogen auf den Banditen j berechnet, er wird mit rj (t) bezeichnet:

rj (t) = Rj (t) / Nj (t), j = 1, ..., k.

Dabei darf natĂŒrlich nicht durch 0 dividiert werden. Dies wĂ€re der Fall, wenn ein Bandit noch nicht gespielt wurde; aber dann wird der mittlere Gewinn gleich 0 gesetzt.

Tabelle 5 zeigt fĂŒr die Beispieldaten diese neuen GrĂ¶ĂŸen (zusammen mit den Rohdaten, um die Werte leichter nachzuvollziehen):

t 1 2 3 4 5 6 7 8 9 10
Bandit 1 -1 - 1 - - 1 -1 -1 - 1
Bandit 2 - 1 - -1 -1 - - - -1 -
N1 (t) 1 1 2 2 2 3 4 5 5 6
N2 (t) 0 1 1 2 3 3 3 3 4 4
r1 (t) -1 -1 0 0 0 1/3 0 -0.2 -0.2 0
r2 (t) 0 1 1 0 -1/3 -1/3 -1/3 -1/3 -1/2 -1/2

Tabelle 5: ZusÀtzlich zu den bekannten Rohdaten wird die Anzahl der Spiele an den beiden Banditen und der jeweilige mittlere Gewinn pro Spiel gezeigt.

Man erkennt in Tabelle 5:

  1. Wird ein Bandit j nicht gespielt, bleiben Nj (t) und rj (t) konstant.
  2. Die GrĂ¶ĂŸen Ă€ndern sich nur, wenn der Bandit gespielt wird.
  3. Solange ein Bandit nicht gespielt wird, ist der mittlere Gewinn gleich 0.

In den folgenden Abschnitt werden Simulationen mit den oben kurz vorgestellten Strategien gezeigt und die hier eingefĂŒhrten und diskutierten GrĂ¶ĂŸen in Diagrammen dargestellt.

Algorithmus 1: zufÀllige Auswahl des Banditen (random)

Eigenschaften des Algorithmus

Um die Vorgehensweise bei der Simulation des Spiels zu demonstrieren, wird zunÀchst das einfachste Selektions-Kriterium verwendet: Der nÀchste Bandit wird immer zufÀllig aus allen k Banditen ausgewÀhlt.

Im Sinne des Dilemmas zwischen Exploration und Exploitation kann man dies auch so sehen: Die Banditen werden ausschließlich untersucht, indem man aus den Ergebnissen die Kennzahlen der Verteilungen berechnet (Exploration), dagegen wird kein Versuch unternommen, das gewonnene Wissen einzusetzen (keine Exploitation).

Ergebnisse von Simulationen

Einige der folgenden Abbildungen sind wenig informativ, sie werden aber auch fĂŒr andere Strategien eingesetzt und liefern dann im Vergleich untereinander wertvolle AufschlĂŒsse ĂŒber die Eigenschaften der angewendeten Strategien.

In Abbildung 2 ist die zeitliche Abfolge zu sehen, mit der die k Banditen ausgewÀhlt werden. Man erkennt,

  • dass die Auswahl völlig unregelmĂ€ĂŸig erfolgt und
  • jeder Bandit etwa gleich oft gespielt wird.

Abbildung 2: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten. Hier und in den weiteren Diagrammen sind die unterschiedlichen Banditen mit den Regenbogenfarben (von rot bis violett) gekennzeichnet.Abbildung 2: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten. Hier und in den weiteren Diagrammen sind die unterschiedlichen Banditen mit den Regenbogenfarben (von rot bis violett) gekennzeichnet.

In Abbildung 3 wird dargestellt, wie oft jeder Bandit gespielt wurde; die Anzahlen schwanken um den Erwartungswert 2700 / 9 = 300.

Abbildung 3: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.Abbildung 3: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.

In Abbildung 2 und 3 wurden noch keine Informationen dargestellt, ob die Spiele gewonnen oder verloren wurde beziehungsweise welcher Gewinn (oder Verlust) insgesamt erzielt wurde. Die beiden folgenden Abbildungen versuchen dies darzustellen.

Dazu wird in Abbildung 4 fĂŒr jeden Banditen separat der durchschnittliche Gewinn pro Spiel berechnet und im Verlauf der Zeit aufgetragen. Dazu muss nach jedem Spiel abgespeichert werden:

  • welcher Bandit wurde gespielt und
  • wie groß war der dabei erzielte Gewinn.

Man kann dann fĂŒr jeden Banditen zu jedem Zeitpunkt t die GrĂ¶ĂŸe:

(Summe der bisher erzielten Gewinne) / (Anzahl der bisher durchgefĂŒhrten Spiele)

bilden; dies wurde oben als rj (t), j = 1, ..., k, bezeichnet und ist in Abbildung 4 aufgetragen. Die unterschiedlichen Banditen sind wieder durch die Regenbogenfarben zu erkennen.

Damit das Diagramm aussagekrĂ€ftiger ist, sind zusĂ€tzlich die Erwartungswerte ÎŒj fĂŒr den Gewinn der 9 Banditen eingetragen (gestrichelte Linien). FĂŒr große t sollte sich der mittlere Gewinn pro Spiel rj (t) an ÎŒj annĂ€hern.

In Phasen, in denen ein Bandit nicht gespielt wird, bleibt die Kurve jeweils konstant.

Abbildung 4: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).Abbildung 4: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).

Man erkennt, dass

  • der mittlere Gewinn pro Spiel zu Beginn stark schwankt,
  • aber sich im Verlauf der Zeit immer mehr dem Erwartungswert annĂ€hert.

Ist man nur daran interessiert, ob eine Strategie einen möglichst großen Gewinn liefert, ist die AufschlĂŒsselung nach einzelnen Banditen nicht nötig; man trĂ€gt den Gesamtgewinn pro Spiel r(t) auf. Da hier alle Banditen etwa gleich oft gespielt werden, wird auf lange Sicht r(t) etwa so groß sein wie der Mittelwert aller ÎŒj, was hier mit dem Erwartungswert des 5. Banditen ÎŒ5 = 0.8 ĂŒbereinstimmt. In Abbildung 5 ist dies zu erkennen.

Abbildung 5: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).Abbildung 5: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).

Algorithmus 2: greedy-Algorithmus

Eigenschaften des Algorithmus

Bei zufĂ€lliger Auswahl des Banditen findet keine Exploitation statt sondern ausschließlich Exploration. Der greedy-Algorithmus ist das genaue Gegenteil (greedy = gierig): hier versucht man in jedem Schritt denjenigen Banditen zu wĂ€hlen, der den grĂ¶ĂŸten Gewinn verspricht. Lediglich zu Beginn werden einige Auswahlen per Zufall getroffen. Die Implementierung, mit der die unten gezeigten Simulationen erzeugt wurden, spielt zu Beginn jeden Banditen genau einmal und startet dann mit der Exploitation.

Realisiert wird der greedy-Algorithmus, indem man bei jeder Selektion die bisher erzielten Mittelwerte pro Spiel aller Banditen vergleicht und den besten Banditen auswÀhlt. Besitzen mehrere Banditen den maximalen Mittelwert, wird einer unter ihnen zufÀllig ausgewÀhlt.

Es sollte klar sein, worin der Nachteil dieses Vorgehens besteht: Sind die Ergebnisse des eigentlich besten Banditen bei den ersten Spielen eher schlecht, dauert es sehr lange bis dieser ausgewĂ€hlt werden kann; denn dazu mĂŒssen erst alle Mittelwerte der anderen Banditen unter dessen Mittelwert fallen. Was kurzfristig den höchsten Gewinn verspricht, kann somit langfristig dazu fĂŒhren, mögliche Gewinne zu verschenken.

Weiter unten werden dann Verbesserungen vorgestellt.

Ergebnisse von Simulationen

Wie beim random-Algorithmus werden 4 Abbildungen gezeigt:

  1. Zeitlicher Verlauf der Auswahl der Banditen.
  2. HĂ€ufigkeit der Auswahl der Banditen.
  3. Gesamtgewinn pro Spiel (je Bandit).
  4. Gesamtgewinn pro Spiel (summiert ĂŒber alle Banditen).

Abbildung 6: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.Abbildung 6: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.

Abbildung 7: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.Abbildung 7: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.

Abbildung 8: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).Abbildung 8: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).

Abbildung 9: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).Abbildung 9: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).

Die Abbildungen zeigen:

  1. Nach nur wenigen Spielen zur Exploration hat der 8. Bandit den höchsten Gewinn pro Spiel und wird ab dann immer gespielt.
  2. WÀhrend des weiteren Verlaufs fÀllt der Gewinn pro Spiel nicht unter die Werte der anderen Banditen, so dass diese nicht mehr ausgewÀhlt werden.
  3. Auf lange Sicht nÀhert sich der Gewinn pro Spiel damit dem Erwartungswert des 8. Banditen (also 1.4), womit aber Gewinne verschenkt werden (der 9. Bandit hat Erwartungswert 1.6).
  4. Obwohl Gewinne verschenkt werden, ist der Gewinn pro Spiel deutlich höher als bei der zufÀlligen Auswahl.

Algorithmus 3: Δ-first-Algorithmus

Eigenschaften des Algorithmus

Die beiden Algorithmen mit zufÀlliger Auswahl und der greedy-Algorithmus können leicht kombiniert werden: Dazu gibt man sich einen Bruchteil Δ vor und es werden

  • zuerst Δ · N Spiele mit zufĂ€lliger Auswahl gespielt,
  • anschießend (1 - Δ) · N Spiele mit dem greedy-Algorithmus.

Der Nachteil sollte auch klar sein: Es ist schwer anzugeben, wie groß Δ im Idealfall zu wĂ€hlen ist. In den GrenzfĂ€llen Δ = 0 und Δ = 1 erhĂ€lt man wieder die beiden Algorithmen mit rein zufĂ€lliger beziehungsweise gieriger Auswahl. Der Idealfall muss irgendwo dazwischen liegen; das "optimale" Δ, also das Δ, das mit höchster Wahrscheinlichkeit zu einem möglichst großen Gesamtgewinn fĂŒhrt, ist von mehreren GrĂ¶ĂŸen abhĂ€ngig:

  1. Von der Anzahl N der Spiele: je mehr Spiele durchgefĂŒhrt werden, umso kleiner kann der Anteil der Exploration sein, da man lediglich dafĂŒr sorgen muss, dass die SchĂ€tzwerte fĂŒr die Mittelwerte des Gewinns pro Bandit einigermaßen zuverlĂ€ssig sind.
  2. Von der Anzahl der Banditen: je mehr Banditen es gibt, umso lÀnger ist die Phase der Exploration.
  3. Von den Standardabweichungen der Zufallsvariablen der Banditen: Je grĂ¶ĂŸer sie sind, umso lĂ€nger mĂŒssen die Stichproben gewĂ€hlt werden um zuverlĂ€ssige SchĂ€tzungen fĂŒr die Mittelwerte zu erhalten. Zu Beginn sind die Standardabweichungen dem Spieler völlig unbekannt.
  4. Von den Ergebnissen der Spiele: Falls sehr untypische Ergebnisse bei den ersten Δ · N Spielen auftreten, soll heißen die SchĂ€tzungen fĂŒr die Mittelwerte weichen stark von den theoretischen Erwartungswerten ab, muss ebenfalls die Phase der Exploration lĂ€nger gewĂ€hlt werden.

Wegen diesen UnwÀgbarkeiten wird sich das optimale Δ leichter aus mehreren TestlÀufen ermitteln lassen als aus theoretischen ErwÀgungen.

Ergebnisse von Simulationen

Die folgende Simulation wurde mit Δ = 0.1 durchgefĂŒhrt und es werden wieder die 4 Abbildungen wie bei den anderen Algorithmen gezeigt.

Abbildung 10: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.Abbildung 10: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.

Abbildung 11: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.Abbildung 11: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.

Abbildung 12: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).Abbildung 12: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).

Abbildung 13: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).Abbildung 13: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).

Man erkennt:

  1. In der Phase der Exploration zeigt sich das selbe Verhalten wie beim random-Algorithmus.
  2. Nach der Exploration hat der 9. Bandit den höchsten Gewinn pro Spiel und wird weiter gespielt.
  3. Sein Gewinn pro Spiel fĂ€llt auch im Verlauf nicht mehr unter den Wert des zweitbesten Banditen zurĂŒck und daher wird der 9. Bandit bis zum Schluss immer ausgewĂ€hlt.
  4. Der Gesamtgewinn pro Spiel pendelt zu Beginn (in den ersten 270 Spielen) um den Erwartungswert des 5. Banditen, also 0.8, und steigt dann gegen den Erwartungswert des 9. Banditen, also 1.6.
  5. Allerdings ist die diese AnnĂ€herung sehr langsam, da in den ersten Δ · N Spielen sehr oft die ungĂŒnstigen Banditen gewĂ€hlt wurden.

Algorithmus 4: Δ-greedy-Algorithmus

Eigenschaften des Algorithmus

Eine andere Möglichkeit, den random-Algorithmus und den greedy-Algorithmus zu kombinieren, bietet der Δ-greedy-Algorithmus. Beim Δ-first-Algorithmus wurde die Phase der Exploration zu Beginn der Spiele gelegt. Beim Δ-greedy-Algorithmus wird bei jedem Spiel entschieden, ob der random-Algorithmus oder der greedy-Algorithmus eingesetzt wird. Der Parameter Δ gibt die Wahrscheinlichkeit an, mit der der random-Algorithmus gewÀhlt wird (entsprechend wird mit Wahrscheinlichkeit 1 - Δ der greedy-Algorithmus gewÀhlt).

Dies mag zunĂ€chst befremdlich klingen, da es doch klar ist, dass man zu Beginn die Banditen untersuchen muss und gegen Ende der N Spiele nur noch ein Wissen ausnutzen wird. Geht man aber davon aus, dass sich die Kennzahlen der Zufallsvariablen, die die Banditen beschreiben, im Lauf der Zeit verĂ€ndern können, wird der Δ-greedy-Algorithmus dem Δ-first-Algorithmus ĂŒberlegen sein, da Letzterer nur schwer seine Auswahl anpassen wird (wie man an der letzten Simulation gesehen hat.)

Probleme, bei denen sich die Zufallsvariablen im Lauf der Zeit verĂ€ndern können, werden als nicht-stationĂ€re Probleme bezeichnet. Die Zufallsvariablen hier wurden als stationĂ€r vorgegeben, aber der Spieler hat diese Information natĂŒrlich nicht.

Ergebnisse von Simulationen

Die folgende Simulation wurde mit Δ = 0.1 durchgefĂŒhrt und es werden wieder die 4 Abbildungen wie bei den anderen Algorithmen gezeigt.

Abbildung 14: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.Abbildung 14: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.

Abbildung 15: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.Abbildung 15: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.

Abbildung 16: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).Abbildung 16: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).

Abbildung 17: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).Abbildung 17: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).

Man erkennt:

Hier ist folgender Effekt deutlich zu sehen: zu Beginn tÀuschen die Ergebnisse vor, dass Bandit 7 der beste Bandit ist und daher wird er sehr hÀufig gewÀhlt. Erst spÀter hat der 9. Bandit den höheren Gewinn pro Spiel. Aber dadurch dauert es wieder sehr lange bis der Erwartungswert des 9. Bandit angenÀhert wird.

Algorithmus 5: Δ-decreasing-Algorithmus

Eigenschaften des Algorithmus

Man kann jetzt einen Algorithmus entwickeln, der versucht den Δ-first- und den Δ-greedy-Algorithmus miteinander zu kombinieren. Dazu ist in Abbildung 18 gezeigt, wie man den Selektionsmechanismus der beiden Algorithmen besser verstehen kann:

Beim Δ-first-Algorithmus wird entweder der random-Algorithmus oder der greedy-Algorithmus gewĂ€hlt, und zwar nach folgender Regel: Ist t < Δ · N, wird der random-Algorithmus gewĂ€hlt, andernfalls der greedy-Algorithmus. Dies kann man sich durch die Funktion f(t) ausdrĂŒcken (in Abbildung 18 oben); die FlĂ€che unter der Funktion ist gleich der Wahrscheinlichkeit Δ.

Entsprechend wird die Auswahl des random-Algorithmus bei Δ-greedy durch die Funktion f(t) in Abbildung 18 mitte bestimmt.

Der Nachteil des Δ-first-Algorithmus ist, dass nach der Exploration die Wahl des besten Banditen nur noch schwer korrigiert werden kann, wenn die Ergebnisse in dieser Phase untypisch waren. Der Nachteil des Δ-greedy-Algorithmus ist, dass die Exploration bis zum Ende der N Spiele stattfindet, obwohl es so spÀt eigentlich unsinnig ist.

Daher kann man eine monoton fallende Funktion definieren (Abbildung 18 unten), die die Wahrscheinlichkeit fĂŒr die Wahl des random-Algorithmus bestimmt; die FlĂ€che unter der Kurve ist wieder gleich Δ, das heißt insgesamt wird mit Wahrscheinlichkeit Δ der random-Algorithmus gespielt. Man könnte hier natĂŒrlich jede andere monoton fallende Funktion einsetzen; die Gerade wurde gewĂ€hlt, da sie sich leicht implementieren lĂ€sst.

Abbildung 18: Darstellung der Funktionen, die die Wahrscheinlichkeit bestimmen, welche Strategie ausgewÀhlt wird (random oder greedy).Abbildung 18: Darstellung der Funktionen, die die Wahrscheinlichkeit bestimmen, welche Strategie ausgewÀhlt wird (random oder greedy).

Ergebnisse von Simulationen

Die folgende Simulation wurde wieder mit Δ = 0.1 durchgefĂŒhrt und es werden die 4 bekannten Abbildungen gezeigt.

Abbildung 19: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.Abbildung 19: Zeitlicher Verlauf der Auswahl des jeweiligen Banditen aus den k = 9 Möglichkeiten.

Abbildung 20: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.Abbildung 20: Das Histogramm zeigt, wie oft jeder der k = 9 Banditen ausgewÀhlt wurde.

Abbildung 21: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).Abbildung 21: Der Gesamtgewinn pro Spiel im Verlauf der Zeit, aufgeschlĂŒsselt nach den 9 Banditen (in Regenbogenfarben) sowie zum Vergleich die Erwartungswerte fĂŒr die einzelnen Banditen (gestrichelt).

Abbildung 22: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).Abbildung 22: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. ZusĂ€tzlich eingetragen sind der höchste Erwartungswert der 9 Banditen (rot) und der zu erwartende Wert, wenn alle Banditen gleich oft gespielt werden (grĂŒn) sowie der kleinste Erwartungswert der 9 Banditen (schwarz).

Vergleich der Strategien

In der folgenden Simulation werden die drei Strategien

  • Δ-first,
  • Δ-greedy und
  • Δ-decreasing

miteinander verglichen. Dazu werden mit jeder Strategie 30 Simulationen durchgefĂŒhrt, bei denen immer k = 9 und N = 2700 gesetzt wird. In Abbildung 23 wird dann der mittlere Gewinn pro Spiel (gemittelt ĂŒber alle Banditen) aufgetragen und den Strategien zugeordnet. ZusĂ€tzlich eingetragen sind die Erwartungswerte des besten und zweitbesten Banditen (1.6 und 1.4 als gestrichelte schwarze Linien).

Abbildung 23: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen bei jeweils 30 Simulationen mit den oben genannten drei Strategien. Genauere ErklĂ€rung im Text.Abbildung 23: Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen bei jeweils 30 Simulationen mit den oben genannten drei Strategien. Genauere ErklĂ€rung im Text.

Man kann aus dem Diagramm ablesen:

  • Die Messpunkte unterhalb der Linie zum Erwartungswert 1.4 kommen dadurch zustande, dass in der Phase der Exploration die Ergebnisse fĂŒr den besten Banditen untypisch ausfallen und sich daher der Mittelwert dem Erwartungswert des zweitbesten Banditen annĂ€hert. Dieser Effekt tritt bei Δ-decreasing am seltensten ein.
  • Die Streuung der Ergebnisse kommt vor allem durch diesen Effekt zustande; wenn er nicht eintritt, liegen die Messpunkte fĂŒr alle Strategien Ă€hnlich nahe beieinander.
  • Die Mittelwerte der drei Strategien sind nur wenig unterschiedlich, wobei Δ-greedy leicht gegenĂŒber den anderen Strategien zurĂŒckfĂ€llt.
  • Damit die Unterschiede zwischen den Strategien deutlicher werden – sofern sie ĂŒberhaupt bestehen –, mĂŒsste man N noch grĂ¶ĂŸer wĂ€hlen und noch mehr Simulationen durchfĂŒhren.

Die folgende Tabelle zeigt die Mittelwerte und Standardabweichungen.

Strategie Δ-first Δ-greedy Δ-decreasing
Mittelwert 1.506 1.480 1.508
Standardabweichung 0.063 0.047 0.035

Tabelle 6: Mittelwerte und Standardabweichungen zu den Messpunkten aus Abbildung 23.

Variation von Δ

Bisher wurde bei allen Simulationen Δ = 0.1 gesetzt und nicht hinterfragt, wie man gerade auf diesen Wert kommt oder wie man Δ wĂ€hlen soll. Aus der Diskussion des Dilemmas zwischen Exploration und Exploitation ist zwar klar geworden, dass man Δ nicht zu klein und nicht zu groß wĂ€hlen darf, aber bisher hat sich noch kein Hinweis ergeben, welcher Wert den optimalen Kompromiss zwischen Exploration und Exploitation herstellt.

Die folgenden Simulationen sollen diese Frage beleuchten – werden aber auch keine eindeutige Antwort liefern.

Untersucht werden wieder die drei Strategien

  • Δ-first,
  • Δ-greedy und
  • Δ-decreasing.

Die Simulationen werden wieder mit k = 9 und N = 2700 durchgefĂŒhrt. Um einen Eindruck zu bekommen, wie groß die Streuungen sind, wird jede Simulation mit identischen Parametern dreimal wiederholt. Variiert wird die Wahrscheinlichkeit Δ: sie lĂ€uft von 0.005 bis 0.20 und wird in Schritten von 0.005 erhöht. FĂŒr jede der drei Strategien wird ein Diagramm erzeugt.

Abbildung 24: Strategie Δ-first. Aufgetragen ist der Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. Zu jedem Wert von Δ werden 3 Simulationen durchgefĂŒhrt.Abbildung 24: Strategie Δ-first. Aufgetragen ist der Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. Zu jedem Wert von Δ werden 3 Simulationen durchgefĂŒhrt.

Abbildung 25: Strategie Δ-greedy. Aufgetragen ist der Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. Zu jedem Wert von Δ werden 3 Simulationen durchgefĂŒhrt.Abbildung 25: Strategie Δ-greedy. Aufgetragen ist der Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. Zu jedem Wert von Δ werden 3 Simulationen durchgefĂŒhrt.

Abbildung 26: Strategie Δ-decreasing. Aufgetragen ist der Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. Zu jedem Wert von Δ werden 3 Simulationen durchgefĂŒhrt.Abbildung 26: Strategie Δ-decreasing. Aufgetragen ist der Gesamtgewinn pro Spiel gemittelt ĂŒber alle Banditen. Zu jedem Wert von Δ werden 3 Simulationen durchgefĂŒhrt.

Vergleicht man die drei Abbildungen, stellt man fest:

  • Es gibt wieder viele Messpunkte, bei denen der zweitbeste oder sogar der drittbeste Bandit sehr hĂ€ufig gespielt wird.
  • FĂŒr diesen Effekt sind die Strategien Δ-first und Δ-greedy besonders anfĂ€llig, bei Δ-decreasing tritt er deutlich seltener ein.
  • Und dieser Effekt tritt vor allem bei kleinen Werten von Δ auf.
  • Ohne diesen Effekt könnte man in allen drei Diagrammen eine eindeutig abfallende Kurve erkennen, was dafĂŒr sprechen wĂŒrde, einen möglichst kleinen Wert von Δ als optimal anzusehen.

Zusammenfassung und Ausblick

Der random-Algorithmus und der greedy-Algorithmus sind fĂŒr sich genommen wenig geeignet, um bei N Spielen mit hoher Wahrscheinlichkeit einen Gewinn pro Spiel zu erzielen, der nahe beim Erwartungswert des besten Banditen liegt. Sie beschreiben eben die reine Exploration beziehungsweise Exploitation.

Diese beiden Strategien lassen sich leicht miteinander kombinieren, so dass ein Kompromiss zwischen Exploration und Exploitation erzielt wird. Dieser wurde mit den drei Algorithmen Δ-first, Δ-greedy und Δ-decreasing erreicht.

Der Nachteil dieser Algorithmen soll aber auch genannt werden: Es ergibt sich nicht sofort aus der Problemstellung (also mit der Angabe von k und N), wie groß Δ gewĂ€hlt werden soll, damit die Algorithmen optimale Ergebnisse liefern. Es bieten sich drei Möglichkeiten an, wie man diesen Nachteil beseitigen kann:

  1. Man macht sehr viele Computerexperimente mit verschiedenen Werten von Δ, um herauszufinden welcher Wert optimal ist. Dies ist sehr aufwendig und man erkennt aus den Abbildungen 24 bis 26: Selbst wenn die Simulationen vorliegen, ist es immer noch nicht leicht, ein optimales Δ anzugeben. Weiter muss man bei einer VerÀnderung von k oder N wieder von Neuem beginnen, da sich die Ergebnisse nur schwer extrapolieren lassen.
  2. Man kann versuchen, durch theoretische AbschĂ€tzungen herauszufinden, wie groß Δ in etwa gewĂ€hlt werden muss. Auch dies ist sehr aufwendig, da Δ nicht nur von k und N abhĂ€ngt, sondern auch von den Ergebnissen der Spiele (bei untypischen Ergebnissen wird man mehr Exploration benötigen). Das heißt aber man kann bestenfalls ĂŒber alle möglichen Ergebnisse mitteln und das Δ bestimmen, das im Durchschnitt den höchsten Gewinn verspricht.
  3. Da die ersten beiden Wege nicht sehr vielversprechend sind, kann man einen völlig anderen Ansatz wĂ€hlen: Die bisherigen Algorithmen besitzen einen Parameter Δ, den man erst aufwendig bestimmen muss. Warum entwickelt man nicht einen Algorithmus, der Δ nicht voraussetzt, sondern den optimale Wert (oder zumindest eine gute NĂ€herung) selbst herausfindet? Das soll heißen, dass der Algorithmus den Kompromiss zwischen Exploration und Exploitation selber im Lauf der Spiele ermitteln soll.

Der letzte Ansatz wird in einem weiteren Kapitel verfolgt.