Scalable Policy Maximization Under Network Interference

Technische Samenvatting: Schaalbare Policy-Maximalisatie onder Netwerkinterferentie

Probleemstelling
Het artikel behandelt de uitdaging van sequentiële besluitvorming (policy-maximalisatie) in omgevingen die worden gekenmerkt door netwerkinterferentie, waarbij de behandelingsstatus van één individu de uitkomsten van anderen beïnvloedt. Hoewel Multi-Armed Bandit (MAB)-algoritmen de standaard zijn voor sequentieel leren, vertrouwen zij doorgaans op onafhankelijkheidsaannames die falen in netwerkomgevingen (bijvoorbeeld klinische trials, online marktplaatsen, sociale netwerken).

Bestaande benaderingen voor MAB's onder interferentie lopen tegen twee kritieke beperkingen aan:

1. Schaalbaarheid: Huidige methoden hebben moeite om te schalen buiten zeer kleine netwerken (ongeveer $n \approx 15$ knopen). Zij proberen vaak willekeurige interferentiepatronen te vangen, wat leidt tot een parameterruimte die exponentieel groeit met de knoopgraad ($d_{max}$) en lineair met de netwerkgrootte ($n$). Voor een netwerk met $n=1000$ en $d_{max}=10$ resulteert dit in meer dan een miljoen onbekende parameters, wat schatting computationeel onuitvoerbaar maakt.
2. Statische Aannames: Veel bestaande algoritmen vereisen dat de netwerkstructuur en de populatie van individuen in de tijd constant blijven, een aanname die inconsistenties creëert in dynamische omgevingen waaruitkomsten afhangen van historische behandelingsstatussen.

Methodologie
De auteurs stellen een schaalbaar Thompson Sampling-algoritme voor dat gebruikmaakt van structurele aannames die gangbaar zijn in de causale inferentieliteratuur om een parsimonische lineaire parametrisatie van de beloningsfunctie te bereiken.

• Structurele Aannames (SANIA): De methode vertrouwt op de Symmetrische en Additieve Buurinterferentie-Aanname (SANIA).

  • Buurinterferentie (NIA): De beloning van een knoop hangt alleen af van zijn eigen behandeling en de behandelingsstatus van zijn directe buren.
  • Additiviteit: Directe effecten interageren niet met indirecte (spillover) effecten.
  • Symmetrie: De beloning van een knoop hangt af van het aantal behandelde buren, niet van hun specifieke identiteit.
    Onder deze aannames kan de vector van knoopniveau-beloningen worden herparametriseerd als een lineair systeem: $r_t = H(Z_t; A_t)\theta + \epsilon_t$, waarbij $\theta$ een laag-dimensionale parametervector is die behandelings- en interferentie-effectparameters bevat.

• Algoritme-ontwerp:

  • Het algoritme onderhoudt een posteriorverdeling over de parametervector $\theta$.
  • Op elk tijdstip $t$ steekt het een parametervector $\theta^{(t)}$ uit de posterior en selecteert een toewijzingsvector voor behandeling $Z_t$ die de totale verwachte beloning maximaliseert, conditioneel op $\theta^{(t)}$.
  • Het kader ondersteunt flexibele parametrisaties, waaronder gedeelde parameters (alle knopen delen $\theta$), gegroepeerde parameters (knopen in latente of waargenomen groepen delen $\theta_g$) en latente kenmodelmodellen (waarbij knoopposities in een Euclidische ruimte de beloningen beïnvloeden).
  • Het algoritme komt tegemoet aan dynamische netwerken (waarbij burenmatrices $A_t$ veranderen) en begrotingsbeperkingen (beperking van het aantal behandelde knopen).

• Regret-analyse:

  • De auteurs bewijzen een bovengrens voor Bayesiaanse regret van $O(D\sqrt{nT} \log(nT))$, waarbij $D$ de dimensie van $\theta$ is, $n$ de netwerkgrootte en $T$ de tijds horizon.
  • Zij leiden een overeenkomstige ondergrens af van $\Omega(D\sqrt{nT})$, wat aantoont dat het algoritme bijna optimaal is.
  • De regretgrenzen weerspiegelen de afweging tussen de verhoogde informatie die wordt verkregen door het observeren van $n$ onderling afhankelijke knopen en de verhoogde complexiteit van de actieruimte.

Belangrijkste Bijdragen

1. Schaalbare Parametrisatie: Het artikel toont aan dat gangbare aannames voor causale inferentie het mogelijk maken de beloningsfunctie uit te drukken als een lineaire functie van een laag-dimensionale parametervector, waardoor de complexiteit wordt gereduceerd van exponentieel naar polynomiaal (specifiek lineair in $n$ voor gedeelde/gegroepeerde modellen).
2. Schaalbaar Thompson Sampling: De auteurs ontwikkelen een algoritme dat netwerken kan verwerken die ordes van grootte groter zijn dan eerdere methoden (gedemonstreerd tot $n=1000$ in simulaties), waarmee de "vloek van de dimensionaliteit" die inherent is aan interferentieproblemen wordt opgelost.
3. Omgaan met Dynamische Netwerken: In tegenstelling tot eerdere werken die vaste netwerken vereisen, staat dit kader toe dat zowel knopen als randen in elke tijdsperiode worden bemonsterd of veranderen, waarmee inconsistenties tussen temporele onafhankelijkheid en aannames over een vaste populatie worden opgelost.
4. Theoretische Garanties: Het artikel biedt rigoureuze boven- en ondergrenzen voor Bayesiaanse regret, waarmee de bijna-optimaliteit van de voorgestelde aanpak wordt vastgesteld.

Resultaten
Simulatie-experimenten valideren de methode over drie parametrisatieschema's:

• Gedeelde Parameters: Het algoritme leert snel en schaalt effectief voor netwerken van grootte $n \in \{100, 500, 1000, 2500\}$.
• Gegroepeerde Parameters: De methode presteert goed zelfs wanneer groepslabels deels latent zijn en moeten worden geschat met behulp van een "anker"-knoop per groep.
• Latente Kenmerken: Het algoritme verwerkt succesvol heterogene effecten die afhankelijk zijn van latente knoopkenmerken in modellen voor latente ruimten.

Vergelijkingen:

• vs. Agarwal et al. (2024): De voorgestelde methode presteert aanzienlijk beter dan de bestaande state-of-the-art (die Fourier-analyse en schaarse netwerkinterferentie gebruikt) op kleine statische netwerken. Cruciaal blijft de voorgestelde methode robuust en presteert deze beter dan Agarwal et al., zelfs wanneer de SANIA-aannames verkeerd gespecificeerd zijn (bijvoorbeeld wanneer additiviteit of symmetrie wordt geschonden). Dit wordt toegeschreven aan het vermogen van de voorgestelde methode om een effectieve benadering te leren met veel minder parameters, terwijl concurrerende methoden lijden onder hoge variantie vanwege de noodzaak om exponentieel grotere parametervectoren te schatten.
• vs. Standaard MAB: Standaard MAB-benaderingen falen in schaalbaarheid vanwege de exponentiële groei van de actieruimte ($2^n$ armen).

Betekenis
Het artikel claimt een belangrijke schaalbaarheidskloof te dichten tussen methoden voor causale inferentie voor interferentie en praktische banditalgoritmen. Door policy-optimalisatie in grootschalige netwerksystemen mogelijk te maken, overbrugt dit werk de kloof tussen theoretische causale identificatie en dynamische besluitvorming. De auteurs suggereren dat dit kader de toepassing van banditalgoritmen op real-world problemen faciliteert die grote, dynamische netwerken omvatten, zoals vaccinverdeling of interventies op online marktplaatsen, waar interferentie wijdverbreid is maar tot nu toe te complex was om dynamisch te modelleren.