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

bookBeleidverbetering

Note
Definitie

Beleidsverbetering is een proces waarbij het beleid wordt verbeterd op basis van de huidige schattingen van de waardefunctie.

Note
Opmerking

Net als bij beleidsevaluatie kan beleidsverbetering werken met zowel de toestandswaardefunctie als de actie-waardefunctie. Voor DP-methoden wordt echter de toestandswaardefunctie gebruikt.

Nu je de toestandswaardefunctie kunt schatten voor elk beleid, is een logische volgende stap om te onderzoeken of er beleid bestaat dat beter is dan het huidige. Een manier om dit te doen, is door te overwegen een andere actie aa te nemen in een toestand ss, en daarna het huidige beleid te volgen. Dit klinkt wellicht bekend, omdat dit vergelijkbaar is met de definitie van de actie-waardefunctie:

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Als deze nieuwe waarde groter is dan de oorspronkelijke toestandswaarde vπ(s)v_\pi(s), duidt dit erop dat het nemen van actie aa in toestand ss en vervolgens doorgaan met beleid π\pi tot betere uitkomsten leidt dan het strikt volgen van beleid π\pi. Aangezien toestanden onafhankelijk zijn, is het optimaal om altijd actie aa te kiezen wanneer toestand ss zich voordoet. Daarom kan een verbeterd beleid π′\pi' worden geconstrueerd, identiek aan π\pi behalve dat het actie aa kiest in toestand ss, wat superieur zou zijn aan het oorspronkelijke beleid π\pi.

Beleidsverbeteringsstelling

De hierboven beschreven redenering kan worden gegeneraliseerd als de beleidsverbeteringsstelling:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)\qquqquad∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquqquad &\forall s \in S \end{aligned}

Het bewijs van deze stelling is relatief eenvoudig en kan worden bereikt door herhaalde substitutie:

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Verbeteringsstrategie

Hoewel het bijwerken van acties voor bepaalde toestanden tot verbeteringen kan leiden, is het effectiever om acties voor alle toestanden gelijktijdig bij te werken. Specifiek, kies voor elke toestand ss de actie aa die de actie-waarde qπ(s,a)q_\pi(s, a) maximaliseert:

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

waarbij arg max⁡\argmax (afkorting voor argument van het maximum) een operator is die de waarde van de variabele retourneert die een gegeven functie maximaliseert.

Het resulterende greedy-beleid, aangeduid met π′\pi', voldoet door constructie aan de voorwaarden van het beleidverbeteringsstelling, waarmee wordt gegarandeerd dat π′\pi' minstens zo goed is als het oorspronkelijke beleid π\pi, en doorgaans beter.

Als π′\pi' even goed is als, maar niet beter dan π\pi, dan zijn zowel π′\pi' als π\pi optimale beleidsvormen, aangezien hun waardefuncties gelijk zijn en voldoen aan de Bellman-optimaliteitsvergelijking:

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

Hoe garandeert het aannemen van een greedy-beleid een verbetering ten opzichte van het vorige beleid?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 5

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

bookBeleidverbetering

Veeg om het menu te tonen

Note
Definitie

Beleidsverbetering is een proces waarbij het beleid wordt verbeterd op basis van de huidige schattingen van de waardefunctie.

Note
Opmerking

Net als bij beleidsevaluatie kan beleidsverbetering werken met zowel de toestandswaardefunctie als de actie-waardefunctie. Voor DP-methoden wordt echter de toestandswaardefunctie gebruikt.

Nu je de toestandswaardefunctie kunt schatten voor elk beleid, is een logische volgende stap om te onderzoeken of er beleid bestaat dat beter is dan het huidige. Een manier om dit te doen, is door te overwegen een andere actie aa te nemen in een toestand ss, en daarna het huidige beleid te volgen. Dit klinkt wellicht bekend, omdat dit vergelijkbaar is met de definitie van de actie-waardefunctie:

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Als deze nieuwe waarde groter is dan de oorspronkelijke toestandswaarde vπ(s)v_\pi(s), duidt dit erop dat het nemen van actie aa in toestand ss en vervolgens doorgaan met beleid π\pi tot betere uitkomsten leidt dan het strikt volgen van beleid π\pi. Aangezien toestanden onafhankelijk zijn, is het optimaal om altijd actie aa te kiezen wanneer toestand ss zich voordoet. Daarom kan een verbeterd beleid π′\pi' worden geconstrueerd, identiek aan π\pi behalve dat het actie aa kiest in toestand ss, wat superieur zou zijn aan het oorspronkelijke beleid π\pi.

Beleidsverbeteringsstelling

De hierboven beschreven redenering kan worden gegeneraliseerd als de beleidsverbeteringsstelling:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)\qquqquad∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquqquad &\forall s \in S \end{aligned}

Het bewijs van deze stelling is relatief eenvoudig en kan worden bereikt door herhaalde substitutie:

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Verbeteringsstrategie

Hoewel het bijwerken van acties voor bepaalde toestanden tot verbeteringen kan leiden, is het effectiever om acties voor alle toestanden gelijktijdig bij te werken. Specifiek, kies voor elke toestand ss de actie aa die de actie-waarde qπ(s,a)q_\pi(s, a) maximaliseert:

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

waarbij arg max⁡\argmax (afkorting voor argument van het maximum) een operator is die de waarde van de variabele retourneert die een gegeven functie maximaliseert.

Het resulterende greedy-beleid, aangeduid met π′\pi', voldoet door constructie aan de voorwaarden van het beleidverbeteringsstelling, waarmee wordt gegarandeerd dat π′\pi' minstens zo goed is als het oorspronkelijke beleid π\pi, en doorgaans beter.

Als π′\pi' even goed is als, maar niet beter dan π\pi, dan zijn zowel π′\pi' als π\pi optimale beleidsvormen, aangezien hun waardefuncties gelijk zijn en voldoen aan de Bellman-optimaliteitsvergelijking:

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

Hoe garandeert het aannemen van een greedy-beleid een verbetering ten opzichte van het vorige beleid?

Select the correct answer

Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 5
some-alt