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

1. Il Problema: Banditi Causali su Grafi Sconosciuti

Il problema dei banditi causali (Causal Bandits) mira a identificare, attraverso sperimentazione sequenziale, un'intervento che massimizzi la ricompensa attesa in un sistema causale modellato da un grafo aciclico diretto (DAG).

• Limitazioni degli approcci esistenti: La maggior parte degli algoritmi attuali assume che la struttura del grafo causale sia nota o imponga restrizioni strutturali severe. Tuttavia, in scenari reali (es. sanità, economia), il DAG sottostante è raramente noto.
• Sfide specifiche:
  • In domini continui (es. modelli Gaussiani), l'intervento ottimale non è necessariamente un genitore della variabile di ricompensa, rendendo difficile la riduzione dello spazio delle azioni.
  • L'uso esclusivo di dati sperimentali è costoso e inefficiente.
  • La presenza di confonditori latenti (variabili non osservate) complica l'identificazione degli effetti causali.

2. Metodologia: L'algoritmo BA-UCB

Gli autori propongono l'algoritmo Backdoor-Adjustment Upper Confidence Bound (BA-UCB), che non richiede la conoscenza a priori del grafo causale.

A. Modelli e Assunzioni

• Caso Base: Variabili osservate (inclusa la ricompensa $Y$) modellate da un DAG Gaussiano lineare (SEM).
• Estensione: Presenza di confonditori latenti, modellati tramite un Grafo Misto Diretto Aciclico (ADMG).
• Dati: L'algoritmo integra due fonti di dati:
  1. Dati Osservazionali: Storici, a basso costo, raccolti senza interventi.
  2. Dati Sperimentali: Raccolti sequenzialmente durante il processo di bandit (costosi).

B. Meccanismo Principale

L'idea centrale è sfruttare il criterio di backdoor per identificare set di aggiustamento validi senza conoscere l'intero DAG.

1. Identificazione dei Set di Aggiustamento:
   • Per ogni braccio (intervento su $X_i$), l'algoritmo stima il "vicinato di regressione" di $X_i$ usando i dati osservazionali.
   • Genera candidati set di aggiustamento $S$ (sottoinsiemi del vicinato).
   • Confronta la stima dell'effetto causale ottenuta dai dati osservazionali (tramite aggiustamento backdoor) con quella ottenuta dai dati sperimentali (intervento diretto).
   • Un set $S$ è considerato candidato valido se l'intervallo di confidenza della differenza tra le due stime include lo zero.
2. Stima Pesata (Weighted Average):
   • Invece di fondere i dati in una singola regressione (che può essere distorta se il set di aggiustamento è errato), BA-UCB calcola stime separate per dati osservazionali e sperimentali.
   • Combina queste stime in una media pesata per costruire i Limiti di Confidenza Superiore (UCB). Questo approccio è più robusto agli errori di selezione del set di aggiustamento.
3. Selezione del Braccio:
   • Si sceglie il braccio che massimizza l'UCB pesato, bilanciando esplorazione e sfruttamento.

C. Gestione dei Confonditori Latenti (ADMG)

In presenza di confonditori latenti, un set di aggiustamento valido potrebbe non esistere per alcuni bracci.

• L'algoritmo modifica la selezione: se nessun set di aggiustamento candidato ha un intervallo di confidenza che include lo zero, l'algoritmo ricade sulla sola stima sperimentale (non distorta ma con maggiore varianza) per quel braccio specifico.

3. Contributi Chiave

1. Indipendenza dal Grafo: L'algoritmo funziona senza conoscere la struttura del DAG o l'ADMG sottostante, identificando dinamicamente i set di aggiustamento necessari.
2. Integrazione Dati Osservazionali/Sperimentali: Propone un framework teorico e pratico per combinare dati a basso costo (osservazionali) e dati ad alto costo (sperimentali) all'interno di un processo decisionale sequenziale.
3. Nuovi Limiti di Regret:
   • Dimostrano che il regret cumulativo è limitato da $O(\sqrt{T \log T / (m+n)})$, dove $T$ è il numero di round, $m$ i dati sperimentali e $n$ quelli osservazionali per round.
   • Vantaggio Critico: A differenza dei metodi MAB standard il cui regret scala con $\sqrt{K}$ (dove $K$ è il numero di bracci), il regret di BA-UCB non dipende da $K$ (o dipende molto meno), grazie alla condivisione dell'informazione attraverso i dati osservazionali che informano simultaneamente tutti i bracci.
4. Estensione ai Confonditori Latenti: Generalizzazione della metodologia ai modelli ADMG, mantenendo garanzie teoriche anche quando l'identificabilità causale non è garantita per tutti i bracci.

4. Risultati Sperimentali

Gli autori hanno condotto estese simulazioni su DAG casuali con variabili da 10 a 50.

• Confronto: BA-UCB è stato confrontato con UCB standard, CN-UCB (Central Node UCB) e BBB-UCB (Bayesian Backdoor Bandit).
• Performance:
  • Regret: BA-UCB ottiene un regret cumulativo significativamente inferiore rispetto a UCB e CN-UCB.
  • Robustezza: A differenza di CN-UCB, che fallisce se l'azione ottimale non è un genitore della ricompensa, BA-UCB performa bene in tutti gli scenari.
  • Efficienza Computazionale: BA-UCB è molto più scalabile di BBB-UCB, che diventa intrattabile per grafi di dimensioni moderate ($p \ge 20$) a causa della complessità esponenziale nel calcolo delle probabilità a posteriori.
  • Identificazione: Le simulazioni mostrano che la capacità di identificare correttamente i set di aggiustamento aumenta rapidamente con il tempo, portando a una convergenza delle stime verso i valori veri.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo avanti significativo nell'apprendimento per rinforzo causale:

• Riduzione dei Costi: Dimostra che l'uso strategico di dati osservazionali storici può ridurre drasticamente la necessità di costose sperimentazioni attive.
• Scalabilità: Rimuove la dipendenza dal numero di azioni ($K$) nel limite superiore del regret, rendendo l'approccio applicabile a problemi con spazi di azione molto grandi.
• Praticità: Offre una soluzione robusta per scenari reali dove la conoscenza del grafo causale è incompleta e sono presenti variabili nascoste, superando le limitazioni dei metodi basati su modelli puramente sperimentali o su assunzioni strutturali rigide.

In sintesi, BA-UCB fornisce un metodo efficiente, teoricamente fondato e computazionalmente scalabile per l'ottimizzazione delle decisioni in sistemi causali complessi e parzialmente osservabili.