În învățarea prin întărire, agentul sau factorul de decizie își generează datele de formare interacționând cu lumea. Agentul trebuie să învețe consecințele acțiunilor sale prin încercare și eroare, mai degrabă decât să i se spună în mod explicit acțiunea corectă.

Problemă cu bandiți multi-armate

În Reinforcement Learning, folosim Multi-Armed Bandit Problem pentru a oficializa noțiunea de luare a deciziilor în condiții de incertitudine folosind bandiți k-armate. Un factor de decizie sau un agent este prezent în Multi-Armed Bandit Problem pentru a alege între k-acțiuni diferite și primește o recompensă în funcție de acțiunea pe care o alege. Problema bandit este folosită pentru a descrie concepte fundamentale în învățarea prin întărire, cum ar fi recompense, pași de timp și valori.

Imaginea de mai sus reprezintă o mașină de slot cunoscută și sub numele de bandit cu două pârghii. Presupunem că fiecare pârghie are o distribuție separată a recompenselor și că există cel puțin o pârghie care generează recompensă maximă.

Distribuția probabilității pentru recompensa corespunzătoare fiecărei pârghii este diferită și este necunoscută jucătorului de noroc (decisor). Prin urmare, scopul aici este de a identifica ce pârghie să trageți pentru a obține recompensa maximă după un anumit set de încercări.

De exemplu:

Imaginați-vă o încercare de publicitate online în care un agent de publicitate dorește să măsoare rata de clic a trei anunțuri diferite pentru același produs. Ori de câte ori un utilizator vizitează site-ul web, agentul de publicitate afișează un anunț la întâmplare. Agentul de publicitate monitorizează apoi dacă utilizatorul face clic pe anunț sau nu. După un timp, agentul de publicitate observă că un anunț pare să funcționeze mai bine decât celelalte. Agentul de publicitate trebuie să decidă acum între a rămâne cu anunțul cu cea mai bună performanță sau a continua cu studiul randomizat.
Dacă agentul de publicitate afișează doar un anunț, atunci nu mai poate colecta date despre celelalte două anunțuri. Poate că una dintre celelalte reclame este mai bună, pare doar mai proastă din cauza întâmplării. Dacă celelalte două reclame sunt mai proaste, atunci continuarea studiului poate afecta negativ rata de clic. Acest proces de publicitate exemplifică luarea deciziilor în condiții de incertitudine.
În exemplul de mai sus, rolul agentului este jucat de un agent de publicitate. Agentul de publicitate trebuie să aleagă între trei acțiuni diferite, pentru a afișa primul, al doilea sau al treilea anunț. Fiecare reclamă este o acțiune. Alegerea anunțului aduce o recompensă necunoscută. În cele din urmă, profitul agentului de publicitate după anunț este recompensa pe care o primește agentul de publicitate.

Valori de acțiune:

Pentru ca agentul de publicitate să decidă care acțiune este cea mai bună, trebuie să definim valoarea fiecărei acțiuni. Definim aceste valori folosind funcția acțiune-valoare folosind limbajul probabilității. Valoarea selectării unei acțiuni q_*(A) este definită ca recompensa așteptată R_t primim atunci când luăm o acțiune A din setul posibil de acţiuni.

Scopul agentului este de a maximiza recompensa așteptată prin selectarea acțiunii care are cea mai mare valoare-acțiune.

Estimarea valorii acțiunii:

masa din latex

Deoarece valoarea selectării unei acțiuni i.e. Q_*(A) nu este cunoscut de agent, așa că vom folosi eșantion-medie metoda de estimare a acesteia.

Explorare vs exploatare:

Greedy Action: Când un agent alege o acțiune care are în prezent cea mai mare valoare estimată. Agentul își exploatează cunoștințele actuale alegând acțiunea lacomă. Acțiune non-lacomă: atunci când agentul nu alege cea mai mare valoare estimată și sacrifică recompensa imediată în speranța de a obține mai multe informații despre celelalte acțiuni. Explorare: permite agentului să-și îmbunătățească cunoștințele despre fiecare acțiune. Sperăm că va duce la un beneficiu pe termen lung. Exploatarea: permite agentului să aleagă acțiunea lacomă pentru a încerca să obțină cea mai mare recompensă pentru beneficii pe termen scurt. O selecție pură de acțiune lacomă poate duce la un comportament suboptim.

Apare o dilemă între explorare și exploatare, deoarece un agent nu poate alege să exploreze și să exploateze în același timp. Prin urmare, folosim Limita superioară a încrederii algoritm pentru a rezolva dilema explorare-exploatare

Selectarea acțiunii cu limitele superioare de încredere:
Selecția acțiunii Upper-Confidence Bound folosește incertitudinea în estimările acțiunii-valoare pentru echilibrarea explorării și exploatării. Deoarece există o incertitudine inerentă în acuratețea estimărilor acțiunii-valoare atunci când folosim un set eșantionat de recompense, astfel UCB folosește incertitudinea în estimări pentru a conduce explorarea.

Q_t(A) aici reprezintă estimarea curentă pentru acțiune A la timp t . Selectăm acțiunea care are cea mai mare valoare estimată a acțiunii plus termenul de explorare al limitei superioare de încredere.

Î(A) în imaginea de mai sus reprezintă estimarea actuală acțiune-valoare pentru acțiune A . Parantezele reprezintă un interval de încredere în jur Q_*(A) care spune că suntem încrezători că acţiunea-valoarea reală a acţiunii A se află undeva în această regiune.

Paranteza inferioară este numită limită inferioară, iar paranteza superioară este limita superioară. Regiunea dintre paranteze este intervalul de încredere care reprezintă incertitudinea estimărilor. Dacă regiunea este foarte mică, atunci devenim foarte siguri că valoarea reală a acțiunii A este aproape de valoarea noastră estimată. Pe de altă parte, dacă regiunea este mare, atunci devenim nesiguri că valoarea acțiunii A este aproape de valoarea noastră estimată.

The Limita superioară a încrederii urmează principiul optimismului în fața incertitudinii care implică că, dacă suntem nesiguri cu privire la o acțiune, ar trebui să presupunem cu optimism că aceasta este acțiunea corectă.

De exemplu, să presupunem că avem aceste patru acțiuni cu incertitudini asociate în imaginea de mai jos, agentul nostru nu are idee care este cea mai bună acțiune. Deci, conform algoritmului UCB, va alege în mod optimist acțiunea care are cea mai mare limită superioară, de exemplu. A . Făcând acest lucru, fie va avea cea mai mare valoare și va primi cea mai mare recompensă, fie luând asta vom ajunge să învățăm despre o acțiune despre care știm cel mai puțin.

Să presupunem că după selectarea acțiunii A ajungem într-o stare descrisă în imaginea de mai jos. De data aceasta, UCB va selecta acțiunea B de cand Q(B) are cea mai mare limită superioară de încredere, deoarece estimarea valorii acțiunii este cea mai mare, chiar dacă intervalul de încredere este mic.

Css alinierea imaginilor

Inițial, UCB explorează mai mult pentru a reduce în mod sistematic incertitudinea, dar explorarea sa se reduce în timp. Astfel, putem spune că UCB obține o recompensă mai mare în medie decât alți algoritmi precum Epsilon-greedy, Optimistic Initial Values ​​etc.