Muestreo de Thompson: Algoritmo de Bandits

El muestreo de Thompson es el algoritmo bayesiano que la mayoría de los multi-armed bandits de producción usa para decidir, visitante a visitante, a qué variación mandar el próximo clic. En vez de fijar la división de tráfico al inicio y analizar solo al final, como un test A/B clásico, sortea un valor de la creencia actual sobre cada brazo y manda al visitante hacia el que sorteó el valor más alto, actualizando esa creencia con cada resultado observado. Esta guía explica la mecánica detrás del sorteo (la distribución Beta y la actualización conjugada), muestra la matemática paso a paso con un ejemplo de tres variaciones y números reales, calculados por el mismo motor bayesiano que ya corre en este blog, y dice con claridad cuándo esta técnica vale más que un test A/B con significancia formal, y cuándo no vale.

El problema que el muestreo de Thompson resuelve: exploración vs. explotación

Todo bandit multi-brazo necesita equilibrar dos fuerzas opuestas. Explorar es gastar tráfico en brazos sobre los que todavía hay poca certeza, para aprender más sobre ellos. Explotar es concentrar tráfico en el brazo que, con la información disponible hasta ahora, parece el mejor. Un algoritmo que solo explora nunca converge y desperdicia conversión indefinidamente; un algoritmo que solo explota corre el riesgo de atascarse demasiado pronto en una elección equivocada, porque los primeros datos de cualquier brazo son ruidosos.

Existen tres familias clásicas de respuesta a este problema, cada una con una filosofía diferente:

• Epsilon-greedy reserva una fracción fija y pequeña del tráfico (el epsilon, ε) para exploración aleatoria entre todos los brazos, y manda el resto siempre al brazo que parece mejor ahora. Es simple, pero explora del mismo modo todo el tiempo, gastando el mismo ε% en brazos ya claramente malos después de miles de visitantes.
• UCB (Upper Confidence Bound) suma, a la tasa estimada de cada brazo, un bono de optimismo proporcional a la incertidumbre sobre él, y elige siempre el mayor valor combinado. El bono se reduce a medida que llegan más datos, así que la exploración disminuye sola, sin necesitar un parámetro fijo como el ε.
• El muestreo de Thompson cambia el cálculo determinístico de un bono por un sorteo genuinamente aleatorio de la distribución de creencia de cada brazo, el tema de esta guía.

La diferencia central entre los tres aparece en la forma en que la exploración disminuye a lo largo del test. En epsilon-greedy se mantiene constante (a menos que alguien decida reducir ε manualmente); en UCB y en el muestreo de Thompson disminuye sola, como consecuencia directa de que más datos reducen la incertidumbre de cada brazo:

Cómo decide el muestreo de Thompson, paso a paso

El mecanismo es más simple de lo que parece a primera vista, y no exige ningún parámetro manual como el ε del epsilon-greedy. Para cada brazo del test, el algoritmo mantiene una distribución de probabilidad que representa la creencia actual sobre la tasa de conversión real de ese brazo, dado todo lo que ya se observó. Cuando la métrica es una conversión binaria (convirtió o no convirtió), esa distribución de creencia es una Beta(α, β), el par conjugado natural de la distribución binomial.

El ciclo se repite con cada nuevo visitante:

En términos simples: un brazo con poco dato tiene una Beta ancha (mucha incertidumbre), así que a veces el sorteo saca de él un valor bastante alto aunque el promedio parezca mediano, y termina recibiendo tráfico de exploración de forma orgánica, sin que nadie necesite reservar una fracción fija para eso. Un brazo con muchos datos y tasa claramente mala tiene una Beta estrecha y baja, así que casi nunca sortea un valor lo bastante alto como para ganar, lo que reduce el tráfico que va hacia él sin llevarlo a cero por completo.

La actualización conjugada: de Beta(1,1) a Beta(1+conversiones, 1+no conversiones)

La parte que hace que el muestreo de Thompson sea barato de calcular (y por eso tan común en producción) es que, para una métrica de conversión binaria, la actualización de la creencia tiene una fórmula cerrada, sin necesitar ninguna simulación pesada. Partiendo de un prior uniforme Beta(1,1), que dice “antes de cualquier dato, toda tasa de conversión entre 0% y 100% es igualmente probable”, la regla de actualización después de observar un número de visitantes y conversiones es:

Esa es la misma fórmula, con el mismo prior Beta(1,1), que ya corre por debajo de la calculadora bayesiana de este blog. El motivo de que sea tan simple es la propiedad de conjugación: cuando el prior es Beta y la observación es binomial (convirtió o no), la posterior sigue siendo Beta, así que basta sumar conversiones al parámetro α y no conversiones al parámetro β. No hay integración numérica pesada ni simulación detrás de este paso específico, solo una suma.

Un ejemplo numérico paso a paso: tres variaciones, una ronda de tráfico

Para salir de la teoría, vamos a correr la cuenta con números reales. Imagina una landing page corriendo un test con tres variaciones (A, B y C) bajo muestreo de Thompson. Al inicio del test, sin ningún dato, los tres brazos parten del mismo prior uniforme Beta(1,1), 33% de probabilidad de tráfico para cada uno. Después de una primera ronda de tráfico con 800 visitantes en cada brazo, los resultados observados fueron:

Brazo	Visitantes	Conversiones	Tasa observada
A	800	40	5,00%
B	800	56	7,00%
C	800	32	4,00%

Aplicando la fórmula de actualización (Beta(1+conversiones, 1+visitantes−conversiones)) a cada brazo:

• Brazo A: Beta(1+40, 1+800−40) = Beta(41, 761).
• Brazo B: Beta(1+56, 1+800−56) = Beta(57, 745).
• Brazo C: Beta(1+32, 1+800−32) = Beta(33, 769).

El promedio de una distribución Beta(α, β) es α ÷ (α+β), y la desviación estándar es la raíz cuadrada de [α·β ÷ ((α+β)²·(α+β+1))]. Calculando ambos para cada brazo:

Brazo	Posterior	Promedio posterior	Desviación estándar
A	Beta(41, 761)	5,11%	0,78%
B	Beta(57, 745)	7,11%	0,91%
C	Beta(33, 769)	4,11%	0,70%

Fíjate en el patrón: cuanto mayor la distancia entre los promedios y menor la superposición de las curvas, más previsible se vuelve qué brazo gana el sorteo en la siguiente ronda, y es exactamente ese mecanismo, sin ningún parámetro manual, el que empuja tráfico creciente hacia B a partir de aquí. Aun así, A y C siguen recibiendo alguna fracción de tráfico, porque sus distribuciones, aunque más bajas, todavía tienen una cola que ocasionalmente sortea un valor competitivo, lo que es la exploración residual que mantiene al algoritmo honesto por si B tuvo, por casualidad, una ronda de suerte.

Comprueba la matemática en la calculadora bayesiana

La posterior de cada brazo en el muestreo de Thompson es el mismo objeto matemático que una calculadora bayesiana de test A/B usa para responder “cuál es la probabilidad de que B sea mejor que A”. Para comparar el brazo B con el brazo A del ejemplo anterior, ingresa los números de la tabla (A: 800 visitantes, 40 conversiones; B: 800 visitantes, 56 conversiones) en la calculadora de abajo:

A (control)

VisitantesConversiones

B (variación)

VisitantesConversiones

-probabilidad de que B le gane a A

Tasa de A (posterior)-

Tasa de B (posterior)-

Probabilidad de que A gane-

Riesgo al elegir B (pérdida esperada)-

Mejora relativa (medias)-

Modelo Beta-Binomial con prior uniforme Beta(1,1) e intervalo de credibilidad del 95%. Cálculo determinístico, recalcula en vivo.

Corriendo estos números en el mismo motor bayesiano que alimenta la calculadora (Beta-Binomial conjugado, prior Beta(1,1), intervalo de credibilidad del 95%), el resultado es: tasa posterior de A en 5,11% (intervalo de credibilidad de 3,70% a 6,74%), tasa posterior de B en 7,11% (intervalo de 5,43% a 8,98%), probabilidad de que B le gane a A de 95,34%, mejora relativa de los promedios de +39,0%, y un riesgo (pérdida esperada) de apenas 0,02 punto porcentual al decidir por B contra 2,02 puntos porcentuales al decidir por A. Comparando B contra C bajo el mismo criterio (C: 800 visitantes, 32 conversiones), la probabilidad de que B le gane a C sube a 99,57%, coherente con la distancia todavía mayor entre las dos curvas en la figura anterior.

Ese es el punto de conexión entre las dos técnicas: un test A/B bayesiano corre esta cuenta una vez, al final del test, para reportar un veredicto. El muestreo de Thompson corre el sorteo equivalente con cada visitante, durante todo el test, para decidir tráfico en tiempo real. La matemática de fondo es la misma; lo que cambia es la frecuencia y el propósito del cálculo.

Por qué el muestreo de Thompson converge más rápido que epsilon-greedy

“Converge más rápido” quiere decir, aquí, que el algoritmo pierde menos conversión posible durante el propio proceso de aprendizaje, lo que se llama regret (arrepentimiento acumulado). La razón estructural de esta ventaja está en cómo cada método decide cuánto explorar en cada momento:

Criterio	Epsilon-greedy	UCB	Muestreo de Thompson
Cómo decide la exploración	Fracción fija (ε) del tráfico, siempre aleatoria entre los brazos	Bono de optimismo sumado a la tasa estimada, mayor cuanto menos dato haya	Sorteo aleatorio de la distribución de creencia de cada brazo
¿La exploración disminuye sola con más datos?	No, ε sigue igual a menos que alguien lo reduzca manualmente	Sí, el bono se reduce conforme baja la incertidumbre	Sí, la distribución se vuelve más estrecha conforme baja la incertidumbre
¿Necesita parámetro manual?	Sí, el valor de ε (y, si se usa epsilon decreciente, también la tasa de decaimiento)	No, el bono se calcula a partir de los propios datos	No, el prior es el único ajuste, y un prior uniforme ya funciona bien en la mayoría de los casos
Dónde desperdicia más tráfico	En brazos ya claramente malos, después de muchos datos	Menos que epsilon-greedy, pero el bono es una aproximación determinística de la incertidumbre	Tiende a desperdiciar menos, porque la varianza real de cada brazo entra directo en el sorteo

Epsilon-greedy trata la incertidumbre como un problema de “cuánto tiempo debo explorar”, resuelto con un número fijo elegido de antemano. El muestreo de Thompson trata la incertidumbre como parte de la propia distribución de cada brazo, así que la cantidad de exploración se ajusta automáticamente: brazos recién llegados exploran mucho (distribución ancha), brazos ya bien establecidos exploran poco (distribución estrecha), sin que nadie necesite decidirlo a mano. Es esta autorregulación, documentada en evaluaciones empíricas como la de Chapelle & Li (2011), la que suele darle al muestreo de Thompson un regret acumulado menor que el de epsilon-greedy en el mismo escenario.

Cuándo usar muestreo de Thompson en vez de un test A/B clásico (y cuándo no)

La pregunta correcta no es “qué técnica es más moderna”, es “qué exige la decisión específica”. El muestreo de Thompson tiende a valer más cuando:

• El costo de mostrar la variación perdedora es alto e inmediato, como en precio o en una oferta, donde cada visitante en la variación mala es una venta potencialmente perdida ahora, no solo un dato estadístico más.
• La decisión es de optimización continua, sin un hito único de “fin del test”: un titular de home page o un algoritmo de recomendación que necesita adaptarse sin parar encaja mejor en un bandit corriendo continuamente.
• Existen muchos brazos (A/B/n con varias variaciones) y no hay tráfico de sobra para darle a todos una fracción igual hasta el final; el muestreo de Thompson ya reduce el tráfico de los brazos débiles desde temprano.

El test A/B clásico sigue siendo la herramienta correcta cuando:

• Necesitas un veredicto que aguante ser defendido formalmente, con valor p o intervalo de confianza, para un informe, un inversor, o una decisión de negocio que será citada después. El muestreo de Thompson no genera ese tipo de significancia estadística en el sentido clásico.
• El cambio necesita analizarse por segmento después (móvil vs. escritorio, por canal de adquisición), lo que exige una asignación de tráfico estable y comparable, exactamente lo que un bandit, al cambiar la asignación continuamente, dificulta.
• La decisión es una auditoría o una comparación justa y documentada entre exactamente dos versiones, donde cualquier desviación de la división acordada necesita justificación registrada. Una asignación que cambia sola a lo largo del test es más difícil de defender en ese contexto que una división fija.

Muchas operaciones maduras usan las dos cosas en secuencia, como ya cubrimos en la guía de bandit vs. test A/B: test A/B para validar formalmente que un cambio funciona, muestreo de Thompson para optimizar continuamente entre variaciones ya validadas, donde la pregunta dejó de ser “¿esto funciona?” y pasó a ser “¿cuál de ellas funciona mejor, siempre?”.

Hazlo automático en Donnu

Acabas de ver la mecánica entera detrás del muestreo de Thompson: la posterior Beta de cada brazo, la actualización conjugada que suma conversiones y no conversiones al prior, el sorteo que decide el próximo visitante, y por qué esta autorregulación de la exploración suele vencer a un epsilon fijo. Donnu A/B ya corre hoy sobre ese mismo motor bayesiano nativo, la misma matemática Beta-Binomial que declara un ganador honesto en un test A/B clásico es la base que un bandit como el muestreo de Thompson usa para optimizar continuamente. No necesitas elegir la herramienta correcta a ciegas, empieza por la estadística que los dos escenarios ya exigen.

Comienza una prueba gratis de 14 días y corre tu propia comparación bayesiana sobre tu tráfico real.

Lee también la guía completa de multi-armed bandits vs. test A/B, la pieza hermana sobre bandit contextual explicado para cuando el ganador cambia según el perfil del visitante, y la guía de significancia estadística en tests A/B para la base frecuentista que complementa esta lectura bayesiana.

Referencias

• Thompson, W. R. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3/4), 285-294, 1933. El artículo original que le da nombre a la técnica. doi.org/10.2307/2332286.
• Chapelle, O. & Li, L. An Empirical Evaluation of Thompson Sampling. Advances in Neural Information Processing Systems (NeurIPS), 2011. proceedings.neurips.cc.
• Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I. & Wen, Z. A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning, 2018. arxiv.org/abs/1707.02038.
• Optimizely. Multi-armed bandit (glosario) y Run a multi-armed bandit (MAB) optimization. optimizely.com/optimization-glossary/multi-armed-bandit.
• Netflix Technology Blog. Artwork Personalization at Netflix (describe el uso de bandits para elegir imágenes de portada personalizadas). netflixtechblog.com.