V posilňovacom učení agent alebo osoba s rozhodovacou právomocou generuje svoje tréningové údaje prostredníctvom interakcie so svetom. Agent sa musí dozvedieť o dôsledkoch svojich činov prostredníctvom pokusov a omylov, namiesto toho, aby mu bolo výslovne povedané, ako správne konať.
Problém viacrukého banditu
V posilňovacom učení používame Problém s mnohorukým banditom na formalizáciu pojmu rozhodovania v neistote pomocou k-ozbrojených banditov. Osoba s rozhodovacou právomocou alebo agent je prítomný v Probléme s mnohorukým banditom, aby si mohol vybrať medzi k-rôznymi akciami a dostane odmenu na základe akcie, ktorú si vyberie. Problém banditov sa používa na opis základných pojmov v posilňovaní učenia, ako sú odmeny, časové kroky a hodnoty.
Obrázok hore predstavuje hrací automat známy aj ako bandita s dvoma pákami. Predpokladáme, že každá páka má samostatné rozdelenie odmien a existuje aspoň jedna páka, ktorá generuje maximálnu odmenu.
Rozdelenie pravdepodobnosti pre odmenu zodpovedajúcu každej páke je iné a hráč (rozhodovateľ) ho nepozná. Cieľom je teda určiť, ktorú páku potiahnuť, aby ste po danom súbore pokusov získali maximálnu odmenu.
Napríklad:
Predstavte si test inzercie online, kde chce inzerent zmerať mieru prekliknutia troch rôznych reklám na rovnaký produkt. Vždy, keď používateľ navštívi webovú stránku, inzerent náhodne zobrazí reklamu. Inzerent potom sleduje, či používateľ klikol na reklamu alebo nie. Po chvíli si inzerent všimne, že jedna reklama funguje lepšie ako ostatné. Inzerent sa teraz musí rozhodnúť, či zostane pri reklame s najlepšou výkonnosťou alebo bude pokračovať v randomizovanej štúdii.
Ak inzerent zobrazí iba jednu reklamu, potom už nemôže zbierať údaje o ďalších dvoch reklamách. Možno je niektorá z ostatných reklám lepšia, len sa náhodou javí horšie. Ak sú ostatné dve reklamy horšie, pokračovanie v štúdii môže nepriaznivo ovplyvniť mieru prekliknutia. Tento reklamný pokus je príkladom rozhodovania v neistote.
Vo vyššie uvedenom príklade hrá úlohu agenta inzerent. Inzerent si musí vybrať z troch rôznych akcií na zobrazenie prvej, druhej alebo tretej reklamy. Každá reklama je akcia. Výber tejto reklamy prináša neznámu odmenu. Nakoniec, zisk inzerenta po reklame je odmena, ktorú inzerent dostane.
Akčné hodnoty:
Aby sa inzerent mohol rozhodnúť, ktorá akcia je najlepšia, musíme definovať hodnotu každej akcie. Tieto hodnoty definujeme pomocou funkcie akčnej hodnoty pomocou jazyka pravdepodobnosti. Hodnota výberu akcie q*(a) je definovaná ako očakávaná odmena Rt dostávame pri vykonávaní akcie a z možného súboru akcií.
Cieľom agenta je maximalizovať očakávanú odmenu výberom akcie, ktorá má najvyššiu akčnú hodnotu.
Odhad hodnoty akcie:
halda a halda triediť
Keďže hodnota výberu akcie t.j. Q*(a) nie je agentovi známe, preto použijeme vzorový priemer spôsob, ako to odhadnúť.
Prieskum verzus využívanie:
- Nenásytná akcia : Keď agent vyberie akciu, ktorá má momentálne najväčšiu odhadovanú hodnotu. Agent využíva svoje súčasné znalosti výberom zištnej akcie. Non-Greedy Action: Keď agent nezvolí najväčšiu odhadovanú hodnotu a obetuje okamžitú odmenu v nádeji, že získa viac informácií o ostatných akciách. Prieskum : Umožňuje agentovi zlepšiť svoje znalosti o každej akcii. Dúfajme, že to povedie k dlhodobému prínosu. Vykorisťovanie : Umožňuje agentovi vybrať si chamtivý postup, aby sa pokúsil získať čo najväčšiu odmenu za krátkodobý prospech. Čistý výber chamtivých akcií môže viesť k neoptimálnemu správaniu.
Medzi prieskumom a vykorisťovaním nastáva dilema, pretože agent si nemôže vybrať, či bude skúmať aj využívať súčasne. Preto používame Horná hranica dôvery algoritmus na vyriešenie dilemy prieskumu a využívania
Výber akcie s hornou hranicou dôvery:
Výber akcie na základe hornej hranice spoľahlivosti využíva neistotu v odhadoch akčnej hodnoty na vyváženie prieskumu a využívania. Keďže existuje inherentná neistota v presnosti odhadov akčnej hodnoty, keď používame vzorkovaný súbor odmien, UCB používa neistotu v odhadoch na riadenie prieskumu.
funkcia volania javascriptu z html
Qt(a) tu predstavuje aktuálny odhad akcie a v čase t . Vyberieme akciu, ktorá má najvyššiu odhadovanú akčnú hodnotu plus výraz prieskumu s hornou hranicou spoľahlivosti.
Q(A) na obrázku vyššie predstavuje aktuálny odhad akčnej hodnoty pre akciu A . Zátvorky predstavujú interval spoľahlivosti Q*(A) čo hovorí, že sme presvedčení, že skutočná akčná hodnota akcie A leží niekde v tomto regióne.
Dolná zátvorka sa nazýva dolná hranica a horná zátvorka je horná hranica. Oblasť medzi zátvorkami je interval spoľahlivosti, ktorý predstavuje neistotu v odhadoch. Ak je región veľmi malý, potom sme si veľmi istí, že skutočná hodnota akcie A sa blíži našej odhadovanej hodnote. Na druhej strane, ak je región veľký, potom si nie sme istí, že hodnota akcie A sa blíži našej odhadovanej hodnote.
The Horná hranica dôvery dodržiava princíp optimizmu tvárou v tvár neistote, ktorý znamená, že ak si nie sme istý konaním, mali by sme optimisticky predpokladať, že je to správne konanie.
Povedzme napríklad, že na obrázku nižšie máme tieto štyri akcie so súvisiacimi neistotami, náš agent netuší, ktorá akcia je najlepšia. Takže podľa algoritmu UCB optimisticky vyberie akciu, ktorá má najvyššiu hornú hranicu, t.j. A . Ak to urobíte, buď to bude mať najvyššiu hodnotu a získate najvyššiu odmenu, alebo ak to urobíte, dozvieme sa o akcii, o ktorej vieme najmenej.
Predpokladajme, že po výbere akcie A skončíme v stave znázornenom na obrázku nižšie. Tentoraz UCB vyberie akciu B odkedy Q(B) má najvyššiu hornú hranicu spoľahlivosti, pretože jej odhad akčnej hodnoty je najvyšší, aj keď je interval spoľahlivosti malý.
Spočiatku UCB skúma viac, aby systematicky znižovala neistotu, ale jej prieskum sa časom znižuje. Môžeme teda povedať, že UCB získava v priemere väčšiu odmenu ako iné algoritmy, ako napríklad Epsilon-greedy, Optimistic Initial Values atď.