Je hebt de afgelopen 2 lessen gekeken naar het n-armed bandits problem. Dit is een probleem waarbij de agent probeert zijn acties zo te kiezen, dat deze binnen een beperkt aantal stappen maximale reward binnensleept. De enige variabele die daarbij een rol speelt is de actie: "neem ik de bandit in het noorden, oosten, zuiden of westen." Dit is een probleem met een action-space, met slechts vier opties.
Om complexere problemen op te lossen, zoals bijvoorbeeld efficient een kamer schoon zuigen of een helikopter te besturen (zie ook hier), hangt de actie die je wilt nemen af van de omgeving. Als je met een helikopter vliegt, kun je moeilijk volhouden dat naar rechts vliegen altijd wat meer reward oplevert dan naar links, zoals met de bandits.
Wat je nodig hebt is een state space: een representatie van de huidige staat van de agent en de wereld, die zich in verschillende toestanden kunnen bevinden en daarmee om verschillende acties vragen. Je Reinforcement Learning algoritme zal niet slechts moeten moeten leren om de juiste actie te kiezen in action-space, het zal moeten leren de juiste actie te nemen, gegeven een bepaalde state van de wereld. Hij moet leren in een state-action-space.
In deze les is ons probleem een simulatie van een van NASA's Mars rovers, die onderzoek doet op Mars. De robot kan vier verschillende kanten op rijden, en zijn state (\(s_t\)) wordt gegeven door de huidige positie. Afhankelijk van de actie die de robot kiest komt hij in een nieuwe state \(s_{t+1}\). Door in elke state \(s\) de goede actie \(a\) te kiezen moet de robot een weg vinden naar een research site, waar misschien wel water of leven is! De robot krijgt pas een reward als hij de research site vindt, maar als hij tegen een obstakel aan rijdt krijgt hij een reward van -1. Als de robot de research site bereikt krijgt hij een reward gelijk aan \(100 - t\). De reward is dus hoger als de robot sneller het einde bereikt.
We moeten nu dus een schatting bijhouden van de verwachte waarden van onze acties in elke state, dus \(Q(a)\) wordt \(Q(s,a)\). Maar omdat we soms acties willen uitvoeren die leiden tot meer reward in de toekomst, bevat \(Q(s,a)\) niet alleen de verwachting van de reward in state \(s\), maar ook een schatting van de toekomstige reward: $$Q(s, a) = E[r_{s_t,a_t}] + \max_{a_{t+1}} Q(s_{t+1}, a_{t+1})$$
Hoe berekenen we deze functie nu? Als de robot aan het probleem begint weet deze nog helemaal niks. We gebruiken temporal difference learning: elke keer dat we een actie doen, kijken we hoeveel reward we daadwerkelijk krijgen (\(r_t\)) en wat de beste verwachte reward in de volgende state is. Deze tellen we bij elkaar op voor een schatting van de waarde \(Q(s,a)\). $$r_{t} + \max_a Q(s_{t+1}, a)$$ Het verschil tussen deze geschatte waarde en de huidige waarde is de temporal difference error \(\delta\) (delta). $$\delta = r_{t} + \max_a Q(s_{t+1}, a) - Q(s,a) $$ Aan de hand van dit verschil passen we de waarde van \(Q(s, a)\) aan. Omdat het mogelijk is dat we niet altijd dezelfde reward krijgen voor een actie, passen we \(Q(s,a)\) langzaam aan richting de schatting, met behulp van de learning rate \(\alpha\). Hoe hoger we \(\alpha\) instellen, hoe sneller de robot zijn gedrag aanpast. $$Q(s, a) = Q(s, a) + \alpha \cdot \delta $$ Vergelijk deze formule even met de `update' functie rechts.
Druk een keer op `run'. Wat zie je gebeuren?
Klik op een vakje om te zien wat de waarden van \(Q(s,a)\) zijn voor een paar states. Wat betekenen de witte pijltjes?
Voor elke state heb je vier state-action waarden (één voor elke mogelijke actie). Waarom krijgt elke state dan maar één kleurtje? Waar staat dit kleurtje voor denk je?
De robot vertrouwt op het feit dat hij in elke staat wel eens een willekeurige actie kiest (exploration), om zo toevallig de research site te vinden. In plaats daarvan kunnen we een techniek gebruiken die optimistic initialization heet. In plaats van de Q-tabel te initializeren met waarde 0, kunnen we hier een hogere waarde in zetten. Elke keer als de robot een actie kiest, zal hij daarom "teleurgesteld" zijn met het resultaat. Immers, zijn huidige actie leverde waarschijnlijk niks op, maar de schatting in \(Q(s,a)\) bevatte wel een hogere waarde. De robot zal dus telkens acties kiezen die hij nog niet geprobeerd heeft, omdat hij de 'hoop' heeft dat die acties een reward opleveren: hij is optimistisch.Implementeer optimistic initialization door de Q-tabel te vullen met een hogere waarde, bijvoorbeeld 10.
Zet Epsilon eens op 0 en initialiseer de Q-tabel zowel met 10 als met 0. Wanneer vindt de robot de research site? Hoe kan dit?
Draai 5 simulaties mét en zónder optimistic initialization. Zet \(\epsilon\) op 0.5 als je géén optimistic initialization gebruikt. (hint: met 'Play All' bespaar je tijd). Vergelijk de gemiddelde return per tijdstap (stop de resultaten van 'Get Data' in een grafiek).
Ga naar les 4