Scalable Policy Maximization Under Network Interference

Resumo Técnico: Maximização de Políticas Escalável sob Interferência de Rede

Declaração do Problema
O artigo aborda o desafio da tomada de decisão sequencial (maximização de políticas) em ambientes caracterizados por interferência de rede, onde o status de tratamento de um indivíduo influencia os resultados de outros. Embora os algoritmos de Bandit Multi-Armed (MAB) sejam padrão para aprendizado sequencial, eles geralmente dependem de suposições de independência que falham em configurações de rede (por exemplo, ensaios clínicos, mercados online, redes sociais).

As abordagens existentes para MABs sob interferência enfrentam duas limitações críticas:

1. Escalabilidade: Os métodos atuais lutam para escalar além de redes muito pequenas (aproximadamente $n \approx 15$ nós). Eles frequentemente tentam capturar padrões de interferência arbitrários, levando a um espaço de parâmetros que cresce exponencialmente com o grau do nó ($d_{max}$) e linearmente com o tamanho da rede ($n$). Para uma rede com $n=1000$ e $d_{max}=10$, isso resulta em mais de um milhão de parâmetros desconhecidos, tornando a estimação computacionalmente inviável.
2. Suposições Estáticas: Muitos algoritmos existentes exigem que a estrutura da rede e a população de indivíduos permaneçam fixas ao longo do tempo, uma suposição que cria inconsistências em ambientes dinâmicos onde os resultados dependem dos históricos de tratamento.

Metodologia
Os autores propõem um algoritmo de Amostragem de Thompson escalável que aproveita suposições estruturais comuns na literatura de inferência causal para alcançar uma parametrização linear parcimoniosa da função de recompensa.

• Suposições Estruturais (SANIA): O método baseia-se na Suposição de Interferência de Vizinhança Simétrica e Aditiva (SANIA).

  • Interferência de Vizinhança (NIA): A recompensa de um nó depende apenas de seu próprio tratamento e do status de tratamento de seus vizinhos imediatos.
  • Aditividade: Efeitos diretos não interagem com efeitos indiretos (transbordamento).
  • Simetria: A recompensa de um nó depende do número de vizinhos tratados, não de suas identidades específicas.
    Sob essas suposições, o vetor de recompensas ao nível do nó pode ser reparametrizado como um sistema linear: $r_t = H(Z_t; A_t)\theta + \epsilon_t$, onde $\theta$ é um vetor de parâmetros de baixa dimensão contendo parâmetros de efeito de tratamento e interferência.

• Design do Algoritmo:

  • O algoritmo mantém uma distribuição a posteriori sobre o vetor de parâmetros $\theta$.
  • Em cada passo de tempo $t$, ele amostra um vetor de parâmetros $\theta^{(t)}$ da posterior e seleciona um vetor de alocação de tratamento $Z_t$ que maximiza a recompensa total esperada condicional a $\theta^{(t)}$.
  • O framework suporta parametrizações flexíveis, incluindo parâmetros compartilhados (todos os nós compartilham $\theta$), parâmetros agrupados (nós em grupos latentes ou observados compartilham $\theta_g$) e modelos de características latentes (onde as posições dos nós em um espaço euclidiano influenciam as recompensas).
  • O algoritmo acomoda redes dinâmicas (onde as matrizes de adjacência $A_t$ mudam) e restrições de orçamento (limitando o número de nós tratados).

• Análise de Arrependimento:

  • Os autores provam um limite superior para o arrependimento bayesiano de $O(D\sqrt{nT} \log(nT))$, onde $D$ é a dimensão de $\theta$, $n$ é o tamanho da rede e $T$ é o horizonte de tempo.
  • Eles derivam um limite inferior correspondente de $\Omega(D\sqrt{nT})$, demonstrando que o algoritmo é quase ótimo.
  • Os limites de arrependimento refletem o trade-off entre a informação aumentada ganha ao observar $n$ nós interdependentes e a complexidade aumentada do espaço de ações.

Principais Contribuições

1. Parametrização Escalável: O artigo demonstra que suposições comuns de inferência causal permitem que a função de recompensa seja expressa como uma função linear de um vetor de parâmetros de baixa dimensão, reduzindo a complexidade de exponencial para polinomial (especificamente, linear em $n$ para modelos compartilhados/agrupados).
2. Amostragem de Thompson Escalável: Os autores desenvolvem um algoritmo capaz de lidar com redes ordens de magnitude maiores do que os métodos anteriores (demonstrado até $n=1000$ em simulações), resolvendo a "maldição da dimensionalidade" inerente a problemas de interferência.
3. Tratamento de Redes Dinâmicas: Ao contrário de trabalhos anteriores que exigem redes fixas, este framework permite que tanto nós quanto arestas sejam amostrados ou alterados em cada período de tempo, resolvendo inconsistências entre a independência temporal e suposições de população fixa.
4. Garantias Teóricas: O artigo fornece limites rigorosos superiores e inferiores para o arrependimento bayesiano, estabelecendo a quase otimalidade da abordagem proposta.

Resultados
Experimentos de simulação validam o método em três esquemas de parametrização:

• Parâmetros Compartilhados: O algoritmo aprende rapidamente e escala efetivamente para redes de tamanho $n \in \{100, 500, 1000, 2500\}$.
• Parâmetros Agrupados: O método performa bem mesmo quando os rótulos de grupo são parcialmente latentes e devem ser estimados usando um nó "âncora" por grupo.
• Características Latentes: O algoritmo lida com sucesso com efeitos heterogêneos dependentes de características latentes dos nós em modelos de espaço latente.

Comparações:

• vs. Agarwal et al. (2024): O método proposto supera significativamente o estado da arte existente (que usa análise de Fourier e interferência de rede esparsa) em redes estáticas pequenas. Crucialmente, o método proposto permanece robusto e supera Agarwal et al. mesmo quando as suposições SANIA estão especificadas incorretamente (por exemplo, quando a aditividade ou simetria é violada). Isso é atribuído à capacidade do método proposto de aprender uma aproximação eficaz com muito menos parâmetros, enquanto os métodos concorrentes sofrem de alta variância devido à necessidade de estimar vetores de parâmetros exponencialmente maiores.
• vs. MAB Padrão: Abordagens padrão de MAB falham em escalar devido ao crescimento exponencial do espaço de ações ($2^n$ braços).

Significância
O artigo afirma fechar uma lacuna de escalabilidade chave entre métodos de inferência causal para interferência e algoritmos práticos de bandit. Ao permitir a otimização de políticas em sistemas de rede em grande escala, o trabalho une a divisão entre identificação causal teórica e tomada de decisão dinâmica. Os autores sugerem que este framework facilita a aplicação de algoritmos de bandit a problemas do mundo real envolvendo redes grandes e dinâmicas, como distribuição de vacinas ou intervenções em mercados online, onde a interferência é prevalente, mas anteriormente complexa demais para ser modelada dinamicamente.