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 ritorno su 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 con più leve (bracci), e ogni braccio è associato a una distribuzione di probabilità distinta per le ricompense. L'obiettivo è massimizzare il ritorno su un numero limitato di tentativi scegliendo con attenzione quale leva tirare.

La Sfida

Il problema MAB rappresenta la sfida di bilanciare esplorazione ed exploitation:

• Esplorazione: provare diverse leve per raccogliere informazioni sui loro pagamenti;
• Exploitation: 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 ma non viene esplorata. Al contrario, un'esplorazione eccessiva può sprecare risorse su opzioni a basso rendimento.

Applicazioni nel Mondo Reale

Sebbene originariamente inquadrato nel gioco d'azzardo, il problema MAB si presenta in molti settori:

• Pubblicità online: selezione del miglior annuncio da mostrare in base al coinvolgimento dell'utente;
• Studi clinici: test di più trattamenti per individuare il più efficace;
• Sistemi di raccomandazione: proposta dei contenuti più rilevanti agli utenti.