Markov Decision Process on vahvistavan oppimisen THE ongelma.

Oppijaa ja ratkaisuntekijää kutsutaan yleensä agentiksi ja se minkä kanssa se on tekemisissä ja käytännössä kaikki muu kuin se agentti on ympäristöä. Kaikki vahvistava oppiminen on näiden interaktiota.

Joka ajanhetkellä t agentti saa tiedon ympäristön tilasta S_t ja valitsee sen perusteella toiminnon A_t. Yhden ajanjakson kuluttua agentti saa palkinnon R_t+1 ja on uudessa tilassa S_t+1 jne. jne. Agentin ohjekirja (policy) määrittää agentin todennäköisyyden jokaisen tilan jokaiselle actionille niin, että pitkän ajan rewardi maximoituu.

Ajan hetket eivät ole välttämättä diskreettejä, eikä rakenne ole välttämättä näin yksinkertainen. Ajanhetket voivat esim. olla päätöksiä ja rakenne voi olla koko roomban toiminto. Tilat ovat yleensä sensoreiden ohjaamia, mutta ne voivat olla esim. kameralla löydettyjä objekteja huoneesta tms. RL frameworkia pystytään näin soveltamaan lähes mihin vain tilanteeseen jossa päämäärä, tekijä ja ympäristö ovat selviä.

Palkintosignaalin tarkoitus EI OLE kertoa miten joku tehdään, vaan palkita sen tekemisestä. Lopullinen päämäärä on tärkeä, ja sivujuonten liika palkitseminen ei johda lopullisen päämäärän saavuttamiseen.

Agentin ja ympäristön raja on kontrollin ja muuttumisen raja. Robotin tapauksessa raja ei siis ole raajat/ilma, vaan cpu/raajat.

Jos rewardin pystyy jakamaan tasaisiin aikajaksoihin tai episodeihin ja jokainen episodi päättyy niin, ettei aiempien episodien tila vaikuta uusimpaan, päättyy jokainen episodi terminaaliseen tilaan. Tällöin tehtävää kutsutaan episodiseksi tehtäväksi. Jos tehtävässä on myös ei-terminaalisia episodeja, on terminaalinen episodi S + ja ei terminaalinen S.

Alennustermi γ laskee myöhempien tekojen tärkeyttä jatkuvassa tehtävässä. (3.2). Tästä johdettuna kaavan 3.3 avulla selviää, että goalin laskeminen on helpompaa jos lähdetään lopusta.

Episodinen ja jatkuva-aikainen tehtävä on kaksi eri asiaa.

Tilasignaalin preprocessointia ei tässä kirjassa tarkastella.

Tilasignaali on yksinkertaisimmillaan aistit. Ne voivat kuitenkin olla myös monimutkaisempia rakenteita, kuten ajan myötä rakentuneet jutut, esim. huoneesta näkyy kerrallaan vain osa, mutta silmiä liikuttamalla muodostuu kokonaisuus. Tilasignaali ei kuitenkaan voi sisältää mitään, mitään agentti ei voisi tietää, sillä se ei auttaisi oppimista. Optimi tilasignaali sisältää sopivasti tietoa menneestä niin, että tämänhetkiset sensaatiot otetaan myös huomioon.

Tilasignaali joka säilyttää kaiken tärkeän tiedon on Markov, esimerkiksi tennispallon sijainti, suunta ja nopeus on markov, sillä se sisältää kaiken tiedon tulevaisuutta varten.

Tilalla on Markov ominaisuus, jos t+1 on riippuvainen vain t:stä, kaava 3.7. Joskus tilasignaalia approksimoidaan Markovina, vaikka se ei sitä ole. Näin jokaista tilaa voidaan approksimoida Markov tilana ja tulevaisuutta voidaan ennustaa arvioimalla.

Markov ominaisuudet ovat hyvin teoreettisiä oikeassa elämässä, sillä sensorien tarkkuus, lämpötila muutokset ja aineiden rakenteet vaikuttavat liikaa kaikkeen.

Vahvistavan oppimisen tehtävä joka toteuttaa markov ominaisuuden on nimeltään Markov Decision Process (MDP). Jos tila- sekä teko-avaruudet on rajattuja, on se finite MDP ja ne käsittää suurimman osan vahvistavan oppimisen teoriasta.

Transitio-graafilla pystyy hyvin kuvaamaan rajallisen MDP'n ominaisuuksia. Siinä on tila-nodeja ja tapahtuma-nodeja ja niiden välillä menee todennäköisyys käyriä (fig 3.3).

Arvofunktion tehtävä on määrittää kuinka hyvä agentin on olla kyseisessä tilassa, tai kuinka hyvä sen on toteuttaa toimintoja kyseisessä tilassa. Arvofunktion voi esittää sääntökirjan (pii) odotusarvon avulla, jota sitten yritetään maksimoida. Tästä saa johdettua tila-arvo sekä tapahtuma-arvo funktiot säännölle pii.

Arvofunktioiden määrittäminen on vaikeaa, jolloin niitä voidaan arvioida kokemuksen avulla. Jos tarpeeksi toistoja tehdään niin arvofunktiot lähestyy jotain arvoa, tällaisia arviointitekniikoita kutsutaan Monte Carlo metodeiksi. Arvofunktioita voidana arvioida joko koko tilakartalle, tai jokaiselle tilalle erikseen.

Bellmanin kaavalle voidaan tutkia yhteyttä tilan arvon ja tulevaisuuden tilojen arvojen välillä. Tämä on pohja monelle tavalle laskea, arvioida ja oppia tila-arvo funktio.

Bellmanin kaavan suora ratkaiseminen ja optimointi johtaa keinoon löytää optimaali sääntö-opas, mutta siitä on harvoin hyötyä. Se vaatisi ainakin: ympäristön dynamiikan ymmärtämisen, suurten laskennalisten resurssien käyttö, Markov-ominaisuuden. Vaikka ensimmäinen ja kolmas ehto toteutuisi, tulee toisessa helposti raja vastaan. Esim backgammonissa kestäisi tuhansia vuosia.

Useat algoritmit arvioivat ratkaisua Bellmannille. Esim heuristinen haku (A* haku).

Vaikka optimaalisen reitin approksimointi voi tuntua huonolta, johtaa se joskus hyviin asioihin. Usein esiintyvien tilojen ratkaisu tulee approksimoimalla usein halvaksi ja helpoksi ja myös onnistuvaksi, kun taas harvoin esiintyvät tapahtumat saattavat mennä väärin, mutta se ei yleensä haittaa juurikaan niiden harvaluontoisuuden vuoksi.

SUMMARY:

Agentti ja ympäristö ovat vuorovaikutuksessa keskenään diskreeteillä aikaväleillä. Niiden speksit määräävät tehtävän:

tapahtumat (actions) ovat agentin valitsemia, tilat (states) antavat päätökset siitä mikä tehtävä valitaan ja palkinnot (rewards) antavat päätöksen siitä mitä tehdään.

Agentin sisäinen tila on täysin agentin tiedossa ja agentin kontrollissa, agentin ulkopuolinen tila ei ole kontrolloitavissa ja voi olla tiedossa tai ei.

Sääntö (policy) on stokastinen sääntö minkä avulla agentti valitsee tapahtuman tilan funktiona.

Palautus (return) on tulevaisuuden palkintojen funktio jota yritetään maksimoida. Alennusfunktio on kätevä jatkuvalle, ja ei-alennus episodiselle.

Tila on täyttää markov-ominaisuuden jos sen tilasignaali sisältää kompaktisti menneisyyden ilman, että tulevaisuuden arviointi heikentyy. Tämä on harvoin täydellistä, mutta usein lähellä. Jos markov-ominaisuus pätee, tilaa sanotaan MDP:ksi. (tai finite mpd)

Säännön arvofunktio on määrää tilan tai tila-tapahtuman palautusarvon oletuksella että agentti käyttää sääntöä. Optimiarvofunktio määrää suurimman palautuksen. Jokaiselle MDP:lle on yksi optimiarvofunktio per tila, mutta optimeita sääntöjä on monia. Jokainen sääntö joka on ahne käyttämällä optimia arvofunktiota on optimi sääntö.

Bellmanin optimikaavat on kaavoja, jotka optimin arvofunktion tulee täyttää ja niitä voi käyttää optimin säännön löytämiseen.

Next up

Previous

Chapter 4: Dynamic Programming