Practicum Cognitie

One Armed Bandits

One Armed Bandits zijn gokautomaten met één hendel. Elke automaat keert een andere gemiddelde reward uit. Stel dat er vier automaten zijn waar onze agent aan kan trekken, we modelleren ze als vier verschillende acties: $$A := \{a_1, a_2, a_3, a_4\}$$ Elke bandit deelt met een proportie tussen 0 en 1 een reward van precies één uit aan de hand van de functie \(R(a)\). De verwachte reward voor bandit \(n\) is gelijk aan deze proportie en wordt gegeven door: $$E[R(a_n)]$$

Het doel van de agent binnen het n-armed bandit probleem is, zoals in elk Reinforcement Learning probleem, om zoveel mogelijk reward binnen te krijgen in een beperkt aantal pogingen. De agent zal daarbij een afweging moeten maken tussen exploration en exploitation: je wilt zo goed mogelijk schatten hoeveel een bandit gemiddeld oplevert, om een optimnale keuze te maken, maar tegelijkertijd zoveel mogelijk reward binnenhalen en dus geen tijd verdoen met 'slechte' automaten.

\({Q}(a_n)\) is een schatting van de verwachte reward \(E[R(a_n)]\), namelijk de gemiddelde uitkering tot nu toe: de totale uitgekeerde reward gedeeld door het aantal keren dat de automaat is uitgeprobeerd (\(k_a\)): $$ {Q}(a) = \frac{r_1 + r_2 + \cdots + r_{k_a}}{k_a} $$

Welke regel code van de 'update'-functie voert deze formule uit?

Het exploration-exploration-dilemma gaat over hoe de agent de \(Q\)-functie gebruikt om een actie te kiezen. De greedy strategie, is het kiezen van de actie die tot nu toe de hoogste gemiddelde reward heeft

$$\DeclareMathOperator*{\argmax}{\arg\!\max} a = \argmax_{a} {Q}(a) $$

Waarom is het suboptimaal om altijd de greedy-strategie te volgen?

Het algoritme wat hier geimplementeerd is, is de \(epsilon\)-greedy-strategie: met een kans van \(0 \leq \epsilon \leq 1 \) doet de agent een random actie. Met een kans van 1-\(\epsilon\) doet de agent de greedy actie.

Probeer dit algoritme een paar keer uit: druk op 'Run' en dan op 'play'. Is de hoeveelheid totale reward na 200 steps elke keer hetzelfde? Waarom wel/niet?

Iedere keer dat je het experiment opnieuw opstart, verandert de echte verwachtingsreward \(E[R(a)]\) van de bandits. De uitkomst van de experimenten is dus niet iedere keer precies hetzelfde, ookal zijn de instellingen hetzelfde.

Run hetzelfde experiment vijf keer en gebruik de 'get data'-functie om de gemiddelde reward voor elke tijdstap te exporteren naar een spreadsheet in Google Docs. Gebruik Google Docs om een grafiek te maken van de vijf experimenten. Maak ook een grafiek van het gemiddelde over alle experimenten. Dit doe je als volgt:
Druk op get_data om een nieuw venster met de data te openen, druk op ctrl+a om alles te selecteren, gebruik ctrl+c om alles te kopieren, ga naar je spreadsheet en gebruik ctrl+v om de data te plakken. Tik in een cel '=AVERAGE(A1:E1)' om het gemiddelde uit te rekenen van alle cellen van A1 t/m E1). Je kan een grafiek maken door een hele kolom te selecteren die je wilt plotten (druk bijvoorbeeld op de 'F' boven de kolom) en vervolgens 'insert -> 'Chart' te doen)

De agent selecteert nu met een proportie van \((1 - \epsilon)\) de bandit met het de hoogste gemiddelde opbrengst tot-nu-toe, dit is een \(\epsilon\)-greedy strategie: $$\DeclareMathOperator*{\argmax}{\arg\!\max} \argmax_{a} {Q}(a) $$

Wat denk je dat er gebeurt met de gemiddelde reward als je epsilon groter of kleiner maakt? Hoe verhoudt epsilon zich tot de exploration-exploitation-balans?

Pas epsilon aan naar 0.1 en 0.5 en maak een gemiddelde grafiek over 5 experimenten, net zoals in opdracht 1c. Wat valt gebeurt er met de gemiddele opbrengst?

Er is een probleem met de \(\epsilon\)-greedy strategie die we tot nu toe gebruikt hebben. In het begin van je experiment is de schatting \({Q}(a)\) nog onnauwkeurig, dus wil je veel uitproberen. Later echter is je schatting beter en wil je die informatie uitbuiten zonder te veel te verkennen. Het ligt dus voor de hand om niet of minder te verkennen naarmate de tijd verstrijkt.

Een manier om dit te doen is de Epsilon-first strategie, waarin je de eerste \(n\) trials altijd willekeurige acties selecteert, en daarna altijd de bandit met de hoogste gemiddelde opbrengst.

Implementeer de Epsilon-first, doe dit door de eerste regel van de Action Selection-functie aan te passen. Tip: het aantal steps dat je tot nu toe hebt genomen zit in de variabele t

Draai nu een paar experimenten met een verschillend aantal stappen (\(n\)) voor epsilon-first. Wat valt je op aan de gemiddelde-reward grafiek? Wat is een goede \(n\) om reward te optimaliseren?

Een andere strategie is die van Epsilon-decreasing: dan laat je de kans dat je agent een random actie doet afhangen van het aantal steps dat al hij heeft gedaan. Je kan dit bijvoorbeeld doen door bij je update-functie epsilon met een discount-proportie \(0 < d < 1\) te vermenigvuldigen: $$\epsilon_{t} = d \cdot \epsilon_{t-1}$$ Als je epsilon dan initialiseert op 1, is deze na 50 stappen: $$0.95^{50} = 0.07$$ en na 100 stappen: $$0.95^{100} = 0.006$$

Implementeer het \(\epsilon\)-decreasing algoritme. Voeg aan de Update-functie een regel toe die EPSILON instelt op 0.95 * EPSILON. Initialiseer EPSILON op 1. Zorg dat regel 1 van de Action selection er weer zo uit ziet:
if (chance(EPSILON))
Run een paar experimenten en vergelijk ze met de standaard \(\epsilon\)-greedy strategie uit opdracht 4. Werk deze strategie beter?

Dit was les 1 van het practicum, ga door naar les 2.