Aloitetaan tarkastelemalla uudelleen tuttua käsitettä: tilan arvofunktio, merkittynä muodossa $v_\pi(s)$. Se voidaan määritellä seuraavasti:

Tämän luvun tavoitteena on arvioida tämä funktio datasta, olettaen että käytössä on kiinteä politiikka $\pi$, mutta ympäristön mallia ei ole saatavilla.

Monte Carlo -arviointi

Monte Carlo -menetelmät lähestyvät tätä arviointitehtävää näytteistämällä jaksoja politiikan $\pi$ mukaisesti ja käyttämällä näitä otoksia muodostamaan empiirisiä arvioita $v_\pi(s)$:stä.

Yleisesti prosessi voidaan jakaa seuraaviin vaiheisiin:

1. Generoi jakso käyttäen politiikkaa $\pi$;
2. Tallenna saatu tuottoarvo jokaiselle jaksossa esiintyvälle tilalle;
3. Toista vaiheet 1-2 useita kertoja;
4. Laske uudet arvot ottamalla keskiarvo tuotoista kullekin tilalle.

Tuottojen kerääminen

Monte Carlo -arviointi arvotoiminnolle edellyttää tuottojen keräämistä generoituista episodeista. Näiden tuottojen laskemiseen voidaan käyttää kahta pääasiallista lähestymistapaa:

• Ensimmäinen esiintymä: jokaiselle tilalle $s$, joka kohdataan episodissa, huomioidaan vain tuotto, joka seuraa sen ensimmäistä esiintymää. Saman tilan myöhemmät esiintymät samassa episodissa jätetään huomiotta arvion kannalta;
• Jokainen esiintymä: jokainen tilan $s$ esiintyminen episodissa otetaan huomioon. Eli tuotto jokaisen tilan vierailun jälkeen sisällytetään arvioon, vaikka tila esiintyisi useita kertoja saman episodin aikana.

Aloitustilojen tutkiminen

Kuvittele yksinkertainen yksisuuntainen maailma, joka on esitetty viivana, joka ulottuu -10:stä +10:een. Agentti aloittaa kohdasta 0, ja sen nykyinen politiikka määrää, että se liikkuu aina oikealle jokaisella aikavälillä.

Jos yritämme tuottaa episodeja tämän politiikan mukaisesti, mitä tapahtuu? Agentti liikkuu jatkuvasti kohti viivan positiivista päätä — käyden tiloissa kuten 1, 2, 3 ja niin edelleen — mutta se ei koskaan vieraile negatiivisissa tiloissa. Tämän seurauksena emme voi arvioida arvofunktioita origon vasemmalla puolella oleville tiloille, koska agentti ei koskaan koe niitä.

Tärkein ongelma on siis: jos tiettyjä tiloja ei koskaan tutkita, niiden arviot pysyvät epätarkkoina tai määrittelemättöminä. Yksi yleinen ratkaisu tähän ongelmaan on exploring starts -menetelmän käyttö.

Exploring starts -menetelmässä jokainen episodi ei ala kiinteästä aloitustilasta, kuten 0, vaan satunnaisesti valitusta tilasta. Kun episodi alkaa, agentti seuraa nykyistä politiikkaansa normaalisti. Ajan myötä, kun aloitustila vaihtelee eri puolilla tilaa, agentti pystyy vierailemaan kaikissa tiloissa — ei vain niissä, joihin sen politiikka luonnollisesti johtaisi. Tämä mahdollistaa Monte Carlo -menetelmän tuottaa tarkempia ja kattavampia arviota koko tilan arvosta.

Pseudokoodi

Tämä pseudokoodi käyttää joka-käynti-lähestymistapaa yhdessä tutkivien aloitusten kanssa.