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

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

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.

Für die Banditen werden folgende Annahmen gemacht, die sich in den Eigenschaften der Zufallsvariablen X₁, X₂, ..., X_k wiederspiegeln:

• Unabhängigkeit: Die Ergebnisse, die ein Bandit liefert, ist jeweils unabhängig von den Ergebnissen der anderen Banditen.
• Stationarität: Die Zufallsvariablen X₁, X₂, ..., X_k verändern sich im Lauf der Zeit nicht.
• Unterschiedliche Erwartungswerte: Die Erwartungswerte μ₁, μ₂, ..., μ_k der Zufallsvariablen X₁, X₂, ..., X_k 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 X₁, X₂, ..., X_k 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 X₁, X₂, ..., X_k 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 X_i 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(μ₁, μ₂, ..., μ_k)

spielt; dies setzt natürlich voraus, dass der mit μ_max verbundene Nettogewinn positiv ist.

Kennt man den Eigenschaften der Zufallsvariablen X₁, X₂, ..., X_k 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 X₁, X₂, ..., X_k, 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.

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

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) = a² 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).

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.

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

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.

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