Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Oppiskele Monte Carlo -ohjausmenetelmät | Monte Carlo -menetelmät
Vahvistusoppimisen Perusteet

bookMonte Carlo -ohjausmenetelmät

Korvaamalla politiikan arviointi -vaihe perinteisessä politiikan iterointi -algoritmissa edellisessä luvussa esitetyillä Monte Carlo -arviointitekniikoilla, voidaan johtaa uusi politiikan iteroinnin muunnelma—sellainen, joka perustuu otettuun kokemukseen dynaamisen ohjelmoinnin sijaan.

Tässä on kuitenkin olennainen rajoitus. Perinteisessä politiikan iteroinnissa politiikan parantaminen edellyttää täydellistä mallia ympäristöstä. Tarkemmin sanottuna politiikkaa päivitetään seuraavan lausekkeen avulla:

π(s)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γv(s′))\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

Tämä yhtälö olettaa, että siirtymätodennäköisyydet p(s′,r∣s,a)p(s', r | s, a) tunnetaan. Mutta juuri tässä on ongelma: Monte Carlo -menetelmät on suunniteltu mallittomiin tilanteisiin, joissa ympäristön siirtymädynamiikka ei ole tiedossa. Jos täydellinen malli on käytettävissä, kannattaa käyttää dynaamista ohjelmointia myös politiikan arviointiin, koska se olisi tehokkaampaa ja tarkempaa.

Siksi, vaikka Monte Carlo -menetelmien käyttäminen arvon estimointiin on askel kohti mallivapaata vahvistusoppimista, täytyy myös löytää tapa suorittaa politiikan parantaminen ilman mallin tuntemusta. Tämä edellyttää siirtymistä tilan arvon funktiosta toiminnon arvon funktioon.

Miksi toimintojen arvot?

Käyttämällä toimintojen arvoja voidaan politiikan parantaminen suorittaa ilman ympäristön mallia. Siirtymätodennäköisyyksien sijaan odotettujen tuottojen laskemiseksi voidaan suoraan valita ne toiminnot, jotka näyttävät tuottavan korkeimman arvon. Politiikan parantamisen vaihe on tällöin:

π(s)←arg max⁡aq(s,a)∀s∈S\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

Ja ei ole vaikea osoittaa, että uusi politiikka ei ole huonompi kuin vanha, sillä politiikan parantamisen lause pätee edelleen:

qπk(s,πk+1(s))=qπk(s,arg max⁡aqπk(s,a))=max⁡aqπk(s,a)≥qπk(s,πk(s))=vπk(s)\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

Ja kuten DP:ssä, tämä lause takaa, että joko πk+1\pi_{k+1} on parempi kuin πk\pi_k, tai ne ovat molemmat yhtä hyviä ja optimaalisia.

Toimintoarvofunktion estimointi

Arviointiprosessi on lähes identtinen tilaarvofunktion kanssa. Kaikkia tilaarvojen arvioinnissa käytettyjä ideoita voidaan hyödyntää myös toimintoarvojen arvioinnissa.

Pseudokoodi

Näin ollen, riittävällä määrällä iteraatioita, arvioidut toimintojen arvot lähestyvät todellisia toimintojen arvoja.

Tämän avulla voidaan jo rakentaa politiikan iterointia muistuttava menetelmä, joka ei perustu malliin. Tässä korvataan politiikan arviointi ja politiikan parantaminen yllä kuvatuilla prosesseilla.

Optimointi

Vaikka arviointivaihe voidaan suorittaa Monte Carlo -arvioinnilla kuten kuvattu, se on usein laskennallisesti tehotonta. Kuten on jo nähty, Monte Carlo -menetelmät vaativat tyypillisesti suuren määrän otoksia tuottaakseen riittävän tarkkoja arvioita. Jos noudatetaan politiikan iteroinnin kaltaista rakennetta, tämä tehottomuus korostuu: jokaisen politiikan parantamisen jälkeen Monte Carlo -arviointi täytyy suorittaa uudelleen uuden politiikan arvioimiseksi — mikä aiheuttaa huomattavaa ylikuormitusta ja hidasta oppimista.

Luontevampi vaihtoehto on päivittää politiikka välittömästi jokaisen episodin käsittelyn jälkeen. Sen sijaan, että odotetaan koko politiikan arvioinnin valmistumista, annetaan agentin hienosäätää käyttäytymistään episodi kerrallaan hyödyntäen uusimpia toimintojen arviota.

Tämä johtaa menetelmään, joka muistuttaa enemmän arvoiterointia: arvioinnin ja parantamisen yhdistäminen yhdeksi vaiheeksi. Tämä lisää otosten tehokkuutta ja nopeuttaa laskentaa.

Pseudokoodi

Tämä algoritmi noudattaa GPI-kehystä, sillä siinä on politiikan arviointi ja politiikan parantaminen -vaiheet, ja sitä kutsutaan nimellä Monte Carlo -kontrolli. Tämän tietyn toteutuksen suurin haittapuoli on oletus exploring starts -periaatteesta. Seuraavissa luvuissa näet, miksi tämä on ongelma ja miten siihen voidaan puuttua.

question mark

Mikä on tärkein etu käyttää toimintoarvoja tilaarvojen sijaan Monte Carlo -kontrollissa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 4. Luku 3

Kysy tekoälyä

expand

Kysy tekoälyä

ChatGPT

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

Suggested prompts:

Can you explain what "exploring starts" means in this context?

How does Monte Carlo control differ from traditional policy iteration?

What are the main challenges when using Monte Carlo methods for control?

Awesome!

Completion rate improved to 2.7

bookMonte Carlo -ohjausmenetelmät

Pyyhkäise näyttääksesi valikon

Korvaamalla politiikan arviointi -vaihe perinteisessä politiikan iterointi -algoritmissa edellisessä luvussa esitetyillä Monte Carlo -arviointitekniikoilla, voidaan johtaa uusi politiikan iteroinnin muunnelma—sellainen, joka perustuu otettuun kokemukseen dynaamisen ohjelmoinnin sijaan.

Tässä on kuitenkin olennainen rajoitus. Perinteisessä politiikan iteroinnissa politiikan parantaminen edellyttää täydellistä mallia ympäristöstä. Tarkemmin sanottuna politiikkaa päivitetään seuraavan lausekkeen avulla:

π(s)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γv(s′))\pi(s) \gets \argmax_a \sum_{s', r} \textcolor{red}{p(s', r | s, a)} \Bigl(r + \gamma v(s')\Bigr)

Tämä yhtälö olettaa, että siirtymätodennäköisyydet p(s′,r∣s,a)p(s', r | s, a) tunnetaan. Mutta juuri tässä on ongelma: Monte Carlo -menetelmät on suunniteltu mallittomiin tilanteisiin, joissa ympäristön siirtymädynamiikka ei ole tiedossa. Jos täydellinen malli on käytettävissä, kannattaa käyttää dynaamista ohjelmointia myös politiikan arviointiin, koska se olisi tehokkaampaa ja tarkempaa.

Siksi, vaikka Monte Carlo -menetelmien käyttäminen arvon estimointiin on askel kohti mallivapaata vahvistusoppimista, täytyy myös löytää tapa suorittaa politiikan parantaminen ilman mallin tuntemusta. Tämä edellyttää siirtymistä tilan arvon funktiosta toiminnon arvon funktioon.

Miksi toimintojen arvot?

Käyttämällä toimintojen arvoja voidaan politiikan parantaminen suorittaa ilman ympäristön mallia. Siirtymätodennäköisyyksien sijaan odotettujen tuottojen laskemiseksi voidaan suoraan valita ne toiminnot, jotka näyttävät tuottavan korkeimman arvon. Politiikan parantamisen vaihe on tällöin:

π(s)←arg max⁡aq(s,a)∀s∈S\pi(s) \gets \argmax_a q(s, a) \qquad \forall s \in S

Ja ei ole vaikea osoittaa, että uusi politiikka ei ole huonompi kuin vanha, sillä politiikan parantamisen lause pätee edelleen:

qπk(s,πk+1(s))=qπk(s,arg max⁡aqπk(s,a))=max⁡aqπk(s,a)≥qπk(s,πk(s))=vπk(s)\begin{aligned} q_{\pi_{k}}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \argmax_a q_{\pi_k}(s, a))\\ &= \max_a q_{\pi_k}(s, a)\\ &\ge q_{\pi_k}(s, \pi_k(s))\\ &= v_{\pi_k}(s) \end{aligned}

Ja kuten DP:ssä, tämä lause takaa, että joko πk+1\pi_{k+1} on parempi kuin πk\pi_k, tai ne ovat molemmat yhtä hyviä ja optimaalisia.

Toimintoarvofunktion estimointi

Arviointiprosessi on lähes identtinen tilaarvofunktion kanssa. Kaikkia tilaarvojen arvioinnissa käytettyjä ideoita voidaan hyödyntää myös toimintoarvojen arvioinnissa.

Pseudokoodi

Näin ollen, riittävällä määrällä iteraatioita, arvioidut toimintojen arvot lähestyvät todellisia toimintojen arvoja.

Tämän avulla voidaan jo rakentaa politiikan iterointia muistuttava menetelmä, joka ei perustu malliin. Tässä korvataan politiikan arviointi ja politiikan parantaminen yllä kuvatuilla prosesseilla.

Optimointi

Vaikka arviointivaihe voidaan suorittaa Monte Carlo -arvioinnilla kuten kuvattu, se on usein laskennallisesti tehotonta. Kuten on jo nähty, Monte Carlo -menetelmät vaativat tyypillisesti suuren määrän otoksia tuottaakseen riittävän tarkkoja arvioita. Jos noudatetaan politiikan iteroinnin kaltaista rakennetta, tämä tehottomuus korostuu: jokaisen politiikan parantamisen jälkeen Monte Carlo -arviointi täytyy suorittaa uudelleen uuden politiikan arvioimiseksi — mikä aiheuttaa huomattavaa ylikuormitusta ja hidasta oppimista.

Luontevampi vaihtoehto on päivittää politiikka välittömästi jokaisen episodin käsittelyn jälkeen. Sen sijaan, että odotetaan koko politiikan arvioinnin valmistumista, annetaan agentin hienosäätää käyttäytymistään episodi kerrallaan hyödyntäen uusimpia toimintojen arviota.

Tämä johtaa menetelmään, joka muistuttaa enemmän arvoiterointia: arvioinnin ja parantamisen yhdistäminen yhdeksi vaiheeksi. Tämä lisää otosten tehokkuutta ja nopeuttaa laskentaa.

Pseudokoodi

Tämä algoritmi noudattaa GPI-kehystä, sillä siinä on politiikan arviointi ja politiikan parantaminen -vaiheet, ja sitä kutsutaan nimellä Monte Carlo -kontrolli. Tämän tietyn toteutuksen suurin haittapuoli on oletus exploring starts -periaatteesta. Seuraavissa luvuissa näet, miksi tämä on ongelma ja miten siihen voidaan puuttua.

question mark

Mikä on tärkein etu käyttää toimintoarvoja tilaarvojen sijaan Monte Carlo -kontrollissa?

Select the correct answer

Oliko kaikki selvää?

Miten voimme parantaa sitä?

Kiitos palautteestasi!

Osio 4. Luku 3
some-alt