Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Leer Off-policy Monte Carlo-controle | Monte Carlo-Methoden
Introductie tot Reinforcement Learning
course content

Cursusinhoud

Introductie tot Reinforcement Learning

Introductie tot Reinforcement Learning

1. Kernprincipes van RL
2. Multi-Armed Bandit Probleem
3. Dynamisch Programmeren
4. Monte Carlo-Methoden
5. Temporale Verschil Leren

book
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 neiging 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 prima," 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.

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.

Belangrijksheidsweging biedt een methode om de opbrengsten die zijn waargenomen onder het gedragspolicy aan te passen, zodat ze geldige schattingen zijn voor het doelpolicy.

Beschouw een traject dat begint vanuit een bepaalde toestand StS_t en een bepaalde policy π\pi volgt totdat de episode eindigt op tijdstip TT. Specifiek observeren we:

At,St+1,At+1,...,STA_t, S_{t+1}, A_{t+1}, ..., S_{T}

Wat is nu de kans dat dit traject zich voordoet onder een policy π\pi? Dit hangt af van zowel de actieprobabiliteiten van de policy als de overgangsdynamiek van de omgeving:

p(trajectoryπ)=k=tT1π(AkSk)p(Sk+1Sk,Ak)p(trajectory | \pi) = \prod_{k=t}^{T-1} \pi(A_k | S_k)p(S_{k+1} | S_k, A_k)

Stel nu dat het traject daadwerkelijk is gegenereerd door een andere policy — het gedragspolicy bb. Om dit traject correct te gebruiken voor het schatten van verwachtingen onder het doelpolicy π\pi, moeten we rekening houden met hoe veel waarschijnlijker of minder waarschijnlijk deze reeks acties zou zijn onder π\pi vergeleken met bb.

Hier komt de belangrijksheidsweging-ratio in beeld. Deze wordt gedefinieerd als de relatieve waarschijnlijkheid van het traject onder de twee policies:

ρ=p(trajectoryπ)p(trajectoryb)=k=tT1π(AkSk)p(Sk+1Sk,Ak)b(AkSk)p(Sk+1Sk,Ak)=k=tT1π(AkSk)b(AkSk)\rho = \frac{p(trajectory | \pi)}{p(trajectory | b)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)p(S_{k+1} | S_k, A_k)}{b(A_k | S_k)p(S_{k+1} | S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}

Uiteindelijk vallen de overgangswaarschijnlijkheden weg, omdat beide policies in dezelfde omgeving opereren, en de waarde van ρ\rho hangt alleen af van de policies, niet van de omgeving.

Waarom Dit Belangrijk Is

De ratio ρ\rho geeft aan hoe de opbrengst GtG_t​ die is waargenomen onder het gedragspolicy moet worden herwogen zodat het een onvertekende schatting wordt van wat de opbrengst zou zijn geweest onder het doelpolicy:

Eπ[Gt]=Eb[ρGt]\def\E{\operatorname{\mathbb{E}}} \E_\pi[G_t] = \E_b[\rho \cdot G_t]

Met andere woorden, ook al zijn de gegevens verzameld met bb, kunnen we nog steeds de verwachte opbrengsten onder π\pi schatten — mits bb een niet-nul kans toekent aan elke actie die π\pi 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)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)=i=0N(s,a)ρi(s,a)Returnsi(s,a)N(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{N(s, a)}

waarbij:

  • ρi(s,a)\rho_i(s, a) de importance sampling-ratio is voor de ii-de traject vanaf (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) de opbrengst is van dat traject;
  • N(s,a)N(s, a) het aantal keren is dat (s,a)(s, a) is bezocht.

Dit staat bekend als gewone importance sampling. Het levert een onbevooroordeelde schatting van q(s,a)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 leren stabieler wordt:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)i=0N(s,a)ρi(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{\sum_{i=0}^{N(s, a)} \rho_i(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.

Beleid

Net als in het on-policy geval gebruiken we ε\varepsilon-greedy beleid voor zowel het doelbeleid π(as)\pi(a | s) als het gedragsbeleid b(as)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 π(as)=0\pi(a | s) = 0 voor de actie die daadwerkelijk werd uitgevoerd door het gedragsbeleid, wordt de importance sampling-ratio ρ\rho nul en wordt het resterende deel van de episode effectief genegeerd.

Door een kleine ε\varepsilon (bijvoorbeeld ε=0.01\varepsilon = 0.01) te gebruiken in het doelbeleid, zorgen we ervoor dat π(as)>0\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 deze keer is dat 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

question mark

Wat is het doel van belanghebbendheidsbemonstering?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 6

Vraag AI

expand

Vraag AI

ChatGPT

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

course content

Cursusinhoud

Introductie tot Reinforcement Learning

Introductie tot Reinforcement Learning

1. Kernprincipes van RL
2. Multi-Armed Bandit Probleem
3. Dynamisch Programmeren
4. Monte Carlo-Methoden
5. Temporale Verschil Leren

book
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 neiging 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 prima," 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.

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.

Belangrijksheidsweging biedt een methode om de opbrengsten die zijn waargenomen onder het gedragspolicy aan te passen, zodat ze geldige schattingen zijn voor het doelpolicy.

Beschouw een traject dat begint vanuit een bepaalde toestand StS_t en een bepaalde policy π\pi volgt totdat de episode eindigt op tijdstip TT. Specifiek observeren we:

At,St+1,At+1,...,STA_t, S_{t+1}, A_{t+1}, ..., S_{T}

Wat is nu de kans dat dit traject zich voordoet onder een policy π\pi? Dit hangt af van zowel de actieprobabiliteiten van de policy als de overgangsdynamiek van de omgeving:

p(trajectoryπ)=k=tT1π(AkSk)p(Sk+1Sk,Ak)p(trajectory | \pi) = \prod_{k=t}^{T-1} \pi(A_k | S_k)p(S_{k+1} | S_k, A_k)

Stel nu dat het traject daadwerkelijk is gegenereerd door een andere policy — het gedragspolicy bb. Om dit traject correct te gebruiken voor het schatten van verwachtingen onder het doelpolicy π\pi, moeten we rekening houden met hoe veel waarschijnlijker of minder waarschijnlijk deze reeks acties zou zijn onder π\pi vergeleken met bb.

Hier komt de belangrijksheidsweging-ratio in beeld. Deze wordt gedefinieerd als de relatieve waarschijnlijkheid van het traject onder de twee policies:

ρ=p(trajectoryπ)p(trajectoryb)=k=tT1π(AkSk)p(Sk+1Sk,Ak)b(AkSk)p(Sk+1Sk,Ak)=k=tT1π(AkSk)b(AkSk)\rho = \frac{p(trajectory | \pi)}{p(trajectory | b)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)p(S_{k+1} | S_k, A_k)}{b(A_k | S_k)p(S_{k+1} | S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k | S_k)}{b(A_k | S_k)}

Uiteindelijk vallen de overgangswaarschijnlijkheden weg, omdat beide policies in dezelfde omgeving opereren, en de waarde van ρ\rho hangt alleen af van de policies, niet van de omgeving.

Waarom Dit Belangrijk Is

De ratio ρ\rho geeft aan hoe de opbrengst GtG_t​ die is waargenomen onder het gedragspolicy moet worden herwogen zodat het een onvertekende schatting wordt van wat de opbrengst zou zijn geweest onder het doelpolicy:

Eπ[Gt]=Eb[ρGt]\def\E{\operatorname{\mathbb{E}}} \E_\pi[G_t] = \E_b[\rho \cdot G_t]

Met andere woorden, ook al zijn de gegevens verzameld met bb, kunnen we nog steeds de verwachte opbrengsten onder π\pi schatten — mits bb een niet-nul kans toekent aan elke actie die π\pi 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)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)=i=0N(s,a)ρi(s,a)Returnsi(s,a)N(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{N(s, a)}

waarbij:

  • ρi(s,a)\rho_i(s, a) de importance sampling-ratio is voor de ii-de traject vanaf (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) de opbrengst is van dat traject;
  • N(s,a)N(s, a) het aantal keren is dat (s,a)(s, a) is bezocht.

Dit staat bekend als gewone importance sampling. Het levert een onbevooroordeelde schatting van q(s,a)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 leren stabieler wordt:

q(s,a)=i=0N(s,a)ρi(s,a)Returnsi(s,a)i=0N(s,a)ρi(s,a)q(s, a) = \frac{\sum_{i=0}^{N(s, a)} \rho_i(s, a) \cdot Returns_i(s, a)}{\sum_{i=0}^{N(s, a)} \rho_i(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.

Beleid

Net als in het on-policy geval gebruiken we ε\varepsilon-greedy beleid voor zowel het doelbeleid π(as)\pi(a | s) als het gedragsbeleid b(as)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 π(as)=0\pi(a | s) = 0 voor de actie die daadwerkelijk werd uitgevoerd door het gedragsbeleid, wordt de importance sampling-ratio ρ\rho nul en wordt het resterende deel van de episode effectief genegeerd.

Door een kleine ε\varepsilon (bijvoorbeeld ε=0.01\varepsilon = 0.01) te gebruiken in het doelbeleid, zorgen we ervoor dat π(as)>0\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 deze keer is dat 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

question mark

Wat is het doel van belanghebbendheidsbemonstering?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 4. Hoofdstuk 6
some-alt