În matematică , mai exact în teoria probabilității , problema banditului cu un singur braț (generalizabilă pentru problema banditului cu brațul K sau problema banditului cu brațul N ) este exprimată pictural după cum urmează: un utilizator (un agent ), care se confruntă cu sloturile, trebuie să decidă ce mașini să joace. Fiecare mașină oferă o recompensă medie pe care utilizatorul nu o cunoaște a priori. Scopul este de a maximiza câștigul cumulativ al utilizatorului.
Acesta este un exemplu de învățare prin întărire . De obicei, politica utilizatorului oscilează între exploatare (folosind mașina pe care a învățat-o o mulțime de recompense) și explorare (testarea unei alte mașini pentru a spera să câștige mai mult). Problema banditului cu un singur braț poate fi văzută ca un proces de decizie markovian cu un singur stat.
În această secțiune, formalizăm problema prin preluarea unor notații din articolul lui Auer și colab..
Luați în considerare K slot machines. Intrarea problemei este dată de variabilele aleatoare X i, n pentru toate 1 ≤ i ≤ K și n ≥ 1, unde indicele i reprezintă una dintre mașinile K (sau un „braț” al banditului) și indicele n reprezintă o rotație. Presupunem că toate aceste variabile aleatoare sunt independente și că variabilele aceleiași mașini i, adică variabilele X i, 1 , X i, 2 etc., urmând aceeași distribuție a probabilității necunoscute a agent, așteptare μ i .
La rândul său, utilizatorul va primi o recompensă care depinde de mașina pe care o alege. Un exemplu clasic de bandit cu un singur braț este cazul în care mașina i aduce o recompensă de 1 cu probabilitatea p i și 0 cu probabilitatea 1-p i .
Utilizatorul încearcă să găsească slotul care aduce cea mai mare recompensă medie. O politică sau strategie pentru problema pinguinului este un algoritm care alege următoarea mașină de jucat, pe baza alegerilor anterioare și a recompenselor obținute. Scopul este de a oferi politici care să minimizeze regretul , adică suma care exprimă ceea ce a pierdut politica în legătură cu alegerea celui mai bun aparat.
Într-o problemă de bandit cu un singur braț, regretul după n încercări este definit ca diferența dintre recompensa pe care ar obține-o folosind de n ori cea mai bună mașină și așteptarea recompensei după n încercări efectuate în conformitate cu politica. În mod formal, acest regret merită:
unde este recompensa medie a celei mai bune mașini și desemnează recompensa care se obține cu strategia propusă în acest moment .
Prin urmare, au fost propuși algoritmi de învățare a întăririi pentru a rezolva problema banditului cu un singur braț.
Algoritmul bandit își ia numele de la slot machines ( bandit multi-armat ) împotriva cărora jucătorul încearcă să-și maximizeze câștigul. Au fost introduse în anii 1960 pentru aplicații în studiile clinice.
Principiul unui algoritm de bandit poate fi definit astfel: avem 2 surse A și B (având respectiv o probabilitate pA și pB de a fi satisfăcătoare atunci când este utilizat) și vrem să determinăm care dintre cele două este cea mai eficientă.
O abordare lacomă este doar a mea, nu a explora. Astfel, calculăm valoarea unui braț a unei mașini (are pentru acțiune) după cum urmează:
Alegerea lacomă constă în alegerea uneia dintre acțiunile care maximizează . Cu această abordare, optimul nu este atins. Arătăm că politica calculată este îmbunătățită dacă agentul alege o acțiune arbitrară cu o probabilitate ε> 0. Următorul algoritm este un algoritm simplu pentru problema banditului cu un singur braț, pe care îl numim ε-lacom.
initialiser pour tout bras a: Q(a) := 0 N(a) := 0 boucle pour toujours: avec une probabilité ε: a := un bras au hasard sinon: a := une action qui maximise Q(a) R := récompense obtenue en tirant a N(a) := N(a) + 1 Q(a) := Q(a) + (R - Q(a)) / N(a)Stocăm valoarea curentă a în Q (a).
Tze Leung Lai și Herbert Robbins a dat algoritmi de armare de învățare permit obținerea unui regret mărginit de o funcție logaritm pentru anumite familii de distribuție de probabilitate pentru premii: . Cu alte cuvinte, înseamnă că mașina optimă este redată exponențial mai des decât alte mașini.
Algoritmul de eșantionare Thompson este primul care a fost propus pentru a rezolva această problemă.
De fiecare dată, utilizatorul alege mașina cu cel mai mare index. Acest indice fiind o variabilă aleatorie care urmează o lege beta . Pentru fiecare mașină, utilizatorul desenează un index conform unei legi beta ai cărei parametri și sunt inițializați la 1. De fiecare dată când utilizatorul folosește una dintre mașini, dacă obține recompensa și altfel.
Algoritmul UCB (pentru limitele de încredere superioară ) a fost propus de P. Auer în 2002. Cu acest algoritm, utilizatorul calculează media empirică a recompensei pentru fiecare dintre mașini.
În această ecuație, desemnează numărul de teste efectuate de utilizator, numărul de teste efectuate de utilizator pe mașină , desemnează recompensa obținută în timpul testului . desemnează funcția indicator care indică faptul că mașina a fost selectată pentru testare .
Pentru a calcula indicele din fiecare canal, adăugăm o părtinire care permite algoritmului să exploreze diferitele mașini.
Tendința trebuie aleasă pentru a avea o scădere logaritmică a regretului. Particularitatea:
permite limitarea regretului într-un mod logaritmic.
Există multe îmbunătățiri ale acestui algoritm.
Cea mai tipică aplicație a problemei banditului cu un singur braț este aceea de a alege între o doză veche și nouă de vaccin sau medicament (sau între două diferite): este necesar să se determine cât de repede posibil dacă noul produs ar trebui adoptat sau a întreținut cel vechi. Orice eroare ar duce la pierderea vieții umane (sau, cel puțin, la persoanele care suferă de probleme care rezultă fie din tratament incomplet, fie din reacții adverse excesive). Din acest motiv, nu putem folosi protocoale statistice clasice ( Fisher ), optime atunci când colectarea informațiilor este ieftină și prelucrarea lor costisitoare și tindem mai degrabă la o proiectare a experimentului folosind metode bayesiene care folosesc informațiile pe măsură ce curg.
Acest model este uneori folosit în învățarea automată , de exemplu pentru a face alegeri publicitare pentru a prezenta pe baza a ceea ce este deja cunoscut, cu excepția faptului că refuzul de a face clic pe un link publicitar în sine oferă informații utilizabile.
În radioul inteligent , acest model este adesea utilizat pentru luarea deciziilor pentru acces oportunist la spectru.