Monte Carlo-Kontroll

Ved å erstatte policy-evaluering-steget i den standard policy-iterasjons-algoritmen med Monte Carlo-estimeringsteknikkene beskrevet i forrige kapittel, kan vi allerede utlede en ny variant av policy-iterasjon—en som baserer seg på prøvet erfaring i stedet for dynamisk programmering.

Det finnes imidlertid en viktig begrensning. I tradisjonell policy-iterasjon er policy-forbedrings-steget avhengig av tilgang til en komplett modell av miljøet. Spesielt bruker vi følgende uttrykk for å oppdatere policyen:

Denne ligningen forutsetter at vi kjenner overgangssannsynlighetene $p(s', r | s, a)$. Men dette er nettopp problemet: Monte Carlo-metoder er laget for modellfrie omgivelser, der miljøets overgangsdynamikk er ukjent. Hvis en komplett modell er tilgjengelig, kan vi like gjerne bruke dynamisk programmering gjennomgående, også for policy-evaluering, siden det ville vært mer effektivt og presist.

Derfor, selv om det å erstatte verdiberegning med Monte Carlo-metoder er et steg mot modellfri forsterkningslæring, må vi også finne en måte å utføre policy-forbedring uten å være avhengig av kunnskap om modellen. Dette krever et skifte fra tilstandsverdifunksjon til aksjonsverdifunksjon.

Hvorfor aksjonsverdier?

Ved å bruke aksjonsverdier er det mulig å utføre policy-forbedring uten å trenge en modell av miljøet. I stedet for å være avhengig av overgangssannsynligheter for å beregne forventet avkastning, kan vi direkte velge handlinger som ser ut til å gi høyest verdi. Policy-forbedringssteget blir da:

Og det er ikke vanskelig å bevise at den nye policyen ikke er dårligere enn den gamle, siden policy improvement theorem fortsatt kan brukes:

Og, som med DP, garanterer denne teoremet at enten er $\pi_{k+1}$ bedre enn $\pi_k$, eller at de er like og optimale.

Estimering av handlingsverdifunksjon

Prosessen for estimering er nesten identisk med tilstandsverdifunksjon. Alle ideer som brukes for å estimere tilstandsverdier, kan brukes for å estimere handlingsverdier.

Pseudokode

På denne måten, med nok iterasjoner, vil estimerte handlingsverdier nærme seg de sanne handlingsverdiene.

Med dette kan du allerede bygge en metode lik policy-iterasjon som ikke er avhengig av en modell. For å gjøre dette, erstatter du trinnene policy-evaluering og policy-forbedring med prosessene beskrevet ovenfor.

Optimalisering

Selv om evalueringssteget kan utføres ved hjelp av Monte Carlo-estimering som beskrevet, har det en tendens til å være beregningsmessig ineffektivt. Som du allerede har sett, krever Monte Carlo-metoder vanligvis et stort antall utvalg for å gi rimelig nøyaktige estimater. Hvis vi følger en struktur som ligner på policy iteration, forsterkes denne ineffektiviteten: etter hver forbedring av policyen må vi kjøre Monte Carlo-estimering på nytt for å re-evaluere den nye policyen — noe som fører til betydelig merarbeid og treg læring.

Et mer naturlig alternativ er å oppdatere policyen umiddelbart etter hver gjennomførte episode. I stedet for å vente til en fullstendig gjennomgang av policy-evaluering er ferdig, lar vi agenten forbedre atferden sin episode for episode, ved å bruke de nyeste estimatene for handlingsverdier.

Dette resulterer i en metode som ligner mer på value iteration: en kombinasjon av evaluering og forbedring i ett steg. Dette øker sample-effektiviteten og gir raskere beregninger.

Pseudokode

Denne algoritmen følger en GPI-ramme, siden den har trinn for policy-evaluering og policy-forbedring, og kalles Monte Carlo-kontroll. Den største ulempen med denne spesifikke implementeringen er antakelsen om exploring starts. I de neste kapitlene vil du se hvorfor dette er et problem, og hvordan det kan håndteres.