Bandits de Múltiplos Braços (Multi-Armed Bandits)

Visão geral

Um bandido de múltiplos braços (multi-armed bandit, MAB) é um problema de decisão sequencial no qual um agente escolhe repetidamente entre (K) ações (chamadas de braços (arms)) e observa uma recompensa do braço escolhido. O desafio central é o trade-off entre exploração e explotação (exploration–exploitation trade-off):

Explotar: escolher o braço que atualmente parece melhor para obter alta recompensa agora.
Explorar: tentar braços menos amostrados para aprender se eles podem ser melhores no longo prazo.

Bandits se inserem em Aprendizado por Reforço (Reinforcement Learning), mas removem dinâmicas de estado de longo horizonte: cada decisão afeta o que você aprende, mas (na formulação mais simples) não afeta o estado subjacente do ambiente.

Aplicações típicas incluem testes A/B/n online, seleção de anúncios, recomendações, ensaios clínicos adaptativos e alocação de recursos — qualquer cenário em que você precisa aprender com feedback enquanto simultaneamente otimiza resultados.

O modelo central de bandido de múltiplos braços

Cenário e notação

Braços: (\mathcal{A} = {1,2,\dots,K})
Passos de tempo: (t = 1,2,\dots,T)
No tempo (t), o agente escolhe um braço (a_t \in \mathcal{A}) e observa uma recompensa (r_t).

No modelo de bandido estocástico (stochastic bandit) (a formulação clássica), cada braço (i) tem uma distribuição de recompensas desconhecida (D_i) com média (\mu_i = \mathbb{E}[r \mid a=i]). Quando você puxa o braço (i), observa uma amostra i.i.d. de (D_i).

Seja (i^* = \arg\max_i \mu_i) o braço ótimo com média (\mu^* = \max_i \mu_i).

Objetivo: maximizar recompensa, minimizar arrependimento

Uma medida padrão de desempenho é o arrependimento cumulativo (pseudo-) (cumulative (pseudo-)regret):

[ R_T = T\mu^* - \mathbb{E}\left[\sum_{t=1}^T r_t\right] ]

Intuitivamente: quanto de recompensa você perdeu em comparação com sempre puxar o melhor braço (que você não conhece inicialmente).

Uma quantidade-chave é a lacuna (gap) para cada braço subótimo (i):

[ \Delta_i = \mu^* - \mu_i ]

Limites de arrependimento frequentemente escalam com (\sum_{i:\Delta_i>0} \frac{\log T}{\Delta_i}) para algoritmos estocásticos ótimos: você explora braços subótimos apenas um número logarítmico de vezes.

Formulações centrais de bandits (o que “bandit” pode significar)

Bandidos de múltiplos braços aparecem em várias formulações intimamente relacionadas; saber em qual delas você está importa para escolha de algoritmo e garantias.

Bandidos estocásticos (recompensas i.i.d. por braço)

Este é o MAB “clássico”: cada braço tem uma distribuição fixa, independente ao longo do tempo.

Modelos comuns de recompensa:

Bandido Bernoulli (Bernoulli bandit): (r_t \in {0,1}) (clique/não clique, conversão/não conversão)
Bandido Gaussiano (Gaussian bandit): (r_t \in \mathbb{R}) com ruído Gaussiano (por exemplo, receita com ruído)
Recompensas limitadas (bounded rewards): (r_t \in [0,1]) (frequentemente assumidas na teoria)

A maioria das estratégias clássicas de exploração (ε-ganancioso, UCB, amostragem de Thompson) visa esse cenário.

Bandidos adversariais

As recompensas podem ser escolhidas por um adversário (ou serem altamente não estacionárias de forma “pior caso”). Você não pode assumir amostragem i.i.d. de uma distribuição fixa.

Aqui, o benchmark adequado costuma ser o arrependimento minimax (minimax regret), e algoritmos como EXP3 atingem arrependimento da ordem de:

[ R_T = O\left(\sqrt{TK\log K}\right) ]

Identificação do melhor braço (exploração pura)

Às vezes você se importa menos com a recompensa cumulativa durante o aprendizado e mais com identificar o melhor braço no final. A métrica passa a ser o arrependimento simples (simple regret):

[ r_{\text{simple}} = \mu^* - \mu_{\hat{i}} ]

onde (\hat{i}) é o braço que você recomenda após a exploração. Algoritmos aqui incluem Eliminação Sucessiva (Successive Elimination) e métodos de corrida (racing methods).

Além dos MABs básicos (brevemente)

Bandidos contextuais (contextual bandits) adicionam atributos (x_t) que mudam a cada interação (contexto do usuário), e a melhor ação depende de (x_t). Veja Bandidos Contextuais (Contextual Bandits).
Bandidos não estacionários (nonstationary bandits) permitem que (\mu_i(t)) derive; métodos de janela deslizante ou de ponto de mudança (change-point) são comuns.
Bandidos combinatórios (combinatorial bandits) escolhem subconjuntos de itens (por exemplo, recomendar um conjunto).

Este artigo foca em formulações centrais de MAB e estratégias clássicas de exploração para o caso não contextual.

Estratégias clássicas de exploração

1) Ganancioso e ε-ganancioso

Ganancioso (greedy) sempre escolhe o braço com a maior média empírica:

[ \hat{\mu}i(t) = \frac{1}{N_i(t)} \sum{s \le t: a_s=i} r_s ]

onde (N_i(t)) é quantas vezes o braço (i) foi puxado até o tempo (t).

O ganancioso é simples, mas pode ficar preso: ruído no início pode fazer um braço subótimo parecer o melhor para sempre.

ε-ganancioso (ε-greedy) corrige isso explorando com probabilidade (\varepsilon):

com probabilidade (1-\varepsilon): explotar (\arg\max_i \hat{\mu}_i(t))
com probabilidade (\varepsilon): explorar um braço aleatório

Variantes práticas:

ε decrescente (decaying ε) (por exemplo, (\varepsilon_t = \min(1, cK/t))) reduz a exploração ao longo do tempo.
Inicialização otimista (optimistic initialization) começa com (\hat{\mu}_i(0)) alto para incentivar exploração cedo (mais comum em cenários de recompensas determinísticas).

Prós:

Muito fácil de implementar e depurar
Funciona razoavelmente em muitos cenários de produto

Contras:

Teoria e desempenho frequentemente são mais fracos do que UCB/amostragem de Thompson
Exploração aleatória uniforme pode ser desperdício quando muitos braços são ruins

Pseudo-code (ε-greedy)

Initialize: pull each arm once to get initial estimates
For t = K+1 ... T:
  With prob ε:
    choose arm uniformly at random
  Else:
    choose arm argmax_i empirical_mean[i]
  Observe reward and update estimates

2) Explorar-Depois-Comprometer (Explore-Then-Commit, ETC)

Um baseline simples: explorar cada braço por um número fixo de puxadas (m), e então comprometer-se com o braço com melhor estimativa pelo restante do horizonte.

Fase de exploração: amostrar cada braço (m) vezes
Fase de comprometimento: escolher (\hat{i} = \arg\max_i \hat{\mu}_i) para sempre

Prós:

Operacionalmente simples, fácil de explicar a stakeholders
Às vezes é uma boa combinação quando você pode arcar com uma janela dedicada de exploração

Contras:

Não é adaptativo: se evidências se acumulam cedo, ainda assim desperdiça exploração
Se o horizonte (T) é desconhecido ou muda, escolher (m) é difícil

ETC é conceitualmente próximo de testes A/B tradicionais (alocação fixa e depois decisão), mas algoritmos de bandit normalmente intercalam exploração e explotação de forma mais eficiente.

3) Limite Superior de Confiança (Upper Confidence Bound, UCB): “otimismo diante da incerteza (optimism in the face of uncertainty)”

UCB escolhe o braço com o maior limite superior de confiança (upper confidence bound) para sua recompensa média:

[ a_t = \arg\max_i \left(\hat{\mu}_i(t) + b_i(t)\right) ]

onde (b_i(t)) é um termo de bônus que diminui à medida que o braço é mais amostrado. Uma escolha clássica (UCB1) para recompensas limitadas é:

[ b_i(t) = \sqrt{\frac{2\log t}{N_i(t)}} ]

Interpretação:

Se um braço tem alta média estimada, ele é atraente.
Se um braço é incerto (pequeno (N_i(t))), ele ganha um “bônus de otimismo”, forçando exploração.

Por que UCB é importante

Tem garantias teóricas fortes em bandidos estocásticos.
O arrependimento é logarítmico em (T) (dependente das lacunas) e quase ótimo sob suposições padrão.

Pseudo-code (UCB1)

Pull each arm once
For t = K+1 ... T:
  For each arm i:
    score[i] = mean[i] + sqrt(2 * log(t) / pulls[i])
  Choose arm with largest score
  Observe reward and update

Aprimoramentos comuns:

KL-UCB usa intervalos de confiança baseados em divergência de KL (KL-divergence) e pode superar UCB1, especialmente para recompensas Bernoulli.
UCB-Ajustado (UCB-Tuned) ajusta o bônus usando a variância empírica.

Nota prática: UCB é determinístico dadas as recompensas; em sistemas de produção você pode querer adicionar aleatoriedade no desempate para evitar efeitos de sincronização.

4) Amostragem de Thompson (Thompson Sampling, TS): amostragem a posteriori bayesiana (Bayesian posterior sampling)

Amostragem de Thompson mantém uma distribuição a posteriori (posterior distribution) sobre a recompensa média de cada braço e amostra dela para decidir:

Para cada braço (i), amostrar (\tilde{\mu}_i \sim p(\mu_i \mid \text{data}))
Jogar (a_t = \arg\max_i \tilde{\mu}_i)
Atualizar a posteriori com a recompensa observada

A amostragem de Thompson costuma ser extremamente competitiva na prática: ela equilibra naturalmente exploração e explotação e é fácil de estender para modelos mais complexos.

Exemplo: recompensas Bernoulli com priores Beta

Se as recompensas são binárias (clique/não clique), um modelo padrão é:

Distribuição a priori (prior): (\mu_i \sim \mathrm{Beta}(\alpha_i, \beta_i))
Observação: (r_t \sim \mathrm{Bernoulli}(\mu_i))

Atualização da posteriori após observar recompensa (r \in {0,1}) no braço (i):

(\alpha_i \leftarrow \alpha_i + r)
(\beta_i \leftarrow \beta_i + (1-r))

Este é um modelo conjugado (conjugate model) clássico: rápido e numericamente estável.

Prós:

Frequentemente excelente desempenho empírico
Naturalmente aleatorizado (bom para plataformas de experimentação)
Fácil de incorporar conhecimento prévio

Contras:

Exige suposições de modelagem probabilística (embora frequentemente razoáveis)
Para modelos não conjugados, você precisa de aproximações (aproximação de Laplace (Laplace), inferência variacional (variational inference), filtros de partículas (particle filters))

5) Exploração Softmax / Boltzmann (Softmax / Boltzmann exploration)

Softmax escolhe braços com probabilidade proporcional ao valor estimado exponenciado:

[ \mathbb{P}(a_t = i) = \frac{\exp(\hat{\mu}_i / \tau)}{\sum_j \exp(\hat{\mu}_j / \tau)} ]

onde (\tau > 0) é um parâmetro de temperatura (temperature parameter):

(\tau) alto: mais exploração (mais uniforme)
(\tau) baixo: mais explotação (mais concentrado)

Prós:

Política estocástica suave; pode ser mais fácil de integrar em sistemas que esperam probabilidades

Contras:

Pode ser mal calibrado: ao contrário de UCB/TS, a “incerteza” surge indiretamente
Sensível à escala da recompensa e ao cronograma de temperatura

6) Bandidos adversariais: EXP3

Quando as recompensas não são estocásticas i.i.d. (por exemplo, podem reagir às suas escolhas), algoritmos como EXP3 mantêm pesos sobre braços e atualizam usando recompensas ponderadas por importância (importance-weighted rewards).

Ideias-chave:

Manter uma distribuição de probabilidade (p_t(i)) sobre braços
Amostrar um braço de acordo com (p_t)
Atualizar pesos para que braços com alta recompensa estimada tenham maior probabilidade

EXP3 é projetado para robustez no pior caso, frequentemente ao custo de ser mais conservador em cenários benignos (estocásticos).

Um exemplo prático: simulando estratégias clássicas

A seguir há um pequeno exemplo em Python para um bandido Bernoulli com três braços. Ele compara ε-ganancioso, UCB1 e amostragem de Thompson.

import math
import random

def run_bandit(T=5000, means=[0.05, 0.06, 0.08], algo="ts", eps=0.1):
    K = len(means)
    best = max(means)
    regret = 0.0

    # stats
    n = [0]*K
    s = [0]*K  # sum of rewards

    # TS Beta params for Bernoulli
    alpha = [1]*K
    beta = [1]*K

    # pull each arm once to initialize (helpful for UCB)
    for i in range(K):
        r = 1 if random.random() < means[i] else 0
        n[i] += 1
        s[i] += r
        alpha[i] += r
        beta[i] += (1 - r)
        regret += best - means[i]

    for t in range(K+1, T+1):
        if algo == "egreedy":
            if random.random() < eps:
                a = random.randrange(K)
            else:
                a = max(range(K), key=lambda i: s[i] / n[i])
        elif algo == "ucb1":
            def ucb(i):
                mean = s[i] / n[i]
                bonus = math.sqrt(2.0 * math.log(t) / n[i])
                return mean + bonus
            a = max(range(K), key=ucb)
        elif algo == "ts":
            # Thompson sampling for Bernoulli-Beta
            samples = [random.betavariate(alpha[i], beta[i]) for i in range(K)]
            a = max(range(K), key=lambda i: samples[i])
        else:
            raise ValueError("unknown algo")

        r = 1 if random.random() < means[a] else 0
        n[a] += 1
        s[a] += r
        alpha[a] += r
        beta[a] += (1 - r)

        regret += best - means[a]

    return regret, n, [s[i]/n[i] for i in range(K)]

if __name__ == "__main__":
    for algo in ["egreedy", "ucb1", "ts"]:
        reg, pulls, est = run_bandit(algo=algo)
        print(algo, "regret=", round(reg, 2), "pulls=", pulls, "est=", [round(x,4) for x in est])

O que você normalmente observa:

ε-ganancioso explora uniformemente, frequentemente desperdiçando puxadas em braços claramente ruins.
UCB1 concentra a exploração em braços que permanecem como possíveis concorrentes.
A amostragem de Thompson frequentemente iguala ou supera UCB na prática, com um comportamento particularmente intuitivo: ela explora em proporção à incerteza.

Bandits vs testes A/B tradicionais

Bandits às vezes são apresentados como “testes A/B melhores”, mas os objetivos diferem:

Teste A/B enfatiza estimação não viesada e significância estatística sob uma alocação fixa.
Bandits enfatizam maximizar a recompensa cumulativa enquanto aprendem.

Se seu principal objetivo é tomada de decisão sob incerteza (por exemplo, maximizar cliques hoje enquanto ainda aprende), MABs se encaixam bem. Se seu objetivo é uma estimativa limpa de um efeito de tratamento para planejamento de longo prazo, experimentação clássica pode ser preferível — ou você pode precisar de desenho e análise cuidadosos.

Na prática, muitas plataformas de experimentação combinam ideias:

Usar um bandit para alocar a maior parte do tráfego de forma adaptativa
Reservar uma fatia de retenção (holdout) para medição confiável
Usar técnicas de Avaliação Fora de Política (Off-Policy Evaluation) para analisar corretamente dados de bandit registrados

Considerações práticas em sistemas reais

Feedback atrasado e ausente

Recompensas podem chegar tarde (conversão após dias) ou não chegar. Abordagens comuns:

Usar recompensas proxy (cliques agora, conversões depois)
Modelar o atraso explicitamente (modelos de sobrevivência, bandits com atraso)
Atualizar posterioris/estimativas de forma assíncrona quando o feedback chega

Não estacionariedade

Preferências de usuários, concorrentes e sazonalidade podem deslocar médias ao longo do tempo. Mitigações comuns:

UCB/TS com janela deslizante (esquecer dados antigos)
Atualizações com desconto
Detecção de ponto de mudança (change-point detection) e reinicializações

Se a não estacionariedade é forte, algoritmos no estilo adversarial ou modelagem explícita de deriva podem ser necessários.

Decisões em lote

Às vezes você precisa escolher ações para um lote (por exemplo, envio diário de e-mails) antes de ver resultados. Bandits em lote reduzem a adaptatividade; correções práticas incluem:

Bônus de incerteza maiores
Amostragem de Thompson com múltiplas amostras da posteriori
Projetar lotes para preservar cobertura de exploração

Restrições e regras de negócio

Implantações reais frequentemente exigem restrições:

Alocação mínima de tráfego para certos braços (contratos)
Limites de risco (não exibir variantes de baixo desempenho demais)
Restrições de fairness ou de política

Isso empurra você em direção a bandidos com restrições (constrained bandits) ou lógica de alocação customizada em camadas acima dos escores do bandit.

Armadilhas de logging e avaliação

Dados de bandit são enviesados pela política que os coletou. Comparar ingenuamente recompensas médias entre braços pode ser enganoso, porque a política amostra preferencialmente braços promissores.

Para avaliação offline e análise contrafactual (counterfactual analysis), você normalmente precisa de:

Probabilidades registradas de ação (propensities)
Métodos como IPS, SNIPS ou estimadores duplamente robustos (doubly robust)

Veja Avaliação Fora de Política.

Quando usar qual estratégia (regra prática)

ε-ganancioso: baseline mais simples; bom quando simplicidade de engenharia domina e o risco é baixo.
UCB (UCB1 / KL-UCB): escolha com teoria forte para bandidos estocásticos; determinístico e interpretável via limites de confiança.
Amostragem de Thompson: frequentemente o melhor padrão prático; naturalmente aleatorizado; fácil de estender e incorporar priores.
EXP3: use quando o ambiente é adversarial ou altamente não estacionário de um modo que quebra suposições estocásticas.
ETC: útil quando você tem uma janela clara de exploração e depois quer uma escolha estável.

Relação com bandidos contextuais e aprendizado por reforço

Bandidos de múltiplos braços assumem que o “melhor” braço é globalmente o melhor. Muitos problemas reais dependem de contexto (usuário, tempo, consulta, dispositivo), o que leva a Bandidos Contextuais. Bandidos contextuais frequentemente reutilizam os mesmos princípios de exploração (otimismo, amostragem a posteriori), mas com um modelo preditivo ( \hat{r}(x, a) ) e estimação de incerteza mais complexa.

Se ações afetam estados futuros (estoque, retenção de usuários, planejamento de longo prazo), você sai de bandits e vai para Aprendizado por Reforço, onde funções de valor (value functions) e atribuição de crédito de longo horizonte (long-horizon credit assignment) importam.

Resumo

Bandidos de múltiplos braços formalizam aprender enquanto faz: você deve alocar tentativas entre ações tanto para ganhar recompensa quanto para reduzir incerteza. O conceito teórico central é arrependimento, e o desafio prático central é equilibrar exploração e explotação sob restrições do mundo real.

Estratégias clássicas formam um kit de ferramentas útil:

ε-ganancioso: exploração aleatória simples
UCB: otimismo via limites de confiança (fortes garantias estocásticas)
Amostragem de Thompson: amostragem a posteriori bayesiana (excelente desempenho prático)
EXP3: robustez em cenários adversariais
ETC: separação clara de exploração e explotação

Em sistemas modernos de ML, bandits frequentemente servem como a camada de decisão para otimização online (online optimization), e fornecem a ponte conceitual de experimentação simples para métodos contextuais e de aprendizado por reforço mais avançados.