Off-Policy Monte Carlo-Kontrol

Mens on-policy-metoder lærer ved at følge og forbedre den samme politik, introducerer off-policy-metoder en variation: de lærer om én politik (målpolitikken), mens de følger en anden (adfærdspolitikken). Denne adskillelse er kraftfuld — det gør det muligt at evaluere eller forbedre en målpolitik uden faktisk at skulle følge den under dataindsamlingen.

Analogi

Lad os vende tilbage til isbutikken fra det forrige kapitel. Du og din ven går ind, og igen er de tre velkendte smagsvarianter på menuen: chokolade, vanilje og jordbær. Chokolade er din personlige favorit, og din første indskydelse er at bestille den. Men denne butik er ny for dig, og du er ikke helt sikker på, om det er det rigtige valg. Heldigvis er din ven en passioneret iselsker, der har besøgt næsten alle butikker i byen. Du spørger om deres mening. "Chokoladen her er okay," siger de, "men tro mig — jordbærisen er enestående." Så på baggrund af deres erfaring vælger du at springe din sædvanlige favorit over og i stedet vælge jordbær.

Denne beslutning — at stole på andres erfaring for at guide dit eget valg — er essensen af off-policy metoder. Du forsøger at forbedre din beslutningstagning ved at bruge data, der er indsamlet under en andens adfærd. Det er stadig udforskning — men det er styret af ekstern erfaring i stedet for din egen.

Importance Sampling

Fordi agenten følger adfærdsstrategien under generering af episoder, skal vi tage højde for forskellen mellem hvad adfærdsstrategien genererer og hvad målstrategien ville generere. Det er her, importance sampling kommer ind i billedet.

Importance sampling giver en metode til at justere de afkast, der observeres under adfærdsstrategien, så de er gyldige estimater for målstrategien.

Lad os se på en bane, der starter fra en bestemt tilstand $S_t$ og følger en bestemt strategi $\pi$, indtil episoden afsluttes på et tidspunkt $T$. Specifikt observerer vi:

Hvad er sandsynligheden for, at denne bane opstår under en strategi $\pi$? Det afhænger både af strategiens aktionssandsynligheder og miljøets overgangsdynamik:

Antag nu, at banen faktisk blev genereret af en anden strategi — adfærdsstrategien $b$. For korrekt at bruge denne bane til at estimere forventninger under målstrategien $\pi$, skal vi tage højde for, hvor meget mere eller mindre sandsynlig denne sekvens af handlinger ville have været under $\pi$ sammenlignet med $b$.

Det er her, importance sampling-ratioen kommer ind. Den defineres som den relative sandsynlighed for banen under de to strategier:

Til sidst udlignes overgangssandsynlighederne, da begge strategier opererer i det samme miljø, og værdien af $\rho$ afhænger kun af strategierne, ikke af miljøet.

Hvorfor dette er vigtigt

Forholdet $\rho$ angiver, hvordan vi kan omvægte afkastet $G_t$, som er observeret under adfærdsstrategien, så det bliver et uvildigt estimat af, hvad afkastet ville have været under målstrategien:

Med andre ord, selvom dataene blev indsamlet ved hjælp af $b$, kan vi stadig estimere forventede afkast under $\pi$ — forudsat at $b$ giver en ikke-nul sandsynlighed for enhver handling, som $\pi$ kunne vælge (antagelse om dækning).

Praktiske overvejelser

Varians ved importance sampling

Inkorporering af importance sampling er konceptuelt ligetil. Den estimerede handlingsværdifunktion $q(s, a)$ justeres ved at vægte hver observeret returnering med den tilsvarende importance sampling-ratio. Den simpleste formulering ser således ud:

hvor:

• $\rho_i(s, a)$ er importance sampling-ratioen for den $i$-te sekvens, der starter fra $(s, a)$;
• $Returns_i(s, a)$ er returneringen fra denne sekvens;
• $N(s, a)$ er antallet af gange $(s, a)$ er blevet besøgt.

Dette kaldes ordinær importance sampling. Det giver et ukorrigeret estimat af $q(s, a)$, men kan have meget høj varians, især når adfærds- og målfunktionerne adskiller sig væsentligt.

For at mindske variansen kan en mere stabil metode anvendes: vægtet importance sampling. Denne metode normaliserer importance-vægtene, hvilket reducerer effekten af store ratioer og giver mere stabil indlæring:

I denne version er tælleren den samme vægtede sum af returneringer, men nævneren er nu summen af importance-vægtene i stedet for blot et simpelt antal.

Dette gør estimatet biased, men biasen mindskes, efterhånden som flere prøver indsamles. I praksis foretrækkes vægtet importance sampling på grund af den markant lavere varians og større numerisk stabilitet.

Politikker

Ligesom i on-policy-tilfældet anvendes $\varepsilon$-grådige politikker for både målpolitik $\pi(a | s)$ og adfærdspolitik $b(a | s)$.

Ved første øjekast virker det naturligt at gøre målpolitikken fuldstændig grådig — vores endelige mål er trods alt en grådig politik. I praksis giver dette dog et stort problem: hvis på noget tidspunkt $\pi(a | s) = 0$ for den handling, der faktisk blev udført af adfærdspolitikken, bliver importance sampling-forholdet $\rho$ nul, og resten af episoden bliver reelt ignoreret.

Ved at bruge en lille $\varepsilon$ (f.eks. $\varepsilon = 0.01$) i målpolitikken sikres det, at $\pi(a | s) > 0$ for enhver handling, så $\rho$ aldrig bliver nul midt i en episode. Når træningen er færdig, er det trivielt at konvertere den lærte $\varepsilon$‑grådige politik til en strengt grådig. Som ved on-policy-læring bør $\varepsilon$ aftage i adfærdspolitikken, men denne gang er det primært for numerisk stabilitet, da $\rho$ stadig kan blive nul midt i en episode på grund af, hvordan tal repræsenteres i computere.

Pseudokode