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 Reinforcement Learning

bookOptimalitetsbetingelser

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 den ene klart overgår den andre. I alle andre tilfeller forblir policies usammenlignbare.

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 flere 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 valgt 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 rekkefølgen av handlinger 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 to handlinger aa og a′a' gir samme forventede avkastning i en tilstand ss, 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 har samme verdifunksjoner — dette blir tydelig når vi vurderer hvordan policyer sammenlignes. Dette innebærer 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 en hvilken som helst annen handling vil være 0. Gitt dette, trenger ikke den opprinnelige Bellman-likningen lenger summeringsoperatoren. 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.

Optimal aksjonsverdifunksjon

Note
Definisjon

Optimal aksjonsverdifunksjon 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 som:

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 policy 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

Awesome!

Completion rate improved to 2.7

bookOptimalitetsbetingelser

Sveip for å vise menyen

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 den ene klart overgår den andre. I alle andre tilfeller forblir policies usammenlignbare.

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 flere 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 valgt 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 rekkefølgen av handlinger 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 to handlinger aa og a′a' gir samme forventede avkastning i en tilstand ss, 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 har samme verdifunksjoner — dette blir tydelig når vi vurderer hvordan policyer sammenlignes. Dette innebærer 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 en hvilken som helst annen handling vil være 0. Gitt dette, trenger ikke den opprinnelige Bellman-likningen lenger summeringsoperatoren. 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.

Optimal aksjonsverdifunksjon

Note
Definisjon

Optimal aksjonsverdifunksjon 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 som:

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 policy 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