A More Accurate Algorithm Comparison through A/B Testing using Offline Evaluation Methods

Sintesi Tecnica: Un confronto tra algoritmi più accurato attraverso il Middle-In-Difference (MID) tramite metodi di valutazione offline

1. Definizione del problema

Nello sviluppo di servizi online come i sistemi di raccomandazione e i motori di ricerca, la selezione dell'algoritmo superiore è critica. Sebbene l'A/B testing sia ampiamente considerato il "gold standard" per la selezione degli algoritmi grazie alla sua capacità di eliminare i fattori di confondimento attraverso la randomizzazione, esso è spesso costoso e comporta il rischio di degradare l'esperienza dell'utente o i ricavi se un algoritmo scadente viene implementato. Al contrario, la valutazione offline (utilizzando dati storici di log) è più sicura ma è tradizionalmente considerata meno accurata a causa della maggiore varianza di stima e del potenziale bias.

Gli autori identificano un fenomeno controintuitivo: in determinati scenari, lo standard stimatore AVG utilizzato nell'A/B testing produce un tasso di errore nella selezione dell'algoritmo superiore rispetto ai metodi di valutazione offline come l'Inverse Propensity Scoring (IPS). Il problema centrale risiede nelle proprietà statistiche degli stimatori:

• Stimatore AVG: Utilizza dati indipendenti per l'Algoritmo A e l'Algoritmo B. Di conseguenza, le stime delle prestazioni sono non correlate. La varianza dello stimatore della differenza è semplicemente la somma delle singole varianze ($Var(\hat{V}_A) + Var(\hat{V}_B)$), offrendo nessun meccanismo per ridurre la varianza attraverso la correlazione.
• Stimatori Offline (es. IPS): Utilizzano dati storici condivisi per stimare le prestazioni di più algoritmi. Questo induce involontariamente una correlazione positiva tra gli stimatori. Secondo la formula di decomposizione della varianza ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$), questa covarianza positiva riduce la varianza totale dello stimatore della differenza, riducendo così la probabilità di errori critici di selezione (sottostimare l'algoritmo superiore o sovrastimare quello inferiore).

Il documento sostiene che l'A/B testing non sfrutta questa correlazione benefica, portando a una precisione di selezione subottimale rispetto ai metodi offline in specifici pre-esperimenti.

2. Metodologia: Lo stimatore Middle-In-Difference (MID)

Per affrontare la mancanza di correlazione nell'A/B testing, gli autori propongono un nuovo stimatore chiamato Middle-In-Difference (MID). L'idea centrale è quella di indurre intenzionalmente una correlazione positiva all'interno del framework dell'A/B testing introducendo un ipotetico algoritmo intermedio ($\pi_M$).

Processo di stima stepwise:
Invece di confrontare direttamente l'Algoritmo A ($\pi_A$) e l'Algoritmo B ($\pi_B$), il MID decompone la differenza di prestazione in due passaggi:

1. Stimare la differenza tra $\pi_A$ e $\pi_M$ utilizzando i dati di log raccolti da $\pi_A$ ($D_A$).
2. Stimare la differenza tra $\pi_M$ e $\pi_B$ utilizzando i dati di log raccolti da $\pi_B$ ($D_B$).

Lo stimatore finale è la somma di queste due differenze:
$$\Delta \hat{V}_{MID} = (\hat{V}_{IPS}(\pi_A; D_A) - \hat{V}_{IPS}(\pi_M; D_A)) + (\hat{V}_{IPS}(\pi_M; D_B) - \hat{V}_{IPS}(\pi_B; D_B))$$

Meccanismo di riduzione della varianza:

• Correlazione indotta: Poiché il primo termine utilizza i dati condivisi $D_A$ per stimare sia $\pi_A$ che $\pi_M$, e il secondo termine utilizza i dati condivisi $D_B$ per $\pi_M$ e $\pi_B$, si inducono correlazioni positive all'interno di ogni passaggio. Ciò riduce la varianza dei singoli termini di differenza.
• Algoritmo intermedio ottimale: Gli autori derivano l'algoritmo intermedio ottimale $\pi_M^*$ che minimizza la varianza dello stimatore. La policy ottimale è definita come la media armonica delle policy di logging:
  $$\pi_M^*(a|x) = \frac{2\pi_A(a|x)\pi_B(a|x)}{\pi_A(a|x) + \pi_B(a|x)}$$
  Questo design assicura che $\pi_M$ rimanga altamente simile sia a $\pi_A$ che a $\pi_B$, mitigando l' "esplosione della varianza" spesso vista nella valutazione offline quando si confrontano algoritmi dissimili (un tipico fallimento del metodo IPS standard).

Proprietà teoriche:

• Incorrettezza (Unbiasedness): Gli autori dimostrano che se l'algoritmo intermedio soddisfa la condizione per cui seleziona solo azioni in cui almeno uno degli algoritmi originali ha una probabilità non nulla, lo stimatore rimane non distorto (unbiased).
• Confronto della varianza: L'analisi teorica dimostra che il termine di reward della varianza del MID è strettamente minore o uguale a quello dello standard stimatore AVG. Inoltre, a differenza del classico IPS, il MID evita l'esplosione della varianza $1/\pi_A$ quando la somiglianza tra gli algoritmi è bassa, poiché i confronti intermedi coinvolgono policy simili.

3. Contributi chiave

1. Intuizione statistica: Il documento chiarisce che lo standard stimatore AVG nell'A/B testing non è necessariamente ottimale per la selezione degli algoritmi perché non riesce a sfruttare i benefici della riduzione della varianza derivanti dalla correlazione positiva tra gli stimatori.
2. Nuovo stimatore (MID): Gli autori propongono lo stimatore MID, che induce intenzionalmente una correlazione positiva tramite un algoritmo intermedio ipotetico e una stima stepwise, ottenendo tassi di errore di selezione inferiori sia rispetto all'A/B testing standard (AVG) che alla valutazione offline (IPS).
3. Derivazione teorica: Il documento deriva l'algoritmo intermedio ottimale per minimizzare la varianza e fornisce un'analisi bias-varianza che mostra perché il MID superi i metodi esistenti.
4. Validazione empirica: Utilizzando dati reali di raccomandazione video (KuaiRec), gli autori dimostrano che il MID ottiene costantemente tassi di errore di selezione inferiori in varie configurazioni.

4. Risultati sperimentali

Gli autori hanno condotto esperimenti utilizzando il dataset KuaiRec, un dataset di raccomandazione video completamente osservato che permette il calcolo delle prestazioni degli algoritmi rispetto al ground-truth. Hanno simulato un ambiente di A/B testing con diverse dimensioni campionarie e somiglianze tra algoritmi.

• Efficienza campionaria: Il MID ha ottenuto lo stesso tasso di errore di selezione degli esistenti metodi (AVG e IPS) utilizzando solo metà o un quarto della dimensione campionaria dell'A/B testing. Ad esempio, mentre l'AVG richiedeva 350–400 campioni per raggiungere un tasso di errore del 5%, il MID ha raggiunto lo stesso risultato con 100–200 campioni.
• Robustezza alla somiglianza:
  • In scenari ad alta somiglianza, il MID ha superato l'IPS (che tipicamente fatica con la varianza nelle impostazioni offline) e l'AVG.
  • In scenari a bassa somiglianza, dove l'IPS soffre di esplosione della varianza a causa del pesatura dell'importanza (importance weighting), il MID è rimasto stabile e ha superato sia l'IPS che l'AVG.
• Verifica del meccanismo: I grafici a dispersione (scatter plots) delle stime hanno confermato che il MID induce con successo una correlazione positiva tra gli stimatori stepwise, risultando in una distribuzione più stretta della stima della differenza finale rispetto alla distribuzione circolare (non correlata) dell'AVG. Questa maggiore compattezza è direttamente correlata a una riduzione degli errori critici di selezione.

5. Significato e affermazioni

Il documento afferma che lo stimatore MID proposto migliora fondamentalmente l'efficienza e l'accuratezza dell'A/B testing per la selezione degli algoritmi. Prendendo in prestito il meccanismo statistico della valutazione offline (dati condivisi che inducono correlazione) e applicandolo all'interno del framework dell'A/B testing tramite un ipotetico algoritmo intermedio, il MID supera i limiti sia dell'A/B testing tradizionale (alta varianza dovuta all'indipendenza) che della valutazione offline (instabilità dovuta alla bassa somiglianza o alla mancanza di nuovi dati).

Gli autori sottolineano che questo approccio consente alle organizzazioni di prendere decisioni sulla selezione degli algoritmi in modo più accurato con significativamente meno utenti o durate di esperimento più brevi, riducendo i costi e i rischi associati alla sperimentazione online. Il lavoro suggerisce che il "gold standard" dell'A/B testing può essere potenziato non abbandonandolo, ma perfezionando la tecnica di stima per sfruttare le correlazioni statistiche che precedentemente non venivano sfruttate negli ambienti online.