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 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 St og følger en gitt policy π til episoden avsluttes ved tid T. Spesifikt observerer vi:
At,St+1,At+1,...,STHva er sannsynligheten for at denne banen oppstår under en policy π? Det avhenger både av policyens handlingssannsynligheter og miljøets overgangsdynamikk:
p(trajectory∣π)=k=t∏T−1π(Ak∣Sk)p(Sk+1∣Sk,Ak)Anta nå at banen faktisk ble generert av en annen policy — atferdspolicyen b. For å bruke denne banen til å estimere forventninger under målpolicyen π, må vi ta hensyn til hvor mye mer eller mindre sannsynlig denne sekvensen av handlinger ville vært under π sammenlignet med b.
Dette er hvor importance sampling-forholdet kommer inn. Det er definert som den relative sannsynligheten for banen under de to policyene:
ρ=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)Til slutt kanselleres overgangssannsynlighetene ut, siden begge policyene opererer i det samme miljøet, og verdien til ρ avhenger kun av policyene, ikke miljøet.
Hvorfor dette er viktig
Forholdet ρ forteller oss hvordan vi kan omvekte avkastningen Gt observert under atferdspolicyen slik at det blir et forventningsrett estimat av hva avkastningen ville vært under målpolicyen:
Eπ[Gt]=Eb[ρ⋅Gt]Med andre ord, selv om dataene ble samlet inn ved bruk av b, kan vi fortsatt estimere forventet avkastning under π — forutsatt at b gir ikke-null sannsynlighet til hver handling som π kan ta (dekningforutsetningen).
Praktiske hensyn
Varians ved importance sampling
Å inkludere importance sampling er konseptuelt enkelt. Vi justerer den estimerte aksjonsverdifunksjonen q(s,a) ved å vekte hver observert retur med den tilsvarende importance sampling-ratioen. Den enkleste formuleringen ser slik ut:
q(s,a)=N(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)hvor:
- ρi(s,a) er importance sampling-ratioen for den i-te trajektorien som starter fra (s,a);
- Returnsi(s,a) er returen fra denne trajektorien;
- N(s,a) er antall ganger (s,a) har blitt besøkt.
Dette kalles ordinær importance sampling. Det gir et upartisk estimat av 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)∑i=0N(s,a)ρi(s,a)⋅Returnsi(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 ε-grådige politikker for både målpolitikk π(a∣s) og atferdspolitikk 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 π(a∣s)=0 for handlingen som faktisk ble valgt av atferdspolitikken, blir importance sampling-forholdet ρ lik null, og resten av episoden blir i praksis forkastet.
Ved å bruke en liten ε (for eksempel ε=0.01) i målpolitikken, sikrer vi at π(a∣s)>0 for alle handlinger, slik at ρ aldri kollapser til null midt i en episode. Når treningen er ferdig, er det enkelt å konvertere den lærte ε‑grådige politikken til en strengt grådig politikk. Som ved on-policy-læring bør ε avta i atferdspolitikken, men denne gangen er det hovedsakelig for numerisk stabilitet, siden ρ fortsatt kan bli null midt i en episode på grunn av hvordan tall representeres i datamaskiner.
Pseudokode
Takk for tilbakemeldingene dine!
Spør AI
Spør AI
Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår
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-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 St og følger en gitt policy π til episoden avsluttes ved tid T. Spesifikt observerer vi:
At,St+1,At+1,...,STHva er sannsynligheten for at denne banen oppstår under en policy π? Det avhenger både av policyens handlingssannsynligheter og miljøets overgangsdynamikk:
p(trajectory∣π)=k=t∏T−1π(Ak∣Sk)p(Sk+1∣Sk,Ak)Anta nå at banen faktisk ble generert av en annen policy — atferdspolicyen b. For å bruke denne banen til å estimere forventninger under målpolicyen π, må vi ta hensyn til hvor mye mer eller mindre sannsynlig denne sekvensen av handlinger ville vært under π sammenlignet med b.
Dette er hvor importance sampling-forholdet kommer inn. Det er definert som den relative sannsynligheten for banen under de to policyene:
ρ=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)Til slutt kanselleres overgangssannsynlighetene ut, siden begge policyene opererer i det samme miljøet, og verdien til ρ avhenger kun av policyene, ikke miljøet.
Hvorfor dette er viktig
Forholdet ρ forteller oss hvordan vi kan omvekte avkastningen Gt observert under atferdspolicyen slik at det blir et forventningsrett estimat av hva avkastningen ville vært under målpolicyen:
Eπ[Gt]=Eb[ρ⋅Gt]Med andre ord, selv om dataene ble samlet inn ved bruk av b, kan vi fortsatt estimere forventet avkastning under π — forutsatt at b gir ikke-null sannsynlighet til hver handling som π kan ta (dekningforutsetningen).
Praktiske hensyn
Varians ved importance sampling
Å inkludere importance sampling er konseptuelt enkelt. Vi justerer den estimerte aksjonsverdifunksjonen q(s,a) ved å vekte hver observert retur med den tilsvarende importance sampling-ratioen. Den enkleste formuleringen ser slik ut:
q(s,a)=N(s,a)∑i=0N(s,a)ρi(s,a)⋅Returnsi(s,a)hvor:
- ρi(s,a) er importance sampling-ratioen for den i-te trajektorien som starter fra (s,a);
- Returnsi(s,a) er returen fra denne trajektorien;
- N(s,a) er antall ganger (s,a) har blitt besøkt.
Dette kalles ordinær importance sampling. Det gir et upartisk estimat av 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)∑i=0N(s,a)ρi(s,a)⋅Returnsi(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 ε-grådige politikker for både målpolitikk π(a∣s) og atferdspolitikk 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 π(a∣s)=0 for handlingen som faktisk ble valgt av atferdspolitikken, blir importance sampling-forholdet ρ lik null, og resten av episoden blir i praksis forkastet.
Ved å bruke en liten ε (for eksempel ε=0.01) i målpolitikken, sikrer vi at π(a∣s)>0 for alle handlinger, slik at ρ aldri kollapser til null midt i en episode. Når treningen er ferdig, er det enkelt å konvertere den lærte ε‑grådige politikken til en strengt grådig politikk. Som ved on-policy-læring bør ε avta i atferdspolitikken, men denne gangen er det hovedsakelig for numerisk stabilitet, siden ρ fortsatt kan bli null midt i en episode på grunn av hvordan tall representeres i datamaskiner.
Pseudokode
Takk for tilbakemeldingene dine!