Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation

Beim mehrarmigen Banditen oder genauer k-armigen Banditen kann man ein GlĂŒcksspiel durch BetĂ€tigen eines Armes auslösen. Mathematisch modelliert werden sie durch Zufallsvariablen mit unterschiedlichen Erwartungswerten. Möchte man am k-armigen Banditen N Spiele durchfĂŒhren und dabei einen möglichst hohen Gewinn erzielen, gerĂ€t man in ein Dilemma: Einerseits muss man alle Arme untersuchen, um ihre Kennzahlen zu schĂ€tzen (Exploration), andererseits möchte man möglichst oft den besten Arm betĂ€tigen (Exploitation). Im nĂ€chsten Kapitel werden dann Algorithmen entwickelt, die versuchen einen Kompromiss zwischen Exploration und Exploitation herzustellen.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

Im nÀchsten Kapitel werden Algorithmen vorgestellt, die einen Kompromiss zwischen Exploration und Exploitation herstellen. Ihre Eigenschaften werden mit Hilfe von Simulationen untersucht.

An mathematischen Voraussetzungen ist hier lediglich der Umgang mit diskreten Zufallsvariablen erforderlich.

EinfĂŒhrung

Mit einem einarmigen Bandit wird hier ein GlĂŒcksspielautomat bezeichnet, bei dem man pro Spiel einen gewissen Einsatz bezahlen muss und mit – unbekannten – Wahrscheinlichkeiten ebenso unbekannte Gewinne erzielen kann. Durch BetĂ€tigen des Armes startet man das Spiel.

Als mehrarmiger Bandit oder genauer k-armiger Bandit wird die Variante des einarmigen Banditen bezeichnet, die k Arme besitzt und die man nacheinander betĂ€tigen kann. Da im Folgenden angenommen wird, dass die von unterschiedlichen Armen ausgelösten Spiele jeweils unabhĂ€ngig voneinander sind, kann man den k-armigen Banditen durch k einarmige Banditen ersetzen. Wichtg ist aber, dass jeder dieser k Banditen unterschiedliche Wahrscheinlichkeiten fĂŒr ihre auszuzahlenden Gewinne besitzen kann. Ebenso können sich die AuszahlungsbetrĂ€ge unterscheiden. Wie ein k-armiger Bandit genau modelliert wird, wird weiter unten beschrieben.

In der Literatur wird der mehrarmige Bandit ĂŒblicherweise so beschrieben, dass jeweils eine Aktion an einem der Arme ausgefĂŒhrt wird. Um die UnabhĂ€ngigkeit der Arme zu betonen, wird im Folgenden der k-armige Bandit durch k einarmige Banditen ersetzt – ansonsten verbirgt sich keine Besonderheit hinter der Verwendung von k Banditen.

Dieses Kapitel soll zuerst die Mathematik zur Modellierung eines k-armigen Banditen erklĂ€ren und die Begriffe Exploration und Exploitation einfĂŒhren. Im nĂ€chsten Kapitel werden dann Algorithmen zu folgender Fragestellung untersucht: Nach welcher Strategie soll man den nĂ€chsten zu spielenden Banditen auswĂ€hlen, wenn man insgesamt N Spiele durchfĂŒhren wird und natĂŒrlich einen möglichst hohen Gewinn erzielen möchte (oder zumindest einen möglichst niedrigen Verlust).

Es soll dabei nicht die optimale Strategie entwickelt werden, sondern vielmehr einige Anregungen gegeben werden, wie man bei der Entwicklung derartiger Strategien vorgehen kann. Die Ergebnisse dieser Untersuchungen werden in einem weiteren Kapitel ĂŒber den Monte-Carlo-Tree-Search-Algorithmus verwendet. Es wird dann ein Algorithmus entwickelt, der zum Beispiel eingesetzt werden kann, um bei einem Spiel den nĂ€chsten Zug auszuwĂ€hlen, indem Gewinn-Wahrscheinlichkeiten fĂŒr alle erlaubten ZĂŒge geschĂ€tzt werden.

Der mehrarmige Bandit (multi-armed bandit)

Eigenschaften des mehrarmigen Banditen

In Abbildung 1 sind die k einarmigen Banditen dargestellt. Charakterisiert wird jeder Bandit durch eine Zufallsvariable, die angibt, mit welcher Wahrscheinlichkeit ein gewisser Gewinn (oder Verlust) eintreten kann.

Abbildung 1: Der k-armige Bandit wird durch k einarmige Banditen ersetzt, um ihre UnabhĂ€ngigkeit zu betonen. Jeder dieser k einarmigen Banditen wird durch eine Zufallsvariable beschrieben. Sie gibt an, mit welcher Wahrscheinlichkeit ein Gewinn oder Verlust (der Einsatz wird einbehalten) eintritt. Die möglichen Werte der Zufallsvariablen und die Wahrscheinlichkeiten, mit denen ihre Werte eintreten, sind dem Spieler zunĂ€chst nicht bekannt. Durch zahlreiche Spiele kann er immer bessere SchĂ€tzungen fĂŒr sie abgeben. Dass die Zufallsvariablen jeweils drei Werte annehmen ist hier willkĂŒrlich angenommen und ohne Bedeutung.Abbildung 1: Der k-armige Bandit wird durch k einarmige Banditen ersetzt, um ihre UnabhĂ€ngigkeit zu betonen. Jeder dieser k einarmigen Banditen wird durch eine Zufallsvariable beschrieben. Sie gibt an, mit welcher Wahrscheinlichkeit ein Gewinn oder Verlust (der Einsatz wird einbehalten) eintritt. Die möglichen Werte der Zufallsvariablen und die Wahrscheinlichkeiten, mit denen ihre Werte eintreten, sind dem Spieler zunĂ€chst nicht bekannt. Durch zahlreiche Spiele kann er immer bessere SchĂ€tzungen fĂŒr sie abgeben. Dass die Zufallsvariablen jeweils drei Werte annehmen ist hier willkĂŒrlich angenommen und ohne Bedeutung.

FĂŒr die Banditen werden folgende Annahmen gemacht, die sich in den Eigenschaften der Zufallsvariablen X1, X2, ..., Xk wiederspiegeln:

  • UnabhĂ€ngigkeit: Die Ergebnisse, die ein Bandit liefert, ist jeweils unabhĂ€ngig von den Ergebnissen der anderen Banditen.
  • StationaritĂ€t: Die Zufallsvariablen X1, X2, ..., Xk verĂ€ndern sich im Lauf der Zeit nicht.
  • Unterschiedliche Erwartungswerte: Die Erwartungswerte ÎŒ1, ÎŒ2, ..., ÎŒk der Zufallsvariablen X1, X2, ..., Xk können unterschiedlich sein.
  • Gleiche Standardabweichungen: Wie spĂ€ter klar wird, vereinfachen sich die Berechnungen deutlich, wenn man annimmt, dass alle k Zufallsvariablen eine identische Standardabweichung σ besitzen.

Aus den spĂ€teren Diskussionen wird sich ergeben, dass es unerheblich ist, ob alle Zufallsvariablen gleichzeitig um einen konstanten Betrag b verschoben werden; es spielt daher keinen Rolle, ob die Zufallsvariablen X1, X2, ..., Xk den Nettogewinn des Spiels oder den pro Spiel ausbezahlten Betrag beschreiben – man muss nur fĂŒr alle Zufallsvariablen dieselbe Konvention anwenden. Im Folgenden wird daher stets die Sprechweise verwendet, dass die Zufallsvariablen X1, X2, ..., Xk den Gewinn fĂŒr den Banditen i = 1, 2, ..., k beschreiben und es wird offen gelassen, ob der Nettogewinn oder der Auszahlungsbetrag gemeint ist. Da fĂŒr den Erwartungswert einer Zufallsvariable X bei Verschiebung um b gilt:

E(X + b) = E(X) + b,

kann man nachtrÀglich jederzeit vom Nettogewinn auf den Auszahlungsbetrag oder umgekehrt umrechnen.

Warum es so wichtig ist, dass die Standardabweichungen der Zufallsvariablen identisch sind, ist jetzt noch schwer zu begrĂŒnden, aber es lĂ€sst sich bereits andeuten: Je grĂ¶ĂŸer die Standardabweichung fĂŒr eine Zufallsvariable Xi ist, um so mehr Spiele muss man mit dem entsprechenden Banditen ausfĂŒhren, um SchĂ€tzungen fĂŒr seine Kennzahlen abzugeben. Die Berechnungen sind leichter, wenn sich hier alle Banditen gleich verhalten; wie sich unterschiedliche Standardabweichungen auf die zu entwickelnden Algorithmen auswirkt, kann man sich am Ende ĂŒberlegen.

Die Problemstellung

FĂŒr einen Spieler am mehrarmigen Banditen sind die oben beschriebenen Zufallsvariablen, sprich welche Werte sie annehmen und wie groß die entsprechenden Wahrscheinlichkeiten sind, natĂŒrlich nicht bekannt. WĂŒrde er sie kennen, so kann er seinen Gewinn dadurch maximieren, indem er immer den Banditen mit dem grĂ¶ĂŸten Erwartungswert

Όmax = max(Ό1, Ό2, ..., Όk)

spielt; dies setzt natĂŒrlich voraus, dass der mit ÎŒmax verbundene Nettogewinn positiv ist.

Kennt man den Eigenschaften der Zufallsvariablen X1, X2, ..., Xk nicht, ergibt sich fĂŒr einen GlĂŒcksspieler sofort eine Fragestellung:

Wie muss man vorgehen, wenn man

  • insgesamt N Spiele bestreiten möchte und
  • dabei einen möglichst großen Gewinn erzielen möchte?

Im nÀchsten Kapitel werden einige Algorithmen entwickelt, die versuchen dieses Problem zu lösen. ZusÀtzlich werden Simulationen gezeigt, aus denen sich einige Eigenschaften dieser Algorithmen ablesen lassen. In diesem Kapitel werden die nötigen Vorbereitungen getroffen.

Das Dilemma Exploration versus Exploitation

Wenn man die Banditen nicht nur zufÀllig durchprobiert, sondern versucht planvoll vorzugehen, ergibt sich ein Dilemma:

  • Einerseits muss man alle Banditen mehrfach spielen, um die Kennzahlen der Zufallsvariablen herauszufinden (exploration).
  • Andererseits möchte man möglichst oft den besten Banditen spielen (exploitation).

Verwendet man zu viele Spiele dafĂŒr, die Banditen zu untersuchen, wird man auch sehr oft Banditen mit den kleineren Erwartungswerten spielen und insgesamt einen sehr kleinen Gewinn erzielen. Entscheidet man sich umgekehrt schon nach wenigen Spielen fĂŒr den bis dahin besten Banditen, so lĂ€uft man ebenfalls Gefahr, zu oft einen Banditen mit kleinem Erwartungswert zu spielen, da man bei einer kleinen StichprobenlĂ€nge die Kennzahlen der Zufallsvariablen nur unzureichend kennt.

Ein zentraler Bestandteil eines Algorithmus zur Vorgehensweise beim mehrarmigen Banditen ist es daher, einen Kompromiss zu finden zwischen der Untersuchung der Banditen (exploration) und dem Spielen des (bis dahin) besten Banditen (exploitation).

Mögliche Anwendungen

Das oben vorgestellte Problem, Algorithmen zu entwickeln, die das Dilemma zwischen Exploration und Exploitation auflösen, wirkt zunĂ€chst sehr speziell und scheint auf GlĂŒcksspiele beschrĂ€nkt zu sein. Man kann sich aber leicht andere Anwendungen vorstellen, die sich in das Problem des mehrarmigen Banditen umformulieren lassen.

1. Beispiel: Auswahl von Nachrichten fĂŒr eine Website

FĂŒr eine Website sollen fĂŒr einen Zeitraum T insgesamt N Nachrichten zur VerfĂŒgung stehen, von denen aber nur k < N Nachrichten mit ihren Überschriften gezeigt werden. Es sollen diejenigen k Nachrichten ausgewĂ€hlt werden, die von den Nutzern am hĂ€ufigsten angeklickt und gelesen werden.

Hier ist das Dilemma zwischen Exploration und Exploitation offensichtlich: Einerseits möchte man die "besten" Nachrichten anzeigen, andererseits muss man erst herausfinden, welche Nachrichten dies sind. Durch die BeschrÀnkung des Zeitraumes T kann man das Leser-Verhalten nicht mit beliebiger Genauigkeit erkunden.

Aus diesem Beispiel kann man leicht ablesen, wann der k-armige Bandit ein geeignetes Modell darstellt:

  1. Es lassen sich mehrere Aktionen benennen, deren Wirkung vorerst unbekannt ist und untersucht werden muss.
  2. Stellt sich heraus, dass die Wirkungen unterschiedlich sind, muss man sie bewerten und eine Strategie ĂŒberlegen, wie man ihre Eigenschaften durch geeignete Tests feststellen kann.
  3. Erst wenn die Wirkungen hinreichend gut untersucht sind, kann man dazu ĂŒbergehen, die beste Aktion auszuwĂ€hlen.

Das folgende Beispiel wirkt zunÀchst zu komplex, es kann aber auch mit Hilfe des k-armigen Banditen bewÀltigt werden:

2. Beispiel: Der Monte-Carlo-Tree-Search-Algorithmus

In einem eigenen Kapitel wird der Monte-Carlo-Tree-Search-Algorithmus untersucht. Er soll in einem Spiel (man denke etwa an Schach oder Go) fĂŒr eine gegebene Spielsituation S die Gewinn-Wahrscheinlichkeiten fĂŒr die aktuell möglichen ZĂŒge schĂ€tzen. Dazu wird ausgehend von S der Spielbaum aufgebaut (der im Prinzip alle möglichen nĂ€chsten ZĂŒge, alle darauf möglichen Antworten und so weiter enthĂ€lt). Jeder Knoten dieses Baumes wird durch einen k-armigen Banditen modelliert. Dabei ergibt sich die Anzahl k durch die in der Spielsituation möglichen ZĂŒge. Ähnlich wie beim k-armigen Banditen eine Strategie entwickelt wird, den nĂ€chsten Arm zu wĂ€hlen, wird der Spielbaum untersucht und die Gewinn-Wahrscheinlichkeiten werden geschĂ€tzt.

Diese zweite Beispiel vermag einen Hinweis geben, wofĂŒr der k-armige Bandit als Paradebeispiel eingesetzt werden kann: Dadurch dass man die Banditen durch die erzielten Gewinne im Lauf der Zeit immer besser voneinander unterscheiden kann, lernt man im Lauf der Exploration aus den Belohnungen, welche Aktionen nĂŒtzlich sind und welche nicht. Man kann jetzt versuchen, daraus eine Strategie abzuleiten, wie man planvoll vorgehen kann, um die Belohnungen zu maximieren.

Diese Vorgehensweise wird meist als bestÀrkendes Lernen oder verstÀrkendes Lernen (reinforcement learning) bezeichnet. Man muss es vom unterweisenden Lernen abgrenzen, bei dem die optimale Strategie bereits bekannt ist und sie einem anderen beigebracht werden soll. Ein Problem der bestÀrkenden Lernens ist nÀmlich: selbst wenn ein bestimmtes Verhalten belohnt wird, ist nicht klar, ob es nicht andere Aktionen gibt, die eine noch höhere Belohnung einbringen; beim unterweisenden Lernen gibt es dieses Problem nicht.

Vergleicht man nochmals die beiden genannten Beispiele, so kann man auch besser einordnen, welchen Stellenwert der mehrarmige Bandit im Rahmen des bestĂ€rkenden Lernens hat: beim mehrarmigen Banditen wird jede Aktion sofort belohnt oder bestraft und somit ist es hier sinnvoll, allein durch Versuch und Irrtum Wissen ĂŒber die Banditen zu erwerben. Dagegen ist es bei einem Spiel wie Schach nur selten möglich, einen Zug sofort zu bewerten. Denn meist ist eine ganze Abfolge von ZĂŒgen zu finden, um aus einer gegebenen Spielsituation heraus das Spiel zu gewinnen. Und versucht man das Prinzip Versuch und Irrtum auf komplette Zugfolgen anzuwenden, entstehen sofort riesige Anzahlen von Möglichkeiten, die zu bewerten sind, da der Spielbaum beim Schach einen Verzweigungsgrad von etwa 30 bis 40 hat. In diesem Sinne stellen die zu entwickelnden Algorithmen nur einen Einstieg in die Thematik des bestĂ€rkenden Lernens dar.

Mathematische Modellierung der Banditen

Um spĂ€ter Simulationen durchzufĂŒhren, benötigt man spezielle Zufallsvariablen X1, X2, ..., Xk, die jeweils den Nettogewinn der k Banditen beschreiben. Da die zu entwickelnden Algorithmen herausfinden sollen, welcher Bandit den höchsten Erwartungswert liefert, werden die Banditen mit echt unterschiedlichen Erwartungswerten modelliert.

Die Zufallsvariablen fĂŒr den Nettogewinn

Die Einzelwahrscheinlichkeiten fĂŒr die Werte der Zufallsvariablen sind in Abbildung 2 zu sehen. Hier ist k = 9 gewĂ€hlt; werden spĂ€ter Simulationen mit unterschiedlichen Werten fĂŒr k ausgefĂŒhrt, so werden aus dieser Folge von Zufallsvariablen immer die ersten k verwendet oder weitere hinzugefĂŒgt.

Abbildung 2: Jeder der k einarmigen Banditen wird durch eine Zufallsvariable beschrieben. Sie gibt an, mit welcher Wahrscheinlichkeit ein Gewinn oder Verlust (der Einsatz wird einbehalten) eintritt. Die möglichen Werte der Zufallsvariablen und die Wahrscheinlichkeiten, mit denen ihre Werte eintreten, sind dem Spieler zunĂ€chst nicht bekannt. Durch zahlreiche Spiele kann er immer bessere SchĂ€tzungen fĂŒr sie abgeben. Blau eingezeichnet sind die Wahrscheinlichkeiten P(X = x) der Werte x der Zufallsvariable X. Rot eingezeichnet ist der Erwartungswert der jeweiligen Zufallsvariable. Um die verschiedenen Banditen untereinander zu vergleichen, muss man beachten, dass die Achsen jeweils anders skaliert sind.Abbildung 2: Jeder der k einarmigen Banditen wird durch eine Zufallsvariable beschrieben. Sie gibt an, mit welcher Wahrscheinlichkeit ein Gewinn oder Verlust (der Einsatz wird einbehalten) eintritt. Die möglichen Werte der Zufallsvariablen und die Wahrscheinlichkeiten, mit denen ihre Werte eintreten, sind dem Spieler zunĂ€chst nicht bekannt. Durch zahlreiche Spiele kann er immer bessere SchĂ€tzungen fĂŒr sie abgeben. Blau eingezeichnet sind die Wahrscheinlichkeiten P(X = x) der Werte x der Zufallsvariable X. Rot eingezeichnet ist der Erwartungswert der jeweiligen Zufallsvariable. Um die verschiedenen Banditen untereinander zu vergleichen, muss man beachten, dass die Achsen jeweils anders skaliert sind.

Man erkennt, dass die Zufallsvariablen nahezu identisch sind:

  • Mit hoher Wahrscheinlichkeit wird der Einsatz einbehalten (negativer Wert der Zufallsvariable).
  • Mit ebenso hoher Wahrscheinlichkeit wird ein kleiner Betrag ausgezahlt.
  • Mit geringer Wahrscheinlichkeit wird ein hoher Betrag ausbezahlt. Nur in der Höhe dieses Betrages unterscheiden sich die Banditen. Man erkennt in Abbildung 2, dass fĂŒr den Banditen i dieser Betrag gleich i + 1 ist.
  • Die Erwartungswerte sind gleich 0, 0.2, 0.4, 0.6, 0.8, ..., oder allgemein: ÎŒi = (i - 1) · 0.2.

Skalierung der Zufallsvariablen

Abbildung 3 zeigt die Bezeichnung fĂŒr die Wahrscheinlichkeit dafĂŒr, dass eine Zufallsvariable X einen bestimmten Wert xi annimmt (Gleichung 1) sowie die Formeln zur Berechnung des Erwartungswertes, der Varianz und der Standardabweichung einer Zufallsvariable X (Gleichung 2 bis 4).

Abbildung 3: Die Wahrscheinlichkeiten der möglichen Werte der Zufallsvariable werden als ihre Einzelwahrscheinlichkeiten bezeichnet. Beim Erwartungswert einer Zufallsvariable werden ihre Werte mit der Wahrscheinlichkeit ihres Eintretens, also den Einzelwahrscheinlichkeiten, gewichtet und summiert (Gleichung 2). Die Varianz einer Zufallsvariable ist gleich der mittleren quadratischen Abweichung vom Erwartungswert (Gleichung 3). Die Standardabweichung ist die Wurzel aus der Varianz (Gleichung 4).Abbildung 3: Die Wahrscheinlichkeiten der möglichen Werte der Zufallsvariable werden als ihre Einzelwahrscheinlichkeiten bezeichnet. Beim Erwartungswert einer Zufallsvariable werden ihre Werte mit der Wahrscheinlichkeit ihres Eintretens, also den Einzelwahrscheinlichkeiten, gewichtet und summiert (Gleichung 2). Die Varianz einer Zufallsvariable ist gleich der mittleren quadratischen Abweichung vom Erwartungswert (Gleichung 3). Die Standardabweichung ist die Wurzel aus der Varianz (Gleichung 4).

Die oben gezeigten Zufallsvariablen (Abbildung 2) besitzen unterschiedliche Erwartungswerte, aber auch unterschiedliche Standardabweichungen. Daher werden die Zufallsvariablen so skaliert, dass die Erwartungswerte unverÀndert bleiben, die Standardabweichungen aber gleich 1 sind.

Abbildung 4 zeigt die Formel zur Skalierung (Gleichung 1) und die BegrĂŒndung fĂŒr das Verhalten des Erwartungswertes (Gleichung 2) und der Standardabweichung (Gleichung 3). Dabei wird verwendet, dass fĂŒr Erwartungswert und Varianz einer Zufallsvariable X und reelle Zahlen a, b gilt:

E[aX + b] = a E[X] + b

Var(aX + b) = a2 Var(X).

Abbildung 4: Die Zufallsvariablen aus Abbildung 2 werden gemĂ€ĂŸ Gleichung 1 skaliert. Dabei bleibt der Erwartungswert unverĂ€ndert und die Varianz ist gleich 1, somit ist auch die Standardabweichung gleich 1 (Gleichung 2 und 3).Abbildung 4: Die Zufallsvariablen aus Abbildung 2 werden gemĂ€ĂŸ Gleichung 1 skaliert. Dabei bleibt der Erwartungswert unverĂ€ndert und die Varianz ist gleich 1, somit ist auch die Standardabweichung gleich 1 (Gleichung 2 und 3).

Wenn im folgenden Kapitel Simulationen gezeigt werden, so werden immer diese skalierten Zufallsvariablen verwendet.

Abbildung 5: Die Zufallsvariablen fĂŒr die 9 Banditen aus Abbildung 2, nachdem sie gemĂ€ĂŸ Gleichung 1 in Abbildung 4 skaliert wurden.Abbildung 5: Die Zufallsvariablen fĂŒr die 9 Banditen aus Abbildung 2, nachdem sie gemĂ€ĂŸ Gleichung 1 in Abbildung 4 skaliert wurden.

Vergleicht man die Abbildungen 2 und 5, so erkennt man:

  • Die Werte der Zufallsvariablen wurden durch die Skalierung verĂ€ndert, nicht aber ihre Wahrscheinlichkeiten.
  • Die Erwartungswerte sind unverĂ€ndert.
  • Die Standardabweichungen sind in den Abbildung nicht unmittelbar erkennbar; wie oben gezeigt wurde, sind sĂ€mtliche Standardabweichungen in Abbildung 5 gleich 1.

Bestandteile eines Algorithmus zur Simulation des Spiels am mehrarmigen Banditen

Im folgenden Kapitel sollen Algorithmen entwickelt werden, die N Spiele am k-armigen Banditen simulieren. Die wichtigste Eigenschaft dieser Algorithmen ist natĂŒrlich: wie wird das Dilemma zwischen Exploration und Exploitation gelöst?

UnabhÀngig von der dazu eingesetzten Strategie kann man folgende Bestandteile eines Algorithmus identifizieren:

  1. Initialisierung: Die zu den k Banditen gehörigen Zufallsvariablen mĂŒssen vorbereitet werden und es muss eine einfache Möglichkeit geschaffen werden, einen Banditen aufzurufen und ein Spiel daran zu simulieren. Weiter mĂŒssen – je nachdem welche Strategie eingesetzt wird – Datenelemente vorbereitet werden, die die Ergebnisse der Spiele speichern und die Berechnung des nĂ€chsten auszuwĂ€hlenden Banditen ermöglichen.
  2. Schleife ĂŒber die N Spiele: Bei jedem der N Spiele sind folgende Schritte auszufĂŒhren:
    1. Selektion: Auswahl des Banditen, der als nÀchster gespielt wird.
    2. Spiel ausfĂŒhren: das Spiel mit dem gewĂ€hlten Banditen wird ausgefĂŒhrt (Zufallsgenerator, der die entsprechende Zufallsvariable Xi verwendet) und das Ergebnis wird abgespeichert.
    3. Update: Je nachdem welches Kriterium in der Selektion verwendet wird, mĂŒssen bestimmte GrĂ¶ĂŸen neu berechnet werden, damit fĂŒr das nĂ€chste Spiel wieder eine Entscheidung getroffen werden kann.
  3. Aufbereitung und Ausgabe der Ergebnisse.

Der entscheidende Punkt ist – wie aus der Diskussion des Dilemmas zwischen exploration und exploitation klar geworden ist – die Auswahl eines Banditen: Hier muss ein Kriterium gefunden werden, das nicht nur kurzfristig den bisher besten Banditen wĂ€hlt, sondern einen langfristigen Erfolg verspricht.

Und abhĂ€ngig von diesem Selektionsmechanismus mĂŒssen geeignete Datenelemente vorbereitet und nach jedem Spiel aktualisiert werden.

R-Skripte

Modellierung von Zufallsvariablen

Eine diskrete Zufallsvariable besitzt endlich viele Zahlenwerte, denen jeweils eine Wahrscheinlichkeit zugeordnet ist; die Summe der Wahrscheinlichkeiten muss 1 ergeben. Modellieren lĂ€sst sich dies zum Beispiel mit einem Dataframe mit 2 Spalten, eine Spalte value fĂŒr die Werte und eine Spalte prob fĂŒr die zugeordneten Wahrscheinlichkeiten.

AusfĂŒhrliche ErklĂ€rungen zu Dataframes finden sich in Dataframes in R: der Datentyp data frame und Dataframes in R: Anwendungen.

Das folgende Skript zeigt, wie die in Abbildung 6 dargestellte Zufallsvariable erzeugt wird.

Abbildung 6: Darstellung der Einzelwahrscheinlichkeiten einer beliebigen Zufallsvariablen X. Das folgende R-Skript zeigt, wie X als Dataframe gespeichert wird und wie dieses Dataframe eingesetzt wird, um das Diagramm zu erzeugen.Abbildung 6: Darstellung der Einzelwahrscheinlichkeiten einer beliebigen Zufallsvariablen X. Das folgende R-Skript zeigt, wie X als Dataframe gespeichert wird und wie dieses Dataframe eingesetzt wird, um das Diagramm zu erzeugen.

probs <- c(0.4, 0.4, 0.2)
values <- c(-1, 1, 2)

rv <-  data.frame(prob = probs, value = values)
rv
#   prob value
# 1  0.4    -1
# 2  0.4     1
# 3  0.2     2

plot(x = rv$value, y = rv$prob, col = "blue", type = "h",
     xlab = "x", ylab = "P(X = x)", frame.plot = TRUE, 
     xlim = c(-1.5, 2.5) , ylim = c(0.0, 0.5),
     main = "Zufallsvariable", lwd = 3)
grid()

Um sicherzustellen, dass sich die Spalte prob im Dataframe als Wahrscheinlichkeiten einer Zufallsvariable interpretieren lassen, könnte man auch eine eigene Funktion zum Erzeugen des Dataframes anbieten, die prĂŒft,

  • ob alle Wahrscheinlichkeiten nicht-negativ sind und
  • ob ihre Summe 1 ergibt.

Funktionen fĂŒr Zufallsvariablen

Mit der Vereinbarung, Zufallsvariablen wie oben beschrieben als Dataframe zu modellieren, kann man jetzt weitere Funktionen anbieten um typische Operationen mit Zufallsvariablen auszufĂŒhren:

  • Berechnung des Erwartungswertes,
  • Berechnung der Varianz,
  • Berechnung der Standardabweichung.

ZusĂ€tzlich ist es sinnvoll, eine Funktion anzubieten, die prĂŒft, ob ein Dataframe eine Zufallsvariable beschreibt

is.randomVariable <- function(rv){
  stopifnot(is.data.frame(rv))
  result <- TRUE
  
  if( !(identical(names(rv), c("prob", "value")) || identical(names(rv), c("value", "prob")) ) ){
    result <- FALSE
  }
  if(any(rv$prob < 0)){
    result <- FALSE
  }
  if(sum(rv$prob) != 1){
    result <- FALSE
  }
  if(rv$value != unique(rv$value)){
    result <- FALSE
  }
  return(result)
}

Mit Hilfe von is.randomVariable() lassen sich die anderen Funktionen leichter implementieren:

# Erwartungswert:
meanValue <- function(rv){
  stopifnot(is.randomVariable(rv))
  return(sum( rv$prob * rv$value ))
}

# Varianz:
variance <- function(rv){
  stopifnot(is.randomVariable(rv))
  difference <- rv$value - sum( rv$prob * rv$value )
  return(sum( (difference * difference) * rv$prob ))
}

# Standardabweichung:
standardDeviation <- function(rv){
  return(sqrt(variance(rv)))
}

Beispiel fĂŒr die Anwendung der Funktionen:

probs <- c(0.4, 0.4, 0.2)
values <- c(-1, 1, 2)

rv <-  data.frame(prob = probs, value = values)

is.randomVariable(rv)
# [1] TRUE

meanValue(rv)
# [1] 0.4

variance(rv)
# [1] 1.44

standardDeviation(rv)
# [1] 1.2

Erzeugen der Zufallsvariablen fĂŒr den mehrarmigen Banditen

Die oben gezeigten Zufallsvariablen fĂŒr die Banditen, die spĂ€ter fĂŒr die Simulationen verwendet werden, können als Dataframes erzeugt werden:

k <- 9
bandits <- vector(mode = "list", length = k)
prob <- c(0.4, 0.4, 0.2)
par(mfrow = c(3,3))

for(i in seq_len(k)){
  value <- c(-2, 1, i + 1)
  bandits[[i]] <-  data.frame(prob = prob, value = value)
  mu <- meanValue(bandits[[i]])
  
  plot(x = bandits[[i]]$value, y = bandits[[i]]$prob, col = "blue", 
       type = "h", xlab = "x", ylab = "P(X = x)", frame.plot = TRUE, 
       xlim = c(-3, i + 2), ylim = c(0.0, 0.5),
       main = paste0("Bandit ", i, collapse = ""),
       lwd = 3, lty = 1)
  grid()
  lines(x = c(mu, mu), y = c(0, 1), col = "red")
}

Zeile 2: Die Dataframes fĂŒr die Zufallsvariablen werden zu einer Liste zusammengefasst.

Zeile 3: Die Einzelwahrscheinlichkeiten sind fĂŒr alle Zufallsvariablen identisch.

Zeile 4: FĂŒr die Plots wird eine Anordnung in einem Gitter mit 3 Reihen und 3 Spalten vorbereitet.

Zeile 6 bis 18: In der for-Schleife werden die Zufallsvariablen definiert (Zeile 8), die Mittelwerte berechnet (Zeile 9) und je ein Plot erzeugt (Zeile 11 bis 17. Die Zufallsvariablen unterscheiden sich lediglich im dritten Wert, der mit Hilfe des Schleifenindex gesetzt wird (Zeile 7).

Die Graphik mit den 9 Plots ist in Abbildung 7 zu sehen.

Abbildung 7: Darstellung der 9 noch unskalierten Zufallsvariablen fĂŒr den mehrarmigen Banditen, die im letzten Skript erzeugt wurden.Abbildung 7: Darstellung der 9 noch unskalierten Zufallsvariablen fĂŒr den mehrarmigen Banditen, die im letzten Skript erzeugt wurden.

Skalierung der Zufallsvariablen

Mit der Funktion normalizeRV() können Zufallsvariablen gemĂ€ĂŸ Gleichung 1 in Abbildung 4 so skaliert werden, dass sie Standardabweichung 1 besitzen:

normalizeRV <- function(rv){
  stopifnot(is.randomVariable(rv))
  stDev <- standardDeviation(rv)
  mv <- meanValue(rv)
  rv$value <- rv$value / stDev + mv * (stDev - 1) / stDev
  return(rv)
}

Mit Hilfe von lapply() und FUN = normalizeRV werden die Zufallsvariablen bandits, die zuletzt dargestellt wurden, skaliert. Ihre Standardabweichungen werden ausgegeben und sie werden in einem 3 × 3-Plot dargestellt (Abbildung 8):

# bandits wie oben
scaledBandits <- lapply(X = bandits, FUN = normalizeRV)

sapply(X = scaledBandits, FUN = standardDeviation)
# [1] 1 1 1 1 1 1 1 1 1

par(mfrow = c(3,3))
for(i in seq_len(k)){
  mu <- meanValue(scaledBandits[[i]])
  plot(x = scaledBandits[[i]]$value, y = scaledBandits[[i]]$prob, col = "blue", 
       type = "h", xlab = "x", ylab = "P(X = x)", frame.plot = TRUE, 
       ylim = c(0.0, 0.5),
       main = paste0("Bandit ", i, collapse = ""),
       lwd = 3, lty = 1)
  grid()
  lines(x = c(mu, mu), y = c(0, 1), col = "red")
}

Abbildung 8: Darstellung der skalierten Zufallsvariablen fĂŒr den mehrarmigen Banditen (Skalierung nach Gleichung 1 in Abbildung 4).Abbildung 8: Darstellung der skalierten Zufallsvariablen fĂŒr den mehrarmigen Banditen (Skalierung nach Gleichung 1 in Abbildung 4).