Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Optimalitetsbetingelser | Dynamisk Programmering
Introduktion til Reinforcement Learning

bookOptimalitetsbetingelser

I det forrige kapitel lærte du om Bellman-ligninger for tilstandsværdi- og tilstands-handlingsværdifunktioner. Disse ligninger beskriver, hvordan tilstandsværdier kan defineres rekursivt gennem værdierne af andre tilstande, hvor værdierne afhænger af en given politik. Dog er ikke alle politikker lige effektive. Faktisk giver værdifunktioner en delvis orden for politikker, som kan beskrives således:

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

Så politik π\pi er bedre end eller lig med politik π′\pi', hvis den forventede gevinst for politik π\pi for alle mulige tilstande ikke er mindre end den forventede gevinst for politik π′\pi'.

Note
Studér Mere

En delvis orden følger de sædvanlige ordensregler, men kræver ikke, at alle par sammenlignes. I vores tilfælde kan vi kun rangere to politikker, hvis de giver samme resultater, eller hvis den ene klart overgår den anden. I alle andre tilfælde forbliver politikker ukomparable.

Optimal politik

Note
Definition

For enhver MDP findes der mindst én politik, der er lige så god som eller bedre end alle andre politikker. Denne politik kaldes en optimal politik π∗\pi_*. Selvom der kan være mange optimale politikker, betegnes de alle som π∗\pi_*.

Hvorfor eksisterer der altid en optimal politik?

Du undrer dig måske over, hvorfor en optimal politik altid eksisterer for enhver MDP. Det er et godt spørgsmål, og intuitionen bag det er overraskende enkel. Husk, at tilstande i en MDP fuldstændigt indfanger miljøets tilstand. Dette indebærer, at hver tilstand er uafhængig af alle andre: handlingen valgt i én tilstand påvirker ikke de belønninger eller resultater, der kan opnås i en anden. Derfor, ved at vælge den optimale handling i hver tilstand separat, opnår du naturligt den samlet bedste rækkefølge af handlinger gennem hele processen. Og dette sæt af optimale handlinger i hver tilstand udgør en optimal politik.

Derudover findes der altid mindst én politik, der er både optimal og deterministisk. Faktisk, hvis to handlinger aa og a′a' i en given tilstand ss giver det samme forventede afkast, vil det ikke påvirke politikkens optimalitet at vælge blot én af dem. Anvendes dette princip på hver eneste tilstand, bliver politikken deterministisk uden at miste sin optimalitet.

Optimale værdifunktioner

Optimale politikker deler de samme værdifunktioner — dette bliver tydeligt, når vi overvejer, hvordan politikker sammenlignes. Det betyder, at optimale politikker deler både tilstands-værdifunktion og aktions-værdifunktion.

Derudover har optimale værdifunktioner deres egne Bellman-ligninger, som kan skrives uden reference til en specifik politik. Disse ligninger kaldes Bellman-optimalitetsligninger.

Optimal tilstands-værdifunktion

Note
Definition

Optimal tilstands-værdifunktion V∗V_* (eller v∗v_*) repræsenterer den maksimale forventede gevinst, der kan opnås fra en given tilstand ved at følge en optimal politik.

Det kan matematisk defineres således:

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 optimalitetsligning for denne værdifunktion kan udledes således:

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}

Intuition

Som du allerede ved, findes der altid mindst én politik, der er både optimal og deterministisk. En sådan politik vil for hver tilstand konsekvent vælge én bestemt handling, der maksimerer den forventede belønning. Derfor vil sandsynligheden for at vælge denne optimale handling altid være 1, og sandsynligheden for at vælge enhver anden handling vil være 0. Givet dette behøver den oprindelige Bellman-ligning ikke længere summationsoperatoren. I stedet, da vi ved, at vi altid vælger den bedst mulige handling, kan vi blot erstatte summen med at tage et maksimum over alle tilgængelige handlinger.

Optimal handlingsværdifunktion

Note
Definition

Optimal handlingsværdifunktion Q∗Q_* (eller q∗q_*) repræsenterer den maksimale forventede belønning, der kan opnås ved at vælge en bestemt handling i en bestemt tilstand og derefter følge den optimale politik.

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 optimalitetsligning for denne værdifunktion kan udledes således:

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}

Intuition

På samme måde som tilstandsværdifunktionen kan summen erstattes med at tage maksimum over alle tilgængelige handlinger.

question mark

Hvorfor eksisterer der altid en optimal politik for enhver Markov beslutningsproces?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 3

Spørg AI

expand

Spørg AI

ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Awesome!

Completion rate improved to 2.7

bookOptimalitetsbetingelser

Stryg for at vise menuen

I det forrige kapitel lærte du om Bellman-ligninger for tilstandsværdi- og tilstands-handlingsværdifunktioner. Disse ligninger beskriver, hvordan tilstandsværdier kan defineres rekursivt gennem værdierne af andre tilstande, hvor værdierne afhænger af en given politik. Dog er ikke alle politikker lige effektive. Faktisk giver værdifunktioner en delvis orden for politikker, som kan beskrives således:

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

Så politik π\pi er bedre end eller lig med politik π′\pi', hvis den forventede gevinst for politik π\pi for alle mulige tilstande ikke er mindre end den forventede gevinst for politik π′\pi'.

Note
Studér Mere

En delvis orden følger de sædvanlige ordensregler, men kræver ikke, at alle par sammenlignes. I vores tilfælde kan vi kun rangere to politikker, hvis de giver samme resultater, eller hvis den ene klart overgår den anden. I alle andre tilfælde forbliver politikker ukomparable.

Optimal politik

Note
Definition

For enhver MDP findes der mindst én politik, der er lige så god som eller bedre end alle andre politikker. Denne politik kaldes en optimal politik π∗\pi_*. Selvom der kan være mange optimale politikker, betegnes de alle som π∗\pi_*.

Hvorfor eksisterer der altid en optimal politik?

Du undrer dig måske over, hvorfor en optimal politik altid eksisterer for enhver MDP. Det er et godt spørgsmål, og intuitionen bag det er overraskende enkel. Husk, at tilstande i en MDP fuldstændigt indfanger miljøets tilstand. Dette indebærer, at hver tilstand er uafhængig af alle andre: handlingen valgt i én tilstand påvirker ikke de belønninger eller resultater, der kan opnås i en anden. Derfor, ved at vælge den optimale handling i hver tilstand separat, opnår du naturligt den samlet bedste rækkefølge af handlinger gennem hele processen. Og dette sæt af optimale handlinger i hver tilstand udgør en optimal politik.

Derudover findes der altid mindst én politik, der er både optimal og deterministisk. Faktisk, hvis to handlinger aa og a′a' i en given tilstand ss giver det samme forventede afkast, vil det ikke påvirke politikkens optimalitet at vælge blot én af dem. Anvendes dette princip på hver eneste tilstand, bliver politikken deterministisk uden at miste sin optimalitet.

Optimale værdifunktioner

Optimale politikker deler de samme værdifunktioner — dette bliver tydeligt, når vi overvejer, hvordan politikker sammenlignes. Det betyder, at optimale politikker deler både tilstands-værdifunktion og aktions-værdifunktion.

Derudover har optimale værdifunktioner deres egne Bellman-ligninger, som kan skrives uden reference til en specifik politik. Disse ligninger kaldes Bellman-optimalitetsligninger.

Optimal tilstands-værdifunktion

Note
Definition

Optimal tilstands-værdifunktion V∗V_* (eller v∗v_*) repræsenterer den maksimale forventede gevinst, der kan opnås fra en given tilstand ved at følge en optimal politik.

Det kan matematisk defineres således:

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 optimalitetsligning for denne værdifunktion kan udledes således:

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}

Intuition

Som du allerede ved, findes der altid mindst én politik, der er både optimal og deterministisk. En sådan politik vil for hver tilstand konsekvent vælge én bestemt handling, der maksimerer den forventede belønning. Derfor vil sandsynligheden for at vælge denne optimale handling altid være 1, og sandsynligheden for at vælge enhver anden handling vil være 0. Givet dette behøver den oprindelige Bellman-ligning ikke længere summationsoperatoren. I stedet, da vi ved, at vi altid vælger den bedst mulige handling, kan vi blot erstatte summen med at tage et maksimum over alle tilgængelige handlinger.

Optimal handlingsværdifunktion

Note
Definition

Optimal handlingsværdifunktion Q∗Q_* (eller q∗q_*) repræsenterer den maksimale forventede belønning, der kan opnås ved at vælge en bestemt handling i en bestemt tilstand og derefter følge den optimale politik.

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 optimalitetsligning for denne værdifunktion kan udledes således:

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}

Intuition

På samme måde som tilstandsværdifunktionen kan summen erstattes med at tage maksimum over alle tilgængelige handlinger.

question mark

Hvorfor eksisterer der altid en optimal politik for enhver Markov beslutningsproces?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 3
some-alt