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 Reinforcement Learning

bookPolicyforbedring

Note
Definisjon

Polisforbedring er en prosess der man forbedrer en politikk basert på nåværende estimater av verdifunksjonen.

Note
Merk

Som ved polisevaluering, kan polisforbedring benytte både tilstandsverdifunksjon og aksjonsverdifunksjon. For DP-metoder vil tilstandsverdifunksjon benyttes.

Nå som du kan estimere tilstandsverdifunksjonen for en hvilken som helst politikk, er et naturlig neste steg å undersøke om det finnes noen politiker 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 politikken. 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 oppdatering av handlinger for enkelte tilstander kan føre til forbedringer, er det mer effektivt å oppdatere handlinger for alle tilstander samtidig. Spesielt, for hver tilstand ss, velges 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 de 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

Suggested prompts:

Can you explain the policy improvement theorem in simpler terms?

How does the greedy policy guarantee improvement over the original policy?

What is the Bellman optimality equation and why is it important?

Awesome!

Completion rate improved to 2.7

bookPolicyforbedring

Sveip for å vise menyen

Note
Definisjon

Polisforbedring er en prosess der man forbedrer en politikk basert på nåværende estimater av verdifunksjonen.

Note
Merk

Som ved polisevaluering, kan polisforbedring benytte både tilstandsverdifunksjon og aksjonsverdifunksjon. For DP-metoder vil tilstandsverdifunksjon benyttes.

Nå som du kan estimere tilstandsverdifunksjonen for en hvilken som helst politikk, er et naturlig neste steg å undersøke om det finnes noen politiker 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 politikken. 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 oppdatering av handlinger for enkelte tilstander kan føre til forbedringer, er det mer effektivt å oppdatere handlinger for alle tilstander samtidig. Spesielt, for hver tilstand ss, velges 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 de 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