Visión general

Apéndice (experimentos multi-armed bandit)

Datos teóricos y computacionales

En primer lugar, debe tener en cuenta que el término "multi-armed bandit" describe un problema para el cual se han propuesto distintas "soluciones". Si consulta un libro sobre aprendizaje por refuerzo, en la introducción encontrará distintos enfoques sobre los experimentos multi-armed bandit. Ello se debe a que la matemática que subyace tras el algoritmo multi-armed bandit es tan complicada que en la práctica se utilizan soluciones heurísticas aproximadas. Las dificultades matemáticas quedan claramente resumidas en una célebre cita de Peter Whittle (Whittle, 1979):

[El problema multi-armed bandit] se formuló durante la (Segunda) Guerra (Mundial) y los esfuerzos realizados para resolverlo debilitaron tanto la fuerza y la mente de los analistas aliados que se sugirió trasladarlo a Alemania como último instrumento de sabotaje intelectual.

Utilizamos una solución heurística conocida como muestreo de Thompson, o Probabilidad de coincidencia al azar, porque combina muchas de las mejores funciones de estos métodos heurísticos. Encontrará más información sobre esta técnica en [5] y puede obtener más detalles sobre sus propiedades matemáticas en [2], [3] y [4].

Probabilidades de la variación óptima

El muestreo de Thompson asigna sesiones a las variaciones proporcionalmente a las probabilidades que tiene cada variación de ser la mejor. Se trata de un cálculo bayesiano. θ = (θ1, θ2,..., θk) designa el vector de los porcentajes de conversiones de las variaciones 1, …, k. E y designa los datos observados hasta el momento en el experimento. Tomamos a "y" como un vector de resultados binomiales independientes y asumimos una distribución a priori uniforme independiente en θ. Ia(θ) señala al indicador del evento que la variación a es la óptima. Así pues, podemos escribir lo siguiente:

P(Ia) = ∫Ia(θ) p(θ|y) dθ

Esta integral puede resolverse en un modelo cerrado (aunque la solución de modelo cerrado requiere el uso de complicadas funciones especiales, como la función beta incompleta) o a través de la integración numérica. En cualquier caso, el cálculo acaba siendo rápidamente inestable, incluso con valores relativamente pequeños de y. No obstante, las probabilidades de encontrar la variación óptima pueden calcularse de forma estable mediante la simulación. Cada uno de los elementos de θ es una variable aleatoria independiente de la distribución beta. Simule una gran matriz que contenga extracciones de θ de las distribuciones beta relevantes, donde las filas de la matriz representan las extracciones aleatorias y las columnas, las variaciones k del experimento. Una estimación basada en el método de Monte Carlo sobre la probabilidad de que la variación "a" sea la óptima es la fracción empírica de filas en las que la variación a presentaba el mayor valor simulado. La probabilidad de que cada variación supere al original puede calcularse de forma similar.

Valor restante

La simulación que ofrece las probabilidades de obtener la variación óptima también puede ofrecer la distribución del valor restante en el experimento. El valor restante es la distribución posterior de (θmax-θ*)/θ*, donde θmax es el mayor valor de θ y θ* es el valor de θ de la variación que presenta más probabilidades de ser la óptima. Para ilustrar este cálculo, supongamos que tenemos tres variaciones con 20, 30 y 40 sesiones respectivamente, que han generado 12, 20 y 30 conversiones. Las probabilidades de ser la variación óptima son de aproximadamente un 0,09, un 0,20 y un 0,71. Las seis primeras extracciones de la simulación de Monte Carlo de θ pueden ser:

[,1] [,2] [,3]
[1,] 0,54 0,73 0,74
[2,] 0,55 0,66 0,73
[3,] 0,53 0,81 0,80
[4,] 0,57 0,50 0,65
[5,] 0,52 0,67 0,83
[6,] 0,65 0,84 063

Para calcular el valor fila por fila restamos el mayor elemento de la fila en cuestión del elemento de la columna 3 (porque la variación 3 es la que tiene más probabilidades de ser la óptima). En las dos primeras filas el valor es cero porque la mayor extracción se produce en la columna 3. En la tercera fila el valor es 0,01/0,80 porque la columna 2 es 0,01 más grande que la columna 3. Si seguimos bajando por cada fila, obtenemos una distribución de valores que podríamos representar en un histograma como en el panel izquierdo de la Figura A1. La variación 3 tiene un 71% de probabilidades de ser la mejor, por lo que el valor que se obtiene de alejarse de la variación 3 es cero en el 71% de los casos. El percentil 95 de la distribución del valor es el "posible valor restante" del experimento, que en este caso es de aproximadamente 0,16. La interpretación que puede hacerse de esta cifra es que "todavía no sabemos con certeza cuál es el porcentaje de conversiones de la variación 3, pero sea cual sea, una de las demás variaciones puede superarla en hasta un 16%".

En el panel derecho de la Figura A1 se muestra lo que le sucede a la distribución del valor restante a medida que avanza el experimento. Supongamos que cada variación tuviera 5 veces el tamaño de la muestra (es decir, 100, 150 y 200 sesiones), con 5 veces el número de conversiones (60, 100 y 150). Con tamaños de muestra más grandes, tenemos muchas más garantías respecto a los porcentajes de conversiones de las variaciones. Ahora, la variación 3 tiene aproximadamente un 95% de probabilidades de ser la variación óptima, de modo que el percentil 95 de la distribución del valor restante es cero.

Figura A1. Distribución del valor restante en un experimento. En cada caso, la línea vertical representa el percentil 95, o el posible valor restante.
¿Te ha sido útil este artículo?
¿Cómo podemos mejorar esta página?