Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lära Policyförbättring | Dynamisk Programmering
Introduktion till Förstärkningsinlärning

bookPolicyförbättring

Note
Definition

Policysförbättring är en process för att förbättra policyn baserat på aktuella värdefunktionsuppskattningar.

Note
Notering

Precis som vid policysutvärdering kan policysförbättring användas med både tillståndsvärdefunktion och aktionsvärdefunktion. Men för DP-metoder kommer tillståndsvärdefunktionen att användas.

Nu när du kan uppskatta tillståndsvärdefunktionen för en godtycklig policy, är ett naturligt nästa steg att undersöka om det finns några policys som är bättre än den nuvarande. Ett sätt att göra detta är att överväga att ta en annan handling aa i ett tillstånd ss, och sedan följa den nuvarande policyn. Om detta låter bekant, är det för att det liknar hur vi definierar aktionsvärdefunktionen:

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)

Om detta nya värde är större än det ursprungliga tillståndsvärdet vπ(s)v_\pi(s), indikerar det att att välja åtgärd aa i tillstånd ss och därefter fortsätta med policyn π\pi leder till bättre utfall än att strikt följa policyn π\pi. Eftersom tillstånd är oberoende är det optimalt att alltid välja åtgärd aa när tillstånd ss påträffas. Därför kan vi konstruera en förbättrad policy π′\pi', identisk med π\pi förutom att den väljer åtgärd aa i tillstånd ss, vilket skulle vara överlägset den ursprungliga policyn π\pi.

Sats om policyförbättring

Resonemanget som beskrivs ovan kan generaliseras som satsen om policyförbättring:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀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) \qquad &\forall s \in S \end{aligned}

Beviset för denna sats är relativt enkelt och kan uppnås genom en upprepad substitution:

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}

Förbättringsstrategi

Att uppdatera åtgärder för vissa tillstånd kan leda till förbättringar, men det är mer effektivt att uppdatera åtgärder för alla tillstånd samtidigt. Specifikt, för varje tillstånd ss, välj den åtgärd aa som maximerar åtgärdsvärdet qπ(s,a)q_\pi(s, a):

π′(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}

där arg max⁡\argmax (förkortning för argumentet för maximum) är en operator som returnerar värdet på den variabel som maximerar en given funktion.

Den resulterande giriga policyn, betecknad med π′\pi', uppfyller villkoren för policyförbättringssatsen genom konstruktion, vilket garanterar att π′\pi' är minst lika bra som den ursprungliga policyn π\pi, och vanligtvis bättre.

Om π′\pi' är lika bra som, men inte bättre än π\pi, så är både π′\pi' och π\pi optimala policies, eftersom deras värdefunktioner är lika och uppfyller Bellmans optimalitetsekvation:

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

Hur garanterar antagandet av en girig policy en förbättring jämfört med den tidigare policyn?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 5

Fråga AI

expand

Fråga AI

ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Awesome!

Completion rate improved to 2.7

bookPolicyförbättring

Svep för att visa menyn

Note
Definition

Policysförbättring är en process för att förbättra policyn baserat på aktuella värdefunktionsuppskattningar.

Note
Notering

Precis som vid policysutvärdering kan policysförbättring användas med både tillståndsvärdefunktion och aktionsvärdefunktion. Men för DP-metoder kommer tillståndsvärdefunktionen att användas.

Nu när du kan uppskatta tillståndsvärdefunktionen för en godtycklig policy, är ett naturligt nästa steg att undersöka om det finns några policys som är bättre än den nuvarande. Ett sätt att göra detta är att överväga att ta en annan handling aa i ett tillstånd ss, och sedan följa den nuvarande policyn. Om detta låter bekant, är det för att det liknar hur vi definierar aktionsvärdefunktionen:

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)

Om detta nya värde är större än det ursprungliga tillståndsvärdet vπ(s)v_\pi(s), indikerar det att att välja åtgärd aa i tillstånd ss och därefter fortsätta med policyn π\pi leder till bättre utfall än att strikt följa policyn π\pi. Eftersom tillstånd är oberoende är det optimalt att alltid välja åtgärd aa när tillstånd ss påträffas. Därför kan vi konstruera en förbättrad policy π′\pi', identisk med π\pi förutom att den väljer åtgärd aa i tillstånd ss, vilket skulle vara överlägset den ursprungliga policyn π\pi.

Sats om policyförbättring

Resonemanget som beskrivs ovan kan generaliseras som satsen om policyförbättring:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀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) \qquad &\forall s \in S \end{aligned}

Beviset för denna sats är relativt enkelt och kan uppnås genom en upprepad substitution:

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}

Förbättringsstrategi

Att uppdatera åtgärder för vissa tillstånd kan leda till förbättringar, men det är mer effektivt att uppdatera åtgärder för alla tillstånd samtidigt. Specifikt, för varje tillstånd ss, välj den åtgärd aa som maximerar åtgärdsvärdet qπ(s,a)q_\pi(s, a):

π′(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}

där arg max⁡\argmax (förkortning för argumentet för maximum) är en operator som returnerar värdet på den variabel som maximerar en given funktion.

Den resulterande giriga policyn, betecknad med π′\pi', uppfyller villkoren för policyförbättringssatsen genom konstruktion, vilket garanterar att π′\pi' är minst lika bra som den ursprungliga policyn π\pi, och vanligtvis bättre.

Om π′\pi' är lika bra som, men inte bättre än π\pi, så är både π′\pi' och π\pi optimala policies, eftersom deras värdefunktioner är lika och uppfyller Bellmans optimalitetsekvation:

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

Hur garanterar antagandet av en girig policy en förbättring jämfört med den tidigare policyn?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 5
some-alt