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

Resumo Técnico: Causal Bandit sobre Grafos Desconhecidos

1. Problema e Motivação

O problema do Bandit Causal (CB) visa identificar, através de experimentação sequencial, uma intervenção que maximize a recompensa esperada em um sistema causal modelado por um Grafo Acíclico Direcionado (DAG).

• Desafio Principal: A maioria dos métodos existentes assume que a estrutura do grafo causal é conhecida ou impõe restrições estruturais severas. Na prática, o DAG subjacente é raramente conhecido.
• Limitações de Abordagens Anteriores:
  • Métodos que tentam aprender o grafo completo antes de tomar decisões são computacionalmente caros e podem ser desnecessários.
  • Abordagens que reduzem o espaço de ação apenas para os pais da variável de recompensa falham em domínios contínuos (como modelos Gaussianos), onde a intervenção ótima nem sempre é um pai direto da recompensa.
  • Métodos Bayesianos que inferem sobre todos os conjuntos de pais possíveis são inviáveis para conjuntos de ação moderados devido à complexidade computacional exponencial.
• Objetivo: Desenvolver um algoritmo que identifique a intervenção ótima sem conhecimento prévio do DAG, integrando eficientemente dados observacionais (históricos, baratos) e dados experimentais (coletados durante o bandit, caros) para reduzir o arrependimento cumulativo (regret).

2. Metodologia: O Algoritmo BA-UCB

Os autores propõem o algoritmo Backdoor Adjustment Upper Confidence Bound (BA-UCB). A abordagem central não é recuperar o DAG completo, mas identificar conjuntos de ajuste de porta traseira (backdoor adjustment sets) candidatos para cada braço (intervenção) durante o processo de decisão.

Principais Componentes:

• Modelo: Assume-se inicialmente um modelo de DAG Gaussiano linear (SEM) sem confundidores latentes. Posteriormente estendido para Grafos Mistos Direcionados Acíclicos (ADMG) com confundidores latentes.
• Identificação de Conjuntos de Ajuste:
  • Para cada variável de intervenção $X_i$, o algoritmo utiliza dados observacionais para estimar o "vizinhança de regressão" (parentes e filhos potenciais).
  • Ele compara duas estimativas da recompensa esperada $\mu_i$:
    1. Estimativa Intervencional ($\hat{\mu}_{i, int}$): Baseada apenas nos dados experimentais coletados até o momento.
    2. Estimativa Observacional ($\hat{\mu}_{i, obs}$): Baseada em regressão linear com um conjunto candidato de covariáveis $S$ (ajuste de porta traseira).
  • Um conjunto $S$ é considerado um candidato válido se a diferença entre as estimativas observacional e intervencional for estatisticamente próxima de zero (verificada via intervalos de confiança).
• Combinação de Dados (Weighted Average):
  • Diferente de uma regressão única sobre dados combinados (que pode ser enviesada se o conjunto de ajuste for inválido), o BA-UCB calcula uma média ponderada das estimativas e variâncias dos dados observacionais e experimentais.
  • Isso permite que a grande quantidade de dados observacionais reduza a variância da estimativa, mesmo que a estrutura exata do grafo não seja totalmente conhecida.
• Seleção de Braço: O algoritmo seleciona o braço que maximiza o limite superior de confiança (UCB) construído a partir da estimativa combinada e sua variância ponderada.

Extensão para Confundidores Latentes (ADMG):

• Quando confundidores latentes existem, conjuntos de ajuste válidos podem não existir para todos os braços.
• O algoritmo é modificado para verificar se o intervalo de confiança do ajuste contém zero. Se nenhum conjunto válido for encontrado, o algoritmo recua automaticamente para usar apenas a estimativa intervencional (não enviesada), garantindo robustez.

3. Contribuições Chave

1. Algoritmo BA-UCB: Um novo método para bandits causais que não requer conhecimento prévio do DAG nem restrições estruturais rígidas.
2. Integração de Dados: Uma estratégia inovadora para combinar dados observacionais e experimentais via ajuste de porta traseira, utilizando médias ponderadas para manter a robustez contra seleção incorreta de conjuntos de ajuste.
3. Análise Teórica de Regret:
   • Estabelecimento de limites superiores de regret de tempo finito.
   • Sem confundidores latentes: O regret é limitado por $O(\sqrt{T \log T / (m + n)})$, onde $m$ e $n$ são amostras experimentais e observacionais por rodada. Isso remove a dependência do número de braços $K$ (comparado a $O(\sqrt{KT \log T})$ no MAB padrão).
   • Com confundidores latentes: O regret é limitado por $O(\sqrt{T \log T / (m + n)}) + O(\sqrt{K_1 T \log T / m})$, onde $K_1$ é o número de braços sem conjunto de ajuste válido. A dependência de $K$ é drasticamente reduzida.
4. Eficiência Computacional: O método evita a inferência Bayesiana sobre todos os grafos possíveis, sendo escalável para grafos maiores do que métodos existentes (como BBB-UCB).

4. Resultados Experimentais

Os autores realizaram extensas simulações com DAGs Gaussianos de diferentes tamanhos ($p = 10, 20, 30, 50$) e com confundidores latentes.

• Comparação com UCB Padrão e CN-UCB:
  • O BA-UCB alcançou um regret cumulativo significativamente menor do que o UCB padrão e o algoritmo CN-UCB (que tenta identificar apenas os pais da recompensa).
  • O desempenho do BA-UCB melhora à medida que o tamanho do grafo aumenta, devido ao compartilhamento de informação via dados observacionais.
  • O CN-UCB falhou em casos onde a intervenção ótima não era um pai da recompensa (comum em modelos contínuos), resultando em regret linear.
• Comparação com BBB-UCB (Bayesiano):
  • O BA-UCB foi computacionalmente muito mais eficiente e escalável. O BBB-UCB tornou-se inviável para $p \ge 20$ devido à complexidade exponencial.
  • Em termos de regret, o BA-UCB foi competitivo ou superior, com uma fração muito menor do tempo de execução.
• Robustez: O algoritmo demonstrou consistência na convergência das estimativas e na identificação correta de conjuntos de ajuste à medida que mais dados eram coletados.

5. Significado e Impacto

Este trabalho representa um avanço significativo na interseção entre aprendizado por reforço e inferência causal:

• Viabilidade Prática: Torna o bandit causal aplicável a cenários do mundo real onde a estrutura causal é desconhecida e dados observacionais históricos estão disponíveis.
• Eficiência de Amostragem: Demonstra que dados observacionais, embora não sejam experimentais, podem ser usados para reduzir drasticamente o custo de exploração (regret), especialmente quando o custo de experimentação é alto.
• Generalização: A extensão para ADMG com confundidores latentes amplia a aplicabilidade do método para sistemas complexos onde variáveis não observadas são comuns (ex: saúde, economia).
• Mudança de Paradigma: Em vez de tentar "descobrir o grafo" antes de agir, o algoritmo aprende a estrutura necessária para a identificação causal enquanto toma decisões, otimizando o compromisso entre exploração e exploração.

Em resumo, o BA-UCB oferece uma solução robusta, teoricamente fundamentada e computacionalmente eficiente para a tomada de decisão sequencial em sistemas causais complexos e parcialmente observados.