Multi-Armed Bandit: Cos’è, Come Funziona e Perché Sostituisce l’A/B Testing

import random

# --------------------------------------------------
# PARAMETRI
# --------------------------------------------------

PROBS = [0.30, 0.50, 0.80]
NAMES = ["A", "B", "C"]
EPSILON = 0.10
T = 1000
MU_STAR = max(PROBS)

# --------------------------------------------------
# STATO DELL'AGENTE
# --------------------------------------------------

counts = [0] * len(PROBS)
rewards = [0] * len(PROBS)

# --------------------------------------------------
# FUNZIONI
# --------------------------------------------------

def estimated_mean(arm):
    """Media empirica stimata."""
    if counts[arm] == 0:
        return 0
    return rewards[arm] / counts[arm]

def choose_arm():
    """
    Epsilon-Greedy con inizializzazione corretta.
    Ogni braccio viene provato almeno una volta.
    """
    for arm in range(len(PROBS)):
        if counts[arm] == 0:
            return arm

    if random.random() < EPSILON:
        # EXPLORATION
        return random.randrange(len(PROBS))

    # EXPLOITATION
    return max(range(len(PROBS)), key=estimated_mean)
 
def pull(arm):
    """
    Simula il ristorante.
    Restituisce:
        1 = cliente soddisfatto
        0 = cliente insoddisfatto
    """
    return 1 if random.random() < PROBS[arm] else 0 
# -------------------------------------------------- 
# SIMULAZIONE 
# -------------------------------------------------- 
cum_reward = 0 
regret_theoretical = 0 
print(f"{'Step':>6} | {'Arm':^5} | {'Reward':^6} | {'CumReward':>10} | {'Regret':>8}")
print("-" * 60)

for t in range(1, T + 1):
    arm = choose_arm()
    reward = pull(arm)
    counts[arm] += 1
    rewards[arm] += reward
    cum_reward += reward
    regret_theoretical += MU_STAR - PROBS[arm]

    if t == 1 or t % 100 == 0:
        means = " | ".join(f"{NAMES[i]}={estimated_mean(i):.2f}" for i in range(len(PROBS)))
        print(f"{t:>6} | {NAMES[arm]:^5} | {reward:^6} | {cum_reward:>10} | {regret_theoretical:>8.2f}")
        print("       Stime:", means)

 

# --------------------------------------------------
# RISULTATI FINALI
# --------------------------------------------------

print("\n" + "=" * 60)
print("RISULTATI FINALI")
print("=" * 60)

print(f"\nTentativi totali : {T}")
print(f"Epsilon          : {EPSILON}")
print(f"Reward totale    : {cum_reward}")
print(f"Ottimo teorico   : {MU_STAR * T:.0f}")
print(f"Regret teorico   : {regret_theoretical:.2f}")
efficiency = (cum_reward / (MU_STAR * T)) * 100
print(f"Efficienza       : {efficiency:.1f}%")

print("\nDistribuzione scelte:\n")
for i in range(len(PROBS)):
    pct = counts[i] / T * 100
    bar = "█" * int(pct / 2)
    print(f"{NAMES[i]} ({PROBS[i]*100:.0f}%) → {counts[i]:4d} scelte ({pct:5.1f}%) {bar}")
    print(f"    Stima finale: {estimated_mean(i):.3f}")

best_arm = counts.index(max(counts))
print(f"\nBraccio preferito: {NAMES[best_arm]}")
print(f"Probabilità reale: {PROBS[best_arm]*100:.0f}%")

# --------------------------------------------------
# FORMULE
# --------------------------------------------------

print("\n" + "-" * 60)
print("FORMULE")

print("\nMedia stimata:")
print("mu_hat = successi / tentativi")

print("\nRegret teorico:")
print("R(T) = Σ (μ* - μ_a)")

print("\nReward cumulativo:")
print("Reward(T) = Σ r_t")

Altri algoritmi più sofisticati

• Upper Confidence Bound (UCB): sceglie il braccio che massimizza una combinazione di ricompensa media e incertezza. Penalizza i bracci poco esplorati dando loro un bonus di esplorazione che diminuisce con il numero di prove.
• Thompson Sampling: approccio bayesiano. Mantiene una distribuzione di probabilità sulla vera ricompensa di ciascun braccio e campiona da essa. È spesso lo stato dell’arte per molti problemi.
• Gradient Bandit e algoritmi basati su policy gradient.

for arm in range(len(PROBS)):
    if counts[arm] == 0:
        return arm

Metriche di performance

Per valutare un algoritmo bandit è essenziale monitorare tre grandezze:

Reward cumulativo

[math]R_t = \sum_{i=1}^{t} r_i[/math]
Misura quanto valore abbiamo accumulato fino al tempo [math]t[/math].

Frequenza di scelta dei bracci

Dopo molte iterazioni dovremmo vedere una distribuzione fortemente sbilanciata verso il braccio migliore.

Ad esempio:

Regret (il rimpianto)

La metrica più importante nella letteratura scientifica:
[math]\text{Regret}(T) = T \mu^* – \sum_{t=1}^{T} r_t[/math]
dove [math]\mu^*[/math] è la ricompensa attesa del braccio ottimale.

Il regret misura quanto abbiamo “perso” rispetto all’oracolo che conosceva fin dall’inizio la macchina migliore.

Un buon algoritmo ha un regret che cresce logaritmicamente con [math]T[/math] (sublineare), anziché linearmente.

Simulazioni: cosa osservare nella pratica

Quando si implementa una simulazione di Multi-Armed Bandit , è istruttivo osservare:

• Come il regret cresce nel tempo per diversi algoritmi.
• La velocità con cui l’algoritmo identifica il braccio migliore.
• Il comportamento con distribuzioni di reward diverse (Bernoulliane, Gaussiane, non stazionarie).
• L’effetto del parametro [math]\epsilon[/math]: valori troppo alti portano a troppo rumore, valori troppo bassi a convergenza lenta o sub-ottima.

In una tipica simulazione con i tre ristoranti, dopo poche centinaia di iterazioni l’algoritmo epsilon-greedy o Thompson Sampling sceglie il ristorante C oltre l’80-90% delle volte.

Applicazioni reali del Multi-Armed Bandit

Il problema MAB è ovunque nella vita moderna:

• A/B Testing e ottimizzazione web: invece di test fissi, si usano algoritmi bandit per allocare più traffico alla versione migliore mentre il test è ancora in corso (Contextual Bandits).
• Recommendation Systems: Netflix, YouTube, Spotify usano varianti di bandit per bilanciare novità e preferenze consolidate.
• Pubblicità online (Ad Tech): scegliere quale annuncio mostrare a un utente in tempo reale.
• Trial clinici: allocare pazienti ai trattamenti più promettenti riducendo il numero di persone che ricevono terapie inefficaci.
• Robotica e controllo: un robot deve esplorare l’ambiente senza trascurare compiti noti.
• Finanza: portfolio optimization sotto incertezza.
• Personalizzazione dell’istruzione: sistemi di tutoring adattivi.

Varianti avanzate

• Contextual Bandits: i bracci dipendono dal contesto (es. caratteristiche dell’utente). È il modello dietro molti sistemi di raccomandazione moderni.
• Non-stationary Bandits: le probabilità cambiano nel tempo (es. preferenze dei clienti che evolvono).
• Combinatorial Bandits: scegliere più bracci contemporaneamente (es. assortimento di prodotti).
• Bandits con grafi o relazioni: quando esiste una struttura tra le opzioni.

Perché è fondamentale per la Scienza dei Dati

Il Multi-Armed Bandit insegna una lezione profonda: l’apprendimento ottimale non è mai solo esplorazione né solo sfruttamento. È una danza continua tra curiosità e pragmatismo.

Nell’era dei Big Data e dell’AI, dove le decisioni devono essere prese in tempo reale con informazioni parziali, padroneggiare i bandit significa passare da un approccio “testa tutto e poi scegli” a un approccio sequenziale e adattivo, molto più efficiente.

Inoltre, il concetto di regret fornisce un framework matematico rigoroso per quantificare il costo dell’incertezza, fondamentale sia nella ricerca teorica che nelle applicazioni aziendali.

Conclusione

Il problema del Multi-Armed Bandit è importante perché cattura l’essenza dell’intelligenza: prendere decisioni buone in un mondo incerto, con informazioni limitate e costi per l’esperimento. Dal semplice epsilon-greedy fino agli algoritmi bayesiani più sofisticati, la famiglia dei bandit offre strumenti potenti, eleganti e sorprendentemente pratici.

Che tu stia ottimizzando una campagna marketing, progettando un sistema di raccomandazione o semplicemente cercando di prendere decisioni migliori nella vita, capire exploration vs exploitation ti dà un vantaggio cognitivo enorme.

La prossima volta che devi scegliere un ristorante in una città nuova, ricordati: stai risolvendo un Multi-Armed Bandit. E con gli algoritmi giusti, puoi massimizzare la tua soddisfazione cumulativa nel corso della vita.