Amostragem de Thompson (Thompson Sampling)

Visão geral

Amostragem de Thompson (Thompson Sampling, TS) é uma estratégia bayesiana de exploração para os problemas de bandido de múltiplos braços (multi-armed bandit) e bandido contextual (contextual bandit). A cada etapa de decisão, ela:

  1. Mantém uma distribuição posterior sobre os parâmetros desconhecidos do modelo de recompensa para cada ação (braço).
  2. Amostra um conjunto plausível de parâmetros a partir dessas posteriores.
  3. Escolhe a ação que parece melhor sob os parâmetros amostrados (isto é, age de forma gulosa na amostra).

Essa regra simples de “amostrar e depois ser guloso” produz um comportamento poderoso conhecido como casamento de probabilidade (probability matching): ações são escolhidas na proporção da probabilidade de serem ótimas sob a posterior atual.

A amostragem de Thompson é amplamente usada em experimentação online e personalização porque é:

  • Estatisticamente eficiente (frequentemente com arrependimento quase ótimo),
  • Fácil de implementar com priors conjugadas,
  • Naturalmente equilibra exploração e exploração de forma oportunista sem cronogramas ad-hoc.

Para contexto sobre o cenário do problema, veja Bandidos de Múltiplos Braços e Bandidos Contextuais.

Intuição central: explorar amostrando a incerteza

Suponha que você esteja escolhendo entre múltiplas variantes de um site. No início, você tem poucos dados, então está incerto sobre a verdadeira taxa de conversão de cada variante. A amostragem de Thompson captura essa incerteza de forma explícita:

  • Braços com alta recompensa estimada tendem a ser escolhidos com frequência porque parâmetros amostrados muitas vezes os fazem parecer melhores.
  • Braços com alta incerteza também são escolhidos às vezes porque amostras ocasionais os fazem parecer surpreendentemente bons — isso é exploração “de graça”, guiada pela variância da posterior, em vez de uma regra de exploração separada.

Uma intuição-chave é:

A amostragem de Thompson explora na proporção de quão plausível é que uma ação seja ótima.

Isso difere de abordagens de “otimismo” (como UCB) que escolhem ações com base em um limite superior de confiança; a TS, em vez disso, randomiza de acordo com crenças posteriores.

Configuração formal de bandidos e algoritmo

Modelo de bandido de múltiplos braços

Em um bandido com (K) braços, em cada instante (t = 1,2,\dots):

  • Você escolhe uma ação (a_t \in {1,\dots,K}).
  • Você observa uma recompensa (r_t) extraída de uma distribuição desconhecida associada àquele braço.

Uma suposição comum de modelagem é que cada braço (i) tem um parâmetro desconhecido (\theta_i), e as recompensas vêm de uma verossimilhança (p(r \mid \theta_i)). A amostragem de Thompson mantém uma posterior (p(\theta_i \mid \mathcal{D}_t)) dado o conjunto de dados (\mathcal{D}_t).

Regra da amostragem de Thompson (amostragem da posterior)

Em cada rodada:

  1. Amostre (\tilde{\theta}_i \sim p(\theta_i \mid \mathcal{D}_t)) para cada braço (i).
  2. Escolha (a_t = \arg\max_i \mathbb{E}[r \mid \tilde{\theta}_i]) (ou diretamente a média amostrada).
  3. Observe (r_t) e atualize a posterior do braço escolhido.

Pseudocódigo

Initialize priors p(θ_i) for i = 1..K
for t = 1..T:
    for each arm i:
        sample θ̃_i ~ p(θ_i | D_t)
        compute sampled value v_i = E[r | θ̃_i]
    choose a_t = argmax_i v_i
    observe reward r_t
    update posterior p(θ_{a_t} | D_{t+1})

O algoritmo é extremamente geral: o principal requisito é conseguir amostrar da posterior (de forma exata ou aproximada).

Implementações com modelos conjugados (comuns na prática)

Em muitas aplicações de bandidos, você pode escolher uma verossimilhança e uma prior que formem um par conjugado (conjugate pair), tornando as atualizações da posterior e a amostragem baratas e exatas. (Veja também Inferência Bayesiana e Priori Conjugadas.)

Amostragem de Thompson Beta–Bernoulli (recompensas binárias)

Este é o arranjo clássico para eventos de conversão: (r \in {0,1}).

  • Verossimilhança: (r \mid p \sim \mathrm{Bernoulli}(p))
  • Priori: (p \sim \mathrm{Beta}(\alpha, \beta))
  • Posterior após observar (s) sucessos e (f) falhas: [ p \mid \mathcal{D} \sim \mathrm{Beta}(\alpha + s, \beta + f) ]

Regra de decisão: amostre (\tilde{p}_i \sim \mathrm{Beta}(\alpha_i, \beta_i)) e escolha o braço com maior (\tilde{p}_i).

Interpretação da priori: (\alpha-1) e (\beta-1) se comportam como pseudo-contagens de sucessos e falhas. Uma priori “leve” comum é (\mathrm{Beta}(1,1)) (uniforme), ou (\mathrm{Beta}(0.5,0.5)) (priori de Jeffreys) para um pouco mais de massa perto de 0 e 1.

Exemplo prático (teste A/B/n)

Você tem 3 variantes (A, B, C). Cada vez que um usuário chega, escolha uma variante e observe se ele converte. A TS automaticamente desloca tráfego para variantes melhores enquanto ainda explora as incertas.

Exemplo mínimo em Python

import numpy as np

rng = np.random.default_rng(0)

K = 3
alpha = np.ones(K)  # Beta(1,1) priors
beta  = np.ones(K)

def choose_arm(alpha, beta):
    samples = rng.beta(alpha, beta)
    return int(np.argmax(samples))

def update(alpha, beta, arm, reward):
    # reward is 0 or 1
    alpha[arm] += reward
    beta[arm]  += 1 - reward

# Simulated true conversion rates for demo
p_true = np.array([0.03, 0.05, 0.04])

for t in range(10_000):
    a = choose_arm(alpha, beta)
    r = 1 if rng.random() < p_true[a] else 0
    update(alpha, beta, a, r)

posterior_means = alpha / (alpha + beta)
print("Posterior means:", posterior_means)
print("Chosen best arm:", int(np.argmax(posterior_means)))

Recompensas gaussianas com variância conhecida (Normal–Normal)

Para recompensas de valor real (por exemplo, receita), um modelo comum é:

  • Verossimilhança: (r \mid \mu \sim \mathcal{N}(\mu, \sigma^2)), com (\sigma^2) conhecido
  • Priori: (\mu \sim \mathcal{N}(\mu_0, \tau_0^2))

A posterior permanece gaussiana: [ \tau_n^2 = \left(\frac{1}{\tau_0^2} + \frac{n}{\sigma^2}\right)^{-1}, \quad \mu_n = \tau_n^2\left(\frac{\mu_0}{\tau_0^2} + \frac{n\bar{r}}{\sigma^2}\right) ] onde (n) é o número de puxadas daquele braço e (\bar{r}) é a média amostral.

Regra de decisão: amostre (\tilde{\mu}i \sim \mathcal{N}(\mu{n,i}, \tau_{n,i}^2)) e escolha o braço com maior (\tilde{\mu}_i).

Dica: se sua recompensa é limitada (por exemplo, em ([0,1])), um modelo gaussiano ainda pode funcionar, mas pode ficar mal calibrado nas caudas; Beta-Bernoulli ou outros modelos limitados podem ser mais fiéis.

Recompensas gaussianas com variância desconhecida (Normal–Inversa-Gama)

Se (\sigma^2) é desconhecido, uma escolha conjugada é:

  • ((\mu, \sigma^2) \sim \text{Normal-Inverse-Gamma})

Então você pode amostrar (\sigma^2) e (\mu) da posterior e proceder como de costume. Isso é mais robusto quando o ruído da recompensa difere entre braços, mas as atualizações são um pouco mais envolvidas.

Outros pares conjugados comuns

  • Contagens: verossimilhança Poisson com priori Gama (Gama–Poisson) para contagens de eventos por unidade de tempo.
  • Resultados categóricos: verossimilhança multinomial com priori Dirichlet (Dirichlet–Multinomial).

Eles são úteis quando a “recompensa” não é escalar, mas ainda pode ser mapeada para uma utilidade (por exemplo, categorias ponderadas).

Amostragem de Thompson para bandidos contextuais

Em Bandidos Contextuais, cada rodada tem um contexto (x_t) (atributos sobre o usuário/requisição/item). Cada ação (a) tem uma recompensa esperada que depende de (x_t). A amostragem de Thompson se generaliza naturalmente: manter uma posterior sobre os parâmetros do modelo e amostrar um modelo a cada rodada.

Amostragem de Thompson linear (regressão linear bayesiana)

Um modelo padrão é: [ r_t = x_{t,a_t}^\top \theta + \varepsilon_t,\quad \varepsilon_t \sim \mathcal{N}(0, \sigma^2) ] onde (x_{t,a}\in\mathbb{R}^d) são atributos para a ação (a) no tempo (t).

Assuma uma priori gaussiana: [ \theta \sim \mathcal{N}(0, \lambda^{-1} I) ]

A posterior é gaussiana: [ \Sigma_t = \left(\lambda I + \frac{1}{\sigma^2}\sum_{s \le t} x_s x_s^\top\right)^{-1},\quad \mu_t = \Sigma_t \left(\frac{1}{\sigma^2}\sum_{s \le t} x_s r_s\right) ]

No momento da decisão:

  1. Amostre (\tilde{\theta} \sim \mathcal{N}(\mu_t, \Sigma_t))
  2. Escolha (a_t = \arg\max_a x_{t,a}^\top \tilde{\theta})

Isso é frequentemente chamado de LinTS e é um dos principais “cavalos de batalha” em personalização e recomendação quando os atributos são razoavelmente bem modelados de forma linear.

Esboço mínimo em Python (LinTS)

import numpy as np

rng = np.random.default_rng(0)

d = 5
lam = 1.0
sigma2 = 1.0

A = lam * np.eye(d)     # precision-like matrix
b = np.zeros(d)

def sample_theta(A, b):
    # Posterior: theta ~ N(mu, Sigma) where Sigma = inv(A), mu = inv(A) b
    Sigma = np.linalg.inv(A)
    mu = Sigma @ b
    return rng.multivariate_normal(mu, Sigma)

def update(A, b, x, r):
    # With sigma2=1 for simplicity; otherwise scale by 1/sigma2
    A += np.outer(x, x)
    b += x * r

# Example decision step:
# Given a set of action feature vectors X_actions: shape (K, d)
K = 10
X_actions = rng.normal(size=(K, d))

theta_tilde = sample_theta(A, b)
a = int(np.argmax(X_actions @ theta_tilde))
# observe reward r, then update(A, b, X_actions[a], r)

Nota de engenharia: em produção, raramente você inverte matrizes diretamente; use atualizações via fatoração de Cholesky ou mantenha (A^{-1}) via Sherman–Morrison quando for estável.

Amostragem de Thompson contextual logística (binária)

Para recompensas binárias com contexto, um modelo comum é a regressão logística (logistic regression): [ \Pr(r=1 \mid x,a) = \sigma(x^\top \theta) ] Não há priori conjugada, então posteriores exatas são intratáveis. Aproximações comuns:

  • Aproximação de Laplace (Laplace approximation) (aproximar a posterior como gaussiana ao redor do MAP)
  • Inferência variacional (variational inference) (aproximar a posterior com uma família tratável), veja Inferência Variacional
  • Amostragem MCMC (MCMC sampling) para maior fidelidade, veja Monte Carlo via Cadeias de Markov (Markov Chain Monte Carlo, MCMC)
  • Métodos com bootstrap / comitês (bootstrapped / ensemble methods) como proxy prático (veja “Variantes” abaixo)

Essas aproximações preservam o padrão da TS: amostrar um vetor de parâmetros, pontuar ações, escolher a melhor sob a amostra.

Arrependimento e fundamentos teóricos

A medida de desempenho padrão para bandidos é o arrependimento (regret): a lacuna cumulativa de recompensa entre o algoritmo e sempre escolher a ação ótima.

Duas noções comuns:

  • Arrependimento frequentista (dependente do problema): arrependimento para um ambiente verdadeiro fixo.
  • Arrependimento bayesiano: arrependimento esperado quando os parâmetros verdadeiros são amostrados de uma priori.

A amostragem de Thompson é bem estudada e tem garantias fortes em muitos cenários:

  • Para bandidos de múltiplos braços clássicos com distribuições de recompensa bem comportadas, a TS alcança arrependimento logarítmico no tempo (T) (dependente do problema) e é assintoticamente ótima no sentido de igualar limites inferiores (por exemplo, resultados do tipo Lai–Robbins).
  • Para bandidos contextuais lineares (LinTS), limites de arrependimento escalam aproximadamente como [ \tilde{O}\left(d\sqrt{T}\right) ] sob suposições padrão (atributos limitados, ruído sub-gaussiano), comparáveis a algoritmos de bandido linear no estilo UCB.

O que torna a TS notável é que essas garantias fortes vêm com uma forma algorítmica muito simples e prática.

Considerações práticas

Escolha de priors (e por que isso importa)

Priors influenciam o comportamento inicial e podem evitar exploração patológica.

  • Priors fracamente informativas (por exemplo, Beta(1,1)) são padrões comuns.
  • Priors informativas podem ser valiosas quando você tem dados históricos ou conhecimento de domínio (por exemplo, taxas de conversão base conhecidas).
  • Priors excessivamente confiantes podem prejudicar o aprendizado ao suprimir exploração; em caso de dúvida, prefira priors com variância maior.

Em cenários contextuais, priors correspondem à força de regularização (por exemplo, (\lambda) na TS linear). Um (\lambda) maior encolhe coeficientes e tipicamente aumenta a incerteza no início.

Uma abordagem prática é Bayes empírico (empirical Bayes): ajustar hiperparâmetros da priori a partir de logs históricos, mas tenha cuidado com mudança de distribuição (dataset shift) e viés de seleção (veja Avaliação Off-Policy para armadilhas em dados de bandido registrados).

Escalonamento de recompensa e desajuste de modelo

A TS é tão bem calibrada quanto sua posterior.

  • Se você usa TS gaussiana em recompensas com cauda pesada (por exemplo, receita com picos ocasionais enormes), estimativas de variância da posterior podem ser enganosas.
  • Considere transformações (log-receita), verossimilhanças robustas ou modelos com caudas mais pesadas.
  • Para recompensas limitadas, a modelagem Beta-Bernoulli ou Beta-Binomial pode estar mais alinhada.

Desajuste de modelo não necessariamente quebra a TS, mas pode afetar a qualidade da exploração e o arrependimento.

Feedback atrasado e processamento em lotes

Em muitos sistemas reais (anúncios, marketplaces), recompensas chegam tarde.

Estratégias comuns:

  • Atualizações em lote (batched updates): amostrar usando a posterior do último lote concluído; atualizar após as recompensas do lote chegarem.
  • Tratamento de resultados pendentes: manter alocações “em voo”; alguns sistemas usam correções aproximadas ou evitam reutilizar braços incertos de forma agressiva até que o feedback chegue.

O processamento em lotes reduz overhead computacional, mas pode desacelerar a adaptação.

Não estacionariedade (distribuições de recompensa mudando)

Se as taxas de recompensa derivam ao longo do tempo, uma posterior estacionária ficará desatualizada. Correções comuns:

  • Atualizações por janela deslizante (sliding window) (usar apenas as últimas (W) observações)
  • Desconto exponencial (exponential discounting) (reduzir peso de dados antigos)
  • Detecção de ponto de mudança (change-point detection) (reinicializar ou adaptar priors quando mudanças são detectadas)

Essas técnicas trocam estabilidade por responsividade.

Restrições, segurança e regras de negócio

A TS “pura” maximiza recompensa esperada. Implantações reais frequentemente adicionam restrições:

  • Exposição mínima para certos braços (equidade, exigências contratuais)
  • Limites de risco (evitar ações com alta incerteza se a perda potencial for severa)
  • Guardrails (por exemplo, não exceder limites de taxa de erro)

Isso tipicamente é implementado filtrando ações viáveis antes de aplicar TS, ou otimizando um objetivo com restrições.

Escalabilidade

  • Muitos braços (não contextual): TS Beta-Bernoulli escala bem — armazene ((\alpha,\beta)) por braço; amostrar é barato.
  • Contextual com grande dimensão de atributos: TS linear exige atualizar uma matriz (d \times d) (ou sua fatoração). Para (d) grande, considere:
    • Aproximações diagonais ou de baixa ordem (low-rank)
    • Atributos aleatorizados online
    • Álgebra linear esparsa
  • Posteriores complexas (por exemplo, modelos neurais): inferência bayesiana exata não é viável; usam-se métodos aproximados (veja variantes abaixo).

Comparação com outras estratégias de exploração

Dentro de Bandidos de Múltiplos Braços, a TS é frequentemente comparada a:

  • ε-gulosa (ε-greedy): simples, mas pode desperdiçar exploração de maneira uniforme e requer ajuste de cronogramas de ε.
  • UCB (Limite Superior de Confiança — Upper Confidence Bound): otimismo determinístico; garantias fortes; pode ser mais conservador ou mais agressivo dependendo do ajuste e do raio de confiança.
  • Explorar e então comprometer (explore-then-commit): fácil, mas pode ser ineficiente se a aleatoriedade inicial induzir ao erro.

Por que a TS é popular na prática:

  • Ajuste mínimo (priors importam, mas não é necessário um cronograma explícito de exploração).
  • A randomização ajuda a evitar comportamentos determinísticos frágeis.
  • Frequentemente excelente desempenho empírico mesmo sob desajuste moderado de modelo.

Possível desvantagem:

  • Requer amostragem da posterior; para modelos complexos isso pode ser computacionalmente pesado ou aproximado.
  • O desempenho depende da calibração da posterior; estimativas ruins de incerteza podem prejudicar a exploração.

Aplicações

A amostragem de Thompson é uma ferramenta padrão em:

  • Testes A/B/n online e experimentação: aloca automaticamente mais tráfego para variantes melhores enquanto ainda aprende.
  • Publicidade e otimização de CTR: escolher criativos/lances; lidar com resultados atrasados com processamento em lotes.
  • Recomendações/personalização: TS contextual (frequentemente linear) para ranqueamento ou seleção de listas (slates) (às vezes com aproximações).
  • Ensaios clínicos / alocação adaptativa: atraente do ponto de vista ético porque tende a atribuir mais pacientes a tratamentos melhores à medida que a evidência se acumula (sujeito a restrições regulatórias/estatísticas).
  • Ajuste de sistemas: seleção adaptativa de configurações (por exemplo, políticas de cache, alocações de recursos).

Em muitas dessas aplicações, a TS fica entre métodos clássicos de bandido e Aprendizado por Reforço: ela lida com tomada de decisão sequencial sem dinâmicas de estado de longo horizonte.

Variantes e extensões

Amostragem de Thompson com bootstrap

Em vez de uma posterior bayesiana, mantenha um comitê (ensemble) treinado em reamostragens bootstrap dos dados; amostre um modelo por rodada. Isso pode aproximar o comportamento da TS e é popular quando:

  • Posteriores bayesianas são difíceis de computar,
  • Você já tem um pipeline de treinamento de ML para comitês.

Métodos no estilo Thompson com deep/neural

Para bandidos contextuais com atributos complexos (texto, imagens), profissionais às vezes usam:

  • Comitês de redes neurais,
  • Redes neurais bayesianas aproximadas,
  • Aproximações de Laplace sobre a última camada.

Esses métodos buscam recuperar exploração semelhante à TS ao representar incerteza, mas a calibração pode ser desafiadora.

Amostragem da Posterior para Aprendizado por Reforço (PSRL)

A amostragem de Thompson se generaliza para RL completo ao amostrar um MDP da posterior e seguir a política ótima no MDP amostrado por algum período. Isso é conceitualmente elegante, mas frequentemente computacionalmente exigente.

Resumo

A amostragem de Thompson é uma abordagem bayesiana, fundamentada e prática, para exploração em bandidos:

  • Manter uma posterior sobre parâmetros do modelo de recompensa.
  • Amostrar um modelo plausível a cada rodada.
  • Escolher a ação que é gulosa sob o modelo amostrado.

Com modelos conjugados como Beta–Bernoulli e Normal–Normal, ela é fácil de implementar e escala bem. Para bandidos contextuais, a amostragem de Thompson linear é um padrão comum com forte suporte teórico e bom desempenho empírico. Em cenários mais complexos, inferência aproximada (Laplace/VI/MCMC) ou proxies baseados em comitês podem reter grande parte do benefício da TS.

Para implantar TS de forma responsável, preste atenção à escolha da priori, calibração da posterior, feedback atrasado, não estacionariedade e quaisquer restrições exigidas pela aplicação.