I Reinforcement learning genererer agenten eller beslutningstageren sine træningsdata ved at interagere med verden. Agenten skal lære konsekvenserne af sine handlinger gennem forsøg og fejl, i stedet for at blive eksplicit fortalt den korrekte handling.

Multi-Armed Bandit Problem

I Reinforcement Learning bruger vi Multi-Armed Bandit Problem til at formalisere forestillingen om beslutningstagning under usikkerhed ved hjælp af k-armede banditter. En beslutningstager eller agent er til stede i Multi-Armed Bandit Problem for at vælge mellem k-forskellige handlinger og modtager en belønning baseret på den handling, den vælger. Banditproblem bruges til at beskrive grundlæggende begreber i forstærkende læring, såsom belønninger, tidstrin og værdier.

Billedet ovenfor repræsenterer en spilleautomat også kendt som en bandit med to håndtag. Vi antager, at hvert håndtag har en separat fordeling af belønninger, og der er mindst én håndtag, der genererer maksimal belønning.

Sandsynlighedsfordelingen for belønningen svarende til hver håndtag er forskellig og er ukendt for spilleren (beslutningstageren). Derfor er målet her at identificere, hvilken håndtag der skal trækkes for at få den maksimale belønning efter et givet sæt forsøg.

For eksempel:

Forestil dig en online annonceringsprøve, hvor en annoncør ønsker at måle klikraten for tre forskellige annoncer for det samme produkt. Når en bruger besøger hjemmesiden, viser annoncøren en annonce tilfældigt. Annoncøren overvåger derefter, om brugeren klikker på annoncen eller ej. Efter et stykke tid bemærker annoncøren, at en annonce ser ud til at fungere bedre end de andre. Annoncøren skal nu vælge mellem at holde fast i den bedst ydende annonce eller fortsætte med den randomiserede undersøgelse.
Hvis annoncøren kun viser én annonce, kan han ikke længere indsamle data om de to andre annoncer. Måske er en af ​​de andre annoncer bedre, den fremstår kun værre på grund af tilfældigheder. Hvis de to andre annoncer er værre, kan en fortsættelse af undersøgelsen påvirke klikraten negativt. Dette reklameforsøg eksemplificerer beslutningstagning under usikkerhed.
I ovenstående eksempel spilles agentens rolle af en annoncør. Annoncøren skal vælge mellem tre forskellige handlinger for at vise den første, anden eller tredje annonce. Hver annonce er en handling. At vælge den annonce giver en ukendt belønning. Endelig er annoncørens fortjeneste efter annoncen den belønning, som annoncøren modtager.

Handlingsværdier:

For at annoncøren kan beslutte, hvilken handling der er bedst, skal vi definere værdien af ​​at udføre hver handling. Vi definerer disse værdier ved hjælp af handling-værdi-funktionen ved hjælp af sandsynlighedssproget. Værdien af ​​at vælge en handling q_*(en) defineres som den forventede belønning R_t vi modtager, når vi foretager en handling -en fra det mulige sæt af handlinger.

Agentens mål er at maksimere den forventede belønning ved at vælge den handling, der har den højeste handlingsværdi.

Handlingsværdiestimat:

fjerner sidste commit git

Da værdien af ​​at vælge en handling dvs. Q_*(en) er ikke kendt af agenten, så vi vil bruge stikprøvegennemsnit metode til at vurdere det.

Udforskning vs udnyttelse:

Grådig handling : Når en agent vælger en handling, der i øjeblikket har den største estimerede værdi. Agenten udnytter sin nuværende viden ved at vælge den grådige handling. Ikke-grådig handling: Når agenten ikke vælger den største estimerede værdi og ofrer øjeblikkelig belønning i håb om at få mere information om de andre handlinger. Udforskning: Det giver agenten mulighed for at forbedre sin viden om hver handling. Forhåbentlig fører til en langsigtet fordel. Udnyttelse : Det giver agenten mulighed for at vælge den grådige handling for at forsøge at få den største belønning for kortsigtede fordele. En ren grådig handlingsudvælgelse kan føre til suboptimal adfærd.

Et dilemma opstår mellem udforskning og udnyttelse, fordi en agent ikke kan vælge både at udforske og udnytte på samme tid. Derfor bruger vi Øvre tillidsgrænse algoritme til at løse udforskning-udnyttelsesdilemmaet

Øvre tillidsgrænse handlingsvalg:
Øvre tillidsbundet handlingsvalg bruger usikkerhed i handlingsværdiestimaterne til at balancere udforskning og udnyttelse. Da der er en iboende usikkerhed i nøjagtigheden af ​​aktionsværdiestimaterne, når vi bruger et stikprøvesæt af belønninger, bruger UCB derfor usikkerhed i estimaterne til at drive udforskning.

Q_t(en) her repræsenterer det aktuelle estimat for handling -en på tidspunktet t . Vi vælger den handling, der har den højeste estimerede handlingsværdi plus den øvre konfidensbundne udforskningsterm.

Q(A) i ovenstående billede repræsenterer det aktuelle handlingsværdiestimat for handling EN . Klammerne repræsenterer et konfidensinterval omkring Q_*(EN) hvilket siger, at vi er sikre på, at den faktiske handling-værdi af handling EN ligger et sted i denne region.

Den nederste parentes kaldes den nedre grænse, og den øverste parentes er den øvre grænse. Området mellem parenteserne er konfidensintervallet, som repræsenterer usikkerheden i estimaterne. Hvis regionen er meget lille, så bliver vi meget sikre på, at den faktiske værdi af handling EN er tæt på vores anslåede værdi. På den anden side, hvis regionen er stor, så bliver vi usikre på, at værdien af ​​handling EN er tæt på vores anslåede værdi.

Det Øvre tillidsgrænse følger princippet om optimisme i lyset af usikkerhed, hvilket indebærer, at hvis vi er usikre på en handling, bør vi optimistisk antage, at det er den rigtige handling.

For eksempel, lad os sige, at vi har disse fire handlinger med tilhørende usikkerheder på billedet nedenfor, vores agent har ingen idé om, hvilken der er den bedste handling. Så ifølge UCB-algoritmen vil den optimistisk vælge den handling, der har den højeste øvre grænse, dvs. EN . Ved at gøre dette vil det enten have den højeste værdi og få den højeste belønning, eller ved at tage det vil vi lære om en handling, vi ved mindst om.

np.histogram

Lad os antage det efter at have valgt handlingen EN vi ender i en tilstand afbildet på billedet nedenfor. Denne gang vil UCB vælge handlingen B siden Q(B) har den højeste øvre konfidensgrænse, fordi dens handlingsværdi-estimat er den højeste, selvom konfidensintervallet er lille.

Til at begynde med udforsker UCB mere for systematisk at reducere usikkerheden, men dets udforskning reduceres over tid. Således kan vi sige, at UCB opnår større belønning i gennemsnit end andre algoritmer såsom Epsilon-greedy, Optimistic Initial Values ​​osv.