Modulo 8 · Lezione 8.1
Imparare dalle azioni: esplorazione e ricompense
Nell’apprendimento per rinforzo un sistema sceglie azioni, osserva conseguenze e cerca di migliorare una strategia. L’informazione raccolta dipende anche dalle scelte che compie.
Il caso più semplice: il bandit
Un bandit modella decisioni ripetute fra alternative con ricompense incerte, senza descrivere transizioni di stato come in un problema sequenziale generale. Per esempio, un sito può confrontare diversi ordinamenti di contenuti e osservare le interazioni con quello mostrato.
La ricompensa, o reward, è il numero usato per valutare l’esito. Osserviamo quello dell’azione scelta, mentre normalmente non vediamo che cosa sarebbe accaduto con tutte le altre nello stesso momento.
Esplorare o sfruttare
Sfruttare significa scegliere l’alternativa che sembra migliore secondo le stime attuali. Esplorare significa provare alternative per ottenere informazione. Se sfruttiamo troppo presto, un risultato fortunato può bloccarci su una scelta mediocre; esplorare continuamente ha un costo.
Una strategia epsilon-greedy riserva una quota delle scelte all’esplorazione casuale. Altri metodi considerano l’incertezza delle stime, come gli intervalli di confidenza o il campionamento da una distribuzione sui possibili valori.
Scegliere ciò che conosci o imparare di più?
Che cosa misura il rimpianto
Il rimpianto, o regret, confronta la ricompensa ottenuta con quella di un riferimento definito, spesso la migliore azione in valore atteso. Il riferimento e le ipotesi del problema devono essere espliciti.
Nel caso dei contenuti, massimizzare clic non equivale automaticamente a migliorare soddisfazione o apprendimento. La scelta della ricompensa è parte del problema, non un dettaglio del codice.
Esempio svolto: quale spiegazione proporre dopo?
Un’app didattica può mostrare una spiegazione A, B o C e osservare se viene risolto l’esercizio successivo. I dati di esempio nella figura sono 8 successi su 10, 2 su 2 e 72 su 100. B ha la media più alta, ma pochissime prove: scegliere sempre B scambierebbe una stima incerta per una certezza.
Con una strategia ε-greedy e ε = 0,1, nel 90% dei casi scegli l’alternativa con media osservata migliore; nel 10% scegli uniformemente fra tutte e tre. Se B è l’unica migliore, la sua probabilità totale è 0,9 + 0,1/3 ≈ 93,3%. Anche il ramo esplorativo può selezionare B. Le altre due ricevono circa 3,3% ciascuna.
Il rimpianto confronta le ricompense attese delle azioni prese con quelle della migliore alternativa di riferimento. Se in una simulazione la migliore ha probabilità di successo 0,8 e scegli dieci volte una con probabilità 0,6, il rimpianto atteso su quei dieci passi è 10 × (0,8 − 0,6) = 2. Nel mondo reale queste probabilità spesso non sono note: le medie osservate sono stime.
Quando il bandit semplice non basta
La spiegazione migliore dipende dal livello dello studente. Che cosa manca al modello precedente?
Soluzione: Il contesto della scelta. Un contextual bandit può usare caratteristiche disponibili prima dell’azione. Se la scelta cambia anche conoscenze e possibilità future dello studente, emerge inoltre una dinamica sequenziale che richiede una formulazione più ricca.
Pratica guidata
Calcola le probabilità di scelta. Con tre spiegazioni A, B e C e B unica migliore per media osservata, calcola le probabilità di scelta con ε = 0,3. Disegna una barra composta da sfruttamento ed esplorazione per ogni azione. Poi confronta la prova B = 2/2 con A = 8/10: quale informazione manca per chiamare B certamente superiore?
Come procedere
Il ramo esplorativo sceglie uniformemente anche B, non soltanto le alternative peggiori.
Lo sfruttamento assegna 0,7 a B; l’esplorazione assegna 0,3/3 a ciascuna azione.
Confronta la soluzione
B riceve probabilità 0,8; A e C 0,1 ciascuna. Se assegnassi a B solo 0,7, avresti dimenticato i casi in cui la scegli esplorando. I due successi su due producono una media alta ma poca evidenza: servono ulteriori osservazioni e un’analisi dell’incertezza nel contesto d’uso. Non conosci le probabilità vere come in un simulatore. Se la spiegazione cambia l’apprendimento futuro, il reward del prossimo esercizio può inoltre non esaurire il compito sequenziale.
Prova su un caso nuovo
Progetta un esperimento per due livelli di studenti: indica il contesto disponibile prima della scelta e un esito didattico diverso dal semplice clic. Distingui un contextual bandit da un problema in cui la scelta modifica gli stati futuri.
Controllo del tuo elaborato: Le probabilità sommano a uno e la proposta distingue stima osservata, probabilità vera e obiettivo didattico.
Dalla pratica al laboratorio
Il laboratorio conosce le ricompense attese perché costruisce il simulatore: lì può misurare il rimpianto. In un’app reale queste probabilità sono ignote: puoi applicare la strategia di esplorazione, ma non calcolare il rimpianto usando valori veri già noti.
Controlla il ragionamento
Scegli una risposta e leggi la spiegazione.
Con tre azioni, B unica migliore osservata e ε = 0,3, quale probabilità ha B in ε-greedy con esplorazione uniforme su tutte le azioni?
La probabilità della policy dipende dalla regola di scelta. La media osservata più alta non coincide con certezza sulla ricompensa attesa vera.
Rileggi la spiegazioneApprofondimento tecnico facoltativo
Derivazioni e laboratorio
Lezione 8.1. Nei problemi supervisionati il dataset è spesso trattato come dato. In una decisione sequenziale le azioni determinano quali osservazioni riceveremo. Studiamo prima il caso in cui un’azione cambia la ricompensa immediata, ma non lo stato futuro del mondo.
Un esperimento con informazione parziale
Tre procedure producono esiti Bernoulli con probabilità di successo 0,2, 0,5 e 0,65. Le medie sono note al simulatore e al valutatore, non all’algoritmo. A ogni turno scegliamo una procedura e osserviamo soltanto il suo esito. Il valore di una politica dipende sia da ciò che sa già sia da ciò che decide di provare.
Il laboratorio prepara una matrice di potenziali esiti per tempo e braccio, condivisa fra i metodi nella stessa replica. Ogni metodo può leggere soltanto la cella dell’azione scelta. Questa costruzione rende i confronti appaiati rispetto al mondo simulato senza consegnare osservazioni controfattuali all’agente.
Dopo un’osservazione r, la media empirica si aggiorna senza conservare tutta la storia:
N_a ← N_a + 1
Q_a ← Q_a + (r − Q_a)/N_a
La ricompensa osservata non è la media del braccio: un insuccesso iniziale può verificarsi anche per l’opzione migliore. Usare sempre il massimo Q può impedire di correggere una stima iniziale sfortunata.
Tre politiche da confrontare
Il greedy sceglie sempre la media empirica maggiore. L’epsilon-greedy esplora con probabilità 0,1 scegliendo uniformemente fra tutti i bracci; altrimenti usa il greedy. Anche durante l’esplorazione può scegliere il braccio attualmente migliore.
L’UCB aggiunge un termine che cresce con l’incertezza:
a_t = argmax_a [Q_a + √(2 log(t+1)/N_a)]
Prima di applicare queste regole campioniamo ciascun braccio una volta, evitando divisioni per zero. Il bonus diminuisce quando un braccio viene osservato spesso e cresce lentamente col tempo per i bracci trascurati. Non è un intervallo di confidenza simultaneo automaticamente calibrato per qualunque processo: dipende da ipotesi sulle ricompense, qui indipendenti e limitate fra zero e uno.
L’esplorazione costante dell’epsilon-greedy conserva un costo anche quando le medie sono ormai ben stimate. Sotto scelta uniforme esplorativa, il solo costo atteso per turno dovuto all’esplorazione è 0,1 · (0,45+0,15+0)/3 = 0,02. A lungo termine, con epsilon fisso, questo contributo cresce linearmente col numero di turni.
Misurare il costo delle scelte
Il laboratorio registra il pseudo-regret:
R_T = Σ_{t=1}^T [μ* − μ_{a_t}]
Ogni termine usa la media vera dell’azione selezionata. È una variabile casuale perché le azioni dipendono dagli esiti precedenti, ma elimina il rumore dell’ultima ricompensa dalla misura. Non è la differenza osservata fra due somme di successi; non può essere calcolato da normali log quando le medie vere sono ignote.
| Politica | Pseudo-regret medio a 1.000 turni | Deviazione standard su 100 repliche |
|---|---|---|
| Greedy | 104,98 | 162,35 |
| Epsilon-greedy | 31,90 | 24,73 |
| UCB | 45,01 | 8,40 |
In questo esperimento epsilon-greedy ha la media migliore; UCB ha minore dispersione. Il greedy può bloccarsi a lungo su una scelta sbagliata. Non esiste una conclusione universale sull’ordinamento dei tre metodi: dipende da distanze fra medie, orizzonte, inizializzazione e parametri. La deviazione standard delle repliche non è l’errore standard della media; per quest’ultimo, sotto indipendenza delle repliche, si divide per la radice del loro numero.
Dal bandit al contesto e al tempo
Un bandit contestuale osserva caratteristiche x prima di scegliere e usa π(a|x). Occorre registrare anche la probabilità con cui la politica di raccolta ha scelto l’azione: sarà essenziale per valutare altre politiche. Se invece un’azione influenza le possibilità future, la sola ricompensa immediata perde una parte del problema. Il prossimo modello introduce esplicitamente le transizioni.
Dal bonus di confidenza al numero di esplorazioni
Per n ricompense indipendenti in [0,1], Hoeffding dà P(μ−Q_n≥c) ≤ exp(−2nc²). Ponendo c=√(2 log t/n) otteniamo un limite puntuale t⁻⁴. Poiché nel bandit il numero di osservazioni è adattivo, una dimostrazione completa deve controllare i possibili conteggi e i tempi, per esempio con un’unione di eventi; non basta inserire una numerosità casuale in un intervallo fisso e dichiararlo simultaneo.
Sul buon evento in cui le stime sono vicine alle medie, un braccio subottimale con gap Δₐ può continuare a competere quando il suo bonus è dello stesso ordine del gap. Dalla condizione 2√(2 log t/Nₐ) ≥ Δₐ segue Nₐ ≤ 8 log t/Δₐ². Questo passaggio spiega la scala: distinguere bracci con medie vicine richiede più osservazioni; il loro contributo al rimpianto è ΔₐNₐ, quindi dell’ordine di log T/Δₐ, più i termini necessari a gestire inizializzazione ed eventi sfavorevoli. Non è una previsione esatta della tabella a T=1.000.
La decomposizione R_T=Σₐ ΔₐNₐ(T) vale invece esattamente per il pseudo-regret di ogni esecuzione. Usala come controllo indipendente: sommare i gap lungo la sequenza delle azioni e moltiplicarli per i conteggi finali deve dare lo stesso numero. La dimostrazione del limite atteso completo è nel lavoro di Auer, Cesa-Bianchi e Fischer.
Costruzione guidata del simulatore
Nella funzione bandit, isola il generatore della matrice degli esiti dall’algoritmo di scelta. Passa al decisore soltanto storia osservata, conteggi e medie. Verifica che la somma dei conteggi sia T e che ogni aggiornamento tocchi un solo braccio. Dopo l’inizializzazione, confronta greedy, epsilon-greedy e UCB sullo stesso seed del mondo.
Per confrontare due metodi, conserva la differenza di pseudo-regret entro ogni replica. La deviazione standard delle differenze incorpora la correlazione indotta dal mondo condiviso; non si ricava sommando automaticamente le varianze marginali. Un’estensione con medie che cambiano nel tempo richiede un’altra ipotesi statistica: la media cumulativa e il bonus qui usati sono progettati per ricompense stazionarie. Specifica prima istante e ampiezza del cambiamento, poi confronta finestre o pesi temporali senza attribuire loro le garanzie del caso stazionario.
Esercizi
- Dopo cinque esiti con media 0,4 osservi un successo. Calcola la nuova stima.
Soluzione: 0,4 + (1−0,4)/6 = 0,5. Equivale a tre successi su sei osservazioni.
- Scegli il secondo braccio per 100 turni. Quanto vale il pseudo-regret?
Soluzione: 100·(0,65−0,5)=15, indipendentemente dal numero di successi effettivamente osservati. Questi ultimi influenzerebbero una misura basata sulle ricompense realizzate.
- Perché la tabella non giustifica una prova reale con azioni rischiose scelte casualmente?
Soluzione: Le ricompense simulate sono limitate, le azioni non hanno conseguenze esterne e i costi sono interamente descritti. In un sistema reale occorre definire azioni ammissibili e costi prima di esplorare. Il risultato nel simulatore, da solo, non giustifica l’esecuzione di quelle azioni in un sistema reale.
Prosegui con MDP e Bellman.
Il tuo riscontro
Com’è andata questa lezione?
Dimmi cosa è chiaro e dove la spiegazione può migliorare.