Bandidos

O que são bandits?

Um problema de bandido (de múltiplos braços) (multi-armed bandit) é um modelo fundamental de tomada de decisão sequencial sob incerteza (sequential decision-making under uncertainty) em que:

A cada rodada (t = 1,2,\dots,T), um agente (agent) escolhe uma ação (action) (um “braço (arm)”) (a_t \in {1,\dots,K})
O ambiente (environment) revela uma recompensa (reward) (r_t) para essa ação escolhida
O objetivo do agente é maximizar a recompensa acumulada (ou, de forma equivalente, minimizar o arrependimento)

Bandits capturam cenários em que as ações têm consequências imediatas e não há dinâmicas de longo horizonte (long-horizon dynamics): escolher uma ação não altera um estado latente (latent state) que afeta recompensas futuras (além do que você aprende). Isso torna os bandits mais simples do que conceitos completos de aprendizado por reforço (reinforcement learning, RL), como os descritos em Conceitos de Aprendizado por Reforço, como processos de decisão de Markov (Markov decision processes, MDPs), e ainda assim ricos o suficiente para estudar a tensão central de Exploração vs Aproveitamento (Exploration vs Exploitation).

Um modelo mental útil é: bandits são “RL com um único estado” (ou horizonte episódico (episodic horizon) (H=1)).

Por que bandits importam

Bandits são amplamente usados para experimentação adaptativa (adaptive experimentation): em vez de se comprometer com uma divisão fixa de um teste A/B, você ajusta continuamente o tráfego em direção a opções melhores, enquanto ainda explora alternativas. Isso pode:

Melhorar a experiência do usuário durante o experimento (menor exposição a variantes ruins)
Aprender mais rápido sob restrições de recursos
Permitir personalização via contextos (características)

Aplicações comuns no mundo real incluem:

Publicidade online (escolher qual anúncio mostrar)
Recomendação/personalização (escolher conteúdo ou estratégia de ranqueamento)
Experimentos de produto (escolher variantes de UI)
Ensaios clínicos adaptativos (escolher braços de tratamento)
Precificação dinâmica (dynamic pricing) (escolher pontos de preço)
Otimização de sistemas (systems optimization) (escolher configurações)
Ajuste de hiperparâmetros (hyperparameter tuning) (escolher configurações de modelo com avaliações ruidosas)

Fundamentos teóricos

Modelo básico de bandit estocástico

No bandit clássico estocástico (stochastic) de (K) braços:

Cada braço (i) tem uma distribuição de recompensas desconhecida (D_i) com média (\mu_i)
Quando você puxa o braço (i), observa (r \sim D_i), i.i.d. ao longo do tempo para esse braço

O braço ótimo é (i^* = \arg\max_i \mu_i).

Arrependimento

Uma métrica central de desempenho é o arrependimento cumulativo (cumulative regret):

[ R_T = \sum_{t=1}^T \left(\mu^* - \mu_{a_t}\right) ]

onde (\mu^* = \max_i \mu_i).

Intuição: arrependimento é a recompensa que você “deixa na mesa” por não escolher sempre o melhor braço. Bons algoritmos garantem arrependimento sublinear (sublinear regret) (por exemplo, (O(\log T)) ou (O(\sqrt{T}))), o que significa que o arrependimento médio (R_T/T \to 0).

Uma decomposição útil usa as lacunas (\Delta_i = \mu^* - \mu_i):

[ R_T = \sum_{i \ne i^*} \Delta_i , \mathbb{E}[N_i(T)] ]

onde (N_i(T)) é o número de vezes que o braço (i) é selecionado até o tempo (T). O projeto de bandits é, em grande parte, sobre controlar (N_i(T)): explorar o suficiente para identificar bons braços, mas não tanto a ponto de desperdiçar puxadas em braços ruins.

Uma nota sobre pressupostos

A teoria de bandits frequentemente se apoia em pressupostos como:

Distribuições de recompensa estacionárias (as médias não derivam)
Independência condicional (dado o braço escolhido)
Recompensas limitadas ou subgaussianas

Em produção, isso pode ser violado (sazonalidade, ciclos de realimentação, recompensas atrasadas), motivando extensões práticas discutidas mais adiante.

Algoritmos centrais (bandits de múltiplos braços)

Para uma cobertura mais profunda de formulações e estratégias padrão, veja Bandits de Múltiplos Braços. A seguir, uma visão geral focada.

Guloso e \(\varepsilon\)-guloso

Guloso (greedy): sempre escolhe o braço com maior média estimada (\hat{\mu}_i).

Simples e frequentemente forte quando você tem muitos dados e diferenças claras
Pode falhar muito no início: se as amostras iniciais forem azaradas, pode ficar preso explorando o braço errado

(\varepsilon)-guloso ((\varepsilon)-greedy): com probabilidade (\varepsilon), explora (escolhe um braço aleatório); caso contrário, aproveita (explora) a melhor estimativa atual.

Notas práticas:

Muitas vezes (\varepsilon) decai ao longo do tempo (por exemplo, (\varepsilon_t \propto 1/t))
Fácil de implementar e robusto, mas em geral não é ótimo em arrependimento

Limite Superior de Confiança (Upper Confidence Bound, UCB)

Métodos UCB formalizam “otimismo sob incerteza” ao selecionar o braço com o melhor limite superior de confiança:

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

Uma escolha comum (UCB1) usa:

[ \text{bonus}_i(t) = \sqrt{\frac{2 \log t}{N_i(t)}} ]

Ideia-chave: braços raramente testados recebem um bônus maior de incerteza, forçando a exploração. Algoritmos UCB atingem forte arrependimento logarítmico em cenários estocásticos.

Amostragem de Thompson (Thompson Sampling) (bandits bayesianos (Bayesian bandits))

A Amostragem de Thompson (TS) é uma abordagem de correspondência de probabilidade:

Manter uma distribuição a posteriori (posterior distribution) sobre a recompensa média de cada braço
Amostrar uma média candidata (\tilde{\mu}_i) de cada posterior
Escolher o braço com a maior (\tilde{\mu}_i) amostrada

Para recompensas Bernoulli, uma escolha comum é um prior Beta (Beta prior): (\mu_i \sim \text{Beta}(\alpha_i,\beta_i)).

Notas práticas:

TS é amplamente usada na indústria por seu forte desempenho empírico e simplicidade
Lida naturalmente com exploração sem ajuste manual de (\varepsilon)
Requer escolher priors (em geral, priors fracamente informativos funcionam bem)

Bandits adversariais (adversarial bandits) (EXP3)

Em bandits adversariais (adversarial), as recompensas podem ser escolhidas por um adversário (ou surgir de processos não estacionários, estratégicos ou altamente correlacionados). Algoritmos como EXP3 mantêm uma distribuição sobre braços e a atualizam multiplicativamente com base em recompensas ponderadas por importância, alcançando arrependimento (O(\sqrt{KT \log K})) sem pressupostos estocásticos.

Isso importa quando:

O ambiente está reagindo às suas escolhas (cenários estratégicos)
As distribuições de recompensa derivam de formas desconhecidas
Registro (logging) ou medição mudam ao longo do tempo

Um exemplo prático: simulando UCB vs Amostragem de Thompson

Abaixo está um exemplo mínimo em Python para um bandit Bernoulli com três braços.

import numpy as np

rng = np.random.default_rng(0)

true_p = np.array([0.05, 0.08, 0.10])  # unknown to the agent
K = len(true_p)
T = 10_000

def pull(arm):
    return 1.0 if rng.random() < true_p[arm] else 0.0

def run_ucb():
    N = np.zeros(K, dtype=int)
    S = np.zeros(K, dtype=float)
    rewards = []

    # Initialize: pull each arm once
    for a in range(K):
        r = pull(a)
        N[a] += 1
        S[a] += r
        rewards.append(r)

    for t in range(K + 1, T + 1):
        mu_hat = S / N
        bonus = np.sqrt(2.0 * np.log(t) / N)
        a = int(np.argmax(mu_hat + bonus))
        r = pull(a)
        N[a] += 1
        S[a] += r
        rewards.append(r)
    return np.array(rewards)

def run_thompson():
    alpha = np.ones(K)  # successes + 1
    beta  = np.ones(K)  # failures  + 1
    rewards = []

    for _ in range(T):
        samples = rng.beta(alpha, beta)
        a = int(np.argmax(samples))
        r = pull(a)
        alpha[a] += r
        beta[a]  += (1.0 - r)
        rewards.append(r)
    return np.array(rewards)

r_ucb = run_ucb()
r_ts  = run_thompson()

print("Mean reward UCB:", r_ucb.mean())
print("Mean reward TS :", r_ts.mean())
print("Optimal mean   :", true_p.max())

O que você deve observar:

Ambos os métodos rapidamente se concentram no melhor braço
Eles ainda ocasionalmente exploram no início (UCB via bônus; TS via incerteza da posterior)

Bandits contextuais: decisões com características

Muitas aplicações dependem de quem é o usuário ou qual é a situação. Em bandits contextuais (contextual bandits), cada rodada fornece um contexto (x_t) (características (features)), e o agente escolhe uma ação (a_t), recebendo recompensa (r_t):

[ \pi(a \mid x) \rightarrow r ]

O objetivo é aprender uma política (policy) (\pi) que escolha boas ações condicionadas ao contexto.

Exemplos:

Recomendação de notícias: contexto = usuário + horário + dispositivo; ação = artigo; recompensa = clique/tempo de permanência
Anúncios: contexto = usuário + página; ação = criativo do anúncio; recompensa = conversão
Suporte ao cliente: contexto = texto do ticket; ação = escolha de roteamento; recompensa = tempo de resolução

Desafio-chave: você só observa a recompensa da ação que tomou (realimentação de bandit (bandit feedback)), não das ações que não tomou (ao contrário dos rótulos no aprendizado supervisionado).

Abordagens comuns incluem:

Bandits contextuais lineares (linear contextual bandits) (por exemplo, LinUCB, Amostragem de Thompson Linear), assumindo [ \mathbb{E}[r \mid x,a] = x^\top \theta_a ]
Bandits lineares generalizados (generalized linear bandits) (recompensas logísticas)
Bandits contextuais neurais (neural contextual bandits) (modelos profundos + heurísticas de exploração)
Métodos baseados em políticas (policy-based methods) usando amostragem por importância (importance sampling) e aprendizado online (online learning)

Para um tratamento dedicado, veja Bandits Contextuais.

Redução para aprendizado supervisionado (com ressalvas)

Uma ideia tentadora é registrar dados ((x_t, a_t, r_t)) e treinar um modelo para prever recompensa. Mas um treinamento ingênuo pode ser enviesado porque as ações escolhidas dependem de decisões anteriores da política (viés de seleção). Métodos adequados normalmente exigem:

Exploração explícita durante a coleta de dados e/ou
Técnicas de correção fora da política

Isso leva diretamente à avaliação fora da política.

Avaliação fora da política (off-policy evaluation, OPE) e dados de bandit registrados

Frequentemente você quer avaliar uma nova política sem implantá-la, usando interações registradas de uma política antiga (a política de registro (logging policy)). Isso é crucial quando experimentação online é cara ou arriscada.

Estimadores padrão de OPE incluem:

IPS (Pontuação de Propensão Inversa (Inverse Propensity Scoring, IPS)): [ \hat{V}{IPS}(\pi) = \frac{1}{n}\sum{t=1}^n \frac{\pi(a_t\mid x_t)}{b(a_t\mid x_t)} r_t ] onde (b) são as propensões da política de comportamento (behavior policy) (de registro).
IPS auto-normalizado (self-normalized IPS) (redução de variância)
Estimadores duplamente robustos (doubly robust) (combinam um modelo de recompensa com IPS para robustez)

OPE é sutil: erros no registro de propensões, incompatibilidade de suporte (support mismatch) (a nova política escolhe ações raramente/nunca tomadas nos logs) e pesos de importância de caudas pesadas (heavy-tailed) podem quebrar as estimativas.

Para detalhes e armadilhas, veja Avaliação Fora da Política.

Aplicações práticas

1) Publicidade online e otimização de criativos

Problema: escolher entre múltiplos criativos de anúncio, lances ou posicionamentos.

Braços: criativos ou estratégias
Recompensa: clique, conversão, receita
Contexto: características do usuário, categoria da página, horário do dia

Bandits ajudam a alocar impressões de forma adaptativa, especialmente quando novos criativos são introduzidos e precisam de exploração.

Considerações práticas:

Recompensas atrasadas (delayed rewards) (conversões podem ocorrer horas depois)
Atribuição (attribution) e ruído (spam de cliques, cross-device)
Restrições de orçamento (budget constraints) e pacing (uma variante de bandit com restrições)

2) Sistemas de recomendação e personalização

Bandits são usados para a “última milha” da personalização: escolher qual item (ou variante de ranqueamento) mostrar agora.

Configurações típicas:

Bandit contextual sobre um conjunto candidato
Sinais de recompensa: clique, tempo de permanência, long-click, proxy de retenção

Bandits complementam recomendadores supervisionados:

Um modelo supervisionado propõe candidatos (preditivo)
Uma política de bandit gerencia exploração, adapta-se online e corrige mudança de distribuição (distribution shift) (sensível à decisão (decision-aware))

3) Ensaios clínicos adaptativos

Em ensaios clínicos, pacientes são atribuídos a tratamentos ao longo do tempo.

Braços: tratamentos/doses
Recompensa: desfecho de saúde, penalidade por evento adverso, endpoints substitutos

Alocação ao estilo bandit pode:

Reduzir a exposição de pacientes a tratamentos inferiores
Identificar tratamentos eficazes mais cedo

No entanto, requisitos regulatórios e estatísticos são rigorosos. Os desenhos precisam controlar:

Erro tipo I e viés
Desequilíbrio de covariáveis
Restrições de segurança (frequentemente exigindo exploração conservadora)

4) Precificação dinâmica e gestão de receita

Escolha um preço (p) (discreto ou contínuo) para maximizar receita.

Braço: ponto de preço (ou política de preço)
Recompensa: receita (= p \cdot \mathbb{1}[\text{purchase}])
Contexto: segmento de usuário, produto, sazonalidade

Isso frequentemente é um bandit contextual e não estacionário (non-stationary): curvas de demanda derivam e o comportamento de concorrentes muda.

5) Ajuste de hiperparâmetros e configurações

Muitas tarefas de ajuste podem ser formuladas como bandits:

Braços: configurações de hiperparâmetros, arquiteturas de modelo, flags de compilador
Recompensa: métrica de validação (ruidosa, treinamento estocástico)
Contexto: características do conjunto de dados ou orçamento de recursos

Ideias relacionadas:

redução sucessiva (successive halving) / Hyperband (alocação de recursos inspirada em bandits entre configurações)
otimização bayesiana (Bayesian optimization) (não é um bandit propriamente dito, mas compartilha princípios de exploração)

6) Sistemas e redes

Exemplos:

Escolher estratégias de cache
Selecionar caminhos de roteamento
Definir contagens de réplicas ou limiares de autoscaling

Recompensas podem refletir latência, throughput, custo ou violações de objetivos de nível de serviço (service level objectives, SLOs). Não estacionariedade e realimentação atrasada são comuns.

Bandits em produção: considerações de design e engenharia

Definindo a recompensa

A definição da recompensa frequentemente é a parte mais difícil.

Boas recompensas são:

Alinhadas (aligned) ao objetivo real (por exemplo, satisfação de longo prazo vs cliques em clickbait)
Mensuráveis rápido o suficiente para permitir aprendizado
Robustas a manipulação

Frequentemente você usará recompensas proxy com guardrails (por exemplo, otimizar CTR sujeito a churn não aumentar).

Realimentação atrasada e ausente

Muitas recompensas reais chegam tarde (conversões, retenção). Estratégias comuns:

Usar recompensas proxy intermediárias (clique → funil de conversão)
Modelar o atraso explicitamente (atribuição de crédito ao longo do tempo)
Atualizações em lote (atualizar a política uma vez por hora/dia)

Não estacionariedade

Preferências de usuários derivam; inventário muda; há sazonalidade.

Abordagens:

Janelas deslizantes (sliding windows) ou decaimento exponencial (exponential decay) nas estimativas
Detecção de ponto de mudança (change-point detection)
Algoritmos projetados para ambientes com deriva (variantes de UCB/TS com desconto)

Restrições e segurança

Sistemas reais impõem restrições:

Limites de orçamento
Requisitos mínimos de exposição (por exemplo, obrigações contratuais)
Restrições de risco (evitar perdas grandes)
Restrições de equidade (fairness constraints) entre grupos

Isso gera bandits com restrições (constrained bandits) ou bandits seguros (safe bandits), normalmente exigindo métodos Lagrangianos, exploração conservadora ou tratamento explícito de restrições.

Logging e propensões (crítico para OPE)

Se você algum dia quiser avaliação offline, deve registrar:

Contexto (x_t)
Ação escolhida (a_t)
Recompensa (r_t)
Probabilidade da ação sob a política implantada (b(a_t \mid x_t)) (a propensão (propensity))

Sem propensões corretas, avaliação fora da política não enviesada geralmente é impossível.

Integração com experimentação online

Bandits não substituem a disciplina de experimentação; são uma ferramenta dentro dela.

Padrões comuns de implantação:

Começar com um teste A/B para validar medição e segurança
Fazer ramp-up de uma política de bandit gradualmente com monitoramento
Usar configurações de campeão/desafiante (champion/challenger) e fallbacks
Manter um conjunto de controle (holdout) para detectar hacking de recompensa ou deriva de métricas

Variantes e extensões (o que “bandits” pode significar)

Problemas de bandit vêm em muitas formas além do caso estocástico básico de (K) braços:

Identificação do melhor braço (best arm identification) (exploração pura (pure exploration)): minimizar amostras para encontrar o melhor braço com confiança (por exemplo, para seleção de modelo)
Bandits combinatórios (combinatorial bandits): escolher um subconjunto de itens (por exemplo, um slate de recomendações)
Bandits de duelo (dueling bandits): realimentação é uma preferência pareada (“A vs B”), comum em ranqueamento e preferência humana
Bandits adormecidos (sleeping bandits): ações disponíveis mudam ao longo do tempo (restrições de inventário)
Bandits em lotes (batched bandits): decisões feitas em lotes antes de observar resultados (comum em saúde e pipelines offline)
Bandits não estacionários (non-stationary bandits): distribuições de recompensa derivam
Bandits adversariais (adversarial bandits): sem pressuposto estocástico; garantias robustas de arrependimento

Essas variantes frequentemente aparecem quando o mundo real viola os pressupostos mais simples.

Quando usar bandits vs RL completo

Bandits são uma boa escolha quando:

O impacto da ação é majoritariamente imediato
Não há um estado significativo do ambiente que você consiga controlar ao longo do tempo
Você precisa de aprendizado online rápido, confiável e com garantias fortes
Você consegue instrumentar recompensas por decisão

Métodos completos de RL (veja Métodos de Aprendizado por Reforço) tornam-se necessários quando:

Ações afetam estados futuros e oportunidades futuras (planejamento de longo horizonte)
Você precisa de atribuição de crédito (credit assignment) ao longo de múltiplos passos
O sistema tem consequências atrasadas que dependem de sequências de ações

Se você só tem dados registrados e não pode explorar online, talvez precise de aprendizado por reforço offline (Offline RL) ou de abordagens baseadas em OPE para bandits, dependendo de se as dinâmicas de longo horizonte importam.

Principais conclusões

Bandits modelam tomada de decisão sequencial com recompensas imediatas: aprender quais ações funcionam enquanto continua agindo.
O desafio central é exploração vs. aproveitamento, tipicamente formalizado via arrependimento (regret).
Algoritmos clássicos incluem (\varepsilon)-guloso, UCB, Amostragem de Thompson e EXP3 (adversarial).
Bandits contextuais estendem bandits a personalização e recomendação ao condicionar em características.
Implantações reais exigem atenção cuidadosa a design de recompensa, logging, atrasos, não estacionariedade e restrições.
Bandits ficam em um ponto de equilíbrio entre aprendizado supervisionado e RL completo: mais simples do que RL de longo horizonte, mas sensível à decisão e adaptativo.