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:
vπ(s)=a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))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 ∣S∣ lineære ligninger med ∣S∣ ukjente.
For eksempel, hvis en MDP har 2 tilstander (s1, s2) og 2 handlinger (flytt til s1, flytt til s2), kan tilstandsverdifunksjonen defineres slik:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))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 γ<1;
- Politikken π, når den følges fra en hvilken som helst tilstand s, 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:
vk+1(s)←a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Den estimerte tilstandsverdifunksjonen vk konvergerer til slutt mot en sann tilstandsverdifunksjon vπ når k→∞ dersom vπ 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, ∣vk+1(s)−vk(s)∣, 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!
Spør AI
Spør AI
Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår
Awesome!
Completion rate improved to 2.7
Policyvurdering
Sveip for å vise menyen
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:
vπ(s)=a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))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 ∣S∣ lineære ligninger med ∣S∣ ukjente.
For eksempel, hvis en MDP har 2 tilstander (s1, s2) og 2 handlinger (flytt til s1, flytt til s2), kan tilstandsverdifunksjonen defineres slik:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))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 γ<1;
- Politikken π, når den følges fra en hvilken som helst tilstand s, 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:
vk+1(s)←a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Den estimerte tilstandsverdifunksjonen vk konvergerer til slutt mot en sann tilstandsverdifunksjon vπ når k→∞ dersom vπ 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, ∣vk+1(s)−vk(s)∣, 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!