Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Policyvurdering | Dynamisk Programmering
Introduksjon til Forsterkende Læring
course content

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
2. Multi-Armet Bandittproblem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-læring

book
Policyvurdering

Note
Definisjon

Policyevaluering er en prosess for å bestemme verdifunksjonen til en gitt policy.

Note
Merk

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π(as)s,rp(s,rs,a)(r+γvπ(s))v_\pi(s) = \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

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|S| lineære ligninger med S|S| ukjente.

For eksempel, hvis en MDP har 2 tilstander (s1s_1, s2s_2) og 2 handlinger (flytt til s1s_1, flytt til s2s_2), kan tilstandsverdifunksjonen defineres slik:

{V(s1)=0.5(5+0.9V(s1))+0.5(10+0.9V(s2))V(s2)=0.7(2+0.9V(s1))+0.3(0+0.9V(s2))\begin{cases} V(s_1) = 0.5 \cdot (5 + 0.9 \cdot V(s_1)) + 0.5 \cdot (10 + 0.9 \cdot V(s_2)) \\ V(s_2) = 0.7 \cdot (2 + 0.9 \cdot V(s_1)) + 0.3 \cdot (0 + 0.9 \cdot V(s_2)) \end{cases}

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γ < 1;
  • Politikken π\pi, når den følges fra en hvilken som helst tilstand ss, 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π(as)s,rp(s,rs,a)(r+γvk(s))v_{k+1}(s) \gets \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_k(s')\Bigr)

Den estimerte tilstandsverdifunksjonen vkv_k konvergerer til slutt mot en sann tilstandsverdifunksjon vπv_\pi når kk \to \infty dersom vπv_\pi 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)|v_{k+1}(s) - v_k(s)|, og sammenligne dette med en liten terskelverdi θ\theta. Dersom ingen endringer overstiger θ\theta etter en full oppdateringssyklus (hvor verdiene for alle tilstander er oppdatert), kan prosessen trygt avsluttes.

Pseudokode

question mark

Hvilket av følgende utsagn er sant med hensyn til metoden for iterativ policy-evaluering?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 4

Spør AI

expand

Spør AI

ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

course content

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
2. Multi-Armet Bandittproblem
3. Dynamisk Programmering
4. Monte Carlo-metoder
5. Temporal Difference-læring

book
Policyvurdering

Note
Definisjon

Policyevaluering er en prosess for å bestemme verdifunksjonen til en gitt policy.

Note
Merk

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π(as)s,rp(s,rs,a)(r+γvπ(s))v_\pi(s) = \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

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|S| lineære ligninger med S|S| ukjente.

For eksempel, hvis en MDP har 2 tilstander (s1s_1, s2s_2) og 2 handlinger (flytt til s1s_1, flytt til s2s_2), kan tilstandsverdifunksjonen defineres slik:

{V(s1)=0.5(5+0.9V(s1))+0.5(10+0.9V(s2))V(s2)=0.7(2+0.9V(s1))+0.3(0+0.9V(s2))\begin{cases} V(s_1) = 0.5 \cdot (5 + 0.9 \cdot V(s_1)) + 0.5 \cdot (10 + 0.9 \cdot V(s_2)) \\ V(s_2) = 0.7 \cdot (2 + 0.9 \cdot V(s_1)) + 0.3 \cdot (0 + 0.9 \cdot V(s_2)) \end{cases}

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γ < 1;
  • Politikken π\pi, når den følges fra en hvilken som helst tilstand ss, 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π(as)s,rp(s,rs,a)(r+γvk(s))v_{k+1}(s) \gets \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_k(s')\Bigr)

Den estimerte tilstandsverdifunksjonen vkv_k konvergerer til slutt mot en sann tilstandsverdifunksjon vπv_\pi når kk \to \infty dersom vπv_\pi 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)|v_{k+1}(s) - v_k(s)|, og sammenligne dette med en liten terskelverdi θ\theta. Dersom ingen endringer overstiger θ\theta etter en full oppdateringssyklus (hvor verdiene for alle tilstander er oppdatert), kan prosessen trygt avsluttes.

Pseudokode

question mark

Hvilket av følgende utsagn er sant med hensyn til metoden for iterativ policy-evaluering?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 4
some-alt