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 forsterkningslæring

bookOff-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 rette 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. Her forsøker man å forbedre beslutningstakingen ved å bruke data samlet inn under en annen atferd. Det er fortsatt utforskning — men den styres av ekstern erfaring i stedet for 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 bane som starter fra en gitt tilstand StS_t og følger en gitt 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 banen 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 banen faktisk ble generert av en annen policy — atferdspolicyen bb. For å bruke denne banen 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 banen 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 kanselleres overgangssannsynlighetene 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 (dekningforutsetningen).

Praktiske hensyn

Varians ved importance sampling

Å inkludere importance sampling er konseptuelt enkelt. Vi justerer den estimerte aksjonsverdifunksjonen q(s,a)q(s, a) ved å vekte hver observert retur med den tilsvarende 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 denne 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 atferdspolicyen og målpolicyen er svært forskjellige.

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 returer, 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.

Politikker

Som i on-policy-tilfellet, brukes ε\varepsilon-grådige politikker for både målpolitikk π(as)\pi(a | s) og atferdspolitikk b(as)b(a | s).

Ved første øyekast virker det naturlig å gjøre målpolitikken fullt ut grådig — til slutt er det jo en grådig politikk vi ønsker. I praksis gir dette imidlertid et stort problem: hvis det på et tidspunkt er slik at π(as)=0\pi(a | s) = 0 for handlingen som faktisk ble valgt av atferdspolitikken, blir importance sampling-forholdet ρ\rho lik null, og resten av episoden blir i praksis forkastet.

Ved å bruke en liten ε\varepsilon (for eksempel ε=0.01\varepsilon = 0.01) i målpolitikken, sikrer vi at π(as)>0\pi(a | s) > 0 for alle handlinger, slik at ρ\rho aldri kollapser til null midt i en episode. Når treningen er ferdig, er det enkelt å konvertere den lærte ε\varepsilon‑grådige politikken til en strengt grådig politikk. Som ved on-policy-læring bør ε\varepsilon avta i atferdspolitikken, men denne gangen er det hovedsakelig for numerisk stabilitet, siden ρ\rho fortsatt kan bli null midt i en episode 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

Suggested prompts:

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

bookOff-policy Monte Carlo-kontroll

Sveip for å vise menyen

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 rette 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. Her forsøker man å forbedre beslutningstakingen ved å bruke data samlet inn under en annen atferd. Det er fortsatt utforskning — men den styres av ekstern erfaring i stedet for 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 bane som starter fra en gitt tilstand StS_t og følger en gitt 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 banen 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 banen faktisk ble generert av en annen policy — atferdspolicyen bb. For å bruke denne banen 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 banen 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 kanselleres overgangssannsynlighetene 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 (dekningforutsetningen).

Praktiske hensyn

Varians ved importance sampling

Å inkludere importance sampling er konseptuelt enkelt. Vi justerer den estimerte aksjonsverdifunksjonen q(s,a)q(s, a) ved å vekte hver observert retur med den tilsvarende 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 denne 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 atferdspolicyen og målpolicyen er svært forskjellige.

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 returer, 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.

Politikker

Som i on-policy-tilfellet, brukes ε\varepsilon-grådige politikker for både målpolitikk π(as)\pi(a | s) og atferdspolitikk b(as)b(a | s).

Ved første øyekast virker det naturlig å gjøre målpolitikken fullt ut grådig — til slutt er det jo en grådig politikk vi ønsker. I praksis gir dette imidlertid et stort problem: hvis det på et tidspunkt er slik at π(as)=0\pi(a | s) = 0 for handlingen som faktisk ble valgt av atferdspolitikken, blir importance sampling-forholdet ρ\rho lik null, og resten av episoden blir i praksis forkastet.

Ved å bruke en liten ε\varepsilon (for eksempel ε=0.01\varepsilon = 0.01) i målpolitikken, sikrer vi at π(as)>0\pi(a | s) > 0 for alle handlinger, slik at ρ\rho aldri kollapser til null midt i en episode. Når treningen er ferdig, er det enkelt å konvertere den lærte ε\varepsilon‑grådige politikken til en strengt grådig politikk. Som ved on-policy-læring bør ε\varepsilon avta i atferdspolitikken, men denne gangen er det hovedsakelig for numerisk stabilitet, siden ρ\rho fortsatt kan bli null midt i en episode 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