Bij Reinforcement Learning genereert de agent of beslisser zijn trainingsgegevens door interactie met de wereld. De agent moet met vallen en opstaan ​​de gevolgen van zijn acties leren kennen, in plaats van dat hem expliciet de juiste actie wordt verteld.

Probleem met meerarmige bandieten

Bij Reinforcement Learning gebruiken we Multi-Armed Bandit Problem om het idee van besluitvorming onder onzekerheid te formaliseren met behulp van k-armed bandieten. In Multi-Armed Bandit Problem is een beslisser of agent aanwezig die kan kiezen tussen k-verschillende acties en ontvangt een beloning op basis van de actie die hij kiest. Het bandietenprobleem wordt gebruikt om fundamentele concepten bij versterkend leren te beschrijven, zoals beloningen, tijdstappen en waarden.

De afbeelding hierboven stelt een gokautomaat voor, ook wel bandiet genoemd, met twee hendels. We gaan ervan uit dat elke hefboom een ​​aparte verdeling van beloningen heeft en dat er minstens één hefboom is die maximale beloning genereert.

De kansverdeling voor de beloning die overeenkomt met elke hefboom is verschillend en onbekend voor de gokker (beslisser). Het doel hier is dus om vast te stellen welke hefboom moet worden gebruikt om de maximale beloning te krijgen na een bepaalde reeks beproevingen.

Bijvoorbeeld:

Stel je een online advertentieproef voor waarbij een adverteerder de klikfrequentie van drie verschillende advertenties voor hetzelfde product wil meten. Wanneer een gebruiker de website bezoekt, toont de adverteerder willekeurig een advertentie. Vervolgens houdt de adverteerder in de gaten of de gebruiker op de advertentie klikt of niet. Na een tijdje merkt de adverteerder dat de ene advertentie beter lijkt te werken dan de andere. De adverteerder moet nu beslissen tussen vasthouden aan de best presterende advertentie of doorgaan met het gerandomiseerde onderzoek.
Als de adverteerder slechts één advertentie weergeeft, kan hij geen gegevens meer verzamelen over de andere twee advertenties. Misschien is een van de andere advertenties beter, maar door toeval lijkt deze alleen maar slechter. Als de andere twee advertenties slechter zijn, kan het voortzetten van het onderzoek de klikfrequentie negatief beïnvloeden. Deze reclameproef is een voorbeeld van besluitvorming onder onzekerheid.
In het bovenstaande voorbeeld wordt de rol van de agent gespeeld door een adverteerder. De adverteerder moet kiezen tussen drie verschillende acties om de eerste, tweede of derde advertentie weer te geven. Elke advertentie is een actie. Het kiezen van die advertentie levert een onbekende beloning op. Ten slotte is de winst van de adverteerder na de advertentie de beloning die de adverteerder ontvangt.

Actiewaarden:

Om ervoor te zorgen dat de adverteerder kan beslissen welke actie het beste is, moeten we de waarde van elke actie definiëren. We definiëren deze waarden met behulp van de actiewaardefunctie en gebruiken de taal van waarschijnlijkheid. De waarde van het selecteren van een actie Q _* (A) wordt gedefinieerd als de verwachte beloning R _T die we ontvangen als we een actie ondernemen A uit de mogelijke reeks acties.

Het doel van de agent is om de verwachte beloning te maximaliseren door de actie te selecteren met de hoogste actiewaarde.

Schatting van de actiewaarde:

Omdat de waarde van het selecteren van een actie, d.w.z. Q _* (A) is niet bekend bij de agent, daarom zullen we de steekproefgemiddelde methode om dit te schatten.

Verkenning versus exploitatie:

Hebzuchtige actie: wanneer een agent een actie kiest die momenteel de grootste geschatte waarde heeft. De agent exploiteert zijn huidige kennis door de hebzuchtige actie te kiezen. Niet-hebzuchtige actie: wanneer de agent niet de grootste geschatte waarde kiest en een onmiddellijke beloning opoffert in de hoop meer informatie over de andere acties te krijgen. Verkenning: Hiermee kan de agent zijn kennis over elke actie verbeteren. Hopelijk leidt dit tot een voordeel op de lange termijn. Uitbuiting: Hiermee kan de agent de hebzuchtige actie kiezen om te proberen de meeste beloning te krijgen voor voordeel op de korte termijn. Een pure hebzuchtige actieselectie kan leiden tot suboptimaal gedrag.

Er ontstaat een dilemma tussen exploratie en exploitatie, omdat een agent er niet voor kan kiezen om tegelijkertijd te verkennen en te exploiteren. Daarom gebruiken wij de Bovenste vertrouwensgrens algoritme om het exploratie-exploitatie dilemma op te lossen

Hoger vertrouwen gebonden actieselectie:
Upper-Confidence Bound actieselectie maakt gebruik van onzekerheid in de actiewaardeschattingen om exploratie en exploitatie in evenwicht te brengen. Omdat er inherente onzekerheid zit in de nauwkeurigheid van de schattingen van de actiewaarde wanneer we een steekproef van beloningen gebruiken, gebruikt UCB onzekerheid in de schattingen om exploratie te stimuleren.

Q _T (A) hier staat de huidige schatting voor actie A op tijd T . We selecteren de actie met de hoogste geschatte actiewaarde plus de verkenningsterm die het hoogste vertrouwen biedt.

Vraag(A) in de bovenstaande afbeelding vertegenwoordigt de huidige schatting van de actiewaarde voor actie A . De haakjes vertegenwoordigen een betrouwbaarheidsinterval rond Q _* (A) wat zegt dat we er zeker van zijn dat de werkelijke actiewaarde van actie is A ligt ergens in deze regio.

De onderste beugel wordt de ondergrens genoemd en de bovenste beugel de bovengrens. Het gebied tussen de haakjes is het betrouwbaarheidsinterval dat de onzekerheid in de schattingen weergeeft. Als de regio erg klein is, worden we er zeer zeker van dat de werkelijke waarde van actie A ligt in de buurt van onze geschatte waarde. Aan de andere kant, als de regio groot is, worden we onzeker over de waarde van actie A ligt in de buurt van onze geschatte waarde.

De Bovenste vertrouwensgrens volgt het principe van optimisme in het licht van onzekerheid, wat inhoudt dat als we onzeker zijn over een actie, we optimistisch moeten aannemen dat dit de juiste actie is.

Laten we bijvoorbeeld zeggen dat we deze vier acties met bijbehorende onzekerheden in de onderstaande afbeelding hebben, onze agent heeft geen idee welke de beste actie is. Dus volgens het UCB-algoritme zal het optimistisch de actie kiezen die de hoogste bovengrens heeft, d.w.z. A . Door dit te doen zal het óf de hoogste waarde hebben en de hoogste beloning krijgen, óf door dat te doen leren we over een actie waar we het minst van weten.

Laten we aannemen dat na het selecteren van de actie A we komen terecht in een toestand zoals weergegeven in de onderstaande afbeelding. Deze keer selecteert UCB de actie B sinds Q(B) heeft de hoogste bovengrens voor het vertrouwen, omdat de schatting van de actiewaarde het hoogst is, ook al is het betrouwbaarheidsinterval klein.

In eerste instantie doet UCB meer onderzoek om de onzekerheid systematisch te verminderen, maar het onderzoek neemt in de loop van de tijd af. We kunnen dus zeggen dat UCB gemiddeld een grotere beloning krijgt dan andere algoritmen zoals Epsilon-greedy, Optimistic Initial Values, enz.