Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making

1. Formulação do Problema

O artigo aborda o desafio da alocação de tratamentos com restrição orçamentária em publicidade digital, especificamente em cenários de início frio (cold-start) onde dados históricos são escassos ou inexistentes (ex.: novas campanhas, novos mercados).

• Objetivo Central: Maximizar o total de conversões (resultados do tratamento) selecionando um subconjunto de usuários para exibir anúncios, sujeito a uma restrição orçamentária total $B$.
• Principais Restrições e Desafios:
  1. Efeitos de Tratamento Heterogêneos (HTE): Os usuários respondem de maneira diferente aos anúncios. O objetivo é direcionar usuários com altos efeitos causais positivos ($\tau(x)$), evitando aqueles que não são afetados ou são afetados negativamente.
  2. Restrições Orçamentárias: Cada usuário tem um custo específico $c_t$ (ex.: preço de leilão de anúncio). O custo cumulativo não deve exceder $B$.
  3. Início Frio / Escassez de Dados: Métodos offline tradicionais exigem grandes conjuntos de dados históricos para treinar modelos de impacto. Em novos cenários, esses dados não estão disponíveis, levando ao problema de "início frio".
  4. Tomada de Decisão Sequencial: Os usuários chegam um por um. O sistema deve aprender os efeitos de tratamento online enquanto gerencia simultaneamente o ritmo do orçamento (evitando o esgotamento prematuro ou o gasto insuficiente desperdiçado).

Definição Formal:
O problema é modelado como um processo sequencial ao longo de $T$ rodadas. Em cada rodada $t$, o agente observa um usuário com características $x_t$ e custo $c_t$, e escolhe uma ação $a_t \in \{0, 1\}$ (tratar ou não). O objetivo é:
$$\max \sum_{t=1}^T a_t \cdot Y_t(1) \quad \text{sujeito a} \quad \sum_{t=1}^T a_t \cdot c_t \le B$$
onde $Y_t(1)$ é o resultado potencial se tratado.

2. Metodologia: Bandits Causais com Restrição Orçamentária (BCCB)

Os autores propõem o BCCB, um framework online unificado que integra três componentes distintos em um único processo de decisão sequencial. Diferentemente de pipelines offline de duas etapas (treinar e depois otimizar) ou bandits padrão (que ignoram HTE), o BCCB aprende, explora e ajusta o ritmo simultaneamente.

A. Estimação Online de HTE

• Abordagem: Utiliza uma abordagem de dois modelos para estimar efeitos de tratamento individuais online.
  • Modelo 1: Estima $P(Y=1 | x, T=1)$ (Probabilidade de conversão se tratado).
  • Modelo 2: Estima $P(Y=1 | x, T=0)$ (Probabilidade de conversão se controle).
• Mecanismo: Ambos os modelos são atualizados incrementalmente usando Descida de Gradiente Estocástico (SGD) com perda logística após cada observação.
• Tratamento de Início Frio: Antes que dados suficientes sejam coletados (menos de 50 observações tratadas/controle), um prior otimista ($\hat{\tau} = 0.002$) é usado para encorajar a exploração inicial.

B. Exploração por Amostragem de Thompson

• Objetivo: Equilibrar exploração (aprender sobre usuários incertos) e exploração (direcionar usuários de alto valor conhecidos).
• Mecanismo: Mantém distribuições posteriores Beta para as taxas globais de sucesso do tratamento e do controle.
• Bônus de Exploração: Em cada passo, o algoritmo amostra das posteriores para calcular um bônus de exploração:
  $$\text{bônus\_exploração}_t = (\theta_t^{(1)} - \theta_t^{(0)}) \cdot \eta$$
  Este bônus é adicionado ao HTE estimado, encorajando o algoritmo a tratar usuários com efeitos incertos, mesmo que a estimativa atual de HTE seja ambígua.

C. Ajuste Adaptativo de Orçamento (Budget Pacing)

• Objetivo: Prevenir o esgotamento prematuro do orçamento ou o gasto insuficiente ineficiente.
• Mecanismo: Calcula uma razão de pressão orçamentária ($pace_t$) em cada rodada:
  $$pace_t = \frac{B_t / B_0}{(T - t) / T}$$
  • Se $pace_t > 1$: O orçamento é abundante em relação ao tempo; o algoritmo gasta mais livremente.
  • Se $pace_t < 1$: O orçamento está se esgotando muito rápido; o algoritmo torna-se mais seletivo.
• Modulação de Limiar: A razão de ajuste dinamicamente ajusta o limiar de decisão. Quando o orçamento é escasso, o limiar para tratamento aumenta, garantindo que apenas usuários de alta relação custo-benefício sejam selecionados.

D. Regra de Decisão Combinada

Para cada usuário $t$, o algoritmo calcula uma pontuação e uma métrica de valor por dólar:

1. Pontuação: $s_t = \hat{\tau}(x_t) + \text{bônus\_exploração}_t$
2. Valor: $v_t = s_t / c_t$
3. Decisão: Tratar ($a_t=1$) se $v_t > \frac{\lambda}{\max(pace_t, \epsilon)}$, onde $\lambda$ é um limiar base.

3. Principais Contribuições

1. Framework Unificado: Propõe o BCCB, o primeiro framework a unificar aprendizado de HTE, exploração por Amostragem de Thompson e ajuste adaptativo de orçamento em um único processo online sem exigir dados históricos pré-coletados.
2. Cruzamento de Eficiência de Dados: Identifica empiricamente um limiar crítico (~10.000 observações históricas). Abaixo deste, métodos offline falham ou são altamente instáveis; acima deste, métodos offline podem superar os online. O BCCB opera efetivamente desde o primeiro usuário.
3. Estabilidade de Desempenho: Demonstra que o BCCB possui 3–5x menor variância de desempenho comparado a métodos offline em execuções repetidas, tornando-o mais confiável para o planejamento de campanhas.
4. Desempenho Online Superior: Entre métodos puramente online, o BCCB supera consistentemente a Amostragem de Thompson Padrão, a Amostragem de Thompson Orçamentada e a estimação HTE Gananciosa em todos os níveis de orçamento.

4. Resultados Experimentais

O estudo foi avaliado no conjunto de dados Criteo Uplift (1,4 milhão de usuários) com custos sintéticos gerados via distribuição log-normal.

• Comparação Online vs. Online:
  • Com um orçamento alto ($8.000), o BCCB alcançou 46 conversões, superando a Amostragem de Thompson Padrão (37) e o HTE Ganancioso (29).
  • Com orçamentos apertados ($1.000), o BCCB e a TS Orçamentada performaram melhor, destacando a importância da consciência orçamentária.
• Cruzamento de Eficiência de Dados (Offline vs. Online):
  • < 2.000 observações: Métodos offline falharam completamente (o modelo não pôde ajustar devido a exemplos positivos zero no grupo de controle). O BCCB operou com sucesso.
  • 2.000 – 10.000 observações: Métodos offline mostraram variância extrema (Coeficiente de Variação > 100%). O BCCB permaneceu estável.
  • > 50.000 observações: Métodos offline eventualmente superaram o BCCB (104 vs. 25 conversões), confirmando que métodos offline são superiores quando dados abundantes e representativos existem.
• Estabilidade: O BCCB exibiu desvios padrão de 7–13 conversões, enquanto métodos offline variaram de 35–65. Esta redução de 3–5x na variância é crucial para previsões de ROI previsíveis.
• Escalabilidade: O BCCB manteve o desempenho superior em diferentes escalas de conjuntos de dados (100K, 500K, 1,4M de usuários), enquanto métodos de HTE Ganancioso foram altamente inconsistentes.

5. Significado e Limitações

Significado:

• Resolve o Problema de Início Frio: Oferece uma solução viável para novas campanhas publicitárias onde dados históricos não estão disponíveis, um cenário onde pipelines padrão da indústria falham.
• Mitigação de Risco: A alta estabilidade do BCCB reduz o risco de falha da campanha devido à variância de sementes aleatórias, uma questão comum com modelos offline treinados em pequenos conjuntos de dados.
• Mudança de Paradigma: Move o campo de "treinar e depois implantar" para "aprender e alocar simultaneamente" para inferência causal com restrições de recursos.

Limitações:

• Abundância de Dados: Se uma empresa tiver 50.000+ observações históricas da mesma população, métodos offline permanecem superiores.
• Custos Sintéticos: O estudo usou custos sintéticos baseados em uma distribuição log-normal. Dinâmicas de leilão do mundo real podem ser mais complexas.
• Complexidade do Modelo: A implementação atual usa classificadores lineares para HTE. Modelos online mais expressivos (ex.: redes neurais online) poderiam melhorar a precisão, mas foram deixados para trabalhos futuros.

Conclusão:
O BCCB preenche a lacuna entre modelagem de impacto e tomada de decisão sequencial, oferecendo uma solução robusta e eficiente em dados para alocação de tratamentos com restrição orçamentária em publicidade digital, particularmente em cenários caracterizados por escassez de dados e necessidade de desempenho imediato e estável.