Genom att ersätta steget policyutvärdering i den standardiserade algoritmen för policyiteration 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änds följande uttryck:

Denna ekvation förutsätter att vi känner till övergångssannolikheterna $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 genomföra policyförbättring utan att förlita oss på kunskap om modellen. Detta kräver en övergång från tillståndsvärdesfunktion till aktionsvärdesfunktion.

Varför aktionsvärden?

Genom att använda aktionsvärden är det möjligt att genomfö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 åtgärder som verkar ge högst värde. Steget för policyförbättring blir då:

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

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

Uppskattning av åtgärdsvärdesfunktion

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

Pseudokod

På så sätt, med tillräckligt många iterationer, bör de uppskattade åtgärdsvärdena närma sig de sanna åtgärdsvä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 policyutvärdering 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 tillräckligt noggranna uppskattningar. Om vi följer en struktur liknande policy iteration 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 varje genomförd episod. Istället för att vänta på att slutföra en fullständig policyutvärdering, 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 value iteration: en kombination av utvärdering och förbättring i ett enda steg. Det ökar sampleffektiviteten och förbättrar beräkningshastigheten.

Pseudokod

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