Resumo Técnico: Identificação do Melhor Braço com Confiança Fixa para Análise de Mediação Causal

1. Definição do Problema

Este artigo aborda o problema de Identificação do Melhor Braço (Best-Arm Identification - BAI) dentro de um cenário de bandido causal, focando especificamente em análise de mediação causal.

• Contexto: Em bandidos causais padrão, o objetivo é tipicamente maximizar a média intervencional $E[Y | do(X=x)]$, que agrega efeitos através de todos os caminhos causais. No entanto, pesquisadores frequentemente desejam isolar o efeito de um tratamento $X$ sobre um resultado $Y$ que não passa por um mediador específico $Z$ (por exemplo, para excluir mecanismos antiéticos, viés de posicionamento em anúncios ou reações intermediárias adversas).
• Objetivo: O artigo visa identificar o braço $x^*$ que maximiza o Resultado Potencial Direto Natural Esperado (NDPO), definido como $E[Y_{x, Z_{x_0}}]$. Esta quantidade representa o resultado esperado se o tratamento for definido como $x$ enquanto o mediador $Z$ é mantido no valor que teria tomado sob um braço de referência $x_0$.
• Configuração: O problema é formulado em uma configuração de confiança fixa, onde um aprendiz puxa braços sequencialmente (intervenções $do(X=x)$), observando amostras i.i.d. da distribuição intervencional $P(Z, Y | do(X=x))$. O objetivo é identificar o braço ótimo com probabilidade de pelo menos $1-\delta$ enquanto minimiza o tempo de parada esperado (complexidade de amostragem).

2. Metodologia

2.1 Identificação ao Nível da População

Os autores estabelecem primeiro que o NDPO esperado é identificável a partir de distribuições intervencionais observáveis sob um cenário de bandido causal.

• Suposição: Eles baseiam-se na suposição padrão de identificação para efeitos diretos naturais: $Y_{x,z} \perp\!\!\perp Z_{x'}$ para todo $x, x', z$. Graficamente, isso corresponde à ausência de confusão não medida entre o mediador $Z$ e o resultado $Y$ no grafo onde as arestas de saída de $X$ e $Z$ são removidas.
• Fórmula de Identificação: Sob esta suposição, o NDPO esperado $\theta(x)$ é identificado como:
  $$\theta(x) = \sum_{y,z} y P(Y=y | Z=z, do(X=x)) P(Z=z | do(X=x_0))$$
  Esta formulação permite a estimação usando apenas as distribuições intervencionais conjuntas $P(Z, Y | do(X=x))$e$P(Z | do(X=x_0))$, evitando a necessidade de contrafatuais aninhados que não são diretamente observáveis no cenário de bandido.

2.1 Complexidade de Amostragem (Limite Inferior)

O artigo deriva um limite inferior dependente da instância para a complexidade de amostragem de qualquer algoritmo $\delta$-correto.

• Diferença Fundamental em relação ao BAI Padrão: Ao contrário do BAI padrão, onde o objetivo depende apenas da própria distribuição do braço, o NDPO acopla a distribuição do resultado sob o braço $x$ com a distribuição do mediador sob o braço de referência $x_0$.
• Estrutura de Complexidade: O limite inferior envolve um problema de otimização semi-infinito. O tempo característico $T^*(P)$ é definido por:
  $$(T^*(P))^{-1} = \sup_{w \in \Sigma_K} \inf_{Q \in \text{Alt}(P)} \sum_{x \in \mathcal{X}} w_x KL(P_x \| Q_x)$$
  onde $\text{Alt}(P)$ é o conjunto de modelos alternativos onde um braço diferente é o ótimo. A restrição que define $\text{Alt}(P)$ é não-separável porque a distribuição do mediador de referência $Q_{x_0}(Z)$ aparece no objetivo para cada braço, criando um acoplamento entre os braços que não existe no BAI clássico.

2.3 Algoritmo Proposto: TaS-NDPO

Os autores propõem o TaS-NDPO, um algoritmo de Track-and-Stop (TaS) adaptado para este objetivo específico. O algoritmo consiste em três componentes principais:

1. Estimação Plug-in: Estimativas empíricas das distribuições intervencionais são usadas para computar estimativas plug-in de $\theta(x)$.
2. Regra de Amostragem (D-tracking com Forçamento):
   • D-tracking: O algoritmo rastreia as proporções de amostragem ótimas $w^*$ derivadas do limite inferior.
   • Cobertura de Competidores: Para lidar com as restrições não-separáveis, o algoritmo garante que cada braço seja selecionado como um "competidor" no problema de otimização suficientemente vezes.
   • Forçamento ao Nível de Célula: Crucialmente, o algoritmo força a exploração ao nível de célula $(x, z)$ (combinações de valor de braço e mediador). Isso é necessário porque a divergência KL se decompõe em termos ponderados pelas probabilidades do mediador; valores raros do mediador devem ser amostrados o suficiente para garantir a estimação consistente das probabilidades condicionais do resultado $P(Y|Z, do(X))$.
3. Regra de Parada (GLRT): O algoritmo para quando o estatístico do Teste de Razão de Verossimilhança Generalizado (GLRT) excede um limiar $\beta(t, \delta)$. O estatístico mede a divergência KL mínima para qualquer modelo alternativo onde um braço subótimo pareça melhor que o atual melhor braço.
4. Solver de Otimização: Resolver a minimização interna na regra de amostragem e na regra de parada envolve um problema de otimização semi-infinito. Os autores empregam um método de conjunto de cortes (cutting-set method; Mutapçic e Boyd, 2009) combinado com uma redução para três braços (o de referência, o atual melhor e um competidor) e um esquema de minimização alternada para resolver os subproblemas bi-convexos resultantes.

3. Principais Contribuições

1. Formulação do Problema: O artigo define e estuda formalmente o problema de BAI para maximizar o NDPO esperado, uma quantidade relevante para isolar efeitos diretos causais na presença de mediadores.
2. Identificação em Bandidos: Estabelece a identificação do NDPO esperado usando apenas as distribuições intervencionais disponíveis em um cenário de bandido causal, unindo a teoria de inferência causal com a tomada de decisão sequencial.
3. Limites Teóricos: Deriva um novo limite inferior de complexidade de amostragem que destaca os desafios únicos da otimização de NDPO, especificamente o acoplamento de braços via a distribuição do mediador de referência e a necessidade de acumulação de informação ao nível de célula.
4. Design de Algoritmo: Introduz o TaS-NDPO, um novo algoritmo que:
   • Utiliza um método de conjunto de cortes para resolver a otimização complexa de semi-infinito necessária para as proporções de amostragem ótimas.
   • Incorpora o forçamento ao nível de célula para garantir consistência em regimes de esparsidade de mediadores.
   • Prova a $\delta$-corretude (corretude garantida com probabilidade $1-\delta$) e a otimalidade assintótica (alcançando o limite inferior na complexidade de amostragem conforme $\delta \to 0$).

4. Resultados Experimentais

Os autores avaliaram o TaS-NDPO tanto em dados sintéticos quanto em um grande conjunto de dados de publicidade do mundo real (IPinYou).

• Validação no Mundo Real (IPinYou):
  • O conjunto de dados envolvia a seleção de criativos de anúncios ($X$) para maximizar cliques ($Y$), com a visibilidade do slot ($Z$) como o mediador.
  • Divergência de Decisão: O braço que maximiza a média intervencional padrão era diferente do braço que maximiza o NDPO. A média padrão favorecia um criativo que aparecia frequentemente em slots superiores (efeito mediado), enquanto o braço ótimo do NDPO era diferente.
  • Desempenho: O TaS-NDPO alcançou um tempo de parada mediana de 12.928 amostras, aproximadamente 50% mais eficiente que a variante de nível de braço (25.856 amostras) e superando significativamente a amostragem uniforme e uma abordagem de prioridade ao braço de referência (baseline-first). Todos os métodos mantiveram taxas de erro empírico zero para $\delta=0.05$.
• Experimentos Sintéticos:
  • Escalonamento de Gap: Os resultados confirmaram o escalonamento $1/\Delta^2$ da complexidade de amostragem previsto pelo limite inferior.
  • Esparsidade do Mediador: A vantagem do forçamento ao nível de célula foi mais pronunciada em configurações com células mediador-resultado raras (regimes esparsos), onde o forçamento ao nível de braço falhou em acumular informação suficiente.
  • Tempo de Execução: O overhead computacional do método de conjunto de cortes foi moderado (média de 22,5 segundos por execução para até 100 mil amostras), não constituindo um gargalo em comparação aos ganhos em eficiência de amostragem.

5. Significância e Alegações

O artigo afirma que o TaS-NDPO fornece uma solução teoricamente fundamentada e empiricamente eficiente para identificar tratamentos que maximizam efeitos causais diretos enquanto excluem caminhos mediados.

• Significância Teórica: Estende o framework Track-and-Stop para cenários causais com contrafatuais aninhados, provando que a otimalidade assintótica é alcançável mesmo quando a função objetivo acopla distribuições de diferentes braços (via o mediador de referência).
• Significância Prática: Ao isolar efeitos diretos, o método permite a tomada de decisão que evita mecanismos indesejáveis (ex: clickbait, efeitos colaterais adversos ou posicionamento antiético) que poderiam, de outra forma, ser favorecidos por abordagens de maximização de média padrão.
• Modéstia: Os autores reconhecem que seu framework atual foca em resultados binários e uma estrutura de grafo causal específica (Mediador entre Tratamento e Resultado). Eles observam que estender para resultados multicategoria é direto, mas generalizar para efeitos específicos de caminho em estruturas causais mais amplas permanece como uma direção para trabalhos futuros. Eles também esclarecem que a identificação depende da plausibilidade do grafo causal subjacente (especificamente a ausência de confusão não medida entre $Z$ e $Y$), que é uma suposição padrão, porém não testável, em inferência causal.