I Reinforcement learning genererar agenten eller beslutsfattaren sina träningsdata genom att interagera med världen. Agenten måste lära sig konsekvenserna av sina handlingar genom försök och misstag, snarare än att uttryckligen få veta den korrekta åtgärden.

Flerarmad banditproblem

I Reinforcement Learning använder vi Multi-Armed Bandit Problem för att formalisera uppfattningen om beslutsfattande under osäkerhet med hjälp av k-armade banditer. En beslutsfattare eller agent är närvarande i Multi-Armed Bandit Problem för att välja mellan k-different actions och får en belöning baserat på den handling den väljer. Banditproblem används för att beskriva grundläggande begrepp inom förstärkningsinlärning, såsom belöningar, tidssteg och värderingar.

Bilden ovan föreställer en spelautomat även känd som en bandit med två spakar. Vi antar att varje spak har en separat fördelning av belöningar och det finns minst en spak som genererar maximal belöning.

Sannolikhetsfördelningen för belöningen som motsvarar varje spak är olika och är okänd för spelaren (beslutsfattaren). Därför är målet här att identifiera vilken spak som ska dras för att få maximal belöning efter en given uppsättning försök.

Till exempel:

Föreställ dig en testversion av onlineannonsering där en annonsör vill mäta klickfrekvensen för tre olika annonser för samma produkt. När en användare besöker webbplatsen visar annonsören en annons slumpmässigt. Annonsören övervakar sedan om användaren klickar på annonsen eller inte. Efter ett tag märker annonsören att en annons verkar fungera bättre än de andra. Annonsören måste nu välja mellan att hålla fast vid den annons som ger bäst resultat eller att fortsätta med den randomiserade studien.
Om annonsören bara visar en annons kan han inte längre samla in data om de andra två annonserna. Kanske är någon av de andra annonserna bättre, den ser bara sämre ut på grund av slumpen. Om de andra två annonserna är sämre kan en fortsatt undersökning påverka klickfrekvensen negativt. Denna reklamförsök exemplifierar beslutsfattande under osäkerhet.
I exemplet ovan spelas agentens roll av en annonsör. Annonsören måste välja mellan tre olika åtgärder för att visa den första, andra eller tredje annonsen. Varje annons är en åtgärd. Att välja den annonsen ger en okänd belöning. Slutligen är annonsörens vinst efter annonsen belöningen som annonsören får.

Action-Värden:

För att annonsören ska kunna bestämma vilken åtgärd som är bäst måste vi definiera värdet av att vidta varje åtgärd. Vi definierar dessa värden med hjälp av action-value-funktionen med hjälp av sannolikhetsspråket. Värdet av att välja en åtgärd q_*(a) definieras som den förväntade belöningen R_t vi får när vi vidtar en åtgärd a från den möjliga uppsättningen av åtgärder.

Målet för agenten är att maximera den förväntade belöningen genom att välja den åtgärd som har det högsta åtgärdsvärdet.

Uppskattning av åtgärdsvärde:

java regex för

Eftersom värdet av att välja en åtgärd, dvs. Q_*(a) är inte känd för agenten, så vi kommer att använda urvalsgenomsnitt metod för att uppskatta det.

Utforskning vs exploatering:

Greedy Action : När en agent väljer en åtgärd som för närvarande har det största uppskattade värdet. Agenten utnyttjar sin nuvarande kunskap genom att välja den giriga handlingen. Icke-girig handling: När agenten inte väljer det största uppskattade värdet och offrar omedelbar belöning i hopp om att få mer information om de andra åtgärderna. Utforskning: Det låter agenten förbättra sin kunskap om varje åtgärd. Förhoppningsvis leder till en långsiktig fördel. Exploatering : Det tillåter agenten att välja den giriga handlingen för att försöka få mest belöning för kortsiktiga fördelar. Ett rent girigt handlingsval kan leda till suboptimalt beteende.

Ett dilemma uppstår mellan utforskning och exploatering eftersom en agent inte kan välja att både utforska och exploatera samtidigt. Därför använder vi Övre förtroendegräns algoritm för att lösa prospekterings-exploateringsdilemmat

Val av åtgärd för övre förtroendegräns:
Upper-Confidence Bound åtgärdsval använder osäkerhet i åtgärdsvärdeskattningarna för att balansera utforskning och exploatering. Eftersom det finns en inneboende osäkerhet i åtgärdsvärdesskattningarnas noggrannhet när vi använder en samplad uppsättning belöningar, så använder UCB osäkerhet i uppskattningarna för att driva utforskningen.

Q_t(a) här representerar den aktuella uppskattningen för åtgärder a vid tidpunkten t . Vi väljer den åtgärd som har det högsta uppskattade åtgärdsvärdet plus den övre konfidensgränsen utforskningstermen.

Q(A) i bilden ovan representerar den aktuella åtgärdsvärdeskattningen för åtgärd A . Hakparenteserna representerar ett konfidensintervall runt Q_*(A) vilket säger att vi är övertygade om att handlingens faktiska handlingsvärde A ligger någonstans i denna region.

Den nedre parentesen kallas den nedre gränsen och den övre parentesen är den övre gränsen. Området mellan parenteserna är det konfidensintervall som representerar osäkerheten i skattningarna. Om regionen är mycket liten, då vi blir mycket säkra på att det faktiska värdet av åtgärder A är nära vårt uppskattade värde. Å andra sidan, om regionen är stor, då blir vi osäkra på att värdet av handling A är nära vårt uppskattade värde.

De Övre förtroendegräns följer principen om optimism inför osäkerhet som innebär att om vi är osäkra på en handling, bör vi optimistiskt anta att det är den korrekta handlingen.

Låt oss till exempel säga att vi har dessa fyra åtgärder med tillhörande osäkerheter på bilden nedan, vår agent har ingen aning om vilken som är den bästa åtgärden. Så enligt UCB-algoritmen kommer den optimistiskt att välja den åtgärd som har den högsta övre gränsen, dvs. A . Genom att göra detta kommer det antingen att ha det högsta värdet och få den högsta belöningen, eller genom att ta det kommer vi att få lära oss om en handling vi vet minst om.

bubbelsortering i algoritm

Låt oss anta det efter att ha valt åtgärden A vi hamnar i ett tillstånd som avbildas på bilden nedan. Den här gången väljer UCB åtgärden B eftersom Q(B) har den högsta övre konfidensgränsen eftersom dess uppskattning av handlingsvärde är den högsta, även om konfidensintervallet är litet.

Inledningsvis utforskar UCB mer för att systematiskt minska osäkerheten men dess utforskning minskar med tiden. Således kan vi säga att UCB erhåller större belöning i genomsnitt än andra algoritmer som Epsilon-greedy, Optimistic Initial Values, etc.