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 experience 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-fri indstillinger, hvor miljøets overgangsdynamik er ukendt. Hvis en komplet model er tilgængelig, kan vi lige så godt bruge dynamisk programmering overalt, også til policy evaluation, da det ville være mere effektivt og præcist.

Derfor, selvom det at erstatte Monte Carlo-metoder til værdiberegning 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 have en model af miljøet. I stedet for at være afhængig af overgangssandsynligheder for 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 handlingsværdifunktion

Estimeringsprocessen er næsten identisk med tilstandsværdifunktionen. Alle idéer, der anvendes til at estimere tilstandsværdier, kan bruges til at estimere handlingsværdier.

Pseudokode

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

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

Optimering

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

Et mere naturligt alternativ er at opdatere politikken umiddelbart efter behandling af hver episode. I stedet for at vente på at gennemføre en fuld omgang politikevaluering, 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 værdi-iteration: kombinerer aspekter af evaluering og forbedring i ét trin. Det øger prøveeffektiviteten og øger beregningshastigheden.

Pseudokode

Denne algoritme følger en GPI-ramme, da den har trin for policyevaluering og policyforbedring, 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.