Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lära 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
Monte Carlo-Kontroll

Genom att ersätta steget policyutvärdering i den standardiserade policyiteration-algoritmen med Monte Carlo-estimeringsteknikerna som beskrevs i föregående kapitel, kan vi redan härleda en ny variant av policyiteration—en som bygger på samplad erfarenhet istället för dynamisk programmering.

Det finns dock en avgörande begränsning. I traditionell policyiteration är steget policyförbättring beroende av att ha tillgång till en komplett modell av miljön. För att uppdatera policyn använder vi följande uttryck:

π(s)arg maxas,rp(s,rs,a)(r+γv(s))\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

Denna ekvation förutsätter att vi känner till övergångssannolikheterna p(s,rs,a)p(s', r | s, a). Men det är just detta som är problemet: Monte Carlo-metoder är utformade för modellfria miljöer, där miljöns övergångsdynamik är okänd. Om en komplett modell finns tillgänglig, kan vi lika gärna använda dynamisk programmering rakt igenom, även för policyutvärdering, eftersom det skulle vara mer effektivt och exakt.

Därför, även om det är ett steg mot modellfri förstärkningsinlärning att ersätta värdeuppskattning med Monte Carlo-metoder, måste vi också hitta ett sätt att utföra policyförbättring utan att förlita oss på kunskap om modellen. Detta kräver ett skifte från tillståndsvärdesfunktion till aktionsvärdesfunktion.

Varför aktionsvärden?

Genom att använda aktionsvärden är det möjligt att utföra policyförbättring utan att behöva en modell av miljön. Istället för att förlita sig på övergångssannolikheter för att beräkna förväntad avkastning, kan vi direkt välja de handlingar som verkar ge högst värde. Steget för policyförbättring blir då:

π(s)arg maxaq(s,a)sS\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

Och det är inte svårt att bevisa att den nya policyn inte är sämre än den gamla, eftersom teoremet om policyförbättring fortfarande kan tillämpas:

qπk(s,πk+1(s))=qπk(s,arg maxaqπk(s,a))=maxaqπk(s,a)qπk(s,πk(s))=vπk(s)\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

Och, precis som med DP, garanterar detta teorem att antingen är πk+1\pi_{k+1} bättre än πk\pi_k, eller så är de båda lika och optimala.

Skattning av åtgärdsvärdesfunktion

Skattningsprocessen är nästan identisk med tillståndsvärdesfunktionen. Alla idéer som används för att skatta tillståndsvärden kan användas för att skatta åtgärdsvärden.

Pseudokod

På så sätt, med tillräckligt många iterationer, bör de uppskattade aktionsvärdena närma sig de sanna aktionsvärdena.

Med detta kan du redan konstruera en metod liknande policyiteration som inte är beroende av en modell. För att göra detta ersätter du stegen policyevaluering och policyförbättring med de processer som beskrivits ovan.

Optimering

Även om utvärderingssteget kan utföras med Monte Carlo-estimering som beskrivet, tenderar det att vara beräkningsmässigt ineffektivt. Som du redan har sett kräver Monte Carlo-metoder vanligtvis ett stort antal prover för att ge rimligt noggranna uppskattningar. Om vi följer en struktur liknande policyiteration förstärks denna ineffektivitet: efter varje policyförbättring måste vi köra Monte Carlo-estimering igen för att utvärdera den nya policyn — vilket leder till betydande overhead och långsam inlärning.

Ett mer naturligt alternativ är att uppdatera policyn omedelbart efter att varje episod har bearbetats. Istället för att vänta på att slutföra en fullständig omgång av policyevaluering, låter vi agenten förfina sitt beteende episod för episod, med hjälp av de senaste uppskattningarna av aktionsvärden.

Detta resulterar i en metod som mer liknar värdeiteration: kombinerar aspekter av utvärdering och förbättring i ett enda steg. Det ökar sampleffektiviteten och ökar beräkningshastigheten.

Pseudokod

Denna algoritm följer ett GPI-ramverk, eftersom den har steg för policyevaluering och policyförbättring, och den kallas Monte Carlo-kontroll. Den största nackdelen med denna specifika implementation är antagandet om utforskande starter. I kommande kapitel kommer du att se varför detta är ett problem och hur det kan hanteras.

question mark

Vad är den främsta fördelen med att använda åtgärdsvärden istället för tillståndsvärden i Monte Carlo-kontroll?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 3

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
Monte Carlo-Kontroll

Genom att ersätta steget policyutvärdering i den standardiserade policyiteration-algoritmen med Monte Carlo-estimeringsteknikerna som beskrevs i föregående kapitel, kan vi redan härleda en ny variant av policyiteration—en som bygger på samplad erfarenhet istället för dynamisk programmering.

Det finns dock en avgörande begränsning. I traditionell policyiteration är steget policyförbättring beroende av att ha tillgång till en komplett modell av miljön. För att uppdatera policyn använder vi följande uttryck:

π(s)arg maxas,rp(s,rs,a)(r+γv(s))\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

Denna ekvation förutsätter att vi känner till övergångssannolikheterna p(s,rs,a)p(s', r | s, a). Men det är just detta som är problemet: Monte Carlo-metoder är utformade för modellfria miljöer, där miljöns övergångsdynamik är okänd. Om en komplett modell finns tillgänglig, kan vi lika gärna använda dynamisk programmering rakt igenom, även för policyutvärdering, eftersom det skulle vara mer effektivt och exakt.

Därför, även om det är ett steg mot modellfri förstärkningsinlärning att ersätta värdeuppskattning med Monte Carlo-metoder, måste vi också hitta ett sätt att utföra policyförbättring utan att förlita oss på kunskap om modellen. Detta kräver ett skifte från tillståndsvärdesfunktion till aktionsvärdesfunktion.

Varför aktionsvärden?

Genom att använda aktionsvärden är det möjligt att utföra policyförbättring utan att behöva en modell av miljön. Istället för att förlita sig på övergångssannolikheter för att beräkna förväntad avkastning, kan vi direkt välja de handlingar som verkar ge högst värde. Steget för policyförbättring blir då:

π(s)arg maxaq(s,a)sS\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

Och det är inte svårt att bevisa att den nya policyn inte är sämre än den gamla, eftersom teoremet om policyförbättring fortfarande kan tillämpas:

qπk(s,πk+1(s))=qπk(s,arg maxaqπk(s,a))=maxaqπk(s,a)qπk(s,πk(s))=vπk(s)\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

Och, precis som med DP, garanterar detta teorem att antingen är πk+1\pi_{k+1} bättre än πk\pi_k, eller så är de båda lika och optimala.

Skattning av åtgärdsvärdesfunktion

Skattningsprocessen är nästan identisk med tillståndsvärdesfunktionen. Alla idéer som används för att skatta tillståndsvärden kan användas för att skatta åtgärdsvärden.

Pseudokod

På så sätt, med tillräckligt många iterationer, bör de uppskattade aktionsvärdena närma sig de sanna aktionsvärdena.

Med detta kan du redan konstruera en metod liknande policyiteration som inte är beroende av en modell. För att göra detta ersätter du stegen policyevaluering och policyförbättring med de processer som beskrivits ovan.

Optimering

Även om utvärderingssteget kan utföras med Monte Carlo-estimering som beskrivet, tenderar det att vara beräkningsmässigt ineffektivt. Som du redan har sett kräver Monte Carlo-metoder vanligtvis ett stort antal prover för att ge rimligt noggranna uppskattningar. Om vi följer en struktur liknande policyiteration förstärks denna ineffektivitet: efter varje policyförbättring måste vi köra Monte Carlo-estimering igen för att utvärdera den nya policyn — vilket leder till betydande overhead och långsam inlärning.

Ett mer naturligt alternativ är att uppdatera policyn omedelbart efter att varje episod har bearbetats. Istället för att vänta på att slutföra en fullständig omgång av policyevaluering, låter vi agenten förfina sitt beteende episod för episod, med hjälp av de senaste uppskattningarna av aktionsvärden.

Detta resulterar i en metod som mer liknar värdeiteration: kombinerar aspekter av utvärdering och förbättring i ett enda steg. Det ökar sampleffektiviteten och ökar beräkningshastigheten.

Pseudokod

Denna algoritm följer ett GPI-ramverk, eftersom den har steg för policyevaluering och policyförbättring, och den kallas Monte Carlo-kontroll. Den största nackdelen med denna specifika implementation är antagandet om utforskande starter. I kommande kapitel kommer du att se varför detta är ett problem och hur det kan hanteras.

question mark

Vad är den främsta fördelen med att använda åtgärdsvärden istället för tillståndsvärden i Monte Carlo-kontroll?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 4. Kapitel 3
some-alt