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

Ved å erstatte politikkevaluering-steget i den standard politikkiterasjons-algoritmen med Monte Carlo-estimeringsteknikkene beskrevet i forrige kapittel, kan vi allerede utlede en ny variant av politikkiterasjon—en som baserer seg på prøvet erfaring i stedet for dynamisk programmering.

Det finnes imidlertid en kritisk begrensning. I tradisjonell politikkiterasjon avhenger politikkforbedrings-steget av å ha tilgang til en komplett modell av miljøet. Spesielt bruker vi følgende uttrykk for å oppdatere politikken:

π(s)arg maxas,rp(s,rs,a)(r+γv(s))\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

Denne ligningen forutsetter at vi kjenner overgangssannsynlighetene p(s,rs,a)p(s', r | s, a). Men dette er nettopp problemet: Monte Carlo-metoder er utviklet for modellfrie omgivelser, der miljøets overgangsdynamikk er ukjent. Hvis en komplett modell er tilgjengelig, kan vi like gjerne bruke dynamisk programmering gjennomgående, også for politikkevaluering, siden det ville vært mer effektivt og presist.

Derfor, selv om det å erstatte Monte Carlo-metoder for verdiberegning er et steg mot modellfri forsterkningslæring, må vi også finne en måte å utføre politikkforbedring uten å være avhengig av kunnskap om modellen. Dette krever et skifte fra tilstandsverdifunksjon til aksjonsverdifunksjon.

Hvorfor aksjonsverdier?

Ved å bruke aksjonsverdier er det mulig å utføre politikkforbedring uten å trenge en modell av miljøet. I stedet for å basere oss på overgangssannsynligheter for å beregne forventet avkastning, kan vi direkte velge de handlingene som ser ut til å gi høyest verdi. Politikkforbedringssteget blir da:

π(s)arg maxaq(s,a)sS\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

Og det er ikke vanskelig å bevise at den nye politikken ikke er dårligere enn den gamle, siden teoremet om politikkforbedring fortsatt kan anvendes:

qπk(s,πk+1(s))=qπk(s,arg maxaqπk(s,a))=maxaqπk(s,a)qπk(s,πk(s))=vπk(s)\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

Og, som med DP, garanterer dette teoremet at enten er πk+1\pi_{k+1} bedre enn πk\pi_k, eller at de begge er like og optimale.

Estimering av handlingsverdifunksjon

Estimeringsprosessen er nesten identisk med tilstandsverdifunksjonen. Alle ideer som brukes for å estimere tilstandsverdier, kan også benyttes for å estimere handlingsverdier.

Pseudokode

På denne måten, med nok iterasjoner, vil de estimerte handlingsverdiene nærme seg de sanne handlingsverdiene.

Med dette kan du allerede bygge en metode tilsvarende politikkiterasjon som ikke er avhengig av en modell. For å gjøre dette, erstatter du trinnene politikkevaluering og politikkforbedring med prosessene beskrevet ovenfor.

Optimalisering

Selv om evaluerings-steget kan utføres ved hjelp av Monte Carlo-estimering som beskrevet, har det en tendens til å være beregningsmessig ineffektivt. Som du allerede har sett, krever Monte Carlo-metoder vanligvis et stort antall utvalg for å gi rimelig nøyaktige estimater. Hvis vi følger en struktur som ligner på politikkiterasjon, forsterkes denne ineffektiviteten: etter hver politikkforbedring må vi kjøre Monte Carlo-estimering på nytt for å evaluere den nye politikken — noe som gir betydelig merarbeid og treg læring.

Et mer naturlig alternativ er å oppdatere politikken umiddelbart etter hver gjennomførte episode. I stedet for å vente til en fullstendig runde med politikkevaluering er ferdig, lar vi agenten forbedre sin atferd episode for episode, ved å bruke de nyeste estimatene for handlingsverdier.

Dette resulterer i en metode som ligner mer på verdiiterasjon: en kombinasjon av evaluering og forbedring i ett steg. Dette øker utvalgsutnyttelsen og gir raskere beregninger.

Pseudokode

Denne algoritmen følger en GPI-ramme, siden den har trinn for policyevaluering og policyforbedring, og den kalles Monte Carlo-kontroll. Den største ulempen med denne spesifikke implementeringen er antakelsen om utforskende starttilstander. I de neste kapitlene vil du se hvorfor dette er et problem, og hvordan det kan håndteres.

question mark

Hva er hovedfordelen med å bruke aksjonsverdier i stedet for tilstandsverdier i Monte Carlo-kontroll?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 3

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
Monte Carlo-Kontroll

Ved å erstatte politikkevaluering-steget i den standard politikkiterasjons-algoritmen med Monte Carlo-estimeringsteknikkene beskrevet i forrige kapittel, kan vi allerede utlede en ny variant av politikkiterasjon—en som baserer seg på prøvet erfaring i stedet for dynamisk programmering.

Det finnes imidlertid en kritisk begrensning. I tradisjonell politikkiterasjon avhenger politikkforbedrings-steget av å ha tilgang til en komplett modell av miljøet. Spesielt bruker vi følgende uttrykk for å oppdatere politikken:

π(s)arg maxas,rp(s,rs,a)(r+γv(s))\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

Denne ligningen forutsetter at vi kjenner overgangssannsynlighetene p(s,rs,a)p(s', r | s, a). Men dette er nettopp problemet: Monte Carlo-metoder er utviklet for modellfrie omgivelser, der miljøets overgangsdynamikk er ukjent. Hvis en komplett modell er tilgjengelig, kan vi like gjerne bruke dynamisk programmering gjennomgående, også for politikkevaluering, siden det ville vært mer effektivt og presist.

Derfor, selv om det å erstatte Monte Carlo-metoder for verdiberegning er et steg mot modellfri forsterkningslæring, må vi også finne en måte å utføre politikkforbedring uten å være avhengig av kunnskap om modellen. Dette krever et skifte fra tilstandsverdifunksjon til aksjonsverdifunksjon.

Hvorfor aksjonsverdier?

Ved å bruke aksjonsverdier er det mulig å utføre politikkforbedring uten å trenge en modell av miljøet. I stedet for å basere oss på overgangssannsynligheter for å beregne forventet avkastning, kan vi direkte velge de handlingene som ser ut til å gi høyest verdi. Politikkforbedringssteget blir da:

π(s)arg maxaq(s,a)sS\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

Og det er ikke vanskelig å bevise at den nye politikken ikke er dårligere enn den gamle, siden teoremet om politikkforbedring fortsatt kan anvendes:

qπk(s,πk+1(s))=qπk(s,arg maxaqπk(s,a))=maxaqπk(s,a)qπk(s,πk(s))=vπk(s)\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

Og, som med DP, garanterer dette teoremet at enten er πk+1\pi_{k+1} bedre enn πk\pi_k, eller at de begge er like og optimale.

Estimering av handlingsverdifunksjon

Estimeringsprosessen er nesten identisk med tilstandsverdifunksjonen. Alle ideer som brukes for å estimere tilstandsverdier, kan også benyttes for å estimere handlingsverdier.

Pseudokode

På denne måten, med nok iterasjoner, vil de estimerte handlingsverdiene nærme seg de sanne handlingsverdiene.

Med dette kan du allerede bygge en metode tilsvarende politikkiterasjon som ikke er avhengig av en modell. For å gjøre dette, erstatter du trinnene politikkevaluering og politikkforbedring med prosessene beskrevet ovenfor.

Optimalisering

Selv om evaluerings-steget kan utføres ved hjelp av Monte Carlo-estimering som beskrevet, har det en tendens til å være beregningsmessig ineffektivt. Som du allerede har sett, krever Monte Carlo-metoder vanligvis et stort antall utvalg for å gi rimelig nøyaktige estimater. Hvis vi følger en struktur som ligner på politikkiterasjon, forsterkes denne ineffektiviteten: etter hver politikkforbedring må vi kjøre Monte Carlo-estimering på nytt for å evaluere den nye politikken — noe som gir betydelig merarbeid og treg læring.

Et mer naturlig alternativ er å oppdatere politikken umiddelbart etter hver gjennomførte episode. I stedet for å vente til en fullstendig runde med politikkevaluering er ferdig, lar vi agenten forbedre sin atferd episode for episode, ved å bruke de nyeste estimatene for handlingsverdier.

Dette resulterer i en metode som ligner mer på verdiiterasjon: en kombinasjon av evaluering og forbedring i ett steg. Dette øker utvalgsutnyttelsen og gir raskere beregninger.

Pseudokode

Denne algoritmen følger en GPI-ramme, siden den har trinn for policyevaluering og policyforbedring, og den kalles Monte Carlo-kontroll. Den største ulempen med denne spesifikke implementeringen er antakelsen om utforskende starttilstander. I de neste kapitlene vil du se hvorfor dette er et problem, og hvordan det kan håndteres.

question mark

Hva er hovedfordelen med å bruke aksjonsverdier i stedet for tilstandsverdier i Monte Carlo-kontroll?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 3
some-alt