Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lära Off-policy Monte Carlo-kontroll | Monte Carlo-metoder
Introduktion till Förstärkningsinlärning

bookOff-policy Monte Carlo-kontroll

Medan on-policy-metoder lär sig genom att följa och förbättra samma policy, introducerar off-policy-metoder en variation: de lär sig om en policy (målpolicyn) samtidigt som de följer en annan (beteendepolicyn). Denna uppdelning är kraftfull — det gör det möjligt att utvärdera eller förbättra en målpolicy utan att faktiskt behöva följa den under datainsamlingen.

Analogi

Låt oss återvända till glassbutiken från föregående kapitel. Du och din vän går in, och återigen erbjuds de tre välbekanta smakerna: choklad, vanilj och jordgubb. Choklad är din personliga favorit, och din första instinkt är att beställa den. Men denna butik är ny för dig, och du är inte helt säker på om choklad är rätt val. Som tur är har din vän besökt nästan alla glassbutiker i staden och är en framstående glassälskare. Du frågar om deras åsikt. "Chokladen här är okej," säger de, "men lita på mig — jordgubben är exceptionell." Så, baserat på deras erfarenhet, bestämmer du dig för att hoppa över ditt vanliga val och istället välja jordgubb.

Det beslutet — att förlita sig på någon annans erfarenhet för att vägleda sitt eget val — är kärnan i off-policy-metoder. Du försöker förbättra ditt beslutsfattande med data som samlats in under någon annans beteende. Det är fortfarande utforskning — men det styrs av extern erfarenhet snarare än din egen.

Viktighetsprovtagning

Eftersom agenten följer beteendepolicyn under episodgenerering måste vi ta hänsyn till skillnaden mellan vad beteendepolicyn genererar och vad målpolicyn skulle generera. Det är här viktighetsprovtagning kommer in.

Viktad stickprovsdragning (importance sampling) möjliggör justering av de utfall som observeras under beteendepolicyn så att de utgör giltiga skattningar för målpolicyn.

Låt oss betrakta en sekvens som börjar från ett visst tillstånd StS_t och följer en viss policy π\pi tills episoden avslutas vid tidpunkt TT. Specifikt observerar vi:

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

Vad är sannolikheten att denna sekvens inträffar under en policy π\pi? Det beror på både policyns sannolikheter för handlingar och miljöns övergångsdynamik:

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 att sekvensen faktiskt genererades av en annan policy — beteendepolicyn bb. För att korrekt använda denna sekvens för att skatta förväntningar under målpolicyn π\pi måste vi ta hänsyn till hur mycket mer eller mindre sannolik denna följd av handlingar hade varit under π\pi jämfört med bb.

Här introduceras importance sampling-kvoten. Den definieras som den relativa sannolikheten för sekvensen under de två policyerna:

ρ=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)}

I slutändan försvann övergångssannolikheterna, eftersom båda policyerna verkar i samma miljö, och värdet på ρ\rho beror endast på policyerna, inte på miljön.

Varför detta är viktigt

Kvoten ρ\rho anger hur vi ska omviktas utfall GtG_t som observerats under beteendepolicyn så att det blir en snedfri skattning av vad utfallet skulle ha varit under målpolicyn:

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

Med andra ord, även om data samlades in med bb, kan vi ändå skatta förväntade utfall under π\pi — förutsatt att bb ger icke-noll sannolikhet till varje handling som π\pi kan välja (täkningsantagandet).

Praktiska överväganden

Varians vid viktad sannolikhetsprovtagning

Att inkludera viktad sannolikhetsprovtagning är konceptuellt enkelt. Den skattade aktionsvärdesfunktionen q(s,a)q(s, a) justeras genom att varje observerad avkastning viktas med motsvarande viktad sannolikhetskvot. Den enklaste formuleringen ser ut så här:

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)}

där:

  • ρi(s,a)\rho_i(s, a) är viktad sannolikhetskvot för den ii:te banan som startar från (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) är avkastningen från den banan;
  • N(s,a)N(s, a) är antalet gånger (s,a)(s, a) har besökts.

Detta kallas ordinär viktad sannolikhetsprovtagning. Den ger en oberoende skattning av q(s,a)q(s, a), men kan drabbas av mycket hög varians, särskilt när beteende- och målpolicyn skiljer sig avsevärt.

För att minska variansen kan en mer stabil metod användas: normaliserad viktad sannolikhetsprovtagning. Denna metod normaliserar vikterna, vilket minskar påverkan av stora kvoter och leder till stabilare inlärning:

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 denna version är täljaren samma viktade summa av avkastningar, men nämnaren är nu summan av vikterna, istället för en enkel räkning.

Detta gör skattningen snedvriden, men snedvridningen minskar när fler prover samlas in. I praktiken föredras normaliserad viktad sannolikhetsprovtagning på grund av dess betydligt lägre varians och större numerisk stabilitet.

Policys

Precis som i on-policy-fallet används ε\varepsilon-giriga policys för både målpolicyn π(as)\pi(a | s) och beteendepolicyn b(as)b(a | s).

Vid första anblick kan det verka naturligt att göra målpolicyn fullt girig — vårt slutgiltiga mål är trots allt en girig policy. I praktiken leder detta dock till ett stort problem: om vid något steg π(as)=0\pi(a | s) = 0 för den åtgärd som faktiskt valdes av beteendepolicyn, blir viktningen ρ\rho noll och återstående del av episoden ignoreras effektivt.

Genom att använda ett litet ε\varepsilon (t.ex. ε=0.01\varepsilon = 0.01) i målpolicyn säkerställs att π(as)>0\pi(a | s) > 0 för varje åtgärd, så att ρ\rho aldrig blir noll mitt i en episod. När träningen är klar är det trivialt att konvertera den inlärda ε\varepsilon-giriga policyn till en strikt girig. Precis som vid on-policy-inlärning bör avtagande ε\varepsilon användas i beteendepolicyn, men denna gång är det främst för numerisk stabilitet, eftersom ρ\rho fortfarande kan bli noll mitt i en episod på grund av hur tal representeras i datorer.

Pseudokod

question mark

Vad är syftet med viktad stickprovsdragning (importance sampling)?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 6

Fråga AI

expand

Fråga AI

ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

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

Svep för att visa menyn

Medan on-policy-metoder lär sig genom att följa och förbättra samma policy, introducerar off-policy-metoder en variation: de lär sig om en policy (målpolicyn) samtidigt som de följer en annan (beteendepolicyn). Denna uppdelning är kraftfull — det gör det möjligt att utvärdera eller förbättra en målpolicy utan att faktiskt behöva följa den under datainsamlingen.

Analogi

Låt oss återvända till glassbutiken från föregående kapitel. Du och din vän går in, och återigen erbjuds de tre välbekanta smakerna: choklad, vanilj och jordgubb. Choklad är din personliga favorit, och din första instinkt är att beställa den. Men denna butik är ny för dig, och du är inte helt säker på om choklad är rätt val. Som tur är har din vän besökt nästan alla glassbutiker i staden och är en framstående glassälskare. Du frågar om deras åsikt. "Chokladen här är okej," säger de, "men lita på mig — jordgubben är exceptionell." Så, baserat på deras erfarenhet, bestämmer du dig för att hoppa över ditt vanliga val och istället välja jordgubb.

Det beslutet — att förlita sig på någon annans erfarenhet för att vägleda sitt eget val — är kärnan i off-policy-metoder. Du försöker förbättra ditt beslutsfattande med data som samlats in under någon annans beteende. Det är fortfarande utforskning — men det styrs av extern erfarenhet snarare än din egen.

Viktighetsprovtagning

Eftersom agenten följer beteendepolicyn under episodgenerering måste vi ta hänsyn till skillnaden mellan vad beteendepolicyn genererar och vad målpolicyn skulle generera. Det är här viktighetsprovtagning kommer in.

Viktad stickprovsdragning (importance sampling) möjliggör justering av de utfall som observeras under beteendepolicyn så att de utgör giltiga skattningar för målpolicyn.

Låt oss betrakta en sekvens som börjar från ett visst tillstånd StS_t och följer en viss policy π\pi tills episoden avslutas vid tidpunkt TT. Specifikt observerar vi:

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

Vad är sannolikheten att denna sekvens inträffar under en policy π\pi? Det beror på både policyns sannolikheter för handlingar och miljöns övergångsdynamik:

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 att sekvensen faktiskt genererades av en annan policy — beteendepolicyn bb. För att korrekt använda denna sekvens för att skatta förväntningar under målpolicyn π\pi måste vi ta hänsyn till hur mycket mer eller mindre sannolik denna följd av handlingar hade varit under π\pi jämfört med bb.

Här introduceras importance sampling-kvoten. Den definieras som den relativa sannolikheten för sekvensen under de två policyerna:

ρ=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)}

I slutändan försvann övergångssannolikheterna, eftersom båda policyerna verkar i samma miljö, och värdet på ρ\rho beror endast på policyerna, inte på miljön.

Varför detta är viktigt

Kvoten ρ\rho anger hur vi ska omviktas utfall GtG_t som observerats under beteendepolicyn så att det blir en snedfri skattning av vad utfallet skulle ha varit under målpolicyn:

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

Med andra ord, även om data samlades in med bb, kan vi ändå skatta förväntade utfall under π\pi — förutsatt att bb ger icke-noll sannolikhet till varje handling som π\pi kan välja (täkningsantagandet).

Praktiska överväganden

Varians vid viktad sannolikhetsprovtagning

Att inkludera viktad sannolikhetsprovtagning är konceptuellt enkelt. Den skattade aktionsvärdesfunktionen q(s,a)q(s, a) justeras genom att varje observerad avkastning viktas med motsvarande viktad sannolikhetskvot. Den enklaste formuleringen ser ut så här:

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)}

där:

  • ρi(s,a)\rho_i(s, a) är viktad sannolikhetskvot för den ii:te banan som startar från (s,a)(s, a);
  • Returnsi(s,a)Returns_i(s, a) är avkastningen från den banan;
  • N(s,a)N(s, a) är antalet gånger (s,a)(s, a) har besökts.

Detta kallas ordinär viktad sannolikhetsprovtagning. Den ger en oberoende skattning av q(s,a)q(s, a), men kan drabbas av mycket hög varians, särskilt när beteende- och målpolicyn skiljer sig avsevärt.

För att minska variansen kan en mer stabil metod användas: normaliserad viktad sannolikhetsprovtagning. Denna metod normaliserar vikterna, vilket minskar påverkan av stora kvoter och leder till stabilare inlärning:

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 denna version är täljaren samma viktade summa av avkastningar, men nämnaren är nu summan av vikterna, istället för en enkel räkning.

Detta gör skattningen snedvriden, men snedvridningen minskar när fler prover samlas in. I praktiken föredras normaliserad viktad sannolikhetsprovtagning på grund av dess betydligt lägre varians och större numerisk stabilitet.

Policys

Precis som i on-policy-fallet används ε\varepsilon-giriga policys för både målpolicyn π(as)\pi(a | s) och beteendepolicyn b(as)b(a | s).

Vid första anblick kan det verka naturligt att göra målpolicyn fullt girig — vårt slutgiltiga mål är trots allt en girig policy. I praktiken leder detta dock till ett stort problem: om vid något steg π(as)=0\pi(a | s) = 0 för den åtgärd som faktiskt valdes av beteendepolicyn, blir viktningen ρ\rho noll och återstående del av episoden ignoreras effektivt.

Genom att använda ett litet ε\varepsilon (t.ex. ε=0.01\varepsilon = 0.01) i målpolicyn säkerställs att π(as)>0\pi(a | s) > 0 för varje åtgärd, så att ρ\rho aldrig blir noll mitt i en episod. När träningen är klar är det trivialt att konvertera den inlärda ε\varepsilon-giriga policyn till en strikt girig. Precis som vid on-policy-inlärning bör avtagande ε\varepsilon användas i beteendepolicyn, men denna gång är det främst för numerisk stabilitet, eftersom ρ\rho fortfarande kan bli noll mitt i en episod på grund av hur tal representeras i datorer.

Pseudokod

question mark

Vad är syftet med viktad stickprovsdragning (importance sampling)?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 6
some-alt