Causal Inference on Stopped Random Walks in Online Advertising

Sintesi Tecnica: Inferenza Causale su Cammini Aleatori Interrotti nella Pubblicità Online

Definizione del Problema
Il documento affronta una sfida di inferenza causale specifica per le piattaforme di pubblicità online (publisher), dove l'obiettivo è stimare l'effetto del trattamento a lungo termine dei parametri del meccanismo, come i prezzi di riserva delle aste. A differenza dei contesti classici (ad esempio, i trial clinici) in cui la dimensione della popolazione è fissa e indipendente dal trattamento, la pubblicità online coinvolge un sistema complesso e interconnesso di publisher, utenti e inserzionisti. In questo ambiente:

1. Il trattamento influenza la dimensione della popolazione: Un trattamento (ad esempio, un prezzo di riserva più elevato) altera le traiettorie di interazione degli utenti (lunghezza della sessione) e i comportamenti di offerta degli inserzionisti (vincolati da budget finiti), modificando così il numero totale di opportunità di impression generati in un periodo di tempo fisso.
2. Interferenza e Dinamiche: La decisione di misurare gli effetti del trattamento altera il sistema stesso che viene misurato. Le sessioni degli utenti sono modellate come catene di Markov, e i budget degli inserzionisti evolvono come un'altra catena di Markov dipendente dai risultati delle aste passate.
3. Disallineamento della Scala di Misurazione: La metrica target è il ricavo a lungo termine (ad esempio, su $k$ giorni), ma l'unità naturale di osservazione è la singola impression pubblicitaria. Il numero di impression in una finestra temporale fissa è una variabile casuale (un tempo di arresto) dipendente dal trattamento.

La difficoltà principale è che gli approoli standard del Teorema del Limite Centrale (CLT) che assumono misurazioni indipendenti e identicamente distribuite (i.i.d.) o dimensioni del campione fisse sono insufficienti. Il documento modella il ricavo cumulativo come un cammino aleatorio interrotto (stopped random walk), dove il tempo di arresto (il numero totale di impression in $k$ giorni) è casuale e dipendente dal trattamento.

Metodologia

1. Framework di Modellazione
Gli autori modellano l'interazione trilaterale tra il publisher, gli utenti e gli inserzionisti come una catena di Markov a tempo discreto.

• Spazio degli Stati: Lo stato include il profilo delle pagine visitate da tutti gli utenti ($X_n$), i budget rimanenti di tutti gli inserzionisti ($\Omega_n$) e l'indice dell'utente attivo ($I_n$).
• Dinamiche: Le transizioni di pagina degli utenti e gli aggiornamenti del budget degli inserzionisti sono governati da strategie stazionarie (funzioni di prezzo di riserva e funzioni di offerta) e variabili casuali che rappresentano il comportamento degli utenti e il ripristino dei budget.
• Ricavo: Il ricavo del publisher è una funzione non lineare, potenzialmente discontinua, del prezzo di riserva e dell'offerta vincente (logica dell'asta a prezzo secondo).

2. Riduzione della Dimensionalità: Il Trucco della Permutazione
Un ostacolo maggiore è la dimensione esponenziale dello spazio degli stati quando si modellano simultaneamente $d$ utenti e $m$ inserzionisti. Per affrontare questo problema, gli autori introducono un trucco della permutazione:

• Motivazione: Basandosi sull'osservazione che l'ordine di intercalazione delle transizioni di pagina provenienti da diverse sessioni utente concorrenti ha un effetto trascurabile sulle vendite aggregate e sul flusso di cassa, a condizione che le scale temporali delle sessioni utente siano molto più piccole delle durate delle campagne degli inserzionisti.
• Meccanismo: Gli autori definiscono una permutazione $\sigma$ che riordina la sequenza delle impression per raggruppare tutte le transizioni di pagina appartenenti alla stessa sessione utente.
• Risultato: Ciò trasforma l'originale catena di Markov ad alta dimensionalità in una approssimazione con uno spazio degli stati significativamente più piccolo ($\mathcal{X} \times \mathbb{R}^m \times [d]$), dove intere sessioni utente sono intercalate anziché singole transizioni di pagina. Questa approssimazione si basa sull'Assunzione 2.1, la quale postula che i budget e le durate delle campagne pubblicitarie siano grandi rispetto ai costi delle singole impression e alle lunghezze delle sessioni.

3. Design Sperimentale: Divisione del Budget
Per stimare l'effetto del trattamento, il documento propone un design sperimentale basato sulla divisione del budget (ispirato a [LMK21]):

• Divisione della Popolazione: Gli utenti sono assegnati casualmente a sottopopolazioni $A$ e $B$ con probabilità $q$ e $1-q$.
• Assegnazione del Trattamento: La sottopopolazione $A$ riceve il trattamento $v$ (prezzo di riserva $v$) e la sottopopolazione $B$ riceve il trattamento $w$.
• Divisione del Budget: Il budget di ogni inserzionista è diviso proporzionalmente ($q$ e $1-q$) tra le due sottopopolazioni. Gli inserzionisti in ciascun gruppo competono solo all'interno della catena di Markov assegnata alla propria sottopopolazione.
• Stimatore: Lo stimatore $\hat{\Delta}$ per l'effetto totale del trattamento è costruito scalando i ricavi medi e i conteggi delle impression osservati dalle sottopopolazioni rispettivamente per $1/q$ e $1/(1-q)$, estrapolando efficacementamente i risultati delle sottopopolazioni all'intera popolazione.

4. Garanzie Teoriche
Il documento deriva un intervallo di confidenza per l'effetto del trattamento a lungo termine $\Delta$ utilizzando:

• CLT per Catene di Markov: Applicato alle catene permutate per stabilire la normalità asintotica delle somme dei ricavi.
• Equazione di tipo Wald: Utilizzata per gestire i tempi di arresto casuali (numero totale di impression in $k$ giorni).
• Teorema di Anscombe: Impiegato per giustificare la convergenza del cammino aleatorio interrotto verso una distribuzione normale, nonostante la dimensione del campione sia casuale.
• Assunzioni di Ergodicità: L'analisi assume che le catene di Markov sottostanti siano Harris ergodiche e geometricamente ergodiche, garantendo l'esistenza di distribuzioni invarianti.

Contributi Chiave

1. Modellazione: Introduzione di un modello di cammino aleatorio interrotto per l'inferenza causale in cui la dimensione della popolazione (numero di impression) è casuale e dipendente dal trattamento. Questo generalizza l'inferenza causale classica, che tipicamente assume una popolazione fissa.
2. Analitico: Sviluppo di un trucco della permutazione per ridurre la dimensionalità dello spazio degli stati in sistemi markoviani con più utenti e inserzionisti, consentendo un'analisi trattabile sotto assunzioni deboli riguardanti le scale temporali.
3. Inferenza Statistica: Derivazione di intervalli di confidenza per gli effetti del trattamento a lungo termine in questo contesto complesso combinando un CLT markoviano, un'equazione di tipo Wald e il Teorema di Anscombe. Ciò fornisce una base teorica per determinare la durata necessaria degli esperimenti.

Risultati
Il risultato principale (Teorema 3.6) stabilisce che, sotto assunzioni di strategie invarianti nel tempo, ergodicità e scala della campagna, lo stimatore proposto $\hat{\Delta}$ converge al vero effetto del trattamento $\Delta$. Nello specifico, il documento dimostra che:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
dove $\epsilon$ è un limite dipendente dalle varianze asintotiche delle catene delle sottopopolazioni e dalla differenza tra le distribuzioni invarianti della sottopopolazione e della popolazione completa. Il documento nota che, nella pratica, con popolazioni di utenti ampie, queste distribuzioni dovrebbero essere vicine, rendendo efficace lo stimatore.

Significato e Rivendicazioni
Il documento sostiene di fornire un framework rigoroso per l'inferenza causale nei sistemi di pubblicità online dove l'"unità di analisi" (la sessione utente) e l'"unità di misurazione" (l'impression) operano su scale diverse, e dove il trattamento stesso altera il volume di dati generati.

• Si va oltre l'assunzione di "popolazione finita" dell'inferenza causale classica per passare a una popolazione casuale e dipendente dal trattamento.
• Offre una soluzione pratica al problema dell' "interferenza" nei mercati bilaterali, modellando esplicitamente le dinamiche di utenti e inserzionisti invece di fare affidamento esclusivamente su tecniche di randomizzazione per controllare l'interferenza.
• Fornisce una guida pratica per la durata degli esperimenti collegando l'ampiezza dell'intervallo di confidenza alle varianze asintotiche e al numero di periodi $k$.

Gli autori riconoscono i limiti, notando che il modello assume strategie stazionarie e non gestisce esplicitamente le dinamiche non stazionarie (ad esempio, l'ingresso di nuovi inserzionisti nel sistema). Suggeriscono inoltre che, sebbene il design di divisione del budget sia efficace, potrebbe non correggere per effetti di interferenza arbitrari non catturati dal modello markoviano specifico.