Il problema del bandito a più braccia: come funziona il multi-armed bandit

Immagina di entrare in un casinò e di trovarti davanti a una fila di slot machine. Ognuna ha una probabilità di vincita diversa, ma tu non la conosci. Hai un numero limitato di gettoni e un solo obiettivo, portare a casa la vincita più alta possibile. Su quale macchina punti? E soprattutto, quanto tempo dedichi a provarle tutte prima di concentrarti su quella che ti sembra la migliore?

Questo piccolo dilemma, all’apparenza banale, ha un nome preciso e una lunga storia nella teoria delle decisioni e nell’intelligenza artificiale, il problema del bandito a più braccia, in inglese multi-armed bandit. È uno dei modelli più eleganti e utili di tutto l’apprendimento per rinforzo, perché isola in forma pura la tensione che attraversa ogni decisione presa in condizioni di incertezza, quella tra esplorare per imparare e sfruttare ciò che già si sa.

In questa guida vedrai da dove nasce il nome, come si formula il problema, quali sono le strategie principali per affrontarlo e, soprattutto, perché un concetto nato attorno alle slot machine oggi decide quali annunci vedi online, quali prodotti ti vengono consigliati e come vengono ottimizzati i test di un sito web.

Che cos’è il problema del bandito a più braccia

Il problema del bandito a più braccia descrive una situazione in cui devi scegliere ripetutamente tra diverse opzioni, senza sapere in anticipo quale sia la migliore. Ogni volta che scegli un’opzione ottieni una ricompensa, ma il valore medio di quella ricompensa ti è ignoto e lo puoi stimare solo provando.

In termini più formali hai un insieme di alternative, che chiamiamo braccia o leve, e un numero limitato di tentativi. A ogni tentativo scegli un braccio, ricevi una ricompensa estratta da una distribuzione di probabilità sconosciuta e propria di quel braccio, e passi al tentativo successivo. Il tuo scopo è massimizzare la ricompensa totale accumulata alla fine di tutti i tentativi.

La difficoltà sta tutta qui. Se conoscessi già quale braccio rende di più, la strategia sarebbe ovvia, giocheresti sempre quello. Ma non lo conosci, e l’unico modo per scoprirlo è spendere tentativi preziosi su braccia che potrebbero rivelarsi mediocri.

Un esempio concreto aiuta a fissare le idee. Immagina tre macchine, che chiamiamo A, B e C. La macchina A ti fa vincere in media tre volte su dieci, la B quattro volte su dieci e la C due volte su dieci, ma tu questi numeri non li conosci, li puoi solo intuire osservando i risultati. Dopo appena venti tentativi potresti aver visto la A vincere spesso per pura fortuna e convincerti che sia la migliore, quando in realtà lo è la B. Ecco perché ogni conclusione tratta da pochi dati va presa con grande prudenza.

Da dove nasce il nome

Il nome è più curioso di quanto sembri. Negli Stati Uniti la slot machine viene chiamata da tempo one-armed bandit, letteralmente bandito con un braccio solo, perché si aziona tirando una leva, il braccio, e ha la fama di svuotare le tasche di chi gioca, proprio come farebbe un bandito.

Il bandito a più braccia è quindi una slot machine immaginaria con molte leve, ciascuna con un comportamento diverso e sconosciuto. La metafora è rimasta perché cattura alla perfezione l’idea di dover scegliere tra più opzioni rischiose, ognuna con una resa incerta.

Gli ingredienti del problema

Per riconoscere un problema di bandito ovunque lo incontri ti bastano tre ingredienti. Il primo sono le braccia, cioè le azioni possibili tra cui scegliere, che possono essere due pulsanti di un sito, dieci annunci pubblicitari o mille articoli da consigliare. Il secondo è la ricompensa, un segnale numerico che misura quanto è andata bene la scelta, per esempio un clic, un acquisto o un incasso. Il terzo è il budget, ovvero il numero di tentativi o il tempo a disposizione, che è sempre limitato.

Manca però un elemento che caratterizza l’apprendimento per rinforzo nella sua forma completa, lo stato. Nel bandito classico l’ambiente non cambia in base alle tue azioni e non esiste una situazione che evolve, ogni scelta è indipendente dalle precedenti.

Proprio per questo il bandito viene spesso descritto come la porta d’ingresso al reinforcement learning, la versione più semplice in cui concentrarsi su un solo problema alla volta. Se vuoi un quadro d’insieme prima di procedere, puoi partire dalla nostra guida completa al reinforcement learning.

Il cuore del problema: esplorazione contro sfruttamento

Ogni volta che devi scegliere un braccio ti trovi davanti a un bivio. Puoi sfruttare, cioè puntare sul braccio che finora ti ha dato i risultati migliori, oppure puoi esplorare, cioè provare un braccio diverso per raccogliere informazioni e capire se nasconde qualcosa di meglio.

Sfruttare troppo presto è rischioso. Dopo pochi tentativi le tue stime sono ancora rozze, e il braccio che sembra il migliore potrebbe esserlo solo per fortuna. Rischi di restare bloccato su una scelta mediocre senza accorgerti che ne esisteva una superiore.

Esplorare troppo a lungo, però, ha un costo altrettanto concreto. Ogni tentativo speso su un braccino scadente è una ricompensa che avresti potuto ottenere e non otterrai mai. L’esplorazione si paga sempre, in gettoni, in denaro o in tempo.

Il compromesso tra questi due bisogni opposti è noto come dilemma tra esplorazione e sfruttamento, ed è il vero motore di tutto il problema. Non è un dettaglio tecnico, è la stessa logica con cui scegli se tornare al ristorante che conosci e ti piace o provarne uno nuovo di cui non sai nulla.

Abbiamo dedicato un approfondimento specifico a questo tema nell’articolo su esplorazione e sfruttamento nel reinforcement learning, utile per capire quanto questo compromesso sia universale.

Il rammarico: come si misura un buon algoritmo

Per capire se una strategia è buona serve un modo per misurarla. Nel mondo dei bandit questo strumento si chiama rammarico, in inglese regret, e ha una definizione tanto semplice quanto illuminante.

Il rammarico è la differenza tra la ricompensa che avresti ottenuto giocando sempre il braccio migliore, se solo l’avessi conosciuto dall’inizio, e la ricompensa che hai davvero accumulato con la tua strategia. In altre parole, misura quanto ti è costata l’ignoranza.

Un algoritmo perfetto avrebbe rammarico pari a zero, ma è impossibile, perché all’inizio non puoi sapere quale braccio sia il migliore senza provarne almeno qualcuno. L’obiettivo realistico è quindi far crescere il rammarico il più lentamente possibile con il passare dei tentativi.

Qui si nasconde un risultato profondo. Gli algoritmi migliori non riducono il rammarico a zero, ma lo fanno crescere in modo molto lento, all’incirca in proporzione al logaritmo del numero di tentativi invece che in proporzione ai tentativi stessi. Tradotto, più a lungo giochi più le tue scelte sbagliate diventano rare, e la quota di errori tende progressivamente ad assottigliarsi. Un classico risultato teorico degli anni Ottanta ha dimostrato che questo ritmo logaritmico è, in sostanza, il meglio a cui si possa aspirare.

Le strategie principali per risolvere il problema

Nel corso dei decenni sono state proposte molte strategie per bilanciare esplorazione e sfruttamento. Tre in particolare sono diventate dei riferimenti, perché uniscono semplicità di implementazione e ottime prestazioni. Vale la pena capirle una per una, ma prima conviene vedere perché la scelta più ovvia non funziona.

La trappola della strategia puramente avida

La strategia puramente avida consiste nel giocare sempre il braccio con la media più alta osservata fino a quel momento, senza mai esplorare. Sembra ragionevole, eppure nasconde una trappola pericolosa.

Se i primi tentativi su un braccio davvero ottimo danno per sfortuna risultati scarsi, l’algoritmo lo scarta e non lo prova mai più, restando convinto per sempre che un altro braccio sia il migliore. Senza una dose di esplorazione, un singolo colpo di sfortuna iniziale può condannarti a una scelta sbagliata per l’intera durata del gioco. Ecco perché tutte le strategie serie prevedono un meccanismo, esplicito o implicito, per continuare a mettere in discussione le proprie certezze.

La strategia epsilon-greedy

La strategia epsilon-greedy è la più intuitiva di tutte. La maggior parte delle volte scegli il braccio che al momento ha la media di ricompensa più alta, cioè sfrutti. Ogni tanto, però, con una piccola probabilità che chiamiamo epsilon, metti da parte le tue convinzioni e scegli un braccio a caso, cioè esplori.

Il parametro epsilon regola l’equilibrio. Un valore alto, per esempio il dieci per cento, ti fa esplorare spesso e imparare in fretta, ma ti fa anche sprecare molte giocate su opzioni deboli. Un valore basso ti fa sfruttare quasi sempre, con il rischio di restare ancorato a una scelta sbagliata.

Una raffinatezza molto usata consiste nel far diminuire epsilon nel tempo. All’inizio esplori molto, perché sai poco, poi riduci gradualmente l’esplorazione man mano che le tue stime diventano affidabili. È un compromesso semplice ma sorprendentemente efficace.

Il metodo Upper Confidence Bound

La strategia epsilon-greedy ha un limite, quando esplora lo fa a caso, senza distinguere tra un braccio che conosce già bene e uno che non ha quasi mai provato. Il metodo Upper Confidence Bound, spesso abbreviato in UCB, corregge proprio questo difetto.

L’idea si riassume in una frase, ottimismo di fronte all’incertezza. A ogni braccio l’algoritmo associa non solo la ricompensa media osservata, ma anche un margine di incertezza che è tanto più grande quanto meno quel braccio è stato provato. La scelta ricade sul braccio con la somma più alta tra media stimata e margine di incertezza.

Il risultato è un’esplorazione intelligente. Un braccio poco provato viene preferito non perché sembri buono, ma perché potrebbe esserlo e vale la pena verificarlo. Man mano che lo provi il suo margine di incertezza si restringe, e la scelta diventa sempre più guidata dai dati reali. UCB raggiunge quel ritmo di rammarico logaritmico di cui parlavamo, ed è per questo molto apprezzato tanto in teoria quanto nella pratica.

Il campionamento di Thompson

Il campionamento di Thompson, in inglese Thompson sampling, adotta un punto di vista diverso e sorprendentemente antico, visto che la sua idea originale risale al 1933. Invece di calcolare una singola stima, mantiene per ogni braccio un’intera distribuzione di probabilità che rappresenta quanto ritiene possibile ciascun valore di ricompensa.

Il funzionamento è quasi giocoso. A ogni tentativo l’algoritmo estrae un valore a caso dalla distribuzione di ciascun braccio, come se tirasse un dado costruito su misura per ognuno, e poi gioca il braccio che ha prodotto il valore più alto. Le braccia molto promettenti o ancora molto incerte hanno buone probabilità di essere scelte, mentre quelle chiaramente scadenti vengono via via accantonate.

Nonostante la sua età, questo metodo si comporta spesso meglio degli altri nelle prove pratiche, ed è oggi tra i più usati nei sistemi reali. La sua natura probabilistica lo rende anche naturale da adattare a contesti complessi.

Le varianti: bandit contestuali e ambienti che cambiano

Il modello di base che abbiamo descritto è potente, ma il mondo reale è più complicato. Per questo nel tempo sono nate diverse varianti del problema, pensate per situazioni specifiche.

La più importante è il bandit contestuale. Qui, prima di scegliere un braccio, ricevi delle informazioni sul contesto, per esempio l’età di un utente, il dispositivo che sta usando o la pagina che sta visitando. La ricompensa non dipende più solo dal braccio, ma anche dal contesto, e l’algoritmo deve imparare quale scelta è migliore in ciascuna situazione.

Questa variante è preziosa perché è il ponte tra il bandito classico e l’apprendimento per rinforzo completo, oltre a essere il motore della personalizzazione moderna, dai consigli sui prodotti alla pubblicità mirata.

Esistono poi altre due varianti che risolvono problemi molto concreti. Nel bandit non stazionario le distribuzioni di ricompensa cambiano nel tempo, come accade quando i gusti del pubblico evolvono, e gli algoritmi imparano a dare più peso alle osservazioni recenti. Nel bandit avversariale, invece, si rinuncia all’ipotesi che le ricompense seguano una distribuzione fissa e si progettano strategie robuste anche nel caso peggiore, quando qualcuno o qualcosa lavora contro di te.

A cosa serve davvero il multi-armed bandit

Se tutto questo ti sembra teoria astratta, è il momento di ricrederti. Il bandito a più braccia è uno dei modelli di intelligenza artificiale con più applicazioni pratiche e silenziose nella vita di ogni giorno.

Pensa alla pubblicità online. Una piattaforma deve decidere quale annuncio mostrare tra molti candidati, e vuole massimizzare i clic senza sprecare troppe visualizzazioni su annunci deboli. È esattamente un problema di bandit, spesso nella sua versione contestuale.

Lo stesso vale per i sistemi di raccomandazione. Quale prodotto, quale film o quale notizia proporre? Ogni scelta è un braccio, ogni clic o acquisto è una ricompensa, e il sistema deve continuare a esplorare le novità senza mai smettere di sfruttare ciò che funziona.

Il modello si ritrova anche in ambiti lontani dal marketing. Nelle sperimentazioni cliniche può aiutare a indirizzare più pazienti verso i trattamenti che si stanno rivelando efficaci, riducendo il numero di persone assegnate a quelli meno promettenti. Compare nella definizione dinamica dei prezzi, nell’ottimizzazione delle reti e perfino nella messa a punto dei parametri di altri modelli di apprendimento automatico.

Per un quadro più ampio di questi impieghi, che valgono per tutto l’apprendimento per rinforzo, puoi leggere la nostra panoramica su a cosa serve il reinforcement learning.

Bandit contro test A/B

Una delle applicazioni più interessanti, soprattutto per chi si occupa di siti web e marketing, è l’alternativa ai classici test A/B. Capire la differenza aiuta a scegliere lo strumento giusto al momento giusto.

In un test A/B tradizionale dividi il traffico in parti uguali tra le versioni da confrontare, per esempio due varianti di una pagina, e mantieni questa divisione fissa fino a quando hai raccolto dati sufficienti per dichiarare un vincitore con sicurezza statistica. Solo alla fine sposti tutto il traffico sulla versione migliore.

Un approccio a bandit fa qualcosa di diverso. Sposta il traffico verso la versione più promettente già durante il test, in modo continuo, riducendo così le visualizzazioni sprecate sulle varianti peggiori. In pratica impari mentre agisci, invece di aspettare la fine per raccogliere i frutti.

Non esiste un vincitore assoluto tra i due. Il test A/B resta più adatto quando ti serve una misura pulita e affidabile della differenza tra le versioni, tipica di decisioni importanti e definitive. Il bandit brilla quando l’obiettivo è massimizzare i risultati fin da subito e quando le opzioni sono molte o cambiano spesso. Conoscere entrambi ti permette di scegliere con cognizione di causa.

Dal bandito all’apprendimento per rinforzo completo

Abbiamo detto che il bandito è la porta d’ingresso al reinforcement learning. Vale la pena capire cosa manca per fare il passo successivo.

Nel bandito ogni scelta è indipendente e l’ambiente non ha memoria. Nel reinforcement learning completo, invece, compaiono gli stati, cioè le situazioni in cui si trova l’agente, e le azioni non producono solo una ricompensa immediata ma cambiano anche lo stato futuro. Una mossa può sembrare poco redditizia sul momento e rivelarsi decisiva molte scelte più avanti.

Questo salto di complessità introduce concetti come il processo decisionale di Markov e algoritmi capaci di ragionare sul lungo periodo. Se vuoi vedere come si affronta questo scenario più ricco, il passo naturale è la nostra guida al Q-learning, uno degli algoritmi fondamentali dell’apprendimento per rinforzo.

Conclusioni

Il problema del bandito a più braccia dimostra come un’idea nata giocando con le slot machine sia diventata uno strumento serio e diffusissimo. La sua forza sta nella capacità di isolare, in forma pulita, la sfida che accompagna ogni decisione presa senza informazioni complete, sapere quando insistere su ciò che funziona e quando osare qualcosa di nuovo.

Che tu stia ottimizzando una campagna pubblicitaria, progettando un sistema di raccomandazione o semplicemente cercando di capire meglio come ragionano le macchine, la logica del bandito ti offre un modo chiaro per pensare al rapporto tra rischio e conoscenza.

Se questo tema ti ha incuriosito, esplora le altre guide dedicate all’apprendimento per rinforzo qui sul sito, parti dai concetti di base e arriva agli algoritmi più avanzati. Ogni tassello che aggiungi rende più nitido il quadro complessivo dell’intelligenza artificiale che sta trasformando il mondo attorno a noi.

Newsletter gratuita · ogni venerdì

Tutta l'AI della settimana, in 5 minuti, nella tua email

• Le guide e le notizie della settimana, divise per rubrica
• Solo ciò che conta, verificato e spiegato in italiano
• Niente spam, ti cancelli con un clic

La tua email Iscriviti gratis

Ho letto l'informativa privacy e voglio ricevere la newsletter.

Preferisci i social? Seguici:

Seguici su Facebook X LinkedIn