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 velge jordbær i stedet.

Denne avgjørelsen — å stole på andres erfaring for å veilede ditt eget valg — er kjernen i off-policy-metoder. Du prøver å forbedre beslutningstakingen din ved å bruke data samlet inn under andres atferd. Det er fortsatt utforskning — men det styres av ekstern erfaring i stedet for din egen.

Viktighetsutvalg

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 måte å justere avkastningen observert under atferdspolicyen slik at de er gyldige estimater for målpolicyen.

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

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

Anta nå at trajektorien faktisk ble generert av en annen policy — atferdspolicyen $b$. For å bruke denne trajektorien riktig 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 $b$.

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

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

Hvorfor dette er viktig

Forholdstallet $\rho$ forteller oss hvordan vi kan omvekte avkastningen $G_t$​ observert under atferdspolitikken slik at det blir et forventningsrett estimat av hva avkastningen ville vært under målpolitikken:

Med andre ord, selv om dataene ble samlet inn ved bruk av $b$, kan vi fortsatt estimere forventet avkastning under $\pi$ — forutsatt at $b$ 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 aksjonsverdifunksjonen $q(s, a)$ ved å vekte hver observert retur med den tilhørende importance sampling-ratioen. Den enkleste formuleringen ser slik ut:

hvor:

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

Dette kalles ordinær importance sampling. Det gir et ubiasert estimat av $q(s, a)$, men kan ha svært høy varians, spesielt når atferds- og målpolitikken 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:

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

Dette gjør estimatet biasert, men biasen avtar etter hvert som flere eksempler 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, bruk $\varepsilon$-grådige policyer for både målpolicy $\pi(a | s)$ og atferdspolicy $b(a | s)$.

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

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

Pseudokode