A More Accurate Algorithm Comparison through A/B Testing using Offline Evaluation Methods

Resumo Técnico: Uma Comparação de Algoritmos Mais Precisa através de Testes A/B usando Métodos de Avaliação Offline

1. Declaração do Problema

No desenvolvimento de serviços online, como sistemas de recomendação e mecanismos de busca, selecionar o algoritmo superior é crítico. Embora o teste A/B seja amplamente considerado o "padrão ouro" para a seleção de algoritmos devido à sua capacidade de eliminar fatores de confusão através da randomização, ele é frequentemente custoso e acarreta riscos de degradar a experiência do usuário ou a receita se um algoritmo ruim for implantado. Por outro conjunto, a avaliação offline (usando dados de logs históricos) é mais segura, mas tradicionalmente considerada menos precisa devido à maior variância de estimativa e ao potencial viés.

Os autores identificam um fenômeno contraintuitivo: em certos cenários, o estimador de Média (AVG) padrão usado em testes A/B produz uma taxa de erro de seleção de algoritmo maior do que métodos de avaliação offline como o Inverse Propensity Scoring (IPS). A questão central reside nas propriedades estatísticas dos estimadores:

• Estimador AVG: Utiliza dados independentes para o Algoritmo A e o Algoritmo B. Consequentemente, as estimativas de desempenho são não correlacionadas. A variância do estimador de diferença é simplesmente a soma das variâncias individuais ($Var(\hat{V}_A) + Var(\hat{V}_B)$), não oferecendo nenhum mecanismo para reduzir a variância através da correlação.
• Estimadores Offline (ex: IPS): Utilizam dados históricos compartilhados para estimar o desempenho de múltiplos algoritmos. Isso induz involuntariamente uma correlação positiva entre os estimadores. De acordo com a fórmula de decomposição da variância ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$), essa covariância positiva reduz a variância total do estimador de diferença, diminuindo assim a probabilidade de erros críticos de seleção (subestimar o algoritmo superior ou superestimar o inferior).

O artigo postula que o teste A/B falha em aproveitar essa correlação benéfica, levando a uma precisão de seleção subótima em comparação com métodos offline em experimentos prévios específicos.

2. Metodologia: O Estimador Middle-In-Difference (MID)

Para abordar a falta de correlação no teste A/B, os autores propõem um novo estimador chamado Middle-In-Difference (MID). A ideia central é induzir intencionalmente uma correlação positiva dentro da estrutura de teste A/B, introduzindo um hipotético algoritmo do meio ($\pi_M$).

Processo de Estimativa Passo a Passo:
Em vez de comparar diretamente o Algoritmo A ($\pi_A$) e o Algoritmo B ($\pi_B$), o MID decompõe a diferença de desempenho em duas etapas:

1. Estimar a diferença entre $\pi_A$ e $\pi_M$ usando os dados de log coletados de $\pi_A$ ($D_A$).
2. Estimar a diferença entre $\pi_M$ e $\pi_B$ usando os dados de log coletados de $\pi_B$ ($D_B$).

O estimador final é a soma dessas duas diferenças:
$$\Delta \hat{V}_{MID} = (\hat{V}_{IPS}(\pi_A; D_A) - \hat{V}_{IPS}(\pi_M; D_A)) + (\hat{V}_{IPS}(\pi_M; D_B) - \hat{V}_{IPS}(\pi_B; D_B))$$

Mecanismo de Redução de Variância:

• Correlação Induzida: Como o primeiro termo usa dados compartilhados $D_A$ para estimar tanto $\pi_A$ quanto $\pi_M$, e o segundo termo usa $D_B$ para $\pi_M$ e $\pi_B$, correlações positivas são induzidas dentro de cada etapa. Isso reduz a variância dos termos de diferença individuais.
• Algoritmo do Meio Ótimo: Os autores derivam o algoritmo do meio ótimo $\pi_M^*$ que minimiza a variância do estimador. A política ótima é definida como a média harmônica das políticas de registro:
  $$\pi_M^*(a|x) = \frac{2\pi_A(a|x)\pi_B(a|x)}{\pi_A(a|x) + \pi_B(a|x)}$$
  Este design garante que $\pi_M$ permaneça altamente semelhante tanto a $\pi_A$ quanto a $\pi_B$, mitigando a "explosão de variância" frequentemente vista na avaliação offline ao comparar algoritmos dissimilares (um modo comum de falha do IPS padrão).

Propriedades Teóricas:

• Não-viesamento (Unbiasedness): Os autores provam que, se o algoritmo do meio satisfizer a condição de que ele apenas seleciona ações onde pelo menos um dos algoritmos originais tem probabilidade não nula, o estimador permanece não-viesado.
• Comparação de Variância: A análise teórica demonstra que o termo de recompensa da variância do MID é estritamente menor ou igual ao do estimador AVG padrão. Além disso, ao contrário do IPS padrão, o MID evita a explosão de variância $1/\pi_A$ quando a similaridade entre algoritmos é baixa, porque as comparações intermediárias envolvem políticas similares.

3. Principais Contribuições

1. Insight Estatístico: O artigo esclarece que o estimador AVG padrão em testes A/B não é necessariamente ótimo para a seleção de algoritmos porque falha em explorar os benefícios de redução de variância da correlação positiva entre estimadores.
2. Novo Estimador (MID): Os autores propõem o estimador MID, que induz intencionalmente a correlação positiva via um algoritmo do meio hipotético e estimativa passo a passo, alcançando taxas de erro de seleção menores do que tanto o teste A/B padrão (AVG) quanto a avaliação offline (IPS).
3. Derivação Teórica: O artigo deriva o algoritmo do meio ótimo para minimizar a variância e fornece uma análise de viés-variância mostrando por que o MID supera os métodos existentes.
4. Validação Empírica: Usando dados reais de recomendação de vídeo (KuaiRec), os autores demonstram que o MID alcança consistentemente menores taxas de erro de seleção em vários cenários.

4. Resultados Experimentais

Os autores conduziram experimentos usando o conjunto de dados KuaiRec, um conjunto de dados de recomendação de vídeo totalmente observado que permite o cálculo do desempenho real dos algoritmos. Eles simularam um ambiente de teste A/B com variados tamanhos de amostra e similaridades de algoritmos.

• Eficiência de Amostra: O MID alcançou a mesma taxa de erro de seleção que os métodos existentes (AVG e IPS) usando apenas metade ou um quarto do tamanho da amostra do teste A/B. Por exemplo, enquanto o AVG exigiu 350–400 amostras para atingir uma taxa de erro de 5%, o MID alcançou o mesmo com 100–200 amostras.
• Robustez à Similaridade:
  • Em cenários de alta similaridade, o MID superou o IPS (que normalmente enfrenta dificuldades com variância em ambientes offline) e o AVG.
  • Em cenários de baixa similaridade, onde o IPS sofre com a explosão de variância devido ao peso de importância, o MID permaneceu estável e superou tanto o IPS quanto o AVG.
• Verificação de Mecanismo: Gráficos de dispersão das estimativas confirmaram que o MID induz com sucesso a correlação positiva entre os estimadores passo a passo, resultando em uma distribuição mais estreita da estimativa de diferença final em comparação com a distribuição circular (não correlacionada) do AVG. Esse espalhamento mais estreito correlaciona-se diretamente com uma redução nos erros críticos de seleção.

5. Significância e Alegações

O artigo afirma que o estimador MID proposto melhora fundamentalmente a eficiência e a precisão dos testes A/B para a seleção de algoritmos. Ao tomar emprestado o mecanismo estatístico da avaliação offline (dados compartilhados induzindo correlação) e aplicá-lo dentro da estrutura de teste A/B via um algoritmo do meio hipotético, o MID supera as limitações tanto do teste A/B tradicional (alta variância devido à independência) quanto da avaliação offline (instabilidade devido à baixa similaridade ou falta de novos dados).

Os autores enfatizam que esta abordagem permite que organizações tomem decisões de seleção de algoritmos mais precisas com significativamente menos usuários ou durações de experimento menores, reduzindo o custo e o risco associados à experimentação online. O trabalho sugere que o "padrão ouro" do teste A/B pode ser aprimorado não abandonando-o, mas refinando a técnica de estimativa para aproveitar as correlações estatísticas que anteriormente não eram exploradas em ambientes online.