📊 statistics

Adaptive Policy Learning Under Unknown Network Interference

Dieser Artikel schlägt einen Thompson-Sampling-Algorithmus vor, der mittels eines Gibbs-Samplers unbekannte Netzwerkkonfusionsdynamiken gemeinsam erlernt und individuelle Behandlungszuweisungen optimiert, wodurch ein sublineares bayesianisches Regret erreicht und eine präzise nachgelagerte Kausaleffekt-Schätzung in adaptiven Experimentierumgebungen ermöglicht wird.

Ursprüngliche Autoren: Aidan Gleich, Eric Laber, Alexander Volfovsky

Veröffentlicht 2026-05-13

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Aidan Gleich, Eric Laber, Alexander Volfovsky

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Manager eines großen sozialen Clubs. Sie haben ein begrenztes Budget, um Ihren Mitgliedern „Belohnungen" (wie kostenlosen Kaffee oder Rabatte) zu geben. Ihr Ziel ist es, den Club so glücklich und profitabel wie möglich zu machen.

Hier liegt der Haken: Sie wissen nicht genau, wer mit wem spricht. Tatsächlich wissen Sie nicht einmal, ob das Geben einer Belohnung an eine Person deren Freunde beeinflusst. Vielleicht wird Bob, ein Freund von Alice, einfach durch die Assoziation glücklich, wenn Sie Alice eine Belohnung geben. Oder vielleicht heben sich die Effekte auf, wenn Sie beiden Belohnungen geben. Dies wird als Interferenz bezeichnet.

Lange Zeit mussten Wissenschaftler, die versuchten, dieses Problem zu lösen, eine große Annahme treffen: „Nehmen wir an, wir kennen bereits die Freundschaftskarte", oder „Behandeln wir einfach ganze Gruppen von Menschen auf einmal, damit wir uns keine Gedanken über Einzelpersonen machen müssen." In der realen Welt haben Sie jedoch oft keine Karte, und das Behandeln ganzer Gruppen ist ineffizient.

Diese Arbeit stellt eine neue, intelligente Methode vor, um mit dieser Situation umzugehen. Denken Sie daran als an einen Detektiv, der die Karte lernt, während er das Spiel spielt.

Das Problem: Der „blinde" Manager

Normalerweise benötigen Sie zwei Dinge, um herauszufinden, wie Sie Belohnungen am besten verteilen:

Die Karte: Wer ist mit wem befreundet?
Die Strategie: Wer sollte die Belohnung erhalten, um das Glück zu maximieren?

Bestehende Methoden waren wie ein Manager, der entweder:

So tat, als hätte er bereits die Karte (was selten der Fall ist).
Auf eine individuelle Strategie verzichtete und einfach große, ungeschickte Gruppen behandelte.
Überfordert war, wenn der Club zu groß war (mehr als ein Dutzend Personen).

Die Lösung: Der „Gibbs"-Detektiv

Die Autoren (Aidan Gleich, Eric Laber und Alexander Volfovsky) entwickelten einen neuen Algorithmus, den sie Gibbs-TS nennen. Stellen Sie sich einen Detektiv vor, der zwei Dinge gleichzeitig tut:

Er spielt das Spiel: Er gibt einige Belohnungen aus, sieht, wie der Club reagiert, und berechnet den „Glückswert".
Er aktualisiert die Karte: Basierend auf den Reaktionen schätzt er, wer mit wem befreundet ist. Wenn Alice eine Belohnung erhält und Bob plötzlich glücklicher wirkt, denkt der Detektiv: „Aha! Alice und Bob sind wahrscheinlich befreundet."

Sie verwenden einen mathematischen Trick namens Gibbs-Sampler. Denken Sie daran als an eine „Was-wäre-wenn"-Maschine. Die Maschine führt Tausende von winzigen Simulationen in ihrem Kopf durch:

Szenario A: Was wäre, wenn Alice und Bob befreundet wären? Wie hätten die Belohnungen gewirkt?
Szenario B: Was wäre, wenn sie es nicht wären? Wie würde das aussehen?

Indem sie diese Szenarien immer wieder durchspielt, schränkt die Maschine die Wahrheit langsam ein. Sie erstellt eine best-geschätzte Karte der Freundschaften und ermittelt gleichzeitig die beste Strategie für die Verteilung von Belohnungen.

Warum dies eine große Sache ist

Die Arbeit behauptet, dass diese Methode in drei Hinsichten ein massives Upgrade darstellt:

1. Sie lernt die Karte und gewinnt das Spiel.
Die meisten anderen Methoden versuchen nur, das Spiel zu gewinnen, unter der Annahme, dass die Karte bekannt ist, oder sie versuchen, die Karte zu zeichnen, ohne sich um das Spiel zu kümmern. Diese Methode tut beides gleichzeitig. Es ist wie ein GPS, das die Straßenverhältnisse lernt, während Sie fahren, anstatt zu warten, bis Sie nach Hause kommen, um die Karte zu zeichnen.

2. Sie funktioniert bei großen Netzwerken.
Frühere Methoden konnten nur winzige Gruppen bewältigen (etwa 12 Personen). Diese neue Methode funktioniert bei Netzwerken mit Hunderten oder sogar Tausenden von Personen. Die Autoren testeten sie an echten Daten aus einem Dorf in Indien und einer Schule in den USA, und sie funktionierte hervorragend.

3. Sie erstellt einen „Bonus-Bericht".
Da der Algorithmus die Freundschaftskarte lernt, sagt er Ihnen nicht nur, wem Sie Belohnungen geben sollen; er liefert Ihnen eine rekonstruierte Karte des Netzwerks. Dies ist wertvoll für Wissenschaftler, die untersuchen wollen, wie sich Einfluss ausbreitet (wie sich ein Gerücht oder eine Krankheit durch eine Gruppe bewegt).

Die Ergebnisse: Weniger Reue, mehr Glück

In der Welt der Experimente ist „Reue" ein elegantes Wort für „verpasste Chancen". Wenn Sie einer falschen Person eine Belohnung gegeben haben, haben Sie „Reue", weil Sie mehr Glück hätten erzielen können, wenn Sie sie jemand anderem gegeben hätten.

Alte Methoden: Als sie die Tatsache ignorierten, dass Menschen sich gegenseitig beeinflussen, machten sie riesige Fehler (lineare Reue). Sie trafen immer wieder dieselben falschen Entscheidungen.
Diese neue Methode: Sie machte Fehler, lernte aber schnell. Die „Reue" wuchs sehr langsam (sublinear). In direkten Vergleichen machte diese neue Methode 10-mal weniger Fehler als der nächste beste Konkurrent.

Das Fazit

Die Arbeit stellt ein Werkzeug vor, das es Forschern ermöglicht, Experimente in unübersichtlichen, realen sozialen Netzwerken durchzuführen, in denen sie die Verbindungen zwischen den Menschen nicht kennen. Es lernt die Verbindungen im laufenden Betrieb, während es versucht, die besten Ergebnisse zu erzielen.

Die Autoren bewiesen mathematisch, dass dieser Ansatz effizient ist, und zeigten durch Computersimulationen und reale Daten, dass er viel besser funktioniert als frühere Methoden. Sie stellten auch fest, dass die von ihm erstellte Karte später verwendet werden kann, um andere wissenschaftliche Fragen darüber zu beantworten, wie Menschen sich gegenseitig beeinflussen.

Kurz gesagt: Es ist ein intelligentes, selbstlernendes System, das das verborgene soziale Netz entschlüsselt und gleichzeitig den besten Weg findet, Menschen zu helfen, alles ohne eine im Voraus gezeichnete Karte.

Technisches Fazit: Adaptives Policy-Lernen unter unbekannter Netzwerk-Interferenz

Problemstellung

In vielen experimentellen Settings hängt das Ergebnis einer Einheit nicht nur von ihrer eigenen Behandlung ab, sondern auch von den Behandlungen, die ihren Nachbarn innerhalb eines zugrunde liegenden Netzwerks zugewiesen werden. Dieses Phänomen, bekannt als Interferenz oder Spillover, verletzt die Stable Unit Treatment Value Assumption (SUTVA). Während die Literatur zur kausalen Inferenz robuste Methoden für statische Experimente unter Interferenz entwickelt hat (z. B. Sussman und Airoldi, 2017; Aronow und Samii, 2017), gehen diese Ansätze typischerweise davon aus, dass das Interferenznetzwerk bekannt ist, oder stützen sich auf grobe Randomisierungen auf Cluster-Ebene.

Bestehende adaptive (sequenzielle) Experimentiermethoden weisen erhebliche Einschränkungen auf:

Annahme eines bekannten Netzwerks: Skalierbare Methoden wie Gleich et al. (2025) gehen davon aus, dass die Netzwerkstruktur vollständig beobachtet ist, was in vielen Anwendungen unrealistisch ist, in denen soziale oder verhaltensbezogene Bindungen latent sind.
Skalierbarkeitsprobleme: Methoden, die versuchen, die Netzwerkstruktur zu lernen, wie z. B. Agarwal et al. (2024), stützen sich auf Fourier-Analysen über alle möglichen Nachbarkonfigurationen, was zu einer Parameteranzahl führt, die exponentiell in der Nachbarschaftsgröße wächst. Diese Methoden skalieren nicht über etwa $n \approx 12$ Einheiten hinaus.
Verlust der Granularität: Andere adaptive Designs (z. B. Viviano und Rudder, 2024) operieren auf vordefinierten Clustern, umgehen die Optimierung auf individueller Ebene und scheitern daran, das Interferenznetzwerk selbst zu rekonstruieren.

Die zentrale Herausforderung, die von diesem Papier adressiert wird, besteht darin, das unbekannte Interferenznetzwerk gemeinsam zu lernen und die Behandlungszuweisungen auf individueller Ebene in einem sequenziellen Setting zu optimieren, um kumulative Ergebnisse (z. B. Umsatz, Gesundheitskennzahlen) zu maximieren.

Methodik

Die Autoren schlagen ein Thompson-Sampling (TS)-Rahmenwerk vor, das mithilfe eines Gibbs-Samplers gemeinsam das Interferenznetzwerk und die Belohnungsparameter inferiert.

1. Modellaufbau

Setting: Sequenzielle Zuweisung binärer Behandlungen $Z_t \in \{0, 1\}^n$ an $n$ Einheiten über $T$ Runden, unterliegt einer Budgetbeschränkung $\|Z_t\|_1 \le B$ .
Annahme der Nachbarschaftsinterferenz (NIA): Das Ergebnis der Einheit $i$ hängt nur von ihrer eigenen Behandlung und den Behandlungen ihrer Nachbarn ab, die durch eine unbekannte Adjazenzmatrix $A$ definiert sind.
Belohnungsmodell: Der erwartete Output ist linear in einem Parametervektor $\theta$ , d. h., $r(Z; A, \theta) = H(Z; A)\theta$ . Die Designmatrix $H$ hängt vom Netzwerk $A$ ab.

2. Gemeinsames Posterior-Sampling via Gibbs

Da die Likelihood-Funktion in $A$ nicht-linear ist (aufgrund der Nachbarnummern), steht eine geschlossene Form des Posteriors nicht zur Verfügung. Die Autoren setzen einen kantenweisen Gibbs-Sampler ein, um approximative gemeinsame Stichproben aus dem Posterior $\pi(\theta, A | \mathcal{D}_{t-1})$ zu ziehen:

Parameter-Update ( $\theta | A$ ): Bei festgehaltener $A$ reduziert sich das Modell auf eine Standard-konjugierte Gauß-Regression. Der Posterior für $\theta$ ist Gauß-verteilt.
Kanten-Update ( $A | \theta$ ): Bei festgehaltene $\theta$ durchläuft der Sampler alle Kanten $(i, j)$ . Die vollständige bedingte Verteilung für die Kante $A_{ij}$ hängt nur von den Belohnungsströmen der Knoten $i$ und $j$ ab. Die Update-Regel wird durch eine Logit-Transformation des Likelihood-Verhältnisses hergeleitet, was ein effizientes Sampling ermöglicht, ohne alle $2^{\binom{n}{2}}$ Graphkonfigurationen aufzuzählen.

3. Algorithmus (Gibbs-TS)

In jeder Runde $t$ :

Führen Sie $K$ Gibbs-Durchläufe durch, um eine approximative gemeinsame Stichprobe $(\theta^{(t)}, A^{(t)})$ zu erhalten.
Wählen Sie den Behandlungsvektor $Z_t$ , der die gesampelte erwartete Gesamtbelohnung maximiert: $Z_t = \arg\max_{Z: \|Z\|_1 \le B} \mathbf{1}^\top H(Z; A^{(t)}) \theta^{(t)}$ .
Beobachten Sie Belohnungen und aktualisieren Sie den Verlauf $\mathcal{D}_t$ .
Starten Sie die Gibbs-Kette der nächsten Runde warm mit der finalen Stichprobe der aktuellen Runde.

4. Explore-Then-Commit (ETC)-Variante

Für allgemeine NIA-Belohnungen, bei denen keine modulare Kollaps-Struktur vorliegt, analysieren die Autoren eine ETC-Strategie:

Phase 1: Behandeln Sie jeden Knoten isoliert für $m$ Runden, um Kantenwahrscheinlichkeiten basierend auf beobachteten Spillovers zu schätzen.
Phase 2: Führen Sie einen Standard-Thompson-Sampling-Algorithmus durch (unter der Annahme, dass das Netzwerk bekannt ist), unter Verwendung des geschätzten Graphen $\hat{A}$ .

Hauptbeiträge

Gemeinsames Lernrahmenwerk: Das Papier formuliert das gemeinsame Problem der Netzwerkwiederherstellung und der adaptiven Behandlungszuweisung unter NIA. Es führt einen Thompson-Sampling-Algorithmus ein, der kantenweise Gibbs-Durchläufe verwendet, um aus dem gemeinsamen Posterior des Netzwerks und der Belohnungsparameter zu sampeln.
Downstream-Kausale Inferenz: Das geschätzte Netzwerk $\hat{A}$ ist nicht nur ein Nebenprodukt, sondern ein wissenschaftliches Deliverable. Es unterstützt die nachträgliche Schätzung direkter, indirekter und totaler Behandlungseffekte sowie die Gestaltung von Folgeexperimenten.
Theoretische Regret-Schranken:
- Additive Spillover-Modelle: Für Modelle, bei denen die Gesamtbelohnung linear im Behandlungsvektor mit latenten Score-Koeffizienten ist (z. B. linear-in-means), beweisen die Autoren eine Bayessche Regret-Schranke der Ordnung $O(\sqrt{nT \cdot B \log(en/B)})$ für exaktes Posterior-Sampling. Diese Schranke hängt von der latenten Score-Dimension $n$ ab, nicht von der umgebenden Dimension von $\theta$ .
- Allgemeine NIA: Für allgemeine Belohnungen erreicht die ETC-Variante eine Regret-Schranke mit einem Graph-Entdeckungskosten von $O(n^2 \log T)$ .
- Untere Schranke: Eine informationstheoretische untere Schranke von $\Omega(n \log T)$ wird etabliert, was zeigt, dass jeder konsistente Algorithmus Kosten in linearer Abhängigkeit von $n$ für die Netzwerkwiedererkennung zahlen muss.
Skalierbarkeit: Die Methode skaliert auf Netzwerke mit Hunderten von Knoten (bis zu $n=1000$ unter linear-in-means), was bestehende Methoden, die auf $n \approx 12$ begrenzt sind, deutlich übertrifft.

Empirische Ergebnisse

Regret-Leistung: Auf zwei realen Netzwerken (ein Haushalt-Netzwerk für Geldverleih mit $n=63$ und ein Freundschaftsnetzwerk an Schulen mit $n=121$ ) erreicht der Gibbs-TS-Algorithmus sublineares Regret. Zwar besteht eine Lücke im Vergleich zu einem Oracle, das das wahre Netzwerk kennt, doch ist das Regret signifikant niedriger als bei Baselines, die Interferenz ignorieren (die lineares Regret erleiden).
Vergleich mit dem State-of-the-Art: In direkten Vergleichen auf kleinen Netzwerken ( $n=8$ ), bei denen Agarwal et al. (2024) machbar ist, erreicht Gibbs-TS eine Reduktion des Regrets um mehr als eine Größenordnung (z. B. medianes Regret von 141 vs. 1571 für Agarwal et al. unter spezifischen Bedingungen).
Netzwerkwiedererkennung: Der Algorithmus stellt das Interferenznetzwerk mit hoher Genauigkeit wieder her (F1-Scores > 0,98 in synthetischen Settings und 0,74 in realen Settings).
Downstream-Schätzung: Unter Verwendung des wiederhergestellten Netzwerks $\hat{A}$ zeigt das Papier, dass Schätzungen direkter, indirekter und totaler Behandlungseffekte eng denen folgen, die unter Verwendung des wahren Netzwerks erhalten wurden, mit kleinen Root Mean Squared Errors (RMSE).

Bedeutung und Behauptungen

Das Papier behauptet, das erste adaptive Experimentaldesign zu liefern, das das Interferenznetzwerk gemeinsam lernt und die Behandlungszuweisungen auf individueller Ebene in einem sequenziellen Setting optimiert, ohne vordefinierte Cluster-Strukturen zu erfordern.

Wissenschaftlicher Wert: Das wiederhergestellte Netzwerk dient als direktes wissenschaftliches Ergebnis und ermöglicht kausale Analysen (direkte/indirekte Effekte), die in adaptiven Settings zuvor nicht zugänglich waren.
Praktische Auswirkungen: Die Methode schließt die Lücke zwischen theoretischer kausaler Inferenz unter Interferenz und praktischem, großflächigem adaptivem Experimentieren. Sie ermöglicht Plattformen und Behörden, Interventionen (z. B. Impfkampagnen, Marketing) in Echtzeit zu optimieren und gleichzeitig die zugrunde liegenden sozialen oder verhaltensbezogenen Dynamiken zu kartieren.
Theoretische Einsicht: Die Arbeit stellt fest, dass sich unter additiven Spillover-Modellen die Komplexität des Problems auf die Dimension des latenten Score-Vektors reduziert, was Regret-Schranken ermöglicht, die unabhängig von der Komplexität der Graphentopologie sind.

Die Autoren erkennen Einschränkungen an, darunter die Abhängigkeit von einer korrekten Spezifikation der Belohnungsfunktion, den Rechenengpass der ganzzahligen linearen Programmierung für die Behandlungsauswahl in allgemeinen NIA-Settings sowie die Lücke zwischen der $O(n^2)$ -oberen Schranke und der $\Omega(n)$ -unteren Schranke für Graph-Entdeckungskosten. Sie betonen jedoch, dass ihr Ansatz einen bedeutenden Schritt nach vorne in Richtung skalierbarem, adaptivem Experimentieren unter unbekannter Netzwerkinterferenz darstellt.