Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Oppiskele Politiikan Parantaminen | Dynaaminen Ohjelmointi
Johdatus Vahvistusoppimiseen

bookPolitiikan Parantaminen

Note
Määritelmä

Politiikan parantaminen on prosessi, jossa politiikkaa kehitetään nykyisten arvofunktioestimaattien perusteella.

Note
Huomio

Kuten politiikan arvioinnissa, politiikan parantaminen voi hyödyntää sekä tilan arvofunktiota että toiminnon arvofunktiota. Dynaamisen ohjelmoinnin menetelmissä käytetään kuitenkin tilan arvofunktiota.

Nyt kun osaat arvioida tilan arvofunktion mille tahansa politiikalle, luonnollinen seuraava askel on selvittää, löytyykö nykyistä politiikkaa parempia politiikkoja. Yksi tapa tehdä tämä on harkita eri toiminnon aa valitsemista tilassa ss ja noudattaa sen jälkeen nykyistä politiikkaa. Jos tämä kuulostaa tutulta, se johtuu siitä, että tämä muistuttaa toiminnon arvofunktion määritelmää:

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)

Jos tämä uusi arvo on suurempi kuin alkuperäinen tilan arvo vπ(s)v_\pi(s), se osoittaa, että toiminnon aa valitseminen tilassa ss ja sen jälkeen politiikan π\pi noudattaminen johtaa parempiin tuloksiin kuin politiikan π\pi tiukka seuraaminen. Koska tilat ovat riippumattomia, on optimaalista valita aina toiminto aa, kun tila ss kohdataan. Näin ollen voimme muodostaa parannetun politiikan π′\pi', joka on muuten identtinen politiikan π\pi kanssa, mutta valitsee toiminnon aa tilassa ss, mikä olisi alkuperäistä politiikkaa π\pi parempi.

Politiikan parantamisen lause

Yllä kuvattua päättelyä voidaan yleistää politiikan parantamisen lauseeksi:

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}

Tämän lauseen todistus on melko yksinkertainen ja voidaan saavuttaa toistuvalla sijoituksella:

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}

Parannusstrategia

Vaikka tiettyjen tilojen toimintojen päivittäminen voi johtaa parannuksiin, on tehokkaampaa päivittää toiminnot kaikille tiloille samanaikaisesti. Tarkemmin sanottuna, jokaiselle tilalle ss valitaan toiminto aa, joka maksimoi toimintojen arvon 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}

missä arg max⁡\argmax (lyhenne sanoista argument of the maximum) on operaattori, joka palauttaa sen muuttujan arvon, jolla annettu funktio saa suurimman arvonsa.

Tuloksena syntyvä ahne politiikka (greedy policy), jota merkitään π′\pi', täyttää politiikan parantamisen lauseen ehdot rakenteensa ansiosta, mikä takaa, että π′\pi' on vähintään yhtä hyvä kuin alkuperäinen politiikka π\pi, ja tyypillisesti parempi.

Jos π′\pi' on yhtä hyvä, mutta ei parempi kuin π\pi, molemmat π′\pi' ja π\pi ovat optimaalisia politiikkoja, sillä niiden arvofunktiot ovat yhtäsuuret ja ne täyttävät Bellmanin optimaalisen yhtälön:

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

Miten ahneen politiikan (greedy policy) omaksuminen takaa parannuksen edelliseen politiikkaan verrattuna?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 5

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Awesome!

Completion rate improved to 2.7

bookPolitiikan Parantaminen

Pyyhkäise näyttääksesi valikon

Note
Määritelmä

Politiikan parantaminen on prosessi, jossa politiikkaa kehitetään nykyisten arvofunktioestimaattien perusteella.

Note
Huomio

Kuten politiikan arvioinnissa, politiikan parantaminen voi hyödyntää sekä tilan arvofunktiota että toiminnon arvofunktiota. Dynaamisen ohjelmoinnin menetelmissä käytetään kuitenkin tilan arvofunktiota.

Nyt kun osaat arvioida tilan arvofunktion mille tahansa politiikalle, luonnollinen seuraava askel on selvittää, löytyykö nykyistä politiikkaa parempia politiikkoja. Yksi tapa tehdä tämä on harkita eri toiminnon aa valitsemista tilassa ss ja noudattaa sen jälkeen nykyistä politiikkaa. Jos tämä kuulostaa tutulta, se johtuu siitä, että tämä muistuttaa toiminnon arvofunktion määritelmää:

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)

Jos tämä uusi arvo on suurempi kuin alkuperäinen tilan arvo vπ(s)v_\pi(s), se osoittaa, että toiminnon aa valitseminen tilassa ss ja sen jälkeen politiikan π\pi noudattaminen johtaa parempiin tuloksiin kuin politiikan π\pi tiukka seuraaminen. Koska tilat ovat riippumattomia, on optimaalista valita aina toiminto aa, kun tila ss kohdataan. Näin ollen voimme muodostaa parannetun politiikan π′\pi', joka on muuten identtinen politiikan π\pi kanssa, mutta valitsee toiminnon aa tilassa ss, mikä olisi alkuperäistä politiikkaa π\pi parempi.

Politiikan parantamisen lause

Yllä kuvattua päättelyä voidaan yleistää politiikan parantamisen lauseeksi:

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}

Tämän lauseen todistus on melko yksinkertainen ja voidaan saavuttaa toistuvalla sijoituksella:

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}

Parannusstrategia

Vaikka tiettyjen tilojen toimintojen päivittäminen voi johtaa parannuksiin, on tehokkaampaa päivittää toiminnot kaikille tiloille samanaikaisesti. Tarkemmin sanottuna, jokaiselle tilalle ss valitaan toiminto aa, joka maksimoi toimintojen arvon 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}

missä arg max⁡\argmax (lyhenne sanoista argument of the maximum) on operaattori, joka palauttaa sen muuttujan arvon, jolla annettu funktio saa suurimman arvonsa.

Tuloksena syntyvä ahne politiikka (greedy policy), jota merkitään π′\pi', täyttää politiikan parantamisen lauseen ehdot rakenteensa ansiosta, mikä takaa, että π′\pi' on vähintään yhtä hyvä kuin alkuperäinen politiikka π\pi, ja tyypillisesti parempi.

Jos π′\pi' on yhtä hyvä, mutta ei parempi kuin π\pi, molemmat π′\pi' ja π\pi ovat optimaalisia politiikkoja, sillä niiden arvofunktiot ovat yhtäsuuret ja ne täyttävät Bellmanin optimaalisen yhtälön:

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

Miten ahneen politiikan (greedy policy) omaksuminen takaa parannuksen edelliseen politiikkaan verrattuna?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 5
some-alt