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

Ein Algorithmus zur Simulation von N Spielen am k-armigen Banditen (multi-armed bandit) wird in R implementiert. Der Algorithmus erlaubt die Auswahl einer Strategie zur Wahl des n├Ąchsten zu spielenden Armes. Als Strategien stehen die im Artikel "Der mehrarmige Bandit (multi-armed bandit): Simulationen mit einfachen Algorithmen vorgestellten Strategien zur Auswahl, es k├Ânnen aber leicht weitere Strategien implementiert und eingef├╝gt werden.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

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

Algorithmus Kriterium f├╝r die Auswahl des n├Ąchsten Banditen interne Funktion Index
random Der n├Ąchste Bandit wird immer zuf├Ąllig ausgew├Ąhlt.random() 1
greedy Es wird derjenige Bandit ausgew├Ąhlt, der bisher den h├Âchsten Gewinn pro Spiel geliefert hat. greedy() 2
╬Á-greedy Bei jeder Selektion wird eine Zufalls-Entscheidung getroffen: mit Wahrscheinlichkeit ╬Á wird der random-Algorithmus eingesetzt und mit Wahrscheinlichkeit 1 - ╬Á der greedy-Algorithmus. eps_greedy() 3
╬Á-first Zuerst wird bei einem Bruchteil ╬Á an Spielen der n├Ąchste Bandit zuf├Ąllig ausgew├Ąhlt, danach wird der greedy-Algorithmus eingesetzt. eps_first() 4
╬Á-decreasing Wie bei ╬Á-greedy wird eine Zufalls-Entscheidung getroffen, ob der random oder der greedy-Algorithmus eingesetzt wird; aber es wird eine monoton fallende Funktion vorgegeben, die den Verlauf der Wahrscheinlichkeit bestimmt. eps_decreasing() 5

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.