Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Off-Policy Monte Carlo-Kontroll | Monte Carlo-metoder
Introduksjon til Forsterkende Læring
course content

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
2. Multi-Armet Bandittproblem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-læring

book
Off-Policy Monte Carlo-Kontroll

Mens on-policy-metoder lærer ved å følge og forbedre den samme policyen, introduserer off-policy-metoder en vri: de lærer om én policy (målpolicyen) mens de følger en annen (atferdspolicyen). Denne adskillelsen er kraftfull — det gjør det mulig å evaluere eller forbedre en målpolicy uten å faktisk måtte følge den under datainnsamlingen.

Analogi

La oss gå tilbake til iskrembutikken fra forrige kapittel. Du og vennen din går inn, og igjen tilbys de tre kjente smakene: sjokolade, vanilje og jordbær. Sjokolade er din personlige favoritt, og din første impuls er å bestille den. Men denne butikken er ny for deg, og du er ikke helt sikker på om sjokolade er det riktige valget. Heldigvis er vennen din en fremtredende iskremelsker som har besøkt nesten alle butikker i byen. Du spør om deres mening. "Sjokoladen her er grei," sier de, "men stol på meg — jordbæren er eksepsjonell." Så, basert på deres erfaring, bestemmer du deg for å droppe ditt vanlige valg og gå for jordbær i stedet.

Den avgjørelsen — å stole på andres erfaring for å veilede egne valg — er kjernen i off-policy-metoder. Du forsøker å forbedre beslutningstakingen din ved å bruke data samlet inn under andres atferd. Det er fortsatt utforskning — men den er styrt av ekstern erfaring i stedet for din egen.

Importance Sampling

Fordi agenten følger atferdspolicyen under generering av episoder, må vi ta hensyn til forskjellen mellom hva atferdspolicyen genererer og hva målpolicyen ville generert. Det er her importance sampling kommer inn.

Importance sampling gir en metode for å justere avkastningen observert under atferdspolicyen slik at de blir gyldige estimater for målpolicyen.

La oss se på en trajektorie som starter fra en gitt tilstand StS_t og følger en policy π\pi til episoden avsluttes ved tid TT. Spesifikt observerer vi:

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

Hva er sannsynligheten for at denne trajektorien oppstår under en policy π\pi? Det avhenger både av policyens handlingssannsynligheter og miljøets overgangsdynamikk:

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)

Anta nå at trajektorien faktisk ble generert av en annen policy — atferdspolicyen bb. For å bruke denne trajektorien til å estimere forventninger under målpolicyen π\pi, må vi ta hensyn til hvor mye mer eller mindre sannsynlig denne sekvensen av handlinger ville vært under π\pi sammenlignet med bb.

Dette er hvor importance sampling-forholdet kommer inn. Det er definert som den relative sannsynligheten for trajektorien under de to policyene:

ρ=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)}

Til slutt kansellerte overgangssannsynlighetene hverandre ut, siden begge policyene opererer i det samme miljøet, og verdien til ρ\rho avhenger kun av policyene, ikke miljøet.

Hvorfor dette er viktig

Forholdet ρ\rho forteller oss hvordan vi kan omvekte avkastningen GtG_t observert under atferdspolicyen slik at det blir et forventningsrett estimat av hva avkastningen ville vært under målpolicyen:

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

Med andre ord, selv om dataene ble samlet inn ved bruk av bb, kan vi fortsatt estimere forventet avkastning under π\pi — forutsatt at bb gir ikke-null sannsynlighet til hver handling som π\pi kan ta (dekningforutsetning).

Praktiske hensyn

Varians ved importance sampling

Å inkludere importance sampling er konseptuelt enkelt. Vi justerer den estimerte handlingsverdifunksjonen q(s,a)q(s, a) ved å vekte hver observert retur med den tilhørende importance sampling-ratioen. Den enkleste formuleringen ser slik ut:

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)}

hvor:

  • ρi(s,a)\rho_i(s, a) er importance sampling-ratioen for den ii-te trajektorien som starter fra (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) er returen fra den trajektorien;
  • N(s,a)N(s, a) er antall ganger (s,a)(s, a) har blitt besøkt.

Dette kalles ordinær importance sampling. Det gir et upartisk estimat av q(s,a)q(s, a), men kan ha svært høy varians, spesielt når atferds- og målpolitikken skiller seg betydelig.

For å redusere variansen kan vi bruke et mer stabilt alternativ: vektet importance sampling. Denne metoden normaliserer importance-vektene, noe som reduserer effekten av store ratioer og gir mer stabil læring:

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)}

I denne versjonen er telleren den samme vektede summen av returene, men nevneren er nå summen av importance-vektene, i stedet for et enkelt antall.

Dette gjør estimatet partisk, men biasen avtar etter hvert som flere utvalg samles inn. I praksis foretrekkes vektet importance sampling på grunn av betydelig lavere varians og større numerisk stabilitet.

Policyer

Som i on-policy-tilfellet, la oss bruke ε\varepsilon-grådige policyer for både målpolicy π(as)\pi(a | s) og atferdspolicy b(as)b(a | s).

Ved første øyekast virker det naturlig å gjøre målpolicyen fullt ut grådig — til syvende og sist er vårt endelige mål en grådig policy. I praksis fører dette imidlertid til et stort problem: hvis det på noe tidspunkt er slik at π(as)=0\pi(a | s) = 0 for handlingen som faktisk ble valgt av atferdspolicyen, blir importance sampling-forholdet ρ\rho lik null, og resten av episoden blir effektivt forkastet.

Ved å bruke en liten ε\varepsilon (for eksempel ε=0.01\varepsilon = 0.01) i målpolicyen, sikrer vi at π(as)>0\pi(a | s) > 0 for hver handling, slik at ρ\rho aldri kollapser til null midt i episoden. Når treningen er ferdig, er det trivielt å konvertere den lærte ε\varepsilon‑grådige policyen til en strengt grådig policy. Som ved on-policy-læring bør avtagende ε\varepsilon brukes i atferdspolicyen, men denne gangen er det hovedsakelig for numerisk stabilitet, siden ρ\rho fortsatt kan falle til null midt i episoden på grunn av hvordan tall representeres i datamaskiner.

Pseudokode

question mark

Hva er hensikten med importance sampling?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 6

Spør AI

expand

Spør AI

ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

course content

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
2. Multi-Armet Bandittproblem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-læring

book
Off-Policy Monte Carlo-Kontroll

Mens on-policy-metoder lærer ved å følge og forbedre den samme policyen, introduserer off-policy-metoder en vri: de lærer om én policy (målpolicyen) mens de følger en annen (atferdspolicyen). Denne adskillelsen er kraftfull — det gjør det mulig å evaluere eller forbedre en målpolicy uten å faktisk måtte følge den under datainnsamlingen.

Analogi

La oss gå tilbake til iskrembutikken fra forrige kapittel. Du og vennen din går inn, og igjen tilbys de tre kjente smakene: sjokolade, vanilje og jordbær. Sjokolade er din personlige favoritt, og din første impuls er å bestille den. Men denne butikken er ny for deg, og du er ikke helt sikker på om sjokolade er det riktige valget. Heldigvis er vennen din en fremtredende iskremelsker som har besøkt nesten alle butikker i byen. Du spør om deres mening. "Sjokoladen her er grei," sier de, "men stol på meg — jordbæren er eksepsjonell." Så, basert på deres erfaring, bestemmer du deg for å droppe ditt vanlige valg og gå for jordbær i stedet.

Den avgjørelsen — å stole på andres erfaring for å veilede egne valg — er kjernen i off-policy-metoder. Du forsøker å forbedre beslutningstakingen din ved å bruke data samlet inn under andres atferd. Det er fortsatt utforskning — men den er styrt av ekstern erfaring i stedet for din egen.

Importance Sampling

Fordi agenten følger atferdspolicyen under generering av episoder, må vi ta hensyn til forskjellen mellom hva atferdspolicyen genererer og hva målpolicyen ville generert. Det er her importance sampling kommer inn.

Importance sampling gir en metode for å justere avkastningen observert under atferdspolicyen slik at de blir gyldige estimater for målpolicyen.

La oss se på en trajektorie som starter fra en gitt tilstand StS_t og følger en policy π\pi til episoden avsluttes ved tid TT. Spesifikt observerer vi:

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

Hva er sannsynligheten for at denne trajektorien oppstår under en policy π\pi? Det avhenger både av policyens handlingssannsynligheter og miljøets overgangsdynamikk:

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)

Anta nå at trajektorien faktisk ble generert av en annen policy — atferdspolicyen bb. For å bruke denne trajektorien til å estimere forventninger under målpolicyen π\pi, må vi ta hensyn til hvor mye mer eller mindre sannsynlig denne sekvensen av handlinger ville vært under π\pi sammenlignet med bb.

Dette er hvor importance sampling-forholdet kommer inn. Det er definert som den relative sannsynligheten for trajektorien under de to policyene:

ρ=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)}

Til slutt kansellerte overgangssannsynlighetene hverandre ut, siden begge policyene opererer i det samme miljøet, og verdien til ρ\rho avhenger kun av policyene, ikke miljøet.

Hvorfor dette er viktig

Forholdet ρ\rho forteller oss hvordan vi kan omvekte avkastningen GtG_t observert under atferdspolicyen slik at det blir et forventningsrett estimat av hva avkastningen ville vært under målpolicyen:

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

Med andre ord, selv om dataene ble samlet inn ved bruk av bb, kan vi fortsatt estimere forventet avkastning under π\pi — forutsatt at bb gir ikke-null sannsynlighet til hver handling som π\pi kan ta (dekningforutsetning).

Praktiske hensyn

Varians ved importance sampling

Å inkludere importance sampling er konseptuelt enkelt. Vi justerer den estimerte handlingsverdifunksjonen q(s,a)q(s, a) ved å vekte hver observert retur med den tilhørende importance sampling-ratioen. Den enkleste formuleringen ser slik ut:

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)}

hvor:

  • ρi(s,a)\rho_i(s, a) er importance sampling-ratioen for den ii-te trajektorien som starter fra (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) er returen fra den trajektorien;
  • N(s,a)N(s, a) er antall ganger (s,a)(s, a) har blitt besøkt.

Dette kalles ordinær importance sampling. Det gir et upartisk estimat av q(s,a)q(s, a), men kan ha svært høy varians, spesielt når atferds- og målpolitikken skiller seg betydelig.

For å redusere variansen kan vi bruke et mer stabilt alternativ: vektet importance sampling. Denne metoden normaliserer importance-vektene, noe som reduserer effekten av store ratioer og gir mer stabil læring:

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)}

I denne versjonen er telleren den samme vektede summen av returene, men nevneren er nå summen av importance-vektene, i stedet for et enkelt antall.

Dette gjør estimatet partisk, men biasen avtar etter hvert som flere utvalg samles inn. I praksis foretrekkes vektet importance sampling på grunn av betydelig lavere varians og større numerisk stabilitet.

Policyer

Som i on-policy-tilfellet, la oss bruke ε\varepsilon-grådige policyer for både målpolicy π(as)\pi(a | s) og atferdspolicy b(as)b(a | s).

Ved første øyekast virker det naturlig å gjøre målpolicyen fullt ut grådig — til syvende og sist er vårt endelige mål en grådig policy. I praksis fører dette imidlertid til et stort problem: hvis det på noe tidspunkt er slik at π(as)=0\pi(a | s) = 0 for handlingen som faktisk ble valgt av atferdspolicyen, blir importance sampling-forholdet ρ\rho lik null, og resten av episoden blir effektivt forkastet.

Ved å bruke en liten ε\varepsilon (for eksempel ε=0.01\varepsilon = 0.01) i målpolicyen, sikrer vi at π(as)>0\pi(a | s) > 0 for hver handling, slik at ρ\rho aldri kollapser til null midt i episoden. Når treningen er ferdig, er det trivielt å konvertere den lærte ε\varepsilon‑grådige policyen til en strengt grådig policy. Som ved on-policy-læring bør avtagende ε\varepsilon brukes i atferdspolicyen, men denne gangen er det hovedsakelig for numerisk stabilitet, siden ρ\rho fortsatt kan falle til null midt i episoden på grunn av hvordan tall representeres i datamaskiner.

Pseudokode

question mark

Hva er hensikten med importance sampling?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 6
some-alt