Technische Samenvatting: Information-Directed Sampling voor Causal Bandits

Probleemformulering

Dit artikel behandelt het probleem van contextuele causale bandits in omgevingen die niet-manipuleerbare variabelen bevatten. In standaard multi-armed bandit problemen worden acties geselecteerd om beloningen te maximaliseren met onbekende distributies. In causale bandits corresponderen acties met interventies ($do(X=x)$) op een structureel causaal model (SCM), waarbij beloningen gekoppeld zijn via gedeelde causale mechanismen.

De specifieke uitdaging die hier wordt aangepakt, ontstaat wanneer bepaalde variabelen in de causale graaf de beloning beïnvloeden maar niet direct manipuleerbaar zijn (bijv. demografische kenmerken, genetische eigenschappen of macro-economische omstandigheden). Hoewel deze variabelen niet kunnen worden onderworpen aan een interventie, dienen ze als contextvariabelen die vóór de actieselectie worden waargenomen en als geobserveerde variabelen na de interventie. Het doel is om een haalbare interventie te selecteren uit een verzameling kandidaat-armen om de context-afhankelijke verwachte beloning, $\mu_x(c) = E[Y | do(x), C=c]$, te maximaliseren, terwijl efficiënt informatie wordt gedeeld over verschillende interventies.

De auteurs gaan uit van de volgende aannames:

1. Een bekende causale graaf $G$ zonder latente confounders.
2. Een verzameling niet-manipuleerbare variabelen $N \subseteq V \setminus \{Y\}$.
3. Contextvariabelen $C$ worden waargenomen vóór de actieselectie en zijn gesloten onder afstamming (d.w.z. $An(C)=C$).
4. De observationele distributie is onbekend, geparametriseerd door conditionele kanstabellen (CPT's).

Methodologie

1. Bayesiaanse Formulering en Parametrisatie

De auteurs hanteren een Bayesiaans kader waarbij de onbekende parameter $\theta$ bestaat uit de conditionele kanstabellen van de observationele distributie. Onder de aanname van geen latente confounders zijn de interventionele distributies identificeerbaar vanuit de observationele distributie via de getrunceerde factorisatieformule.

• Parameteronafhankelijkheid: De parametervector $\theta$ wordt ontleed in lokale vectoren $\theta_{ij}$ die overeenkomen met de CPT's van elke variabele gegeven de configuraties van de ouders.
• Posterior Updates: Uitgaande van conjunctieve Dirichlet-priors, wordt de posterior distributie over $\theta$ analytisch bijgewerkt op basis van geobserveerde data. Dit maakt het mogelijk dat samples verzameld onder één interventie de schattingen voor andere interventies bijwerken door de gedeelde CPT's te verfijnen.

2. Identificatie van Kandidaat-armen

Om niet-manipuleerbare variabelen te behandelen, maakt het artikel gebruik van het concept van Possibly Optimal Minimal Intervention Sets (POMISs), afgeleid van Lee en Bareinboim [2019].

• Projectie: De oorspronkelijke graaf wordt geprojecteerd op een graaf $H$ die alleen manipuleerbare variabelen bevat. Latente confounding veroorzaakt door niet-manipuleerbare variabelen wordt gerepresenteerd door bidirectionele randen in $H$.
• Armselectie: De verzameling kandidaat-armen $\mathcal{A}$ wordt gegenereerd door de POMISs van de geprojecteerde graaf $H$ te enumereren. Dit zorgt ervoor dat het algoritme alleen interventies overweegt die theoretisch optimaal zijn onder de manipuleerbaarheidsrestricties.

3. Voorgestelde Algoritmen

Het artikel stelt twee causale varianten van standaard bandit-algoritmen voor:

A. Causale Thompson Sampling (TS)

• Mechanisme: In elke ronde $t$, gegeven context $C_t=c_t$, selecteert het algoritme een parameter $\theta_t$ uit de context-geconditioneerde posterior $P(\theta | F_t, C_t=c_t)$. Vervolgens selecteert het de actie $a_t$ die de verwachte beloning maximaliseert onder de gesamplede parameter: $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$.
• Regret Analyse: De auteurs stellen een sublineaire Bayesiaanse regret-bound vast die afhankelijk is van de entropie van de optimale actie-mapping, $H(\Pi^*)$. De bound schaalt als $O(\sqrt{T |A| |C| \log |A|})$.

B. Causale Information-Directed Sampling (IDS)

• Mechanisme: IDS selecteert een distributie over acties die de informatieratio minimaliseert, gedefinieerd als de gekwadrateerde verwachte instantane regret gedeeld door de verwachte informatie-winst over de optimale actie.
  • Regret Term: $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$.
  • Informatiewinst Term: $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$.
• Monte Carlo Approximatie: Omdat de benodigde posterior verwachtingen voor het berekenen van de informatie-ratio analytisch onhandelbaar zijn in continue parameterruimtes, benadert het algoritme deze met behulp van $N$ Monte Carlo-samples uit de posterior.
• Foutcontrole: De auteurs leiden hoog-waarschijnlijkheid concentratiebounds (Lemma's 3 en 4) af voor de Monte Carlo-schattingen van zowel de verwachte regret als de informatie-winst. Deze bounds kwantificeren expliciet de extra fout die door de benadering wordt geïntroduceerd.

Belangrijkste Bijdragen

1. Bayesiaans Kader voor Niet-Manipuleerbare Variabelen: Het artikel formuleert contextuele causale bandits met niet-manipuleerbare variabelen door de observationele CPT's als de onbekende parameter te behandelen. Deze formulering maakt informatie-deling tussen interventies mogelijk via gedeelde causale mechanismen, zelfs wanneer sommige variabelen niet manipuleerbaar zijn.
2. Causale Thompson Sampling met Regret Guarantees: De auteurs stellen een causaal TS-algoritme voor en bewijzen een entropie-afhankelijke sublineaire Bayesiaanse regret-bound. Dit breidt de TS-garanties uit naar settings met structurele restricties en context.
3. Causale IDS met Approximatieanalyse: Het artikel ontwikkelt een causaal IDS-algoritme dat een balans vindt tussen regret-minimalisatie en informatieverwerving. Cruciaal is dat zij een regret-bound afleiden die expliciet de standaard informatie-theoretische term scheidt van de fout die wordt geïntroduceerd door de Monte Carlo-approximatie. Wanneer de informatie-ratio exact wordt berekend (oracle versie), wordt de standaard sublineaire IDS-rate hersteld.
4. Concentratiebounds voor Monte Carlo-schattingen: De auteurs bieden hoog-waarschijnlijkheid betrouwbaarheidsbounds voor de Monte Carlo-schattingen van de verwachte instantane regret en de contextuele informatie-winst. Deze resultaten kwantificeren de impact van de posterior-sampling fout op de prestatiegaranties van het algoritme.

Resultaten en Evaluatie

De voorgestelde methoden werden geëvalueerd op meerdere synthetische causale bandit-taken, inclusief gestructureerde voorbeelden en willekeurig gegenereerde causale grafen.

• Prestaties: De experimenten tonen aan dat de voorgestelde Causale TS en Causale IDS algoritmen zowel causale als niet-causale baselines overtreffen.
• Mechanisme: De superieure prestaties worden toegeschreven aan het vermogen van de algoritmen om effectiever informatie te exploiteren die gedeeld wordt tussen verschillende interventies via de gedeelde causale structuur, met name in de aanwezigheid van niet-manipuleerbare variabelen.

Betekenis

Het artikel claimt significantie door een principieel kader te bieden voor besluitvorming in causale omgevingen waar volledige controle over variabelen onmogelijk is. Door niet-manipuleerbare variabelen te integreren in het causale bandit-kader en algoritmen aan te bieden met rigoureuze regret-bounds (inclusief analyse van benaderingsfouten), overbrugt dit werk de kloof tussen theoretische causale inferentie en praktische sequentiële besluitvorming. De expliciete behandeling van Monte Carlo-approximatiefouten in IDS wordt benadrukt als een belangrijke theoretische vooruitgang, wat ervoor zorgt dat de voordelen van information-directed sampling behouden blijven, zelfs wanneer exacte berekening onhaalbaar is.