Technische Samenvatting: Fixed-Confidence Best-Arm Identification voor Causale Mediatieanalyse

1. Probleemdefinitie

Dit artikel behandelt het probleem van Best-Arm Identification (BAI) binnen een causale bandit-setting, specifiek gericht op causale mediatieanalyse.

• Context: In standaard causale bandits is het doel doorgaans het maximaliseren van het interventionele gemiddelde $E[Y | do(X=x)]$, wat de effecten over alle causale paden aggregeert. Echter, onderzoekers willen vaak het effect van een behandeling $X$ op een uitkomst $Y$ isoleren dat niet verloopt via een specifieke mediator $Z$ (bijv. om onethische mechanismen, positioneringsbias in advertenties of nadelige intermediaire reacties uit te sluiten).
• Doelstelling: Het artikel beoogt de arm $x^*$ te identificeren die de Verwachte Natuurlijke Directe Potentiële Uitkomst (NDPO) maximaliseert, gedefinieerd als $E[Y_{x, Z_{x_0}}]$. Deze grootheid vertegenwoordigt de verwachte uitkomst als de behandeling wordt ingesteld op $x$, terwijl de mediator $Z$ de waarde aanneemt die het zou hebben onder een referentie-arm $x_0$.
• Setting: Het probleem is geformuleerd in een fixed-confidence setting. Een leerder trekt sequentieel armen (interventies $do(X=x)$) en observeert i.i.d. steekproeven uit de interventionele distributie $P(Z, Y | do(X=x))$. Het doel is om de optimale arm te identificeren met een waarschijnlijkheid van ten minste $1-\delta$, terwijl de verwachte stoptijd (steekproefcomplexiteit) wordt geminimaliseerd.

2. Methodologie

2.1 Identificatie op Populatieniveau

De auteurs stellen eerst vast dat de verwachte NDPO identificeerbaar is vanuit observeerbare interventionele distributies onder een causale bandit-setting.

• Aanname: Ze vertrouwen op de standaard identificatie-aanname voor natuurlijke directe effecten: $Y_{x,z} \perp\!\!\perp Z_{x'}$ voor alle $x, x', z$. Grafisch komt dit overeen met de afwezigheid van niet-gemeten confounding tussen de mediator $Z$ en de uitkomst $Y$ in de graaf waar de uitgaande randen van $X$ en $Z$ zijn verwijderd.
• Identificatieformule: Onder deze aanname is de verwachte NDPO $\theta(x)$ geïdentificeerd als:
  $$\theta(x) = \sum_{y,z} y P(Y=y | Z=z, do(X=x)) P(Z=z | do(X=x_0))$$
  Deze formulering maakt schatting mogelijk met behulp van enkel de gezamenlijke interventionele distributies $P(Z, Y | do(X=x))$ en $P(Z | do(X=x_0))$, waardoor de noodzaak voor geneste contrafeituele variabelen die niet direct observeerbaar zijn in de bandit-setting wordt vermeden.

2.2 Steekproefcomplexiteit Ondergrens

Het artikel leidt een instantie-afhankelijke ondergrens af voor de steekproefcomplexiteit voor elk $\delta$-correct algoritme.

• Belangrijk verschil met standaard BAI: In tegenstelling tot standaard BAI, waarbij de doelstelling alleen afhangt van de eigen distributie van de arm, koppelt de NDPO de uitkomstdistributie onder arm $x$ aan de mediatordistributie onder de baseline-arm $x_0$.
• Complexiteitsstructuur: De ondergrens betreft een semi-oneindig optimalisatieprobleem. De karakteristieke tijd $T^*(P)$ wordt gedefinieerd als:
  $$(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)$$
  waarbij $\text{Alt}(P)$ de verzameling alternatieve modellen is waarin een andere arm optimaal is. De beperking die $\text{Alt}(P)$ definieert is niet-scheidbaar omdat de baseline-mediatordistributie $Q_{x_0}(Z)$ in de doelstelling voor elke arm verschijnt, wat een koppeling creëert tussen armen die in klassieke BAI niet bestaat.

2.3 Voorgesteld Algoritme: TaS-NDPO

De auteurs stellen TaS-NDPO voor, een Track-and-Stop (TaS) algoritme aangepast voor deze specifieke doelstelling. Het algoritme bestaat uit drie hoofdonderdelen:

1. Plug-in Schatting: Empirische schattingen van de interventionele distributies worden gebruikt om plug-in schattingen van $\theta(x)$ te berekenen.
2. Sampling Regel (D-tracking met Forcing):
   • D-tracking: Het algoritme volgt de optimale sampling-proporties $w^*$ afgeleid van de ondergrens.
   • Competitor Coverage: Om de niet-scheidbare beperkingen aan te pakken, zorgt het algoritme ervoor dat elke arm voldoende vaak wordt geselecteerd als een "competitor" in het optimalisatieprobleem.
   • Cell-level Forcing: Cruciaal is dat het algoritme exploratie dwingt op celniveau $(x, z)$ (combinaties van arm en mediatorwaarde). Dit is noodzakelijk omdat de KL-divergentie uiteenvalt in termen gewogen door mediator-kansen; zeldzame mediatorwaarden moeten voldoende worden gesampled om consistente schattingen van de conditionele uitkomstkansen $P(Y|Z, do(X))$ te garanderen.
3. Stoppingsregel (GLRT): Het algoritme stopt wanneer de Generalized Likelihood Ratio Test (GLRT) statistiek een drempelwaarde $\beta(t, \delta)$ overschrijdt. De statistiek meet de minimale KL-divergentie naar elk alternatief model waar een suboptimale arm beter lijkt dan de huidige empirische beste arm.
4. Optimization Solver: Het oplossen van de innerlijke minimalisatie in de sampling-regel en de stoppingsregel omvat een semi-oneindig optimalisatieprobleem. De auteurs maken gebruik van een cutting-set methode (Mutapcic en Boyd, 2009) gecombineerd met een reductie naar drie armen (de baseline, de huidige beste, en een competitor) en een alternerende minimalisatieschema om de resulterende bi-convexe subproblemen op te lossen.

3. Belangrijkste Bijdragen

1. Probleemformulering: Het artikel definieert en bestudeert formeel het BAI-probleem voor het maximaliseren van de verwachte NDPO, een grootheid die relevant is voor het isoleren van directe causale effecten in de aanwezigheid van mediatoren.
2. Identificatie in Bandits: Het stelt de identificatie van de verwachte NDPO vast met behulp van enkel de beschikbare interventionele distributies in een causale bandit-setting, waarmee de brug wordt geslagen tussen causale inferentietheorie en sequentiële besluitvorming.
3. Theoretische Grenzen: Het leidt een nieuwe ondergrens voor de steekproefcomplexiteit af die de unieke uitdagingen van NDPO-optimalisatie benadrukt, specifiek de koppeling van armen via de baseline-mediatordistributie en de noodzaak voor informatieaccumulatie op celniveau.
4. Algoritmeontwerp: Het introduceert TaS-NDPO, een nieuw algoritme dat:
   • Een cutting-set methode gebruikt om de complexe semi-oneindige optimalisatie vereist voor de optimale sampling-proporties op te lossen.
   • Cell-level forcing incorporeert om consistentie te garanderen in scenario's met schaarse mediatoren.
   • $\delta$-correctheid ($\delta$-correctheid) bewijst (gegarandeerde correctheid met waarschijnlijkheid $1-\delta$) en asymptotische optimaliteit (het bereiken van de ondergrens op steekproefcomplexiteit als $\delta \to 0$).

4. Experimentele Resultaten

De auteurs evalueerden TaS-NDPO op zowel synthetische data als een grootschalige real-world advertentie-dataset (IPinYou).

• Real-World Validatie (IPinYou):
  • De dataset betrof het selecteren van advertentiecreaties ($X$) om klikken ($Y$) te maximaliseren, met slotzichtbaarheid ($Z$) als de mediator.
  • Beslissingsdivergentie: De arm die het standaard interventionele gemiddelde maximaliseerde, verschilde van de arm die de NDPO maximaliseerde. Het standaard gemiddelde bevoordeelde een creatie die veel voorkwam in top-slots (gemedieerd effect), terwijl de NDPO-optimale arm anders was.
  • Prestaties: TaS-NDPO bereikte een mediane stoptijd van 12.928 samples, wat ongeveer 50% efficiënter is dan de arm-level variant (25.856 samples), en presteerde aanzienlijk beter dan uniforme sampling en een baseline-first benadering. Alle methoden behielden een empirische foutmarge van nul bij $\delta=0.05$.
• Synthetische Experimenten:
  • Gap Scaling: De resultaten bevestigden de $1/\Delta^2$ schaling van de steekproefcomplexiteit zoals voorspeld door de ondergrens.
  • Mediator Sparsity: Het voordeel van cell-level forcing was het meest uitgesproken in settings met zeldzame mediator-uitkomst cellen (sparse regimes), waar arm-level forcing faalde om voldoende informatie te accumuleren.
  • Runtime: De computationele overhead van de cutting-set optimalisatie was matig (gemiddeld 22,5 seconden per run voor tot 100k samples), wat geen bottleneck vormde vergeleken met de winst in steekproefefficiëntie.

5. Betekenis en Claims

Het artikel claimt dat TaS-NDPO een theoretisch gefundeerde en empirisch efficiënte oplossing biedt voor het identificeren van behandelingen die directe causale effecten maximaliseren terwijl gemedieerde paden worden uitgesloten.

• Theoretische Betekenis: Het breidt het Track-and-Stop framework uit naar causale settings met geneste contrafeituele variabelen, en bewijst dat asymptotische optimaliteit haalbaar is, zelfs wanneer de doelstelling distributies over verschillende armen koppelt (via de baseline-mediator).
• Praktische Betekenis: Door directe effecten te isoleren, maakt de methode besluitvorming mogelijk die ongewenste mechanismen (bijv. clickbait, nadelige bijwerkingen of onethische positionering) vermijdt die anders door standaard gemiddelde-maximalisatie benaderingen zouden worden bevoordeeld.
• Bescheidenheid: De auteurs erkennen dat hun huidige framework zich richt op binaire uitkomsten en een specifieke causale graafstructuur (Mediator tussen Treatment en Outcome). Ze merken op dat het uitbreiden naar multi-categorie uitkomsten eenvoudig is, maar dat het generaliseren naar complexere pad-specifieke effecten in bredere causale structuren een richting is voor toekomstig werk. Ze verduidelijken ook dat de identificatie rust op de plausibiliteit van de onderliggende causale graaf (specifiek de afwezigheid van ongemeten confounding tussen $Z$ en $Y$), wat een standaard maar niet-testbare aanname is in causale inferentie.