Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Estimering av Verdifunksjon | Monte Carlo-metoder
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
Estimering av Verdifunksjon

La oss begynne med å se på et kjent konsept: tilstandsverdifunksjonen, betegnet som vπ(s)v_\pi(s). Den kan defineres som

vπ(s)=Eπ[GtSt=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi [ G_t | S_t = s]

Målet i dette kapittelet er å estimere denne funksjonen fra data, gitt at vi har en fast politikk π\pi, men ikke har tilgang til miljøets modell.

Monte Carlo-estimering

Monte Carlo-metoder tilnærmer denne estimeringsoppgaven ved å samle episoder av erfaring under politikken π\pi, og deretter bruke disse prøvene til å lage empiriske estimater av vπ(s)v_\pi(s).

Generelt kan prosessen deles inn i følgende trinn:

  1. Generer en episode ved å bruke politikk π\pi;
  2. Lagre den oppnådde returverdien for hver tilstand som opptrer i episoden;
  3. Gjenta trinn 1-2 over tid;
  4. Beregn de nye verdiene ved å ta gjennomsnittet av returene for hver tilstand.

Innhenting av avkastning

Monte Carlo-estimering av verdifunksjonen krever innhenting av avkastning fra genererte episoder. For å beregne disse avkastningene kan to hovedmetoder benyttes:

  • Første-besøk: for hver tilstand ss som oppstår i en episode, tas kun avkastningen etter første forekomst med i betraktningen. Senere forekomster av samme tilstand i samme episode ignoreres for estimeringsformål;
  • Alle-besøk: hver forekomst av en tilstand ss i en episode benyttes. Det vil si at avkastningen etter hvert besøk til tilstanden inkluderes i estimatet, selv om tilstanden opptrer flere ganger i samme episode.

Utforskende starttilstander

Tenk deg en enkel endimensjonal verden representert av en linje som strekker seg fra -10 til +10. Agenten starter på posisjon 0, og dens nåværende policy tilsier at den alltid beveger seg til høyre ved hvert tidsskritt.

Hvis vi forsøker å generere episoder under denne policyen, hva skjer da? Agenten vil kontinuerlig bevege seg mot den positive enden av linjen — besøke tilstander som 1, 2, 3, og så videre — men den vil aldri besøke noen negative tilstander. Som et resultat kan vi ikke estimere verdifunksjoner for tilstander til venstre for origo, rett og slett fordi agenten aldri opplever dem.

Hovedproblemet er altså: hvis visse deler av tilstandsrommet aldri utforskes, vil deres verdiestimat forbli unøyaktige eller udefinerte. En vanlig løsning på dette problemet er bruk av utforskende starttilstander.

Med utforskende starttilstander begynner hver episode ikke i en fast starttilstand som 0, men i en tilfeldig valgt tilstand. Når episoden starter, følger agenten sin nåværende policy som vanlig. Over tid, ved å starte fra mange ulike punkter i tilstandsrommet, får agenten besøkt alle tilstander — ikke bare de policyen naturlig ville ført den til. Dette gjør at Monte Carlo-metoden kan gi mer nøyaktige og komplette verdiestimat for hele tilstandsrommet.

Pseudokode

Denne pseudokoden bruker hver-besøk-tilnærmingen sammen med utforskende startpunkter.

1. Hvordan skiller første-besøk MC-metoden seg fra hver-besøk MC-metoden?

2. Hva er hovedfordelen med å bruke utforskende startpunkter i Monte Carlo-metoder?

question mark

Hvordan skiller første-besøk MC-metoden seg fra hver-besøk MC-metoden?

Select the correct answer

question mark

Hva er hovedfordelen med å bruke utforskende startpunkter i Monte Carlo-metoder?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 2

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
Estimering av Verdifunksjon

La oss begynne med å se på et kjent konsept: tilstandsverdifunksjonen, betegnet som vπ(s)v_\pi(s). Den kan defineres som

vπ(s)=Eπ[GtSt=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi [ G_t | S_t = s]

Målet i dette kapittelet er å estimere denne funksjonen fra data, gitt at vi har en fast politikk π\pi, men ikke har tilgang til miljøets modell.

Monte Carlo-estimering

Monte Carlo-metoder tilnærmer denne estimeringsoppgaven ved å samle episoder av erfaring under politikken π\pi, og deretter bruke disse prøvene til å lage empiriske estimater av vπ(s)v_\pi(s).

Generelt kan prosessen deles inn i følgende trinn:

  1. Generer en episode ved å bruke politikk π\pi;
  2. Lagre den oppnådde returverdien for hver tilstand som opptrer i episoden;
  3. Gjenta trinn 1-2 over tid;
  4. Beregn de nye verdiene ved å ta gjennomsnittet av returene for hver tilstand.

Innhenting av avkastning

Monte Carlo-estimering av verdifunksjonen krever innhenting av avkastning fra genererte episoder. For å beregne disse avkastningene kan to hovedmetoder benyttes:

  • Første-besøk: for hver tilstand ss som oppstår i en episode, tas kun avkastningen etter første forekomst med i betraktningen. Senere forekomster av samme tilstand i samme episode ignoreres for estimeringsformål;
  • Alle-besøk: hver forekomst av en tilstand ss i en episode benyttes. Det vil si at avkastningen etter hvert besøk til tilstanden inkluderes i estimatet, selv om tilstanden opptrer flere ganger i samme episode.

Utforskende starttilstander

Tenk deg en enkel endimensjonal verden representert av en linje som strekker seg fra -10 til +10. Agenten starter på posisjon 0, og dens nåværende policy tilsier at den alltid beveger seg til høyre ved hvert tidsskritt.

Hvis vi forsøker å generere episoder under denne policyen, hva skjer da? Agenten vil kontinuerlig bevege seg mot den positive enden av linjen — besøke tilstander som 1, 2, 3, og så videre — men den vil aldri besøke noen negative tilstander. Som et resultat kan vi ikke estimere verdifunksjoner for tilstander til venstre for origo, rett og slett fordi agenten aldri opplever dem.

Hovedproblemet er altså: hvis visse deler av tilstandsrommet aldri utforskes, vil deres verdiestimat forbli unøyaktige eller udefinerte. En vanlig løsning på dette problemet er bruk av utforskende starttilstander.

Med utforskende starttilstander begynner hver episode ikke i en fast starttilstand som 0, men i en tilfeldig valgt tilstand. Når episoden starter, følger agenten sin nåværende policy som vanlig. Over tid, ved å starte fra mange ulike punkter i tilstandsrommet, får agenten besøkt alle tilstander — ikke bare de policyen naturlig ville ført den til. Dette gjør at Monte Carlo-metoden kan gi mer nøyaktige og komplette verdiestimat for hele tilstandsrommet.

Pseudokode

Denne pseudokoden bruker hver-besøk-tilnærmingen sammen med utforskende startpunkter.

1. Hvordan skiller første-besøk MC-metoden seg fra hver-besøk MC-metoden?

2. Hva er hovedfordelen med å bruke utforskende startpunkter i Monte Carlo-metoder?

question mark

Hvordan skiller første-besøk MC-metoden seg fra hver-besøk MC-metoden?

Select the correct answer

question mark

Hva er hovedfordelen med å bruke utforskende startpunkter i Monte Carlo-metoder?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 2
some-alt