UCB e Thompson sampling

Due paradigmi di esplorazione — ottimismo deterministico e randomizzazione bayesiana — che reggono mezzo secolo di decision making sotto incertezza, dal trial clinico di Thompson nel 1933 al rollout di AlphaZero, dal backbone del MCTS al reward model di RLHF.

Perché questo capitolo

Il capitolo precedente ha presentato il problema bandit e ha messo in fila le strategie principali — ε-greedy, UCB1, Thompson sampling, EXP3 — come membri di un’unica famiglia che bilancia esplorazione e sfruttamento. Quel livello introduttivo è sufficiente per capire l’idea di regret e per leggere l’80% della letteratura applicata. Per il restante 20%, e soprattutto per chi deve mettere mano a un sistema di recommendation, a un reward model, a un planner MCTS o a un Bayesian optimizer, serve una passata più profonda.

Il motivo è che UCB e Thompson non sono due algoritmi tra altri: sono due filosofie complementari di esplorazione. UCB è la versione tecnica di “agisci come se fossi fortunato”: costruisci un upper confidence bound sulla media di ogni braccio e scegli il bound più alto. Thompson è la versione tecnica di “agisci secondo la probabilità che tu abbia ragione”: campiona dal posterior corrente e scegli arg max del campione. Quasi tutto il resto — KL-UCB, Bayes-UCB, GP-UCB, IDS, neural UCB, Bootstrapped DQN — è una raffinatura di una delle due.

Capire entrambi a fondo paga subito quando ci si trova davanti a un problema reale. Il bonus di UCB1 è derivato da una disuguaglianza di concentrazione (Hoeffding) e da un union bound: è generale ma deliberatamente conservativo. Il sample di Thompson è “tarato” dalla varianza del posterior: non ha costanti da scegliere ma richiede un prior. Su display advertising, news recommendation, A/B test dinamico, in produzione spesso vince Thompson — e spiegare perché richiede di entrare in entrambe le derivazioni.

Tutto il capitolo dà per noto il problema bandit standard come definito in multi-armed-bandits. Qui si scava sotto al cofano.

Contesto

Il grafo concettuale parte da quattro nodi e si dirama. Hoeffding (Wassily Hoeffding, statistico tedesco-americano) nel 1963 pubblica le disuguaglianze di concentrazione che portano il suo nome: la media empirica di n variabili aleatorie limitate si concentra esponenzialmente attorno alla media vera. Lai-Robbins (Tze Leung Lai, statistico di Stanford; Herbert Robbins, statistico americano, padre della stochastic approximation) nel 1985 dimostrano il lower bound asintotico del regret per qualsiasi politica consistente in un bandit stocastico: nessun algoritmo può fare meglio di Σ_i Δ_i / KL(p_i || p*) · log T. Diventa il metro contro cui si misurano gli algoritmi.

Peter Auer (informatico austriaco), Nicolò Cesa-Bianchi (informatico italiano) e Paul Fischer nel 2002, in Finite-time Analysis of the Multiarmed Bandit Problem (Machine Learning), introducono UCB1 e dimostrano regret O(K log T) in tempo finito, con costanti esplicite. È il primo algoritmo “leggibile in un’ora” che chiude il gap col lower bound a meno di una costante.

William R. Thompson (statistico medico americano), molto prima di tutti, nel 1933 in un articolo dimenticato su Biometrika propone una regola bayesiana per allocare pazienti a trattamenti: campiona dal posterior, scegli il braccio col campione più alto. La comunità ML lo riscopre nel 2010-2012, dopo che Olivier Chapelle e Lihong Li in An Empirical Evaluation of Thompson Sampling (NeurIPS 2011) mostrano sperimentalmente che batte UCB su display advertising di Yahoo. Subito dopo Emilie Kaufmann, Nathaniel Korda e Rémi Munos (2012), e indipendentemente Shipra Agrawal e Navin Goyal (2012-2013), provano che Thompson sampling è asintoticamente ottimale: chiude il lower bound di Lai-Robbins.

Nel frattempo nascono i raffinamenti di UCB. Aurélien Garivier e Olivier Cappé (2011) introducono KL-UCB: invece di Hoeffding usano la divergenza KL, ottenendo un bonus più stretto e matched al lower bound per Bernoulli. Emilie Kaufmann, Olivier Cappé e Aurélien Garivier (2012) propongono Bayes-UCB: bonus pari al quantile del posterior, una sorta di compromesso tra UCB e Thompson.

Sul fronte contextual, Peter Auer nel 2002 in Using Confidence Bounds for Exploitation-Exploration Trade-offs (JMLR) introduce LinUCB per reward lineari nel contesto. Otto anni dopo Lihong Li, Wei Chu, John Langford e Robert Schapire (2010) lo deployano sulla home page di Yahoo News (A Contextual-Bandit Approach to Personalized News Article Recommendation, WWW): primo large-scale documentato. La versione Thompson contextual la formalizza ancora Agrawal-Goyal nel 2013.

Infine, su un piano più astratto, Daniel Russo e Benjamin Van Roy in una serie di paper 2014-2018 reinterpretano Thompson sampling in chiave information-theoretic: il regret è bilanciato dal rapporto tra costo immediato della scelta e information gain sul braccio ottimo. Lo stesso framework dà luce al Information-Directed Sampling (IDS, 2018), che minimizza esplicitamente questo rapporto e in problemi strutturati può battere Thompson.

Per i collegamenti pratici di base — definizione di regret, ε-greedy, varianti adversarial — il riferimento è multi-armed-bandits. Il capitolo qui si concentra sulle due famiglie e sulle loro derivazioni.

L’intuizione

Prima di scrivere formule, due immagini per fissare le due filosofie. Sono complementari: chi le tiene entrambe in testa capisce in pochi secondi qualsiasi paper successivo.

Primo angolo — ottimismo in faccia all’incertezza

Hai cinque ristoranti e dieci giorni di viaggio. Vuoi mangiare bene. Per ogni ristorante hai una valutazione media (le tue impressioni passate) e un’idea di quanto poco ne sai (quante volte ci sei andato). La regola UCB è: somma alla valutazione un bonus proporzionale all’incertezza e scegli la somma più alta.

Concretamente: se il ristorante A ha media 8.5/10 dopo venti visite e il ristorante B ha 7.8/10 dopo due visite, il bonus di B è grande, quello di A è piccolo. La somma di B può superare quella di A. Con il tempo i bonus si stringono e la scelta tende verso il vero migliore.

La filosofia è deterministica e trasparente: a parità di stato dei tuoi dati, la scelta è univoca. Se qualcuno ti chiede “perché hai scelto B?” puoi rispondere “perché il suo upper confidence bound era più alto”. È debuggabile.

ANALOGIA didattica (non causale, non filiazione): è la versione tecnica del proverbio “chi non risica non rosica”, ma con un teorema dietro. Il bonus non è arbitrario: viene da una disuguaglianza di concentrazione che lega quanto può essere lontana la media empirica dalla vera media.

Secondo angolo — randomizzazione dal posterior

Cambia la lente. Per ogni ristorante mantieni una distribuzione di credenza sulla sua qualità vera. All’inizio è piatta — non sai niente. Dopo ogni visita la distribuzione si stringe attorno alla media empirica.

La regola Thompson è: per ogni ristorante tira un dado pesato dalla sua distribuzione di credenza, e scegli quello col tiro più alto.

Niente bonus, niente costanti. Se una distribuzione è larga, tende a tirare valori estremi più spesso, e quindi il braccio “viene esplorato” naturalmente. Se è stretta, tira sempre attorno alla sua media. È probability matching: la probabilità che Thompson scelga il braccio i è esattamente la probabilità (sotto il posterior corrente) che il braccio i sia il migliore.

Il vantaggio operativo è che non tarari nulla: il “bonus” è già dentro la varianza del posterior. Lo svantaggio è che richiede un prior — una scelta di partenza sulla distribuzione di credenza — e un meccanismo per aggiornarlo.

ANALOGIA didattica: è come decidere coerentemente con la propria incertezza, lasciando che il caso giochi nelle proporzioni giuste. Non sei né sempre conservativo né sempre azzardato: sei calibrato.

I due angoli convergono nel comportamento asintotico — entrambi raggiungono il lower bound di Lai-Robbins — ma divergono nei dettagli pratici, ed è dove succede il lavoro di ingegneria.

La meccanica

Hoeffding bound

TEOREMA (Hoeffding 1963). Se X_1, …, X_n sono variabili aleatorie indipendenti, ognuna a valori in [0,1], con media comune μ, e μ̂_n = (1/n) Σ X_i, allora per ogni ε > 0:

$$P(|μ̂_n - μ| > ε) ≤ 2 exp(-2 n ε²)$$

L’intuizione: la media empirica si concentra attorno alla media vera in modo esponenziale nel numero di campioni. Per dimezzare l’errore servono quattro volte più campioni.

Da Hoeffding a UCB1

Vogliamo un bonus tale che, con alta probabilità su tutti gli step, la vera media μ_i di ogni braccio sia minore o uguale alla stima più il bonus. Procedimento in quattro righe:

1. Vogliamo P(μ_i > μ̂_i + ε) ≤ δ per ogni step e braccio.
2. Hoeffding dà 2 exp(-2 n_i ε²) ≤ δ, da cui ε ≥ √(ln(2/δ) / (2 n_i)).
3. Per coprire t step e K bracci con union bound conviene δ = O(t^{-4}).
4. Sostituendo: ε = √(2 ln t / n_i). Ecco il bonus di UCB1.

L’algoritmo:

def ucb1_select(N, S, t):
    # N[i] = numero di pull, S[i] = somma reward del braccio i
    K = len(N)
    # Pull iniziale di ogni braccio
    for i in range(K):
        if N[i] == 0:
            return i
    means = S / N
    bonus = np.sqrt(2 * np.log(t) / N)
    return int(np.argmax(means + bonus))

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

$$E[R_T] ≤ Σ_{i: Δ_i > 0} (8 ln T / Δ_i) + (1 + π²/3) Σ_i Δ_i = O(K log T)$$

dove Δ_i = μ* - μ_i è il gap del braccio i. Il bound è in tempo finito, con costanti esplicite. Confronto col lower bound Lai-Robbins: Σ Δ_i / KL(μ_i || μ*) · log T. Per Bernoulli, 8 / Δ_i è strettamente peggiore di 1 / KL — il fattore di slack viene da Hoeffding (che non sfrutta la struttura Bernoulli) e dal union bound conservativo.

KL-UCB

Per chiudere il gap: invece di Hoeffding usa la disuguaglianza di Sanov / KL bound. Il bonus implicito di KL-UCB:

$$u_i(t) = max { q ∈ [0,1] : n_i · KL(μ̂_i || q) ≤ ln t + c log log t }$$

dove KL(p || q) = p log(p/q) + (1-p) log((1-p)/(1-q)) per Bernoulli. Si trova q via root finding (1D, cinque iterazioni di bisezione bastano).

from scipy.optimize import brentq

def kl_bernoulli(p, q, eps=1e-12):
    p = min(max(p, eps), 1 - eps)
    q = min(max(q, eps), 1 - eps)
    return p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q))

def kl_ucb_index(p_hat, n, t, c=3.0):
    threshold = (np.log(t) + c * np.log(max(np.log(t), 1))) / n
    if p_hat >= 1.0:
        return 1.0
    return brentq(lambda q: kl_bernoulli(p_hat, q) - threshold, p_hat, 1 - 1e-12)

TEOREMA (Garivier-Cappé 2011). Per Bernoulli (e famiglie esponenziali a un parametro), KL-UCB raggiunge il lower bound di Lai-Robbins:

$$lim_{T→∞} E[R_T] / log T = Σ_{i: Δ_i > 0} Δ_i / KL(μ_i || μ*)$$

KL-UCB è asintoticamente ottimo. UCB1 sopravvive perché è semplice, generale (qualsiasi reward bounded) e didatticamente trasparente.

Altri membri della famiglia UCB

• UCB-Tuned (Auer 2002). Bonus √((ln t / n) · min(1/4, V_i(n) + √(2 ln t / n))) con V_i la varianza empirica. Spesso vince UCB1 in pratica, analisi formale meno pulita.
• UCB2 (Auer 2002). Pull a “epoche” geometriche τ(r) = ⌈(1+α)^r⌉. Costanti migliori, codice più complicato.
• UCB-V (Audibert-Munos-Szepesvári 2009). Usa Bernstein bound: bonus √(2 V_i ln t / n) + 3 ln t / n. Più stretto quando la varianza è bassa.
• Bayes-UCB (Kaufmann-Cappé-Garivier 2012). Bonus = quantile (1 − 1/(t (log T)^c)) del posterior corrente. Asintoticamente ottimo come KL-UCB. Si adatta naturalmente a prior informativi.

Thompson sampling — Bernoulli

Prior coniugato Beta(α_0, β_0). Default Beta(1,1) = uniforme. Likelihood Bernoulli. Posterior dopo s successi e f fallimenti: Beta(α_0 + s, β_0 + f). Update O(1).

def thompson_bernoulli(alpha, beta_p):
    # alpha[i], beta_p[i] = parametri posterior del braccio i
    samples = np.random.beta(alpha, beta_p)
    return int(np.argmax(samples))

# Update dopo aver pullato i e osservato r ∈ {0,1}
def update_bernoulli(alpha, beta_p, i, r):
    alpha[i] += r
    beta_p[i] += 1 - r

TEOREMA (Kaufmann-Korda-Munos 2012, Bernoulli con prior Beta(1,1)):

$$lim_{T→∞} E[R_T] / log T = Σ_{i: Δ_i > 0} Δ_i / KL(μ_i || μ*)$$

stesso lower bound Lai-Robbins. Asintoticamente ottimale.

TEOREMA (Agrawal-Goyal 2013). Regret frequentista finite-time: E[R_T] = O((K / Δ_min²) log T) o, in forma più stretta, O((Σ_i 1/Δ_i²) log T).

Thompson sampling — Gaussian

Prior coniugato per varianza nota σ²: Normal(μ_0, σ_0²). Dopo n osservazioni con somma S:

$$σ_n² = 1 / (1/σ_0² + n/σ²) μ_n = σ_n² (μ_0 / σ_0² + S / σ²)$$

Posterior Normal(μ_n, σ_n²). Sample θ̂_i ~ Normal(μ_n, σ_n²), pull arg max θ̂_i.

Per varianza ignota: prior Normal-Inverse-Gamma o Normal-Gamma. Lattimore-Szepesvári (2020) dà la forma chiusa.

Thompson — perché spesso vince in pratica

L’osservazione è di Chapelle-Li (2011). Su display advertising e news recommendation, Thompson batte UCB con lo stesso budget di pull, anche con prior uniforme. Tre ragioni:

1. Bonus naturale. La varianza del posterior è esattamente la “giusta dose” di esplorazione; il bonus √(2 ln t / n) è derivato per resistere al peggior caso possibile del union bound, ed è quindi conservativo.
2. Probability matching. Il regret istantaneo medio è bilanciato bene con l’information gain — è il cuore del bound di Russo-Van Roy.
3. Robustezza al delay. In sistemi reali la reward arriva in ritardo (latenza, batching). UCB con delay grande continua a esplorare un braccio finché non vede l’esito; Thompson sample comunque dal posterior corrente e si comporta meglio.

Information-Directed Sampling (cenno)

Russo-Van Roy 2018. Definisce information ratio Ψ_t(π) = E[Δ_t]² / I_t(A*; (a_t, r_t)) — costo medio del regret in unità di information gain sul braccio ottimo. IDS sceglie a_t = arg min_a Ψ_t(δ_a) (politica deterministica, oppure mix di due bracci).

Bayesian regret bound: BayesRegret(T) ≤ √(Γ · H(A*) · T) con Γ = sup_t Ψ_t. Dimension-free in problemi strutturati. In linear bandit con prior informativo IDS migliora costanti significativamente; in problemi senza struttura coincide essenzialmente con Thompson.

Costo computazionale: stimare expected information gain è oneroso (Monte Carlo, approssimazioni). Vale la pena solo quando l’orizzonte è lungo e la struttura informativa forte.

LinUCB

Setting contextual lineare. A ogni step osservi un contesto x_a ∈ R^d per ogni braccio (oppure x_t condiviso e φ_a delle feature di braccio). Reward attesa lineare: E[r_a | x_a] = θ^T x_a. Da stimare θ.

Ridge regression online. Sia A_t = λ I + Σ_{s<t} x_{a_s} x_{a_s}^T, b_t = Σ_{s<t} r_s x_{a_s}. Stima:

$$θ̂_t = A_t^{-1} b_t$$

Confidence ellipsoide attorno a θ̂_t. Per la predizione lineare θ^T x_a, l’intervallo di confidenza è:

$$| θ^T x_a - θ̂_t^T x_a | ≤ α √(x_a^T A_t^{-1} x_a)$$

con α = O(√(d log T)). LinUCB sceglie:

a_t = arg max_a [ θ̂_t^T x_a + α √(x_a^T A_t^{-1} x_a) ]

Update: A_{t+1} = A_t + x x^T, b_{t+1} = b_t + r · x. Inverse update via Sherman-Morrison: O(d²) per step.

def linucb_select(A_inv, b, contexts, alpha):
    theta_hat = A_inv @ b
    # contexts: matrice K x d con riga = feature del braccio a
    means = contexts @ theta_hat
    bonuses = alpha * np.sqrt(np.einsum('ij,jk,ik->i', contexts, A_inv, contexts))
    return int(np.argmax(means + bonuses))

def linucb_update(A_inv, b, x, r):
    Ax = A_inv @ x
    A_inv -= np.outer(Ax, Ax) / (1.0 + x @ Ax)
    b += r * x
    return A_inv, b

TEOREMA (Abbasi-Yadkori-Pál-Szepesvári 2011). Regret O(d √(T log T)). Indipendente da K.

flowchart LR
    U[feature utente x_t] --> F[feature braccio φ_a]
    F --> P[reward predetto θ_hat^T x_a]
    P --> B["+ α √(x_a^T A^-1 x_a)"]
    B --> S[arg max sui bracci]
    S --> R[serve item, osserva click]
    R --> UP[update A, b]
    UP --> P

Figura 5 — pipeline LinUCB come stima lineare θ̂^T x più bonus ellittico α √(x^T A⁻¹ x), con update Sherman-Morrison di A e b dopo ogni click osservato

Thompson contextual lineare

Stessa A_t e b_t. Posterior su θ: Normal(θ̂_t, σ² A_t^{-1}). Sample θ_tilde ~ N(θ̂_t, σ² A_t^{-1}); pull a_t = arg max_a θ_tilde^T x_a.

TEOREMA (Agrawal-Goyal 2013). Regret Õ(d^{3/2} √T). Peggiore di LinUCB di √d, ma in pratica spesso vince per le stesse ragioni del caso non-contextual.

Approximate Thompson per posterior intrattabili

Con neural net, GP fitting su dati massivi, o policy gradient, il posterior non è più gaussiano e l’inference esatta è impossibile. Approssimazioni standard:

• Bootstrap: tieni m copie del modello, ognuna addestrata su resample (bootstrap) del dataset. Al pull, scegli a caso un modello e usa la sua predizione. Equivale a sample dal posterior empirico.
• Ensemble di reti con random initialization (Osband-Blundell-Pritzel-Van Roy 2016, Deep Exploration via Bootstrapped DQN).
• Laplace approximation: posterior ≈ N(MAP, H^{-1}) con H Hessiano della log-posterior al MAP.
• Langevin Monte Carlo: SGD con noise gaussiano calibrato; le iterate convergono in distribuzione al posterior.
• Variational inference: famiglia parametrica q_φ(θ) minimizza KL(q || posterior).

Costo computazionale dominato dal sampling: in serving real-time questo è il tradeoff principale.

Esempi

Esempio 1 — Posterior Beta dopo dieci pull, sample manuale

Tre bracci Bernoulli con prior Beta(1,1). Dopo dieci pull osservi:

• Braccio A: 4 pull, 3 successi → posterior Beta(4, 2)
• Braccio B: 3 pull, 1 successo → posterior Beta(2, 3)
• Braccio C: 3 pull, 2 successi → posterior Beta(3, 2)

Media a posteriori (E[Beta(α, β)] = α/(α+β)):

• A: 4/6 ≈ 0.67
• B: 2/5 = 0.40
• C: 3/5 = 0.60

Sampling. Tiri da ciascun posterior:

• θ̂_A ~ Beta(4,2) → 0.71
• θ̂_B ~ Beta(2,3) → 0.55
• θ̂_C ~ Beta(3,2) → 0.48

Thompson pulla A. Notare che B, pur avendo media bassa, può tirare alto perché la sua distribuzione è larga: in altre realizzazioni di sampling il sample di B può superare gli altri. Su 10000 sample da questi posterior, Pr(A è il max) ≈ 0.55, Pr(B) ≈ 0.18, Pr(C) ≈ 0.27 — esattamente le frequenze con cui Thompson li sceglie, probability matching.

Confronto con UCB1 al passo t=11:

• bonus = √(2 ln 11 / n)
• A: 0.75 + √(2 · 2.4 / 4) = 0.75 + 1.10 = 1.85
• B: 0.33 + √(2 · 2.4 / 3) = 0.33 + 1.27 = 1.60
• C: 0.67 + √(2 · 2.4 / 3) = 0.67 + 1.27 = 1.94

UCB1 pulla C (vince per via del bonus su pochi pull, anche se la media è leggermente sotto A). Tipico: nei primi step UCB privilegia bracci poco visti. Asintoticamente entrambi convergono al braccio col vero μ più alto.

Esempio 2 — Simulazione 10-armed Bernoulli, codice e regret

import numpy as np

def simulate(algo_select, algo_update, init_state, mus, T, rng):
    state = init_state(len(mus))
    regret = 0.0
    mu_star = max(mus)
    history = np.zeros(T)
    for t in range(1, T + 1):
        a = algo_select(state, t)
        r = float(rng.random() < mus[a])
        algo_update(state, a, r)
        regret += mu_star - mus[a]
        history[t - 1] = regret
    return history

mus = np.array([0.10, 0.15, 0.20, 0.30, 0.35, 0.40, 0.50, 0.55, 0.60, 0.70])
T = 10000
R = 100  # replicazioni

# Stati
def init_ucb(K): return {'N': np.zeros(K), 'S': np.zeros(K)}
def select_ucb1(s, t):
    K = len(s['N'])
    for i in range(K):
        if s['N'][i] == 0: return i
    means = s['S'] / s['N']
    bonus = np.sqrt(2 * np.log(t) / s['N'])
    return int(np.argmax(means + bonus))
def update_ucb(s, a, r):
    s['N'][a] += 1; s['S'][a] += r

def init_ts(K): return {'a': np.ones(K), 'b': np.ones(K)}
def select_ts(s, t):
    return int(np.argmax(np.random.beta(s['a'], s['b'])))
def update_ts(s, a, r):
    s['a'][a] += r; s['b'][a] += 1 - r

rng = np.random.default_rng(0)
hist_ucb = np.mean([simulate(select_ucb1, update_ucb, init_ucb, mus, T, rng) for _ in range(R)], axis=0)
hist_ts  = np.mean([simulate(select_ts, update_ts, init_ts, mus, T, rng) for _ in range(R)], axis=0)

Risultato tipico (ordini di grandezza):

• UCB1: regret medio a T=10000 ≈ 220-260, deviazione ≈ 30
• KL-UCB: ≈ 110-140, deviazione ≈ 20
• Thompson sampling: ≈ 80-110, deviazione ≈ 25
• ε-greedy con ε=0.1: ≈ 350-400 (lineare in ε)

Le banda di confidenza al 95% mostra Thompson e KL-UCB a livelli simili e ben sotto UCB1; ε-greedy resta lineare. Il messaggio operativo è chiaro: per Bernoulli “puro”, KL-UCB e Thompson sono i due candidati seri. UCB1 paga le costanti del worst-case.

Esempio 3 — Pipeline LinUCB per recommendation reale

Scenario: home page di un sito di news. K = 200 articoli candidati. Per ogni richiesta hai feature utente x_u ∈ R^{20} (paese, cluster di interessi, device, ora). Per ogni articolo a hai feature φ_a ∈ R^{20} (topic, recency, source, lunghezza). Costruisci x_a = [x_u, φ_a, x_u ⊗ φ_a] (concat + cross), dimensione effettiva d ≈ 60.

Pipeline (vedi figura):

1. Richiesta utente arriva con x_u.
2. Per ogni candidate a, costruisci x_a.
3. Calcola predizione θ̂^T x_a.
4. Calcola bonus α √(x_a^T A^{-1} x_a).
5. Servi arg max della somma.
6. Osserva click (r ∈ {0,1}) entro un timeout (5 secondi tipico). Reward delayed: tieni in coda.
7. Update A += x x^T, b += r · x. Sherman-Morrison per A^{-1}.

flowchart LR
    U[feature utente x_t] --> F[feature braccio φ_a]
    F --> P[reward predetto θ_hat^T x_a]
    P --> B["+ α √(x_a^T A^-1 x_a)"]
    B --> S[arg max sui bracci]
    S --> R[serve item, osserva click]
    R --> UP[update A, b]
    UP --> P

Figura 5 — LinUCB pipeline for recommendation

Numeri operativi tipici:

• Latenza per inference: 10 ms (matrice d x d con d=60, K=200 candidates).
• Memoria per modello: O(d²) = 3600 float = 30 KB. Trascurabile.
• α: tipicamente 1.0-2.0 in produzione, tunato su replay offline.
• Cold start: prior λ I con λ piccolo (0.01) per non frenare l’esplorazione iniziale.

Equivalente Thompson contextual: cambia il punto 4. Sample θ_tilde ~ N(θ̂, σ² A^{-1}) una volta per request, poi calcola θ_tilde^T x_a per tutti gli articoli. In pratica più robusto al delay e al cold start.

Per un deployment serio servono inoltre: (a) off-policy evaluation per scegliere α e prior senza A/B costose ([Dudík-Langford-Li 2011], doubly-robust estimator), (b) decadimento temporale per non-stationarity (sliding window su A, b), (c) clipping su x e regolarizzazione adattiva per stability.

Applicazioni pratiche

Monte Carlo Tree Search e UCT. Kocsis-Szepesvári (2006) introducono UCT: a ogni nodo dell’albero MCTS, si applica UCB1 considerando i figli come bracci, con valore stimato Q(s, a) e bonus c · √(ln N(s) / N(s, a)). EQUIVALENZA argomentabile: UCT è UCB1 ricorsivo sulla struttura ad albero. La spina dorsale di AlphaGo (Silver 2016) e AlphaZero (Silver 2017): la rete neurale produce policy prior e value, MCTS con UCT-like selection (PUCT, una variante) costruisce il piano di gioco. Stesso meccanismo in MuZero (Schrittwieser 2019), AlphaCode 2, e nei moderni reasoning solver.

Bayesian optimization. Hyperparameter tuning, materials discovery, drug discovery. GP-UCB (Srinivas-Krause-Kakade-Seeger 2010) modella la funzione obiettivo come Gaussian Process; bonus √(β_T · σ_t²(x)) con β_T crescente. GP-Thompson sample una funzione dal posterior GP e ottimizza. Tool: Spearmint, BoTorch (Meta), Vizier (Google), Optuna, Hyperopt — la maggior parte in produzione usa varianti di Expected Improvement o GP-UCB. Per chi viene da ML applicato è il primo punto di contatto col framework bandit.

A/B testing dinamico. A/B classico assume traffico fisso per variant. Bandit con Thompson sampling alloca dinamicamente il traffico verso le varianti che convertono meglio. Microsoft Personalizer, Optimizely Stats Engine, Dynamic Yield, AB Tasty hanno tutti varianti bandit-driven. Trade-off rispetto all’A/B classico: non si ottiene un p-value standard, ma si massimizza la conversione totale durante il test.

Recommendation systems online. Yahoo News (LinUCB, Li 2010), Spotify (contextual Thompson, blog 2019), Netflix (artwork selection con contextual bandit, blog 2017), LinkedIn Ads (LinUCB-style), Stitch Fix (Thompson per outfit recommendations). Tipicamente combinati con counterfactual evaluation per scegliere iperparametri offline.

RLHF e dueling bandit. Il reward model in RLHF è addestrato su preference pair ((y_a, y_b), winner). Active learning: quale coppia far valutare a un annotator umano? Formalizzazione: dueling bandit (Yue-Joachims 2009). Algoritmi: Beat-the-Mean, Relative UCB (RUCB, Zoghi 2014), Double Thompson Sampling (Wu-Liu 2016). Connessione con rlhf-ppo (in preparazione) e con la selezione di reward shaping policies.

Hyperparameter tuning di LLM. Successive Halving (Karnin-Koren-Somekh 2013), Hyperband (Li-Jamieson-DeSalvo-Rostamizadeh-Talwalkar 2017), BOHB (Falkner-Klein-Hutter 2018). BO over neural architecture search.

Tool selection in agent harness. Quando l’agente sceglie tra più tool con costi e success rate variabili, framework bandit applica come euristica. Marca: ASSUMPTION — non è un vero bandit, perché tool calls non sono i.i.d. valutabili e il “reward” dipende dal context completo del task. Ma l’intuizione “esplora tool poco usati, sfrutta tool affidabili” è utile per progettare descrizioni e gating.

Cost-aware exploration in inferenza. Decidere se chiamare un modello small o large, o se usare CoT vs no-CoT, è un setting bandit con context (il prompt) e reward = qualità - λ · costo. Frame esplicitamente in vari paper recenti su routing tra LLM (FrugalGPT, Chen-Zaharia-Zou 2023).

Backbone in MCTS per reasoning LLM. Tree-of-Thoughts con UCB selection sui rami di reasoning. AlphaZero-style search applicato a token (Yao 2023, Hao 2023). In tutti questi casi l’algoritmo di selezione ai nodi è una variante UCB.

flowchart TD
    Root[nodo root] -->|selezione UCB1| C1[child 1]
    Root -->|selezione UCB1| C2[child 2]
    C1 -->|espansione| L1[leaf]
    L1 -->|rollout / value net| V[valore v]
    V -.backup.-> C1
    V -.backup.-> Root

Figura 6 — singolo step di UCT in MCTS — selezione UCB1 dal nodo root verso un child, espansione di una foglia, rollout o value net per stimare v, backup del valore lungo il cammino come spina dorsale di AlphaGo/AlphaZero

Dove si rompe

Hoeffding-tightness vs Lai-Robbins. UCB1 ha regret O(K log T) ma con costante 8/Δ_i invece di 1/KL(μ_i || μ*). Per Bernoulli con μ* vicino a 0 o 1, il gap è grande. KL-UCB lo chiude — al prezzo di un root finding numerico. In ambienti dove i Δ sono piccoli e gli orizzonti lunghi, vale la pena.

Prior sbagliato in Thompson. Il sample θ̂_i ~ P_t(μ_i) dipende dal prior. Prior “informato” da dati storici accelera molto la convergenza, ma se l’informazione è scorretta (drift, bias di selezione, popolazioni diverse) Thompson ci mette di più a recuperare. Caso classico: prior basato su una stagione precedente che non riflette la stagione attuale. Mitigation: prior debole (Beta(1,1), Beta(2,2)) di default; aggiunta di prior solo dopo validation offline.

Posterior intrattabile. Per neural net o GP grandi, il posterior esatto non si calcola. Approximate Thompson via bootstrap, ensemble, Laplace, Langevin, VI. Ognuno introduce bias che rovina le garanzie teoriche; in pratica funzionano ma il costo computazionale del sampling diventa il bottleneck — soprattutto in serving real-time, dove ogni request richiede un forward pass per modello.

Heavy-tailed reward. Hoeffding e Bernstein assumono reward limitati o sub-gaussian. Pareto, log-normal, distribuzioni con outlier estremi rompono UCB1 e Thompson Bernoulli/Gaussian. Soluzioni: trimmed estimator (taglia gli outlier), median-of-means (Bubeck-Cesa-Bianchi-Lugosi 2013), robust UCB. Per Thompson, prior Student-t o miscele.

Non-stazionarietà. Reward distribution che evolve nel tempo (mercato finanziario, news cycle, stagionalità). Senza adattamento, UCB e Thompson convergono a una stima media del passato e perdono performance quando il presente diverge. Soluzioni: discounted UCB (Garivier-Moulines 2008) con decadimento esponenziale dei dati; sliding-window UCB; Thompson con discount factor sul posterior; change-point detection esplicito.

Curse of dimensionality nel contextual. LinUCB con d = 1000 features ha matrice A^{-1} di 10^6 entries, ridge regression instabile, bonus dominato dal termine √d. Servono assunzioni strutturali: sparsità (Lasso bandits, Bastani-Bayati 2020), low-rank (Jun-Willett-Wright-Nowak 2017), reti neurali con NTK approximation (NeuralUCB, Zhou-Wang-Wei 2020). In pratica spesso si torna a feature engineering con d < 100. Cfr. curse-dimensionalita.

Costo computazionale in produzione. UCB1: O(K) per step. KL-UCB: O(K) ma con root finding 1D. Thompson Bernoulli: O(K). LinUCB: O(d² + K d). Linear Thompson: O(d² + K d) + Cholesky O(d³) per il sample. Ensemble di m reti neurali: O(m · forward_pass). Con K = 10^4 candidates e d = 100, latenza in single-threaded serving è dominata dal pass su K, non dalla matematica del bandit.

Cold start. Bandit puro all’inizio è uniforme: pulla bracci a caso. In sistemi con K grande (10000 articoli) e budget di pull modesto (10000 utenti / ora), gli algoritmi standard non hanno tempo di esplorare tutto. Soluzioni: prior informativo basato su feature (LinUCB / Thompson contextual), warm-start su dati storici (off-policy training), gerarchia di bracci (categorie → articoli) con bandit a più livelli.

Best-arm identification vs regret minimization. Sono problemi diversi. UCB e Thompson minimizzano cumulative regret — fanno spesso il braccio migliore durante il processo. Per identificare con alta probabilità il braccio migliore al termine di un budget T (best-arm identification), gli algoritmi sono diversi: Successive Halving, lil’UCB (Jamieson-Malloy-Nowak-Bubeck 2014). Confondere i due obiettivi è uno degli errori più frequenti in produzione: in RLHF preference selection è spesso più rilevante BAI che regret.

Reward delayed o batched. In sistemi reali la reward arriva con latenza variabile (clic, conversioni a 7 giorni). UCB con bracci pulled ma non ancora osservati può continuare a esplorare lo stesso braccio finché non vede la reward. Thompson è strutturalmente più robusto: campiona dal posterior corrente che riflette correttamente l’incertezza. Mitigation per UCB: pessimistic update, in-flight assumption.

Quando il bandit non è il modello giusto. Se l’azione cambia lo stato dell’ambiente (ricompensa influenzata dalle scelte precedenti), il problema è un MDP, non un bandit. Cfr. capitolo successivo markov-decision-process (in preparazione). Se le reward fra bracci sono correlate con struttura non lineare e non kernelizzabile, servono RL con function approximation generale. Se ci sono vincoli di budget intrinseci (ogni pull costa una risorsa con vincolo), Bandits with Knapsacks (Badanidiyuru-Kleinberg-Slivkins 2013).

LLM agent decision sotto risorse. Marca esplicita: APPROFONDIRE in capitoli agente. Quando un LLM agent deve scegliere tra azioni a costo eterogeneo, il framing bandit è suggestivo ma non rigorosamente applicabile: le azioni non sono i.i.d. valutabili, la “reward” è un giudizio composito, il context cambia drasticamente turn-by-turn. UCB e Thompson sono utili come euristiche di prompting e tool gating, non come framework di garanzia.

Collegamenti

• probabilita-base — Tutto Thompson sampling poggia su distribuzioni di probabilità (posterior Beta, Gaussian, Normal-Inverse-Gamma) e valore atteso. Il regret è un’aspettativa.
• bayes-base — Thompson è un’applicazione diretta del teorema di Bayes con likelihood + prior coniugato. L’update Beta(α + s, β + f) viene da Bayes con prior Beta e likelihood Bernoulli.
• entropia-cross-entropy — KL-UCB usa la divergenza KL come misura di gap fra distribuzioni. L’information ratio di IDS misura l’entropia del braccio ottimo.
• bias-varianza — La scelta del prior in Thompson è un bias-varianza al setting bandit: prior forte = bias, prior debole = varianza.
• curse-dimensionalita — LinUCB e LinTS soffrono curse: per d grande il bonus ellittico domina; servono assunzioni strutturali (sparsità, low-rank).
• giochi-definizione — Bandit e RL si formalizzano come giochi a un giocatore contro la natura.
• minimax — UCT (UCB1 ricorsivo su alberi di gioco) ha sostituito alpha-beta minimax in Go e domini con branching factor alto.
• multi-armed-bandits — Capitolo introduttivo. Il presente lo approfondisce su UCB e Thompson come paradigmi.
• markov-decision-process (in preparazione) — MDP estende bandit con stato dinamico; UCB e Thompson hanno controparti (UCRL, Thompson per MDP).
• monte-carlo-tree-search (in preparazione) — UCT come applicazione diretta di UCB1.
• rlhf-ppo (in preparazione) — Reward model RLHF si formalizza come dueling bandit; active learning per preference selection usa varianti di Thompson.
• agente-definizione (in preparazione) — Frame bandit come euristica per tool selection in agent harness.

Per andare oltre

• Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. Riferimento canonico moderno: copre UCB, Thompson, IDS, contextual, adversarial, BAI, restless. Free online.
• Russo, D., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018). A Tutorial on Thompson Sampling. Foundations and Trends in ML 11(1), 1-96. Trattazione sistematica di Thompson con conjugate priors, approximate sampling, case studies.
• Chapelle, O., & Li, L. (2011). An Empirical Evaluation of Thompson Sampling. NeurIPS 2011. Lettura veloce e illuminante sul perché Thompson vince in pratica.
• 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.
• Garivier, A., & Cappé, O. (2011). The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond. COLT 2011. Per chi vuole chiudere il gap con Lai-Robbins.
• Slivkins, A. (2019). Introduction to Multi-Armed Bandits. Foundations and Trends in ML 12(1-2), 1-286. Trattazione lunga ma molto pulita; ottima per chi viene da ML applicato.