Off-Policy Monte Carlo-controle
Waar 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.
Analogie
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 is hier oké," zegt je vriend, "maar geloof me — de aardbei is uitzonderlijk." 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 een ander. Het blijft exploratie — maar het wordt geleid door externe ervaring in plaats van je eigen.
Importance Sampling
Omdat de agent het gedragsbeleid volgt tijdens het genereren van episodes, moeten we rekening houden met het verschil tussen wat het gedragsbeleid genereert en wat het doelbeleid zou genereren. Dit is waar importance sampling van pas komt.
Importance sampling biedt een methode om de opbrengsten die zijn waargenomen onder het gedragbeleid aan te passen, zodat ze geldige schattingen zijn voor het doelbeleid.
Beschouw een traject dat begint vanuit een bepaalde toestand St en een bepaald beleid π volgt totdat de episode eindigt op tijdstip T. We observeren specifiek:
At,St+1,At+1,...,STWat is nu de kans dat dit traject zich voordoet onder een beleid π? Dit hangt af van zowel de actieprobabiliteiten van het beleid als de transitiedynamiek van de omgeving:
p(trajectory∣π)=k=t∏T−1π(Ak∣Sk)p(Sk+1∣Sk,Ak)Stel nu dat het traject daadwerkelijk is gegenereerd door een ander beleid — het gedragbeleid b. Om dit traject correct te gebruiken voor het schatten van verwachtingen onder het doelbeleid π, moeten we rekening houden met hoe veel waarschijnlijker of minder waarschijnlijk deze reeks acties zou zijn onder π vergeleken met b.
Hier komt de importance sampling-ratio in beeld. Deze wordt gedefinieerd als de relatieve waarschijnlijkheid van het traject onder de twee beleids:
ρ=p(trajectory∣b)p(trajectory∣π)=k=t∏T−1b(Ak∣Sk)p(Sk+1∣Sk,Ak)π(Ak∣Sk)p(Sk+1∣Sk,Ak)=k=t∏T−1b(Ak∣Sk)π(Ak∣Sk)Uiteindelijk vallen de overgangswaarschijnlijkheden weg, omdat beide beleids in dezelfde omgeving opereren, en de waarde van ρ hangt alleen af van de beleids, niet van de omgeving.
Waarom Dit Belangrijk Is
De ratio ρ geeft aan hoe de opbrengst Gt die is waargenomen onder het gedragbeleid moet worden herwogen, zodat het een onvertekende schatting wordt van wat de opbrengst zou zijn geweest onder het doelbeleid:
Eπ[Gt]=Eb[ρ⋅Gt]Met andere woorden, ook al zijn de gegevens verzameld met b, kunnen we nog steeds de verwachte opbrengsten onder π schatten — mits b een niet-nul kans toekent aan elke actie die π zou kunnen nemen (de dekkingsaanname).
Praktische Overwegingen
Varianties bij Importance Sampling
Het toepassen van importance sampling is conceptueel eenvoudig. De geschatte actie-waardefunctie q(s,a) wordt aangepast door elke waargenomen opbrengst te wegen met de bijbehorende importance sampling-ratio. De eenvoudigste formulering is als volgt:
q(s,a)=N(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)waarbij:
- ρi(s,a) de importance sampling-ratio is voor de i-de traject vanaf (s,a);
- Returnsi(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 doelbeleid sterk van elkaar verschillen.
Om het variantieprobleem te beperken, kan een stabieler alternatief worden gebruikt: gewogen importance sampling. Deze methode normaliseert de importance-gewichten, waardoor de invloed van grote ratio's wordt verminderd en het leerproces stabieler wordt:
q(s,a)=∑i=0N(s,a)ρi(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)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.
Hierdoor wordt de schatting bevooroordeeld, maar deze 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.
Beleidsregels
Net als in het on-policy geval gebruiken we ε-greedy beleidsregels voor zowel de doelbeleidsregel π(a∣s) als de gedragsbeleidsregel b(a∣s).
Op het eerste gezicht lijkt het logisch om de doelbeleidsregel volledig greedy te maken — uiteindelijk is ons doel een greedy beleidsregel. In de praktijk veroorzaakt dit echter een groot probleem: als op enig moment π(a∣s)=0 voor de actie die daadwerkelijk door de gedragsbeleidsregel is gekozen, wordt de importance sampling-verhouding ρ nul en wordt het resterende deel van de episode feitelijk genegeerd.
Door een kleine ε (bijvoorbeeld ε=0.01) te gebruiken in de doelbeleidsregel, zorgen we ervoor dat π(a∣s)>0 voor elke actie, zodat ρ nooit midden in een episode naar nul zakt. Zodra de training is voltooid, is het eenvoudig om de geleerde ε-greedy beleidsregel om te zetten naar een strikt greedy variant. Net als bij on-policy leren, moet ε in de gedragsbeleidsregel worden afgebouwd, maar dit is nu vooral voor numerieke stabiliteit, omdat ρ nog steeds naar nul kan dalen tijdens een episode, vanwege de manier waarop getallen in computers worden weergegeven.
Pseudocode
Bedankt voor je feedback!
Vraag AI
Vraag AI
Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.
Can you explain the difference between ordinary and weighted importance sampling in more detail?
Why does using a fully greedy target policy cause problems in off-policy learning?
Can you summarize the key advantages of off-policy methods compared to on-policy methods?
Awesome!
Completion rate improved to 2.7
Off-Policy Monte Carlo-controle
Veeg om het menu te tonen
Waar 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.
Analogie
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 is hier oké," zegt je vriend, "maar geloof me — de aardbei is uitzonderlijk." 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 een ander. Het blijft exploratie — maar het wordt geleid door externe ervaring in plaats van je eigen.
Importance Sampling
Omdat de agent het gedragsbeleid volgt tijdens het genereren van episodes, moeten we rekening houden met het verschil tussen wat het gedragsbeleid genereert en wat het doelbeleid zou genereren. Dit is waar importance sampling van pas komt.
Importance sampling biedt een methode om de opbrengsten die zijn waargenomen onder het gedragbeleid aan te passen, zodat ze geldige schattingen zijn voor het doelbeleid.
Beschouw een traject dat begint vanuit een bepaalde toestand St en een bepaald beleid π volgt totdat de episode eindigt op tijdstip T. We observeren specifiek:
At,St+1,At+1,...,STWat is nu de kans dat dit traject zich voordoet onder een beleid π? Dit hangt af van zowel de actieprobabiliteiten van het beleid als de transitiedynamiek van de omgeving:
p(trajectory∣π)=k=t∏T−1π(Ak∣Sk)p(Sk+1∣Sk,Ak)Stel nu dat het traject daadwerkelijk is gegenereerd door een ander beleid — het gedragbeleid b. Om dit traject correct te gebruiken voor het schatten van verwachtingen onder het doelbeleid π, moeten we rekening houden met hoe veel waarschijnlijker of minder waarschijnlijk deze reeks acties zou zijn onder π vergeleken met b.
Hier komt de importance sampling-ratio in beeld. Deze wordt gedefinieerd als de relatieve waarschijnlijkheid van het traject onder de twee beleids:
ρ=p(trajectory∣b)p(trajectory∣π)=k=t∏T−1b(Ak∣Sk)p(Sk+1∣Sk,Ak)π(Ak∣Sk)p(Sk+1∣Sk,Ak)=k=t∏T−1b(Ak∣Sk)π(Ak∣Sk)Uiteindelijk vallen de overgangswaarschijnlijkheden weg, omdat beide beleids in dezelfde omgeving opereren, en de waarde van ρ hangt alleen af van de beleids, niet van de omgeving.
Waarom Dit Belangrijk Is
De ratio ρ geeft aan hoe de opbrengst Gt die is waargenomen onder het gedragbeleid moet worden herwogen, zodat het een onvertekende schatting wordt van wat de opbrengst zou zijn geweest onder het doelbeleid:
Eπ[Gt]=Eb[ρ⋅Gt]Met andere woorden, ook al zijn de gegevens verzameld met b, kunnen we nog steeds de verwachte opbrengsten onder π schatten — mits b een niet-nul kans toekent aan elke actie die π zou kunnen nemen (de dekkingsaanname).
Praktische Overwegingen
Varianties bij Importance Sampling
Het toepassen van importance sampling is conceptueel eenvoudig. De geschatte actie-waardefunctie q(s,a) wordt aangepast door elke waargenomen opbrengst te wegen met de bijbehorende importance sampling-ratio. De eenvoudigste formulering is als volgt:
q(s,a)=N(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)waarbij:
- ρi(s,a) de importance sampling-ratio is voor de i-de traject vanaf (s,a);
- Returnsi(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 doelbeleid sterk van elkaar verschillen.
Om het variantieprobleem te beperken, kan een stabieler alternatief worden gebruikt: gewogen importance sampling. Deze methode normaliseert de importance-gewichten, waardoor de invloed van grote ratio's wordt verminderd en het leerproces stabieler wordt:
q(s,a)=∑i=0N(s,a)ρi(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)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.
Hierdoor wordt de schatting bevooroordeeld, maar deze 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.
Beleidsregels
Net als in het on-policy geval gebruiken we ε-greedy beleidsregels voor zowel de doelbeleidsregel π(a∣s) als de gedragsbeleidsregel b(a∣s).
Op het eerste gezicht lijkt het logisch om de doelbeleidsregel volledig greedy te maken — uiteindelijk is ons doel een greedy beleidsregel. In de praktijk veroorzaakt dit echter een groot probleem: als op enig moment π(a∣s)=0 voor de actie die daadwerkelijk door de gedragsbeleidsregel is gekozen, wordt de importance sampling-verhouding ρ nul en wordt het resterende deel van de episode feitelijk genegeerd.
Door een kleine ε (bijvoorbeeld ε=0.01) te gebruiken in de doelbeleidsregel, zorgen we ervoor dat π(a∣s)>0 voor elke actie, zodat ρ nooit midden in een episode naar nul zakt. Zodra de training is voltooid, is het eenvoudig om de geleerde ε-greedy beleidsregel om te zetten naar een strikt greedy variant. Net als bij on-policy leren, moet ε in de gedragsbeleidsregel worden afgebouwd, maar dit is nu vooral voor numerieke stabiliteit, omdat ρ nog steeds naar nul kan dalen tijdens een episode, vanwege de manier waarop getallen in computers worden weergegeven.
Pseudocode
Bedankt voor je feedback!