http://incompleteideas.net/sutton/book/the-book-2nd.html   http://incompleteideas.net/sutton/book/bookdraft2017june19.pdf   Skipatut kappaleet: 1.7 Early History of Reinforcement Learning

Chapter 1: The Reinforcement Learning Problem Ongelma selitetty, helppoja esimerkkejä.   Osa 1:   Chapter 2: Multi-armed Bandit Miten valita oikea valinta?   Chapter 3: Finite Markov Decision Processes Markov prossesseissa ulostulon oletetaan olevan HiEMAN satunnainen   Chapter 4: Dynamic Programming Perusteet iteraatioille yms.   Chapter 5: Monte Carlo Methods Monte Carlo metodit käyttää useata random sämpläystä ja valitsee parhaan (neuroverkon satunnaiset painoarvot??)   Chapter 6: Temporal-Difference Learning Ennustavaa osaamista   Chapter 7: Multi-step Bootstrapping ????   Chapter 8: Planning and Learning with Tabular Methods Usean variablen funtion minimikohtien löytämiseen

Reinforcement learning = luonnollista oppimista (ympäristöstä) tietokoneille MDP (Markov Decision Process) kaavan 3 tekijää: tunnetila, tekeminen ja päämäärä. Palkinnon maksimointi on eri asia kuin piilotetun rakenteen löytäminen. Näin koneoppiminen jakautuu kolmeen osa-alueeseen, ohjattu, ei-ohjattu ja vahvistettu. Exploit & Explore, opitun hyödyntäminen ja uuden kokeilu, sopivan balanssin löytäminen on vaikeaa. Yleensä koneoppiminen on down-up (pienestä kuviosta isompaan), RL on up-down eli aloitetaan koko kuvasta ja opitaan pienet kuviot matkan varrella. Agentin ja ympäristön lisäksi 4 aihealuetta voi erotella:  1. Ohjekirja, policy: määrää sopivan actionin sopivaan tilaan. 2. Palkintosignaali: palkintosignaalin generoija on RIIPPUMATON agentin tilasta, siis se on täysin ulkopuolinen tekijä. Näin agentti ei voi muuttaa ongelmaa toiseksi maksimoidakseen palkinnon. 3. Arvofunktio: mikä on hyväksi pitkällä aikavälillä. Arvio palkinnosta tulevaisuudessa tila-jonon funktiona. Esim. tilan palkinto voi olla huono, mutta siitä seuraavien tilojen palkinto on iso joten arvofunktio on hyvä. Esim. salitreenaus tuntuu perseeltä, mutta lopputulos hyvä. Arvofunktion arvioiminen on ehkä haastavin ja tärkein osa hyvän RL algoritmin käytössä. 4. Ympäristön malli. Miten ympäristö käyttäytyy ja millaisessa tilassa se on. Käytetään suunnitteluun ja arvofunktion arvioimiseen.  Kaikki RL mallit eivät käytä ympäristöä apuna, jolloin ne perustuvat pelkkään trial-and-error harjoitteluun. Arvofunktioiden käyttö ei ole välttämätöntä. Geneettiset algoritmit yms. eivät käytä. Ne keskittyvät agentin koko elinikään ja perustavat tekonsa siihen. Nämä tosin vaativat pienen tila-avaruuden, sillä muuten ne olisivat liian vaikeita opettaa (vielä...). Tämän kirjan puitteissa RL metodit eivät sisällä evoluutio menetelmiä. Joitain tila-gradientti-metodeihin perustuvia malleja kirjassa tosin on ja ne eivät perustu arvofunktioihin.   Tic tac toe esimerkki, exploratory oppiminen on tärkeää.

Helppoja metodeja joihin löytyy lopullinen ratkaisu.

Evaluoiva oppiminen: Riippuvainen tehdystä työstä. instruktoiva oppiminen: Riippumaton tehdystä työstä. k-armed bandit: k-kappaletta satunnaisjakaumia jotka pitää oppia mahdollisimman tehokkaasti (nopeasti) niin, että ulostulos maksimoituu. Parhaimman arvofunktion valintaa sanotaan ahneeksi valinnaksi, koska silloin hyödynnetään aiempaa tietoa siitä mikä on paras. Jos taas valitaan joku toinen, käytetään aika tutkimiseen joka taas parantaa tietoa jakaumista. Oikean teon valinta perustuu: tunnettuun arvojakaumaan, epätietouden määrään ja jäljellä olevien yritysten määrään. Yleensä ahnetta, mutta satunnaisesti tutkivaa, metodia kutsutaan ε-ahneeksi, jolloin todennäköisyydellä ε tutkitaan muita vaihtoehtoja. Suurella varianssilla (yleisessä tapauksessa) ε-ahne on hyödyllinen, koska pelkällä alkutiedolla ei yleensä pitkälle pötkitä. Update Rule: NewEstimate ← OldEstimate + StepSize*[Target − OldEstimate], missä StepSize  n:nelle rewardille actionilla a on 1/n. Päivityssääntö toimii, jos 'bandiitti' ei muutu. Sen muuttuessa tulee kuitenkin uusimpia tuloksia painottaa eniten. Tällöin stepsize kannattaa asettaa vakioksi ts. learning rate α (0, 1] jolloin NewEstimate on painotettu keskiarvo. Alkuperäinen update rule missä StepSize = 1/n convergeentyy kun kaikki ratkaisut on käyty ja on näin helppo ratkaisu helppoihin ongelmiin, mutta vaikeiisin ongelmiin joihin ei ole helppoa käydä kaikki ratkaisuja lävitse käytetään α-parametriä, jolloin arvio ei ikinä supistu nollaan vaan aina reagoi uusimpiin tapahtumiin. Initial valuen vaikutus koko oppimiseen tällä keinolla on suuri, ja sen valintaa voidaan pitää priori-tiedon hyödyntämisenä. Oikeaan suuntaan valittujen alkuarvojen valintaa kutsutaan optimistiseksi alkuarvojen valinnaksi ja sitä voi pitää yksinkertaisena temppuna nopeuttaa oppimista etenkin helpoissa stationaarisissa ongelmissa koska se aiheuttaa nopeaa, väliaikaista oppimista alussa. ε-ahne on hyvä alku tutkimiselle, mutta satunnaisuus ei ole paras vaihtoehto. Parhaan vaihtoehdon tutkiminen ensiksi vaikuttaa paremmalta idealta. Yksi esimerkki tähän on upper confidence bound joka etenkin alkuun painottaa optimistisimpia vaihtoehtoja. Se on usein parempi kuin ε-ahne, mutta sen käyttö on huomattavasti vaikeampaa laajemmissa ongelmissa.  Gradientti bandiitti preferoi actionia verrattuna muihin actioneihin, eikä rewardiin softmaxin avulla. Käytännössä hyvin lähellä SGD:tä. Assosiatiivisessa haussa oikealle tilanteelle keksitään oikea actioni. Tilanne opitaan ja sille luodaan ohje.    tl;dr. greedy, ε-greedy, UCB ja gradientti on kaikki vaihtoehtoja yksinkertaseen k-bandit ongelmaan mutta kaikissa on myös parametri jonka oikean arvon löytäminen on tärkeää, liian pieni/suuri on huono. UCB tuntuu parhaalta.  Gittins Indices on keino jolla laskea optimi tapa oppia, jos tiedetään priori distribuutiot.  Bayesian optimisaatiolla on mahdollista löytää täydellinen ratkaisu, mutta sen laskenta on liian vaativaa.

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.

Dynaaminen ohjelmointi viittaa algoritmeihin joita voidaan käyttää optimisäännön löytämiseen oletuksella, että ympäristöä voidaan käsitellä MDP:nä.

Tälle joku helpompi ratkasu.. policy(pii) määrittää todennäköisyyden aktionille a tilassa s. Update rule (2.4) ja incremental update rule (2.5), yksinkertaiset päivitykset arvoille uuden tuloksen mukaan, ts. yksinkertaisin versio oppimisesta. Upper-Confidence-Bound action selection (2.8) toiminnon valinta joka tutkii parasta sellaista vaihtoehtoa, joiden potentiaali olla optimi on korkea.   3.1 Goal = Reward(t+1) + Reward(t+2).. 3.2 Goal = Reward(t+1) + γ*Reward(t+2) + γ²*Reward(t+3)..., 0<γ<1 3.3 Goal = Reward(t+1) + γ*Goal(t+1) 3.8 ja siitä johdetut eteenpäin, rajattu markov ketjun yleiset versiot. 3.12 tila-arvo funktio säännölle pii.  3.13 tapahtuma-arvo funktio säännölle pii. 3.14 Bellmanin Kaava kaavalle 3.12.

1. Ei mitään?   2. greedy, ε-greedy, UCB, gradient bandit   3. Goal = Reward (t+1) + y*Goal(t+1) Rajotetusta markov ketjusta johdetut kaavat rewardille, tila-muutoksen todennäkösyydelle ja odotetut rewardit.