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 adgang til en komplet model af miljøet. Specifikt bruger vi følgende udtryk til at opdatere policyen:

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, kan vi lige så godt bruge dynamisk programmering hele vejen igennem, også til policy evaluation, da det ville være mere effektivt og præcist.

Derfor, selvom det at erstatte Monte Carlo-metoder for value estimation 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 state value function til action value function.

Hvorfor Action Values?

Ved at bruge action values 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 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 policy 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ærdifunktion. Alle idéer, der anvendes til at estimere tilstandsværdier, kan bruges til at estimere handlingsværdier.

Pseudokode

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

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 processer, der er beskrevet ovenfor.

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 fuldføre en fuld gennemgang af 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 i højere grad ligner 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.