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

Det finnes imidlertid en kritisk begrensning. I tradisjonell politikkiterasjon er politikkforbedring-steget avhengig av tilgang til en komplett modell av miljøet. Spesifikt bruker vi følgende uttrykk for å oppdatere politikken:

Denne ligningen forutsetter at vi kjenner overgangssannsynlighetene $p(s', r | s, a)$. Men dette er nettopp problemet: Monte Carlo-metoder er utviklet 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 politikkevaluering, 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 politikkforbedring 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 politikkforbedring uten behov for 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. Politikkforbedringssteget blir da:

Og det er ikke vanskelig å bevise at den nye politikken ikke er dårligere enn den gamle, ettersom teoremet om politikkforbedring fortsatt kan anvendes:

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

Estimering av handlingsverdifunksjon

Estimeringsprosessen er nesten identisk med tilstandsverdifunksjonen. Alle ideer som brukes for å estimere tilstandsverdier, kan også 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 tilsvarende politikkiterasjon som ikke er avhengig av en modell. For å gjøre dette, erstatter du trinnene politikkevaluering og politikkforbedring med prosessene beskrevet ovenfor.

Optimalisering

Selv om evaluerings-steget 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å politikkiterasjon, forsterkes denne ineffektiviteten: etter hver politikkforbedring må vi kjøre Monte Carlo-estimering på nytt for å evaluere den nye politikken — noe som fører til betydelig merarbeid og treg læring.

Et mer naturlig alternativ er å oppdatere politikken umiddelbart etter hver gjennomførte episode. I stedet for å vente til en fullstendig runde med politikkevaluering er ferdig, lar vi agenten forbedre sin atferd episode for episode, ved å bruke de nyeste estimatene for handlingsverdier.

Dette resulterer i en metode som ligner mer på verdiiterasjon: en kombinasjon av evaluering og forbedring i ett steg. Det øker utvalgsutnyttelsen og gir raskere beregning.

Pseudokode

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