Resumen Técnico: Muestreo Dirigido por Información para Bandidos Causales

Formulación del Problema

Este artículo aborda el problema de los bandidos causales contextuales en entornos que contienen variables no manipulables. En los problemas estándar de bandidos multi-brazos, las acciones se seleccionan para maximizar las recompensas con distribuciones desconocidas. En los bandidos causales, las acciones corresponden a intervenciones ($do(X=x)$) sobre un modelo causal estructural (SCM), donde las recompensas están acopladas a través de mecanismos causales compartidos.

El desafío específico abordado aquí surge cuando ciertas variables en el grafo causal influyen en la recompensa pero no pueden ser manipuladas directamente (por ejemplo, atributos demográficos, características genéticas o condiciones macroeconómicas). Aunque no se puede intervenir sobre estas variables, sirven como variables de contexto observadas antes de la selección de la acción y como variables observadas después de la intervención. El objetivo es seleccionar una intervención factible de un conjunto de brazos candidatos para maximizar la recompensa esperada dependiente del contexto, $\mu_x(c) = E[Y | do(x), C=c]$, mientras se comparte información de manera eficiente entre diferentes intervenciones.

Los autores asumen:

1. Un grafo causal $G$ conocido sin confundidores latentes.
2. Un conjunto de variables no manipulables $N \subseteq V \setminus \{Y\}$.
3. Las variables de contexto $C$ se observan antes de la selección de la acción y son cerradas bajo ascendencia (es decir, $An(C)=C$).
4. La distribución observacional es desconocida, parametrizada por tablas de probabilidad condicional (CPT).

Metodología

1. Formulación Bayesiana y Parametrización

Los autores adoptan un marco bayesiano donde el parámetro desconocido $\theta$ consiste en las tablas de probabilidad condicional de la distribución observacional. Bajo el supuesto de ausencia de confundidores latentes, las distribuciones intervencionales son identificables a partir de la distribución observacional mediante la fórmula de factorización truncada.

• Independencia de Parámetros: El vector de parámetros $\theta$ se descompone en vectores locales $\theta_{ij}$ correspondientes a las CPT de cada configuración de los padres.
• Actualizaciones de la Posterior: Asumiendo prioris de Dirichlet conjugados, la distribución posterior sobre $\theta$ se actualiza analíticamente basándose en los datos observados. Esto permite que las muestras recolectadas bajo una intervención actualicen las estimaciones para otras intervenciones mediante el refinamiento de las CPT compartidas.

2. Identificación de Brazos Candidatos

Para manejar las variables no manipulables, el artículo utiliza el concepto de Conjuntos de Intervención Mínima Posiblemente Óptimos (POMISs) derivados de Lee y Bareinboim [2019].

• Proyección: El grafo original se proyecta sobre un grafo $H$ que contiene solo variables manipulables. El confundimiento latente inducido por las variables no manipulables se representa mediante aristas bidireccionales en $H$.
• Selección de Brazos: El conjunto de brazos candidatos $\mathcal{A}$ se genera enumerando los POMISs del grafo proyectado $H$. Esto asegura que el algoritmo solo considere intervenciones que son teóricamente óptimas bajo las restricciones de manipulabilidad.

3. Algoritmos Propuestos

El artículo propone dos variantes causales de algoritmos de bandidos estándar:

A. Thompson Sampling Causal (TS)

• Mecanismo: En cada ronda $t$, dado el contexto $C_t=c_t$, el algoritmo muestrea un parámetro $\theta_t$ de la posterior condicionada al contexto $P(\theta | F_t, C_t=c_t)$. Luego selecciona la acción $a_t$ que maximiza la recompensa esperada bajo el parámetro muestreado: $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$.
• Análisis de Regret: Los autores establecen un límite de regret bayesiano sublineal dependiente de la entropía del mapeo de la acción óptima, $H(\Pi^*)$. El límite escala como $O(\sqrt{T |A| |C| \log |A|})$.

B. Muestreo Dirigido por Información Causal (IDS)

• Mecanismo: IDS selecciona una distribución sobre las acciones que minimiza la relación de información, definida como el cuadrado del regret instantáneo esperado dividido por la ganancia de información esperada sobre la acción óptima.
  • Término de Regret: $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$.
  • Término de Ganancia de Información: $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$.
• Aproximación de Monte Carlo: Dado que las expectativas posteriores requeridas para calcular la relación de información son analíticamente intratables en espacios de parámetros continuos, el algoritmo las aproxima utilizando $N$ muestras de Monte Carlo de la posterior.
• Control de Error: Los autores derivan límites de concentración de alta probabilidad (Lemmas 3 y 4) para las estimaciones de Monte Carlo tanto del regret esperado como de la ganancia de información. Estos límites cuantifican explícitamente el error adicional introducido por la aproximación.

Contribuciones Clave

1. Marco Bayesiano para Variables No Manipulables: El artículo formula bandidos causales contextuales con variables no manipulables tratando las CPT observacionales como el parámetro desconocido. Esta formulación permite el intercambio de información entre intervenciones a través de las CPT compartidas, incluso cuando algunas variables no pueden ser intervenidas.
2. Thompson Sampling Causal con Garantías de Regret: Los autores proponen un algoritmo de TS causal y prueban un límite de regret bayesiano sublineal dependiente de la entropía. Esto extiende las garantías de TS a entornos con restricciones estructurales y contexto.
3. IDS Causal con Análisis de Aproximación: El artículo desarrolla un algoritmo de IDS causal que equilibra la minimización del regret y la adquisición de información. Crucialmente, deriva un límite de regret que separa explícitamente el término de información estándar del error introducido por la aproximación de Monte Carlo. Cuando la relación de información se calcula exactamente (versión oracle), se recupera la tasa estándar de IDS sublineal.
4. Límites de Concentración para Estimaciones de Monte Carlo: Los autores proporcionan límites de confianza de alta probabilidad para las estimaciones de Monte Carlo del regret instantáneo esperado y la ganancia de información contextual. Estos resultados cuantifican el impacto del error de muestreo de la posterior en las garantías de rendimiento del algoritmo.

Resultados y Evaluación

Los métodos propuestos fueron evaluados en múltiples tareas de bandidos causales sintéticos, incluyendo ejemplos estructurados y grafos causales generados aleatoriamente.

• Desempeño: Los experimentos demuestran que los algoritmos de Causal TS y Causal IDS propuestos superan tanto a las líneas base causales como no causales.
• Mecanismo: El desempeño superior se atribuye a la capacidad de los algoritmos para explotar más eficazmente la información compartida a través de diferentes intervenciones mediante la estructura causal compartida, particularmente en presencia de variables no manipulables.

Significado

El artículo afirma su relevancia al proporcionar un marco principista para la toma de decisiones en entornos causales donde el control total sobre las variables es imposible. Al integrar las variables no manipulables en el marco de los bandidos causales y ofrecer algoritmos con límites de regret rigurosos (incluyendo el análisis de errores de aproximación), el trabajo cierra la brecha entre la inferencia causal teórica y la toma de decisiones secuenciales práctica. El manejo explícito de los errores de aproximación de Monte Carlo en IDS se destaca como un avance teórico clave, asegurando que los beneficios del muestreo dirigido por información se preserven incluso cuando el cálculo exacto es infactible.