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

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 tutkia, löytyykö politiikkoja, jotka ovat parempia kuin nykyinen. Yksi tapa tehdä tämä on harkita eri toiminnon aa valitsemista tilassa ss ja seurata nykyistä politiikkaa sen jälkeen. 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 seuraaminen alusta alkaen. 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ä tekee siitä alkuperäistä politiikkaa π\pi paremman.

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 suhteellisen 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. Erityisesti 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 muuttujan arvon, jolla annettu funktio saavuttaa maksimiarvonsa.

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 yleensä parempi.

Jos π′\pi' on yhtä hyvä kuin, 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 tutkia, löytyykö politiikkoja, jotka ovat parempia kuin nykyinen. Yksi tapa tehdä tämä on harkita eri toiminnon aa valitsemista tilassa ss ja seurata nykyistä politiikkaa sen jälkeen. 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 seuraaminen alusta alkaen. 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ä tekee siitä alkuperäistä politiikkaa π\pi paremman.

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 suhteellisen 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. Erityisesti 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 muuttujan arvon, jolla annettu funktio saavuttaa maksimiarvonsa.

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 yleensä parempi.

Jos π′\pi' on yhtä hyvä kuin, 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