Resumo Técnico: Amostragem Direcionada por Informação para Bandidos Causais

Formulação do Problema

Este artigo aborda o problema de bandidos causais contextuais em ambientes que contêm variáveis não manipuláveis. Em problemas padrão de multi-braços (multi-armed bandits), as ações são selecionadas para maximizar recompensas com distribuições desconhecidas. Em bandidos causais, as ações correspondem a intervenções ($do(X=x)$) em um modelo causal estrutural (SCM), onde as recompensas são acopladas através de mecanismos causais compartilhados.

O desafio específico tratado aqui surge quando certas variáveis no grafo causal influenciam a recompensa, mas não podem ser diretamente manipuladas (ex: atributos demográficos, características genéticas ou condições macroeconômicas). Embora essas variáveis não possam sofrer intervenção, elas servem como variáveis de contexto observadas antes da seleção da ação e como variáveis observadas após a intervenção. O objetivo é selecionar uma intervenção viável de um conjunto de braços candidatos para maximizar a recompensa esperada dependente do contexto, $\mu_x(c) = E[Y | do(x), C=c]$, enquanto compartilha informação eficientemente entre diferentes intervenções.

Os autores assumem:

1. Um grafo causal $G$ conhecido sem confundidores latentes.
2. Um conjunto de variáveis não manipuláveis $N \subseteq V \setminus \{Y\}$.
3. Variáveis de contexto $C$ são observadas antes da seleção da ação e são fechadas sob ancestralidade (ou seja, $An(C)=C$).
4. A distribuição observacional é desconhecida, parametrizada por tabelas de probabilidade condicional (CPTs).

Metodologia

1. Formulação Bayesiana e Parametrização

Os autores adotam uma estrutura Bayesiana onde o parâmetro desconhecido $\theta$ consiste nas tabelas de probabilidade condicional das distribuições observacionais. Sob a suposição de ausência de confundidores latentes, as distribuições intervencionais são identificáveis a partir da distribuição observacional via a fórmula de fatoração truncada.

• Independência de Parâmetros: O vetor de parâmetros $\theta$ é decomposto em vetores locais $\theta_{ij}$ correspondentes às CPTs de cada variável dado as configurações de seus pais.
• Atualizações de Posterior: Assumindo priors de Dirichlet conjugados, a distribuição posterior sobre $\theta$ é atualizada analiticamente com base nos dados observados. Isso permite que amostras coletadas sob uma intervenção atualizem as estimativas para outras intervenções ao refinar as CPTs compartilhadas.

2. Identificação de Braços Candidatos

Para lidar com variáveis não manipuláveis, o artigo utiliza o conceito de Conjuntos de Intervenção Mínima Possivelmente Ótimos (POMISs) derivados de Lee e Bareinboim [2019].

• Projeção: O grafo original é projetado em um grafo $H$ contendo apenas variáveis manipuláveis. O confundimento latente induzido por variáveis não manipuláveis é representado por arestas bidirecionais em $H$.
• Seleção de Braços: O conjunto de braços candidatos $\mathcal{A}$ é gerado pela enumeração dos POMISs do grafo projetado $H$. Isso garante que o algoritmo considere apenas intervenções que são teoricamente ótimas sob as restrições de manipulabilidade.

3. Algoritmos Propostos

A. Thompson Sampling (TS) Causal

• Mecanismo: Em cada rodada $t$, dado o contexto $C_t=c_t$, o algoritmo amostra um parâmetro $\theta_t$ da posterior condicionada ao contexto $P(\theta | F_t, C_t=c_t)$. Ele então seleciona a ação $a_t$ que maximiza a recompensa esperada sob o parâmetro amostrado: $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$.
• Análise de Regret: Os autores estabelecem um limite de regret bayesiano sublinear dependente da entropia do mapeamento da ação ótima, $H(\Pi^*)$. O limite escala como $O(\sqrt{T |A| |C| \log |A|})$.

B. Amostragem Direcionada por Informação (IDS) Causal

• Mecanismo: O IDS seleciona uma distribuição sobre as ações que minimiza a razão de informação, definida como o quadrado do regret instantâneo esperado dividido pelo ganho de informação esperado sobre a ação ótima.
  • Termo de Regret: $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$.
  • Termo de Ganho de Informação: $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$.
• Aproximação de Monte Carlo: Como as expectativas de posterior necessárias para calcular a razão de informação são analiticamente intratáveis em espaços de parâmetros contínuos, o algoritmo as aproxima usando $N$ amostras de Monte Carlo da posterior.
• Controle de Erro: Os autores derivam limites de concentração de alta probabilidade (Lemmas 3 e 4) para as estimativas de Monte Carlo tanto do regret esperado quanto do ganho de informação contextual. Esses limites quantificam explicitamente o erro adicional introduzido pela aproximação.

Principais Contribuições

1. Estrutura Bayesiana para Variáveis Não Manipuláveis: O artigo formula bandidos causais contextuais com variáveis não manipuláveis tratando as CPTs observacionais como o parâmetro desconhecido. Esta formulação permite o compartilhamento de informação entre intervenções através de mecanismos causais compartilhados, mesmo quando algumas variáveis não podem ser intervencionadas.
2. Thompson Sampling Causal com Garantias de Regret: Os autores propõem um algoritmo TS causal e provam um limite de regret bayesiano sublinear dependente da entropia. Isso estende as garantias do TS para configurações com restrições estruturais e contexto.
3. IDS Causal com Análise de Aproximação: O artigo desenvolve um algoritmo IDS causal que equilibra a minimização de regret e a aquisição de informação. Crucialmente, deriva um limite de regret que separa explicitamente o termo informacional padrão do erro introduzido pela aproximação de Monte Carlo. Quando a razão de informação é calculada exatamente (versão oracle), o padrão de IDS sublinear é recuperado.
4. Limites de Concentração para Estimativas de Monte Carlo: Os autores fornecem limites de confiança de alta probabilidade para as estimativas de Monte Carlo do regret instantâneo esperado e do ganho de informação contextual. Esses resultados quantificam o impacto do erro de amostragem da posterior no desempenho das garantias do algoritmo.

Resultados e Avaliação

Os métodos propostos foram avaliados em múltiplas tarefas de bandidos causais sintéticos, incluindo exemplos estruturados e grafos causais gerados aleatoriamente.

• Desempenho: Os experimentos demonstram que os algoritmos Causal TS e Causal IDS propostos superam tanto as bases causais quanto as não causais.
• Mecanismo: O desempenho superior é atribuído à capacidade dos algoritmos de explorar mais efetivamente a informação compartilhada entre diferentes intervenções via estrutura causal compartilhada, particularmente na presença de variáveis não manipuláveis.

Significância

O artigo afirma sua significância ao fornecer um framework principiado para a tomada de decisão em ambientes causais onde o controle total sobre as variáveis é impossível. Ao integrar variáveis não manipuláveis no framework de bandidos causais e oferecer algoritmos com limites de regret rigorosos (incluindo análise de erros de aproximação), o trabalho preenche a lacuna entre a inferência causal teórica e a tomada de decisão sequencial prática. O tratamento explícito dos erros de aproximação de Monte Carlo no IDS é destacado como um avanço teórico fundamental, garantindo que os benefícios da amostragem direcionada por informação sejam preservados mesmo quando o cálculo exato é inviável.