Chapter 2: Multi-armed bandits

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.