Il capitolo 9 ha introdotto il linguaggio generale dei problemi di decisione sequenziale, il Processo Decisionale di Markov. Questo capitolo fa un passo indietro apparente e studia la forma più semplice possibile di problema di reinforcement learning: il multi-armed bandit (bandito a più braccia). Nel bandit non c’è stato, non ci sono conseguenze a lungo termine, non c’è delayed reward: c’è un agente che a ogni passo sceglie una tra $k$ azioni e riceve un reward. Proprio questa semplicità lo rende il laboratorio ideale per isolare e studiare in purezza il dilemma che attraversa tutto il reinforcement learning: il compromesso tra esplorazione (provare azioni per conoscerle meglio) e sfruttamento (usare ciò che si sa per guadagnare subito). Il percorso del capitolo: formalizzazione del problema e delle action-value, stima dai dati con aggiornamento incrementale, il regret come misura del costo dell’apprendimento, il fallimento della strategia greedy, l’esplorazione forzata di $\epsilon$-greedy, i valori iniziali ottimistici, l’ottimismo di fronte all’incertezza di UCB, l’approccio bayesiano del Thompson Sampling, un confronto sistematico e una sezione finale di esercizi svolti in stile esame.

Riferimenti sul testo: Sutton e Barto, Reinforcement Learning: An Introduction, capitolo 2. Materiale complementare consigliato: il corso online Fundamentals of Reinforcement Learning (Coursera); per gli approfondimenti su regret e approccio bayesiano, Lattimore e Szepesvári, Bandit Algorithms.

1. Decidere nell’incertezza: il dilemma del bandito#

1.1 Slot machine, medici e inserzionisti#

Il nome del problema viene dal gergo dei casinò: la slot machine è detta in inglese one-armed bandit, il “bandito con un braccio solo”, perché ha una leva e svuota le tasche dei giocatori. Si immagini un giocatore davanti a $k$ slot machine, ciascuna con una probabilità di vincita diversa e ignota. Il giocatore ha un budget finito di gettoni e vuole massimizzare la vincita totale. Ogni gettone speso ha un doppio valore: produce (forse) una vincita e, allo stesso tempo, produce informazione sulla macchina provata. Il dilemma è immediato: conviene continuare a giocare sulla macchina che finora ha pagato meglio, o investire gettoni sulle altre, che potrebbero rivelarsi migliori?

Lo stesso schema, decidere ripetutamente sotto incertezza ricevendo solo una valutazione delle proprie scelte, descrive molti problemi reali (le slide del corso aprono proprio così, con tre scenari: quale film raccomandare, quale trattamento somministrare, quale playlist proporre):

• trial clinici: ci sono $k$ trattamenti alternativi per una malattia e i pazienti arrivano uno alla volta; per ogni paziente si sceglie un trattamento e si osserva se funziona (reward 1) o no (reward 0); esplorare significa somministrare trattamenti di cui si sa poco, e il costo dell’esplorazione si misura in salute dei pazienti;
• pubblicità online: a ogni visita di un utente si sceglie quale tra $k$ annunci mostrare; il reward è il click; le probabilità di click dei vari annunci non sono note in anticipo;
• A/B testing e sistemi di raccomandazione: scegliere quale variante di un’interfaccia proporre, quale contenuto raccomandare, quale prezzo testare, osservando solo l’esito della variante effettivamente proposta.

In parole semplici: in tutti questi problemi si ripete tante volte la stessa scelta tra poche opzioni, si vede solo il risultato dell’opzione scelta, e non si sa in partenza quale opzione sia la migliore. Ogni tentativo serve sia a guadagnare sia a imparare, e le due cose spesso tirano in direzioni opposte.

1.2 Il problema del bandit a k braccia#

La formalizzazione è essenziale e volutamente scarna.

L’immagine mentale, presa dall’esempio guida del corso, è un medico di fronte a una fila di banditi (per esempio $k = 3$ trattamenti): a ogni passo l’agente “tira una leva” scegliendo $A_t$, e il bandito corrispondente restituisce il reward $R_t$.

Le caratteristiche distintive del problema, che lo qualificano come la forma più semplice di reinforcement learning, sono le seguenti:

• l’obiettivo è trovare la decisione (azione) ottima tra $k$ opzioni;
• la decisione ottima non dipende dal contesto: non c’è alcuno stato, la scelta migliore è sempre la stessa a ogni passo;
• il feedback è una valutazione delle decisioni prese sotto incertezza: si osserva solo il reward dell’azione scelta, mai quale fosse l’azione giusta né quanto avrebbero pagato le alternative;
• si impara per tentativi ed errori, attraverso l’interazione diretta con l’ambiente.

In parole semplici: il bandit è un reinforcement learning “senza mappa”: non c’è un mondo da attraversare né mosse che cambiano la situazione. C’è solo una scelta secca da ripetere tante volte, con l’obiettivo di capire il prima possibile quale opzione rende di più, sprecando meno tentativi possibile sulle altre.

1.3 Il bandit come caso speciale di reinforcement learning#

Rispetto al framework completo degli MDP, nel bandit mancano due ingredienti. Manca lo stato: l’ambiente si presenta identico a ogni passo, quindi non serve una policy $\pi(a \mid s)$ ma solo una regola per scegliere l’azione dato ciò che si è osservato finora. E mancano le conseguenze a lungo termine: l’azione scelta influenza solo il reward immediato, non ciò che accadrà dopo; non c’è delayed reward né problema di credit assignment. Formalmente, un bandit è un MDP con un solo stato in cui ogni azione riporta immediatamente allo stesso stato.

Ciò che resta è esattamente il nucleo che rende il reinforcement learning diverso dall’apprendimento supervisionato: il feedback valutativo, e con esso la necessità di esplorare. Nel supervisionato la risposta corretta è data; qui l’unico modo per sapere se un braccio è buono è tirarlo, pagando il costo dei tentativi. Per questo i bandit si studiano prima degli algoritmi di RL completi: le tecniche di esplorazione sviluppate qui ($\epsilon$-greedy, ottimismo, upper confidence bound) verranno riutilizzate identiche dentro gli algoritmi dei capitoli successivi.

Idea chiave: nel bandit ogni azione è contemporaneamente una giocata e un esperimento. Sfruttare significa massimizzare il guadagno della giocata; esplorare significa massimizzare il valore dell’esperimento. Tutti gli algoritmi di questo capitolo sono modi diversi di arbitrare questo conflitto.

2. Action-value: quanto vale un braccio#

2.1 Il valore di un’azione#

Se le distribuzioni dei reward fossero note, il problema sarebbe banale. La quantità rilevante di ciascun braccio è il suo reward medio.

Le slide illustrano il calcolo su tre farmaci con distribuzioni note: il primo paga $-11$ oppure $9$ con uguale probabilità, quindi $q^{*}(a_1) = 0{,}5 \cdot (-11) + 0{,}5 \cdot 9 = -1$; il secondo ha una distribuzione a campana centrata in $1$, quindi $q^{*}(a_2) = 1$; il terzo è uniforme tra $1$ e $5$, quindi $q^{*}(a_3) = 3$. Con la tabella dei valori in mano, il braccio da scegliere sarebbe sempre il terzo.

Nel trial clinico con reward binario (1 se il trattamento funziona, 0 altrimenti), $q^{*}(a)$ è semplicemente la probabilità di successo del trattamento $a$. Se un oracolo fornisse la tabella dei $q^{*}(a)$, la strategia ottima sarebbe scegliere sempre $a^{*}$: nessun apprendimento, nessun dilemma. Tutta la difficoltà nasce dal fatto che $p(r \mid a)$, e quindi $q^{*}(a)$, non è nota.

In parole semplici: ogni braccio ha un “voto vero” che nessuno conosce: quanto paga in media. Se i voti fossero scritti sulle macchine, si giocherebbe sempre quella col voto più alto e il problema non esisterebbe. Il gioco consiste nello stimare i voti tirando le leve.

2.2 La stima campionaria#

Non potendo calcolare $q^{*}(a)$, lo si stima dall’esperienza. La stima più naturale è la media campionaria dei reward ottenuti scegliendo quell’azione:

$$Q_t(a) = \frac{\text{somma dei reward ottenuti scegliendo } a \text{ prima del passo } t}{\text{numero di volte in cui } a \text{ è stata scelta prima del passo } t} = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbb{1}\left[ A_i = a \right]}{\sum_{i=1}^{t-1} \mathbb{1}\left[ A_i = a \right]}$$

dove $\mathbb{1}[\cdot]$ è la funzione indicatrice. Si indica con $N_t(a) = \sum_{i=1}^{t-1} \mathbb{1}[A_i = a]$ il numero di estrazioni del braccio $a$ prima del passo $t$; se $N_t(a) = 0$ si usa un valore di default (per esempio $Q_t(a) = 0$). Per la legge dei grandi numeri, se il braccio $a$ viene scelto infinite volte la stima converge al valore vero:

$$Q_t(a) \longrightarrow q^{*}(a) \qquad \text{per } N_t(a) \to \infty$$

C’è però un dettaglio cruciale: la qualità della stima di ciascun braccio dipende da quante volte lo si sceglie, e la scelta dipende a sua volta dalle stime. Stima e decisione sono accoppiate: un braccio mai provato ha una stima priva di significato, e resterà tale finché qualcuno non lo prova. Questo accoppiamento è il cuore del problema di esplorazione.

In parole semplici: la stima di un braccio è la media dei suoi risultati passati, e più volte lo si prova più la media è affidabile. Ma le medie guidano le scelte e le scelte alimentano le medie: se un braccio non viene mai scelto, la sua stima non migliora mai, e un errore iniziale può non venire mai corretto.

2.3 Esempio: il trial clinico a tre trattamenti#

L’esempio guida del capitolo è un trial clinico con $k = 3$ trattamenti. Il reward è 1 se il trattamento funziona sul paziente corrente, 0 altrimenti. Le probabilità di successo vere, ignote all’agente, sono

$$q^{*}(a_1) = 0{,}25, \qquad q^{*}(a_2) = 0{,}75, \qquad q^{*}(a_3) = 0{,}50$$

quindi il braccio ottimo è $a_2$. Le slide del corso sviluppano l’esecuzione paziente per paziente: ogni casella della griglia è un passo, la faccina registra l’esito del trattamento somministrato, e nella barra in basso scorre la stima corrente $Q_t(a)$ di ciascun braccio.

La tabella seguente riporta la stessa esecuzione di 12 passi in forma numerica: a ogni passo viene somministrato un trattamento (qui la sequenza di scelte è fissata a priori, in modo da provare tutti i bracci: come sceglierli bene è il tema delle prossime sezioni), si osserva il reward e si aggiorna la media campionaria del braccio scelto. Le colonne di destra riportano le stime $Q(a)$ dopo l’aggiornamento del passo (i valori $0{,}33$ e $0{,}66$ abbreviano $1/3$ e $2/3$).

Qualche verifica esplicita. Al passo 1 il braccio $a_1$ ottiene reward 1, quindi $Q(a_1) = 1/1 = 1{,}0$; al passo 2 lo stesso braccio ottiene 0 e la media scende a $1/2 = 0{,}5$. Al passo 7, terza estrazione di $a_1$ con reward 0: $Q(a_1) = 1/3 \approx 0{,}33$. Al passo 12, quarta estrazione di $a_2$ con reward 1: $Q(a_2) = 3/4 = 0{,}75$.

Due osservazioni importanti. Primo: le stime iniziali sono molto rumorose e possono essere gravemente fuorvianti; dopo il passo 2 il braccio che “sembra” migliore è $a_1$ (stima $0{,}5$), che in realtà è il peggiore. Secondo: dopo 12 passi, con 4 estrazioni per braccio, le stime in questa esecuzione coincidono con i valori veri $(0{,}25;\ 0{,}75;\ 0{,}5)$; è un caso fortunato, ma illustra la convergenza della media campionaria quando tutti i bracci vengono campionati.

2.4 Aggiornamento incrementale#

Calcolare $Q_t(a)$ dalla definizione richiederebbe di memorizzare tutti i reward passati e rifare la somma a ogni passo. C’è un modo molto più efficiente. Si consideri un singolo braccio e si indichi con $Q_n$ la stima dopo $n-1$ estrazioni di quel braccio e con $R_n$ il reward della sua $n$-esima estrazione. Allora

$$Q_{n+1} = \frac{1}{n} \sum_{i=1}^{n} R_i = \frac{1}{n} \left( R_n + \sum_{i=1}^{n-1} R_i \right) = \frac{1}{n} \left( R_n + (n-1) \, Q_n \right) = Q_n + \frac{1}{n} \left( R_n - Q_n \right)$$

La media campionaria si aggiorna quindi in modo incrementale: basta conservare, per ogni braccio, la stima corrente $Q$ e il contatore $N$, con costo di memoria costante.

Idea chiave: l’aggiornamento incrementale ha la forma generale

$$\text{NuovaStima} \leftarrow \text{VecchiaStima} + \text{PassoDiApprendimento} \cdot \left( \text{Target} - \text{VecchiaStima} \right)$$

la nuova stima è la vecchia corretta di una frazione dell’errore tra l’osservazione appena ricevuta (il target) e la stima corrente. Questo schema, con target e passi diversi, è lo scheletro di quasi tutti gli algoritmi di reinforcement learning dei capitoli successivi.

In parole semplici: per tenere aggiornata una media non serve ricordare tutti i numeri: basta la media attuale e quanti numeri la compongono. Ogni nuovo dato sposta la media verso di sé, di un passettino sempre più piccolo man mano che i dati aumentano.

2.5 Problemi non stazionari e passo costante#

Finora si è assunto che le distribuzioni dei reward siano fisse nel tempo (problema stazionario). In molti casi reali non è così: nel trial clinico, l’efficacia del terzo trattamento potrebbe cambiare nel tempo, per esempio salendo da $0{,}50$ a $0{,}80$ (una mutazione del patogeno, un cambiamento nella popolazione dei pazienti), rendendolo il nuovo braccio ottimo; nella pubblicità, le preferenze degli utenti derivano continuamente.

La media campionaria è inadatta ai problemi non stazionari: pesa tutti i reward allo stesso modo, anche quelli raccolti quando il mondo era diverso, e il suo passo di apprendimento $1/n$ tende a zero, quindi le osservazioni recenti contano sempre meno proprio quando servirebbero di più. La soluzione è sostituire il passo $1/n$ con un passo costante $\alpha \in (0, 1]$:

$$Q_{n+1} = Q_n + \alpha \left( R_n - Q_n \right)$$

Espandendo la ricorsione si scopre che cosa calcola davvero questo aggiornamento:

$$Q_{n+1} = (1 - \alpha)^n \, Q_1 + \sum_{i=1}^{n} \alpha \, (1 - \alpha)^{n-i} \, R_i$$

È una media pesata con decadimento esponenziale (exponential recency-weighted average): i pesi sommano a 1, il reward $R_i$ ha peso $\alpha (1-\alpha)^{n-i}$, che decade esponenzialmente con l’età dell’osservazione (dopo 20 passi il peso di un reward risulta moltiplicato per $(1-\alpha)^{20}$), e il valore iniziale $Q_1$ ha peso $(1-\alpha)^n$, che svanisce col tempo. Le osservazioni recenti dominano, quelle antiche vengono progressivamente dimenticate: esattamente ciò che serve per inseguire un ambiente che cambia. Il rovescio della medaglia è che con passo costante la stima non converge mai del tutto, continua a oscillare attorno al valore vero; è il prezzo della capacità di inseguimento. Il passo $1/n$ garantisce invece convergenza, ma solo in ambienti stazionari.

In parole semplici: con il passo $1/n$ la stima è una memoria perfetta che dà lo stesso peso a tutto il passato; con il passo costante è una memoria che sbiadisce, dove i ricordi vecchi contano sempre meno. La prima è ideale se il mondo non cambia mai, la seconda se il mondo cambia e conviene fidarsi soprattutto degli ultimi dati.

3. Il prezzo dell’apprendimento: il regret#

3.1 Definizione#

Per confrontare le strategie di selezione serve una misura di prestazione più fine del semplice reward accumulato. La misura standard è il regret (rimpianto): quanto reward atteso si è perso, rispetto a un oracolo che conoscesse il braccio ottimo, a causa delle scelte subottime fatte durante l’apprendimento. Nella letteratura sui bandit si usa la notazione compatta

$$\mu_i = q^{*}(a_i), \qquad \mu^{*} = \max_{i} \mu_i = q^{*}(a^{*}), \qquad \Delta_i = \mu^{*} - \mu_i$$

dove $\Delta_i$, detto gap del braccio $i$, misura quanto quel braccio è peggiore dell’ottimo ($\Delta_i = 0$ per il braccio ottimo).

Il regret ammette una decomposizione estremamente utile nei calcoli. Detto $N_T(i)$ il numero di estrazioni del braccio $i$ nei primi $T$ passi, e osservando che $\sum_t \mu_{A_t} = \sum_i \mu_i N_T(i)$ e che $T = \sum_i N_T(i)$:

il regret è la somma, su tutti i bracci subottimi, del loro gap moltiplicato per il numero atteso di volte in cui sono stati tirati. Le estrazioni del braccio ottimo non costano nulla; ogni estrazione di un braccio subottimo costa esattamente il suo gap. Si noti che il regret si calcola con i valori attesi veri $\mu_i$, non con i reward effettivamente osservati: misura la qualità delle decisioni, non la fortuna delle estrazioni.

In parole semplici: il regret è il conto di quanto si è “lasciato sul tavolo” per non aver giocato sempre il braccio migliore. Ogni tirata su un braccio sbagliato costa la differenza tra il suo valore medio e quello del migliore; sommando questi costi su tutta la partita si ottiene il regret. Un buon algoritmo tiene questo conto il più basso possibile.

3.2 Regret lineare e logaritmico#

Il comportamento asintotico di $L_T$ al crescere di $T$ classifica gli algoritmi:

• regret lineare, $L_T = \Theta(T)$: l’algoritmo continua a scegliere bracci subottimi con frequenza costante; il regret medio per passo $L_T / T$ non si azzera mai. È il destino sia di chi non esplora abbastanza (e resta bloccato su un braccio sbagliato) sia di chi esplora per sempre alla stessa intensità;
• regret sublineare, $L_T = o(T)$: il regret medio per passo tende a zero, cioè l’algoritmo impara a giocare in modo asintoticamente ottimo;
• regret logaritmico, $L_T = O(\ln T)$: il caso sublineare migliore possibile, in cui i tentativi sprecati crescono solo come il logaritmo dell’orizzonte.

Che il logaritmo sia il traguardo, e non un traguardo migliorabile, è il contenuto di un risultato classico.

L’intuizione del lower bound: per essere sicuri che un braccio è subottimo bisogna campionarlo un numero di volte proporzionale a $\ln T$ (tanto più grande quanto più il braccio è “simile” all’ottimo, cioè quanto più piccola è la divergenza KL), e ognuno di questi campioni obbligati costa $\Delta_i$. Un minimo di esplorazione è quindi inevitabile: il regret logaritmico è il prezzo irriducibile dell’apprendimento. Gli algoritmi delle prossime sezioni si giudicheranno su questa scala: greedy ed $\epsilon$-greedy a $\epsilon$ fisso hanno regret lineare; UCB1 e Thompson Sampling raggiungono il regret logaritmico.

In parole semplici: anche l’algoritmo perfetto deve sprecare qualche tentativo per convincersi che i bracci scadenti sono davvero scadenti, e questi tentativi obbligati crescono come il logaritmo del tempo. Chi spreca solo così poco è di fatto ottimale; chi spreca una frazione fissa dei tentativi (o resta incastrato su un braccio sbagliato) ha regret lineare, il marchio degli algoritmi inadeguati.

4. Il fallimento del greedy e l’esplorazione forzata#

4.1 La selezione greedy e il suo difetto#

Date le stime $Q_t(a)$, la regola di selezione più ovvia è scegliere sempre il braccio con la stima più alta, cioè l’azione greedy:

$$A_t = \arg\max_{a} Q_t(a)$$

Se per esempio le stime correnti sono $Q(a_1) = 0{,}25$, $Q(a_2) = 0{,}5$, $Q(a_3) = 0{,}75$, l’azione greedy è $a_3$ e le altre due sono azioni non-greedy. Scegliere l’azione greedy significa sfruttare la conoscenza corrente.

Che cosa succede selezionando sempre l’azione greedy? Il difetto è strutturale e l’esempio del trial clinico lo mostra subito. Si parta da stime tutte nulle e si supponga che il primo paziente riceva $a_1$ (il braccio peggiore, $\mu_1 = 0{,}25$) e guarisca: $Q(a_1) = 1$. Da quel momento $a_1$ è l’azione greedy, e continuando a sceglierla la sua stima convergerà verso $0{,}25$, che resta comunque maggiore delle stime di $a_2$ e $a_3$, ferme a 0 perché quei bracci non vengono mai provati. L’agente resta bloccato per sempre sul braccio peggiore, e nulla nel meccanismo può correggere l’errore: le stime dei bracci non scelti non si aggiornano, quindi un braccio sottovalutato non ha alcun modo di riscattarsi. Poiché questo blocco su un braccio subottimo avviene con probabilità positiva, il regret atteso della strategia greedy cresce linearmente in $T$.

In parole semplici: il greedy si fida ciecamente delle prime impressioni. Se per sfortuna il braccio migliore parte con un risultato deludente, o uno scadente con un colpo di fortuna, il greedy non se ne accorgerà mai, perché smette di raccogliere le informazioni che potrebbero fargli cambiare idea. È il fallimento di chi non esplora affatto.

4.2 Esplorazione contro sfruttamento#

Il fallimento del greedy mette a fuoco il dilemma centrale:

• sfruttamento (exploitation): l’agente usa la conoscenza accumulata per il beneficio a breve termine: sceglie il braccio con la stima migliore e incassa;
• esplorazione (exploration): l’agente migliora la propria conoscenza per il beneficio a lungo termine: sceglie un braccio incerto, accettando un probabile sacrificio immediato in cambio di stime migliori, e quindi di decisioni migliori, in futuro.

Con una singola azione non si può fare bene entrambe le cose: esplorare e sfruttare si escludono a vicenda passo per passo. La domanda progettuale diventa quindi: quando esplorare e quando sfruttare? Tutti gli algoritmi che seguono sono risposte diverse a questa domanda.

Idea chiave: né lo sfruttamento puro (greedy, che rischia il blocco permanente su un braccio sbagliato) né l’esplorazione pura (scelta casuale, che spreca metà della vita su bracci noti come pessimi) sono accettabili. Serve un meccanismo che dosi le due componenti, idealmente riducendo l’esplorazione man mano che l’incertezza si scioglie.

4.3 La selezione $\epsilon$-greedy#

Il correttivo più semplice al greedy è iniettare una dose fissa di casualità.

Poiché l’estrazione casuale può ricadere anche sull’azione greedy, la probabilità complessiva di scegliere il braccio con la stima migliore è $1 - \epsilon + \epsilon / k$, e ogni braccio non-greedy viene scelto con probabilità $\epsilon / k$. Una traccia tipica di esecuzione con $\epsilon$ piccolo alterna lunghe sequenze di passi greedy a occasionali passi di esplorazione.

La proprietà fondamentale: con $\epsilon > 0$ ogni braccio viene campionato infinitamente spesso, quindi tutte le stime $Q_t(a)$ convergono ai valori veri $q^{*}(a)$. Da un certo punto in poi l’azione greedy coincide con l’azione realmente ottima, che viene quindi scelta con probabilità almeno $1 - \epsilon + \epsilon/k$. Il blocco permanente del greedy è scongiurato: gli errori di valutazione prima o poi vengono sempre corretti.

In parole semplici: $\epsilon$-greedy è il greedy con un tarlo del dubbio: quasi sempre gioca la scelta che sembra migliore, ma ogni tanto (una volta su dieci se $\epsilon = 0{,}1$) tira un dado e prova un braccio qualsiasi. Quel dado occasionale garantisce che nessun braccio venga dimenticato e che ogni errore di giudizio, prima o poi, venga scoperto.

4.4 Il testbed a 10 braccia#

Il confronto empirico standard tra queste strategie è il 10-armed testbed di Sutton e Barto: si generano 2000 problemi bandit indipendenti con $k = 10$, in ciascuno i valori veri $q^{*}(a)$ sono estratti da una gaussiana standard $\mathcal{N}(0, 1)$ e i reward osservati sono $R_t \sim \mathcal{N}(q^{*}(A_t), 1)$; ogni algoritmo gioca 1000 passi su ogni problema e le curve di prestazione (reward medio per passo e percentuale di volte in cui viene scelta l’azione ottima) vengono mediate sulle 2000 esecuzioni, così da eliminare il rumore delle singole partite.

I risultati del confronto tra greedy ($\epsilon = 0$), $\epsilon = 0{,}1$ e $\epsilon = 0{,}01$:

• il greedy puro migliora leggermente all’inizio ma poi si stabilizza su un livello nettamente subottimo: in circa due terzi delle esecuzioni resta agganciato a un braccio sbagliato, e la percentuale di scelte ottime ristagna su valori bassi;
• $\epsilon = 0{,}1$ impara in fretta: esplora abbastanza da individuare rapidamente il braccio migliore; il suo limite è il plateau, perché continua per sempre a esplorare, scegliendo l’azione ottima al più il $91\%$ delle volte ($1 - \epsilon + \epsilon/k = 0{,}91$);
• $\epsilon = 0{,}01$ impara molto più lentamente, ma il suo plateau finale è più alto, perché a regime spreca solo l’$1\%$ dei passi in esplorazione.

Emerge un trade-off netto tra velocità di apprendimento (favorita da $\epsilon$ grande) e prestazione asintotica (favorita da $\epsilon$ piccolo), che suggerisce l’idea naturale di ridurre $\epsilon$ nel tempo: esplorare molto all’inizio, quando le stime sono incerte, e sempre meno man mano che si consolidano.

4.5 Il regret di $\epsilon$-greedy: $\epsilon$ fisso contro $\epsilon$ decrescente#

L’analisi tramite il regret rende quantitativo il difetto del plateau. Con $\epsilon$ fisso, a ogni passo ogni braccio subottimo viene scelto con probabilità almeno $\epsilon / k$ (per via dell’esplorazione uniforme), quindi anche nello scenario migliore, con stime già perfette, il regret atteso per passo resta almeno

$$\frac{\epsilon}{k} \sum_{i=1}^{k} \Delta_i$$

e il regret cumulato cresce linearmente: $L_T \geq \frac{\epsilon}{k} \left( \sum_i \Delta_i \right) T$. L’algoritmo impara la risposta giusta ma continua a pagare per sempre una tassa di esplorazione costante.

Con $\epsilon$ decrescente nel tempo, per esempio con schedule del tipo $\epsilon_t = \min\left\{ 1, \, \frac{c \, k}{d^2 \, t} \right\}$ (dove $d$ è un limite inferiore ai gap dei bracci subottimi), si può dimostrare che il regret diventa logaritmico: l’esplorazione si concentra all’inizio e si spegne al ritmo giusto. Il problema pratico è che lo schedule ottimale dipende dai gap $\Delta_i$, che sono esattamente le quantità ignote del problema: se $\epsilon_t$ decresce troppo in fretta si rischia il blocco alla greedy, se decresce troppo piano si paga esplorazione inutile. Questa fragilità motiva la ricerca di meccanismi di esplorazione più intelligenti, che non trattino tutti i bracci allo stesso modo: è la direzione delle prossime due sezioni.

In parole semplici: con $\epsilon$ fisso si continua a lanciare il dado anche quando ormai si sa tutto, e ogni lancio inutile costa: il rimpianto cresce in proporzione al tempo di gioco. Facendo calare $\epsilon$ si può scendere al rimpianto logaritmico, ma bisogna indovinare la velocità giusta di discesa senza conoscere il problema: è un equilibrismo delicato.

5. Valori iniziali ottimistici#

5.1 Il meccanismo#

Finora le stime sono state inizializzate a $Q_1(a) = 0{,}0$. Che cosa succede inizializzandole a valori più grandi, deliberatamente irrealistici? Per esempio, nel trial clinico con reward in $\{0, 1\}$, si ponga $Q_1(a) = 2{,}0$ per tutti i bracci: un valore che nessun braccio può mantenere, perché supera il massimo reward ottenibile.

Il meccanismo che si innesca, usando la pura selezione greedy, è il seguente. Qualunque braccio venga provato, il reward osservato (0 o 1) è inferiore alla stima gonfiata, quindi la stima di quel braccio scende. Gli altri bracci, non ancora provati, conservano il loro valore ottimistico e diventano automaticamente i più appetibili: al passo successivo il greedy sceglierà uno di loro. Il risultato è una rotazione sistematica su tutti i bracci nelle fasi iniziali, cioè esplorazione senza casualità: ogni braccio viene provato ripetutamente finché tutte le stime non scendono a livelli realistici, e solo allora il greedy inizia a sfruttare davvero. La delusione sistematica delle aspettative fa da motore dell’esplorazione.

Idea chiave: l’ottimismo iniziale trasforma il greedy in un esploratore: ogni braccio parte con un credito immeritato, e per smontare quel credito bisogna provarlo. L’esplorazione non è imposta da un dado esterno, ma emerge dal confronto tra aspettative gonfiate e realtà.

In parole semplici: si dice all’algoritmo che tutte le macchine sono fantastiche. Provandone una, resta deluso e passa alla successiva, che sulla carta sembra ancora fantastica. Quando ha finito di deludersi su tutte, ha ottenuto ciò che serviva: averle provate tutte a sufficienza per confrontarle sul serio.

5.2 Il trial clinico con inizializzazione ottimistica#

Si ripete l’esperimento del trial clinico ($\mu = (0{,}25;\ 0{,}75;\ 0{,}50)$) con $Q_1(a) = 2{,}0$ per tutti i bracci, selezione greedy pura (con pareggi risolti in modo arbitrario) e aggiornamento a passo costante $\alpha = 0{,}5$, cioè $Q \leftarrow Q + 0{,}5 (R - Q)$; con il passo costante il valore iniziale agisce come un bias che decade come $(1-\alpha)^n$, quindi l’ottimismo si esaurisce gradualmente. La tabella riporta un’esecuzione di 12 passi:

La lettura della dinamica è istruttiva. Al passo 1 tutti i bracci valgono $2{,}0$ (pareggio): viene provato $a_1$, che pur ottenendo reward 1 vede la stima scendere a $2 + 0{,}5(1 - 2) = 1{,}5$; con stime gonfiate, perfino un successo è una delusione. Ai passi 2 e 3 il greedy si sposta sui bracci rimasti a $2{,}0$: in tre passi tutti i bracci sono stati provati, senza alcun meccanismo casuale. Nei passi successivi il greedy insegue di volta in volta la stima più alta ($a_3$ al passo 4, $a_1$ al passo 5 dopo il pareggio a $1{,}5$, e così via), continuando a distribuire tentativi. Verso la fine le stime si sono sgonfiate a livelli realistici e la selezione si concentra su $a_2$, che è effettivamente il braccio ottimo.

5.3 Risultati sul testbed e limiti dell’approccio#

Sul 10-armed testbed il confronto standard oppone il greedy ottimistico ($Q_1 = 5$, $\epsilon = 0$, passo costante $\alpha = 0{,}1$; si noti che 5 è molto ottimistico per valori veri estratti da $\mathcal{N}(0,1)$) all’$\epsilon$-greedy realistico ($Q_1 = 0$, $\epsilon = 0{,}1$, $\alpha = 0{,}1$). L’ottimistico è peggiore all’inizio, perché spende i primi passi a esplorare sistematicamente tutti i bracci, ma migliore a regime: una volta esaurito l’ottimismo si comporta come un greedy ben informato, senza pagare la tassa perpetua di esplorazione dell’$\epsilon$-greedy, e la sua percentuale di scelte ottime supera stabilmente quella dell’avversario.

La tecnica ha però limiti precisi:

• l’ottimismo iniziale guida solo l’esplorazione iniziale: è una spinta temporanea che si esaurisce quando le stime si sgonfiano;
• proprio per questo è inadatto ai problemi non stazionari: se il braccio ottimo cambia a metà partita, la riserva di ottimismo è già esaurita e nulla spinge più a riesplorare;
• richiede di sapere quale valore sia “ottimistico”: per fissare $Q_1$ sopra ogni reward plausibile bisogna conoscere la scala dei reward, informazione non sempre disponibile.

In parole semplici: l’ottimismo iniziale è una carica di esplorazione a molla: potente ma monouso. Funziona se il mondo non cambia e se si sa quanto caricare la molla; non può reagire a sorprese tardive, perché a quel punto la spinta esplorativa si è esaurita.

6. UCB: l’ottimismo di fronte all’incertezza#

6.1 Oltre l’esplorazione uniforme: quantificare l’incertezza#

Si torni all’$\epsilon$-greedy con occhio critico. Quando esplora, sceglie uniformemente a caso: tratta allo stesso modo un braccio provato 100 volte con risultati pessimi e un braccio provato 2 volte con risultati promettenti. È uno spreco evidente: il primo braccio non ha più nulla da insegnare, il secondo sì. Le due domande naturali (si può fare meglio della selezione uniforme? si può valutare l’incertezza delle stime delle action-value?) hanno entrambe risposta affermativa, e la seconda risponde alla prima.

L’idea è affiancare a ogni stima puntuale $Q_t(a)$ una misura della sua affidabilità, sotto forma di intervallo di confidenza: un intervallo $[\, Q_t(a) - U_t(a), \; Q_t(a) + U_t(a) \,]$ che contiene il valore vero $q^{*}(a)$ con alta probabilità. Il termine $U_t(a)$ dipende da quante volte il braccio è stato campionato: con poche osservazioni l’intervallo è largo (grande incertezza), e si restringe man mano che $N_t(a)$ cresce. L’estremo superiore $Q_t(a) + U_t(a)$ si chiama upper confidence bound ed è, in un senso preciso, il massimo valore che il braccio può plausibilmente avere alla luce dei dati.

6.2 La selezione UCB e il principio di ottimismo#

Perché è una buona idea? Un braccio può avere bound alto per due ragioni: perché la sua stima è alta (e allora sceglierlo è sfruttamento) o perché la sua incertezza è grande (e allora sceglierlo è esplorazione). In entrambi i casi la scelta è sensata. E il meccanismo si autocorregge: se l’ottimismo era giustificato, il braccio scelto si rivela davvero buono e si continua a sfruttarlo; se era ingiustificato, le nuove osservazioni abbassano la stima e restringono l’intervallo, il bound crolla e il braccio smette di essere scelto. A differenza di $\epsilon$-greedy, l’esplorazione è mirata: si concentra sui bracci che sono ancora plausibilmente ottimi, e ignora quelli già dimostratisi scadenti con alta confidenza.

Idea chiave: UCB fonde esplorazione e sfruttamento in un unico criterio: scegli il braccio col miglior “scenario ottimistico credibile”. I bracci incerti vengono provati perché potrebbero essere ottimi; ogni prova riduce la loro incertezza; alla lunga sopravvivono al vertice solo i bracci realmente buoni.

In parole semplici: invece di chiedersi “quale braccio ha la media migliore?”, UCB si chiede “quale braccio potrebbe ancora essere il migliore, dando a ciascuno il beneficio del dubbio?”. Il beneficio del dubbio è grande per i bracci poco provati e minuscolo per quelli provati mille volte: così l’esplorazione va automaticamente dove serve.

6.3 Da dove viene il bound: la disuguaglianza di Hoeffding e UCB1#

Resta da costruire concretamente $U_t(a)$. Lo strumento è una disuguaglianza di concentrazione classica.

Applicata al braccio $a$ ($\bar{X}_n = Q_t(a)$, $n = N_t(a)$), la disuguaglianza dice che la probabilità che il valore vero superi la stima di più di $U_t(a)$ è al massimo $e^{-2 N_t(a) U_t(a)^2}$. Si fissa allora una probabilità di errore tollerata $p$ e si risolve rispetto al margine:

$$e^{-2 N_t(a) U_t(a)^2} = p \quad \Longrightarrow \quad U_t(a) = \sqrt{\frac{\ln(1/p)}{2 N_t(a)}}$$

La scelta furba è far diminuire $p$ col tempo, per esempio $p = t^{-4}$: man mano che il gioco procede si richiedono garanzie sempre più forti, così che i bound restino validi lungo tutta l’esecuzione e ogni braccio venga rivisitato prima o poi. Con $p = t^{-4}$ il margine diventa $U_t(a) = \sqrt{\frac{4 \ln t}{2 N_t(a)}} = \sqrt{\frac{2 \ln t}{N_t(a)}}$, e si ottiene l’algoritmo UCB1.

La formulazione generale usata nel corso introduce un coefficiente $c > 0$ definito dall’utente che regola l’intensità dell’esplorazione:

$$A_t = \arg\max_{a} \Bigg[ \underbrace{Q_t(a)}_{\text{sfruttamento}} \; + \; \underbrace{c \, \sqrt{\frac{\ln t}{N_t(a)}}}_{\text{esplorazione}} \Bigg]$$

UCB1 corrisponde alla scelta $c = \sqrt{2}$. Il primo termine spinge verso i bracci con stima alta (exploit), il secondo verso i bracci poco campionati (explore); $c$ più grande significa più peso all’esplorazione.

La struttura del termine di esplorazione merita un commento. Il numeratore $\ln t$ cresce (lentamente) nel tempo: un braccio ignorato a lungo vede il proprio bonus salire, finché non torna abbastanza appetibile da essere riprovato; nessun braccio viene abbandonato per sempre. Il denominatore $N_t(a)$ cresce a ogni estrazione del braccio: ogni prova riduce l’incertezza e quindi il bonus. L’equilibrio tra le due forze fa sì che ogni braccio venga campionato infinite volte, ma i bracci subottimi solo con frequenza logaritmica.

In parole semplici: il bonus di esplorazione è una molla che si carica col passare del tempo per i bracci trascurati e si scarica a ogni prova. I bracci pessimi vengono riprovati ogni tanto, giusto per sicurezza, ma a intervalli sempre più lunghi; i bracci promettenti vengono provati spesso finché il dubbio non è sciolto.

6.4 Il regret di UCB1#

L’analisi teorica premia la costruzione.

Il regret di UCB1 è quindi logaritmico in $T$, lo stesso ordine di crescita del lower bound di Lai e Robbins: UCB1 è ottimo a meno di costanti, e lo è su ogni istanza, senza bisogno di conoscere i gap, la scala del problema o l’orizzonte, e senza parametri da calibrare (nella versione con $c = \sqrt{2}$). La struttura del bound è anche interpretabile: ogni braccio subottimo viene estratto circa $\frac{8 \ln T}{\Delta_i^2}$ volte, e ogni estrazione costa $\Delta_i$; i bracci quasi buoni (gap piccolo) vengono provati più a lungo ma costano poco per prova, quelli pessimi (gap grande) costano tanto per prova ma vengono liquidati in fretta.

6.5 UCB sul testbed#

Sul 10-armed testbed, UCB con $c = 2$ confrontato con $\epsilon$-greedy a $\epsilon = 0{,}1$ ottiene un reward medio complessivamente superiore dopo la fase iniziale. La curva di UCB mostra un andamento caratteristico nei primissimi passi: dopo aver provato una volta ciascuno dei 10 bracci (i bound dei bracci mai provati sono infiniti), all’undicesimo passo l’algoritmo sfrutta brevemente il braccio empiricamente migliore producendo un picco di reward, poi i bonus di esplorazione dei bracci trascurati tornano a crescere e impongono altri passi esplorativi, con un temporaneo calo; superata questa fase di assestamento, la selezione si concentra stabilmente sul braccio ottimo e la prestazione asintotica supera quella di $\epsilon$-greedy, che continua per sempre a pagare la sua tassa di esplorazione uniforme.

7. L’approccio bayesiano: il Thompson Sampling#

7.1 Dalla stima puntuale alla distribuzione a posteriori#

UCB rappresenta la conoscenza su ogni braccio con due numeri: una stima puntuale e un margine di incertezza. L’approccio bayesiano compie il passo successivo: rappresenta la conoscenza su $q^{*}(a)$ con un’intera distribuzione di probabilità. Si parte da una distribuzione a priori (prior) che codifica la conoscenza iniziale, e a ogni osservazione la si aggiorna con la regola di Bayes ottenendo la distribuzione a posteriori (posterior). Il posterior contiene in un solo oggetto sia la stima (per esempio la sua media) sia l’incertezza (la sua dispersione), e l’incertezza si riduce automaticamente man mano che i dati si accumulano.

7.2 Il caso Bernoulli: prior e posterior Beta#

Nel caso più comune in pratica (e negli esami), i reward sono binari: $R_t \in \{0, 1\}$ e ogni braccio $i$ è una Bernoulli di parametro ignoto $\mu_i$. La famiglia di distribuzioni naturale per rappresentare la conoscenza su un parametro in $[0, 1]$ è la distribuzione Beta.

La proprietà che rende la Beta perfetta per i bandit Bernoulliani è la coniugatezza: se il prior su $\mu_i$ è una Beta e si osserva un’estrazione Bernoulliana, il posterior è ancora una Beta, con parametri aggiornati in modo banale.

Il posterior si comporta esattamente come ci si aspetta: la sua media $\frac{\alpha_i}{\alpha_i + \beta_i}$ tende alla frequenza empirica dei successi, e la sua varianza si riduce al crescere del numero di osservazioni $\alpha_i + \beta_i - 2$: pochi dati danno una campana larga (grande incertezza), molti dati una campana stretta attorno al valore vero.

In parole semplici: per ogni braccio si tengono due contatori: successi e fallimenti (più uno di cortesia ciascuno, ereditato dal prior). La coppia di contatori disegna una curva a campana su “quanto potrebbe valere questo braccio”: all’inizio piatta (può valere qualsiasi cosa), sempre più appuntita man mano che i tentativi si accumulano.

7.3 L’algoritmo#

Il Thompson Sampling (proposto da W. Thompson nel 1933, ed è quindi il più antico algoritmo per bandit) usa i posterior in un modo elegantemente semplice: invece di scegliere il braccio con la media a posteriori più alta (che sarebbe un greedy bayesiano, con gli stessi difetti del greedy), campiona un valore da ciascun posterior e sceglie il braccio col campione migliore.

7.4 Perché funziona e con quale regret#

L’esplorazione del Thompson Sampling nasce dalla casualità del campionamento, ma è una casualità calibrata sull’incertezza, non uniforme come in $\epsilon$-greedy. Un braccio con posterior largo (poco provato) produce campioni molto variabili: ogni tanto estrarrà un valore alto e vincerà la selezione, guadagnandosi una prova; un braccio provato a lungo con esiti mediocri ha un posterior stretto e basso, i suoi campioni non vincono quasi mai, e il braccio viene di fatto abbandonato. La proprietà che ne risulta è nota come probability matching: a ogni passo, il Thompson Sampling sceglie ciascun braccio esattamente con la probabilità che quel braccio sia il migliore alla luce dei dati raccolti. L’esplorazione si spegne da sola, braccio per braccio, al ritmo con cui si spegne il dubbio.

Sul piano teorico il Thompson Sampling ha regret logaritmico e, nel caso Bernoulli, asintoticamente ottimale anche nelle costanti: raggiunge esattamente il lower bound di Lai e Robbins (risultati di Agrawal e Goyal e di Kaufmann, Korda e Munos, 2012). Sul piano empirico è spesso il migliore della famiglia, con prestazioni pari o superiori a UCB su molti problemi reali. I suoi requisiti: bisogna assumere un modello probabilistico dei reward e saper mantenere (o approssimare) il posterior; con reward Bernoulliani e prior Beta tutto è in forma chiusa e l’algoritmo costa quanto un $\epsilon$-greedy.

In parole semplici: il Thompson Sampling fa decidere a un sorteggio onesto: ogni braccio “pesca” un possibile valore di sé stesso dalla propria campana di incertezza, e vince il braccio con la pescata migliore. I bracci incerti hanno campane larghe e ogni tanto pescano alto, quindi vengono provati; i bracci noti e scadenti non vincono mai. Più si gioca, più le campane si stringono e il sorteggio converge sul braccio davvero migliore.

8. Confronto tra gli approcci#

Il quadro complessivo degli algoritmi visti, con i rispettivi meccanismi e garanzie:

La linea evolutiva è chiara. Il greedy non esplora e fallisce. L’$\epsilon$-greedy esplora, ma alla cieca: uniformemente su tutti i bracci e per sempre, pagando regret lineare. L’ottimismo iniziale esplora gratis ma solo all’inizio. UCB e Thompson Sampling esplorano in modo proporzionale all’incertezza, ciascuno col proprio linguaggio (intervalli di confidenza frequentisti l’uno, distribuzioni a posteriori bayesiane l’altro), e per questo raggiungono entrambi il regret logaritmico, il migliore possibile.

In parole semplici: la domanda giusta non è “quanto esplorare?” ma “dove ha ancora senso esplorare?”. Gli algoritmi che dosano l’esplorazione braccio per braccio, in base a quanto è rimasto da imparare su ciascuno, battono strutturalmente quelli che esplorano a caso o smettono troppo presto.

9. Esercizi svolti in stile esame#

9.1 Calcolo del regret di una sequenza#

Testo. Un bandit ha $k = 3$ bracci con reward Bernoulliani di medie $\mu_1 = 0{,}25$, $\mu_2 = 0{,}75$, $\mu_3 = 0{,}50$. Un algoritmo gioca $T = 12$ passi tirando: il braccio 1 ai passi $\{1, 2, 7, 11\}$, il braccio 2 ai passi $\{3, 5, 9, 12\}$, il braccio 3 ai passi $\{4, 6, 8, 10\}$. Calcolare il regret cumulato atteso della sequenza e il regret medio per passo. Quale sarebbe stato il regret della strategia che gioca sempre il braccio 2?

Procedura meccanica.

1. Identificare il braccio ottimo e il suo valore: $\mu^{*} = \max_i \mu_i$.
2. Calcolare i gap: $\Delta_i = \mu^{*} - \mu_i$ per ogni braccio.
3. Contare le estrazioni di ciascun braccio nella sequenza: $N_T(i)$.
4. Applicare la decomposizione del regret $L_T = \sum_i N_T(i) \, \Delta_i$.
5. Attenzione alla trappola classica: il regret si calcola con le medie vere $\mu_i$, non con i reward osservati nella sequenza; i reward osservati non entrano nel calcolo.

Svolgimento

1. Il braccio ottimo è il 2: $\mu^{*} = 0{,}75$.
2. Gap: $\Delta_1 = 0{,}75 - 0{,}25 = 0{,}50$; $\Delta_2 = 0$; $\Delta_3 = 0{,}75 - 0{,}50 = 0{,}25$.
3. Conteggi: $N_{12}(1) = 4$, $N_{12}(2) = 4$, $N_{12}(3) = 4$.
4. Regret:

$$L_{12} = 4 \cdot 0{,}50 + 4 \cdot 0 + 4 \cdot 0{,}25 = 2 + 0 + 1 = 3$$

Il regret medio per passo è $L_{12} / 12 = 0{,}25$. La strategia costante sul braccio 2 tira solo il braccio ottimo, quindi il suo regret è $L_{12} = 0$: il regret misura esattamente il costo delle 8 estrazioni “sprecate” sui bracci subottimi.

Estensione tipica (regret atteso di $\epsilon$-greedy a regime). Se un $\epsilon$-greedy con $\epsilon = 0{,}1$ ha ormai stime corrette (il greedy punta al braccio 2) e gioca altri $T = 1000$ passi, l’esplorazione uniforme tira ogni braccio con probabilità $\epsilon / k = 0{,}1/3$ a passo. Regret atteso per passo: $\frac{\epsilon}{k} \sum_i \Delta_i = \frac{0{,}1}{3} (0{,}50 + 0 + 0{,}25) = 0{,}025$; su 1000 passi, $L_{1000} \approx 25$. La crescita è lineare in $T$: raddoppiando l’orizzonte raddoppia il regret.

9.2 Scelta del braccio con UCB1#

Testo. In un bandit a 3 bracci sono state effettuate $t = 10$ estrazioni, con conteggi $N(1) = 5$, $N(2) = 3$, $N(3) = 2$ e stime correnti $Q(1) = 0{,}6$, $Q(2) = 0{,}7$, $Q(3) = 0{,}4$. (a) Quale braccio seleziona UCB1? (b) Quale braccio seleziona la variante con coefficiente $c = 2$? (c) Se il braccio selezionato da UCB1 restituisce reward $R = 0$, come si aggiornano conteggio e stima? (Usare $\ln 10 \approx 2{,}3026$.)

Procedura meccanica.

1. Se qualche braccio ha $N(i) = 0$, va scelto quello (bonus infinito); altrimenti proseguire.
2. Calcolare $\ln t$ con il valore di $t$ indicato dal testo (qui il numero totale di estrazioni effettuate; specificare sempre la convenzione adottata).
3. Per ogni braccio calcolare il bonus: $\sqrt{2 \ln t / N(i)}$ per UCB1, oppure $c \sqrt{\ln t / N(i)}$ nella forma generale.
4. Sommare stima e bonus per ottenere l’indice UCB di ogni braccio.
5. Scegliere il braccio con indice massimo (pareggi risolti arbitrariamente).
6. Dopo l’osservazione del reward: $N \leftarrow N + 1$ e aggiornamento incrementale $Q \leftarrow Q + \frac{1}{N}(R - Q)$ per il solo braccio tirato.

Svolgimento

(a) UCB1, bonus $\sqrt{2 \ln t / N}$ con $2 \ln 10 \approx 4{,}6052$.

$$\mathrm{UCB}(1) = 0{,}6 + \sqrt{\frac{4{,}6052}{5}} = 0{,}6 + \sqrt{0{,}9210} \approx 0{,}6 + 0{,}960 = 1{,}560$$

$$\mathrm{UCB}(2) = 0{,}7 + \sqrt{\frac{4{,}6052}{3}} = 0{,}7 + \sqrt{1{,}5351} \approx 0{,}7 + 1{,}239 = 1{,}939$$

$$\mathrm{UCB}(3) = 0{,}4 + \sqrt{\frac{4{,}6052}{2}} = 0{,}4 + \sqrt{2{,}3026} \approx 0{,}4 + 1{,}517 = 1{,}917$$

Il massimo è $\mathrm{UCB}(2) \approx 1{,}939$: UCB1 seleziona il braccio 2. Si noti quanto il braccio 3, pur avendo la stima puntuale peggiore ($0{,}4$), arrivi a un soffio dal vincere grazie al bonus di incertezza: è l’ottimismo di fronte all’incertezza in azione.

(b) Forma generale con $c = 2$, bonus $2\sqrt{\ln t / N}$.

$$\mathrm{UCB}(1) = 0{,}6 + 2\sqrt{0{,}4605} \approx 0{,}6 + 1{,}357 = 1{,}957$$

$$\mathrm{UCB}(2) = 0{,}7 + 2\sqrt{0{,}7675} \approx 0{,}7 + 1{,}752 = 2{,}452$$

$$\mathrm{UCB}(3) = 0{,}4 + 2\sqrt{1{,}1513} \approx 0{,}4 + 2{,}146 = 2{,}546$$

Con $c = 2 > \sqrt{2}$ il peso dell’esplorazione cresce e la selezione cambia: vince il braccio 3, il meno campionato. È la dimostrazione numerica del ruolo di $c$: coefficienti più grandi spostano la scelta verso i bracci più incerti.

(c) Aggiornamento dopo il reward. UCB1 ha tirato il braccio 2, che restituisce $R = 0$. Aggiornamento: $N(2) \leftarrow 3 + 1 = 4$ e

$$Q(2) \leftarrow 0{,}7 + \frac{1}{4} \left( 0 - 0{,}7 \right) = 0{,}7 - 0{,}175 = 0{,}525$$

Gli altri bracci restano invariati. Al passo successivo si ripete l’intera procedura con $t = 11$.

9.3 Thompson Sampling: aggiornamento Beta e scelta del braccio#

Testo. Un bandit Bernoulliano a 3 bracci viene affrontato col Thompson Sampling, partendo dal prior uniforme $\mathrm{Beta}(1, 1)$ su ogni braccio. La storia finora: il braccio 1 è stato tirato 4 volte con 3 successi; il braccio 2, 2 volte con 1 successo; il braccio 3, 1 volta con 0 successi. (a) Scrivere il posterior di ogni braccio e la sua media. (b) Al passo corrente i campioni estratti dai posterior sono $\theta_1 = 0{,}55$, $\theta_2 = 0{,}71$, $\theta_3 = 0{,}60$: quale braccio viene tirato? (c) Il braccio tirato restituisce reward $0$: scrivere il nuovo posterior e la nuova media.

Procedura meccanica.

1. Per ogni braccio contare successi $s_i$ e fallimenti $f_i$ nella storia.
2. Posterior con prior $\mathrm{Beta}(1,1)$, per l’aggiornamento Beta-Bernoulli: $\mathrm{Beta}(1 + s_i, \, 1 + f_i)$; se il prior è $\mathrm{Beta}(\alpha_0, \beta_0)$, allora $\mathrm{Beta}(\alpha_0 + s_i, \beta_0 + f_i)$.
3. Media a posteriori: $\alpha_i / (\alpha_i + \beta_i)$.
4. Selezione: braccio col campione $\theta_i$ massimo (non con la media massima: è il campionamento a produrre l’esplorazione).
5. Aggiornamento del solo braccio tirato: successo $\Rightarrow \alpha \leftarrow \alpha + 1$; fallimento $\Rightarrow \beta \leftarrow \beta + 1$.

Svolgimento

(a) Successi e fallimenti: braccio 1: $s = 3$, $f = 1$; braccio 2: $s = 1$, $f = 1$; braccio 3: $s = 0$, $f = 1$. Posterior:

$$\mu_1 \sim \mathrm{Beta}(1+3, \, 1+1) = \mathrm{Beta}(4, 2), \qquad \text{media } \frac{4}{6} \approx 0{,}667$$

$$\mu_2 \sim \mathrm{Beta}(1+1, \, 1+1) = \mathrm{Beta}(2, 2), \qquad \text{media } \frac{2}{4} = 0{,}5$$

$$\mu_3 \sim \mathrm{Beta}(1+0, \, 1+1) = \mathrm{Beta}(1, 2), \qquad \text{media } \frac{1}{3} \approx 0{,}333$$

(Le tre densità sono esattamente quelle della figura dei posterior.)

(b) Si confronta il vettore dei campioni $(\theta_1, \theta_2, \theta_3) = (0{,}55; \, 0{,}71; \, 0{,}60)$: il massimo è $\theta_2 = 0{,}71$, quindi viene tirato il braccio 2. Si osservi che il braccio 1 ha la media a posteriori più alta ($0{,}667$) ma non viene scelto: il suo posterior, più concentrato (6 pseudo-osservazioni contro 4), ha prodotto stavolta un campione basso, mentre il braccio 2, più incerto, ha pescato alto. È esattamente il meccanismo con cui il Thompson Sampling esplora le alternative ancora plausibili.

(c) Il braccio 2 restituisce $r = 0$ (fallimento): si incrementa $\beta_2$,

$$\mu_2 \sim \mathrm{Beta}(2, \, 2+1) = \mathrm{Beta}(2, 3), \qquad \text{nuova media } \frac{2}{5} = 0{,}4$$

I posterior dei bracci 1 e 3 restano invariati. La media del braccio 2 scende da $0{,}5$ a $0{,}4$ e il suo posterior si stringe: al prossimo giro sarà un po’ meno probabile che vinca il sorteggio.

9.4 Domande di teoria: risposte modello#

Domanda 1: perché la strategia greedy ha regret lineare? Risposta modello: perché con probabilità positiva le prime osservazioni portano le stime a preferire un braccio subottimo, e da quel momento i bracci alternativi, non venendo più selezionati, non aggiornano le proprie stime: l’errore non è mai corretto e l’agente paga il gap $\Delta_i > 0$ a ogni passo per sempre. Il regret atteso cresce quindi come $\Theta(T)$.

Domanda 2: confrontare il regret atteso di $\epsilon$-greedy (con $\epsilon$ fisso) e di UCB1. Risposta modello: $\epsilon$-greedy con $\epsilon$ fisso ha regret lineare, $L_T \geq \frac{\epsilon}{k} \left( \sum_i \Delta_i \right) T$, perché l’esplorazione uniforme seleziona ogni braccio subottimo con probabilità costante $\epsilon/k$ a ogni passo, anche quando le stime sono ormai corrette. UCB1 ha regret logaritmico, $L_T = O\left( \sum_{i: \Delta_i > 0} \frac{\ln T}{\Delta_i} \right)$, perché il bonus $\sqrt{2 \ln t / N_t(i)}$ concentra l’esplorazione sui bracci incerti e la riduce automaticamente man mano che i conteggi crescono; l’ordine $\ln T$ coincide con il lower bound di Lai e Robbins, quindi UCB1 è ottimale a meno di costanti.

Domanda 3: in che senso UCB e Thompson Sampling applicano entrambi lo stesso principio, e in che cosa differiscono? Risposta modello: entrambi dosano l’esplorazione in proporzione all’incertezza residua su ciascun braccio, invece che uniformemente. UCB lo fa in modo frequentista e deterministico: costruisce un intervallo di confidenza per ogni braccio e sceglie l’estremo superiore più alto (ottimismo di fronte all’incertezza). Il Thompson Sampling lo fa in modo bayesiano e stocastico: mantiene un posterior per ogni braccio, ne campiona un valore e sceglie il campione più alto, selezionando così ogni braccio con la probabilità che sia ottimo dati i dati (probability matching). Entrambi ottengono regret logaritmico; il TS richiede un modello probabilistico dei reward, UCB solo reward limitati.

Domanda 4: perché i valori iniziali ottimistici non risolvono i problemi non stazionari? Risposta modello: l’ottimismo iniziale genera esplorazione solo finché le stime gonfiate non si sgonfiano al livello dei valori veri: è una spinta esclusivamente iniziale e non rinnovabile. In un problema non stazionario il braccio ottimo può cambiare dopo che l’ottimismo si è esaurito, e a quel punto un agente greedy non ha più alcun meccanismo che lo induca a riesplorare; servono meccanismi di esplorazione persistenti ($\epsilon$-greedy, UCB con finestre o sconto) e stime a passo costante che dimentichino il passato remoto.

Glossario#

Dispensa Machine Learning · Politecnico di Milano