Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Policyforbedring | Dynamisk Programmering
Introduksjon til Forsterkende Læring

bookPolicyforbedring

Note
Definisjon

Policy improvement er en prosess for å forbedre policyen basert på nåværende estimater av verdifunksjonen.

Note
Merk

Akkurat som med policy-evaluering, kan policyforbedring benytte både tilstandsverdifunksjon og aksjonsverdifunksjon. Men for DP-metoder vil tilstandsverdifunksjonen bli brukt.

Nå som du kan estimere tilstandsverdifunksjonen for en hvilken som helst policy, er et naturlig neste steg å undersøke om det finnes noen policyer som er bedre enn den nåværende. En måte å gjøre dette på, er å vurdere å ta en annen handling aa i en tilstand ss, og deretter følge den nåværende policyen. Hvis dette virker kjent, er det fordi dette ligner på hvordan vi definerer aksjonsverdifunksjonen:

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)

Hvis denne nye verdien er større enn den opprinnelige tilstandsverdien vπ(s)v_\pi(s), indikerer det at å velge handling aa i tilstand ss og deretter fortsette med politikk π\pi gir bedre resultater enn å følge politikk π\pi strengt. Siden tilstander er uavhengige, er det optimalt å alltid velge handling aa hver gang tilstand ss oppstår. Derfor kan vi konstruere en forbedret politikk π′\pi', identisk med π\pi bortsett fra at den velger handling aa i tilstand ss, noe som vil være bedre enn den opprinnelige politikken π\pi.

Teorem for politikkforbedring

Resonnementet beskrevet ovenfor kan generaliseres som teorem for politikkforbedring:

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 for denne teoremet er relativt enkelt, og kan oppnås ved en gjentatt substitusjon:

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}

Forbedringsstrategi

Selv om det å oppdatere handlinger for enkelte tilstander kan føre til forbedringer, er det mer effektivt å oppdatere handlinger for alle tilstander samtidig. Spesielt, for hver tilstand ss, velg den handlingen aa som maksimerer handlingsverdien 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}

hvor arg max⁡\argmax (forkortelse for argumentet til maksimumet) er en operator som returnerer verdien av variabelen som maksimerer en gitt funksjon.

Den resulterende grådige policyen, betegnet som π′\pi', oppfyller betingelsene i policy improvement-teoremet ved konstruksjon, noe som garanterer at π′\pi' er minst like god som den opprinnelige policyen π\pi, og vanligvis bedre.

Hvis π′\pi' er like god som, men ikke bedre enn π\pi, er både π′\pi' og π\pi optimale policyer, ettersom deres verdifunksjoner er like og oppfyller Bellmans optimalitetslikning:

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

Hvordan garanterer det å ta i bruk en grådig policy en forbedring i forhold til den forrige policyen?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 5

Spør AI

expand

Spør AI

ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Awesome!

Completion rate improved to 2.7

bookPolicyforbedring

Sveip for å vise menyen

Note
Definisjon

Policy improvement er en prosess for å forbedre policyen basert på nåværende estimater av verdifunksjonen.

Note
Merk

Akkurat som med policy-evaluering, kan policyforbedring benytte både tilstandsverdifunksjon og aksjonsverdifunksjon. Men for DP-metoder vil tilstandsverdifunksjonen bli brukt.

Nå som du kan estimere tilstandsverdifunksjonen for en hvilken som helst policy, er et naturlig neste steg å undersøke om det finnes noen policyer som er bedre enn den nåværende. En måte å gjøre dette på, er å vurdere å ta en annen handling aa i en tilstand ss, og deretter følge den nåværende policyen. Hvis dette virker kjent, er det fordi dette ligner på hvordan vi definerer aksjonsverdifunksjonen:

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)

Hvis denne nye verdien er større enn den opprinnelige tilstandsverdien vπ(s)v_\pi(s), indikerer det at å velge handling aa i tilstand ss og deretter fortsette med politikk π\pi gir bedre resultater enn å følge politikk π\pi strengt. Siden tilstander er uavhengige, er det optimalt å alltid velge handling aa hver gang tilstand ss oppstår. Derfor kan vi konstruere en forbedret politikk π′\pi', identisk med π\pi bortsett fra at den velger handling aa i tilstand ss, noe som vil være bedre enn den opprinnelige politikken π\pi.

Teorem for politikkforbedring

Resonnementet beskrevet ovenfor kan generaliseres som teorem for politikkforbedring:

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 for denne teoremet er relativt enkelt, og kan oppnås ved en gjentatt substitusjon:

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}

Forbedringsstrategi

Selv om det å oppdatere handlinger for enkelte tilstander kan føre til forbedringer, er det mer effektivt å oppdatere handlinger for alle tilstander samtidig. Spesielt, for hver tilstand ss, velg den handlingen aa som maksimerer handlingsverdien 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}

hvor arg max⁡\argmax (forkortelse for argumentet til maksimumet) er en operator som returnerer verdien av variabelen som maksimerer en gitt funksjon.

Den resulterende grådige policyen, betegnet som π′\pi', oppfyller betingelsene i policy improvement-teoremet ved konstruksjon, noe som garanterer at π′\pi' er minst like god som den opprinnelige policyen π\pi, og vanligvis bedre.

Hvis π′\pi' er like god som, men ikke bedre enn π\pi, er både π′\pi' og π\pi optimale policyer, ettersom deres verdifunksjoner er like og oppfyller Bellmans optimalitetslikning:

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

Hvordan garanterer det å ta i bruk en grådig policy en forbedring i forhold til den forrige policyen?

Select the correct answer

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 5
some-alt