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 å ha 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, hvor miljøets overgangsdynamikk er ukjent. Dersom 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 Monte Carlo-metoder for verdiberegning 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 å trenge en modell av miljøet. I stedet for å basere oss på overgangssannsynligheter for å beregne forventet avkastning, kan vi direkte velge de handlingene 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, siden teoremet om politikkforbedring fortsatt kan anvendes:

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

Estimering av handlingsverdifunksjon

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

Pseudokode

På denne måten, med tilstrekkelig mange iterasjoner, vil de estimerte aksjonsverdiene nærme seg de sanne aksjonsverdiene.

Med dette kan du allerede konstruere 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 prøver 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 fullført, lar vi agenten forbedre sin atferd episode for episode, ved å bruke de nyeste estimatene for aksjonsverdier.

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

Pseudokode

Denne algoritmen følger en GPI-ramme, siden den har trinn for politikkevaluering og politikkforbedring, 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.