📊 statistics

Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment

Dit artikel introduceert het BA-UCB-algoritme voor causale banditproblemen met een onbekend causaal graf, dat door het combineren van observationele en experimentele data via backdoor-aanpassing de cumulatieve regret aanzienlijk verlaagt en de afhankelijkheid van het aantal interventies vermindert.

Oorspronkelijke auteurs: Yijia Zhao, Qing Zhou

Gepubliceerd 2026-04-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yijia Zhao, Qing Zhou

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een boer bent die probeert de beste oogst te krijgen. Je weet dat de opbrengst wordt beïnvloed door temperatuur, vocht en kunstmest. Maar je weet niet precies hoe deze factoren met elkaar samenhangen. Is het de temperatuur die de mest beïnvloedt? Of werkt de vochtigheid direct op de plant?

Je hebt twee manieren om dit uit te vinden:

Kijken (Observatie): Je kijkt naar je oude velden en noteert wat er gebeurde zonder ingrijpen. Dit is gratis en je hebt veel data, maar het kan verwarrend zijn omdat dingen tegelijkertijd gebeuren.
Proberen (Experiment): Je verandert bewust iets, bijvoorbeeld door de temperatuur te verhogen. Dit geeft je zekerheid, maar het is duur, tijdrovend en je kunt het niet elke dag doen.

Het probleem is: hoe vind je de beste combinatie van factoren om de oogst te maximaliseren, zonder je hele budget op te maken aan dure experimenten?

Dit is precies wat het artikel "Causal Bandit over Unknown Graphs" behandelt. De auteurs (Yijia Zhao en Qing Zhou) hebben een slimme nieuwe methode bedacht, genaamd BA-UCB. Laten we dit uitleggen met een paar creatieve metaforen.

1. Het Probleem: De "Zwarte Doos" vs. De "Landkaart"

Standaard methoden om dit soort problemen op te lossen (zoals de "UCB" algoritmen) behandelen de wereld als een zwarte doos. Ze proberen elke knop (temperatuur, vocht, mest) een beetje te drukken, kijken wat de beloning is, en hopen dat ze op de lange termijn de beste knop vinden.

Het nadeel: Als je 100 knoppen hebt, moet je ze allemaal vaak proberen. Dat kost enorm veel tijd en geld.
De oude oplossing: Sommige wetenschappers zeiden: "Als we maar de landkaart (het 'causale graf') hadden, zouden we weten welke knoppen belangrijk zijn!" Maar in het echt is die landkaart bijna nooit bekend.

2. De Oplossing: BA-UCB (De "Slimme Gids")

De auteurs zeggen: "We hoeven de volledige landkaart niet te kennen om slim te spelen." In plaats daarvan gebruiken ze een trucje uit de statistiek genaamd "Backdoor Adjustment".

Stel je voor dat je een detective bent die een moord wil oplossen.

De Observatie: Je ziet dat mensen die paraplu's dragen, vaak nat worden.
De Valstrik: Je denkt misschien: "Paraplu's maken mensen nat!" (Fout! Het regent, en daarom dragen ze paraplu's én worden ze nat).
De Backdoor Adjustment: Je kijkt naar de "achterdeur" (de oorzaak). Als je weet dat het regent, kun je de invloed van de paraplu corrigeren. Je zegt: "Oké, als het regent, is de paraplu niet de schuldige."

De BA-UCB methode doet dit automatisch:

Mixen: Ze nemen de gratis, oude data (observaties) en de dure, nieuwe data (experimenten) en mixen ze.
Zoeken naar de "Achterdeur": Ze proberen voor elke knop (bijv. temperatuur) te vinden welke andere factoren ze moeten "vasthouden" (controleren) om de echte oorzaak te zien. Ze doen dit niet door de hele wereld te analyseren, maar door slimme gokken te doen op basis van de data die ze al hebben.
De Slimme Gids: Zodra ze een goede "achterdeur" hebben gevonden, kunnen ze de oude data gebruiken om de nieuwe knoppen te testen. Het is alsof je met de oude data een voorspelling doet over wat er zou gebeuren als je de temperatuur verhoogt, zonder het daadwerkelijk te hoeven doen.

3. Waarom is dit zo geweldig? (De "Kostprijs" van Regret)

In de wereld van bandieten (wiskundige spelletjes) heet het verlies van een kans op een betere beloning "Regret" (spijt).

De oude manier: Als je 100 knoppen hebt, is je "spijt" (regret) evenredig met de wortel van 100. Dat is veel.
De BA-UCB manier: Omdat ze de gratis observatie-data gebruiken om de dure experimenten te "versterken", hangt hun spijt niet meer af van het aantal knoppen.
- Metafoor: Stel je voor dat je een leraar bent met 100 leerlingen. De oude methode moet elk kind 10 keer testen om te weten wie slim is. De BA-UCB methode kijkt naar de huiswerkresultaten (gratis data) en weet al snel wie de beste is, zodat ze alleen de lastige kinderen hoeven te testen.

4. Wat als er "Onzichtbare Daders" zijn? (Latente Confounders)

Soms zijn er factoren die je niet kunt zien, zoals "geluk" of "verborgen ziektes" die zowel de temperatuur als de oogst beïnvloeden. Dit zijn latente confounders.

De auteurs hebben hun methode ook hierop aangepast. Als ze merken dat ze geen goede "achterdeur" kunnen vinden (omdat er een onzichtbare dader is), stoppen ze niet. Ze zeggen: "Oké, deze knop is lastig, dan gaan we hem puur testen met dure experimenten."
Ze zijn dus robuust: ze werken goed als de wereld simpel is, en ze werken nog steeds goed (hoewel iets minder efficiënt) als de wereld complex en ondoorzichtig is.

Samenvatting in één zin

De auteurs hebben een slimme algoritme bedacht dat gratis, oude data gebruikt om duurzame, nieuwe experimenten te sturen, zodat we de beste beslissingen kunnen nemen zonder de hele wereld eerst volledig te hoeven begrijpen of te hoeven testen.

De kernboodschap: Je hoeft niet de hele landkaart te hebben om de snelste route te vinden; als je slim kijkt naar de sporen die je al hebt (observaties), kun je de dure tocht (experimenten) veel efficiënter maken.

Probleemstelling

Het Causal Bandit-probleem richt zich op het identificeren van een interventie die de verwachte beloning maximaliseert in een causaal systeem, gemodelleerd door een gerichte acyclische graaf (DAG). In tegenstelling tot het klassieke Multi-Armed Bandit (MAB) probleem, waarbij acties als onafhankelijke "black boxes" worden behandeld, benut het causale bandit-probleem de onderliggende causale structuur om efficiënter te leren.

De belangrijkste uitdaging waar deze paper op inspeelt, is dat de onderliggende causale graaf in de praktijk vaak onbekend is. Bestaande methoden vereisen meestal volledige kennis van de DAG of maken restrictieve structurele aannames (bijv. dat de optimale interventie altijd een ouder van de reward-variabele is). Wanneer de graaf onbekend is en de variabelen continu zijn (Gaussisch), is het niet vanzelfsprekend dat de optimale interventie een directe ouder van de reward is. Bestaande benaderingen voor onbekende grafen zijn vaak computationally intensief (zoals Bayesiaanse methoden) of missen theoretische garanties op de cumulatieve regret.

Het doel is dus: een algoritme ontwikkelen dat de optimale interventie kan vinden in een Gaussisch DAG-systeem zonder voorafgaande kennis van de graaf, gebruikmakend van zowel observationele data (historisch, goedkoop) als experimentele data (sequentiële interventies, duur), zelfs bij aanwezigheid van latente confounders.

Methodologie: BA-UCB

De auteurs stellen het Backdoor Adjustment Upper Confidence Bound (BA-UCB) algoritme voor. De kern van de methode is het combineren van observationele en experimentele data om de causale effecten te schatten en de onzekerheid te verminderen, zonder de volledige graaf te hoeven reconstrueren.

1. Gebruik van Backdoor-Adjustment:
In plaats van de volledige DAG te leren, identificeert het algoritme voor elke mogelijke interventie (arm) $X_i$ een backdoor-adjustment set $S$ . Als een set $S$ voldoet aan het backdoor-criterium ten opzichte van $(X_i, Y)$ , dan kan het causale effect $\gamma_i$ worden geschat via regressie:
$\gamma_i = \beta_i(Y \sim X_i + X_S)$
Dit maakt het mogelijk om causale effecten te schatten met observationele data alleen, mits een geldige set $S$ bekend is.

2. Data-integratie en Schatting:
Het algoritme combineert twee bronnen van data:

Experimentele data: Data verzameld onder interventie $do(X_i)$ .
Observationele data: Data verzameld zonder interventie.
Het algoritme schat de regressie-omgeving (regression neighborhood) $M_i$ van elke variabele $X_i$ op basis van observationele data. Vervolgens worden kandidaat-adjustment sets geselecteerd uit de subsets van $M_i$ .

3. Identificatie van Geldige Sets:
Om te bepalen of een set $S$ een geldige backdoor-set is, vergelijkt het algoritme de schatting van het causale effect uit observationele data ( $\hat{\mu}_{i,obs}$ ) met die uit experimentele data ( $\hat{\mu}_{i,int}$ ).

Als $S$ een geldige set is, zouden deze schattingen gelijk moeten zijn (het verschil is 0).
Het algoritme construeert betrouwbaarheidsintervallen voor het verschil $\hat{\mu}_{i,obs} - \hat{\mu}_{i,int}$ . Sets waarvan het interval 0 bevat, worden beschouwd als kandidaat-geldige sets.

4. Gewogen UCB:
Voor elke arm wordt een Upper Confidence Bound (UCB) geconstrueerd door een gewogen gemiddelde te nemen van de schattingen uit observationele en experimentele data. Dit gewogen gemiddelde vermindert de variantie van de schatter, vooral wanneer er veel observationele data beschikbaar is. Het algoritme kiest de arm met de hoogste UCB-waarde voor de volgende ronde.

5. Uitbreiding naar Latente Confounders:
Het algoritme wordt uitgebreid naar scenario's met latente confounders, gemodelleerd door een Acyclic Directed Mixed Graph (ADMG). In dit geval kunnen backdoor-sets niet altijd bestaan (bijv. bij een bidirectionele kant). Het algoritme past zich aan door:

Alleen sets te overwegen waarvan het betrouwbaarheidsinterval 0 bevat.
Als geen enkele geldige set wordt gevonden, terug te vallen op puur experimentele schattingen (unbiased interventional estimation) om bias te voorkomen.

Belangrijkste Bijdragen

Algoritme zonder Graafkennis: BA-UCB vereist geen vooraf bekende DAG en maakt geen restrictieve aannames over de structuur (zoals dat de optimale arm een ouder moet zijn). Het leert de noodzakelijke adjustment sets dynamisch tijdens het bandit-proces.
Theoretische Garanties: De auteurs bewijzen finite-time upper bounds voor de cumulatieve regret.
- Zonder latente confounders: De regret is begrensd door $O(\sqrt{T \log T / (m+n)})$ , waarbij $T$ het aantal rondes is, en $m, n$ respectievelijk het aantal experimentele en observationele samples per ronde.
- Voordeel: Deze bound is onafhankelijk van het aantal armen $K$ (in tegenstelling tot de standaard MAB bound van $O(\sqrt{KT \log T})$ ), mits er voldoende observationele data is. Dit betekent dat de schaalbaarheid met het aantal armen drastisch verbetert.
- Met latente confounders: De regret wordt opgesplitst in een term voor identificeerbare armen (die profiteren van observationele data) en niet-identificeerbare armen (die alleen op experimentele data vertrouwen).
Efficiëntie: Het algoritme is computationally veel efficiënter dan Bayesiaanse alternatieven (zoals BBB-UCB), die posterior probabilities over alle mogelijke parent sets moeten bijwerken. BA-UCB heeft een lagere complexiteit en schaleert beter met de grootte van de graaf.

Resultaten

De auteurs hebben uitgebreide simulaties uitgevoerd op Gaussische DAG's en ADMG's:

Vergelijking met Standaard UCB en CN-UCB: BA-UCB presteert significant beter dan de standaard UCB en de Central Node (CN)-UCB algoritmen.
- CN-UCB faalt vaak wanneer de optimale interventie geen ouder van de reward is (wat vaak het geval is in Gaussische modellen).
- BA-UCB benut de informatie uit observationele data om sneller te convergeren, zelfs bij grote aantallen armen.
Vergelijking met BBB-UCB: Hoewel BBB-UCB goede resultaten levert, is het computationally onhaalbaar voor grotere grafen ( $p \ge 20$ ) vanwege de exponentiële complexiteit. BA-UCB behaalt vergelijkbare of betere resultaten met een fractie van de rekentijd.
Invloed van Observationele Data: Simulaties tonen aan dat het toevoegen van observationele data (zelfs zonder initiële dataset, maar tijdens het proces) de cumulatieve regret aanzienlijk verlaagt. De prestaties verbeteren naarmate de verhouding tussen observationele en experimentele data toeneemt.
Robuustheid: In aanwezigheid van latente confounders behoudt het aangepaste algoritme zijn robuustheid door terug te vallen op experimentele data wanneer geen geldige adjustment set kan worden geïdentificeerd.

Betekenis en Conclusie

Deze paper biedt een doorbraak in het veld van causale bandits door een praktische en theoretisch onderbouwde oplossing te bieden voor het probleem van onbekende causale grafen.

Praktische Toepasbaarheid: In veel real-world scenario's (zoals gezondheidszorg of marketing) is het duur om experimenten uit te voeren, maar is er vaak een overvloed aan observationele data. BA-UCB laat zien hoe deze goedkope data kan worden gebruikt om de kosten van dure experimenten te verlagen en sneller de optimale strategie te vinden.
Schalbaarheid: De vermindering van de afhankelijkheid van het aantal armen $K$ in de regret-bound is een fundamenteel voordeel voor complexe systemen met veel mogelijke interventies.
Robuustheid: De methode is niet alleen effectief voor zuivere DAG's, maar ook voor realistischere scenario's met latente confounders.

Kortom, BA-UCB combineert de kracht van causale inferentie (backdoor adjustment) met de efficiëntie van bandit-algoritmen, waardoor het een krachtig instrument wordt voor sequentiële besluitvorming in onzekere en complexe causale omgevingen.