Opdracht 3: The Climbing Game

Inleiding

In deze opdracht gaan we bekijken hoe agents kunnen leren in een 'coöperative multi-agent game'. Deze spellen worden gekarakteriseerd door hun payoff matrix: de dimensies bevatten de acties die de agents kunnen doen, en de cellen de rewards die de agents ontvangen [p.282, W.Flake, 1998]. In deze opdracht beschouwen we een zeer interessante twee-player game: 'the climbing game' [Claus & Boutilier, 1998]. De payoff matrix voor dit spel wordt gegeven door:

In andere woorden, als Agent 1 de actie 'a₂' kiest, en Agent 2 de actie 'a₃', is de reward voor beide agents 0. In dit spel is het moeilijk om te convergeren naar de optimale joint-actie (a₁,a₁), omdat er een hoge negatieve reward is in het geval er miscommunicatie plaatsvindt. Stel Agent 1 kiest 'a₁', en Agent 2 kiest 'a₂', dan is er een hoge negatieve reward voor beide agenten (-30). Als een agent echter actie 'a₃' kiest is het niet zo ernstig als er miscommunicatie plaatsvindt, het laagste wat je kan krijgen is '0'.

Dit spel wordt de climbing game genoemd omdat de agenten gaan 'klimmen' in de payoff matrix. Initieel zullen de agenten waarschijnlijk eerst de veilige strategie (a₃,a₃) gaan exploiteren. Echter, als ze eenmaal geconvergeerd zijn naar deze strategie, zal Agent 2 actie a₂ gaan kiezen als er ook maar enige vorm van exploratie is. Vervolgens als dit eenmaal een stabiele strategie is, kan Agent 1 ook a₂ gaan kiezen, zodat de joint reward uiteindelijk naar 7 zal convergeren. Vanaf hier is het moeilijk om uiteindelijk de top te bereiken, dus de joint actie (a₂,a₂) is waarschijnlijk de laatste stabiele strategie. We gaan kijken hoe we dit kunnen modelleren door middel van Q-learning [Sutton and Barto, 1998] (deze zijn sommige van jullie al eerder tegengekomen bij imperatief programmeren).

De opdracht

We gaan twee lerende agenten modelleren, die beiden geen kennis hebben van de payoff matrix (het enige wat ze initieel weten is dat ze drie acties tot hun beschikking hebben: {a₁,a₂,a₃}). We kunnen dit probleem modelleren als ware het stateless is, wat inhoudt dat de formule voor het Q-learning gedeelte sterk vereenvoudigt kan worden:

Initieel wordt elke Q-waarde gezet op 0. Het updaten gaat als volgt: beiden agenten kiezen een actie (wordt zo uitgelegd hoe dit gekozen wordt), ze observeren de reward, en vervolgens updaten ze hun Q-waardes.

Het kiezen van een actie kan op verschillende manieren. Belangrijk is echter dat er een goede mix tussen exploratie/exploitatie is. We beschouwen de volgende twee manieren voor het kiezen van een actie:

• epsilon-greedy: Selecteer altijd de greedy actie (d.w.z. de actie met de hoogste Q-waarde), maar selecteer met kans epsilon een willekeurige actie (uniform verdeeld over de resterende acties).
• optimistic greedy [Sutton and Barto, 1998]: Initialiseer alle Q-waardes optimistisch (dat wil zeggen, hoger dan dat ze maximaal kunnen zijn), en selecteer altijd de greedy actie.

Implementatie

We gaan dit als volgt in Netlogo visueel modelleren. Deel het grid op in 9 vakjes die overeenkomen met de payoff matrix. We gaan een turtle maken die dit landschap gaat beklimmen, afhankelijk van de gekozen joint acties. We hebben dus in weze drie turtles: twee onzichtbare die herhaaldelijk het spel gaan uitvoeren, en één zichtbare die afhankelijk van het resultaat gaat lopen op het grid. Dit kan op de volgende manier:

1. Laat actie a₁ corresponderen met het getal 1, a₂ met 2 en a₃ met 3.
2. Bereken de gemiddelde actie waarde van Agent 1 door te middelen over de laatste n gekozen acties (noem dit m₁). Doe hetzelfde voor Agent 2 (noem dit m₂).
3. Laat de turtle lopen naar (m₁,m₂) in het veld.

Laat in je model zo veel mogelijk parameters instelbaar voor de gebruikers. Experimenteer met de leersnelheid en de exploratie factor.

Belangrijk: Gezien de aard van deze opdracht (minder visueel, meer theoretisch), is het belangrijk om de 'information tab' zinvol in te vullen (hier zal op gelet worden). Het is handig als je voor iedere vraag een aparte sectie maakt in de documentatie. Bespreek de volgende punten:

1. Wat voor soort klimgedrag levert 'epsilon-greedy' selectie strategie op? Hoe is dit afhankelijk van de exploratie factor 'epsilon' en de leersnelheid 'alfa'? Verklaar je antwoord met behulp van de formules uit de opgave.
2. Wat voor soort klimgedrag levert 'optimistic greedy' selectie strategie op? Hoe is dit afhankelijk van de leersnelheid 'alfa' en de initialisatie van de Q-waarden? Verklaar je antwoord met behulp van de formules uit de opgave.
3. Leg concreet uit op welke manier de 'optimistic greedy' selectie strategie exploratie/exploitatie afdwingt.
4. Welke selectie strategie heeft voor jou de voorkeur, en welke parameter instellingen zou je gebruiken? Verklaar je antwoord.
5. Zou je het probleem anders aanpakken als een agent wel de actie van de andere agent kan observeren? Verklaar welke aanpak je (mogelijk) zou toepassen.
6. Kun je suggesties geven om het agent gedrag te veranderen zodanig dat de optimale joint actie snel en betrouwbaar bereikt kan worden? Je kunt bijvoorbeeld denken aan een andere manier dan Q-learning, of een andere selectie strategie. Let op dat de agenten (initieel) geen kennis hebben van de payoff matrix, dat ze de actie van de andere agent niet kunnen observeren, dat ze niet mogen overleggen en dat ze initieel geen kennis hebben van het gedrag van de andere agent (ze kunnen hoogstens het een en ander afleiden van de ontvangen rewards).