Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Leer Optimaliteitsvoorwaarden | Dynamisch Programmeren
Introductie tot Reinforcement Learning

bookOptimaliteitsvoorwaarden

In het vorige hoofdstuk heb je geleerd over de Bellman-vergelijkingen voor toestandswaarde- en toestand-actie-waardefuncties. Deze vergelijkingen beschrijven hoe toestandswaarden recursief kunnen worden gedefinieerd via de waarden van andere toestanden, waarbij de waarden afhankelijk zijn van een gegeven beleid. Niet alle beleidsvormen zijn echter even effectief. Waardefuncties bieden namelijk een partiële ordening voor beleidsvormen, die als volgt kan worden beschreven:

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

Beleid π\pi is beter dan of gelijk aan beleid π′\pi' als voor alle mogelijke toestanden de verwachte opbrengst van beleid π\pi niet lager is dan de verwachte opbrengst van beleid π′\pi'.

Note
Meer leren

Een partiële ordening volgt de gebruikelijke ordeningsregels, maar vereist niet dat elk paar wordt vergeleken. In ons geval kunnen we twee beleidsvormen alleen rangschikken als ze dezelfde resultaten opleveren, of als één duidelijk beter presteert dan de ander. In alle andere gevallen blijven beleidsvormen onvergelijkbaar.

Optimale Beleidsstrategie

Note
Definitie

Voor elke MDP bestaat er ten minste één beleidsstrategie die even goed is als of beter dan alle andere beleidsstrategieën. Deze beleidsstrategie wordt een optimale beleidsstrategie π∗\pi_* genoemd. Hoewel er meerdere optimale beleidsstrategieën kunnen zijn, worden ze allemaal aangeduid als π∗\pi_*.

Waarom bestaat er altijd een optimale beleidsstrategie?

Je vraagt je misschien af waarom er voor elke MDP altijd een optimaal beleid bestaat. Dat is een goede vraag, en de intuïtie erachter is verrassend eenvoudig. Onthoud dat toestanden in een MDP de toestand van de omgeving volledig vastleggen. Dit betekent dat elke toestand onafhankelijk is van alle andere: de actie die in de ene toestand wordt gekozen, beïnvloedt niet de beloningen of uitkomsten die in een andere toestand haalbaar zijn. Door in elke toestand afzonderlijk de optimale actie te kiezen, kom je vanzelf tot de algeheel beste reeks acties voor het hele proces. En deze verzameling optimale acties in elke toestand vormt een optimaal beleid.

Bovendien is er altijd minstens één beleid dat zowel optimaal als deterministisch is. Als voor een bepaalde toestand ss twee acties aa en a′a' dezelfde verwachte opbrengst opleveren, zal het kiezen van slechts één van deze acties de optimaliteit van het beleid niet beïnvloeden. Door dit principe op elke afzonderlijke toestand toe te passen, wordt het beleid deterministisch terwijl de optimaliteit behouden blijft.

Optimale waardefuncties

Optimale beleidsregels delen dezelfde waarde-functies — een feit dat duidelijk wordt wanneer we bekijken hoe beleidsregels vergeleken worden. Dit betekent dat optimale beleidsregels zowel de toestandswaarde-functie als de actie-waarde-functie delen.

Daarnaast hebben optimale waarde-functies hun eigen Bellman-vergelijkingen die kunnen worden opgesteld zonder verwijzing naar een specifiek beleid. Deze vergelijkingen worden Bellman-optimaliteitsvergelijkingen genoemd.

Optimale toestandswaarde-functie

Note
Definitie

Optimale toestandswaarde-functie V∗V_* (of v∗v_*) vertegenwoordigt de maximaal verwachte opbrengst die haalbaar is vanuit een bepaalde toestand door een optimaal beleid te volgen.

Het kan wiskundig als volgt worden gedefinieerd:

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]

Bellman-optimaliteitsvergelijking voor deze waardefunctie kan als volgt worden afgeleid:

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}

Intuïtie

Zoals reeds bekend, bestaat er altijd ten minste één beleid dat zowel optimaal als deterministisch is. Zo'n beleid kiest voor elke toestand consequent één specifieke actie die de verwachte opbrengst maximaliseert. Daarom is de kans om deze optimale actie te kiezen altijd 1, en de kans om elke andere actie te kiezen altijd 0. Gegeven dit gegeven is de oorspronkelijke Bellman-vergelijking niet langer afhankelijk van de somoperator. In plaats daarvan, omdat we altijd de best mogelijke actie kiezen, kunnen we de som vervangen door het nemen van een maximum over alle beschikbare acties.

Optimale actie-waardefunctie

Note
Definitie

Optimale actie-waardefunctie Q∗Q_* (of q∗q_*) geeft de maximaal verwachte opbrengst weer die haalbaar is door een bepaalde actie in een bepaalde toestand te nemen en vervolgens het optimale beleid te volgen.

Het kan wiskundig als volgt worden gedefinieerd:

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]

Bellman-optimaliteitsvergelijking voor deze waardefunctie kan als volgt worden afgeleid:

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}

Intuïtie

Net als bij de toestandswaardefunctie kan de som worden vervangen door het nemen van het maximum over alle beschikbare acties.

question mark

Waarom bestaat er altijd een optimaal beleid voor elk Markov-beslissingsproces?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 3

Vraag AI

expand

Vraag AI

ChatGPT

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Awesome!

Completion rate improved to 2.7

bookOptimaliteitsvoorwaarden

Veeg om het menu te tonen

In het vorige hoofdstuk heb je geleerd over de Bellman-vergelijkingen voor toestandswaarde- en toestand-actie-waardefuncties. Deze vergelijkingen beschrijven hoe toestandswaarden recursief kunnen worden gedefinieerd via de waarden van andere toestanden, waarbij de waarden afhankelijk zijn van een gegeven beleid. Niet alle beleidsvormen zijn echter even effectief. Waardefuncties bieden namelijk een partiële ordening voor beleidsvormen, die als volgt kan worden beschreven:

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

Beleid π\pi is beter dan of gelijk aan beleid π′\pi' als voor alle mogelijke toestanden de verwachte opbrengst van beleid π\pi niet lager is dan de verwachte opbrengst van beleid π′\pi'.

Note
Meer leren

Een partiële ordening volgt de gebruikelijke ordeningsregels, maar vereist niet dat elk paar wordt vergeleken. In ons geval kunnen we twee beleidsvormen alleen rangschikken als ze dezelfde resultaten opleveren, of als één duidelijk beter presteert dan de ander. In alle andere gevallen blijven beleidsvormen onvergelijkbaar.

Optimale Beleidsstrategie

Note
Definitie

Voor elke MDP bestaat er ten minste één beleidsstrategie die even goed is als of beter dan alle andere beleidsstrategieën. Deze beleidsstrategie wordt een optimale beleidsstrategie π∗\pi_* genoemd. Hoewel er meerdere optimale beleidsstrategieën kunnen zijn, worden ze allemaal aangeduid als π∗\pi_*.

Waarom bestaat er altijd een optimale beleidsstrategie?

Je vraagt je misschien af waarom er voor elke MDP altijd een optimaal beleid bestaat. Dat is een goede vraag, en de intuïtie erachter is verrassend eenvoudig. Onthoud dat toestanden in een MDP de toestand van de omgeving volledig vastleggen. Dit betekent dat elke toestand onafhankelijk is van alle andere: de actie die in de ene toestand wordt gekozen, beïnvloedt niet de beloningen of uitkomsten die in een andere toestand haalbaar zijn. Door in elke toestand afzonderlijk de optimale actie te kiezen, kom je vanzelf tot de algeheel beste reeks acties voor het hele proces. En deze verzameling optimale acties in elke toestand vormt een optimaal beleid.

Bovendien is er altijd minstens één beleid dat zowel optimaal als deterministisch is. Als voor een bepaalde toestand ss twee acties aa en a′a' dezelfde verwachte opbrengst opleveren, zal het kiezen van slechts één van deze acties de optimaliteit van het beleid niet beïnvloeden. Door dit principe op elke afzonderlijke toestand toe te passen, wordt het beleid deterministisch terwijl de optimaliteit behouden blijft.

Optimale waardefuncties

Optimale beleidsregels delen dezelfde waarde-functies — een feit dat duidelijk wordt wanneer we bekijken hoe beleidsregels vergeleken worden. Dit betekent dat optimale beleidsregels zowel de toestandswaarde-functie als de actie-waarde-functie delen.

Daarnaast hebben optimale waarde-functies hun eigen Bellman-vergelijkingen die kunnen worden opgesteld zonder verwijzing naar een specifiek beleid. Deze vergelijkingen worden Bellman-optimaliteitsvergelijkingen genoemd.

Optimale toestandswaarde-functie

Note
Definitie

Optimale toestandswaarde-functie V∗V_* (of v∗v_*) vertegenwoordigt de maximaal verwachte opbrengst die haalbaar is vanuit een bepaalde toestand door een optimaal beleid te volgen.

Het kan wiskundig als volgt worden gedefinieerd:

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]

Bellman-optimaliteitsvergelijking voor deze waardefunctie kan als volgt worden afgeleid:

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}

Intuïtie

Zoals reeds bekend, bestaat er altijd ten minste één beleid dat zowel optimaal als deterministisch is. Zo'n beleid kiest voor elke toestand consequent één specifieke actie die de verwachte opbrengst maximaliseert. Daarom is de kans om deze optimale actie te kiezen altijd 1, en de kans om elke andere actie te kiezen altijd 0. Gegeven dit gegeven is de oorspronkelijke Bellman-vergelijking niet langer afhankelijk van de somoperator. In plaats daarvan, omdat we altijd de best mogelijke actie kiezen, kunnen we de som vervangen door het nemen van een maximum over alle beschikbare acties.

Optimale actie-waardefunctie

Note
Definitie

Optimale actie-waardefunctie Q∗Q_* (of q∗q_*) geeft de maximaal verwachte opbrengst weer die haalbaar is door een bepaalde actie in een bepaalde toestand te nemen en vervolgens het optimale beleid te volgen.

Het kan wiskundig als volgt worden gedefinieerd:

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]

Bellman-optimaliteitsvergelijking voor deze waardefunctie kan als volgt worden afgeleid:

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}

Intuïtie

Net als bij de toestandswaardefunctie kan de som worden vervangen door het nemen van het maximum over alle beschikbare acties.

question mark

Waarom bestaat er altijd een optimaal beleid voor elk Markov-beslissingsproces?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 3
some-alt