Il problema del multi-armed bandit (MAB) è una sfida ben nota nell'apprendimento per rinforzo, nel processo decisionale e nella teoria della probabilità. Coinvolge un agente che sceglie ripetutamente tra più azioni, ognuna delle quali offre una ricompensa proveniente da una distribuzione di probabilità fissa. L'obiettivo è massimizzare il rendimento in un numero fisso di passi temporali.

Origine del problema

Il termine "multi-armed bandit" deriva dall'analogia con una slot machine, spesso chiamata "one-armed bandit" a causa della sua leva. In questo scenario, si immagini di avere più slot machine, o una slot machine dotata di più leve (bracci), e ogni braccio è associato a una distribuzione di probabilità distinta per le ricompense. L'obiettivo è massimizzare il rendimento in un numero limitato di tentativi scegliendo con attenzione quale leva tirare.

La sfida

Il problema MAB rappresenta la sfida di bilanciare esplorazione e sfruttamento:

• Esplorazione: provare diverse leve per raccogliere informazioni sui loro pagamenti;
• Sfruttamento: tirare la leva che attualmente sembra la migliore per massimizzare le ricompense immediate.

Un approccio ingenuo — giocare ripetutamente una sola leva — può portare a rendimenti subottimali se esiste una leva migliore che rimane inesplorata. Al contrario, un'eccessiva esplorazione può sprecare risorse su opzioni a basso rendimento.

Applicazioni nel mondo reale

Sebbene inizialmente concepito nel contesto del gioco d'azzardo, il problema MAB si presenta in numerosi settori:

• Pubblicità online: selezione del miglior annuncio da mostrare in base all'interazione degli utenti;
• Studi clinici: sperimentazione di diversi trattamenti per individuare il più efficace;
• Sistemi di raccomandazione: proposta dei contenuti più rilevanti agli utenti.