Multi-armed bandit: ottimizzare le varianti mentre il test è ancora in corso

Nell’articolo sull’A/B test bayesiano abbiamo confrontato due varianti a campione fisso: si raccolgono i dati per tutta la durata pianificata, si calcola la probabilità che B batta A, si decide. È un metodo solido, ma porta con sé un costo che di solito passa sotto silenzio.
Quel costo è il traffico che, per tutta la durata del test, continuiamo a mandare sulla variante peggiore. Se a metà esperimento B sta già stravincendo, ogni visitatore assegnato ad A è una conversione che probabilmente stiamo buttando via. Il test a campione fisso ci fa pagare l’informazione che raccogliamo: per sapere quale variante è migliore, dobbiamo continuare a mostrare anche quella che sospettiamo essere la peggiore.

C’è un modo per ridurre questo conto, e si chiama multi-armed bandit. L’idea è spostare il traffico in modo adattivo verso la variante che sta vincendo mentre il test è ancora in corso, invece di aspettare il verdetto finale. In questo articolo lo costruiamo con uno degli algoritmi più eleganti e pratici, il Thompson sampling, che è la naturale prosecuzione del ragionamento bayesiano che abbiamo seguito finora.

Di cosa parleremo:

• Il dilemma fra esplorazione e sfruttamento
• Thompson sampling: lasciar decidere il posterior
• Quanto si guadagna davvero: il regret evitato
• Quando un bandit ha senso, e quando no
• Prova tu
• Per approfondire

Esplorazione contro sfruttamento

Il nome viene dalle slot machine: un bandito a un braccio solo (one-armed bandit) è la macchinetta del casinò, e immaginiamo di averne davanti diverse, ciascuna con una probabilità di vincita sconosciuta e diversa dalle altre. Abbiamo un numero limitato di gettoni. A ogni giocata dobbiamo scegliere quale braccio tirare. Qual è la strategia che massimizza la vincita totale?

La traduzione per chi fa SEO o marketing è immediata: i bracci sono le varianti (tre versioni di un title tag, di una call to action, di una landing page), i gettoni sono i visitatori, la vincita è la conversione. Ogni visitatore va assegnato a una variante, e vogliamo massimizzare le conversioni totali lungo tutto l’esperimento.

Qui nasce la tensione di fondo, quella che rende il problema interessante. Da un lato vorremmo sfruttare (exploit) la variante che finora sembra la migliore, per incassare più conversioni possibili. Dall’altro dobbiamo continuare a esplorare (explore) anche le altre, perché “finora sembra la migliore” si basa su pochi dati e potrebbe essere un’impressione sbagliata.
È un equilibrio delicato: troppa esplorazione e sprechiamo traffico su varianti mediocri; troppo sfruttamento e rischiamo di incoronare un vincitore sbagliato sulla base di un colpo di fortuna iniziale. Il dilemma esplorazione-sfruttamento è il cuore di ogni problema di multi-armed bandit: ogni scelta è insieme un’occasione di guadagno e un’occasione di apprendimento, e le due cose tirano in direzioni opposte.

Thompson sampling: lasciar decidere il posterior

L’A/B test classico risolve il dilemma nel modo più rozzo possibile: esplora e basta, in parti uguali, fino alla fine. Metà traffico ad A, metà a B, nessun adattamento. Thompson sampling lo risolve in modo molto più astuto, e quasi sorprendente per quanto è semplice.

Riprendiamo il filo bayesiano. Per ogni variante manteniamo un posterior sul suo tasso di conversione: come abbiamo visto stimando il conversion rate, partendo da un prior Beta e osservando esiti binari (conversione sì/no), il posterior di ogni braccio è ancora una distribuzione Beta, che si aggiorna a ogni visitatore. All’inizio, quando non sappiamo nulla, ogni braccio parte da un prior non informativo Beta(1, 1).

La regola di Thompson, a parole prima che in formule, è questa: invece di chiederci “qual è la variante con la media più alta finora?”, a ogni visitatore campioniamo un tasso a caso dal posterior di ciascun braccio, e giochiamo il braccio che ha prodotto il campione più alto. È un modo di scegliere “in proporzione alla probabilità di essere il migliore”: una variante di cui siamo molto incerti può ancora vincere l’estrazione ogni tanto (ed è così che continua a essere esplorata), ma man mano che i dati si accumulano i suoi campioni si concentrano e, se è davvero peggiore, smette di essere scelta quasi da sola.

L’eleganza sta proprio qui: non c’è un parametro di esplorazione da regolare a mano. L’incertezza del posterior è il motore dell’esplorazione. Più un braccio è incerto, più i suoi campioni sono dispersi, più spesso capita che vinca l’estrazione e venga provato; più diventa certo, più i campioni si stringono attorno al valore vero e il braccio viene giocato (o evitato) con decisione.

Simulo in R l’intero processo su tre varianti con tassi reali del 5%, 7% e 9% (che ovviamente l’algoritmo non conosce), su 5000 visitatori:

set.seed(7)
true_rates <- c(0.05, 0.07, 0.09)   # 3 varianti, la terza e' la migliore
K <- length(true_rates); N <- 5000
alpha <- rep(1, K); beta_ <- rep(1, K)   # prior Beta(1,1) per braccio
pulls <- rep(0, K); rewards <- rep(0, K)
for (t in 1:N) {
  theta <- rbeta(K, alpha, beta_)        # campiona un tasso per braccio
  arm <- which.max(theta)                 # gioca il braccio campionato migliore
  r <- rbinom(1, 1, true_rates[arm])      # esito (conv si/no)
  alpha[arm] <- alpha[arm] + r; beta_[arm] <- beta_[arm] + (1 - r)
  pulls[arm] <- pulls[arm] + 1; rewards[arm] <- rewards[arm] + r
}

Il ciclo è tutto qui. A ogni iterazione campioniamo un theta per braccio (rbeta), scegliamo il massimo (which.max), simuliamo l’esito (rbinom) e aggiorniamo i parametri del braccio giocato: una conversione aumenta di uno il suo alpha, una mancata conversione il suo beta_. Nessun’altra logica, nessuna soglia da tarare.

Quanto si guadagna: il regret evitato

Vediamo dove ci ha portato la simulazione. La prima cosa da guardare è come si sono distribuiti i 5000 visitatori fra i tre bracci:

cat("pull per braccio:", pulls, "\n")
cat("conv totali bandit:", sum(rewards), "\n")

Output: pull per braccio = 359, 278, 4363; conv totali bandit = 424.

Dei 5000 visitatori, ben 4363 sono finiti sulla variante migliore, e solo poco più di 600 in totale sulle due peggiori. L’algoritmo, senza che gli avessimo detto nulla sui tassi veri, ha capito da solo quale braccio premiare e ci ha dirottato la stragrande maggioranza del traffico. È esattamente lo sfruttamento che volevamo, raggiunto attraverso un’esplorazione iniziale appena sufficiente a distinguere i bracci.

Ora il confronto che dà la misura del vantaggio. Un A/B test classico avrebbe diviso i 5000 visitatori in parti uguali fra le tre varianti, circa 1667 ciascuna, per tutta la durata. Le conversioni attese in quello scenario sono semplicemente la media dei tre tassi moltiplicata per il numero di visitatori:

exp_ab <- sum(true_rates) / K * N
cat("conv attese A/B equipartito:", round(exp_ab), "\n")
cat("regret evitato (circa):", round(sum(rewards) - exp_ab), "conv\n")

Output: conv attese A/B equipartito = 350; regret evitato (circa) = 74 conv.

Un A/B equipartito si sarebbe portato a casa circa 350 conversioni; il bandit ne ha raccolte 424. La differenza, circa 74 conversioni in più sullo stesso identico traffico, è ciò che in gergo si chiama regret evitato: il rimpianto, cioè le conversioni perse per aver giocato i bracci sbagliati, che l’allocazione adattiva ci ha risparmiato. In termini più chiari e diretti, a parità di visitatori il bandit ha convertito oltre il 20% in più, semplicemente non insistendo sulle varianti deboli.
Si noti che non abbiamo dovuto sacrificare nulla per ottenerlo: alla fine dell’esperimento conosciamo comunque il vincitore (anzi, lo conosciamo con grande sicurezza, visti i 4363 dati raccolti su di esso), e nel frattempo abbiamo convertito di più. È il vantaggio strutturale del bandit sul test a campione fisso.

Quando ha senso (e quando no)

Detto questo, un bandit non è la risposta giusta a ogni domanda, ed è importante capire dove brilla e dove invece un A/B test tradizionale resta preferibile.

Il bandit dà il meglio di sé quando il traffico è continuo e di lungo corso (una pagina sempre attiva, una campagna che gira per mesi) e quando le varianti da confrontare sono molte: lì l’allocazione adattiva ripaga, perché c’è tempo e volume per spostare il traffico e tante varianti deboli da abbandonare in fretta. È ideale per ottimizzazioni continue in cui l’obiettivo è massimizzare le conversioni lungo tutto il percorso, non scattare una fotografia statistica pulita in un dato momento.

Quando invece l’obiettivo è proprio quella fotografia — una stima precisa e imparziale di quanto una variante è migliore, magari da difendere davanti a un cliente o da usare per una decisione strategica — il test a campione fisso resta più adatto: proprio perché esplora in parti uguali, raccoglie dati bilanciati su tutte le varianti e produce stime più nette dell’effetto. Il bandit, concentrandosi presto sul vincitore, raccoglie pochi dati sui perdenti e quindi stima peggio di quanto siano peggiori.

Un avvertimento: il bandit dà per scontato che i tassi di conversione restino stabili nel tempo. Ma il mondo reale è spesso non stazionario — stagionalità, cambi di pubblico, una promozione che parte. Se la variante migliore cambia dopo che l’algoritmo si è già concentrato su un’altra, un Thompson sampling ingenuo come quello visto qui fatica ad accorgersene, perché ha smesso di esplorare le alternative. In contesti che cambiano servono varianti che “dimenticano” i dati vecchi (per esempio scontando gradualmente le osservazioni passate), altrimenti si rischia di restare ancorati a un vincitore che non lo è più.

Prova tu

La simulazione è un terreno di gioco perfetto per costruire l’intuizione. Riprendendo il codice qui sopra, prova a cambiare i numeri di partenza e osserva come si ridistribuiscono i pulls:

1. Avvicina i tassi veri, per esempio true_rates <- c(0.07, 0.08, 0.09): con varianti più simili, quanto più traffico serve prima che il braccio migliore si stacchi? La concentrazione dei pull resta così netta?
2. Riduci drasticamente il traffico (N <- 500): con pochi visitatori il bandit fa ancora in tempo a individuare il vincitore, o l’esplorazione si mangia tutto il budget?
3. Aggiungi varianti: passa a quattro o cinque bracci. Con più alternative da scartare, il vantaggio sul regret evitato rispetto all’A/B equipartito cresce o si assottiglia?

Suggerimento: la struttura del ciclo non cambia mai, basta modificare true_rates e N. È proprio osservando come il vettore pulls si sbilancia (o non si sbilancia) in funzione della distanza fra i tassi che si capisce davvero cosa fa, sotto il cofano, il Thompson sampling.

Finora abbiamo usato Bayes per decidere fra varianti: stimare un tasso, confrontarne due, allocare il traffico in modo adattivo. Ma lo stesso impianto — un prior, dei dati, un posterior — serve anche per un compito diverso e molto comune: classificare, cioè assegnare a ogni nuova osservazione l’etichetta più probabile date le sue caratteristiche. È il salto dal decidere al classificare, e l’algoritmo che lo fa con eleganza disarmante, ancora una volta partendo dal teorema di Bayes, è il Naive Bayes: l’argomento del prossimo articolo.

Per approfondire

Se vuoi approfondire i bandit applicati all’ottimizzazione dei siti web, Bandit Algorithms for Website Optimization di John Myles White è il libro che consiglio. È un volumetto agile e dichiaratamente pratico, che mette a confronto A/B test e algoritmi bandit (epsilon-greedy, softmax, UCB) proprio nell’ottica di chi ottimizza pagine e conversioni, con il codice sotto mano. È il punto di partenza ideale per chi vuole passare dalla simulazione che abbiamo visto a un bandit che gira davvero sul proprio sito.

Questo articolo fa parte del percorso «L’approccio bayesiano», la guida ragionata agli articoli su statistica e inferenza bayesiana applicate alla SEO.