I forsterkningslæring genererer agenten eller beslutningstakeren sine treningsdata ved å samhandle med verden. Agenten må lære konsekvensene av sine handlinger gjennom prøving og feiling, i stedet for å bli eksplisitt fortalt den riktige handlingen.

Problem med flerarmede banditter

I Reinforcement Learning bruker vi Multi-Armed Bandit Problem for å formalisere forestillingen om beslutningstaking under usikkerhet ved å bruke k-armede banditter. En beslutningstaker eller agent er til stede i Multi-Armed Bandit Problem for å velge mellom k-forskjellige handlinger og mottar en belønning basert på handlingen den velger. Banditproblem brukes til å beskrive grunnleggende konsepter i forsterkende læring, som belønning, tidstrinn og verdier.

Bildet ovenfor representerer en spilleautomat også kjent som en banditt med to spaker. Vi antar at hver spak har en separat fordeling av belønninger og det er minst én spak som genererer maksimal belønning.

Sannsynlighetsfordelingen for belønningen som tilsvarer hver spak er forskjellig og er ukjent for spilleren (beslutningstakeren). Derfor er målet her å identifisere hvilken spak du skal trekke for å få maksimal belønning etter et gitt sett med forsøk.

For eksempel:

Tenk deg en prøveversjon på nettannonsering der en annonsør ønsker å måle klikkfrekvensen til tre forskjellige annonser for samme produkt. Når en bruker besøker nettstedet, viser annonsøren en tilfeldig annonse. Annonsøren overvåker deretter om brukeren klikker på annonsen eller ikke. Etter en stund merker annonsøren at en annonse ser ut til å fungere bedre enn de andre. Annonsøren må nå velge mellom å holde seg til den annonsen som gir best resultater eller å fortsette med den randomiserte studien.
Hvis annonsøren bare viser én annonse, kan han ikke lenger samle inn data om de to andre annonsene. Kanskje en av de andre annonsene er bedre, den ser bare dårligere ut på grunn av tilfeldigheter. Hvis de to andre annonsene er dårligere, kan det å fortsette studien påvirke klikkfrekvensen negativt. Denne reklameprøven eksemplifiserer beslutningstaking under usikkerhet.
I eksemplet ovenfor spilles rollen som agent av en annonsør. Annonsøren må velge mellom tre forskjellige handlinger for å vise den første, andre eller tredje annonsen. Hver annonse er en handling. Å velge den annonsen gir en ukjent belønning. Til slutt er fortjenesten til annonsøren etter annonsen belønningen som annonsøren mottar.

Handlingsverdier:

For at annonsøren skal avgjøre hvilken handling som er best, må vi definere verdien av å utføre hver handling. Vi definerer disse verdiene ved å bruke handlingsverdi-funksjonen ved å bruke sannsynlighetsspråket. Verdien av å velge en handling q_*(en) er definert som forventet belønning R_t vi mottar når vi gjør en handling en fra det mulige settet av handlinger.

Målet til agenten er å maksimere den forventede belønningen ved å velge handlingen som har høyest handlingsverdi.

Handlingsverdiestimat:

k klyngealgoritme

Siden verdien av å velge en handling, dvs. Q_*(en) er ikke kjent for agenten, så vi vil bruke utvalgsgjennomsnitt metode for å anslå det.

Utforskning vs utnyttelse:

Grådig handling : Når en agent velger en handling som for øyeblikket har den største estimerte verdien. Agenten utnytter sin nåværende kunnskap ved å velge den grådige handlingen. Ikke-grådig handling: Når agenten ikke velger den største estimerte verdien og ofrer umiddelbar belønning i håp om å få mer informasjon om de andre handlingene. Utforskning: Det lar agenten forbedre kunnskapen sin om hver handling. Forhåpentligvis fører til en langsiktig fordel. Utnyttelse : Det lar agenten velge den grådige handlingen for å prøve å få mest mulig belønning for kortsiktig fordel. Et rent grådig handlingsvalg kan føre til suboptimal oppførsel.

Et dilemma oppstår mellom leting og utnyttelse fordi en agent ikke kan velge å både utforske og utnytte på samme tid. Derfor bruker vi Øvre tillitsgrense algoritme for å løse leting-utnyttelse-dilemmaet

Øvre tillitsgrense handlingsvalg:
Øvre tillitsgrense handlingsvalg bruker usikkerhet i handlingsverdiestimatene for å balansere leting og utnyttelse. Siden det er iboende usikkerhet i nøyaktigheten av handlingsverdi-estimatene når vi bruker et utvalgt sett med belønninger, bruker UCB derfor usikkerhet i estimatene for å drive leting.

Q_t(en) her representerer gjeldende anslag for handling en på tidspunktet t . Vi velger handlingen som har den høyeste estimerte handlingsverdien pluss den øvre konfidensgrense utforskningstermen.

Q(A) i bildet ovenfor representerer gjeldende handlingsverdiestimat for handling EN . Klammerne representerer et konfidensintervall rundt Q_*(EN) som sier at vi er sikre på at den faktiske handling-verdien av handling EN ligger et sted i denne regionen.

Den nedre parentesen kalles den nedre grensen, og den øvre parentesen er den øvre grensen. Området mellom parentesene er konfidensintervallet som representerer usikkerheten i estimatene. Hvis regionen er veldig liten, så blir vi veldig sikre på at den faktiske verdien av handling EN er nær vår estimerte verdi. På den annen side, hvis regionen er stor, så blir vi usikre på at verdien av handling EN er nær vår estimerte verdi.

De Øvre tillitsgrense følger prinsippet om optimisme i møte med usikkerhet som innebærer at hvis vi er usikre på en handling, bør vi optimistisk anta at det er den riktige handlingen.

La oss for eksempel si at vi har disse fire handlingene med tilhørende usikkerheter på bildet nedenfor, vår agent har ingen anelse om hvilken som er den beste handlingen. Så ifølge UCB-algoritmen vil den optimistisk velge handlingen som har den høyeste øvre grensen, dvs. EN . Ved å gjøre dette vil det enten ha den høyeste verdien og få den høyeste belønningen, eller ved å ta det vil vi lære om en handling vi vet minst om.

hva er kart java

La oss anta det etter å ha valgt handlingen EN vi ender opp i en tilstand som er avbildet på bildet nedenfor. Denne gangen vil UCB velge handlingen B siden Q(B) har den høyeste øvre konfidensgrensen fordi handlingsverdiestimatet er det høyeste, selv om konfidensintervallet er lite.

Til å begynne med utforsker UCB mer for å systematisk redusere usikkerhet, men letingen reduseres over tid. Dermed kan vi si at UCB oppnår større belønning i gjennomsnitt enn andre algoritmer som Epsilon-greedy, Optimistic Initial Values, etc.