Multi-armed bandits

Davanti a K leve di slot machine, ognuna con un payout ignoto, qual è la sequenza di pull che massimizza le vincite? È la versione minimale di ogni decisione sequenziale sotto incertezza: il dilemma esplorazione-sfruttamento ridotto al suo nucleo, e il punto di partenza obbligato per chiunque voglia capire come un agente impara ad agire.

Perché questo capitolo

Il problema dei multi-armed bandit è il setting più semplice possibile dove un agente deve agire e imparare insieme. Niente stato, niente transizioni, niente discount factor. Solo K azioni, una reward dopo ogni scelta, un orizzonte. Eppure dentro a questa semplicità vive il dilemma centrale del reinforcement learning: ogni step in cui scegli un braccio è un’opportunità persa di provare gli altri, e ogni step in cui esplori è una rinuncia consapevole alla scelta che oggi sembra migliore. Capire come gestire questo trade-off è la condizione per capire cose molto più complicate — MDP, Q-learning, policy gradient, RLHF.

Il capitolo serve due funzioni nella struttura del libro. Prima: chiude la Parte V (teoria dei giochi e decisioni) con il primo problema veramente “online”, in cui le decisioni vengono prese in sequenza e l’algoritmo non vede mai il modello vero del mondo. Dopo i giochi a informazione completa di equilibrio-nash e minimax, e il mechanism design di meccanismi-aste, i bandits sono il bridge verso decisioni sotto incertezza che caratterizzano la teoria dell’apprendimento sequenziale. Seconda: prepara il terreno per i prossimi capitoli su MDP (markov-decision-process in preparazione) e su algoritmi RL completi (Q-learning, actor-critic, PPO, tutti in preparazione).

Ma c’è una terza ragione, più operativa. I bandit non sono solo un giocattolo didattico: sono lo strumento attivo dietro cose che usi tutti i giorni. Monte Carlo Tree Search di AlphaZero usa UCB1 ad ogni nodo. A/B testing dinamico di Microsoft, Yahoo, Optimizely è contextual bandit. Reward modeling in RLHF è formalizzabile come dueling bandit. Hyperparameter tuning con Hyperband è bandit. La selezione di tool da parte di un agente LLM — quando Claude Code decide tra Read, Bash, Grep — può essere modellata come contextual bandit dove il contesto è il task. Un capitolo sui bandit, fatto bene, dà al lettore l’apparato concettuale per riconoscere lo stesso pattern in mille travestimenti.

Contesto

Una manciata di nomi e date orientano il campo.

• William R. Thompson (statistico medico, americano): nel 1933 pubblica On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples su Biometrika. Lavora sul problema clinico di assegnare pazienti a trattamenti alternativi quando l’efficacia è ignota. Inventa il Thompson sampling: campiona dalla distribuzione a posteriori, scegli il braccio col campione più alto. Il paper rimane praticamente dimenticato per ottant’anni.
• Herbert Robbins (statistico americano, Columbia): nel 1952 con Some Aspects of the Sequential Design of Experiments (Bulletin of the American Mathematical Society) riformula il problema in chiave moderna. È lui che porta nella letteratura accademica l’espressione “multi-armed bandit”, per analogia con le slot machine (“one-armed bandit” era il soprannome popolare).
• Tze Leung Lai e ancora Robbins: nel 1985 con Asymptotically Efficient Adaptive Allocation Rules (Advances in Applied Mathematics) dimostrano il lower bound logaritmico: per qualunque algoritmo “uniformly good”, il regret cresce almeno come Ω(log T). Nessuno può fare meglio asintoticamente.
• Peter Auer (informatico austriaco, JKU Linz), Nicolò Cesa-Bianchi (informatico italiano, Università degli Studi di Milano), Paul Fischer: nel 2002 con Finite-time Analysis of the Multiarmed Bandit Problem (Machine Learning) introducono UCB1, la regola più semplice che raggiunge regret O(K log T) in tempo finito, con costanti esplicite. È il paper di riferimento dell’analisi moderna dei bandits stocastici.
• Auer, Cesa-Bianchi, Yoav Freund (informatico americano, UCSD), Robert Schapire (informatico americano, Princeton/MSR): nel 2002 sullo SIAM Journal on Computing pubblicano The Nonstochastic Multiarmed Bandit Problem, dove introducono EXP3 per il setting adversarial. Regret O(√(KT log K)) senza assunzioni sulla distribuzione.
• Levente Kocsis e Csaba Szepesvári (informatici ungheresi): nel 2006 con Bandit Based Monte-Carlo Planning (ECML) estendono UCB1 ad alberi di ricerca, definendo UCT. Da qui in dritta su AlphaGo (Silver 2016) e AlphaZero (Silver 2017).
• Lihong Li, Wei Chu, John Langford, Robert Schapire: nel 2010 con A Contextual-Bandit Approach to Personalized News Article Recommendation (WWW ‘10) definiscono e applicano LinUCB alla home page di Yahoo. Primo deployment large-scale di contextual bandits.

Decoder dei termini base che useremo, prima menzione di ognuno qui:

• Bandit (in senso tecnico): protocollo in cui ad ogni istante si sceglie un’azione tra K, si osserva una reward, e si vuole massimizzare la somma cumulata.
• Braccio (arm): ogni azione possibile. Termine ereditato dalle slot machine.
• Reward: il valore osservato dopo aver tirato un braccio. Tipicamente in [0,1] o reale.
• Regret: differenza in expectation tra la reward del genio (sempre il braccio migliore) e la reward dell’algoritmo. Misura quanto “perdiamo per non aver saputo”.
• Esplorazione (exploration): tirare bracci diversi per imparare i loro payout.
• Sfruttamento (exploitation): tirare il braccio che attualmente sembra migliore.
• i.i.d. (independent and identically distributed): le reward di un braccio sono campioni indipendenti dalla stessa distribuzione, fissa nel tempo.
• Contextual bandit: variante in cui prima di scegliere si osserva un contesto x_t, e la reward dipende da (x_t, azione).

I bandit nascono storicamente in biostatistica medica (Thompson 1933, contesto: assegnazione trattamenti) prima di diventare un oggetto di studio in operations research (Robbins 1952), poi in informatica teorica (Auer 1995-2002), e infine in produzione su larga scala (Yahoo News 2010, Microsoft, Optimizely). Le applicazioni sono cambiate, la matematica essenzialmente no. Cross-reference verso il resto della Parte V: useremo intuizioni di probabilita-base (valore atteso, varianza), bayes-base (posterior aggiornata, prior coniugata) e bias-varianza (l’incertezza statistica è una varianza che decresce con n).

L’intuizione

Angolo 1: la slot machine multipla

Sei in un casinò con dieci slot machine. Ognuna ha un payout medio sconosciuto. Hai 5000 monete. Come le spendi?

La strategia “tutta esplorazione” — 500 pull a ognuna — ti dà ottime stime delle medie ma spreca metà delle monete su macchine palesemente perdenti. La strategia “tutto sfruttamento” — tira la prima leva 5000 volte — è disastrosa se per sfortuna hai cominciato dalla peggiore. La strategia ε-greedy — il 90% dei pull sul “miglior candidato attuale”, il 10% a caso — è meglio di entrambe, ma non sa mai “smettere di esplorare”: continua a tirare bracci ovviamente perdenti per il 10% del budget anche al milionesimo step.

Il punto è che la quantità giusta di esplorazione decresce nel tempo, ma in modo non banale. All’inizio ogni braccio merita un pull perché non sai nulla. Dopo molti pull, un braccio con stima 0.3 e standard error 0.01 non merita più altri pull se il leader è 0.7 con standard error 0.02. Devi bilanciare la stima con la sua incertezza. Il bonus di esplorazione deve essere proporzionale all’incertezza, non costante.

UCB1 rende esplicita questa intuizione: il “valore” di un braccio è la stima più un termine di esplorazione che decresce come 1/√n_i. Bracci poco visti hanno un grande bonus, bracci molto visti hanno un bonus piccolo. Il braccio scelto è quello con la somma più alta — non semplicemente il più visto né il più ignoto, ma quello che ha la migliore combinazione di “potrebbe essere buono” + “potrebbe ancora sorprendermi”.

Angolo 2: il “non sapere ancora” come risorsa

Cambia lente. Non pensare ai bracci come oggetti con un valore intrinseco, ma alle tue credenze su di loro come oggetto che evolve. All’inizio le credenze sono uniformi, totalmente ignoranti. Ogni pull è un’osservazione che restringe l’incertezza su quel braccio.

In ottica bayesiana questo è letterale: ogni braccio ha una distribuzione a posteriori sulla sua media. All’inizio prior uniforme (Beta(1,1) per Bernoulli, normale ampia per Gaussian). Dopo n pull con somma s, il posterior diventa Beta(1+s, 1+n−s). Più stretto, più informato. Il posterior incorpora già l’incertezza in modo automatico.

Thompson sampling sfrutta questa rappresentazione: ad ogni step, campiona un valore di media da ogni posterior, scegli il braccio col campione più alto. L’azione è probabilistica perché lo stato di credenza è probabilistico. Bracci con posterior strette finiscono per essere campionati su valori vicini alla loro media stimata (poca incertezza, poca variabilità). Bracci con posterior larghe possono campionare valori alti per puro caso e quindi finire scelti — ed è esattamente l’esplorazione che vorremmo.

C’è una proprietà filosofica notevole. Thompson sampling è probability matching: la probabilità che l’algoritmo scelga il braccio i è esattamente la probabilità (sotto il posterior corrente) che il braccio i sia il migliore. Niente arbitrario, niente costanti da tunare. È la regola di Bayes che decide.

Angolo 3: ottimismo davanti all’incertezza

Una terza lente, più filosofica e più direttamente collegata a UCB. Considera due bracci: A con stima 0.6 e 100 pull, B con stima 0.55 e 5 pull. Il leader è A. Ma B è quasi alla pari, e con così pochi pull la sua media potrebbe in realtà essere 0.7. L’intervallo di confidenza superiore di B è alto perché la sua incertezza è alta.

UCB sceglie il braccio con il bound superiore più alto. Sostiene un atteggiamento epistemico ben preciso: “agisci come se il mondo fosse il più favorevole compatibile con i tuoi dati”. Se sbagli sull’ottimismo, scopri presto che il braccio non è così buono (l’evidenza si accumula). Se non sbagli, ottieni un guadagno. È un trade-off asimmetrico: l’errore “ottimista” si autocorregge rapidamente, l’errore “pessimista” no, perché smetti di esplorare il braccio sospetto e non scopri mai se aveva ragione il sospetto.

ANALOGIA filosofica: questo principio — optimism in the face of uncertainty — è uno dei più portanti in tutto il reinforcement learning. Compare in UCB1, in UCB-tree (UCT), in posterior sampling, in optimistic initialization, in count-based exploration con neural nets. È la versione tecnica del proverbio “chi non risica non rosica”, ma con un teorema dietro.

La meccanica

Formulazione formale

Sia K il numero di bracci. Per ogni i ∈ {1, …, K} sia P_i una distribuzione di reward su [0, 1] (per semplicità) con media μ_i sconosciuta. Sia μ* = max_i μ_i e i* = arg max_i μ_i. Sia Δ_i = μ* − μ_i il gap del braccio i (Δ_i ≥ 0, con Δ_{i*} = 0).

Ad ogni step t = 1, …, T:

1. l’algoritmo sceglie a_t ∈ {1, …, K},
2. estrae r_t ∼ P_{a_t} e lo osserva,
3. aggiorna il proprio stato.

Il regret cumulativo è:

R_T = T · μ* − E[Σ_{t=1}^T r_t]

Equivalentemente, per linearità dell’aspettativa, è il pseudo-regret:

R_T = Σ_{i=1}^K Δ_i · E[N_i(T)]

dove N_i(T) è il numero di volte che il braccio i è stato tirato fino allo step T. La forma pseudo-regret è informativa: il regret è la somma, su tutti i bracci subottimi, di “quante volte li ho tirati × quanto sono peggio del migliore”.

Una buona strategia bandit deve garantire che N_i(T) cresca lentamente per i ≠ i*. Quanto lentamente? Il prossimo risultato risponde.

Lower bound di Lai-Robbins

TEOREMA (Lai-Robbins 1985). Per ogni algoritmo “uniformly good” su una famiglia di distribuzioni one-parameter exponential, e per ogni istanza con bracci subottimali,

lim inf_{T→∞} R_T / log T ≥ Σ_{i: Δ_i > 0} Δ_i / D_KL(P_i, P_{i*})

dove D_KL è la divergenza di Kullback-Leibler. In particolare R_T = Ω(log T): nessun algoritmo può avere regret sub-logaritmico.

L’intuizione del teorema: per essere sicuri che un braccio i sia subottimo serve raccogliere abbastanza evidenza statistica da escludere che la sua media sia vicina a μ*. Ma “abbastanza evidenza” è una funzione log T (se vuoi affidabilità 1 − 1/T) divisa per la KL-divergence (quanto velocemente l’evidenza si accumula). Il prezzo dell’esplorazione è incomprimibile.

ε-greedy

Strategia più semplice. Ad ogni step:

• con probabilità ε scegli un braccio uniformemente a caso (esplora),
• con probabilità 1 − ε scegli arg max_i μ̂_i (sfrutta).

Dove μ̂_i è la media campionaria delle reward osservate per il braccio i.

Pro: implementazione in 5 righe. Funziona ragionevolmente bene in molti casi pratici.

Contro: se ε è costante, ad ogni step c’è probabilità ε/(K) di tirare ognuno dei bracci subottimali, quindi N_i(T) ≈ ε · T / K. Sostituendo nella pseudo-regret formula: R_T = Θ(T). Lineare. Non match con il lower bound logaritmico.

Variante ε_t = c/t (decrescente): si dimostra regret O(K log T / Δ²_min) sotto condizioni — match logaritmico, ma costanti peggiori di UCB1 in pratica e tunare c richiede conoscenza di Δ_min.

In pratica ε-greedy con ε ≈ 0.05-0.1 è la baseline standard. Quando vince UCB1 di poco, vale la pena la complessità extra.

UCB1: la derivazione del bonus

UCB1 sceglie

a_t = arg max_i [ μ̂_i(t) + √( 2 ln t / n_i(t) ) ]

dove n_i(t) è il numero di pull del braccio i fino allo step t e μ̂_i la sua media campionaria.

Il termine √(2 ln t / n_i) è l’upper confidence bound sulla media. Da dove viene? Dalla disuguaglianza di Hoeffding: per reward in [0,1] e n campioni i.i.d. di un braccio con media μ,

P(|μ̂ − μ| ≥ ε) ≤ 2 exp(−2 n ε²)

Vogliamo un ε tale che questa probabilità sia ≤ 1/t² (così via union bound su tutti gli step e bracci la probabilità di un fallimento totale è ≤ K/t — trascurabile asintoticamente). Imponiamo

2 exp(−2 n ε²) ≤ 1/t² ⟹ ε² ≥ ln(2 t²) / (2 n) ⟹ ε ≈ √(ln t / n)

A meno di costanti, è il bonus di UCB1. Il “2” davanti al ln t bilancia esattamente la probability mass cumulativa della union bound.

TEOREMA (Auer-Cesa-Bianchi-Fischer 2002). Per reward in [0,1], il regret di UCB1 soddisfa:

R_T ≤ 8 Σ_{i: Δ_i > 0} ln T / Δ_i + (1 + π²/3) Σ_i Δ_i

In notazione asintotica O(K ln T / Δ_min). Match con il lower bound a meno di una costante (8 invece di 1/D_KL, che per Bernoulli vicine può essere notevolmente più piccolo, ma è una costante).

Pseudocodice:

import numpy as np

def ucb1(env, K, T):
    mu_hat = np.zeros(K)
    n = np.zeros(K)
    rewards = []
    for t in range(1, T + 1):
        if t <= K:
            a = t - 1                            # un pull a ogni braccio
        else:
            bonus = np.sqrt(2 * np.log(t) / n)
            a = int(np.argmax(mu_hat + bonus))
        r = env.pull(a)
        n[a] += 1
        mu_hat[a] += (r - mu_hat[a]) / n[a]      # media incrementale
        rewards.append(r)
    return rewards

Tre dettagli pratici. Primo: la fase iniziale (un pull per braccio) è obbligatoria, altrimenti n_i = 0 al denominatore. Secondo: la media è aggiornata in forma incrementale per evitare overflow. Terzo: numericamente, per t molto grande il bonus diventa minuscolo e UCB1 si comporta quasi greedy — è atteso, riflette che l’incertezza è scesa.

Thompson sampling

Algoritmo:

1. Mantieni un posterior P_t(μ_i) per ogni braccio.
2. Ad ogni step: campiona θ_i ∼ P_t(μ_i) per ogni i, scegli a_t = arg max_i θ_i.
3. Osserva r_t, aggiorna il posterior del braccio a_t.

Per Bernoulli con prior coniugato Beta(1, 1):

import numpy as np

def thompson_bernoulli(env, K, T, rng=None):
    rng = rng or np.random.default_rng()
    alpha = np.ones(K)
    beta = np.ones(K)
    rewards = []
    for t in range(T):
        theta = rng.beta(alpha, beta)
        a = int(np.argmax(theta))
        r = env.pull(a)
        alpha[a] += r
        beta[a] += 1 - r
        rewards.append(r)
    return rewards

Per Gaussian con varianza nota σ² e prior N(0, σ_0²): posterior N(μ_n, σ_n²) chiuso. Per modelli più complessi (LinUCB neuralizzato, modelli generativi) si ricorre a Laplace approximation, MCMC, o variational inference.

Risultati teorici principali:

• TEOREMA (Russo-Van Roy 2014): regret bayesiano O(√(KT log T)).
• TEOREMA (Agrawal-Goyal 2013): regret frequentista O(K log T / Δ_min) per Bernoulli, matching UCB1 e il lower bound.

In pratica Thompson sampling spesso vince con un fattore costante 2-3× su UCB1, soprattutto su orizzonti corti e con poca informazione iniziale.

EXP3 per il caso adversarial

Quando le reward non sono i.i.d. ma scelte da un avversario, UCB1 e Thompson possono fallire. EXP3 (Auer-Cesa-Bianchi-Freund-Schapire 2002) lavora senza assunzioni stocastiche.

Idea: mantieni un peso w_i per ogni braccio. Ad ogni step:

1. p_i = (1 − γ) · w_i / Σ_j w_j + γ / K (mix con uniforme per garantire esplorazione minima)
2. campiona a_t ∼ p
3. ricevi r_t (l’avversario può scegliere come vuole)
4. aggiorna w_{a_t} ← w_{a_t} · exp(γ · (r_t / p_{a_t}) / K)

L’aggiornamento moltiplicativo (con fattore importance-weighted r_t / p_{a_t}) è l’ingrediente chiave: i bracci buoni accumulano peso esponenzialmente, ma la randomizzazione p_i ≥ γ/K garantisce che ogni braccio venga toccato con probabilità non-zero.

TEOREMA: il regret rispetto al miglior braccio fisso in retrospettiva è O(√(KT log K)). Notare la radice (peggio del log dello stocastico): è il prezzo del setting adversarial.

EXP3 è il bandit-feedback equivalente di Hedge / multiplicative weights nel framework di Freund-Schapire 1997.

Il setting adversarial sembra estremo ma cattura situazioni reali: un agente di trading dove gli altri partecipanti reagiscono alle tue azioni; un’asta dove i co-bidder modificano la strategia in funzione delle tue mosse; un sistema di moderazione dove gli utenti malintenzionati cambiano comportamento per gaming la policy. In questi scenari assumere i.i.d. è esattamente sbagliato — l’avversario cerca attivamente la tua debolezza statistica. EXP3 è la garanzia minima che si può ottenere senza assunzioni: non promette di battere il braccio migliore in ogni istante, ma promette di non fare molto peggio del miglior braccio fisso scelto in retrospettiva. È una forma di regret nei confronti del miglior expert statico, che è la lente standard del competitive online learning.

Contextual bandits: LinUCB

Variante: ad ogni step osservi un contesto x_t ∈ R^d prima di scegliere a_t. La reward attesa dipende da (x_t, a_t). LinUCB (Li et al. 2010) assume modello lineare:

E[r_t | x_t, a_t = a] = x_t^T θ_a

Stima θ_a via ridge regression sui dati raccolti finora del braccio a. Sceglie:

a_t = arg max_a [ x_t^T θ̂_a + α · √(x_t^T A_a^{-1} x_t) ]

dove A_a = X_a^T X_a + λ I è la matrice di design ridge per il braccio a. Il primo termine è la stima lineare, il secondo è la confidenza (cresce per direzioni x_t mai esplorate per quell’azione).

In produzione (Yahoo News 2010): +12.5% click-through rate su uno dei pochi A/B test pubblicati di bandit large-scale. Il dato è particolarmente significativo perché contesta la presunzione comune che algoritmi più sofisticati offrano guadagni marginali — il salto da ε-greedy a contextual bandit con modello lineare è netto.

flowchart LR
    A[Contesto utente x_t] --> B[Estrazione feature]
    B --> C[Reward model per braccio: x_t^T theta_a]
    C --> D[Selezione UCB: argmax sui bracci]
    D --> E[Mostra item all'utente]
    E --> F[Osserva reward r_t<br/>click / no-click]
    F --> G[Aggiorna theta_a via ridge regression]
    G --> C

Figura 5 — pipeline di un contextual bandit lineare — feature dell’utente, score per braccio, selezione UCB, observation del reward, update via ridge regression

Estensioni naturali. Kernelized bandit / GP-UCB (Srinivas et al. 2010): la reward attesa è modellata come Gaussian process, generalizzazione non parametrica di LinUCB. Connessione diretta con Bayesian optimization, alla base di tool come Spearmint, Vizier, Optuna. Neural bandit: la stima di reward è una rete neurale; la covarianza arriva via NTK approximation o ensemble. Promettente in alta dimensionalità ma costoso in compute.

Esempi

Esempio 1: tre bracci Bernoulli, primo step di UCB1 a mano

Tre bracci con p reali (sconosciute all’algoritmo) p_1 = 0.7, p_2 = 0.5, p_3 = 0.3.

Inizializzazione (t = 1, 2, 3): un pull per braccio. Supponiamo per sfortuna r = (1, 0, 1): il braccio 3 ha avuto fortuna iniziale.

Stato a t = 4:

• μ̂ = (1.0, 0.0, 1.0)
• n = (1, 1, 1)

Bonus di esplorazione: √(2 ln 4 / 1) = √(2 · 1.3863) = √2.7726 ≈ 1.665

UCB bound:

• braccio 1: 1.0 + 1.665 = 2.665
• braccio 2: 0.0 + 1.665 = 1.665
• braccio 3: 1.0 + 1.665 = 2.665

Pareggio tra 1 e 3. Tie-breaking arbitrario (es. indice più basso) → braccio 1.

Step t = 4: tira il braccio 1, supponiamo r = 1. Stato:

• μ̂ = (1.0, 0.0, 1.0), n = (2, 1, 1)

Bonus a t = 5: √(2 ln 5 / n) = (√(2 · 1.6094 / 2), √(2 · 1.6094 / 1), √(2 · 1.6094 / 1)) = (1.269, 1.794, 1.794).

Bound: (2.269, 1.794, 2.794). Vince braccio 3.

Asintoticamente: μ̂_3 → 0.3 (la fortuna iniziale viene diluita), il bonus √(2 ln t / n) decresce, UCB1 finisce per concentrare i pull sul braccio 1.

Esempio 2: simulazione 10-armed Gaussian (banco prova classico)

Setup à la Sutton-Barto cap. 2: K = 10, μ_i ∼ N(0, 1) (estratte una volta all’inizio), reward al pull r ∼ N(μ_{a}, 1). Orizzonte T = 5000. Mediato su 200 esecuzioni.

Risultati tipici (regret cumulativo R_T):

• ε-greedy ε = 0.1: ≈ 80
• UCB1 (con costante c = √2): ≈ 50
• Thompson sampling (prior N(0, 1)): ≈ 45

Curve nel tempo:

• ε-greedy: cresce circa linearmente (asintoto Δ_avg · ε)
• UCB1: log(t)
• Thompson: log(t), costante migliore di UCB1

Codice minimo (testato):

import numpy as np

class GaussianBandit:
    def __init__(self, K=10, seed=0):
        self.rng = np.random.default_rng(seed)
        self.mu = self.rng.normal(0, 1, K)
    def pull(self, a):
        return self.rng.normal(self.mu[a], 1)
    def regret_step(self, a):
        return self.mu.max() - self.mu[a]

def run(algo, env, K, T):
    cum_regret = []
    R = 0.0
    state = algo.init(K)
    for t in range(1, T + 1):
        a = algo.act(state, t)
        r = env.pull(a)
        algo.update(state, a, r)
        R += env.regret_step(a)
        cum_regret.append(R)
    return cum_regret

Le tre policy si iniettano via algo.act e algo.update. La struttura minima evidenzia la differenza puramente algoritmica.

Esempio 3: A/B test “vincente in 7 giorni” vs continuous learning

Scenario reale, ricorrente nei team product. Un e-commerce vuole testare quattro varianti di pulsante checkout. Conversion rates ipotetiche reali (sconosciute al team): 5.0%, 5.5%, 6.0%, 4.5%. Traffico ≈ 100K visitor / settimana.

Approccio A/B classico (frequentista). Allochi 25% del traffico a ognuna per 7 giorni. Calcoli p-value di pairwise z-test. Decidi winner se p < 0.05.

• Pro: stima accurata di tutte le varianti, anche perdenti. Inference causale pulita.
• Contro: per 7 giorni il 75% del traffico va su varianti subottime. Opportunity cost stimato ≈ 30K visitatori “sprecati” sulla 4.5% e altrettanti sulla 5.0% e 5.5%. A 5% di conversion media, ≈ 200 conversioni perse rispetto al optimal.

Approccio bandit (Thompson sampling con prior Beta). Allocazione dinamica. La variante che converte meglio riceve sempre più traffico. Dopo 1 giorno la 6% potrebbe avere già il 40% del traffico, dopo 7 il 60-70%.

• Pro: opportunity cost minimo. Decisione “graduale” — non c’è un momento “test concluso” ma un’allocazione che converge.
• Contro: stime delle varianti perdenti restano rumorose (poco traffico → poca precisione). Se un domani vuoi capire perché la 6% vince, non hai dati robusti sulle altre.

Perché Microsoft, Yahoo, Optimizely usano in produzione bandit contextual (LinUCB-style) per home page e recommendation, non A/B classico:

• Traffico alto e proporzionale al fatturato → il opportunity cost del A/B su 7 giorni è significativo.
• Effetti contextual chiari → utenti diversi reagiscono diversamente alle varianti, e contextual bandit personalizza.
• Tante varianti simultanee → A/B/n con 50 varianti richiede statistica multipla aggressiva, bandit gestisce naturalmente.

Applicazioni pratiche

Monte Carlo Tree Search (MCTS) e UCT. Kocsis-Szepesvári 2006 mostrano che applicare UCB1 ad ogni nodo dell’albero di ricerca dà un algoritmo che converge alla policy minimax. La reward del braccio “mossa M” al nodo N è la win-rate stimata dei rollout passati che sono passati per (N, M). Ad ogni ramo, UCB seleziona la mossa più promettente. AlphaGo (Silver 2016) usa UCT con priori dati da una policy network. AlphaZero rimuove i rollout, usa solo value network + UCT con priori. Il tema è ripreso in monte-carlo-tree-search (in preparazione).

EQUIVALENZA argomentabile: UCT è UCB1 ricorsivo. A ogni nodo dell’albero, le mosse legali sono i bracci, la “reward” è il valore stimato del subtree sotto quella mossa.

A/B testing dinamico. Microsoft Multi-Armed Bandit Service (parte di Azure ML), Google Optimize, Optimizely Stats Engine, Facebook Ax. Sostituiscono il classico test fisso con allocazione dinamica del traffico. Particolarmente vincente quando il traffico è caro (medical devices, fintech), o le varianti sono molte (A/B/n con n > 10), o c’è un context naturale (utente, dispositivo, geo).

Recommendation systems online. LinUCB su Yahoo Today Module è il caso paradigmatico (Li 2010). Modelli più moderni: Doubly-Robust per off-policy evaluation (Dudík-Langford-Li 2011), neural bandits per contesti ad alta dimensionalità (Riquelme-Tucker-Snoek 2018). Trade-off tipico: cold-start dei nuovi item (esplora) vs personalizzazione (sfrutta).

Hyperparameter tuning. Hyperband (Li et al. 2017) e BOHB (Falkner 2018) trattano la scelta tra configurazioni come bandit: ogni configurazione è un braccio, la reward è la performance dopo k epoche di training. Successive halving alloca dinamicamente il compute alle configurazioni più promettenti, scartando le altre.

RLHF e dueling bandit. Il reward model in RLHF è addestrato su preference pairs ((y_a, y_b), winner). Formalizzazione: dueling bandit (Yue-Joachims 2009), in cui ad ogni step si sceglie una coppia di bracci e si osserva quale è preferito. Algoritmi come Beat-the-Mean, RUCB, Thompson Dueling. Connessione esplicita con instruction-rlhf-era (in preparazione) e rlhf-ppo (in preparazione).

RLAIF (Constitutional AI). Bai et al. 2022. Il signal di preferenza viene da un modello stesso (o un suo “constitutional” sub-agent) invece che da labeler umani. Si può analizzare come bandit in cui la reward è osservazione rumorosa di una funzione che vorremmo apprendere. Riferimento futuro rlaif-constitutional (in preparazione).

LLM agent action selection. Quando un agente sceglie quale tool attivare — Read vs Bash vs Grep vs WebSearch — è una scelta sequenziale con feedback (success, latency, cost). Approcci recenti (es. ToolBandit 2024, MetaTool benchmark) modellano la selezione come contextual bandit con context = task description, action = tool, reward = success metric. Limite reale: il tool set evolve, distribuzione drifta. È più restless che stationary. Tema ripreso in tool-use-fondamenti (in preparazione).

Online ad bidding / GSP auctions con bidder learning. I bidder in Generalized Second-Price auctions di Google AdWords non conoscono il valore di click in advance — lo apprendono iterativamente come bandit. Edelman-Ostrovsky-Schwarz 2007 menzionano questo nel paper sulle GSP. Cross-reference con meccanismi-aste.

Dove si rompe

1. Stationarity. Tutta la teoria classica assume distribuzione di reward fissa nel tempo. Nel mondo reale le distribuzioni driftano: un nuovo competitor entra nel mercato, l’estate cambia il comportamento d’acquisto, il prompt template viene aggiornato. Il regime corretto è restless bandit (Whittle 1988): ogni braccio evolve nel tempo anche quando non lo tiri. Il problema generale è PSPACE-hard (Papadimitriou-Tsitsiklis 1999). Approssimazioni: Whittle index, sliding window UCB, discounted UCB.

2. i.i.d. Il setting stocastico assume reward i.i.d. condizionate sul braccio. In LLM agent settings questo è quasi sempre falso: lo stesso tool su due task simili produce reward correlate, il successo di un’azione dipende dallo storico di azioni precedenti (è un MDP, non un bandit). Quando l’i.i.d. è chiaramente violato senza assunzioni alternative buone, si passa al setting adversarial (EXP3) o al setting MDP (Q-learning).

3. Reward immediata. I bandit classici assumono che la reward sia osservata subito dopo l’azione. In e-commerce il “click” arriva in secondi ma il “purchase” in giorni e il “lifetime value” in mesi. Counterfactual estimation e off-policy evaluation diventano centrali (Bottou 2013, Dudík 2011). Una variante: delayed feedback bandit con loss aggiuntiva.

4. K grande. Se K è dell’ordine di T, il termine K log T diventa peggiore di T. Servono assunzioni strutturali sui bracci: lineari (LinUCB), low-rank, gerarchiche. Senza struttura, su 10000 bracci e orizzonte 1 anno il regret garantito è inutilizzabile.

5. High-dimensional context. Contextual bandit con d = 1000 features soffre di curse of dimensionality. Ridge regression diventa instabile. Servono assunzioni di sparsità (Lasso bandits, Bastani-Bayati 2020) o reti neurali (NeuralUCB, Zhou 2020) — le quali richiedono compute significativo per la matrice di covarianza.

6. Prior arbitrari (Thompson). Il Thompson sampling richiede un prior. In assenza di informazione, prior uniforme è standard, ma può essere subottimo. Prior “informato” da dati storici migliora drasticamente la performance — ma se l’informazione è scorretta, peggiora. È un caso di bias-varianza (cfr. bias-varianza) trasposto al setting bandit.

7. Click ≠ outcome reale. Nel mondo reale la “reward osservata” è un proxy. I clicks misurano interesse, non valore. Il valore vero (purchase, retention, lifetime value) ha attribution sporca. Un bandit che ottimizza clicks può degradare metriche di lungo termine. È il classico problema di proxy gaming, riferimento futuro a Goodhart’s law e a reward-hacking nei capitoli RL.

8. Combinatorial action space. “Scegli 5 articoli da 10000 da mostrare” significa C(10000, 5) ≈ 10^17 bracci. Servono assunzioni: lineare in feature aggregate, sub-modulare (Streeter-Golovin 2009), ranked. Lo stesso vale per LLM tool selection con tool composti.

9. Safety / vincoli. In medical, financial, legal il “exploration” può essere eticamente o legalmente vincolato. Constrained bandits (Amani-Alizadeh-Thrampoulidis 2019), safe exploration (Sui-Gotovos-Burdick-Krause 2015). Tema spinoso: il regret optimal richiede di provare tutto un po’, ma “tutto un po’” può essere inaccettabile sui pazienti.

10. Multi-objective. Reward vettoriale (revenue, retention, fairness) → il problema cambia natura. Pareto-bandit (Drugan-Nowé 2013), scalarization con preferenze. Spesso si finisce con scalarizzazione + Lagrangiani — perdendo ottimalità formale.

11. Quando il bandit non è bandit. Modellazione errata: il “tool selection” dell’agente LLM non è veramente bandit perché (a) l’azione cambia lo stato del sistema (file modificato, side effect), (b) i tool stessi cambiano nel tempo, (c) la reward è sporca e delayed, (d) l’agente ha context ricco. È un POMDP, e trattarlo come bandit è una semplificazione utile per primi prototipi ma fuorviante per produzione.

Collegamenti

• probabilita-base — il framework di valore atteso, varianza e media campionaria è la base per parlare di bandit e regret.
• bayes-base — Thompson sampling è un’applicazione diretta di posterior aggiornamento; il prior coniugato (Beta-Bernoulli, Normal-Normal) è il pane quotidiano.
• entropia-cross-entropy — il lower bound di Lai-Robbins è espresso in KL-divergence, che è cross-entropy meno entropia.
• bias-varianza — il dilemma esplorazione-sfruttamento è un cugino diretto del trade-off bias-varianza nello stimare ogni μ_i.
• complessita-big-o — i bound del regret (O(log T), Ω(log T), O(√KT log K)) sono una palestra di big-O sequenziale.
• giochi-definizione — bandit è gioco a un giocatore contro la natura. Il setting adversarial (EXP3) è un gioco a due giocatori.
• minimax — UCT (UCB1 ricorsivo su alberi) è la spina dorsale del MCTS che ha sostituito alpha-beta nel Go.
• meccanismi-aste — bidder che apprendono il valore in GSP auctions sono bandit.
• markov-decision-process (in preparazione) — generalizzazione del bandit con stato e transizioni.
• monte-carlo-tree-search (in preparazione) — UCT in dettaglio, fondamenta di AlphaGo/AlphaZero.
• instruction-rlhf-era (in preparazione) e rlhf-ppo (in preparazione) — preference modeling come dueling bandit.
• tool-use-fondamenti (in preparazione) — tool selection come contextual bandit (con tutti i caveat di “Dove si rompe”).

Per andare oltre

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press, capitolo 2. Trattazione didattica standard, ε-greedy, UCB, gradient bandit. Punto di partenza obbligato.
• Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. Riferimento moderno completo, 500+ pagine, scaricabile gratis dal sito dell’autore (https://tor-lattimore.com/downloads/book/book.pdf). Stocastico, adversarial, contextual, Bayesian.
• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47(2-3), 235-256. Il paper di UCB1, leggibile in un’ora. Da leggere prima delle generalizzazioni.
• Russo, D., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018). A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning 11(1), 1-96. Trattazione moderna del Thompson sampling con information ratio.
• Slivkins, A. (2019). Introduction to Multi-Armed Bandits. Foundations and Trends in Machine Learning 12(1-2), 1-286. Survey complementare a Lattimore-Szepesvári, più leggera. Buon ingresso.
• Bubeck, S., & Cesa-Bianchi, N. (2012). Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Foundations and Trends in Machine Learning 5(1), 1-122. Survey precedente, focus sull’analisi del regret. Compatto, tecnico, ottimo come riferimento di consultazione una volta padroneggiate le idee di base.