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

Resumen Técnico: Una comparación de algoritmos más precisa mediante pruebas A/B utilizando métodos de evaluación offline

1. Planteamiento del problema

En el desarrollo de servicios en línea como sistemas de recomendación y motores de búsqueda, la selección del algoritmo superior es crítica. Aunque las pruebas A/B son ampliamente consideradas como el "estándar de oro" para la selección de algoritmos debido a su capacidad para eliminar factores de confusión mediante la aleatorización, suelen ser costosas y conllevan el riesgo de degradar la experiencia del usuario o los ingresos si se despliega un algoritmo deficiente. Por el contrario, la evaluación offline (utilizando datos de registros históricos) es más segura, pero tradicionalmente se considera menos precisa debido a una mayor varianza de estimación y un posible sesgo.

Los autores identifican un fenómeno contraintuitivo: en ciertos escenarios, el estimador de Promedio (AVG) estándar utilizado en las pruebas A/B produce una tasa de error de selección de algoritmos más alta que los métodos de evaluación offline como el Inverse Propensity Scoring (IPS). El problema central reside en las propiedades estadísticas de los estimadores:

• Estimador AVG: Utiliza datos independientes para el Algoritmo A y el Algoritmo B. En consecuencia, las estimaciones de rendimiento no están correlacionadas. La varianza del estimador de la diferencia es simplemente la suma de las varianzas individuales ($Var(\hat{V}_A) + Var(\hat{V}_B)$), lo que no ofrece ningún mecanismo para reducir la varianza mediante la correlación.
• Estimadores Offline (ej. IPS): Utilizan datos históricos compartidos para estimar el rendimiento de múltiples algoritmos. Esto induce involuntariamente una correlación positiva entre los estimadores. De acuerdo con la fórmula de descomposición de la varianza ($Var(X-Y) = Var(X) + Var(Y) - 2Cov(X,Y)$), esta covarianza positiva reduce la varianza total del estimador de la diferencia, disminuyendo así la probabilidad de errores críticos de selección (subestimar el algoritmo superior o sobreestimar el inferior).

El artículo postula que las pruebas A/B no aprovechan esta correlación beneficiosa, lo que conduce a una precisión de selección subóptima en comparación con los métodos offline en ciertos pre-experimentos.

2. Metodología: El estimador Middle-In-Difference (MID)

Para abordar la falta de correlación en las pruebas A/B, los autores proponen un nuevo estimador llamado Middle-In-Difference (MID). La idea central es inducir intencionalmente una correlación positiva dentro del marco de las pruebas A/B mediante la introducción de un hipotético algoritmo intermedio ($\pi_M$).

Proceso de estimación paso a paso:
En lugar de comparar directamente el Algoritmo A ($\pi_A$) con el Algoritmo B ($\pi_B$), el MID descompone la diferencia de rendimiento en dos pasos:

1. Estimar la diferencia entre $\pi_A$ y $\pi_M$ utilizando los datos de registro recolectados de $\pi_A$ ($D_A$).
2. Estimar la diferencia entre $\pi_M$ y $\pi_B$ utilizando los datos de registro recolectados de $\pi_B$ ($D_B$).

El estimador final es la suma de estas dos diferencias:
$$\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 reducción de la varianza:

• Correlación inducida: Debido a que el primer término utiliza datos compartidos $D_A$ para estimar tanto $\pi_A$ como $\pi_M$, y el segundo término utiliza $D_B$ para $\pi_M$ y $\pi_B$, se inducen correlaciones positivas dentro de cada paso. Esto reduce la varianza de los términos de diferencia individuales.
• Algoritmo intermedio óptimo: Los autores derivan el algoritmo intermedio óptimo $\pi_M^*$ que minimiza la varianza del estimador. La política óptima se define como la media armónica de las 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 diseño asegura que $\pi_M$ sea altamente similar tanto a $\pi_A$ como a $\pi_B$, mitigando la "explosión de varianza" que suele verse en la evaluación offline cuando se comparan algoritmos disímiles (un modo de falla común del IPS estándar).

Propiedades teóricas:

• Insesgadez: Los autores demuestran que si el algoritmo intermedio cumple la condición de que solo selecciona acciones donde al menos uno de los algoritmos originales tiene una probabilidad no nula, el estimador permanece insesgado.
• Comparación de varianza: El análisis teórico demuestra que el término de recompensa de la varianza de MID es estrictamente menor o igual al del estimador AVG estándar. Además, a diferencia del IPS estándar, MID evita la explosión de varianza de $1/\pi_A$ cuando la similitud entre algoritmos es baja, porque las comparaciones intermedias involucran políticas similares.

3. Contribuciones clave

1. Perspectiva estadística: El artículo aclara que el estimador AVG estándar en las pruebas A/B no es necesariamente óptimo para la selección de algoritmos porque no logra explotar los beneficios de reducción de varianza de la correlación positiva entre estimadores.
2. Nuevo estimador (MID): Los autores proponen el estimador MID, que induce intencionalmente una correlación positiva mediante un algoritmo intermedio hipotético y una estimación por pasos, logrando tasas de error de selección más bajas que tanto las pruebas A/B estándar (AVG) como la evaluación offline (IPS).
3. Derivación teórica: El documento deriva el algoritmo intermedio óptimo para minimizar la varianza y proporciona un análisis de sesgo-varianza que muestra por qué MID supera a los métodos existentes.
4. Validación empírica: Utilizando datos de recomendación de video del mundo real (KuaiRec), los autores demuestran que MID logra consistentemente menores tasas de error de selección en diversos entornos.

4. Resultados experimentales

Los autores realizaron experimentos utilizando el conjunto de datos KuaiRec, un conjunto de datos de recomendación de video totalmente observado que permite el cálculo del rendimiento real de los algoritmos. Simularon un entorno de pruebas A/B con tamaños de muestra y similitudes de algoritmos variables.

• Eficiencia de muestreo: MID logró la misma tasa de error de selección que los métodos existentes (AVG e IPS) utilizando solo la mitad o un cuarto del tamaño de muestra de las pruebas A/B. Por ejemplo, mientras que AVG requería de 350 a 400 muestras para alcanzar una tasa de error del 5%, MID logró lo mismo con 100 a 200 muestras.
• Robustez a la similitud:
  • En escenarios de alta similitud, MID superó a IPS (que suele tener dificultades con la varianza en entornos offline) y a AVG.
  • En escenarios de baja similitud, donde IPS sufre una explosión de varianza debido al pesaje de importancia, MID se mantuvo estable y superó tanto a IPS como a AVG.
• Verificación del mecanismo: Los diagramas de dispersión de las estimaciones confirmaron que MID induce con éxito una correlación positiva entre los estimadores paso a paso, lo que resulta en una distribución más ajustada de la estimación de la diferencia final en comparación con la distribución circular (no correlacionada) de AVG. Esta dispersión más ajustada se correlaciona directamente con una reducción en los errores críticos de selección.

5. Significado y afirmaciones

El artículo afirma que el estimador MID propuesto mejora fundamentalmente la eficiencia y la precisión de las pruebas A/B para la selección de algoritmos. Al tomar prestado el mecanismo estadístico de la evaluación offline (datos compartidos que inducen correlación) y aplicarlo dentro del marco de las pruebas A/B mediante un algoritmo intermedio hipotético, MID supera las limitaciones tanto de las pruebas A/B tradicionales (alta varianza debido a la independencia) como de la evaluación offline (inestabilidad debido a la baja similitud o falta de nuevos datos).

Los autores enfatizan que este enfoque permite a las organizaciones tomar decisiones de selección de algoritmos más precisas con significativamente menos usuarios o duraciones de experimento más cortas, reduciendo el costo y el riesgo asociados con la experimentación en línea. El trabajo sugiere que el "estándar de oro" de las pruebas A/B puede mejorarse no abandonándolo, sino refinando la técnica de estimación para aprovechar las correlaciones estadísticas que anteriormente no se explotaban en entornos en línea.