Technisches Resümee: Fixed-Confidence Best-Arm-Identification für Kausale Mediationsanalyse

1. Problemdefinition

Diese Arbeit befasst sich mit dem Problem der Best-Arm-Identification (BAI) in einem kausalen Bandit-Szenario, wobei der Schwerpunkt spezifisch auf der kausalen Mediationsanalyse liegt.

• Kontext: In Standard-kausalen Banditen besteht das Ziel typischerweise darin, den interventionellen Mittelwert $E[Y | do(X=x)]$ zu maximieren, der die Effekte über alle kausalen Pfade hinweg aggregiert. Forscher möchten jedoch häufig den Effekt einer Behandlung $X$ auf ein Ergebnis $Y$ isolieren, der nicht über einen spezifischen Mediator $Z$ verläuft (z. B. um unethische Mechanismen, Positionierungs-Bias in Werbeanzeigen oder unerwünschte Zwischenreaktionen auszuschließen).
• Zielsetzung: Das Ziel der Arbeit ist die Identifizierung des Arms $x^*$, der den erwarteten natürlichen direkten potenziellen Outcome (Natural Direct Potential Outcome, NDPO) maximiert, definiert als $E[Y_{x, Z_{x_0}}]$. Diese Größe repräsentiert den erwarteten Outcome, wenn die Behandlung auf $x$ gesetzt wird, während der Mediator $Z$ auf dem Wert gehalten wird, den er unter einem Referenzarm $x_0$ angenommen hätte.
• Szenario: Das Problem wird in einem Fixed-Confidence-Setting formuliert. Ein Lerner zieht sequenziell Arme (Interventionen $do(X=x)$) und beobachtet i.i.d. Stichproben aus der interventionellen Verteilung $P(Z, Y | do(X=x))$. Das Ziel ist es, den optimalen Arm mit einer Wahrscheinlichkeit von mindestens $1-\delta$ zu identifizieren, während die erwartete Stoppzeit (Stichprobenkomplexität) minimiert wird.

2. Methodik

2.1 Identifikation auf Populationsebene

Die Autoren stellen zunächst fest, dass der erwartete NDPO unter den beobachtbaren interventionellen Verteilungen in einem kausalen Bandit-Setting identifizierbar ist.

• Annahme: Sie stützen sich auf die Standard-Identifikationsannahme für natürliche direkte Effekte: $Y_{x,z} \perp\!\!\perp Z_{x'}$ für alle $x, x', z$. Grafisch entspricht dies dem Fehlen nicht gemessener Konfundierung zwischen dem Mediator $Z$ und dem Outcome $Y$ in dem Graphen, in dem die ausgehenden Kanten von $X$ und $Z$ entfernt wurden.
• Identifikationsformel: Unter dieser Annahme ist der erwartete NDPO $\theta(x)$ wie folgt identifiziert:
  $$\theta(x) = \sum_{y,z} y P(Y=y | Z=z, do(X=x)) P(Z=z | do(X=x_0))$$
  Diese Formulierung ermöglicht die Schätzung unter Verwendung lediglich der gemeinsamen interventionellen Verteilungen $P(Z, Y | do(X=x))$ und $P(Z | do(X=x_0))$, wodurch die Notwendigkeit verschachtelter Counterfactuals, die im Bandit-Setting nicht direkt beobachtbar sind, vermieden wird.

2.2 Untergrenze der Stichprobenkomplexität

Die Arbeit leitet eine instanzabhängige Untergrenze für die Stichprobenkomplexität für jeden $\delta$-korrekten Algorithmus ab.

• Wesentlicher Unterschied zu Standard-BAI: Im Gegensatz zum Standard-BAI, bei dem das Ziel nur von der eigenen Verteilung des Arms abhängt, koppelt der NDPO die Outcome-Verteilung unter Arm $x$ mit der Mediator-Verteilung unter dem Baseline-Arm $x_0$.
• Komplexitätsstruktur: Die Untergrenze beinhaltet ein semi-infinites Optimierungsproblem. Die charakteristische Zeit $T^*(P)$ ist definiert durch:
  $$(T^*(P))^{-1} = \sup_{w \in \Sigma_K} \inf_{Q \in \text{Alt}(P)} \sum_{x \in \mathcal{X}} w_x KL(P_x \| Q_x)$$
  wobei $\text{Alt}(P)$ die Menge der alternativen Modelle ist, in denen ein anderer Arm optimal ist. Die die $\text{Alt}(P)$ definierende Beschränkung ist nicht-separabel, da die Baseline-Mediator-Verteilung $Q_{x_0}(Z)$ in der Zielgröße für jeden Arm erscheint, was eine Kopplung über die Arme hinweg erzeugt, die im klassischen BAI nicht existiert.

2.3 Vorgeschlagener Algorithmus: TaS-NDPO

Die Autoren schlagen TaS-NDPO vor, einen Track-and-Stop (TaS) Algorithmus, der für dieses spezifische Ziel angepasst wurde. Der Algorithmus besteht aus drei Hauptkomponenten:

1. Plug-in Schätzung: Empirische Schätzungen der interventionellen Verteilungen werden verwendet, um Plug-in-Schätzungen von $\theta(x)$ zu berechnen.
2. Sampling-Regel (D-tracking mit Forcing):
   • D-tracking: Der Algorithmus verfolgt die optimalen Sampling-Anteile $w^*$, die aus der Untergrenze abgeleitet wurden.
   • Kompetitor-Abdeckung: Um die nicht-separablen Beschränkungen zu handhaben, stellt der Algorithmus sicher, dass jeder Arm als „Kompetitor“ im Optimierungsproblem ausreichend oft ausgewählt wird.
   • Cell-level Forcing: Entscheidend ist, dass der Algorithmus die Exploration auf der Zellebene $(x, z)$ (Kombinationen aus Arm und Mediatorwert) erzwingt. Dies ist notwendig, da die KL-Divergenz in Termen zerfällt, die durch Mediator-Wahrscheinlichkeiten gewichtet sind; seltene Mediatorwerte müssen ausreichend oft beprobt werden, um eine konsistente Schätzung der bedingten Outcome-Wahrscheinlichkeiten $P(Y|Z, do(X))$ zu gewährleisten.
3. Stopp-Regel (GLRT): Der Algorithmus stoppt, wenn die Generalized Likelihood Ratio Test (GLRT) Statistik einen Schwellenwert $\beta(t, \delta)$ überschreitet. Die Statistik misst die minimale KL-Divergenz zu jedem alternativen Modell, in dem ein suboptimaler Arm besser erscheint als der aktuelle empirische Beste.
4. Optimierungs-Solver: Das Lösen der inneren Minimierung in der Sampling-Regel und der Stopp-Regel beinhaltet ein semi-infinites Optimierungsproblem. Die Autoren verwenden eine Cutting-Set-Methode (Mutapçic und Boyd, 2009) komb in Verbindung mit einer Reduktion auf drei Arme (den Baseline-Arm, den aktuellen Besten und einen Kompetitor) sowie einem alternierenden Minimierungsschema, um die resultierenden bi-konvexen Teilprobleme zu lösen.

3. Wesentliche Beiträge

1. Problemformulierung: Die Arbeit definiert und untersucht formal das BAI-Problem zur Maximierung des erwarteten NDPO, einer Größe, die für die Isolierung direkter kausaler Effekte in Gegenwart von Mediatoren relevant ist.
2. Identifikation in Banditen: Sie etabliert die Identifikation des erwarteten NDPO unter Verwendung nur der verfügbaren interventionellen Verteilungen in einem kausalen Bandit-Setting und schlägt so eine Brücke zwischen kausaler Inferenztheorie und sequenzieller Entscheidungsfindung.
3. Theoretische Schranken: Sie leitet eine neue Untergrenze für die Stichprobenkomplexität ab, die die einzigartigen Herausforderungen der NDPO-Optimierung verdeutlicht, insbesondere die Kopplung der Arme über die Baseline-Mediator-Verteilung und die Notwendigkeit der Informationsakkumulation auf Zellebene.
4. Algorithmus-Design: Sie führt TaS-NDPO ein, einen neuartigen Algorithmus, der:
   • Eine Cutting-Set-Methode nutzt, um die komplexe semi-infinite Optimierung der optimalen Sampling-Anteile zu lösen.
   • Cell-level Forcing integriert, um Konsistenz in spärlichen (sparse) Mediator-Regimen zu gewährleisten.
   • $\delta$-Korrektheit (garantierte Korrektheit mit Wahrscheinlichkeit $1-\delta$) und ** asymptotische Optimalität** (Erreichen der Untergrenze der Stichprobenkomplexität als $\delta \to 0$) nachweist.

4. Experimentelle Ergebnisse

Die Autoren evaluierten TaS-NDPO sowohl mit synthetischen Daten als auch mit einem großen realen Werbedatensatz (IPinYou).

• Validierung in der realen Welt (IPinYou):
  • Der Datensatz beinhaltete die Auswahl von Werbemitteln ($X$), um Klicks ($Y$) zu maximieren, wobei die Slot-Sichtbarkeit ($Z$) als Mediator diente.
  • Entscheidungs-Divergenz: Der Arm, der den Standard-interventionellen Mittelwert maximiert, war ein anderer als derjenem, der den NDPO maximierte. Der Standard-Mittelwert bevorzugte ein Werbemittel, das häufig in Top-Slots erschien (mediierter Effekt), während der NDPO-optimale Arm ein anderer war.
  • Performance: TaS-NDPO erreichte eine mediane Stoppzeit von 12.928 Stichproben, was etwa 50 % effizienter ist als die Arm-Level-Variante (25.856 Stichproben), und übertraf Uniform-Sampling sowie einen Baseline-First-Ansatz deutlich. Alle Methoden hielten eine empirische Fehlerrate von Null bei $\delta=0,05$ ein.
• Synthetische Experimente:
  • Gap-Skalierung: Die Ergebnisse bestätigten die $1/\Delta^2$-Skalierung der Stichprobenkomplexität, wie sie durch die Untergrenze vorhergesagt wurde.
  • Mediator-Sparsity: Der Vorteil von Cell-level Forcing war in Settings mit seltenen Mediator-Outcome-Zellen (Sparse-Regime) am ausgeprägtesten, in denen Arm-level Forcing nicht genügend Informationen akkumulieren konnte.
  • Laufzeit: Der Rechenaufwand der Cutting-Set-Optimierung war moderat (durchschnittlich 22,5 Sekunden pro Durchlauf für bis zu 100k Stichproben) und stellte keinen Engpass im Vergleich zu den Gewinnen in der Stichprobeneffizienz dar.

5. Bedeutung und Ansprüche

Die Arbeit behauptet, dass TaS-NDPO eine theoretisch fundierte und empirisch effiziente Lösung zur Identifizierung von Behandlungen bietet, die direkte kausale Effekte maximieren, während vermittelte Pfade ausgeschlossen werden.

• Theoretische Bedeutung: Sie erweitert das Track-and-Stop-Framework auf kausale Settings mit verschachtelten Counterfactuals und beweist, dass asymptotische Optimalität auch dann erreichbar ist, wenn die Zielfunktion die Verteilungen über verschiedene Arme hinweg koppelt (über den Baseline-Mediator).
• Praktische Bedeutung: Durch die Isolierung direkter Effekte ermöglicht die Methode Entscheidungen, die unerwünschte Mechanismen (z. B. Clickbait, Nebenwirkungen oder unethische Positionierung) vermeiden, die bei Standard-Mittelwert-Maximierungsansätzen möglicherweise bevorzugt würden.
• Bescheidenheit: Die Autoren räumen ein, dass ihr aktueller Rahmen sich auf binäre Outcomes und eine spezifische kausale Graphstruktur (Mediator zwischen Treatment und Outcome) konzentriert. Sie merken an, dass die Erweiterung auf Multi-Kategorie-Outcomes trivial ist, die Generalisierung auf komplexere pfadspezifische Effekte in breiteren kausalen Strukturen jedoch eine Richtung für zukünftige Arbeiten bleibt. Sie stellen zudem klar, dass die Identifikation auf der Plausibilität des zugrunde liegenden kausalen Graphen beruht (speziell das Fehlen ungemessener Konfundierung zwischen $Z$ und $Y$), was eine Standard-, aber nicht testbare Annahme in der kausalen Inferenz ist.