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
course content

Kursinnehåll

Introduktion till Förstärkningsinlärning

Introduktion till Förstärkningsinlärning

1. RL Kärnteori
2. Multi-Armed Bandit-Problemet
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporär Differensinlärning

book
Off-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 möjliggör utvärdering eller förbättring av en målpolicy utan att behöva följa den under datainsamlingen.

Liknelse

Låt oss återvända till glassbaren 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, en framstående glassälskare, besökt nästan alla glassbarer i staden. Du frågar om deras åsikt. "Chokladen här är okej," säger de, "men lita på mig — jordgubben är enastående." 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 ditt eget val — är kärnan i off-policy-metoder. Du försöker förbättra ditt beslutsfattande med hjälp av 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.

Viktighetsprovtagning tillhandahåller ett sätt att justera de avkastningar som observerats under beteendepolicyn så att de blir giltiga uppskattningar för målpolicyn.

Låt oss titta på en trajektoria 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 trajektoria 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 trajektorien faktiskt genererades av en annan policy — beteendepolicyn bb. För att korrekt använda denna trajektoria för att uppskatta förväntningar under målpolicyn π\pi, måste vi ta hänsyn till hur mycket mer eller mindre sannolik denna sekvens av handlingar skulle ha varit under π\pi jämfört med bb.

Det är här viktighetsprovtagningskvoten kommer in. Den definieras som den relativa sannolikheten för trajektorien 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 avkastningen GtG_t​ som observerats under beteendepolicyn så att den blir en snedfri uppskattning av vad avkastningen 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 hjälp av bb, kan vi fortfarande uppskatta förväntad avkastning 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. Vi justerar den uppskattade aktionsvärdesfunktionen q(s,a)q(s, a) genom att vikta varje observerad avkastning 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 börjar 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. Det 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 mildra variansproblemet kan vi använda ett mer stabilt alternativ: normaliserad viktad sannolikhetsprovtagning. Denna metod normaliserar vikterna, vilket minskar påverkan av stora kvoter och leder till mer stabil 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änd ε\varepsilon-giriga policys för både målpolicyn π(as)\pi(a | s) och beteendepolicyn b(as)b(a | s).

Vid första anblicken verkar det naturligt att göra målpolicyn helt girig — vårt slutgiltiga mål är trots allt en girig policy. I praktiken orsakar detta dock 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 viktade urvalskvoten ρ\rho noll och återstående delen 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 enkelt att konvertera den inlärda ε\varepsilon-giriga policyn till en strikt girig policy. 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

course content

Kursinnehåll

Introduktion till Förstärkningsinlärning

Introduktion till Förstärkningsinlärning

1. RL Kärnteori
2. Multi-Armed Bandit-Problemet
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporär Differensinlärning

book
Off-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 möjliggör utvärdering eller förbättring av en målpolicy utan att behöva följa den under datainsamlingen.

Liknelse

Låt oss återvända till glassbaren 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, en framstående glassälskare, besökt nästan alla glassbarer i staden. Du frågar om deras åsikt. "Chokladen här är okej," säger de, "men lita på mig — jordgubben är enastående." 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 ditt eget val — är kärnan i off-policy-metoder. Du försöker förbättra ditt beslutsfattande med hjälp av 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.

Viktighetsprovtagning tillhandahåller ett sätt att justera de avkastningar som observerats under beteendepolicyn så att de blir giltiga uppskattningar för målpolicyn.

Låt oss titta på en trajektoria 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 trajektoria 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 trajektorien faktiskt genererades av en annan policy — beteendepolicyn bb. För att korrekt använda denna trajektoria för att uppskatta förväntningar under målpolicyn π\pi, måste vi ta hänsyn till hur mycket mer eller mindre sannolik denna sekvens av handlingar skulle ha varit under π\pi jämfört med bb.

Det är här viktighetsprovtagningskvoten kommer in. Den definieras som den relativa sannolikheten för trajektorien 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 avkastningen GtG_t​ som observerats under beteendepolicyn så att den blir en snedfri uppskattning av vad avkastningen 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 hjälp av bb, kan vi fortfarande uppskatta förväntad avkastning 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. Vi justerar den uppskattade aktionsvärdesfunktionen q(s,a)q(s, a) genom att vikta varje observerad avkastning 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 börjar 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. Det 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 mildra variansproblemet kan vi använda ett mer stabilt alternativ: normaliserad viktad sannolikhetsprovtagning. Denna metod normaliserar vikterna, vilket minskar påverkan av stora kvoter och leder till mer stabil 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änd ε\varepsilon-giriga policys för både målpolicyn π(as)\pi(a | s) och beteendepolicyn b(as)b(a | s).

Vid första anblicken verkar det naturligt att göra målpolicyn helt girig — vårt slutgiltiga mål är trots allt en girig policy. I praktiken orsakar detta dock 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 viktade urvalskvoten ρ\rho noll och återstående delen 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 enkelt att konvertera den inlärda ε\varepsilon-giriga policyn till en strikt girig policy. 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