Exploiting Similarities in A/B Testing with Off-Policy Estimation

Resumo Técnico: Explorando Semelhanças em Testes A/B com Estimativa Off-Policy

Problema
O teste A/B é o protocolo padrão para medir o ganho de desempenho de um novo sistema de decisão ($\pi_A$) em relação a uma linha de base ($\pi_B$). Tradicionalmente, isso é realizado usando um estimador de diferença de médias, que trata ambos os sistemas como caixas pretas. Embora não enviesado, este estimador é estatisticamente subótimo porque ignora potenciais semelhanças estruturais entre as políticas. Em aplicações online modernas (ex: publicidade, recomendações), os sistemas de decisão são frequentemente estocásticos e compartilham uma estrutura significativa, o que significa que possuem "propensidades" semelhantes de tomar decisões específicas. O artigo argumenta que, quando as políticas se sobrepõem, o estimador clássico sofre de uma variância desnecessária, enquanto os métodos padrão de estimativa off-policy (OPE), que dependem de ponderação de importância, são frequentemente muito enviesados ou instáveis para substituir o teste A/B diretamente.

Metodologia
Os autores propõem uma família de estimadores de teste A/B que aproveitam técnicas de estimativa off-policy para explorar a sobreposição entre $\pi_A$ e $\pi_B$ sem alterar o protocolo experimental padrão.

1. Estrutura: O problema é modelado dentro de uma estrutura estendida de Processo de Decisão de Markov Não-Markoviano (NMDP), onde usuários interagem com o sistema ao longo de trajetórias $\tau$. O objetivo é estimar a melhoria $I(\pi_A, \pi_B) = V(\pi_A) - V(\pi_B)$.
2. Construção do Estimador: O estimador proposto $\hat{I}_f$ combina dois componentes:
   • Um termo de Pontuação de Propensão Inversa (IPS) $f$-regularizado usando dados da política de linha de base ($D_B$).
   • Um termo de correção de viés usando dados da política alvo ($D_A$).
   • A função $f: \mathbb{R}_+ \to \mathbb{R}$ transforma os pesos de importância $w(\tau) = \pi_{target}(\tau) / \pi_{source}(\tau)$.
3. Condições Teóricas:
   • Não-viesamento: O estimador é não-enviesado se $f(0) = -1$. Esta condição garante que, quando as políticas possuem suportes disjuntos (sem sobreposição), o estimador retorna naturalmente ao estimador de diferença de médias padrão.
   • Redução de Variância: Para reduzir a variância, os autores definem um surrogação de variância $S_f$. Eles derivam condições para $f$ (especificamente $f(1)=0$ e limites para $f(x)$) que garantem uma variância menor do que o estimador de diferença de médias quando as políticas são similares.
4. Transformações Ótimas:
   • Surrogação-Ótima ($f^*_{n_r}$): Os autores derivam uma função de forma fechada $f^*_{n_r}(x) = \frac{x-1}{n_r x + 1}$ (onde $n_r = n_A/n_B$) que minimiza a surrogação de variância. Este estimador efetivamente repondera os dados de ambas as populações para lidar com o desequilíbrio de amostra.
   • Consciente de Erros de Especificação ($f^*_{\lambda, \Delta}$): Reconhecendo que as propensidades são frequentemente estimadas a partir de dados em vez de serem conhecidas, os autores introduzem um parâmetro de regularização $\lambda$ para equilibrar viés e variância sob erro de especificação de propensão. Isso resulta em um estimador robusto que degrada graciosamente para o estimador de diferença de médias conforme a especificação incorreta aumenta.

Principais Contribuições

• Nova Família de Estimadores: Introdução de uma família flexível de estimadores de teste A/B baseada em ponderação de importância que explora explicitamente a sobreposição de políticas.
• Garantias Teóricas: Prova de que os estimadores são não-enviesados sob condições específicas de $f$ e demonstram propriedades de concentração melhoradas (menor variância) quando as políticas são similares.
• Robustez: Desenvolvimento de variantes conscientes de erro de especificação que permanecem robustas quando as propensões são estimadas a partir de dados, evitando a alta variância ou viés típicos dos métodos OPE padrão.
• Degradação Graciosa: Os estimadores são projetados para retornar automaticamente ao estimador de diferença de médias padrão quando as políticas são distintas (sem sobreposição) ou quando a especificação incorreta é severa, garantindo que não haja perda de desempenho em cenários desfavoráveis.

Resultados Experimentais
Os autores validam sua abordagem através de três configurações experimentais:

1. Políticas Sobrepostas e Desequilíbrio de Dados: Em um cenário simplificado de bandit, os estimadores propostos alcançaram uma redução substancial de variância (até 27x em cenários específicos) quando as políticas estavam próximas. A redução foi particularmente eficaz ao lidar com alocações de usuários desequilibradas ($n_A \neq n_B$), onde o estimador de diferença padrão tem dificuldades.
2. Sensibilidade à Especificação Incorreta: Em cenários com erros induzidos na estimativa de propensão, o IPS padrão e os estimadores regularizados ingênuos ($h_1$) mostraram alto Erro Quadrático Médio (MSE). Em contraste, os estimadores conscientes de erro de especificação propostos superaram consistentemente o baseline de diferença de médias, mantendo um MSE menor mesmo sob níveis moderados ou altos de especificação incorreta.
3. Problema de Recomendação Realista: Simulando um ambiente de recomendação não-markoviano com tédio do usuário, os autores testaram horizontes $T \in \{1, \dots, 32\}$. O estimador de variância ótima ($f^*_1$) reduziu significativamente o MSE para horizontes curtos a moderados. No entanto, para horizontos longos, erros acumulados na estimativa de propensão degradaram o desempenho. O estimador consciente de erro de especificação proporcionou ganhos estáveis e modestos em todos os horizontes, superando tanto o estimador de diferença padrão quanto outras abordagens de OPE como o DiffQ.

Significância e Alegações
O artigo afirma que ideias de estimativa off-policy não devem servir meramente como um substituto para o teste A/B, mas como uma ferramenta para aumentar a eficiência estatística do próprio teste A/B. Ao aproveitar as propensões conhecidas ou estimadas dos sistemas sendo testados, os praticantes podem obter estimativas de melhoria mais precisas com o mesmo tamanho de amostra. O método proposto é significativo porque:

• Não requer mudanças no protocolo padrão de coleta de dados de teste A/B.
• É robusto à realidade prática das propensões estimadas.
• Oferece um cenário de "melhor dos dois mundos": proporciona redução substancial de variância quando as políticas são similares (o caso comum em atualizações iterativas de sistemas) enquanto garante segurança (não pior do que o teste A/B padrão) quando elas não são.

Os autores concluem que, embora sua abordagem aborde o problema da variância em políticas sobrepostas, desafios permanecem para horizontes muito longos onde o desvio de propensão é significativo, sugerindo trabalhos futuros para explorar estruturas sequenciais e métodos de dupla robustez.