Nell'apprendimento per rinforzo, l'agente o il decisore genera i propri dati di formazione interagendo con il mondo. L'agente deve apprendere le conseguenze delle sue azioni attraverso tentativi ed errori, piuttosto che sentirsi dire esplicitamente l'azione corretta.

Problema dei banditi multi-armati

Nell'apprendimento per rinforzo, utilizziamo il problema dei banditi multi-armati per formalizzare la nozione di processo decisionale in condizioni di incertezza utilizzando i banditi armati di k. Un decisore o un agente è presente in Multi-Armed Bandit Problem per scegliere tra k-diverse azioni e riceve una ricompensa in base all'azione che sceglie. Il problema del bandito viene utilizzato per descrivere concetti fondamentali nell'apprendimento per rinforzo, come ricompense, tempi e valori.

L'immagine sopra rappresenta una slot machine detta anche bandito a due leve. Assumiamo che ciascuna leva abbia una distribuzione separata dei premi e che ci sia almeno una leva che genera la massima ricompensa.

La distribuzione di probabilità della ricompensa corrispondente a ciascuna leva è diversa ed è sconosciuta al giocatore (decisore). Quindi, l’obiettivo qui è identificare quale leva premere per ottenere la massima ricompensa dopo una determinata serie di prove.

Per esempio:

Immagina una prova pubblicitaria online in cui un inserzionista desidera misurare la percentuale di clic di tre diversi annunci per lo stesso prodotto. Ogni volta che un utente visita il sito Web, l'inserzionista visualizza un annuncio in modo casuale. L'inserzionista monitora quindi se l'utente fa clic o meno sull'annuncio. Dopo un po', l'inserzionista nota che un annuncio sembra funzionare meglio degli altri. L'inserzionista deve ora decidere se restare con l'annuncio con il rendimento migliore o continuare con lo studio randomizzato.
Se l'inserzionista visualizza solo un annuncio, non potrà più raccogliere dati sugli altri due annunci. Forse uno degli altri annunci è migliore, solo per caso sembra peggiore. Se gli altri due annunci sono peggiori, continuare lo studio può influire negativamente sulla percentuale di clic. Questo esperimento pubblicitario esemplifica il processo decisionale in condizioni di incertezza.
Nell'esempio sopra, il ruolo dell'agente è svolto da un inserzionista. L'inserzionista deve scegliere tra tre diverse azioni, per visualizzare il primo, il secondo o il terzo annuncio. Ogni annuncio è un'azione. La scelta di quell'annuncio produce una ricompensa sconosciuta. Infine, il profitto dell'inserzionista dopo l'annuncio è la ricompensa che riceve l'inserzionista.

Valori di azione:

Affinché l'inserzionista possa decidere quale sia l'azione migliore, dobbiamo definire il valore di ciascuna azione. Definiamo questi valori utilizzando la funzione valore-azione utilizzando il linguaggio della probabilità. Il valore della selezione di un'azione Q_*(UN) è definita come la ricompensa attesa R_T riceviamo quando compiamo un'azione UN dal possibile insieme di azioni.

L'obiettivo dell'agente è massimizzare la ricompensa attesa selezionando l'azione che ha il valore di azione più alto.

Stima del valore dell'azione:

np.dove

Poiché il valore della selezione di un'azione, ad es. Q_*(UN) non è noto all'agente, quindi utilizzeremo il file media campionaria metodo per stimarlo.

Esplorazione vs sfruttamento:

css per allineare le immagini

Azione Greedy: quando un agente sceglie un'azione che attualmente ha il valore stimato maggiore. L'agente sfrutta la sua conoscenza attuale scegliendo l'azione avida. Azione non avida: quando l'agente non sceglie il valore stimato più grande e sacrifica la ricompensa immediata sperando di ottenere maggiori informazioni sulle altre azioni. Esplorazione: consente all'agente di migliorare la propria conoscenza di ogni azione. Si spera che porti a un beneficio a lungo termine. Sfruttamento: consente all'agente di scegliere l'azione avida per cercare di ottenere la massima ricompensa per benefici a breve termine. Una selezione di azioni puramente avide può portare a un comportamento non ottimale.

Si verifica un dilemma tra esplorazione e sfruttamento perché un agente non può scegliere di esplorare e sfruttare allo stesso tempo. Quindi, usiamo il Limite di fiducia superiore algoritmo per risolvere il dilemma esplorazione-sfruttamento

Selezione dell'azione del limite di confidenza superiore:
La selezione dell’azione con limite di confidenza superiore utilizza l’incertezza nelle stime del valore dell’azione per bilanciare esplorazione e sfruttamento. Poiché esiste un'incertezza intrinseca nell'accuratezza delle stime del valore dell'azione quando utilizziamo una serie di premi campionati, UCB utilizza l'incertezza nelle stime per guidare l'esplorazione.

Q_T(UN) qui rappresenta la stima attuale dell'azione UN alla volta T . Selezioniamo l'azione che ha il valore di azione stimato più alto più il termine di esplorazione con limite di confidenza superiore.

Q(A) nell'immagine sopra rappresenta l'attuale stima del valore dell'azione per l'azione UN . Le parentesi rappresentano un intervallo di confidenza intorno Q_*(UN) il che dice che siamo fiduciosi che l'effettivo valore dell'azione sia reale UN si trova da qualche parte in questa regione.

La parentesi inferiore è chiamata limite inferiore, mentre la parentesi superiore è il limite superiore. La regione tra parentesi è l'intervallo di confidenza che rappresenta l'incertezza nelle stime. Se la regione è molto piccola, allora diventiamo assolutamente certi dell'effettivo valore dell'azione UN è vicino al nostro valore stimato. D’altro canto, se la regione è grande, allora diventiamo incerti sul valore dell’azione UN è vicino al nostro valore stimato.

IL Limite di fiducia superiore segue il principio dell'ottimismo di fronte all'incertezza che implica che se siamo incerti su un'azione, dovremmo assumere ottimisticamente che sia l'azione corretta.

Ad esempio, supponiamo di avere queste quattro azioni con incertezze associate nell'immagine seguente, il nostro agente non ha idea di quale sia l'azione migliore. Quindi, secondo l'algoritmo UCB, sceglierà ottimisticamente l'azione che ha il limite superiore più alto, ovvero UN . In questo modo o avrà il valore più alto e otterrà la ricompensa più alta, oppure impareremo un'azione di cui sappiamo meno.

Supponiamo che dopo aver selezionato l'azione UN ci ritroviamo in uno stato rappresentato nella figura qui sotto. Questa volta sarà UCB a selezionare l'azione B Da Q(B) ha il limite superiore di confidenza più alto perché la stima del valore dell'azione è la più alta, anche se l'intervallo di confidenza è piccolo.

Inizialmente, UCB esplora di più per ridurre sistematicamente l’incertezza, ma la sua esplorazione si riduce nel tempo. Quindi possiamo dire che UCB ottiene in media una ricompensa maggiore rispetto ad altri algoritmi come Epsilon-greedy, Optimistic Initial Values, ecc.