Vahvistusoppimisessa agentti tai päätöksentekijä luo koulutusdataa vuorovaikutuksessa maailman kanssa. Agentin on opittava tekojensa seuraukset yrityksen ja erehdyksen kautta sen sijaan, että hänelle kerrottaisiin nimenomaisesti oikea toiminta.

Multi-Armed Bandit -ongelma

Vahvistusoppimisessa käytämme Multi-Armed Bandit Problemiä virallistamaan käsitteen päätöksenteosta epävarmuudessa k-kätisten rosvojen avulla. Päättäjä tai agentti on läsnä Multi-Armed Bandit -ongelmassa valitakseen k-eri toiminnon välillä ja saa palkinnon valitsemansa toiminnan perusteella. Bandit-ongelmaa käytetään kuvaamaan vahvistavan oppimisen peruskäsitteitä, kuten palkkioita, aikaaskeleita ja arvoja.

Yllä oleva kuva esittää kolikkopeliä, joka tunnetaan myös nimellä rosvo kahdella vipulla. Oletetaan, että jokaisella vipulla on erillinen palkintojakauma ja että siellä on vähintään yksi vipu, joka tuottaa suurimman palkinnon.

Kutakin vipua vastaavan palkkion todennäköisyysjakauma on erilainen, eikä se ole pelurille (päätöksentekijälle) tiedossa. Siksi tässä tavoitteena on tunnistaa, mitä vipua vedetään saadaksesi maksimaalisen palkinnon tietyn koesarjan jälkeen.

Esimerkiksi:

Kuvittele verkkomainontakokeilua, jossa mainostaja haluaa mitata saman tuotteen kolmen eri mainoksen napsautussuhteen. Aina kun käyttäjä vierailee verkkosivustolla, mainostaja näyttää satunnaisesti mainoksen. Mainostaja seuraa sitten, napsauttaako käyttäjä mainosta vai ei. Jonkin ajan kuluttua mainostaja huomaa, että yksi mainos näyttää toimivan paremmin kuin muut. Mainostajan on nyt päätettävä, pysyykö parhaiten menestyvässä mainoksessa vai jatkaako satunnaistettua tutkimusta.
Jos mainostaja näyttää vain yhden mainoksen, hän ei voi enää kerätä tietoja kahdesta muusta mainoksesta. Ehkä toinen mainoksista on parempi, se näyttää vain sattumalta huonommalta. Jos kaksi muuta mainosta ovat huonompia, tutkimuksen jatkaminen voi vaikuttaa napsautussuhteeseen haitallisesti. Tämä mainoskoe on esimerkki päätöksenteosta epävarmuudessa.
Yllä olevassa esimerkissä agentti on mainostajan roolissa. Mainostajan on valittava kolmen eri toiminnon välillä näyttääkseen ensimmäisen, toisen tai kolmannen mainoksen. Jokainen mainos on toiminta. Mainoksen valitseminen tuottaa tuntemattoman palkinnon. Lopuksi mainostajan voitto mainoksen jälkeen on palkkio, jonka mainostaja saa.

Toiminta-arvot:

Jotta mainostaja voi päättää, mikä toimenpide on paras, meidän on määriteltävä kunkin toimenpiteen arvo. Määritämme nämä arvot toiminta-arvo-funktiolla käyttäen todennäköisyyskieltä. Toiminnon valinnan arvo q_*(a) määritellään odotetuksi palkkioksi R_t saamme toimiessamme a mahdollisista toimenpiteistä.

Agentin tavoitteena on maksimoida odotettu palkkio valitsemalla toiminto, jolla on suurin toiminta-arvo.

Toiminta-arvoarvio:

python //-operaattori

Koska toiminnon valinnan arvo on esim. K_*(a) ei ole agentin tiedossa, joten käytämme näytteen keskiarvo tapa arvioida se.

Tutkiminen vs hyväksikäyttö:

joukkojen algebra

Ahne toiminta: Kun agentti valitsee toiminnon, jolla on tällä hetkellä suurin arvioitu arvo. Agentti hyödyntää nykyistä tietämystään valitsemalla ahneen toiminnan. Ei-ahne toiminta: Kun agentti ei valitse suurinta arvioitua arvoa ja uhraa välitöntä palkkiota toivoen saavansa lisätietoja muista toimista. Tutkiminen: Sen avulla agentti voi parantaa tietojaan jokaisesta toiminnasta. Toivottavasti se johtaa pitkän aikavälin hyötyyn. Hyödyntäminen: Sen avulla agentti voi valita ahneen toiminnan yrittääkseen saada suurimman palkinnon lyhytaikaisesta hyödystä. Puhdas ahne toimintojen valinta voi johtaa epäoptimaaliseen käyttäytymiseen.

Tutkimuksen ja hyväksikäytön välillä syntyy dilemma, koska agentti ei voi valita sekä tutkia että hyödyntää samanaikaisesti. Siksi käytämme Ylempi luottamusraja algoritmi, joka ratkaisee etsintä-hyödyntämisen dilemman

Ylemmän luottamusrajan toimintovalinta:
Upper-Confidence Bound -toimintojen valinnassa käytetään epävarmuutta toiminta-arvoarvioissa etsinnän ja hyödyntämisen tasapainottamiseksi. Koska toiminta-arvo-estimaattien tarkkuudessa on luontaista epävarmuutta, kun käytämme otosjoukkoa palkkioita, UCB käyttää arvioissa epävarmuutta etsinnässä.

K_t(a) tässä on nykyinen toiminta-arvio a Ajallaan t . Valitsemme toiminnon, jolla on suurin arvioitu toiminta-arvo plus ylemmän luottamusrajan tutkimustermi.

K(A) yllä olevassa kuvassa edustaa toiminnan nykyistä toiminta-arvoarviota A . Sulkeet edustavat luottamusväliä K_*(A) joka sanoo, että olemme varmoja siitä, että toiminnan todellinen toiminta-arvo A sijaitsee jossain tällä alueella.

Alempaa sulkua kutsutaan alarajaksi ja ylempää sulkua ylemmäksi rajaksi. Suluissa oleva alue on luottamusväli, joka edustaa arvioiden epävarmuutta. Jos alue on hyvin pieni, tulemme hyvin varmaksi, että toiminnan todellinen arvo A on lähellä arvioitua arvoamme. Toisaalta, jos alue on suuri, meistä tulee epävarmoja toiminnan arvosta A on lähellä arvioitua arvoamme.

The Ylempi luottamusraja noudattaa optimismin periaatetta epävarmuuden edessä, mikä tarkoittaa, että jos olemme epävarmoja toiminnasta, meidän tulee optimistisesti olettaa, että se on oikea toiminta.

Oletetaan esimerkiksi, että meillä on nämä neljä toimintoa ja niihin liittyviä epävarmuustekijöitä alla olevassa kuvassa, agentillamme ei ole aavistustakaan, mikä on paras toimenpide. Joten UCB-algoritmin mukaan se valitsee optimistisesti toiminnon, jolla on korkein yläraja, eli. A . Tekemällä tämän joko sillä on korkein arvo ja se saa suurimman palkinnon, tai sen avulla saamme tietää toiminnasta, josta tiedämme vähiten.

Oletetaan, että toiminnon valinnan jälkeen A päädymme alla olevassa kuvassa esitettyyn tilaan. Tällä kertaa UCB valitsee toiminnon B siitä asti kun Q(B) on korkein ylempi luottamusraja, koska sen toiminta-arvoarvio on korkein, vaikka luottamusväli on pieni.

Aluksi UCB tutkii enemmän vähentääkseen epävarmuutta järjestelmällisesti, mutta sen tutkiminen vähenee ajan myötä. Voidaan siis sanoa, että UCB saa keskimäärin suuremman palkinnon kuin muut algoritmit, kuten Epsilon-greedy, Optimistic Initial Values ​​jne.