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

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Monte Carlo Methoden
    • Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation
    • Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen
    • Der mehrarmige Bandit (multi-armed bandit): Implementierung eines Simulations-Algorithmus in R

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.

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.

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 R_i den Gewinn beim i-ten Spiel beschreibt (R steht hier für reward), dann ist

R(N) = R₁ + R₂ + ... + R_N

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) = R₁ + R₂ + ... + R_t, 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:

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:

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:

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 μ₁, ..., μ_k annähern:

r(t) → μ_max für große t, mit μ_max = max(μ₁, ..., μ_k).

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

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 N_j (t), j = 1, ..., k, bezeichnet wird. Sie gibt an, wie oft der Bandit j bis zur Zeit t gespielt wurde.

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

r_j (t) = R_j (t) / N_j (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):

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 N_j (t) und r_j (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.

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.

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 r_j (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 r_j (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).

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 μ₅ = 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).

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 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 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 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 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 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 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).

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 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 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.

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.

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 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.

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.