Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Politikforbedring | Dynamisk Programmering
Introduktion til Reinforcement Learning

bookPolitikforbedring

Note
Definition

Politikforbedring er en proces, hvor politikken forbedres baseret på de nuværende estimater af værdifunktionen.

Note
Bemærk

Ligesom ved politikkevaluering kan politikforbedring anvendes med både tilstandsværdifunktion og aktionsværdifunktion. Men for DP-metoder vil tilstandsværdifunktionen blive brugt.

Nu hvor du kan estimere tilstandsværdifunktionen for en vilkårlig politik, er det naturlige næste skridt at undersøge, om der findes politikker, der er bedre end den nuværende. En måde at gøre dette på er at overveje at tage en anden handling aa i en tilstand ss og derefter følge den nuværende politik. Hvis dette lyder bekendt, er det fordi det ligner definitionen af aktionsværdifunktionen:

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 værdi er større end den oprindelige tilstandsværdi vπ(s)v_\pi(s), indikerer det, at det at vælge handling aa i tilstand ss og derefter fortsætte med politik π\pi fører til bedre resultater end udelukkende at følge politik π\pi. Da tilstande er uafhængige, er det optimalt altid at vælge handling aa, når tilstand ss opstår. Derfor kan vi konstruere en forbedret politik π′\pi', som er identisk med π\pi, bortset fra at den vælger handling aa i tilstand ss, hvilket vil være bedre end den oprindelige politik π\pi.

Politisk forbedringsteorem

Den ovenfor beskrevne ræsonnement kan generaliseres som politisk forbedringsteorem:

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 sætning er relativt simpelt og kan opnås ved en gentagen 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}

Forbedringsstrategi

Selvom opdatering af handlinger for visse tilstande kan føre til forbedringer, er det mere effektivt at opdatere handlinger for alle tilstande samtidigt. Specifikt vælges for hver tilstand ss den handling aa, der maksimerer handlingsværdien 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 for maksimum) er en operator, der returnerer værdien af den variabel, der maksimerer en given funktion.

Den resulterende grådige politik, betegnet som π′\pi', opfylder betingelserne i policy improvement-sætningen ved konstruktion, hvilket garanterer, at π′\pi' er mindst lige så god som den oprindelige politik π\pi, og typisk bedre.

Hvis π′\pi' er lige så god som, men ikke bedre end π\pi, så er både π′\pi' og π\pi optimale politikker, da deres værdifunktioner er ens og opfylder Bellmans optimalitetsligning:

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 vedtagelsen af en grådig politik en forbedring i forhold til den tidligere politik?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 5

Spørg AI

expand

Spørg AI

ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Awesome!

Completion rate improved to 2.7

bookPolitikforbedring

Stryg for at vise menuen

Note
Definition

Politikforbedring er en proces, hvor politikken forbedres baseret på de nuværende estimater af værdifunktionen.

Note
Bemærk

Ligesom ved politikkevaluering kan politikforbedring anvendes med både tilstandsværdifunktion og aktionsværdifunktion. Men for DP-metoder vil tilstandsværdifunktionen blive brugt.

Nu hvor du kan estimere tilstandsværdifunktionen for en vilkårlig politik, er det naturlige næste skridt at undersøge, om der findes politikker, der er bedre end den nuværende. En måde at gøre dette på er at overveje at tage en anden handling aa i en tilstand ss og derefter følge den nuværende politik. Hvis dette lyder bekendt, er det fordi det ligner definitionen af aktionsværdifunktionen:

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 værdi er større end den oprindelige tilstandsværdi vπ(s)v_\pi(s), indikerer det, at det at vælge handling aa i tilstand ss og derefter fortsætte med politik π\pi fører til bedre resultater end udelukkende at følge politik π\pi. Da tilstande er uafhængige, er det optimalt altid at vælge handling aa, når tilstand ss opstår. Derfor kan vi konstruere en forbedret politik π′\pi', som er identisk med π\pi, bortset fra at den vælger handling aa i tilstand ss, hvilket vil være bedre end den oprindelige politik π\pi.

Politisk forbedringsteorem

Den ovenfor beskrevne ræsonnement kan generaliseres som politisk forbedringsteorem:

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 sætning er relativt simpelt og kan opnås ved en gentagen 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}

Forbedringsstrategi

Selvom opdatering af handlinger for visse tilstande kan føre til forbedringer, er det mere effektivt at opdatere handlinger for alle tilstande samtidigt. Specifikt vælges for hver tilstand ss den handling aa, der maksimerer handlingsværdien 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 for maksimum) er en operator, der returnerer værdien af den variabel, der maksimerer en given funktion.

Den resulterende grådige politik, betegnet som π′\pi', opfylder betingelserne i policy improvement-sætningen ved konstruktion, hvilket garanterer, at π′\pi' er mindst lige så god som den oprindelige politik π\pi, og typisk bedre.

Hvis π′\pi' er lige så god som, men ikke bedre end π\pi, så er både π′\pi' og π\pi optimale politikker, da deres værdifunktioner er ens og opfylder Bellmans optimalitetsligning:

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 vedtagelsen af en grådig politik en forbedring i forhold til den tidligere politik?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 5
some-alt