Technische Samenvatting: Adaptief Beleid Leren onder Onbekende Netwerkinvloed

Probleemstelling

In veel experimentele settings hangt het resultaat van een eenheid niet alleen af van de eigen behandeling, maar ook van de behandelingen die zijn toegewezen aan zijn buren binnen een onderliggend netwerk. Dit fenomeen, bekend als invloed of spillover, schendt de Stable Unit Treatment Value Assumption (SUTVA). Hoewel de literatuur over causale inferentie robuuste methoden heeft ontwikkeld voor statische experimenten onder invloed (bijv. Sussman en Airoldi, 2017; Aronow en Samii, 2017), gaan deze benaderingen doorgaans uit van een bekend invloedsnetwerk of vertrouwen ze op grove randomisatie op cluster-niveau.

Bestaande adaptieve (sequentiële) experimentatiemethoden staan voor aanzienlijke beperkingen:

1. Aanneming van een Bekend Netwerk: Schaalbare methoden zoals Gleich et al. (2025) gaan uit van een volledig waargenomen netwerkstructuur, wat in veel toepassingen onrealistisch is waar sociale of gedragsbanden latent zijn.
2. Schaalbaarheidsproblemen: Methoden die proberen de netwerkstructuur te leren, zoals Agarwal et al. (2024), vertrouwen op Fourier-analyse over alle mogelijke buurconfiguraties, wat resulteert in een aantal parameters dat exponentieel toeneemt met de omvang van de buurt. Deze methoden schalen niet verder dan ongeveer $n \approx 12$ eenheden.
3. Verlies van Granulariteit: Andere adaptieve ontwerpen (bijv. Viviano en Rudder, 2024) werken op vooraf gedefinieerde clusters, omzeilen optimalisatie op individueel niveau en slagen er niet in om het invloedsnetwerk zelf te herstellen.

De kernuitdaging die door dit artikel wordt aangepakt, is het gezamenlijk leren van het onbekende invloedsnetwerk en het optimaliseren van toewijzingen van behandelingen op individueel niveau in een sequentiële setting om cumulatieve uitkomsten (bijv. omzet, gezondheidsindicatoren) te maximaliseren.

Methodologie

De auteurs stellen een Thompson Sampling (TS)-kader voor dat gezamenlijk het invloedsnetwerk en de beloningsparameters infereert met behulp van een Gibbs-sampler.

1. Modelopzet

• Setting: Sequentiële toewijzing van binaire behandelingen $Z_t \in \{0, 1\}^n$ aan $n$ eenheden over $T$ rondes, onderworpen aan een begrotingsbeperking $\|Z_t\|_1 \le B$.
• Aanneming van Buurinvloed (NIA): Het resultaat van eenheid $i$ hangt alleen af van de eigen behandeling en de behandelingen van zijn buren, gedefinieerd door een onbekende adjacentiematrix $A$.
• Beloningsmodel: De verwachte uitkomst is lineair in een parametervector $\theta$, d.w.z. $r(Z; A, \theta) = H(Z; A)\theta$. De ontwerpmatrix $H$ hangt af van het netwerk $A$.

2. Gezamenlijke Posterior Sampling via Gibbs

Omdat de waarschijnlijkheid niet-lineair is in $A$ (door buurtellingen), is een gesloten vorm voor de posterior niet beschikbaar. De auteurs maken gebruik van een edge-wise Gibbs-sampler om benaderde gezamenlijke steekproeven te trekken uit de posterior $\pi(\theta, A | \mathcal{D}_{t-1})$:

• Parameter Update ($\theta | A$): Met $A$ vastgesteld, reduceert het model tot een standaard geconjugeerde Gaussische regressie. De posterior voor $\theta$ is Gaussisch.
• Edge Update ($A | \theta$): Met $\theta$ vastgesteld, scant de sampler alle edges $(i, j)$. De volledige conditionele verdeling voor edge $A_{ij}$ hangt alleen af van de beloningsstromen van knopen $i$ en $j$. De update-regel wordt afgeleid via een logit-transformatie van de waarschijnlijkheidsverhouding, wat efficiënt sampling mogelijk maakt zonder alle $2^{\binom{n}{2}}$ grafconfiguraties te enumereren.

3. Algorithmus (Gibbs-TS)

In elke ronde $t$:

1. Voer $K$ Gibbs-sweeps uit om een benaderde gezamenlijke steekproef $(\theta^{(t)}, A^{(t)})$ te verkrijgen.
2. Selecteer de treatment-vector $Z_t$ die de gesamplede verwachte totale beloning maximaliseert: $Z_t = \arg\max_{Z: \|Z\|_1 \le B} \mathbf{1}^\top H(Z; A^{(t)}) \theta^{(t)}$.
3. Observeer beloningen en update de geschiedenis $\mathcal{D}_t$.
4. Start de Gibbs-keten van de volgende ronde warm met de laatste steekproef van de huidige ronde.

4. Variant Explore-Then-Commit (ETC)

Voor algemene NIA-beloningen waarbij modulaire ineenstorting niet geldt, analyseren de auteurs een ETC-strategie:

• Fase 1: Behandel elke knoop geïsoleerd gedurende $m$ rondes om kansen op edges te schatten op basis van waargenomen spillovers.
• Fase 2: Voer een standaard Thompson Sampling-algoritme uit (onder de aanname dat het netwerk bekend is) met behulp van de geschatte grafiek $\hat{A}$.

Belangrijkste Bijdragen

1. Gezamenlijk Leerframework: Het artikel formuleert het gezamenlijke probleem van netwerkherschrijving en adaptieve toewijzing van behandelingen onder NIA. Het introduceert een Thompson Sampling-algoritme dat edge-wise Gibbs-sweeps gebruikt om te samplen uit de gezamenlijke posterior van het netwerk en de beloningsparameters.
2. Causale Inferentie Downstream: De geschatte netwerk $\hat{A}$ is niet louter een bijproduct, maar een wetenschappelijke leverancier. Het ondersteunt post-experimentele schatting van directe, indirecte en totale behandelingseffecten, evenals het ontwerp van vervollexperimenten.
3. Theoretische Regret-grenzen:
   • Additieve Spillover-modellen: Voor modellen waarbij de totale beloning lineair is in de treatment-vector met latente scorecoëfficiënten (bijv. lineair-in-middens), bewijzen de auteurs een Bayesiaanse regret-grens van de orde $O(\sqrt{nT \cdot B \log(en/B)})$ voor exacte posterior sampling. Deze grens hangt af van de dimensie van de latente score $n$, niet van de omgevingsdimensie van $\theta$.
   • Algemene NIA: Voor algemene beloningen bereikt de ETC-variant een regret-grens met een kostprijs voor grafiekontdekking van $O(n^2 \log T)$.
   • Ondergrens: Een informationeel-theoretische ondergrens van $\Omega(n \log T)$ wordt vastgesteld, wat aantoont dat elke consistente algoritme een kost moet betalen die lineair is in $n$ voor netwerkontdekking.
4. Schaalbaarheid: De methode schaalt naar netwerken met honderden knopen (tot $n=1000$ onder lineair-in-middens), wat aanzienlijk beter presteert dan bestaande methoden die beperkt zijn tot $n \approx 12$.

Empirische Resultaten

• Regret-prestaties: Op twee real-world netwerken (een netwerk van huishoudens dat geld leent met $n=63$ en een schoolvriendschapsnetwerk met $n=121$) bereikt het Gibbs-TS-algoritme sublineaire regret. Hoewel er een kloof is ten opzichte van een orakel dat het ware netwerk kent, is de regret aanzienlijk lager dan bij baselines die invloed negeren (die lijnare regret lijden).
• Vergelijking met State-of-the-Art: In rechtstreekse vergelijkingen op kleine netwerken ($n=8$) waar Agarwal et al. (2024) haalbaar is, bereikt Gibbs-TS meer dan een orde van grootte reductie in regret (bijv. mediane regret van 141 versus 1571 voor Agarwal et al. onder specifieke omstandigheden).
• Netwerkherschrijving: Het algoritme herstelt het invloedsnetwerk succesvol met hoge nauwkeurigheid (F1-scores > 0,98 in synthetische settings en 0,74 in real-world settings).
• Downstream Schatting: Met behulp van het herstelde netwerk $\hat{A}$ toont het artikel aan dat schattingen van directe, indirecte en totale behandelingseffecten nauw overeenkomen met die verkregen met het ware netwerk, met kleine Root Mean Squared Errors (RMSE).

Betekenis en Claims

Het artikel claimt de eerste adaptieve experimentele opzet te bieden die gezamenlijk het invloedsnetwerk leert en toewijzingen van behandelingen op individueel niveau optimaliseert in een sequentiële setting zonder vooraf gedefinieerde clusterstructuren.

• Wetenschappelijke Waarde: Het herstelde netwerk dient als directe wetenschappelijke output, wat causale analyses (directe/indirecte effecten) mogelijk maakt die eerder ontoegankelijk waren in adaptieve settings.
• Praktische Impact: De methode overbrugt de kloof tussen theoretische causale inferentie onder invloed en praktische, grootschalige adaptieve experimentatie. Het stelt platforms en agents in staat om interventies (bijv. vaccinatiecampagnes, marketing) in real-time te optimaliseren, terwijl ze tegelijkertijd de onderliggende sociale of gedragsdynamiek in kaart brengen.
• Theoretisch Inzicht: Het werk stelt vast dat onder additieve spillover-modellen de complexiteit van het probleem reduceert tot de dimensie van de vector met latente scores, wat regret-grenzen mogelijk maakt die onafhankelijk zijn van de complexiteit van de grafiektopologie.

De auteurs erkennen beperkingen, waaronder de afhankelijkheid van een correcte specificatie van de beloningsfunctie, de computatief knelpunt van integer lineaire programmering voor selectie van behandelingen in algemene NIA-settings, en de kloof tussen de bovengrens van $O(n^2)$ en de ondergrens van $\Omega(n)$ voor kosten van grafiekontdekking. Zij stellen echter dat hun benadering een aanzienlijke stap voorwaarts vertegenwoordigt in schaalbare, adaptieve experimentatie onder onbekende netwerkinvloed.