Causal Inference on Stopped Random Walks in Online Advertising

Resumo Técnico: Inferência Causal em Caminhadas Aleatórias Interrompidas em Publicidade Online

Definição do Problema

O artigo aborda um desafio de inferência causal específico para plataformas de publicidade online (editores/publishers), onde o objetivo é estimar o efeito de tratamento de longo prazo de parâmetros de mecanismo, como preços de reserva de leilão. Ao contrário dos cenários clássicos (ex: ensaios clínicos), onde o tamanho da população é fixo e independente do tratamento, a publicidade online envolve um sistema complexo e interconectado de editores, usuários e anunciantes. Neste ambiente:

1. O tratamento afeta o tamanho da população: Um tratamento (ex: um preço de reserva mais alto) altera as trajetórias de interação do usuário (duração da sessão) e os comportamentos de lance dos anunciantes (limitados por orçamentos finitos), alterando, assim, o número total de oportunidades de impressão geradas ao longo de um período de tempo fixo.
2. Interferência e Dinâmica: A decisão de medir os efeitos do tratamento altera o próprio sistema que está sendo medido. As sessões de usuário são modeladas como cadeias de Markov, e os orçamentos dos anunciantes evoluem como outra cadeia de Markov dependente de resultados de leilões passados.
3. Descompasso de Escala de Medição: A métrica alvo é a receita de longo prazo (ex: ao longo de $k$ dias), mas a unidade natural de observação é a impressão de anún individual. O número de impressões em uma janela de tempo fixa é uma variável aleatória (um tempo de parada) dependente do tratamento.

A dificuldade central é que as abordagens padrão do Teorema do Limite Central (TLC) que assumem medições independentes e identicamente distribuídas (i.i.d.) ou tamanhos de amostra fixos são insuficientes. O artigo modela a receita cumulativa como uma caminhada aleatória interrompida (stopped random walk), onde o tempo de parada (total de impressões em $k$ dias) é aleatório e dependente do tratamento.

Metodologia

1. Estrutura de Modelagem
Os autores modelam a interação trilateral entre o editor, os usuários e os anunciantes como uma cadeia de Markov de tempo discreto.

• Espaço de Estados: O estado inclui o perfil das páginas visitadas por todos os usuários ($X_n$), os orçamentos restantes de todos os anunciantes ($\Omega_n$) e o índice do usuário ativo ($I_n$).
• Dinâmica: As transições de página do usuário e as atualizações de orçamento do anunciante são regidas por estratégias estacionárias (funções de preço de reserva e funções de lance) e variáveis aleatórias que representam o comportamento do usuário e a reposição de orçamento.
• Receita: A receita do editor é uma função não linear, potencialmente descontínua, do preço de reserva e do lance vencedor (lógica de leilão de segundo preço).

2. Redução de Dimensionalidade: O Truque da Permutação
Um obstáculo importante é o tamanho exponencial do espaço de estados ao modelar $d$ usuários e $m$ anunciantes simultaneamente. Para resolver isso, os autores introduzem um truque de permutação:

• Motivação: Baseado na observação de que a ordem de intercalação das transições de página de diferentes sessões de usuários concorrentes tem um efeito negligenciável nas vendas agregadas e no fluxo de caixa, desde que as escalas de tempo das sessões de usuário sejam muito menores que as durações das campanhas dos anunciantes.
• Mecanismo: Os autores definem uma permutação $\sigma$ que reordena a sequência de impressões para agrupar todas as transções de página pertencentes à mesma sessão de usuário.
• Resultado: Isso transforma a cadeia de Markov original de alta dimensão em uma aproximação com um espaço de estados significativamente menor ($\mathcal{X} \times \mathbb{R}^m \times [d]$), onde sessões inteiras de usuários são intercaladas em vez de transições de página individuais. Esta aproximação baseia-se na Assunção 2.1, que postula que os orçamentos e durações das campanhas de anúncios são grandes em relação aos custos e durações de sessão de impressões individuais.

3. Desenho Experimental: Divisão de Orçamento (Budget Splitting)
Para estimar o efeito do tratamento, o artigo propõe um desenho experimental de divisão de orçamento (inspirado em [LMK21]):

• Divisão da População: Usuários são atribuídos aleatoriamente a subpopulações $A$ e $B$ com probabilidades $q$ e $1-q$.
• Atribuição de Tratamento: A subpopulação $A$ recebe o tratamento $v$ (preço de reserva $v$) e a $B$ recebe o tratamento $w$.
• Divisão de Orçamento: O orçamento de cada anunciante é dividido proporcionalmente ($q$ e $1-q$) entre as duas subpopulações. Anunciantes em cada grupo competem apenas dentro da cadeia de Markov de sua subpopulação atribuída.
• Estimador: O estimador $\hat{\Delta}$ para o efeito total do tratamento é construído escalonando a receita média observada e as contagens de impressões das subpopulações por $1/q$ e $1/(1-q)$, respectivamente, extrapolando efetivamente os resultados das subpopulações para a população total.

4. Garantias Teóricas
O artigo deriva um intervalo de confiança para o efeito de tratamento de longo prazo usando:

• TLC de Cadeia de Markov: Aplicado às cadeias permutadas para estabelecer a normalidade assintótica das somas de receita.
• Equação tipo Wald: Utilizada para lidar com os tempos de parada aleatórios (total de impressões ao longo de $k$ dias).
• Teorema de Anscombe: Empregado para justificar a convergência da caminhada aleatória interrompida para uma distribuição normal, apesar do tamanho de amostra aleatório.
• Assunções de Ergodicidade: A análise assume que as cadeias de Markov subjacentes são Harris ergódicas e geometricamente ergódicas, garantindo a existência de distribuições invariantes.

Principais Contribuições

1. Modelagem: Introdução de um modelo de caminhada aleatória interrompida para inferência causal onde o tamanho da população (número de impressões) é aleatório e dependente do tratamento. Isso generaliza a inferência causal clássica, que tipicamente assume uma população fixa.
2. Analítica: Desenvolvimento de um truque de permutação para reduzir a dimensionalidade do espaço de estados em sistemas de Markov de múltiplos usuários e múltiplos anunciantes, permitindo uma análise tratável sob suposições moderadas de escalas de tempo.
3. Inferência Estatística: Derivação de intervalos de confiança para efeitos de tratamento de longo prazo neste cenário complexo, combinando um TLC de Markov, uma equação tipo Wald e o Teorema de Anscombe. Isso fornece uma base teórica para determinar a duração necessária dos experimentos.

Resultos
O principal resultado (Teorema 3.6) estabelece que, sob suposições de estratégias invariantes no tempo, ergodicidade e escala de campanha, o estimador proposto $\hat{\Delta}$ converge para o verdadeiro efeito do tratamento $\Delta$. Especificamente, o artigo prova que:
$$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$$
onde $\epsilon$ é um limite dependente das variâncias assintóticas das cadeias das subpopulações e da diferença entre as distribuições invariantes da subpopulação e da população total. O artigo observa que, na prática, com grandes populações de usuários, espera-se que essas distribuições sejam próximas, tornando o estimador eficaz.

Significância e Alegações
O artigo afirma fornecer um arcabouço rigoroso para inferência causal em sistemas de publicidade online onde a "unidade de análise" (sessão de usuário) e a "unidade de medição" (impressão) operam em escalas diferentes, e onde o próprio tratamento altera o volume de dados gerados.

• Ele vai além da suposição de "população finita" da inferência causal clássica para uma população aleatória e dependente do tratamento.
• Oferece uma solução prática para o problema de "interferência" em mercados de dois lados, modelando explicitamente a dinâmica de usuários e anunciantes em vez de depender apenas de técnicas de randomização para controlar a interferência.
• Fornece orientação acionável sobre a duração do experimento, vinculando a largura do intervalo de confiança às variâncias assintóticas e ao número de períodos $k$.

Os autores reconhecem limitações, observando que o modelo assume estratégias estacionárias e não lida explicitamente com dinâmicas não estacionárias (ex: novos anunciantes entrando no sistema). Eles também sugerem que, embora o desenho de divisão de orçamento seja eficaz, ele pode não corrigir efeitos de interferência arbitrários não capturados pelo modelo de Markov específico.