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-Kontrol | Monte Carlo-metoder
Introduktion til Reinforcement Learning
course content

Kursusindhold

Introduktion til Reinforcement Learning

Introduktion til Reinforcement Learning

1. RL Kerneprincipper
2. Multi-Armet Bandit-Problem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-Læring

book
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 tilgængelige: 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 fremtrædende 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å baseret på deres erfaring vælger du at springe din sædvanlige favorit over og i stedet tage jordbær.

Den beslutning — at stole på andres erfaring for at vejlede dit eget valg — er essensen af off-policy metoder. Du forsøger at forbedre din beslutningstagning ved at bruge data 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ærds-politikken under generering af episoder, skal vi tage højde for forskellen mellem hvad adfærds-politikken genererer og hvad mål-politikken 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 sekvens, der starter fra en bestemt tilstand StS_t og følger en bestemt strategi π\pi, indtil episoden afsluttes på tidspunkt TT. Specifikt observerer vi:

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

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

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)

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

Her kommer importance sampling-forholdet ind i billedet. Det defineres som den relative sandsynlighed for sekvensen under de to strategier:

ρ=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 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 skal omvægte afkastet GtG_t observeret under adfærdsstrategien, så det bliver et forventningsret estimat af, hvad afkastet ville have været under målstrategien:

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

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

Praktiske Overvejelser

Varians ved Importance Sampling

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

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 sekvens, der starter fra (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) er returneringen fra den sekvens;
  • N(s,a)N(s, a) er antallet af gange (s,a)(s, a) er blevet besøgt.

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

For at mindske variansen kan vi anvende et mere stabilt alternativ: vægtet importance sampling. Denne metode normaliserer importance-vægtene, hvilket reducerer effekten af store ratioer og fører til mere stabil indlæ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 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 dens markant lavere varians og større numerisk stabilitet.

Politikker

Ligesom i on-policy-tilfældet anvendes ε\varepsilon-grådige politikker for både målpolitikken π(as)\pi(a | s) og adfærdspolitikken b(as)b(a | s).

Ved første øjekast virker det naturligt at gøre målpolitikken fuldstændig grådig — vores ultimative mål er trods alt en grådig politik. I praksis medfører dette dog et stort problem: hvis π(as)=0\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 anvende en lille ε\varepsilon (f.eks. ε=0.01\varepsilon = 0.01) i målpolitikken sikres det, at π(as)>0\pi(a | s) > 0 for enhver handling, så ρ\rho aldrig kollapser til nul midt i episoden. Når træningen er afsluttet, er det trivielt at konvertere den lærte ε\varepsilon‑grådige politik til en strengt grådig politik. 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 falde til nul midt i episoden på grund af, hvordan tal repræsenteres i computere.

Pseudokode

question mark

Hvad er formålet med importance sampling?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 4. Kapitel 6

Spørg AI

expand

Spørg AI

ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

course content

Kursusindhold

Introduktion til Reinforcement Learning

Introduktion til Reinforcement Learning

1. RL Kerneprincipper
2. Multi-Armet Bandit-Problem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-Læring

book
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 tilgængelige: 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 fremtrædende 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å baseret på deres erfaring vælger du at springe din sædvanlige favorit over og i stedet tage jordbær.

Den beslutning — at stole på andres erfaring for at vejlede dit eget valg — er essensen af off-policy metoder. Du forsøger at forbedre din beslutningstagning ved at bruge data 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ærds-politikken under generering af episoder, skal vi tage højde for forskellen mellem hvad adfærds-politikken genererer og hvad mål-politikken 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 sekvens, der starter fra en bestemt tilstand StS_t og følger en bestemt strategi π\pi, indtil episoden afsluttes på tidspunkt TT. Specifikt observerer vi:

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

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

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)

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

Her kommer importance sampling-forholdet ind i billedet. Det defineres som den relative sandsynlighed for sekvensen under de to strategier:

ρ=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 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 skal omvægte afkastet GtG_t observeret under adfærdsstrategien, så det bliver et forventningsret estimat af, hvad afkastet ville have været under målstrategien:

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

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

Praktiske Overvejelser

Varians ved Importance Sampling

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

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 sekvens, der starter fra (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) er returneringen fra den sekvens;
  • N(s,a)N(s, a) er antallet af gange (s,a)(s, a) er blevet besøgt.

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

For at mindske variansen kan vi anvende et mere stabilt alternativ: vægtet importance sampling. Denne metode normaliserer importance-vægtene, hvilket reducerer effekten af store ratioer og fører til mere stabil indlæ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 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 dens markant lavere varians og større numerisk stabilitet.

Politikker

Ligesom i on-policy-tilfældet anvendes ε\varepsilon-grådige politikker for både målpolitikken π(as)\pi(a | s) og adfærdspolitikken b(as)b(a | s).

Ved første øjekast virker det naturligt at gøre målpolitikken fuldstændig grådig — vores ultimative mål er trods alt en grådig politik. I praksis medfører dette dog et stort problem: hvis π(as)=0\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 anvende en lille ε\varepsilon (f.eks. ε=0.01\varepsilon = 0.01) i målpolitikken sikres det, at π(as)>0\pi(a | s) > 0 for enhver handling, så ρ\rho aldrig kollapser til nul midt i episoden. Når træningen er afsluttet, er det trivielt at konvertere den lærte ε\varepsilon‑grådige politik til en strengt grådig politik. 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 falde til nul midt i episoden på grund af, hvordan tal repræsenteres i computere.

Pseudokode

question mark

Hvad er formålet med importance sampling?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 4. Kapitel 6
some-alt