Politiikan Arviointi

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

Jos ympäristön täydellinen malli on käytettävissä (eli siirtymätodennäköisyydet ja odotetut palkkiot kaikille tila-toiminto -pareille tunnetaan), ainoat tuntemattomat muuttujat yhtälössä ovat tilojen arvot. Näin ollen 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 ($s_1$, $s_2$) ja 2 toimintoa (siirry $s_1$:een, siirry $s_2$:een), tilan arvofunktio voidaan määritellä seuraavasti:

Tämä voidaan ratkaista tavanomaisilla lineaarialgebran menetelmillä.

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

• Alennustekijä täyttää ehdon $γ < 1$;
• Politiikka $\pi$ takaa, että mistä tahansa tilasta $s$ aloitettaessa episodi päättyy lopulta.

Iteratiivinen politiikan arviointi

Ratkaisu voidaan laskea suoraan, mutta iteratiivinen lähestymistapa on yleisemmin käytetty sen helpon toteutettavuuden vuoksi. Menetelmässä annetaan aluksi 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ä:

Arvioitu tilan arvon funktio $v_k$ lähestyy lopulta todellista tilan arvon funktiota $v_\pi$, kun $k \to \infty$, jos $v_\pi$ on olemassa.

Arvon varmistusstrategiat

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

• Täysi varmistus: tässä menetelmässä uudet arviot tallennetaan erilliseen taulukkoon, joka on eri kuin aiemmat (varmistetut) arvot sisältävä taulukko. Näin ollen 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ä paikallinen varmistus on suositeltavampi, koska se vaatii vähemmän muistia ja lähestyy ratkaisua nopeammin, koska uusimmat arviot otetaan heti käyttöön.

Milloin lopettaa päivitys?

Iteratiivisessa politiikan arvioinnissa ei ole tarkkaa hetkeä, jolloin algoritmin tulisi pysähtyä. 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ä, $|v_{k+1}(s) - v_k(s)|$, ja verrata sitä pieneen kynnysarvoon $\theta$. Jos täyden päivityskierroksen (kun kaikkien tilojen arvot on päivitetty) jälkeen mikään muutos ei ylitä $\theta$:a, prosessin voi lopettaa turvallisesti.

Pseudokoodi