Kursinnhold
Introduksjon til Forsterkende Læring
Introduksjon til Forsterkende Læring
Policyvurdering
Policyevaluering er en prosess for å bestemme verdifunksjonen til en gitt policy.
Policyevaluering kan brukes til å estimere både tilstandsverdifunksjon og aksjonsverdifunksjon. For DP-metoder vil tilstandsverdifunksjonen benyttes.
Som du vet, kan en tilstandsverdifunksjon for en gitt policy bestemmes ved å løse en Bellman-ligning:
Hvis du har en fullstendig modell av miljøet (dvs. kjente overgangssannsynligheter og forventede belønninger for alle tilstand-handlingspar), er de eneste ukjente variablene i ligningen tilstandsverdiene. Derfor kan ligningen ovenfor omformuleres som et system av lineære ligninger med ukjente.
For eksempel, hvis en MDP har 2 tilstander (, ) og 2 handlinger (flytt til , flytt til ), kan tilstandsverdifunksjonen defineres slik:
Dette kan løses ved hjelp av standard lineær algebra.
En entydig løsning for et slikt lineært system er garantert dersom minst ett av følgende vilkår er oppfylt:
- Diskonteringsfaktoren tilfredsstiller ;
- Politikken , når den følges fra en hvilken som helst tilstand , sikrer at episoden til slutt terminerer.
Iterativ politikkvurdering
Løsningen kan beregnes direkte, men en iterativ tilnærming brukes oftere på grunn av dens enkle implementering. Denne metoden starter med å tildele vilkårlige startverdier til alle tilstander, unntatt terminaltilstander, som settes til 0. Verdiene oppdateres deretter iterativt ved å bruke Bellman-ligningen som oppdateringsregel:
Den estimerte tilstandsverdifunksjonen konvergerer til slutt mot en sann tilstandsverdifunksjon når dersom eksisterer.
Strategier for verdi-backup
Ved oppdatering av verdiestimatene beregnes nye estimater basert på tidligere verdier. Prosessen med å bevare tidligere estimater kalles en backup. Det finnes to vanlige strategier for å utføre backups:
- Full backup: denne metoden innebærer å lagre de nye estimatene i et eget array, adskilt fra det som inneholder de tidligere (backede) verdiene. Dermed kreves to arrays — ett for å opprettholde de tidligere estimatene og ett for å lagre de nyberegnede verdiene;
- In-place backup: denne tilnærmingen holder alle verdier i ett enkelt array. Hvert nytt estimat erstatter umiddelbart den forrige verdien. Denne metoden reduserer minnebruken, ettersom kun ett array er nødvendig.
Vanligvis foretrekkes in-place backup-metoden fordi den krever mindre minne og konvergerer raskere, takket være umiddelbar bruk av de siste estimatene.
Når bør oppdateringen stoppes?
I iterativ policy-evaluering finnes det ikke et eksakt tidspunkt hvor algoritmen bør stoppes. Selv om konvergens er garantert i det uendelige, er det unødvendig å fortsette beregningene utover et visst punkt i praksis. Et enkelt og effektivt stoppkriterium er å følge med på absoluttverdien av forskjellen mellom påfølgende verdiestimater, , og sammenligne dette med en liten terskelverdi . Dersom ingen endringer overstiger etter en full oppdateringssyklus (hvor verdiene for alle tilstander er oppdatert), kan prosessen trygt avsluttes.
Pseudokode
Takk for tilbakemeldingene dine!