Thompson Sampling: o algoritmo por trás dos bandits modernos

Thompson Sampling é o algoritmo bayesiano que a maioria dos multi-armed bandits de produção usa para decidir, visitante a visitante, para qual variação mandar o próximo clique. Em vez de fixar a divisão de tráfego no início e só analisar no fim, como um teste A/B clássico, ele sorteia um valor da crença atual sobre cada braço e manda o visitante para quem sorteou o maior valor, atualizando essa crença a cada resultado observado. Este guia explica a mecânica por trás do sorteio (a distribuição Beta e a atualização conjugada), mostra a matemática passo a passo com um exemplo de três variações e números reais, calculados pelo mesmo motor bayesiano que já roda neste blog, e diz com clareza quando essa técnica vale mais que um teste A/B com significância formal, e quando não vale.

O problema que o Thompson Sampling resolve: exploração x explotação

Todo bandit multi-braço precisa equilibrar duas forças opostas. Explorar é gastar tráfego em braços sobre os quais ainda existe pouca certeza, para aprender mais sobre eles. Explotar é concentrar tráfego no braço que, com a informação disponível até agora, parece o melhor. Um algoritmo que só explora nunca converge e desperdiça conversão indefinidamente; um algoritmo que só explota corre o risco de travar cedo demais numa escolha errada, porque os primeiros dados de qualquer braço são ruidosos.

Existem três famílias clássicas de resposta a esse problema, cada uma com uma filosofia diferente:

• Epsilon-greedy reserva uma fatia fixa e pequena do tráfego (o epsilon, ε) para exploração aleatória entre todos os braços, e manda o resto sempre para o braço que parece melhor agora. É simples, mas explora do mesmo jeito o tempo todo, gastando os mesmos ε% em braços já claramente ruins depois de milhares de visitantes.
• UCB (Upper Confidence Bound) soma, à taxa estimada de cada braço, um bônus de otimismo proporcional à incerteza sobre ele, e escolhe sempre o maior valor combinado. O bônus encolhe conforme mais dados chegam, então a exploração diminui sozinha, sem precisar de um parâmetro fixo como o ε.
• Thompson Sampling troca o cálculo determinístico de um bônus por um sorteio genuinamente aleatório da distribuição de crença de cada braço, o assunto deste guia.

A diferença central entre os três aparece na forma como a exploração diminui ao longo do teste. No epsilon-greedy ela fica constante (a menos que alguém decida reduzir ε manualmente); no UCB e no Thompson Sampling ela diminui sozinha, como consequência direta de mais dados reduzirem a incerteza de cada braço:

Como o Thompson Sampling decide, passo a passo

O mecanismo é mais simples do que parece à primeira vista, e não exige nenhum parâmetro manual como o ε do epsilon-greedy. Para cada braço do teste, o algoritmo mantém uma distribuição de probabilidade que representa a crença atual sobre a taxa de conversão real daquele braço, dado tudo o que já foi observado. Quando a métrica é uma conversão binária (converteu ou não converteu), essa distribuição de crença é uma Beta(α, β), o par conjugado natural da distribuição binomial.

O ciclo se repete a cada novo visitante:

Em termos simples: um braço com pouco dado tem uma Beta larga (muita incerteza), então às vezes o sorteio tira dele um valor bem alto mesmo que a média pareça mediana, e ele acaba recebendo tráfego de exploração de forma orgânica, sem que ninguém precise reservar uma fatia fixa para isso. Um braço com muitos dados e taxa claramente ruim tem uma Beta estreita e baixa, então quase nunca sorteia um valor alto o bastante para vencer, o que reduz o tráfego que vai para ele sem zerá-lo por completo.

A atualização conjugada: de Beta(1,1) a Beta(1+conversões, 1+não-conversões)

A parte que faz o Thompson Sampling ser barato de calcular (e por isso tão comum em produção) é que, para uma métrica de conversão binária, a atualização da crença tem uma fórmula fechada, sem precisar de nenhuma simulação pesada. Partindo de um prior uniforme Beta(1,1), que diz “antes de qualquer dado, toda taxa de conversão entre 0% e 100% é igualmente provável”, a regra de atualização depois de observar um número de visitantes e conversões é:

Essa é a mesma fórmula, com o mesmo prior Beta(1,1), que já roda por baixo da calculadora bayesiana deste blog. O motivo de ela ser tão simples é a propriedade de conjugação: quando o prior é Beta e a observação é binomial (converteu ou não), a posterior continua sendo Beta, então basta somar conversões ao parâmetro α e não-conversões ao parâmetro β. Não há integração numérica pesada nem simulação por trás dessa etapa específica, só uma soma.

Um exemplo numérico passo a passo: três variações, um round de tráfego

Para sair da teoria, vamos rodar a conta com números reais. Imagine uma landing page rodando um teste com três variações (A, B e C) sob Thompson Sampling. No início do teste, sem nenhum dado, todos os três braços partem do mesmo prior uniforme Beta(1,1), 33% de chance de tráfego para cada um. Depois de um primeiro round de tráfego com 800 visitantes em cada braço, os resultados observados foram:

Braço	Visitantes	Conversões	Taxa observada
A	800	40	5,00%
B	800	56	7,00%
C	800	32	4,00%

Aplicando a fórmula de atualização (Beta(1+conversões, 1+visitantes−conversões)) a cada braço:

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

A média de uma distribuição Beta(α, β) é α ÷ (α+β), e o desvio padrão é a raiz quadrada de [α·β ÷ ((α+β)²·(α+β+1))]. Calculando os dois para cada braço:

Braço	Posterior	Média posterior	Desvio padrão
A	Beta(41, 761)	5,11%	0,78%
B	Beta(57, 745)	7,11%	0,91%
C	Beta(33, 769)	4,11%	0,70%

Repare no padrão: quanto maior a distância entre as médias e menor a sobreposição das curvas, mais previsível fica qual braço vence o sorteio na rodada seguinte, e é exatamente esse mecanismo, sem nenhum parâmetro manual, que empurra tráfego crescente para B a partir daqui. Ainda assim, A e C continuam recebendo alguma fatia de tráfego, porque suas distribuições, embora mais baixas, ainda têm uma cauda que ocasionalmente sorteia um valor competitivo, o que é a exploração residual que mantém o algoritmo honesto caso B tenha tido, por acaso, uma rodada de sorte.

Cheque a matemática na calculadora bayesiana

A posterior de cada braço no Thompson Sampling é o mesmo objeto matemático que uma calculadora bayesiana de teste A/B usa para responder “qual a probabilidade de B ser melhor que A”. Para comparar o braço B com o braço A do exemplo acima, insira os números da tabela (A: 800 visitantes, 40 conversões; B: 800 visitantes, 56 conversões) na calculadora abaixo:

A (controle)

VisitantesConversões

B (variação)

VisitantesConversões

-probabilidade de B vencer A

Taxa de A (posterior)-

Taxa de B (posterior)-

Probabilidade de A vencer-

Risco ao escolher B (perda esperada)-

Melhora relativa (médias)-

Modelo Beta-Binomial com prior uniforme Beta(1,1) e intervalo de credibilidade de 95%. Cálculo determinístico, recalcula ao vivo.

Rodando esses números no mesmo motor bayesiano que alimenta a calculadora (Beta-Binomial conjugado, prior Beta(1,1), intervalo de credibilidade de 95%), o resultado é: taxa posterior de A em 5,11% (intervalo de credibilidade de 3,70% a 6,74%), taxa posterior de B em 7,11% (intervalo de 5,43% a 8,98%), probabilidade de B vencer A de 95,34%, melhora relativa das médias de +39,0%, e um risco (perda esperada) de apenas 0,02 ponto percentual ao decidir por B contra 2,02 pontos percentuais ao decidir por A. Comparando B contra C nos mesmos moldes (C: 800 visitantes, 32 conversões), a probabilidade de B vencer C sobe para 99,57%, coerente com a distância ainda maior entre as duas curvas na figura acima.

Esse é o ponto de conexão entre as duas técnicas: um teste A/B bayesiano roda essa conta uma vez, no fim do teste, para relatar um veredito. O Thompson Sampling roda o sorteio equivalente a cada visitante, durante todo o teste, para decidir tráfego em tempo real. A matemática de fundo é a mesma; o que muda é a frequência e o propósito do cálculo.

Por que o Thompson Sampling converge mais rápido que o epsilon-greedy

“Converge mais rápido” quer dizer, aqui, que o algoritmo perde menos conversão possível durante o próprio processo de aprendizado, o chamado regret (arrependimento acumulado). A razão estrutural para essa vantagem está em como cada método decide quanto explorar a cada momento:

Critério	Epsilon-greedy	UCB	Thompson Sampling
Como decide a exploração	Fatia fixa (ε) do tráfego, sempre aleatória entre os braços	Bônus de otimismo somado à taxa estimada, maior quanto menos dado houver	Sorteio aleatório da distribuição de crença de cada braço
A exploração diminui sozinha com mais dados?	Não, ε continua igual a menos que alguém reduza manualmente	Sim, o bônus encolhe conforme a incerteza cai	Sim, a distribuição fica mais estreita conforme a incerteza cai
Precisa de parâmetro manual	Sim, o valor de ε (e, se usar epsilon decrescente, também a taxa de decaimento)	Não, o bônus é calculado a partir dos próprios dados	Não, o prior é o único ajuste, e um prior uniforme já funciona bem na maioria dos casos
Onde desperdiça mais tráfego	Em braços já claramente ruins, depois de muitos dados	Menos que o epsilon-greedy, mas o bônus é uma aproximação determinística da incerteza	Tende a desperdiçar menos, porque a variância real de cada braço entra direto no sorteio

O epsilon-greedy trata a incerteza como um problema de “quanto tempo eu devo explorar”, resolvido com um número fixo escolhido de antemão. O Thompson Sampling trata a incerteza como parte da própria distribuição de cada braço, então a quantidade de exploração se ajusta automaticamente: braços recém-chegados exploram muito (distribuição larga), braços já bem estabelecidos exploram pouco (distribuição estreita), sem que ninguém precise decidir isso à mão. É essa auto-regulação, documentada em avaliações empíricas como a de Chapelle & Li (2011), que costuma dar ao Thompson Sampling um regret acumulado menor do que o do epsilon-greedy no mesmo cenário.

Quando usar Thompson Sampling em vez de um teste A/B clássico (e quando não usar)

A pergunta certa não é “qual técnica é mais moderna”, é “o que a decisão específica exige”. Thompson Sampling tende a valer mais quando:

• O custo de mostrar a variação perdedora é alto e imediato, como em preço ou numa oferta, onde cada visitante na variação ruim é uma venda potencialmente perdida agora, não só um dado estatístico a mais.
• A decisão é de otimização contínua, sem um marco único de “fim do teste”: uma manchete de home page ou um algoritmo de recomendação que precisa se adaptar sem parar se encaixa melhor num bandit rodando continuamente.
• Existem muitos braços (A/B/n com várias variações) e não há tráfego de sobra para dar a todos uma fatia igual até o fim; o Thompson Sampling já reduz tráfego dos braços fracos desde cedo.

O teste A/B clássico continua sendo a ferramenta certa quando:

• Você precisa de um veredito que aguenta ser defendido formalmente, com valor-p ou intervalo de confiança, para um relatório, um investidor, ou uma decisão de negócio que será citada depois. Thompson Sampling não gera esse tipo de significância estatística no sentido clássico.
• A mudança precisa ser analisada por segmento depois (mobile x desktop, por canal de aquisição), o que exige uma alocação de tráfego estável e comparável, exatamente o que um bandit, ao mudar a alocação continuamente, dificulta.
• A decisão é uma auditoria ou uma comparação justa e documentada entre exatamente duas versões, onde qualquer desvio da divisão combinada precisa de justificativa registrada. Uma alocação que muda sozinha ao longo do teste é mais difícil de defender nesse contexto do que uma divisão fixa.

Muitas operações maduras usam as duas coisas em sequência, como já cobrimos no guia de bandit x teste A/B: teste A/B para validar formalmente que uma mudança funciona, Thompson Sampling para otimizar continuamente entre variações já validadas, onde a pergunta deixou de ser “isso funciona?” e passou a ser “qual delas funciona melhor, sempre?”.

Faça isso automático na Donnu

Você acabou de ver a mecânica inteira por trás do Thompson Sampling: a posterior Beta de cada braço, a atualização conjugada que soma conversões e não-conversões ao prior, o sorteio que decide o próximo visitante, e por que essa auto-regulação da exploração costuma vencer um epsilon fixo. A Donnu A/B já roda hoje sobre esse mesmo motor bayesiano nativo, a mesma matemática Beta-Binomial que declara um vencedor honesto num teste A/B clássico é a base que um bandit como o Thompson Sampling usa para otimizar continuamente. Você não precisa escolher a ferramenta certa às cegas, comece pela estatística que os dois cenários já exigem.

Comece um teste grátis de 14 dias e rode a sua própria comparação bayesiana sobre o seu tráfego real.

Leia também o guia completo de multi-armed bandits x teste A/B, a peça-irmã sobre bandit contextual explicado para quando o vencedor muda por perfil de visitante, e o guia de significância estatística em testes A/B para a base frequentista que complementa esta leitura bayesiana.

Referências

• 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. O artigo original que dá nome à 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 (glossário) e Run a multi-armed bandit (MAB) optimization. optimizely.com/optimization-glossary/multi-armed-bandit.
• Netflix Technology Blog. Artwork Personalization at Netflix (descreve o uso de bandits para escolher imagens de capa personalizadas). netflixtechblog.com.