Off-Policy Monte Carlo-Controle

Hoewel on-policy methoden leren door hetzelfde beleid te volgen en te verbeteren, introduceren off-policy methoden een variatie: ze leren over het ene beleid (het doelbeleid) terwijl ze een ander beleid volgen (het gedragsbeleid). Deze scheiding is krachtig — het stelt ons in staat om een doelbeleid te evalueren of te verbeteren zonder het daadwerkelijk te hoeven volgen tijdens het verzamelen van data.

Vergelijking

Laten we teruggaan naar de ijssalon uit het vorige hoofdstuk. Jij en je vriend lopen naar binnen, en opnieuw zijn de drie bekende smaken beschikbaar: chocolade, vanille en aardbei. Chocolade is jouw persoonlijke favoriet, en je eerste instinct is om deze te bestellen. Maar deze winkel is nieuw voor je, en je weet niet zeker of chocolade de juiste keuze is. Gelukkig is je vriend een bekende ijsliefhebber die bijna elke zaak in de stad heeft bezocht. Je vraagt om hun mening. "Chocolade hier is oké," zegt je vriend, "maar geloof me — de aardbei is uitzonderlijk." Dus, op basis van hun ervaring, besluit je je gebruikelijke keuze over te slaan en in plaats daarvan voor aardbei te gaan.

Die beslissing — vertrouwen op de ervaring van iemand anders om je eigen keuze te sturen — is de essentie van off-policy methoden. Je probeert je besluitvorming te verbeteren met gegevens die zijn verzameld op basis van het gedrag van iemand anders. Het blijft verkennen — maar het wordt geleid door externe ervaring in plaats van je eigen.

Belang van steekproeftrekking

Omdat de agent de gedragsstrategie volgt tijdens het genereren van episodes, moeten we rekening houden met het verschil tussen wat de gedragsstrategie genereert en wat de doelstrategie zou genereren. Dit is waar importance sampling van pas komt.

Importance sampling biedt een manier om de opbrengsten die onder de gedragsstrategie zijn waargenomen aan te passen, zodat ze geldige schattingen zijn voor de doelstrategie.

Laten we kijken naar een traject dat begint vanuit een bepaalde toestand $S_t$ en een bepaalde strategie $\pi$ volgt totdat de episode eindigt op tijdstip $T$. We observeren specifiek:

Wat is nu de kans dat dit traject zich voordoet onder een strategie $\pi$? Dit hangt af van zowel de actie-kansen van de strategie als de overgangsdynamiek van de omgeving:

Stel nu dat het traject daadwerkelijk is gegenereerd door een andere strategie — de gedragsstrategie $b$. Om dit traject correct te gebruiken om verwachtingen onder de doelstrategie $\pi$ te schatten, moeten we rekening houden met hoe veel waarschijnlijker of minder waarschijnlijk deze reeks acties zou zijn onder $\pi$ vergeleken met $b$.

Hier komt de importance sampling-ratio in beeld. Deze wordt gedefinieerd als de relatieve waarschijnlijkheid van het traject onder de twee strategieën:

Uiteindelijk vallen de overgangskansen weg, omdat beide strategieën in dezelfde omgeving opereren, en de waarde van $\rho$ hangt alleen af van de strategieën, niet van de omgeving.

Waarom Dit Belangrijk Is

De verhouding $\rho$ geeft aan hoe we de opbrengst $G_t$​, waargenomen onder het gedragspolicy, kunnen herwegen zodat het een onbevooroordeelde schatting wordt van wat de opbrengst zou zijn geweest onder het doelpolicy:

Met andere woorden, ook al zijn de gegevens verzameld met behulp van $b$, kunnen we nog steeds de verwachte opbrengsten onder $\pi$ schatten — mits $b$ een niet-nul kans geeft aan elke actie die $\pi$ zou kunnen nemen (dekkingsveronderstelling).

Praktische Overwegingen

Variantie van importance sampling

Het toepassen van importance sampling is conceptueel eenvoudig. We passen de geschatte actie-waardefunctie $q(s, a)$ aan door elke waargenomen opbrengst te wegen met de bijbehorende importance sampling-ratio. De eenvoudigste formulering ziet er als volgt uit:

waarbij:

• $\rho_i(s, a)$ de importance sampling-ratio is voor de $i$-de traject die start vanuit $(s, a)$;
• $Returns_i(s, a)$ de opbrengst is van dat traject;
• $N(s, a)$ het aantal keren is dat $(s, a)$ is bezocht.

Dit staat bekend als gewone importance sampling. Het levert een onbevooroordeelde schatting van $q(s, a)$, maar kan lijden onder zeer hoge variantie, vooral wanneer het gedrag en het doelbeleid sterk van elkaar verschillen.

Om het variantieprobleem te verminderen, kunnen we een stabieler alternatief gebruiken: gewogen importance sampling. Deze methode normaliseert de importance-gewichten, waardoor de invloed van grote ratio's wordt verminderd en het leren stabieler wordt:

In deze versie is de teller dezelfde gewogen som van opbrengsten, maar de noemer is nu de som van de importance-gewichten in plaats van een eenvoudige telling.

Dit maakt de schatting bevooroordeeld, maar de bias neemt af naarmate er meer steekproeven worden verzameld. In de praktijk heeft gewogen importance sampling de voorkeur vanwege de aanzienlijk lagere variantie en grotere numerieke stabiliteit.

Beleidsvormen

Net als in het on-policy geval gebruiken we $\varepsilon$-greedy beleidsvormen voor zowel het doelbeleid $\pi(a | s)$ als het gedragsbeleid $b(a | s)$.

Op het eerste gezicht lijkt het logisch om het doelbeleid volledig greedy te maken — uiteindelijk is ons doel een greedy beleid. In de praktijk veroorzaakt dit echter een groot probleem: als op enig moment $\pi(a | s) = 0$ voor de actie die daadwerkelijk door het gedragsbeleid is gekozen, wordt de importance sampling-ratio $\rho$ nul en wordt het resterende deel van de episode effectief genegeerd.

Door een kleine $\varepsilon$ (bijvoorbeeld $\varepsilon = 0.01$) in het doelbeleid te gebruiken, zorgen we ervoor dat $\pi(a | s) > 0$ voor elke actie, zodat $\rho$ nooit midden in een episode naar nul zakt. Zodra de training is voltooid, is het eenvoudig om het geleerde $\varepsilon$-greedy beleid om te zetten naar een strikt greedy beleid. Net als bij on-policy leren, moet $\varepsilon$ in het gedragsbeleid worden afgebouwd, maar dit is nu vooral voor numerieke stabiliteit, omdat $\rho$ nog steeds naar nul kan dalen tijdens een episode, vanwege de manier waarop getallen in computers worden weergegeven.

Pseudocode