Scalable Policy Maximization Under Network Interference

Riepilogo Tecnico: Massimizzazione Scalabile delle Politiche in Presenza di Interferenza di Rete

Enunciato del Problema
Il documento affronta la sfida del processo decisionale sequenziale (massimizzazione delle politiche) in ambienti caratterizzati da interferenza di rete, in cui lo stato di trattamento di un individuo influenza i risultati di altri. Sebbene gli algoritmi Multi-Armed Bandit (MAB) siano lo standard per l'apprendimento sequenziale, essi si basano tipicamente su assunzioni di indipendenza che falliscono in contesti di rete (ad esempio, trial clinici, marketplace online, reti sociali).

Gli approcci esistenti ai MAB in presenza di interferenza affrontano due limitazioni critiche:

1. Scalabilità: I metodi attuali faticano a scalare oltre reti molto piccole (circa $n \approx 15$ nodi). Spesso tentano di catturare pattern di interferenza arbitrari, portando a uno spazio dei parametri che cresce esponenzialmente con il grado del nodo ($d_{max}$) e linearmente con la dimensione della rete ($n$). Per una rete con $n=1000$ e $d_{max}=10$, ciò risulta in oltre un milione di parametri sconosciuti, rendendo la stima computazionalmente non fattibile.
2. Assunzioni Statiche: Molti algoritmi esistenti richiedono che la struttura della rete e la popolazione di individui rimangano fisse nel tempo, un'assunzione che crea incoerenze in contesti dinamici dove i risultati dipendono dagli stati di trattamento storici.

Metodologia
Gli autori propongono un algoritmo di Thompson Sampling scalabile che sfrutta assunzioni strutturali comuni nella letteratura sull'inferenza causale per ottenere una parametrizzazione lineare parsimoniosa della funzione di ricompensa.

• Assunzioni Strutturali (SANIA): Il metodo si basa sull'Assunzione di Interferenza di Vicinato Simmetrica e Additiva (SANIA).

  • Interferenza di Vicinato (NIA): La ricompensa di un nodo dipende solo dal proprio trattamento e dallo stato di trattamento dei suoi vicini immediati.
  • Additività: Gli effetti diretti non interagiscono con gli effetti indiretti (spillover).
  • Simmetria: La ricompensa di un nodo dipende dal numero di vicini trattati, non dalle loro identità specifiche.
    Sotto queste assunzioni, il vettore delle ricompense a livello di nodo può essere riparametrizzato come un sistema lineare: $r_t = H(Z_t; A_t)\theta + \epsilon_t$, dove $\theta$ è un vettore di parametri a bassa dimensionalità contenente i parametri degli effetti del trattamento e dell'interferenza.

• Progettazione dell'Algoritmo:

  • L'algoritmo mantiene una distribuzione a posteriori sul vettore dei parametri $\theta$.
  • Ad ogni passo temporale $t$, campiona un vettore di parametri $\theta^{(t)}$ dalla distribuzione a posteriori e seleziona un vettore di allocazione del trattamento $Z_t$ che massimizza la ricompensa totale attesa condizionata a $\theta^{(t)}$.
  • Il framework supporta parametrizzazioni flessibili, inclusi parametri condivisi (tutti i nodi condividono $\theta$), parametri raggruppati (i nodi in gruppi latenti o osservati condividono $\theta_g$) e modelli a caratteristiche latenti (dove le posizioni dei nodi in uno spazio euclideo influenzano le ricompense).
  • L'algoritmo gestisce reti dinamiche (dove le matrici di adiacenza $A_t$ cambiano) e vincoli di budget (limitando il numero di nodi trattati).

• Analisi del Rimpianto (Regret):

  • Gli autori dimostrano un limite superiore sul rimpianto bayesiano di $O(D\sqrt{nT} \log(nT))$, dove $D$ è la dimensionalità di $\theta$, $n$ è la dimensione della rete e $T$ è l'orizzonte temporale.
  • Derivano un limite inferiore corrispondente di $\Omega(D\sqrt{nT})$, dimostrando che l'algoritmo è quasi-ottimale.
  • I limiti sul rimpianto riflettono il compromesso tra l'aumento di informazioni ottenuto osservando $n$ nodi interdipendenti e l'aumentata complessità dello spazio delle azioni.

Contributi Chiave

1. Parametrizzazione Scalabile: Il documento dimostra che le assunzioni comuni nell'inferenza causale permettono di esprimere la funzione di ricompensa come una funzione lineare di un vettore di parametri a bassa dimensionalità, riducendo la complessità da esponenziale a polinomiale (specificamente, lineare in $n$ per modelli condivisi/raggruppati).
2. Thompson Sampling Scalabile: Gli autori sviluppano un algoritmo capace di gestire reti di ordini di grandezza superiori rispetto ai metodi precedenti (dimostrato fino a $n=1000$ nelle simulazioni), risolvendo la "maledizione della dimensionalità" intrinseca nei problemi di interferenza.
3. Gestione di Reti Dinamiche: A differenza di lavori precedenti che richiedevano reti fisse, questo framework permette sia ai nodi che agli spigoli di essere campionati o di cambiare ad ogni periodo temporale, risolvendo le incoerenze tra l'indipendenza temporale e le assunzioni di popolazione fissa.
4. Garanzie Teoriche: Il documento fornisce limiti rigorosi superiori e inferiori sul rimpianto bayesiano, stabilendo la quasi-ottimalità dell'approccio proposto.

Risultati
Gli esperimenti di simulazione validano il metodo attraverso tre schemi di parametrizzazione:

• Parametri Condivisi: L'algoritmo apprende rapidamente e scala efficacemente per reti di dimensioni $n \in \{100, 500, 1000, 2500\}$.
• Parametri Raggruppati: Il metodo performa bene anche quando le etichette dei gruppi sono parzialmente latenti e devono essere stimate utilizzando un nodo "ancora" per gruppo.
• Caratteristiche Latenti: L'algoritmo gestisce con successo effetti eterogenei dipendenti da caratteristiche latenti dei nodi nei modelli a spazio latente.

Confronti:

• vs. Agarwal et al. (2024): Il metodo proposto supera significativamente lo stato dell'arte esistente (che utilizza analisi di Fourier e interferenza di rete sparsa) su reti statiche piccole. Crucialmente, il metodo proposto rimane robusto e supera Agarwal et al. anche quando le assunzioni SANIA sono mal specificate (ad esempio, quando l'additività o la simmetria sono violate). Ciò è attribuito alla capacità del metodo proposto di apprendere un'approssimazione efficace con molti meno parametri, mentre i metodi concorrenti soffrono di un'alta varianza dovuta alla necessità di stimare vettori di parametri esponenzialmente più grandi.
• vs. MAB Standard: Gli approcci MAB standard falliscono nello scalare a causa della crescita esponenziale dello spazio delle azioni ($2^n$ bracci).

Significato
Il documento afferma di colmare un importante divario di scalabilità tra i metodi di inferenza causale per l'interferenza e gli algoritmi pratici di bandit. Abilitando l'ottimizzazione delle politiche in sistemi di rete su larga scala, il lavoro colma la divisione tra identificazione causale teorica e processo decisionale dinamico. Gli autori suggeriscono che questo framework facilita l'applicazione degli algoritmi di bandit a problemi del mondo reale che coinvolgono reti grandi e dinamiche, come la distribuzione di vaccini o interventi nei marketplace online, dove l'interferenza è prevalente ma in precedenza troppo complessa da modellare dinamicamente.