Riepilogo Tecnico: Identificazione del Miglior Braccio a Confidenza Fissa per l'Analisi della Mediazione Causale

1. Definizione del Problema

Questo articolo affronta il problema dell'Identificazione del Miglior Braccio (Best-Arm Identification - BAI) all'interno di un contesto di bandit causale, focalizzandosi specificamente sull'analisi della mediazione causale.

• Contesto: Nei classici bandit causali, l'obiettivo è tipicamente quello di massimizzare la media interventale $E[Y | do(X=x)]$, che aggrega gli effetti attraverso tutti i percorsi causali. Tuttavia, i ricercatori spesso desiderano isolare l'effetto di un trattamento $X$ su un esito $Y$ che non passi attraverso un mediatore specifico $Z$ (ad esempio, per escludere meccanismi non etici, bias di posizionamento negli annunci, o reazioni intermedie avverse).
• Obiettivo: L'articolo mira a identificare il braccio $x^*$ che massimizza l'Esito Potenziale Naturale Diretto (NDPO) Atteso, definito come $E[Y_{x, Z_{x_0}}]$. Questa quantità rappresenta l'esito atteso se il trattamento viene impostato su $x$ mentre il mediatore $Z$ è mantenuto al valore che avrebbe assunto sotto un braccio di riferimento $x_0$.
• Setting: Il problema è formulato in un contesto a confidenza fissa (fixed-confidence). Un apprendista estrae sequenzialmente i braccia (interventi $do(X=x)$), osservando campioni i.i.d. dalla distribuzione interventale $P(Z, Y | do(X=x))$. L'obiettivo è identificare il braccio ottimale con una probabilità almeno di $1-\delta$ minimizzando il tempo di arresto atteso (complessità campionaria).

2. Metodologia

2.1 Identificazione a Livello di Popolazione

Gli autori stabiliscono innanzitutto che l'NDPO atteso è identificabile dalle distribuzioni interventali osservabili in un contesto di bandit causale.

• Assunzione: Si affidano alla standard assunzione di identificazione per gli effetti naturali diretti: $Y_{x,z} \perp\!\!\perp Z_{x'}$ per ogni $x, x', z$. Graficamente, ciò corrisponde all'assenza di confondimento non misurato tra il mediatore $Z$ e l'esito $Y$ nel grafo in cui vengono rimossi gli archi uscenti da $X$ e $Z$.
• Formula di Identificazione: Sotto questa assunzione, l'NDPO atteso $\theta(x)$ è identificato come:
  $$\theta(x) = \sum_{y,z} y P(Y=y | Z=z, do(X=x)) P(Z=z | do(X=x_0))$$
  Questa formulazione permette la stima utilizzando solo le distribuzioni interventali congiunte $P(Z, Y | do(X=x))$e$P(Z | do(X=x_0))$, evitando la necessità di controfatti nidificati che non sono direttamente osservabili nel contesto dei bandit.

2.2 Limite Inferiore della Complessità Campionaria

L'articolo deriva un limite inferiore dipendente dall'istanza per la complessità campionaria di qualsiasi algoritmo $\delta$-corretto.

• Differenza Chiave rispetto al BAI Standard: A differenza del BAI standard dove l'obiettivo dipende solo dalla distribuzione del proprio braccio, l'NDPO accoppia la distribuzione dell'esito sotto il braccio $x$ con la distribuzione del mediatore sotto il braccio di base $x_0$.
• Struttura della Complessità: Il limite inferiore coinvolge un problema di ottimizzazione semi-infinito. Il tempo caratteristico $T^*(P)$ è definito come:
  $$(T^*(P))^{-1} = \sup_{w \in \Sigma_K} \inf_{Q \in \text{Alt}(P)} \sum_{x \in \mathcal{X}} w_x KL(P_x \| Q_x)$$
  dove $\text{Alt}(P)$ è l'insieme di modelli alternativi in cui un braccio diverso è ottimale. Il vincolo che definisce $\text{Alt}(P)$ è non separabile perché la distribuzione del mediatore di base $Q_{x_0}(Z)$ appare nell'obiettivo per ogni braccio, creando un accoppiamento tra i bracci che non esiste nel classico BAI.

2.3 Algoritmo Proposto: TaS-NDPO

Gli autori propongono TaS-NDPO, un algoritmo Track-and-Stop (TaS) adattato per questo specifico obiettivo. L'algoritmo consiste in tre componenti principali:

1. Stima Plug-in: Vengono utilizzate stime empiriche delle distribuzioni interventali per calcolare stime plug-in di $\theta(x)$.
2. Regola di Campionamento (D-tracking con Forcing):
   • D-tracking: L'algoritmo traccia le proporzioni di campionamento ottimali $w^*$ derivate dal limite inferiore.
   • Copertura dei Competitor: Per gestire i vincoli non separabili, l'algoritmo assicura che ogni braccio sia selezionato come "competitore" nel problema di ottimizzazione con sufficiente frequenza.
   • Forcing a Livello di Cellula: Fondamentalmente, l'algoritmo forza l'esplorazione a livello di cella $(x, z)$ (combinazioni di braccio e valore del mediatore). Ciò è necessario perché la divergenza KL si decompone in termini pesati dalle probabilità del mediatore; i valori rari del mediatore devono essere campionati a sufficienza per garantire una stima coerente delle probabilità condizionali dell'esito $P(Y|Z, do(X))$.
3. Regola di Arresto (GLRT): L'algoritmo si arresta quando lo statistico del Test del Rapporto di Verosimiglianza Generalizzato (GLRT) supera una soglia $\beta(t, \delta)$. Lo statistico misura la divergenza KL minima rispetto a qualsiasi modello alternativo in cui un braccio subottimale appaia migliore del braccio empirico corrente migliore.
4. Solver di Ottimizzazione: La risoluzione del problema di minimizzazione interno nella regola di campionamento e nella regola di arresto comporta un problema di ottimizzazione semi-infinito. Gli autori impiegano un metodo di cutting-set (Mutapcic e Boyd, 2009) combinato con una riduzione a tre bracci (il braccio di base, il braccio attualmente migliore e un competitor) e uno schema di minimizzazione alternata per risolvere i sottoproblemi bi-convessi risultanti.

3. Contributi Chiave

1. Formulazione del Problema: L'articolo definisce formalmente e studia il problema del BAI per la massimizzazione dell'NDPO atteso, una quantità rilevante per isolare gli effetti diretti causali in presenza di mediatori.
2. Identificazione nei Bandit: Stabilisce l'identificazione dell'NDPO atteso utilizzando solo le distribuzioni interventali disponibili in un contesto di bandit causale, unendo la teoria dell'inferenza causale con il processo decisionale sequenziale.
3. Limiti Teorici: Deriva un nuovo limite inferiore della complessità campionaria che evidenzia le sfide uniche dell'ottimizzazione NDPO, specificamente l'accoppiamento dei bracci tramite la distribuzione del mediatore di base e la necessità di accumulare informazioni a livello di cella.
4. Design dell'Algoritmo: Introduce TaS-NDPO, un nuovo algoritmo che:
   • Utilizza un metodo di cutting-set per risolvere la complessa ottimizzazione semi-infinita richiesta per le proporzioni di campionamento ottimali.
   • Incorpora il forcing a livello di cella per garantire la coerenza nei regimi di scarsità del mediatore.
   • Dimostra la $\delta$-correttezza (correttezza garantita con probabilità $1-\delta$) e l'ottimalità asintotica (raggiungere il limite inferiore sulla complessità campionaria quando $\delta \to 0$).

4. Risultati Sperimentali

Gli autori hanno valutato TaS-NDPO sia su dati sintetici che su un dataset pubblicitario su larga scala (IPinYou).

• Validazione nel Mondo Reale (IPinYou):
  • Il dataset riguardava la selezione di creatività pubblicitarie ($X$) per massimizzare i clic ($Y$), con la visibilità del slot ($Z$) come mediatore.
  • Divergenza Decisionale: Il braccio che massimizza la media interventale standard era diverso da quello che massimizza l'NDPO. La media standard favoriva una creatività che appariva frequentemente nelle posizioni superiori (effetto mediato), mentre il braccio ottimale per l'NDPO era diverso.
  • Performance: TaS-NDPO ha raggiunto un tempo di arresto mediano di 12.928 campioni, circa il 50% più efficiente della variante a livello di braccio (25.856 campioni) e significativamente superiore al campionamento uniforme e a un approccio basato sul primo braccio. Tutti i metodi hanno mantenuto tassi di errore empirico nulli per $\delta=0.05$.
• Esperimenti Sintetici:
  • Scaling del Gap: I risultati hanno confermato la scalabilità $1/\Delta^2$ della complessità campionaria prevista dal limite inferiore.
  • Scarsità del Mediatore: Il vantaggio del forcing a livello di cella è stato più pronunciato in contesti con celle mediatore-esito rare (regimi di scarsità), dove il forcing a livello di braccio falliva nell'accumulare informazioni sufficienti.
  • Tempo di Esecuzione: L'overhead computazionale dell'ottimizzazione del cutting-set è stato moderato (media di 22,5 secondi per esecuzione per fino a 100k campioni), non costituendo un collo di bottiglia rispetto ai guadagni in efficienza campionaria.

5. Significato e Rivendicazioni

L'articolo sostiene che TaS-NDPO fornisce una soluzione teoricamente fondata ed empiricamente efficiente per identificare i trattamenti che massimizzano gli effetti causali diretti escludendo i percorsi mediati.

• Significato Teorico: Estende il framework Track-and-Stop ai contesti causali con controfatti nidificati, dimostrando che l'ottimalità asintotica è raggiungibile anche quando la funzione obiettivo accoppia le distribuzioni tra diversi bracci (tramite il mediatore di base).
• Significato Pratico: Isolando gli effetti diretti, il metodo consente di prendere decisioni che evitano meccanismi indesiderabili (ad esempio, clickbait, effetti collaterali avversi o posizionamento non etico) che potrebbero altrimenti essere favoriti dagli approcci standard di massimizzazione della media.
• Modestia: Gli autori riconoscono che il loro attuale framework si concentra su esiti binari e su una specifica struttura di grafo causale (Mediatore tra Trattamento e Esito). Notano che l'estensione a esiti multicategoria è immediata, ma generalizzare a strutture causali più ampie con effetti specifici di percorso rimane una direzione per il lavoro futuro. Chiariscono inoltre che l'identificazione si basa sulla plausibilità del grafo causale sottostante (specificamente l'assenza di confondimento non misurato tra $Z$ e $Y$), che è un'assunzione standard ma non testabile nell'inferenza causale.