Résumé technique : Apprentissage de politiques adaptatives sous interférence réseau inconnue

Énoncé du problème

Dans de nombreux contextes expérimentaux, le résultat d'une unité dépend non seulement de son propre traitement, mais aussi des traitements attribués à ses voisins au sein d'un réseau sous-jacent. Ce phénomène, connu sous le nom d'interférence ou de débordement, viole l'hypothèse de stabilité de la valeur de traitement pour les unités (SUTVA). Bien que la littérature sur l'inférence causale ait développé des méthodes robustes pour les expériences statiques sous interférence (par exemple, Sussman et Airoldi, 2017 ; Aronow et Samii, 2017), ces approches supposent généralement que le réseau d'interférence est connu ou reposent sur des randomisations grossières au niveau des clusters.

Les méthodes existantes d'expérimentation adaptative (séquentielle) présentent des limitations significatives :

1. Hypothèse de réseau connu : Les méthodes évolutives comme Gleich et al. (2025) supposent que la structure du réseau est entièrement observée, ce qui est irréaliste dans de nombreuses applications où les liens sociaux ou comportementaux sont latents.
2. Problèmes d'évolutivité : Les méthodes qui tentent d'apprendre la structure du réseau, telles que Agarwal et al. (2024), reposent sur une analyse de Fourier sur toutes les configurations possibles de voisins, entraînant un nombre de paramètres exponentiel par rapport à la taille du voisinage. Ces méthodes ne parviennent pas à s'adapter au-delà d'environ $n \approx 12$ unités.
3. Perte de granularité : D'autres conceptions adaptatives (par exemple, Viviano et Rudder, 2024) opèrent sur des clusters prédéfinis, contournant l'optimisation au niveau individuel et échouant à récupérer le réseau d'interférence lui-même.

Le défi central abordé par cet article est d'apprendre conjointement le réseau d'interférence inconnu et d'optimiser les allocations de traitement au niveau individuel dans un cadre séquentiel afin de maximiser les résultats cumulatifs (par exemple, revenus, indicateurs de santé).

Méthodologie

Les auteurs proposent un cadre d'échantillonnage de Thompson (TS) qui infère conjointement le réseau d'interférence et les paramètres de récompense en utilisant un échantillonneur de Gibbs.

1. Configuration du modèle

• Cadre : Allocation séquentielle de traitements binaires $Z_t \in \{0, 1\}^n$ à $n$ unités sur $T$ tours, soumise à une contrainte de budget $\|Z_t\|_1 \le B$.
• Hypothèse d'interférence de voisinage (NIA) : Le résultat de l'unité $i$ dépend uniquement de son propre traitement et des traitements de ses voisins définis par une matrice d'adjacence inconnue $A$.
• Modèle de récompense : Le résultat attendu est linéaire par rapport à un vecteur de paramètres $\theta$, c'est-à-dire $r(Z; A, \theta) = H(Z; A)\theta$. La matrice de conception $H$ dépend du réseau $A$.

2. Échantillonnage conjoint de la posterior via Gibbs

Puisque la vraisemblance est non linéaire en $A$ (en raison des comptes de voisins), une forme fermée de la posterior n'est pas disponible. Les auteurs emploient un échantillonneur de Gibbs par arêtes pour tirer des échantillons conjoints approximatifs de la posterior $\pi(\theta, A | \mathcal{D}_{t-1})$ :

• Mise à jour des paramètres ($\theta | A$) : Avec $A$ fixe, le modèle se réduit à une régression gaussienne conjuguée standard. La posterior pour $\theta$ est gaussienne.
• Mise à jour des arêtes ($A | \theta$) : Avec $\theta$ fixe, l'échantillonneur parcourt toutes les arêtes $(i, j)$. La conditionnelle complète pour l'arête $A_{ij}$ dépend uniquement des flux de récompenses des nœuds $i$ et $j$. La règle de mise à jour est dérivée via une transformation logit du rapport de vraisemblance, permettant un échantillonnage efficace sans énumérer toutes les $2^{\binom{n}{2}}$ configurations de graphes.

3. Algorithme (Gibbs-TS)

À chaque tour $t$ :

1. Effectuer $K$ balayages Gibbs pour obtenir un échantillon conjoint approximatif $(\theta^{(t)}, A^{(t)})$.
2. Sélectionner le vecteur de traitement $Z_t$ qui maximise la récompense totale attendue échantillonnée : $Z_t = \arg\max_{Z: \|Z\|_1 \le B} \mathbf{1}^\top H(Z; A^{(t)}) \theta^{(t)}$.
3. Observer les récompenses et mettre à jour l'historique $\mathcal{D}_t$.
4. Démarrer à chaud la chaîne Gibbs du tour suivant avec l'échantillon final du tour courant.

4. Variante Explore-Then-Commit (ETC)

Pour les récompenses NIA générales où l'effondrement modulaire ne s'applique pas, les auteurs analysent une stratégie ETC :

• Phase 1 : Traiter chaque nœud isolément pendant $m$ tours pour estimer les probabilités d'arêtes basées sur les débordements observés.
• Phase 2 : Exécuter un algorithme standard d'échantillonnage de Thompson (en supposant que le réseau est connu) en utilisant le graphe estimé $\hat{A}$.

Contributions clés

1. Cadre d'apprentissage conjoint : L'article formule le problème conjoint de la récupération du réseau et de l'allocation adaptative des traitements sous NIA. Il introduit un algorithme d'échantillonnage de Thompson qui utilise des balayages Gibbs par arêtes pour échantillonner la posterior conjointe du réseau et des paramètres de récompense.
2. Inférence causale en aval : Le réseau estimé $\hat{A}$ n'est pas simplement un sous-produit mais un livrable scientifique. Il soutient l'estimation post-expérimentale des effets directs, indirects et totaux du traitement, ainsi que la conception d'expériences de suivi.
3. Bornes théoriques de regret :
   • Modèles de débordement additifs : Pour les modèles où la récompense totale est linéaire par rapport au vecteur de traitement avec des coefficients de score latents (par exemple, linéaire dans les moyennes), les auteurs prouvent une borne de regret bayésien de l'ordre de $O(\sqrt{nT \cdot B \log(en/B)})$ pour l'échantillonnage exact de la posterior. Cette borne dépend de la dimension du score latent $n$, et non de la dimension ambiante de $\theta$.
   • NIA générale : Pour les récompenses générales, la variante ETC atteint une borne de regret avec un coût de découverte de graphe de $O(n^2 \log T)$.
   • Borne inférieure : Une borne inférieure informationnelle de $\Omega(n \log T)$ est établie, démontrant que tout algorithme cohérent doit payer un coût linéaire en $n$ pour la découverte du réseau.
4. Évolutivité : La méthode s'adapte aux réseaux comportant des centaines de nœuds (jusqu'à $n=1000$ dans le cas linéaire dans les moyennes), surpassant significativement les méthodes existantes limitées à $n \approx 12$.

Résultats empiriques

• Performance du regret : Sur deux réseaux réels (un réseau de prêts d'argent entre ménages avec $n=63$ et un réseau d'amitié scolaire avec $n=121$), l'algorithme Gibbs-TS atteint un regret sous-linéaire. Bien qu'il existe un écart par rapport à un oracle connaissant le vrai réseau, le regret est significativement plus faible que celui des lignes de base qui ignorent l'interférence (qui subissent un regret linéaire).
• Comparaison avec l'état de l'art : Dans des comparaisons directes sur de petits réseaux ($n=8$) où Agarwal et al. (2024) est réalisable, Gibbs-TS réalise plus d'un ordre de grandeur de réduction du regret (par exemple, regret médian de 141 contre 1571 pour Agarwal et al. dans des conditions spécifiques).
• Récupération du réseau : L'algorithme récupère avec succès le réseau d'interférence avec une grande précision (scores F1 > 0,98 dans des contextes synthétiques et 0,74 dans des contextes réels).
• Estimation en aval : En utilisant le réseau récupéré $\hat{A}$, l'article démontre que les estimations des effets directs, indirects et totaux du traitement suivent de près celles obtenues en utilisant le vrai réseau, avec de faibles erreurs quadratiques moyennes (RMSE).

Importance et affirmations

L'article affirme fournir la première conception expérimentale adaptative qui apprend conjointement le réseau d'interférence et optimise les allocations de traitement au niveau individuel dans un cadre séquentiel sans nécessiter de structures de clusters prédéfinies.

• Valeur scientifique : Le réseau récupéré sert de résultat scientifique direct, permettant des analyses causales (effets directs/indirects) qui étaient auparavant inaccessibles dans des contextes adaptatifs.
• Impact pratique : La méthode comble le fossé entre l'inférence causale théorique sous interférence et l'expérimentation adaptative pratique à grande échelle. Elle permet aux plateformes et aux agences d'optimiser les interventions (par exemple, déploiement de vaccins, marketing) en temps réel tout en cartographiant simultanément les dynamiques sociales ou comportementales sous-jacentes.
• Perspective théorique : Le travail établit que, sous les modèles de débordement additifs, la complexité du problème se réduit à la dimension du vecteur de score latent, permettant des bornes de regret indépendantes de la complexité de la topologie du graphe.

Les auteurs reconnaissent des limitations, notamment la dépendance à une spécification correcte de la fonction de récompense, le goulot d'étranglement computationnel de la programmation linéaire en nombres entiers pour la sélection de traitement dans les contextes NIA généraux, et l'écart entre la borne supérieure $O(n^2)$ et la borne inférieure $\Omega(n)$ pour les coûts de découverte de graphe. Cependant, ils affirment que leur approche représente une avancée significative dans l'expérimentation adaptative évolutive sous interférence réseau inconnue.