slide 2
----------
Het grid probleem speelt zich af in een NxN grid waarin agents een startpositie hebben (in dit voorbeeld : een agent in elke hoek) en een eindpositie,
ook goal state genaamd. (in dit voorbeeld de hoek over de diagonaal).
Het is de bedoeling dat elke agent een pad vind naar zijn goal state door zo weinig mogelijk te botsen.
Botsingen komen voor wanneer 2 agents naar dezelde positie willen gaan, beiden krijgen dan een penalty en worden teruggestuurd naar hun oorspronkelijke positie.
Het is nu de bedoeling om de agents hun pad te laten leren en hierbij een evenwicht te zoeken tussen exploratie en exploitatie,
om enerzijds niet vast te raken in lokale maxima, maar ook niet eindeloos te verkennen.
slide 3
----------
Een mogelijke oplossing tot dit probleem is het reinforcement learning algoritme genaamd Q-learning algoritme.
We spreken van een Markov decision process omdat de reacties van de omgeving alleen afhangen van de vorige staat van
de agent en de actie die hij gekozen heeft en geen oudere acties die hij mogelijk uitgevoerd heeft.
Het algoritme is dus geen supervised learning want de agents moeten zelf hun acties kiezen.
De agents moet een zo groot mogelijke reward proberen krijgen, maar om een belang te hechten aan immediate of future rewards gebruiken we
een discount factor gelegen tussen 0 en 1 waarbij hoe dichter de discount factor bij 1 hoe meer belang wordt gehecht aan toekomstige rewards.
We zoeken een optimale policy (regel voor het selecteren van acties) zodat de bekomen reward gemaximaliseerd wordt.
In Q-learning wordt gebruik gemaakt van een 2-dimensionale tabel per agent waarin deze zijn State-Action paren bijhoudt en hun Q-waarde, Q(x,a).
Het Q-learning algoritme werkt door het berekenen van een schatting van de Q* functie en door Q-values te updaten gebaseerd op de
gekozen acties van de agent en de gekregen rewards. Dit updaten gebeurt door het verschil te nemen van de immediate reward en discounted
waarde van de volgende state met de Q-value van het huidige state-action paar.
r + gamma x V* (y) − Q*(x, a)
Doordat agents steed de actie nemen met de grootste Q-value noemen we dit een greedy policy.
Er kan geexperimenteerd worden met het kiezen van de actie om bijvoorbeeld meer exploratie te verkrijgen.
Op uiteindelijk een optimale Q functie te vinden moet de agent verschillende acties in alle states veel uitproberen, en het is dus aangeraden
om niet meteen steeds de optimale actie te kiezen om een betere exploratie van de omgeving te verkijgen.
We bieden voor ons algoritme de mogelijkheid van partial observability aan, dit betekent dat de agents het aantal iteraties weten en
hierdoor kunnen we de epsilon parameter introduceren. die bepaald hoe vaak een random actie ipv de optimale actie gekozen wordt.
Deze kans op een random actie wordt kleiner naargelang er meerdere iteraties gebeuren omdat exploratie in het begin belangrijker is
dan later waar exploitatie de bovenhand zou moeten nemen. Partial observability is voor sommige praktische toepassingen echter niet mogelijk en hierdoor
zullen er dan ook meer iteraties nodig zijn om een stabiele oplossing te vinden.
slide 4
---------
In kort , elke agent houdt dus een tabel bij waarin een Q waarde wordt bijgehouden voor elk mogelijke transitie van state naar state door een bepaalde actie.
Deze Q waarden worden constant geupdate terwijl de agents het gridworld probleem uitvoeren. Ze observeren in welke state ze zijn , beslissen welke actie
ze gaan uitvoeren en krijgen een reward. Aan de hand van deze reward updaten ze de Q-waarde en veranderd de state waarin ze zich bevinden naar de nieuwe state.