Pri učenju z okrepitvijo agent ali odločevalec ustvari svoje podatke o usposabljanju z interakcijo s svetom. Agent se mora naučiti posledic svojih dejanj s poskusi in napakami, namesto da bi mu izrecno povedali pravilno dejanje.

Problem z večorokimi razbojniki

V Reinforcement Learning uporabljamo problem večrokih razbojnikov, da formaliziramo pojem odločanja v negotovosti z uporabo k-rokih razbojnikov. Odločevalec ali agent je prisoten v Problemu z večorokimi razbojniki, da izbira med k-različnimi dejanji in prejme nagrado glede na dejanje, ki ga izbere. Problem bandita se uporablja za opisovanje temeljnih konceptov pri učenju z okrepitvijo, kot so nagrade, časovni koraki in vrednosti.

Zgornja slika predstavlja igralni avtomat znan tudi kot bandit z dvema vzvodoma. Predvidevamo, da ima vsak vzvod ločeno porazdelitev nagrad in da obstaja vsaj en vzvod, ki ustvari največjo nagrado.

Porazdelitev verjetnosti za nagrado, ki ustreza vsakemu vzvodu, je drugačna in igralcu (odločevalcu) ni znana. Zato je cilj tukaj ugotoviti, kateri vzvod potegniti, da bi po določenem nizu poskusov dobili največjo nagrado.

Na primer:

Predstavljajte si preskus spletnega oglaševanja, kjer želi oglaševalec izmeriti razmerje med prikazi in kliki treh različnih oglasov za isti izdelek. Kadar koli uporabnik obišče spletno mesto, oglaševalec naključno prikaže oglas. Oglaševalec nato spremlja, ali uporabnik klikne na oglas ali ne. Čez nekaj časa oglaševalec opazi, da se zdi, da en oglas deluje bolje kot drugi. Oglaševalec se mora zdaj odločiti, ali bo ostal pri najuspešnejšem oglasu ali nadaljeval z randomizirano študijo.
Če oglaševalec prikazuje le en oglas, potem ne more več zbirati podatkov o ostalih dveh oglasih. Morda je kateri od drugih oglasov boljši, samo po naključju se zdi slabši. Če sta druga dva oglasa slabša, lahko nadaljevanje študije negativno vpliva na razmerje med prikazi in kliki. Ta preizkus oglaševanja je primer odločanja v negotovosti.
V zgornjem primeru vlogo agenta igra oglaševalec. Oglaševalec mora izbrati med tremi različnimi dejanji, za prikaz prvega, drugega ali tretjega oglasa. Vsak oglas je akcija. Izbira tega oglasa prinese neko neznano nagrado. Končno je dobiček oglaševalca po oglasu nagrada, ki jo oglaševalec prejme.

Action-Vrednosti:

Da se oglaševalec odloči, katero dejanje je najboljše, moramo opredeliti vrednost vsakega dejanja. Te vrednosti definiramo s funkcijo dejanje-vrednost z uporabo jezika verjetnosti. Vrednost izbire dejanja q_*(a) je opredeljena kot pričakovana nagrada R_t prejmemo ob ukrepanju a iz možnega niza dejanj.

Cilj agenta je povečati pričakovano nagrado z izbiro akcije, ki ima najvišjo vrednost akcije.

Ocena vrednosti dejanja:

enako java

Ker je vrednost izbire dejanja, tj. Q_*(a) agentu ni znan, zato bomo uporabili vzorčno povprečje način za njegovo oceno.

Raziskovanje proti izkoriščanju:

Pohlepno dejanje : Ko agent izbere dejanje, ki ima trenutno največjo ocenjeno vrednost. Agent izkorišča svoje trenutno znanje z izbiro pohlepnega dejanja. Nepohlepno dejanje: Ko agent ne izbere največje ocenjene vrednosti in žrtvuje takojšnjo nagrado v upanju, da bo pridobil več informacij o drugih dejanjih. Raziskovanje : omogoča agentu, da izboljša svoje znanje o vsakem dejanju. Upajmo, da vodi v dolgoročno korist. Izkoriščanje: agentu omogoča, da izbere pohlepno dejanje, s katerim poskuša dobiti največjo nagrado za kratkoročno korist. Čisto pohlepna izbira dejanj lahko privede do neoptimalnega vedenja.

Pojavi se dilema med raziskovanjem in izkoriščanjem, ker se agent ne more odločiti za raziskovanje in izkoriščanje hkrati. Zato uporabljamo Zgornja meja zaupanja algoritem za rešitev dileme raziskovanje-izkoriščanje

Izbira dejanja z zgornjo mejo zaupanja:
Izbira dejanja z mejo zgornje meje zaupanja uporablja negotovost v ocenah vrednosti dejanja za uravnoteženje raziskovanja in izkoriščanja. Ker obstaja inherentna negotovost v točnosti ocen vrednosti dejanja, ko uporabljamo vzorčen nabor nagrad, UCB uporablja negotovost v ocenah za spodbujanje raziskovanja.

Q_t(a) tukaj predstavlja trenutno oceno za ukrepanje a v času t . Izberemo dejanje, ki ima najvišjo ocenjeno vrednost dejanja in raziskovalni izraz z zgornjo mejo zaupanja.

V(A) na zgornji sliki predstavlja trenutno oceno vrednosti dejanja za ukrepanje A . Oklepaji predstavljajo interval zaupanja okoli Q_*(A) ki pravi, da smo prepričani, da je dejanska vrednost dejanja A leži nekje v tej regiji.

niz ti int

Spodnji oklepaj se imenuje spodnja meja, zgornji oklepaj pa zgornja meja. Območje med oklepaji je interval zaupanja, ki predstavlja negotovost v ocenah. Če je regija zelo majhna, postanemo zelo prepričani, da je dejanska vrednost akcije A je blizu naše ocenjene vrednosti. Po drugi strani pa, če je regija velika, postanemo negotovi o vrednosti ukrepa A je blizu naše ocenjene vrednosti.

The Zgornja meja zaupanja sledi načelu optimizma ob negotovosti, kar pomeni, da če smo negotovi glede dejanja, moramo optimistično domnevati, da je to pravilno dejanje.

Na primer, recimo, da imamo ta štiri dejanja s povezanimi negotovostmi na spodnji sliki, naš agent nima pojma, katero je najboljše dejanje. Torej bo glede na algoritem UCB optimistično izbral dejanje, ki ima najvišjo zgornjo mejo, tj. A . S tem bo imelo najvišjo vrednost in prejelo najvišjo nagrado ali pa se bomo s tem naučili o dejanju, o katerem najmanj vemo.

Predpostavimo, da po izbiri dejanja A končamo v stanju, prikazanem na spodnji sliki. Tokrat bo akcijo izbral UCB B od Q(B) ima najvišjo zgornjo mejo zaupanja, ker je njegova ocena vrednosti dejanja najvišja, čeprav je interval zaupanja majhen.

Na začetku UCB raziskuje več, da bi sistematično zmanjšal negotovost, vendar se njegovo raziskovanje sčasoma zmanjša. Tako lahko rečemo, da UCB v povprečju dobi večjo nagrado kot drugi algoritmi, kot so Epsilon-greedy, Optimistic Initial Values ​​itd.