Il problema del Multi-armed bandit è un classico problema di apprendimento per rinforzo (reinforcement learning) che richiede al giocatore di scegliere tra più “leve” (bandit arm) – ad esempio, slot machine – ognuna con una probabilità di vincita diversa ma sconosciuta. L’obiettivo è massimizzare la ricompensa totale ottenuta dopo un determinato numero di tentativi. Quindi, cos’è un bandit in questo contesto? Bandit si riferisce a ciascuna leva della slot machine, o in altre parole, a ciascuna scelta che il giocatore può fare. Ogni bandit offre un risultato casuale con una propria distribuzione di probabilità.
Questo problema presenta un dilemma: esplorazione (exploration) o sfruttamento (exploitation). Esplorare significa provare diversi bandit per trovare quello con la più alta probabilità di vincita. Sfruttare significa concentrarsi sul bandit che si ritiene sia il migliore al momento per massimizzare la ricompensa. Il bilanciamento tra esplorazione e sfruttamento è il cuore del problema del Multi-armed bandit.
Cos’è un bandit e perché questo problema è importante? Nella realtà, molti problemi possono essere modellati come un problema del Multi-armed bandit. Per esempio:
- Pubblicità online: Quale banner attirerà più clic? Ogni banner è un bandit, i clic sono la ricompensa.
- Prezzi dinamici: Quale prezzo ottimizzerà le entrate o i profitti? Ogni prezzo è un bandit, le entrate/profitti sono la ricompensa.
- Sistemi di raccomandazione: Quale prodotto dovrebbe essere raccomandato all’utente? Ogni prodotto è un bandit, la soddisfazione dell’utente è la ricompensa.
- Sperimentazioni cliniche: Quale trattamento è il più efficace e con meno effetti collaterali? Ogni trattamento è un bandit, l’efficacia del trattamento è la ricompensa.
Per risolvere il problema del Multi-armed bandit, sono stati sviluppati molti algoritmi, ognuno con un proprio approccio per bilanciare esplorazione e sfruttamento. Alcuni algoritmi comuni includono:
- Algoritmo ingenuo (Naive Algorithm): Prova ogni bandit un numero fisso di volte, quindi scegli il bandit con la ricompensa media più alta.
- Algoritmo ε-Greedy: Con probabilità ε, scegli un bandit casuale per esplorare; con probabilità 1-ε, scegli il bandit con la ricompensa media più alta per sfruttare.
- Algoritmo UCB (Upper Confidence Bound): Scegli il bandit con il limite di confidenza superiore più alto, combinando la ricompensa media e l’incertezza della stima.
- Algoritmo Thompson Sampling: Utilizza una distribuzione di probabilità bayesiana per stimare la ricompensa di ogni bandit e sceglie il bandit in base alla probabilità che sia il migliore.
Ogni algoritmo ha i suoi vantaggi e svantaggi e la sua efficacia dipende dalle specifiche caratteristiche del problema. Capire cos’è un bandit e gli algoritmi correlati aiuta a scegliere il metodo appropriato per ottimizzare le decisioni in situazioni di incertezza.
Video introduttivo sul funzionamento di UCB
La scelta tra questi algoritmi dipende dal problema specifico e dai requisiti di prestazioni computazionali. Ad esempio, il Thompson Sampling è spesso più efficace dell’UCB nelle applicazioni del mondo reale con grandi quantità di dati e requisiti di elaborazione in tempo reale.
