Der mehrarmige Bandit (multi-armed bandit): Implementierung eines Simulations-Algorithmus in R

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 den genannten Artikeln werden hier als bekannt vorausgesetzt.

Überblick über den Algorithmus

Die grobe Struktur des Algorithmus

In Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen wurde bereits der Algorithmus zur Simulation des mehrarmigen Banditen in seinen Grundzügen erklärt; die entsprechende Abbildung ist hier nochmals wiedergegeben.

Abbildung 1: Bildliche Darstellung des Algorithmus zur Simulation von N Spielen am k-armigen Banditen (hier ersetzt durch 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.

Das Kernstück ist natürlich der Selektionsmechanismus: Wie wird aus den bisherigen Ergebnissen der Bandit für das nächste anstehende Spiel ausgewählt? In Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen wurden dazu mehrere Strategien vorgestellt und mit ihnen Simulationen durchgeführt. Dafür soll nun eine Implementierung in R entwickelt werden, die versucht vorzugehen wie in Abbildung 1.

Die Implementierung wird nur in einem Punkt von Abbildung 1 abweichen:

Die Funktion mab() führt die eigentliche Simulation durch und speichert alle Zwischenergebnisse in geeigneten Datenelementen, die dann zurückgegeben werden. Zusätzlich werden die wichtigsten Informationen über die Simulation auf der Konsole ausgegeben. Die in Abbildung 1 angedeuteten graphischen Auswertungen werden hier nicht implementiert; in den Rückgabewerten sind aber alle Zwischenergebnisse der Simulation gespeichert, so dass dies schnell erledigt werden kann.

Verwendete Funktionen

In Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation wurde in den R-Skripten gezeigt, wie Zufallsvariable als Dataframes modelliert wurden, und wie man statistische Funktionen implementiert, die Dataframes verarbeiten:

• Berechnung des Erwartungswertes mit meanValue(rv) ,
• Berechnung der Varianz mit variance(rv) ,
• Berechnung der Standardabweichung mit standardDeviation(rv) .

Für diese Funktionen muss der Eingabewert rv eine Zufallsvariable sein, die als Dataframe gegeben ist; die kann mit der Funktion is.randomVariable(rv) überprüft werden.

Um eine Zufallsvariable als Dataframe abzuspeichern, legt man ein Dataframe mit den beiden Spalten prob und value an, wie es das folgende Beispiel zeigt:

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

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

Alle hier genannten Funktionen werden im Folgenden verwendet; ihre ausführliche Erklärung findet sich im genannten Kapitel.

Anforderung an die Quelltexte

Der Algorithmus wurde geschrieben, um sämtliche Berechnungen mit ihren Zwischenergebnissen nachvollziehbar zu machen und diese in Graphiken aufzubereiten (siehe etwa die Abbildungen in Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen).

Wenn man an einer Implementierung interessiert ist, die auch für viele Banditen oder sehr große Anzahlen von Spielen sehr schnell ist und wenig Speicher benötigt, wird man die Quelltexte deutlich überarbeiten müssen. Insbesondere könnte man auf die Matrizen verzichten, die Zwischenergebnisse speichern. Stattdessen kann man einfachere Variablen einsetzen, die wiederverwendet und immer mit den aktuellen Werten überschrieben werden. Wie genau man dies realisiert, soll hier nicht diskutiert werden.

Die Eingabewerte

Die Liste der Eingabewerte ist ziemlich lang, allerdings wird man für einfache Anwendungen die meisten davon nicht benötigen. Im folgenden Listing ist die Funktion mab() ohne ihre Implementierung gezeigt; man erkennt die Eingabewerte mit ihren default-Werten:

mab <- function(K = 9L,
                N = 2700L, 
                selection_strategy = 1,
                eps = 0.1,
                ret = FALSE,
                normalize = TRUE,
                debug = FALSE,
                dgts = 3){
# Implementierung
}

Die Bedeutung der Eingabewerte:

1. Mit K wird die Anzahl der Banditen angegeben.
2. Mit N wird die Anzahl der auszuführenden Spiele bezeichnet.
3. Die Strategie zur Auswahl des nächsten Banditen wird mit internen Funktionen realisiert, die in der Implementierung zu einer Liste zusammengefasst werden. Mit dem Eingabewert selection_strategy kann der Index in dieser Liste angegeben werden. Implementiert als interne Funktionen sind die 5 in Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen besprochenen Strategien: random() , greedy() , eps_greedy() , eps_first() und eps_decreasing() .
4. Die letzten drei der genannten Strategien benötigen als Eingabewert eine Wahrscheinlichkeit ε, die hier mit eps bezeichnet wird.
5. Der logische Wert ret gibt an, ob ein Rückgabewert berechnet werden soll. Falls ja, werden das Dataframe mit den Banditen (entsprechen Zufallsvariablen) und 4 Matrizen zu einer Liste zusammengefasst. Darin sind alle Zwischenergebnisse über den Verlauf der Simulation gespeichert; sie können später nach Belieben ausgewertet werden. Ohne den Rückgabewert erfolgen lediglich Konsolen-Ausgaben über die wichtigsten Ergebnisse der Simulation.
6. In Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation wurde diskutiert, dass man die Zufallsvariablen, die die Banditen beschreiben, besser so skalieren soll, dass sie identische Standardabweichungen besitzen. Mit normalize lässt sich angeben, ob die Zufallsvariablen skaliert werden oder nicht. (Die unskalierten Zufallsvariablen werden im genannten Artikel beschrieben.)
7. Setzt man debug = TRUE werden am Ende der Simulation die Matrizen mit den Zwischenergebnissen ausgegeben. Bei großen K und N ist dies nicht empfehlenswert, für kleine Tests kann dies sehr hilfreich sein, um die Berechnungen nachzuvollziehen.
8. Durch die Skalierung der Zufallsvariablen sowie durch Mittelwertbildungen entstehen immer Zahlenwerte mit Nachkommastellen. Der Eingabewert dgts gibt an, mit wie vielen gültigen Stellen die Konsolen-Ausgaben erfolgen sollen.

Realisierung der Strategien als interne Funktionen

Wie aus den Eingabewerten zu ersehen war, wird die Auswahl-Strategie durch das Argument selection_strategy gesetzt. Hier werden die 5 Strategien angeboten, die in Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen diskutiert wurden.

Die folgende Tabelle beschreibt die Strategien kurz, gibt die interne Funktion an, die die Strategie implementiert und den Index selection_strategy , mit dem die Strategie beim Aufruf von mab() gesetzt werden kann:

Tabelle 1: Die als interne Funktionen implementierten Auswahl-Strategien.

Die Implementierung der Strategien wird später gezeigt, wenn die Iteration über die Spiele durchgeführt wird. Der Grund ist, dass die Auswahl-Kriterien auf spezielle Datenelemente zugreifen müssen, die jetzt noch nicht erklärt wurden.

Einzig die Strategie random() kann jetzt schon gezeigt werden – sie benötigt keinerlei Information über die vorhergehenden Spiele:

random <- function(){
    return( sample(x = Ks, size = 1, replace = TRUE) )
  }

Mit Ks ist der Vektor (1:K) gemeint, woraus eine Komponente zufällig ausgewählt wird (wobei jeder Bandit 1, ..., K mit gleicher Wahrscheinlichkeit gewählt werden kann).

Man erkennt an diesem Beispiel bereits, wie die Strategien implementiert sind:

• Da sie interne Funktionen sind, benötigen sie keine Eingabewerte und können auf Datenelemente zugreifen, die in der Funktion mab() definiert sind, wie hier Ks.
• Der Rückgabewert ist immer der Index des ausgewählten Banditen.

Weitere Strategien werden entsprechend implementiert oder können später nach Belieben hinzugefügt werden. (Dabei ist "nach Belieben" nicht ganz richtig: sofern sie weitere Datenelemente benötigen, müssen diese bereitgestellt und berechnet werden.)

Initialisierung der Datenelemente und Implementierung der Strategien

Prüfung der Eingabewerte

Die Vielzahl der Eingabewerte führt zu einer Vielzahl von möglichen oder sogar nötigen Prüfungen. Da aber für die meisten Argumente von mab() default-Werte angegeben sind, sollte es nicht schwer fallen, die Argumente richtig zu setzen.

Die beiden wichtigsten Prüfungen betreffen die Auswahl-Strategie selection_strategy und die Wahrscheinlichkeit eps :

stopifnot( is.numeric(selection_strategy), identical(length(selection_strategy), 1L) )
stopifnot( eps >= 0, eps <= 1)

Die Auswahl-Strategie muss als Zahl eingegeben werden (Index der Strategie in der Liste aller Strategien) und muss eindeutig sein, siehe Zeile 1; damit eps als Wahrscheinlichkeit interpretiert werden kann, muss 0 ≤ eps ≤ 1 gelten (Zeile 2).

Initialisierungen

Die Initialisierungen kann man in 4 Gruppen einteilen:

1. Vorbereitung der Iteration über alle Banditen (Zeile 2).
2. Die Zufallsvariablen (als Dataframes) für die K Banditen vorbereiten und eventuell skalieren (Zeile 5 bis 15).
3. Alle internen Funktionen für die Auswahl-Strategien zu einer Liste zusammenfassen und den Index aus dem Eingabewert selection_strategy in eine Funktion umwandeln, die dann später eingesetzt wird (Zeile 19 bis 22).
4. Initialisieren der Matrizen, die die Zwischenergebnisse der Simulation speichern und auf die die Auswahl-Strategien zugreifen werden (Zeile 25 bis 28).

# Für Iteration über alle Banditen:
Ks <- seq_len(K)

# Liste der Banditen erzeugen:
bandits <- vector(mode = "list", length = K)
prob <- c(0.4, 0.4, 0.2)
for(k in Ks){
    value <- c(-2, 1, k + 1)
    bandits[[k]] <-  data.frame(prob = prob, value = value)
}
if(normalize){
    for(k in Ks){
        bandits[[k]] <- normalizeRV(bandits[[k]])
    }
}

# Strategien:
# Alle internen Funktionen zu einer Liste zusammenfassen:
strategies <- list(random = random, greedy = greedy, eps_greedy = eps_greedy,
                     eps_first = eps_first, eps_decreasing = eps_decreasing)
strategy <- strategies[[selection_strategy]]

# KxN-Matrizen für Auswertung
rewards <- matrix(data = NA_integer_, nrow = K, ncol = N)
sumOfRewardsPerBandit <- matrix(data = 0, nrow = K, ncol = N)
playsPerBandit <- matrix(data = 0, nrow = K, ncol = N)
meanRewardPerBandit <- matrix(data = 0, nrow = K, ncol = N)

Einige Details:

1. Die Verwendung von Ks bedarf keiner weiteren Erklärung, die Iteration über alle Banditen wird mehrfach benötigt.
2. Wie man die Banditen durch Zufallsvariablen beschreibt, wurde in Der mehrarmige Bandit (multi-armed bandit): Das Dilemma zwischen Exploration und Exploitation ausführlich erklärt und wird hier nicht wiederholt. Jede Zufallsvariable entspricht einem Dataframe und alle K Dataframes werden zu einer Liste bandits zusammengefasst. Der Zugriff auf einen einzelnen Banditen erfolgt dann über den Index, zum Beispiel bandits[[k]] (siehe etwa Zeile 13).
3. Die Auswahl-Strategien für den nächsten Banditen werden als interne Funktionen implementiert, die weiter unten gezeigt werden. Diese Funktionen werden zu einer Liste strategies zusammengefasst; im Argument von list() stehen somit Paare der Form name = value . Auf die einzelnen Strategien kann dann über den Namen oder den Index zugegriffen werden. Hier muss man sorgfältig auf die Reihenfolge der Argumente in list() achten, da die Strategie in mab() über den Index gesetzt wird (siehe auch Tabelle 1). Eine vielleicht weniger fehleranfällige Lösung ist es, die Strategie in mab() über den Namen zu setzen. In Zeile 22 wird dann mit Hilfe des Index die Strategie aus der Liste strategies geholt. Das heißt das dadurch definierte strategy kann im Folgenden wie eine Funktion eingesetzt werden und ruft die ausgewählte Strategie auf.
4. Die Matrizen in den Zeilen 25 bis 28 wurden in Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen erklärt. Dort wurden unter Die Auswertung von Simulationen die Größen besprochen, die man benötigt, um die verschiedenen Algorithmen zu beurteilen. Dazu wurde ein einfaches Beispiel mit K = 2 Banditen und N = 10 Spielen angeführt und die Ergebnisse der Simulation in Tabellen dargestellt. Für die Inhalte dieser Tabellen werden jetzt Matrizen vorbereitet, nämlich:
   1. Die jeweils ausbezahlten Gewinne werden in rewards abgespeichert. Die Matrix wird zu Beginn mit NA-Werten (NA = not available) aufgefüllt. Wird zur Zeit t am Bandit j ein Gewinn R erzielt, wird an der Stelle rewards[j, t] der Betrag R eingetragen (j-te Zeile, Spalte t).
   2. In der Matrix sumOfRewardsPerBandit stehen dann die kumulierten Zeilensummen von rewards. Dadurch kann man sofort ablesen, welchen Gewinn ein Bandit j bis zur Zeit t insgesamt geliefert hat.
   3. Um von den Beträgen zu gemittelten Werten überzugehen (also Gewinn pro Spiel), benötigt man die Anzahl der Spiele, die an einem Bandit j bis zur Zeit t ausgeführt wurden. Diese Anzahl wird in der Matrix playsPerBandit abgespeichert.
   4. Teilt man den Gewinn, den ein Bandit bis zur Zeit t geliefert hat durch die Anzahl der Spiele, die man am Banditen ausgeführt hat, erhält man den mittleren Gewinn pro Spiel; dieser ist in der Matrix meanRewardPerBandit gespeichert.

Die Matrizen sumOfRewardsPerBandit, playsPerBandit und meanRewardPerBandit können mit 0 initialisiert werden (kein Spiel ausgeführt beziehungsweise kein Gewinn erzielt). In rewards werden NA-Werte anstelle 0 verwendet, da hier ein Eintrag 0 zweideutig wäre:

• Wurde der Bandit nicht gespielt oder
• wurde er gespielt und hat den Gewinn 0 geliefert?

Weiter unten werden zwei Simulationen mit K = 2 Banditen und N = 10 Spielen gezeigt; dort lässt sich die Berechnung der Einträge in den Matrizen leicht nachvollziehen.

Die Implementierung der Auswahl-Strategien

Nachdem jetzt die Matrizen zur Speicherung der Zwischenergebnisse erklärt wurden, können auch die Implementierungen der Auswahl-Strategien angegeben werden.

1. Die Funktion random() trifft immer eine zufällige Entscheidung und greift daher nicht auf bisherige Zwischenergebnisse zurück (Zeile 1 bis 3).
2. Die Funktion greedy() (Zeile 5 bis 22) spielt zunächst alle Banditen genau einmal (Zeile 9 und 10, t ist die Zählvariable, wenn die N Spiele durchgeführt werden). Für das Spiel t wird nachgeschaut, welcher Bandit bei t - 1 den höchsten Gewinn pro Spiel erzielt hat (Suche nach Maximum in meanRewardPerBandit, Zeile 13). Ist das Ergebnis eindeutig, wird der Index des entsprechenden Banditen zurückgegeben (Zeile 17). Andernfalls wird eine Zufalls-Entscheidung zwischen den besten Banditen gefällt (Zeile 19).
3. Die drei weiteren Funktionen eps_greedy() , eps_first() und eps_decreasing() sprechen mit Hilfe einer Zufalls-Entscheidung random() oder greedy() an (Erklärung in Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen).

random <- function(){
  return( sample(x = Ks, size = 1, replace = TRUE) )
}

greedy <- function(){
  # Zuerst alle K Banditen einmal spielen, 
  # dann jeweils besten auswählen;
  # falls nicht eindeutig: zufällige Auswahl
  if(t <= K){
    return(t)
  } else {
    # in meanRewardPerBandit[ , t-1]: Maximum suchen
    bestScore <- max(meanRewardPerBandit[ , t-1])
    idx <- which(meanRewardPerBandit[ , t-1] == bestScore)
    
    if(identical(length(idx), 1L)){
      return(idx)
    } else {
      return(sample(x = idx, size = 1, replace = TRUE))
    }
  }
}

eps_greedy <- function(){
  if(runif(n = 1) < eps){
    return(random())
  } else {
    return(greedy())
  }
}

eps_first <- function(){
  # cat("eps: ", eps, "\n")
  if(t / N < eps){
    return(random())
  } else {
    return(greedy())
  }
}

eps_decreasing <- function(){
  # interne Funktion: linear, abnehmend
  decr_function <- function(t){
    return( 2 * eps * (1 - t / N) )
  }
  
  if(runif(n = 1) < decr_function(t)){    # Zufallszahl < Fkt.wert -> "random"
    return(random())
  } else {          # "greedy"
    return(greedy())
  }
}

Iteration über die Anzahl der Spiele: Auswahl, Spiel, Update

In Abbildung 1 wurde gezeigt, dass der eigentliche Ablauf der Simulation in der Schleife über die N Spiele stattfindet, wobei jeder Durchlauf aus drei Teilen besteht:

1. Auswahl des nächsten Banditen mit strategy() .
2. Spielen des Banditen: mit Hilfe seiner Zufallsvariable wird ein Gewinn ermittelt. Hierfür wird unten eine interne Funktion play() implementiert.
3. Update: Das Ergebnis des Spiels wird verwendet, um die Matrizen zu aktualisieren.

Die Implementierung von play() zeigt das folgende Listing:

play <- function(b){
  bandit <- bandits[[b]]
  return( sample(x = bandit$value, size = 1, replace = FALSE, prob = bandit$prob) )
}

Eingabewert von play() ist der Index des Banditen (der von strategy() geliefert wurde). Mit ihm wird das Dataframe des zugehörigen Banditen geladen (Zeile 2) und mit dessen Wahrscheinlichkeiten für die möglichen Gewinne eine Zufalls-Entscheidung getroffen und der Gewinn zurückgegeben (Zeile 3).

Damit erleichtert sich die Implementierung der eigentlichen Schleife. Der erste Durchlauf der Schleife t <- 1 wird gesondert behandelt, da hier das Update anderen Regeln gehorcht als die späteren Updates.

# t = 1 gesondert behandeln wg. update
t <- 1    # ACHTUNG: wird in den strategies benötigt!
k <- strategy()
rewards[k, 1] <- play(k)

# update:
sumOfRewardsPerBandit[k, 1] <- rewards[k, 1]
playsPerBandit[k, 1] <- 1
meanRewardPerBandit[k, 1] <- rewards[k, 1]

#  2. Schleife 2...N

for(t in (2:N)){
  k <- strategy()
  rewards[k, t] <- play(k)
  
  sumOfRewardsPerBandit[-k, t] <- sumOfRewardsPerBandit[-k, t-1]
  sumOfRewardsPerBandit[k, t] <- sumOfRewardsPerBandit[k, t-1] + rewards[k, t]
  
  playsPerBandit[-k, t] <- playsPerBandit[-k, t-1]
  playsPerBandit[k, t] <- playsPerBandit[k, t-1] + 1
  
  meanRewardPerBandit[-k, t] <- meanRewardPerBandit[-k, t-1]
  meanRewardPerBandit[k, t] <- sumOfRewardsPerBandit[k, t] / playsPerBandit[k, t]
}    # Ende for(t in (2:N))

Zur Erklärung:

Zeile 2: Da einige Strategien die ersten Spiele anders behandeln als spätere Spiele, muss t <- 1 ausdrücklich gesetzt werden.

Zeile 3: Hinter der Funktion strategy() verbirgt sich die gewählte Strategie; sie liefert als Rückgabewert den Index des gewählten Banditen.

Zeile 4: Es wird ein Spiel ausgeführt; der Rückgabewert von play() ist der erzielte Gewinn, der sofort an der richtigen Stelle in der Matrix rewards eingetragen wird (Zeile k, Spalte 1).

Zeile 7 bis 9: In der Matrix rewards sind keine weiteren Aktualisierungen nötig; die Einträge in der ersten Spalte für nicht-gespielte Banditen bleiben NA (hier kann man später nachvollziehen, dass sie nicht gespielt wurden, 0 wäre mehrdeutig).

In den anderen drei Matrizen muss ebenfalls in der Zeile k, Spalte 1 ein neuer Eintrag erzeugt werden; für nicht-gespielte Banditen können die Einträge bei 0 verbleiben.

Zeile 13 bis 25: Die restlichen Spiele werden in der Schleife abgearbeitet.

Zeile 14 und 15: Analog zu Zeile 3 und 4. Die Matrix rewards ist damit aktualisiert.

Zeile 17 bis 24: Neu berechnet werden muss jetzt jeweils der Eintrag Zeile k, Spalte t für die anderen drei Matrizen (Zeile 18, 21, 24). Für die nicht-gespielten Banditen wird der Eintrag der Spalte t - 1 übernommen (Zeile 17, 20, 23).

Ausgaben und Rückgabewert

Nachdem mit der Schleife for(t in (2:N)) die eigentliche Simulation beendet ist, kann man die restlichen Aufgaben in 3 Gruppen unterteilen:

1. Ausgabe der berechneten Matrizen mit jeweils dgts gültigen Stellen (Zeile 2 bis 14). Diese Ausgabe erfolgt nur wenn der logische Wert debug gleich TRUE gesetzt wurde und ist bei umfangreichen Simulationen nicht zu empfehlen.
2. Ausgaben über die wichtigsten Ergebnisse der Simulation, die auch bei debug = FALSE erfolgen (Zeile 16 bis 40).
3. Falls in den Eingabewerten ein Rückgabewert angefordert wurde (mit ret = TRUE ), werden die berechneten Listen (Banditen) und Matrizen zu einer Liste zusammengefasst und zurückgegeben. Andernfalls gibt es keinen Rückgabewert. Aus dem Rückgabewert kann man jetzt leicht die Diagramme erzeugen, die in Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen gezeigt und diskutiert wurden.

if(debug){    # Ausgabe der Matrizen
  cat("rewards: \n")
  print(rewards, digits = dgts)
  
  cat("sumOfRewardsPerBandit: \n")
  print(sumOfRewardsPerBandit, digits = dgts)
  
  cat("playsPerBandit: \n")
  print(playsPerBandit)
  
  cat("sumOfRewardsPerBandit: \n")
  print(sumOfRewardsPerBandit, digits = dgts)
}

cat("gewählte Strategie: \n")
cat(names(strategies)[selection_strategy], "\n")

cat("Anzahlen, wie oft die K Banditen gespielt wurden: \n")
print(playsPerBandit[ , N])

cat("theoretische Mittelwerte \"Gewinn pro Spiel\" (für alle Banditen): \n")
mw <- sapply(X = bandits, FUN = meanValue)
print(mw)

cat("Erwartungswert für den ausbezahlten Betrag, wenn man alle Banditen gleich oft spielt: \n")
print( sum(mw) / K )

cat("Erwartungswert, wenn man nur den besten Banditen spielt: \n")
print( mw[K] )

cat("Insgesamt ausbezahlter Betrag: \n")
print( sum(rewards, na.rm = TRUE), digits = dgts )

cat("Insgesamt ausbezahlter Betrag pro Spiel: \n")
print( sum(rewards, na.rm = TRUE) / N, digits = dgts )

cat("Mittelwerte der Auszahlungsbeträge pro Spiel (für alle Banditen): \n")
mw.rewards <- apply(X = rewards, FUN = function(rw){m <- mean(rw, na.rm = TRUE);
                      if(is.nan(m)) return(0) else return(m)}, MARGIN = 1 )
print( mw.rewards, digits = dgts )

if(ret){
  return(list(bandits = bandits, rewards = rewards, 
              playsPerBandit = playsPerBandit, 
              sumOfRewardsPerBandit = sumOfRewardsPerBandit,
              meanRewardPerBandit = meanRewardPerBandit))
} else return()

Der vollständige Quelltext

Nachdem alle Bestandteile des Algorithmus ausführlich erklärt wurden, zeigt das folgende Listing den vollständigen Quelltext der Funktion mab(), er wird in 5 Teile untergliedert:

1. Prüfung der Eingabewerte
2. Interne Funktionen
3. Initialisierungen
4. Eigentliche Simulation
5. Ausgaben und Rückgabewert.

Wie oben besprochen benötigt man einige statistische Funktionen, die hier nicht nochmals aufgeführt werden; sie verbergen sich hinter dem Befehl source("StatFunctions.R") in Zeile 2. Andere R-Pakete werden nicht benötigt.

# Inkludieren der statistischen Funktionen
source("StatFunctions.R")

mab <- function(K = 9L, 
                       N = 2700L, 
                       selection_strategy = 1,
                       # Liste der Strategien:
                       # strategies <- list(random = random, greedy = greedy, eps_greedy = eps_greedy,
                       #    eps_first = eps_first, eps_decreasing = eps_decreasing)
                       eps = 0.1,
                       ret = FALSE,
                       normalize = TRUE,
                       debug = FALSE,
                       dgts = 3){
                       
  # 1. Prüfung der Eingabewerte
  stopifnot( is.numeric(selection_strategy), identical(length(selection_strategy), 1L) )
  stopifnot( eps >= 0, eps <= 1)

  # 2. Interne Funktionen
  # ---------------------------------------------------------------------------
  
  random <- function(){
    return( sample(x = Ks, size = 1, replace = TRUE) )
  }
  
  greedy <- function(){
    # Zuerst alle K Banditen einmal spielen, 
    # dann jeweils besten auswählen;
    # falls nicht eindeutig: zufällige Auswahl
    if(t <= K){
      return(t)
    } else {
      # in meanRewardPerBandit[ , t-1]: Maximum suchen
      bestScore <- max(meanRewardPerBandit[ , t-1])
      idx <- which(meanRewardPerBandit[ , t-1] == bestScore)
      
      if(identical(length(idx), 1L)){
        return(idx)
      } else {
        return(sample(x = idx, size = 1, replace = TRUE))
      }
    }
  }
  
  eps_greedy <- function(){
    if(runif(n = 1) < eps){
      return(random())
    } else {
      return(greedy())
    }
  }
  
  eps_first <- function(){
    if(t / N < eps){
      return(random())
    } else {
      return(greedy())
    }
  }
  
  eps_decreasing <- function(){
    # interne Funktion: linear, abnehmend
    decr_function <- function(t){
      return( 2 * eps * (1 - t / N) )
    }
    
    if(runif(n = 1) < decr_function(t)){    # Zufallszahl < Fkt.wert -> "random"
      return(random())
    } else {          # "greedy"
      return(greedy())
    }
  }

  # play()
  # Eingabewert: Index des gewählten Banditen
  play <- function(b){
    bandit <- bandits[[b]]
    return( sample(x = bandit$value, size = 1, replace = FALSE, prob = bandit$prob) )
  }

  # 3. Initialisierungen: Banditen, Datenelemente
  # ---------------------------------------------------------------------------
  
  # Für Iterationen:
  Ks <- seq_len(K)
  # ts <- seq_len(N) wird nicht benötigt wg. Iteration (2:N)
  
  # Liste der Banditen erzeugen:
  bandits <- vector(mode = "list", length = K)
  prob <- c(0.4, 0.4, 0.2)
  for(k in Ks){
    value <- c(-2, 1, k + 1)
    bandits[[k]] <-  data.frame(prob = prob, value = value)
  }
  if(normalize){
    for(k in Ks){
      bandits[[k]] <- normalizeRV(bandits[[k]])
    }
  }
  
  # Strategien:
  # Alle internen Funktionen zu einer Liste zusammenfassen:
  strategies <- list(random = random, greedy = greedy, eps_greedy = eps_greedy,
                     eps_first = eps_first, eps_decreasing = eps_decreasing)
  strategy <- strategies[[selection_strategy]]
  
  # KxN-Matrizen für Auswertung
  rewards <- matrix(data = NA_integer_, nrow = K, ncol = N)
  sumOfRewardsPerBandit <- matrix(data = 0, nrow = K, ncol = N)
  playsPerBandit <- matrix(data = 0, nrow = K, ncol = N)
  meanRewardPerBandit <- matrix(data = 0, nrow = K, ncol = N)

  # 4. Simulation
  # ---------------------------------------------------------------------------

  # t = 1 gesondert behandeln wg. update
  t <- 1    # ACHTUNG: wird in den strategies benötigt!
  k <- strategy()
  rewards[k, 1] <- play(k)
  
  # update:
  sumOfRewardsPerBandit[k, 1] <- rewards[k, 1]
  playsPerBandit[k, 1] <- 1
  meanRewardPerBandit[k, 1] <- rewards[k, 1]
  
  #  2. Schleife 2...N

  for(t in (2:N)){
    k <- strategy()
    rewards[k, t] <- play(k)

    sumOfRewardsPerBandit[-k, t] <- sumOfRewardsPerBandit[-k, t-1]    # So??
    sumOfRewardsPerBandit[k, t] <- sumOfRewardsPerBandit[k, t-1] + rewards[k, t]
    
    playsPerBandit[-k, t] <- playsPerBandit[-k, t-1]
    playsPerBandit[k, t] <- playsPerBandit[k, t-1] + 1
    
    meanRewardPerBandit[-k, t] <- meanRewardPerBandit[-k, t-1]
    meanRewardPerBandit[k, t] <- sumOfRewardsPerBandit[k, t] / playsPerBandit[k, t]
  }    # Ende for(t in (2:N))

  # 5. Ausgaben und Rückgabewert
  # ---------------------------------------------------------------------------
  
  if(debug){    # Ausgabe der Matrizen
    cat("rewards: \n")
    print(rewards, digits = dgts)
    
    cat("sumOfRewardsPerBandit: \n")
    print(sumOfRewardsPerBandit, digits = dgts)
    
    cat("playsPerBandit: \n")
    print(playsPerBandit)
    
    cat("meanRewardPerBandit: \n")
    print(meanRewardPerBandit, digits = dgts)
  }
  
  cat("gewählte Strategie: \n")
  cat(names(strategies)[selection_strategy], "\n")
  
  cat("Anzahlen, wie oft die K Banditen gespielt wurden: \n")
  print(playsPerBandit[ , N])

  cat("theoretische Mittelwerte \"Gewinn pro Spiel\" (für alle Banditen): \n")
  mw <- sapply(X = bandits, FUN = meanValue)
  print(mw)
  
  cat("Erwartungswert für den ausbezahlten Betrag, wenn man alle Banditen gleich oft spielt: \n")
  print( sum(mw) / K )
  
  cat("Erwartungswert, wenn man nur den besten Banditen spielt: \n")
  print( mw[K] )
  
  cat("Insgesamt ausbezahlter Betrag: \n")
  print( sum(rewards, na.rm = TRUE), digits = dgts )
  
  cat("Insgesamt ausbezahlter Betrag pro Spiel: \n")
  print( sum(rewards, na.rm = TRUE) / N, digits = dgts )
  
  cat("Mittelwerte der Auszahlungsbeträge pro Spiel (für alle Banditen): \n")
  mw.rewards <- apply(X = rewards, FUN = function(rw){return( mean(rw, na.rm = TRUE))}, MARGIN = 1 )
  print( mw.rewards, digits = dgts )
  
  if(ret){
    return(list(bandits = bandits, rewards = rewards, 
                playsPerBandit = playsPerBandit, 
                sumOfRewardsPerBandit = sumOfRewardsPerBandit,
                meanRewardPerBandit = meanRewardPerBandit))
  } else return()
}

Damit sollen nun zwei einfache Simulationen gezeigt werden:

1. Die Auswahl-Strategie random(),
2. die Auswahl-Strategie greedy(),

wobei jeweils K = 2 und N = 10 gewählt wird und debug = TRUE gesetzt wird.

mab(K = 2, N = 10, debug = TRUE, selection_strategy = 1)

# rewards: 
#   [,1] [,2]  [,3] [,4] [,5] [,6]  [,7] [,8]  [,9] [,10]
# [1,] 0.598   NA    NA -1.2 -1.2 -1.2    NA -1.2 0.598    NA
# [2,]    NA 1.64 0.613   NA   NA   NA 0.613   NA    NA  1.64
# sumOfRewardsPerBandit: 
#   [,1]  [,2]  [,3]   [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
# [1,] 0.598 0.598 0.598 -0.598 -1.79 -2.99 -2.99 -4.18 -3.59 -3.59
# [2,] 0.000 1.644 2.257  2.257  2.26  2.26  2.87  2.87  2.87  4.51
# playsPerBandit: 
#   [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    2    3    4    4    5    6     6
# [2,]    0    1    2    2    2    2    3    3    3     4
# meanRewardPerBandit: 
#   [,1]  [,2]  [,3]   [,4]   [,5]   [,6]   [,7]   [,8]   [,9]  [,10]
# [1,] 0.598 0.598 0.598 -0.299 -0.598 -0.747 -0.747 -0.837 -0.598 -0.598
# [2,] 0.000 1.644 1.128  1.128  1.128  1.128  0.956  0.956  0.956  1.128
# gewählte Strategie: 
#   random 
# Anzahlen, wie oft die K Banditen gespielt wurden: 
#   [1] 6 4
# theoretische Mittelwerte "Gewinn pro Spiel" (für alle Banditen): 
#   [1] 0.0 0.2
# Erwartungswert für den ausbezahlten Betrag, wenn man alle Banditen gleich oft spielt: 
#   [1] 0.1
# Erwartungswert, wenn man nur den besten Banditen spielt: 
#   [1] 0.2
# Insgesamt ausbezahlter Betrag: 
#   [1] 0.927
# Insgesamt ausbezahlter Betrag pro Spiel: 
#   [1] 0.0927
# Mittelwerte der Auszahlungsbeträge pro Spiel (für alle Banditen): 
#   [1] -0.598  1.128

mab(K = 2, N = 10, debug = TRUE, selection_strategy = 2)

# rewards: 
#   [,1]  [,2]   [,3] [,4]   [,5] [,6]   [,7]  [,8]   [,9] [,10]
# [1,] 0.598    NA     NA -1.2     NA -1.2     NA    NA     NA    NA
# [2,]    NA 0.613 -0.935   NA -0.935   NA -0.935 0.613 -0.935 0.613
# sumOfRewardsPerBandit: 
#   [,1]  [,2]   [,3]   [,4]   [,5]  [,6]  [,7]  [,8]  [,9] [,10]
# [1,] 0.598 0.598  0.598 -0.598 -0.598 -1.79 -1.79 -1.79 -1.79 -1.79
# [2,] 0.000 0.613 -0.322 -0.322 -1.257 -1.26 -2.19 -1.58 -2.51 -1.90
# playsPerBandit: 
#   [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,]    1    1    1    2    2    3    3    3    3     3
# [2,]    0    1    2    2    3    3    4    5    6     7
# meanRewardPerBandit: 
#   [,1]  [,2]   [,3]   [,4]   [,5]   [,6]   [,7]   [,8]   [,9]  [,10]
# [1,] 0.598 0.598  0.598 -0.299 -0.299 -0.598 -0.598 -0.598 -0.598 -0.598
# [2,] 0.000 0.613 -0.161 -0.161 -0.419 -0.419 -0.548 -0.316 -0.419 -0.272
# gewählte Strategie: 
#   greedy 
# Anzahlen, wie oft die K Banditen gespielt wurden: 
#   [1] 3 7
# theoretische Mittelwerte "Gewinn pro Spiel" (für alle Banditen): 
#   [1] 0.0 0.2
# Erwartungswert für den ausbezahlten Betrag, wenn man alle Banditen gleich oft spielt: 
#   [1] 0.1
# Erwartungswert, wenn man nur den besten Banditen spielt: 
#   [1] 0.2
# Insgesamt ausbezahlter Betrag: 
#   [1] -3.69
# Insgesamt ausbezahlter Betrag pro Spiel: 
#   [1] -0.369
# Mittelwerte der Auszahlungsbeträge pro Spiel (für alle Banditen): 
#   [1] -0.598 -0.272

An den Matrizen meanRewardPerBandit und rewards kann man hier leicht nachvollziehen, wie der greedy-Algorithmus den nächsten Banditen auswählt.

Einstiegspunkte für Erweiterungen

Zuletzt sollen einige Möglichkeiten besprochen werden, wie man den Algorithmus verändern oder ergänzen kann.

Andere Zufallsvariablen für die Banditen

Die Zufallsvariablen, die die Banditen beschreiben, sind sehr speziell gewählt und können leicht verändert werden.

Sofern man sich an die Konvention hält, wie hier Zufallsvariable mit Hilfe von Dataframes modelliert werden, muss man nur die beiden Spalten value und prob in den Dataframes anpassen. (Im kompletten Quelltext in den Zeilen 87 bis 97.)

Möchte man Zufallsvariablen anders als hier modellieren, muss man auch die interne Funktion play() entsprechend anpassen.

Neue Strategien

Die Liste der Strategien mit den Auswahl-Kriterien für den nächsten Banditen kann natürlich beliebig erweitert werden. Man muss dazu nur die Implementierung der Strategie einfügen (mit der Konvention für den Rückgabewert) und muss die neue Strategie in die Liste strategies aufnehmen.

Komplikationen ergeben sich erst, wenn das Auswahl-Kriterium nicht mit den hier verwendeten Matrizen formuliert werden kann. Dann muss man die entsprechenden Datenelemente hinzufügen und deren Update implementieren.

Graphiken

Die Rückgabewerte enthalten sämtliche Informationen über die Zwischenergebnisse einer Simulation. Vergleicht man etwa die Ausgabe der Matrizen oben mit den Diagrammen aus Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen, kann man schnell Skripte für die graphische Ausgabe entwickeln. Und es lassen sich leicht andere Fragestellungen umsetzen, die etwa ganze Folgen von Simulationen betreffen und deren Ergebnisse darstellen.