Leer Optimaliteitsvoorwaarden | Dynamisch Programmeren

Veeg om het menu te tonen

In het vorige hoofdstuk heb je geleerd over 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 beleidsregels zijn echter even effectief. Waardefuncties bieden in feite een partiële ordening voor beleidsregels, die als volgt kan worden beschreven:

\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'$ .

Meer leren

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

Optimale strategie

Definitie

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

Waarom bestaat er altijd een optimale strategie?

Je vraagt je misschien af waarom er altijd een optimale strategie bestaat voor elke MDP. 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 gekozen actie in de ene toestand beïnvloedt niet de beloningen of uitkomsten die in een andere toestand haalbaar zijn. Door dus in elke toestand afzonderlijk de optimale actie te kiezen, kom je vanzelf tot de algeheel beste reeks acties over het hele proces. En deze set van optimale acties in elke toestand vormt een optimale strategie.

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

Optimale waardefuncties

Optimale beleidsregels delen dezelfde waardefuncties — een feit dat duidelijk wordt wanneer we bekijken hoe beleidsregels met elkaar worden vergeleken. Dit betekent dat optimale beleidsregels zowel de toestandswaardefunctie als de actiewaardefunctie delen.

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

Optimale toestandswaardefunctie

Definitie

Optimale toestandswaardefunctie $V_*$ (of $v_*$ ) geeft de maximaal verwachte opbrengst weer die vanuit een bepaalde toestand kan worden bereikt door het volgen van een optimaal beleid.

Dit kan wiskundig als volgt worden gedefinieerd:

\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:

\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 je al weet, bestaat er altijd ten minste één beleid dat zowel optimaal als deterministisch is. Zo'n beleid zou voor elke toestand consequent één specifieke actie selecteren 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 is 0. Gegeven dit, heeft de oorspronkelijke Bellman-vergelijking de somoperator niet meer nodig. In plaats daarvan, aangezien we altijd de best mogelijke actie kiezen, kunnen we de som eenvoudig vervangen door het nemen van een maximum over alle beschikbare acties.

Optimale actie-waardefunctie

Definitie

Optimale actie-waardefunctie $Q_*$ (of $q_*$ ) geeft de maximale verwachte opbrengst weer die behaald kan worden door een bepaalde actie te nemen in een bepaalde toestand en daarna het optimale beleid te volgen.

Het kan wiskundig als volgt worden gedefinieerd:

\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:

\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 een maximum over alle beschikbare acties.

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 3

Vraag AI

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

Sectie 3. Hoofdstuk 3