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 forsterkningslæring

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

En 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 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 politikk 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, oppnår du naturlig den beste totale rekkefølgen av handlinger gjennom hele prosessen. Og dette settet av optimale handlinger i hver tilstand utgjør en optimal politikk.

Videre finnes det alltid minst én politikk 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 utbytte, vil det å velge bare én av dem ikke påvirke politikkens optimalitet. Ved å anvende dette prinsippet på hver enkelt tilstand blir politikken 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 Bellmans 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. 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 aksjonsverdi-funksjon

Note
Definisjon

Optimal aksjonsverdi-funksjon 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

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

En 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 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 politikk 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, oppnår du naturlig den beste totale rekkefølgen av handlinger gjennom hele prosessen. Og dette settet av optimale handlinger i hver tilstand utgjør en optimal politikk.

Videre finnes det alltid minst én politikk 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 utbytte, vil det å velge bare én av dem ikke påvirke politikkens optimalitet. Ved å anvende dette prinsippet på hver enkelt tilstand blir politikken 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 Bellmans 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. 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 aksjonsverdi-funksjon

Note
Definisjon

Optimal aksjonsverdi-funksjon 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