Ved at erstatte policy evaluation-trinnet i den standard policy iteration-algoritme med Monte Carlo-estimationsteknikkerne beskrevet i det forrige kapitel, kan vi allerede udlede en ny variation af policy iteration—en, der er baseret på sampled erfaring i stedet for dynamisk programmering.

Der er dog en væsentlig begrænsning. I traditionel policy iteration afhænger policy improvement-trinnet af at have adgang til en komplet model af miljøet. Specifikt bruger vi følgende udtryk til at opdatere politikken:

Denne ligning antager, at vi kender overgangssandsynlighederne $p(s', r | s, a)$. Men det er netop problemet: Monte Carlo-metoder er designet til model-frie situationer, hvor miljøets overgangsdynamik er ukendt. Hvis en komplet model er tilgængelig, bør vi i stedet anvende dynamisk programmering overalt, også til policy evaluation, da det ville være mere effektivt og præcist.

Derfor, selvom det at erstatte værdiestimering med Monte Carlo-metoder er et skridt mod model-fri reinforcement learning, skal vi også finde en måde at udføre policy improvement uden at være afhængig af kendskab til modellen. Dette kræver et skift fra tilstands-værdifunktion til aktions-værdifunktion.

Hvorfor aktionsværdier?

Ved at bruge aktionsværdier er det muligt at udføre policy improvement uden at skulle bruge en model af miljøet. I stedet for at være afhængig af overgangssandsynligheder til at beregne forventede afkast, kan vi direkte vælge de handlinger, der ser ud til at give den højeste værdi. Policy improvement-trinnet bliver da:

Og det er ikke svært at bevise, at den nye politik ikke er dårligere end den gamle, da policy improvement-sætningen stadig kan anvendes:

Og ligesom med DP garanterer denne sætning, at enten er $\pi_{k+1}$ bedre end $\pi_k$, eller også er de begge ens og optimale.

Estimering af aktionsværdifunktion

Processen for estimering er næsten identisk med tilstandsværdifunktionen. Alle idéer, der anvendes til at estimere tilstandsværdier, kan bruges til at estimere aktionsværdier.

Pseudokode

På denne måde bør de estimerede handlingsværdier nærme sig de sande handlingsværdier efter tilstrækkeligt mange iterationer.

Med dette kan du allerede konstruere en metode svarende til policy-iteration, som ikke er afhængig af en model. For at gøre dette erstattes trinnene policy-evaluering og policy-forbedring med de ovenfor beskrevne processer.

Optimering

Selvom evaluerings-trinnet kan udføres ved hjælp af Monte Carlo-estimering som beskrevet, er det ofte beregningsmæssigt ineffektivt. Som du allerede har set, kræver Monte Carlo-metoder typisk et stort antal prøver for at opnå rimeligt nøjagtige estimater. Hvis vi følger en struktur svarende til policy-iteration, forstærkes denne ineffektivitet: efter hver policy-forbedring skal vi genkøre Monte Carlo-estimering for at genvurdere den nye policy — hvilket medfører betydelig overhead og langsom indlæring.

Et mere naturligt alternativ er at opdatere policyen umiddelbart efter behandling af hver episode. I stedet for at vente på at fuldføre en fuld gennemgang af policy-evaluering, tillader vi agenten at forfine sin adfærd episode for episode ved at bruge de nyeste estimater af handlingsværdier.

Dette resulterer i en metode, der minder mere om value-iteration: kombination af aspekter fra evaluering og forbedring i ét trin. Det øger sample-effektiviteten og øger beregningshastigheden.

Pseudokode

Denne algoritme følger en GPI-ramme, da den har trin for politikevaluering og politikforbedring, og den kaldes Monte Carlo-kontrol. Den største ulempe ved denne specifikke implementering er antagelsen om exploring starts. I de næste kapitler vil du se, hvorfor dette er et problem, og hvordan det kan håndteres.