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

Kurssisisältö

Johdatus Vahvistusoppimiseen

Johdatus Vahvistusoppimiseen

1. RL:n Ydinteoria
2. Moniaseinen Bandiittiongelma
3. Dynaaminen Ohjelmointi
4. Monte Carlo -Menetelmät
5. Aikaisen Eron Oppiminen

book
Politiikan Arviointi

Note
Määritelmä

Politiikan arviointi on prosessi, jossa määritetään annetun politiikan arvofunktio.

Note
Huomio

Politiikan arviointia voidaan käyttää sekä tilan arvofunktion että toiminnon arvofunktion arvioimiseen. Dynaamisen ohjelmoinnin menetelmissä käytetään kuitenkin tilan arvofunktiota.

Kuten tiedät, annetun politiikan tilan arvofunktio voidaan määrittää ratkaisemalla Bellmanin yhtälö:

vπ(s)=aπ(as)s,rp(s,rs,a)(r+γvπ(s))v_\pi(s) = \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Jos sinulla on täydellinen malli ympäristöstä (eli tunnetut siirtymätodennäköisyydet ja odotetut palkkiot kaikille tila-toiminto -pareille), ainoat tuntemattomat muuttujat yhtälössä ovat tilojen arvot. Näin ollen yllä oleva yhtälö voidaan muotoilla järjestelmäksi, jossa on S|S| lineaarista yhtälöä ja S|S| tuntematonta.

Esimerkiksi, jos MDP:ssä on 2 tilaa (s1s_1, s2s_2) ja 2 toimintoa (siirry s1s_1:een, siirry s2s_2:een), tilan arvofunktio voidaan määritellä seuraavasti:

{V(s1)=0.5(5+0.9V(s1))+0.5(10+0.9V(s2))V(s2)=0.7(2+0.9V(s1))+0.3(0+0.9V(s2))\begin{cases} V(s_1) = 0.5 \cdot (5 + 0.9 \cdot V(s_1)) + 0.5 \cdot (10 + 0.9 \cdot V(s_2)) \\ V(s_2) = 0.7 \cdot (2 + 0.9 \cdot V(s_1)) + 0.3 \cdot (0 + 0.9 \cdot V(s_2)) \end{cases}

Tämä voidaan ratkaista tavanomaisilla lineaarialgebran menetelmillä.

Yksikäsitteinen ratkaisu tällaiselle lineaariselle yhtälöryhmälle on taattu, jos vähintään yksi seuraavista ehdoista täyttyy:

  • Alennustekijä täyttää ehdon γ<1γ < 1;
  • Politiikka π\pi, jota noudatetaan mistä tahansa tilasta ss, varmistaa, että episodi päättyy lopulta.

Iteratiivinen politiikan arviointi

Ratkaisu voidaan laskea suoraan, mutta iteratiivista lähestymistapaa käytetään yleisemmin sen helpon toteutettavuuden vuoksi. Tämä menetelmä alkaa asettamalla satunnaiset alkuarvot kaikille tiloille, paitsi päättäväisille tiloille, jotka asetetaan arvoon 0. Arvoja päivitetään tämän jälkeen iteratiivisesti käyttäen Bellmanin yhtälöä päivityssääntönä:

vk+1(s)aπ(as)s,rp(s,rs,a)(r+γvk(s))v_{k+1}(s) \gets \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_k(s')\Bigr)

Arvioitu tilan arvofunktio vkv_k lähestyy lopulta todellista tilan arvofunktiota vπv_\pi, kun kk \to \infty, jos vπv_\pi on olemassa.

Arvon varmuuskopiointistrategiat

Arvioita päivitettäessä uudet arviot lasketaan aiempien arvojen perusteella. Prosessia, jossa aiemmat arviot säilytetään, kutsutaan varmuuskopioinniksi. Varmuuskopioinnissa on kaksi yleistä strategiaa:

  • Täysi varmuuskopiointi: tässä menetelmässä uudet arviot tallennetaan erilliseen taulukkoon, joka on eri kuin aiemmat (varmuuskopioidut) arvot sisältävä taulukko. Tämän vuoksi tarvitaan kaksi taulukkoa — toinen aiempien arvioiden ylläpitoon ja toinen uusien arvojen tallentamiseen;
  • Paikallinen varmuuskopiointi: tässä lähestymistavassa kaikki arvot säilytetään yhdessä taulukossa. Jokainen uusi arvio korvaa välittömästi aiemman arvon. Tämä menetelmä vähentää muistinkäyttöä, koska tarvitaan vain yksi taulukko.

Yleensä paikallinen varmuuskopiointi on suositeltavampi, koska se vaatii vähemmän muistia ja lähestyy ratkaisua nopeammin, sillä uusimpia arvioita hyödynnetään välittömästi.

Milloin lopettaa päivitys?

Iteratiivisessa politiikan arvioinnissa ei ole tarkkaa hetkeä, jolloin algoritmin tulisi pysähtyä. Vaikka konvergenssi on taattu ääriarvossa, laskennan jatkaminen tietyn pisteen jälkeen on tarpeetonta käytännössä. Yksinkertainen ja tehokas pysäytyskriteeri on seurata absoluuttista erotusta peräkkäisten arviopäivitysten välillä, vk+1(s)vk(s)|v_{k+1}(s) - v_k(s)|, ja verrata sitä pieneen kynnysarvoon θ\theta. Jos täyden päivityskierroksen (jossa kaikkien tilojen arvot päivitetään) jälkeen mikään muutos ei ylitä θ\theta:ta, prosessi voidaan turvallisesti lopettaa.

Pseudokoodi

question mark

Mikä seuraavista väittämistä pitää paikkansa iteroivasta politiikan arviointimenetelmästä?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 4

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

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

course content

Kurssisisältö

Johdatus Vahvistusoppimiseen

Johdatus Vahvistusoppimiseen

1. RL:n Ydinteoria
2. Moniaseinen Bandiittiongelma
3. Dynaaminen Ohjelmointi
4. Monte Carlo -Menetelmät
5. Aikaisen Eron Oppiminen

book
Politiikan Arviointi

Note
Määritelmä

Politiikan arviointi on prosessi, jossa määritetään annetun politiikan arvofunktio.

Note
Huomio

Politiikan arviointia voidaan käyttää sekä tilan arvofunktion että toiminnon arvofunktion arvioimiseen. Dynaamisen ohjelmoinnin menetelmissä käytetään kuitenkin tilan arvofunktiota.

Kuten tiedät, annetun politiikan tilan arvofunktio voidaan määrittää ratkaisemalla Bellmanin yhtälö:

vπ(s)=aπ(as)s,rp(s,rs,a)(r+γvπ(s))v_\pi(s) = \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Jos sinulla on täydellinen malli ympäristöstä (eli tunnetut siirtymätodennäköisyydet ja odotetut palkkiot kaikille tila-toiminto -pareille), ainoat tuntemattomat muuttujat yhtälössä ovat tilojen arvot. Näin ollen yllä oleva yhtälö voidaan muotoilla järjestelmäksi, jossa on S|S| lineaarista yhtälöä ja S|S| tuntematonta.

Esimerkiksi, jos MDP:ssä on 2 tilaa (s1s_1, s2s_2) ja 2 toimintoa (siirry s1s_1:een, siirry s2s_2:een), tilan arvofunktio voidaan määritellä seuraavasti:

{V(s1)=0.5(5+0.9V(s1))+0.5(10+0.9V(s2))V(s2)=0.7(2+0.9V(s1))+0.3(0+0.9V(s2))\begin{cases} V(s_1) = 0.5 \cdot (5 + 0.9 \cdot V(s_1)) + 0.5 \cdot (10 + 0.9 \cdot V(s_2)) \\ V(s_2) = 0.7 \cdot (2 + 0.9 \cdot V(s_1)) + 0.3 \cdot (0 + 0.9 \cdot V(s_2)) \end{cases}

Tämä voidaan ratkaista tavanomaisilla lineaarialgebran menetelmillä.

Yksikäsitteinen ratkaisu tällaiselle lineaariselle yhtälöryhmälle on taattu, jos vähintään yksi seuraavista ehdoista täyttyy:

  • Alennustekijä täyttää ehdon γ<1γ < 1;
  • Politiikka π\pi, jota noudatetaan mistä tahansa tilasta ss, varmistaa, että episodi päättyy lopulta.

Iteratiivinen politiikan arviointi

Ratkaisu voidaan laskea suoraan, mutta iteratiivista lähestymistapaa käytetään yleisemmin sen helpon toteutettavuuden vuoksi. Tämä menetelmä alkaa asettamalla satunnaiset alkuarvot kaikille tiloille, paitsi päättäväisille tiloille, jotka asetetaan arvoon 0. Arvoja päivitetään tämän jälkeen iteratiivisesti käyttäen Bellmanin yhtälöä päivityssääntönä:

vk+1(s)aπ(as)s,rp(s,rs,a)(r+γvk(s))v_{k+1}(s) \gets \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_k(s')\Bigr)

Arvioitu tilan arvofunktio vkv_k lähestyy lopulta todellista tilan arvofunktiota vπv_\pi, kun kk \to \infty, jos vπv_\pi on olemassa.

Arvon varmuuskopiointistrategiat

Arvioita päivitettäessä uudet arviot lasketaan aiempien arvojen perusteella. Prosessia, jossa aiemmat arviot säilytetään, kutsutaan varmuuskopioinniksi. Varmuuskopioinnissa on kaksi yleistä strategiaa:

  • Täysi varmuuskopiointi: tässä menetelmässä uudet arviot tallennetaan erilliseen taulukkoon, joka on eri kuin aiemmat (varmuuskopioidut) arvot sisältävä taulukko. Tämän vuoksi tarvitaan kaksi taulukkoa — toinen aiempien arvioiden ylläpitoon ja toinen uusien arvojen tallentamiseen;
  • Paikallinen varmuuskopiointi: tässä lähestymistavassa kaikki arvot säilytetään yhdessä taulukossa. Jokainen uusi arvio korvaa välittömästi aiemman arvon. Tämä menetelmä vähentää muistinkäyttöä, koska tarvitaan vain yksi taulukko.

Yleensä paikallinen varmuuskopiointi on suositeltavampi, koska se vaatii vähemmän muistia ja lähestyy ratkaisua nopeammin, sillä uusimpia arvioita hyödynnetään välittömästi.

Milloin lopettaa päivitys?

Iteratiivisessa politiikan arvioinnissa ei ole tarkkaa hetkeä, jolloin algoritmin tulisi pysähtyä. Vaikka konvergenssi on taattu ääriarvossa, laskennan jatkaminen tietyn pisteen jälkeen on tarpeetonta käytännössä. Yksinkertainen ja tehokas pysäytyskriteeri on seurata absoluuttista erotusta peräkkäisten arviopäivitysten välillä, vk+1(s)vk(s)|v_{k+1}(s) - v_k(s)|, ja verrata sitä pieneen kynnysarvoon θ\theta. Jos täyden päivityskierroksen (jossa kaikkien tilojen arvot päivitetään) jälkeen mikään muutos ei ylitä θ\theta:ta, prosessi voidaan turvallisesti lopettaa.

Pseudokoodi

question mark

Mikä seuraavista väittämistä pitää paikkansa iteroivasta politiikan arviointimenetelmästä?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 3. Luku 4
some-alt