Politiikan Arviointi
Politiikan arviointi on prosessi, jossa määritetään annetun politiikan arvofunktio.
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∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))Jos ympäristön täydellinen malli on käytettävissä (eli tunnetut siirtymätodennäköisyydet ja odotetut palkkiot kaikille tila-toimintapareille), ainoat tuntemattomat muuttujat yhtälössä ovat tilojen arvot. Tämän vuoksi yllä oleva yhtälö voidaan muotoilla järjestelmäksi, jossa on ∣S∣ lineaarista yhtälöä ja ∣S∣ tuntematonta.
Esimerkiksi, jos MDP:ssä on 2 tilaa (s1, s2) ja 2 toimintoa (siirry s1:een, siirry s2:een), tilan arvofunktio voidaan määritellä seuraavasti:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))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;
- Politiikka π, jota noudatetaan mistä tahansa tilasta s, 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 kaikille tiloille satunnaiset alkuarvot, paitsi päättävät tilat, 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∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Arvioitu tilan arvofunktio vk lähestyy lopulta todellista tilan arvofunktiota vπ, kun k→∞, jos vπ on olemassa.
Arvon varmistusstrategiat
Arvioita päivitettäessä uudet arviot lasketaan aiempien arvojen perusteella. Prosessia, jossa aiemmat arviot säilytetään, kutsutaan varmistukseksi. Varmistuksia voidaan tehdä kahdella yleisellä strategialla:
- Täysi varmistus: tässä menetelmässä uudet arviot tallennetaan erilliseen taulukkoon, joka on eri kuin aiemmat (varmistetut) arvot sisältävä taulukko. Tämän vuoksi tarvitaan kaksi taulukkoa — toinen aiempien arvioiden ylläpitämiseen ja toinen uusien arvojen tallentamiseen;
- Paikallinen varmistus: 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ä paikallista varmistusta suositaan, 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 lopettaa. Vaikka konvergenssi on taattu ääriarvossa, käytännössä laskentaa ei tarvitse jatkaa tietyn pisteen jälkeen. Yksinkertainen ja tehokas pysäytyskriteeri on seurata absoluuttista erotusta peräkkäisten arvoestimaattien välillä, ∣vk+1(s)−vk(s)∣, ja verrata sitä pieneen kynnysarvoon θ. Jos täyden päivityskierroksen (kaikkien tilojen arvojen päivitys) jälkeen mikään muutos ei ylitä θ:a, prosessi voidaan turvallisesti lopettaa.
Pseudokoodi
Kiitos palautteestasi!
Kysy tekoälyä
Kysy tekoälyä
Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme
Awesome!
Completion rate improved to 2.7
Politiikan Arviointi
Pyyhkäise näyttääksesi valikon
Politiikan arviointi on prosessi, jossa määritetään annetun politiikan arvofunktio.
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∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))Jos ympäristön täydellinen malli on käytettävissä (eli tunnetut siirtymätodennäköisyydet ja odotetut palkkiot kaikille tila-toimintapareille), ainoat tuntemattomat muuttujat yhtälössä ovat tilojen arvot. Tämän vuoksi yllä oleva yhtälö voidaan muotoilla järjestelmäksi, jossa on ∣S∣ lineaarista yhtälöä ja ∣S∣ tuntematonta.
Esimerkiksi, jos MDP:ssä on 2 tilaa (s1, s2) ja 2 toimintoa (siirry s1:een, siirry s2:een), tilan arvofunktio voidaan määritellä seuraavasti:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))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;
- Politiikka π, jota noudatetaan mistä tahansa tilasta s, 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 kaikille tiloille satunnaiset alkuarvot, paitsi päättävät tilat, 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∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Arvioitu tilan arvofunktio vk lähestyy lopulta todellista tilan arvofunktiota vπ, kun k→∞, jos vπ on olemassa.
Arvon varmistusstrategiat
Arvioita päivitettäessä uudet arviot lasketaan aiempien arvojen perusteella. Prosessia, jossa aiemmat arviot säilytetään, kutsutaan varmistukseksi. Varmistuksia voidaan tehdä kahdella yleisellä strategialla:
- Täysi varmistus: tässä menetelmässä uudet arviot tallennetaan erilliseen taulukkoon, joka on eri kuin aiemmat (varmistetut) arvot sisältävä taulukko. Tämän vuoksi tarvitaan kaksi taulukkoa — toinen aiempien arvioiden ylläpitämiseen ja toinen uusien arvojen tallentamiseen;
- Paikallinen varmistus: 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ä paikallista varmistusta suositaan, 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 lopettaa. Vaikka konvergenssi on taattu ääriarvossa, käytännössä laskentaa ei tarvitse jatkaa tietyn pisteen jälkeen. Yksinkertainen ja tehokas pysäytyskriteeri on seurata absoluuttista erotusta peräkkäisten arvoestimaattien välillä, ∣vk+1(s)−vk(s)∣, ja verrata sitä pieneen kynnysarvoon θ. Jos täyden päivityskierroksen (kaikkien tilojen arvojen päivitys) jälkeen mikään muutos ei ylitä θ:a, prosessi voidaan turvallisesti lopettaa.
Pseudokoodi
Kiitos palautteestasi!