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

Kursinnhold

Introduksjon til Forsterkende Læring

Introduksjon til Forsterkende Læring

1. Kjerneprinsipper i RL
Hva er RL?RL Kontra Andre LæringsparadigmerMarkov BeslutningsprosessEpisoder og AvkastningModell, policy og verdierUtforskning vs UtnyttelseGrunnleggende om GymnasiumUtfordring: Oppsett av et Miljø
2. Multi-Armet Bandittproblem
ProbleminnledningAksjonsverdierEpsilon-grådig AlgoritmeAlgoritme for Øvre KonfidensgrenseGradientbandittalgoritmeUtfordring: Multi-Armede Banditter
3. Dynamisk Programmering
Hva er dynamisk programmering?Bellman-ligningerOptimalitetsbetingelserPolicyvurderingPolicyforbedringGeneralisert PolicyiterasjonPolicyiterasjonVerdiiterasjonUtfordring: Dynamisk Programmering
4. Monte Carlo-metoder
Hva er Monte Carlo-metoder?Estimering av VerdifunksjonMonte Carlo-KontrollUtforskningsmetoderOn-Policy Monte Carlo-KontrollOff-Policy Monte Carlo-KontrollInkrementelle ImplementasjonerUtfordring: Monte Carlo-metoder
5. Temporal Difference-læring
Hva er temporær differanse-læring?TD(0): VerdifunksjonsestimeringSARSA: On-Policy TD-LæringQ-læring: Off-Policy TD-LæringGeneralisering av TD-læringUtfordring: Temporær Differanse-Læring

book
Optimalitetsbetingelser

I forrige kapittel lærte du om Bellman-likninger for tilstandsverdi- og tilstands-handlingsverdifunksjoner. Disse likningene beskriver hvordan tilstandsverdier kan defineres rekursivt gjennom verdiene til andre tilstander, hvor verdiene avhenger av en gitt policy. Imidlertid er ikke alle policies like effektive. Faktisk gir verdifunksjoner en delvis ordning for policies, som kan beskrives slik:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Så policy π\pi er bedre enn eller lik policy π′\pi' hvis for alle mulige tilstander er den forventede avkastningen til policy π\pi ikke mindre enn den forventede avkastningen til policy π′\pi'.

Note
Les mer

En delvis ordning følger de vanlige ordningsreglene, men tvinger ikke alle par til å sammenlignes. I vårt tilfelle kan vi bare rangere to policies hvis de gir samme resultat, eller hvis en av dem tydelig overgår den andre. I alle andre tilfeller forblir policies ukomparerbare.

Optimal politikk

Note
Definisjon

For enhver MDP finnes det minst én politikk som er like god som eller bedre enn alle andre politiker. Denne politikken kalles en optimal politikk π∗\pi_*. Selv om det kan finnes mange optimale politiker, betegnes alle som π∗\pi_*.

Hvorfor eksisterer alltid en optimal politikk?

Du lurer kanskje på hvorfor en optimal policy alltid eksisterer for enhver MDP. Det er et godt spørsmål, og intuisjonen bak dette er overraskende enkel. Husk at tilstander i en MDP fanger opp miljøets tilstand fullstendig. Dette innebærer at hver tilstand er uavhengig av alle andre: handlingen som velges i én tilstand påvirker ikke belønningene eller utfallene som kan oppnås i en annen. Derfor, ved å velge den optimale handlingen i hver tilstand separat, kommer du naturlig frem til den beste totale handlingssekvensen gjennom hele prosessen. Og dette settet av optimale handlinger i hver tilstand utgjør en optimal policy.

Videre finnes det alltid minst én policy som er både optimal og deterministisk. Faktisk, hvis det for en tilstand ss finnes to handlinger aa og a′a' som gir samme forventede avkastning, vil det å velge bare én av dem ikke påvirke policyens optimalitet. Ved å anvende dette prinsippet på hver enkelt tilstand, blir policyen deterministisk samtidig som den beholder sin optimalitet.

Optimale verdifunksjoner

Optimale policyer deler de samme verdifunksjonene — noe som blir tydelig når vi vurderer hvordan policyer sammenlignes. Dette betyr at optimale policyer deler både tilstandsverdifunksjon og aksjonsverdifunksjon.

I tillegg har optimale verdifunksjoner sine egne Bellman-ligninger som kan skrives uten referanse til en spesifikk policy. Disse ligningene kalles Bellman optimalitetsligninger.

Optimal tilstandsverdifunksjon

Note
Definisjon

Optimal tilstandsverdifunksjon V∗V_* (eller v∗v_*) representerer den maksimale forventede avkastningen som kan oppnås fra en gitt tilstand ved å følge en optimal policy.

Det kan defineres matematisk slik:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

Bellmans optimalitetslikning for denne verdifunksjonen kan utledes slik:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuisjon

Som du allerede vet, finnes det alltid minst én politikk som er både optimal og deterministisk. En slik politikk vil, for hver tilstand, konsekvent velge én bestemt handling som maksimerer forventet avkastning. Derfor vil sannsynligheten for å velge denne optimale handlingen alltid være 1, og sannsynligheten for å velge andre handlinger vil være 0. Gitt dette, trenger ikke den opprinnelige Bellman-likningen lenger summeringsoperatoren. I stedet, siden vi vet at vi alltid vil velge den beste mulige handlingen, kan vi ganske enkelt erstatte summen med å ta et maksimum over alle tilgjengelige handlinger.

Optimalt handlingsverdifunksjon

Note
Definisjon

Optimalt handlingsverdifunksjon Q∗Q_* (eller q∗q_*) representerer den maksimale forventede avkastningen som kan oppnås ved å ta en bestemt handling i en bestemt tilstand og deretter følge den optimale policyen.

Det kan matematisk defineres slik:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Bellmans optimalitetslikning for denne verdifunksjonen kan utledes slik:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuisjon

På samme måte som for tilstandsverdifunksjonen, kan summen erstattes med å ta maksimum over alle tilgjengelige handlinger.

question mark

Hvorfor eksisterer det alltid en optimal politikk for enhver Markov beslutningsprosess?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. 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
Hva er RL?RL Kontra Andre LæringsparadigmerMarkov BeslutningsprosessEpisoder og AvkastningModell, policy og verdierUtforskning vs UtnyttelseGrunnleggende om GymnasiumUtfordring: Oppsett av et Miljø
2. Multi-Armet Bandittproblem
ProbleminnledningAksjonsverdierEpsilon-grådig AlgoritmeAlgoritme for Øvre KonfidensgrenseGradientbandittalgoritmeUtfordring: Multi-Armede Banditter
3. Dynamisk Programmering
Hva er dynamisk programmering?Bellman-ligningerOptimalitetsbetingelserPolicyvurderingPolicyforbedringGeneralisert PolicyiterasjonPolicyiterasjonVerdiiterasjonUtfordring: Dynamisk Programmering
4. Monte Carlo-metoder
Hva er Monte Carlo-metoder?Estimering av VerdifunksjonMonte Carlo-KontrollUtforskningsmetoderOn-Policy Monte Carlo-KontrollOff-Policy Monte Carlo-KontrollInkrementelle ImplementasjonerUtfordring: Monte Carlo-metoder
5. Temporal Difference-læring
Hva er temporær differanse-læring?TD(0): VerdifunksjonsestimeringSARSA: On-Policy TD-LæringQ-læring: Off-Policy TD-LæringGeneralisering av TD-læringUtfordring: Temporær Differanse-Læring

book
Optimalitetsbetingelser

I forrige kapittel lærte du om Bellman-likninger for tilstandsverdi- og tilstands-handlingsverdifunksjoner. Disse likningene beskriver hvordan tilstandsverdier kan defineres rekursivt gjennom verdiene til andre tilstander, hvor verdiene avhenger av en gitt policy. Imidlertid er ikke alle policies like effektive. Faktisk gir verdifunksjoner en delvis ordning for policies, som kan beskrives slik:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Så policy π\pi er bedre enn eller lik policy π′\pi' hvis for alle mulige tilstander er den forventede avkastningen til policy π\pi ikke mindre enn den forventede avkastningen til policy π′\pi'.

Note
Les mer

En delvis ordning følger de vanlige ordningsreglene, men tvinger ikke alle par til å sammenlignes. I vårt tilfelle kan vi bare rangere to policies hvis de gir samme resultat, eller hvis en av dem tydelig overgår den andre. I alle andre tilfeller forblir policies ukomparerbare.

Optimal politikk

Note
Definisjon

For enhver MDP finnes det minst én politikk som er like god som eller bedre enn alle andre politiker. Denne politikken kalles en optimal politikk π∗\pi_*. Selv om det kan finnes mange optimale politiker, betegnes alle som π∗\pi_*.

Hvorfor eksisterer alltid en optimal politikk?

Du lurer kanskje på hvorfor en optimal policy alltid eksisterer for enhver MDP. Det er et godt spørsmål, og intuisjonen bak dette er overraskende enkel. Husk at tilstander i en MDP fanger opp miljøets tilstand fullstendig. Dette innebærer at hver tilstand er uavhengig av alle andre: handlingen som velges i én tilstand påvirker ikke belønningene eller utfallene som kan oppnås i en annen. Derfor, ved å velge den optimale handlingen i hver tilstand separat, kommer du naturlig frem til den beste totale handlingssekvensen gjennom hele prosessen. Og dette settet av optimale handlinger i hver tilstand utgjør en optimal policy.

Videre finnes det alltid minst én policy som er både optimal og deterministisk. Faktisk, hvis det for en tilstand ss finnes to handlinger aa og a′a' som gir samme forventede avkastning, vil det å velge bare én av dem ikke påvirke policyens optimalitet. Ved å anvende dette prinsippet på hver enkelt tilstand, blir policyen deterministisk samtidig som den beholder sin optimalitet.

Optimale verdifunksjoner

Optimale policyer deler de samme verdifunksjonene — noe som blir tydelig når vi vurderer hvordan policyer sammenlignes. Dette betyr at optimale policyer deler både tilstandsverdifunksjon og aksjonsverdifunksjon.

I tillegg har optimale verdifunksjoner sine egne Bellman-ligninger som kan skrives uten referanse til en spesifikk policy. Disse ligningene kalles Bellman optimalitetsligninger.

Optimal tilstandsverdifunksjon

Note
Definisjon

Optimal tilstandsverdifunksjon V∗V_* (eller v∗v_*) representerer den maksimale forventede avkastningen som kan oppnås fra en gitt tilstand ved å følge en optimal policy.

Det kan defineres matematisk slik:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

Bellmans optimalitetslikning for denne verdifunksjonen kan utledes slik:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuisjon

Som du allerede vet, finnes det alltid minst én politikk som er både optimal og deterministisk. En slik politikk vil, for hver tilstand, konsekvent velge én bestemt handling som maksimerer forventet avkastning. Derfor vil sannsynligheten for å velge denne optimale handlingen alltid være 1, og sannsynligheten for å velge andre handlinger vil være 0. Gitt dette, trenger ikke den opprinnelige Bellman-likningen lenger summeringsoperatoren. I stedet, siden vi vet at vi alltid vil velge den beste mulige handlingen, kan vi ganske enkelt erstatte summen med å ta et maksimum over alle tilgjengelige handlinger.

Optimalt handlingsverdifunksjon

Note
Definisjon

Optimalt handlingsverdifunksjon Q∗Q_* (eller q∗q_*) representerer den maksimale forventede avkastningen som kan oppnås ved å ta en bestemt handling i en bestemt tilstand og deretter følge den optimale policyen.

Det kan matematisk defineres slik:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Bellmans optimalitetslikning for denne verdifunksjonen kan utledes slik:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuisjon

På samme måte som for tilstandsverdifunksjonen, kan summen erstattes med å ta maksimum over alle tilgjengelige handlinger.

question mark

Hvorfor eksisterer det alltid en optimal politikk for enhver Markov beslutningsprosess?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 3
some-alt