Bandits Contextuais

Motivação: por que bandits contextuais?

Muitos sistemas de IA do mundo real precisam tomar uma sequência de decisões — qual artigo mostrar, qual anúncio veicular, qual produto recomendar — enquanto observam informações laterais (features) sobre a situação atual (o contexto). O sistema recebe feedback (uma recompensa) como um clique, compra ou tempo de permanência, mas, crucialmente, ele só observa feedback para a opção que de fato escolheu.

Esse cenário é um encaixe natural para bandits contextuais (contextual bandits): um meio-termo entre:

  • testes A/B (A/B testing) (estáticos demais; personalização fraca; lentos para se adaptar),
  • bandits de múltiplos braços (multi-armed bandits) (sem features, mesma estratégia para todos; veja Bandits de Múltiplos Braços),
  • e aprendizado por reforço (reinforcement learning) completo (modela dinâmicas de longo prazo; frequentemente é excesso quando as escolhas não afetam fortemente estados futuros; veja Aprendizado por Reforço).

Bandits contextuais são amplamente usados em personalização e recomendação porque permitem:

  • Decisões individualizadas com base em features de usuário/item/contexto
  • Aprendizado online (online learning) a partir de dados de interação
  • Uma abordagem bem fundamentada para exploração vs. exploração (exploration vs. exploitation), evitando “ficar preso” em vencedores iniciais

Configuração do problema (modelo formal)

Um bandit contextual procede em rodadas (t = 1, 2, \dots, T):

  1. O ambiente revela um contexto (x_t \in \mathcal{X}) (features disponíveis antes de agir).
  2. O aprendiz escolhe uma ação (a_t \in \mathcal{A}_t) (por exemplo, qual item recomendar).
  3. O aprendiz observa uma recompensa (r_t \in \mathbb{R}) apenas para a ação escolhida.

Uma distinção-chave em relação ao aprendizado supervisionado: para as ações não escolhidas, você não observa suas recompensas (isso é feedback de bandit (bandit feedback)).

Contexto, ações e representações de features

Em personalização/recomendação, um padrão comum é representar cada item/ação candidato por meio de um mapa de features conjunto (joint feature map):

[ \phi(x_t, a) \in \mathbb{R}^d ]

Exemplos:

  • (x_t): features do usuário (localidade, dispositivo, interesses), features de sessão (hora do dia), features da consulta
  • (a): um item/anúncio/artigo candidato
  • (\phi(x_t, a)): concatenação ou features de interação (embedding do usuário ⊙ embedding do item, etc.)

Objetivo e arrependimento

Se a melhor ação no tempo (t) (dado o contexto) é:

[ a_t^* \in \arg\max_{a \in \mathcal{A}_t} \mathbb{E}[r_t \mid x_t, a] ]

então o (pseudo-)arrependimento após (T) rodadas é:

[ R_T = \sum_{t=1}^T \left(\mathbb{E}[r_t \mid x_t, a_t^*] - \mathbb{E}[r_t \mid x_t, a_t]\right) ]

Bons algoritmos de bandit contextual atingem arrependimento que cresce sublinearmente em (T), isto é, o arrependimento médio vai a zero.

Como bandits contextuais diferem de RL completo

Bandits contextuais assumem ausência de dinâmicas de estado de longo horizonte relevantes para a tomada de decisão:

  • Sua ação afeta a recompensa imediata, mas não muda de forma significativa o próximo contexto de um modo que você precise modelar.
  • Isso se encaixa em muitos cenários de recomendação/anúncios em que cada impressão é aproximadamente independente, ou em que uma recompensa míope de curto prazo é aceitável.

RL completo (MDPs) torna-se necessário quando ações têm efeitos atrasados significativos (por exemplo, conteúdo moldando retenção no longo prazo). Bandits contextuais muitas vezes são uma linha de base forte mesmo nesse caso.

O trade-off exploração–exploração com features

Mesmo com um modelo poderoso, você enfrenta incerteza:

  • Para algumas regiões do espaço de contexto (novos usuários, novos itens, segmentos raros), previsões são pouco confiáveis.
  • Se você sempre “explorar” o seu melhor palpite atual, pode nunca coletar dados para aprender essas regiões.

Algoritmos de bandit contextual acoplam:

  • um modelo de recompensa (reward model) (predizer (\mathbb{E}[r \mid x,a])),
  • com um mecanismo de exploração (exploration mechanism) que considera a incerteza.

Isso é o que os diferencia de “treinar um preditor offline e sempre escolher argmax”.

Famílias principais de algoritmos

1) Bandits contextuais lineares (cavalo de batalha para muitos sistemas)

Assuma que a recompensa esperada é linear nas features:

[ \mathbb{E}[r \mid x,a] = \theta^\top \phi(x,a) ]

com parâmetro desconhecido (\theta \in \mathbb{R}^d).

Esse modelo é simples, escalável e muitas vezes surpreendentemente competitivo (especialmente com boa engenharia de features e embeddings).

LinUCB (otimismo diante da incerteza)

LinUCB escolhe a ação com o maior limite superior de confiança (upper confidence bound):

[ \text{score}(a) = \hat{\theta}^\top \phi(x,a) ;+; \alpha \sqrt{\phi(x,a)^\top A^{-1}\phi(x,a)} ]

Onde:

  • (A = \lambda I + \sum_{s < t} \phi(x_s,a_s)\phi(x_s,a_s)^\top) (matriz de projeto)
  • (\hat{\theta} = A^{-1} b), com (b = \sum_{s < t} r_s \phi(x_s,a_s))
  • o segundo termo é um raio de incerteza; (\alpha) controla a exploração

Intuição: preferir ações que ou pareçam boas ou sejam incertas.

Exemplo mínimo de LinUCB (Python-like)

import numpy as np

class LinUCB:
    def __init__(self, d, alpha=1.0, lam=1.0):
        self.d = d
        self.alpha = alpha
        self.A = lam * np.eye(d)
        self.b = np.zeros(d)

    def select_action(self, phi_actions):
        # phi_actions: array of shape (K, d), one feature vector per action
        A_inv = np.linalg.inv(self.A)
        theta_hat = A_inv @ self.b

        means = phi_actions @ theta_hat
        unc = np.sqrt(np.sum((phi_actions @ A_inv) * phi_actions, axis=1))
        scores = means + self.alpha * unc

        return int(np.argmax(scores))

    def update(self, phi, reward):
        self.A += np.outer(phi, phi)
        self.b += reward * phi

Em um recomendador, phi_actions pode ser o conjunto de features conjuntas usuário–item para o conjunto candidato.

Variantes

  • Modelos lineares disjuntos (disjoint linear models): um (\theta_a) por ação (bom quando há poucas ações e elas são distintas; pode ser caro com muitos itens).
  • Modelo compartilhado (shared model): um (\theta) para todas as ações usando (\phi(x,a)) (comum para catálogos grandes).

2) Amostragem de Thompson (Thompson sampling) (amostragem bayesiana para exploração)

A amostragem de Thompson mantém uma distribuição posterior sobre os parâmetros do modelo e:

  1. amostra um modelo plausível da posterior,
  2. escolhe a ação que é ótima sob esse modelo amostrado.

Para suposições linear-Gaussianas:

  • Posterior: (\theta \sim \mathcal{N}(\mu, \Sigma))
  • Amostrar (\tilde{\theta}), escolher (a = \arg\max_a \tilde{\theta}^\top \phi(x,a))

Por que é popular: simples, forte desempenho empírico, e a exploração emerge naturalmente da incerteza.

3) Bandits contextuais lineares generalizados e não lineares

Modelos lineares podem ser limitantes quando a recompensa depende de forma não linear das features.

Extensões comuns:

  • Bandits Lineares Generalizados (Generalized Linear Bandits, GLMs): por exemplo, modelo logístico para cliques
    [ \mathbb{P}(\text{click}=1 \mid x,a) = \sigma(\theta^\top \phi(x,a)) ] Útil quando recompensas são Bernoulli e probabilidades importam.

  • Bandits de kernel (kernel bandits): métodos não paramétricos em que similaridade guia a generalização (poderosos, mas podem ser computacionalmente pesados em escala).

  • Bandits contextuais neurais (neural contextual bandits): usam uma rede neural para predizer recompensa e aproximar incerteza (por exemplo, ensembles, bootstrapping, aproximações bayesianas na última camada).
    Eles são atraentes para entradas ricas (texto, imagens) e quando você já tem representações profundas de Redes Neurais.

Ressalva prática: estimar incerteza é a parte difícil. Uma rede neural simples treinada com MSE e argmax guloso não é um algoritmo de bandit contextual; tipicamente ela explora pouco.

4) Linhas de base simples: ε-greedy e explorar-então-comprometer

  • ε-greedy: com probabilidade ε, escolher uma ação aleatória; caso contrário, explorar.
    Fácil de implementar, mas a exploração costuma ser ineficiente porque ignora incerteza e a estrutura do contexto.

  • Explorar-então-comprometer (explore-then-commit): explorar uniformemente por um tempo e depois explorar.
    Em geral, é rígido demais para sistemas não estacionários e grandes espaços de contexto.

Exemplos práticos em personalização e recomendação

Exemplo 1: recomendação de notícias/artigos (um único slot)

  • Contexto (x): embedding do usuário, dispositivo, hora do dia, localização, sinais de recência
  • Ações (a): artigos candidatos
  • Recompensa: clique (0/1), tempo de permanência, ou uma combinação ponderada

Um bandit contextual pode:

  • explorar novos artigos para aprender quem gosta deles,
  • explorar preferências conhecidas para usuários recorrentes,
  • adaptar-se conforme tendências mudam.

Um pipeline típico de engenharia:

  1. Geração de candidatos (modelo de recuperação) produz ~100–1000 candidatos.
  2. O bandit contextual ranqueia ou seleciona entre os candidatos.
  3. O logging registra: contexto, ação escolhida, recompensa e (criticamente) a propensão (propensity) de escolher aquela ação sob a política de logging (necessária para avaliação).

Exemplo 2: seleção de anúncios (otimização de CTR)

  • Recompensa: clique ou conversão
  • Restrições fortes: pacing de orçamento, limite de frequência, segurança de política
  • Muitas vezes modelado com bandits logísticos/GLM ou modelos lineares sobre embeddings aprendidos

Exploração é valiosa para:

  • novas criatividades,
  • novos segmentos de segmentação,
  • dinâmicas de leilão em mudança.

Exemplo 3: educação personalizada

  • Contexto: perfil de habilidade do aluno, erros recentes, tempo disponível
  • Ação: próximo exercício
  • Recompensa: acerto, proxy de ganho de aprendizado, engajamento

Isso pode ser formulado como bandits contextuais quando o foco é o sinal de aprendizado imediato em vez do planejamento de currículo no longo prazo (este último empurra em direção a RL).

Considerações-chave de projeto (o que quebra na prática)

Engenharia de features e representações

Bandits contextuais dependem de generalização entre contextos:

  • Boas features reduzem a dor de cold-start e a complexidade amostral.
  • Features conjuntas (\phi(x,a)) são cruciais: features só do usuário ou só do item normalmente não bastam.

Escolhas comuns:

  • One-hot/categóricas + interações (para modelos lineares)
  • Embeddings aprendidos a partir de logs históricos
  • Embeddings de texto/imagem de modelos pré-treinados (depois um bandit linear por cima)

Grandes espaços de ações e conjuntos candidatos

Recomendadores reais podem ter milhões de itens. Tipicamente, você:

  • recupera (retrieve) um conjunto candidato gerenciável (recuperação two-tower, ANN, etc.),
  • executa o bandit apenas sobre esse conjunto.

Isso significa que o bandit otimiza condicionalmente à geração de candidatos, não sobre o catálogo inteiro.

Recomendação de slate (múltiplos itens exibidos de uma vez)

Muitas UIs mostram uma lista de itens. Isso vira um problema de bandit combinatório / de slate (combinatorial / slate bandit):

  • a recompensa depende do slate inteiro (viés de posição, diversidade, efeitos de substituição),
  • a abordagem ingênua de “pegar top-K independentemente” pode ser subótima.

Aproximações comuns:

  • tratar cada posição como seu próprio bandit contextual com features de posição,
  • usar reranking com penalidades de diversidade,
  • usar métodos contrafactuais de aprendizado para ranqueamento (mais complexos).

Feedback atrasado, ausente e enviesado

Recompensas podem ser atrasadas (conversões), esparsas (compras) e enviesadas por exposição/posição.

Técnicas:

  • definir recompensas proxy de curto prazo (clique, adicionar ao carrinho) + modelagem de longo prazo
  • incorporar features de posição ou correção por propensão
  • usar logging e avaliação cuidadosos (veja Avaliação Off-Policy)

Não estacionariedade (o mundo muda)

Preferências de usuários, inventário e tendências derivam. Respostas comuns:

  • atualizações com janela deslizante ou decaimento exponencial nos dados
  • resets periódicos ou warm starts
  • detecção explícita de pontos de mudança (avançado)
  • features contextuais que capturam tempo/sazonalidade

Segurança, restrições e guardrails

Políticas em produção frequentemente precisam obedecer restrições:

  • não degradar métricas-chave além de um limiar
  • filtros de segurança de conteúdo
  • restrições de justiça entre grupos
  • regras de negócio (inventário, promoções)

Isso leva a bandits contextuais com restrições (constrained contextual bandits) (por exemplo, exploração segura, bandits conservadores), nos quais você restringe a exploração para evitar grande risco de piora.

Treinamento e avaliação offline (armadilhas contrafactuais)

Um desafio recorrente: você quer saber como uma nova política se sairia sem implantá-la.

Mas dados de bandit logados são enviesados em direção ao que a política antiga escolheu. Treinar/avaliar de forma ingênua como aprendizado supervisionado gera resultados enganosos.

Ferramentas padrão incluem:

  • Pontuação por Propensão Inversa (Inverse Propensity Scoring, IPS): reponderar recompensas observadas pelo inverso da probabilidade de a política de logging ter escolhido a ação.
  • Estimadores Duplamente Robustos (Doubly Robust, DR): combinam um modelo de recompensa com ponderação por propensão para melhor estabilidade.
  • IPS auto-normalizado (self-normalized IPS), clipping e truques de redução de variância.

Essa área é grande e importante em recomendação; veja Avaliação Off-Policy.

Escolhendo um algoritmo: orientação prática por regras de bolso

  • Se você quer uma linha de base forte e simples com embasamento teórico:

    • LinUCB ou Amostragem de Thompson Linear (Linear Thompson Sampling) com boa (\phi(x,a))

  • Se recompensas são binárias e probabilidades importam:

    • Bandits logísticos/GLM

  • Se você tem entradas ricas e precisa de modelagem não linear:

    • Bandits contextuais neurais, mas planeje estimativa de incerteza e monitoramento cuidadoso

  • Se você ainda não consegue implementar incerteza bem:

    • comece com ε-greedy como linha de base, mas espere ineficiência e ajuste com cuidado

Quando bandits contextuais são (e não são) a ferramenta certa

Use bandits contextuais quando:

  • você tem contexto por decisão
  • recompensas são imediatas ou quase imediatas
  • você precisa de aprendizado online e exploração
  • ações não influenciam fortemente o próximo contexto de um modo que você precise modelar

Prefira métodos completos de RL quando:

  • há consequências atrasadas relevantes (retenção, satisfação de longo prazo)
  • ações mudam estados futuros de maneiras importantes (interações estratégicas)

Na prática, muitas equipes implantam bandits contextuais primeiro e depois expandem em direção a RL conforme instrumentação, desenho de recompensa e avaliação amadurecem.

Modos comuns de falha (e como mitigá-los)

  • Loop de feedback guloso (greedy feedback loop): sempre explorar → não aprender sobre alternativas
    Mitigação: exploração UCB/Thompson, orçamento explícito de exploração.

  • Má definição de recompensa: otimizar cliques prejudica satisfação de longo prazo
    Mitigação: recompensa multiobjetivo, restrições, proxies de longo prazo.

  • Logging sem propensões: impossível fazer avaliação offline confiável
    Mitigação: registrar probabilidades de ação da política em serving.

  • Mudança de distribuição (distribution shift): modelo treinado offline falha online
    Mitigação: rollouts em estágios, exploração conservadora, monitoramento.

  • Viés de posição e efeitos de UI: recompensa depende de layout e exposição
    Mitigação: incluir features de posição/contexto; usar métodos de remoção de viés.

Resumo

Bandits contextuais estendem bandits clássicos ao incorporar features (contexto) para que o aprendizado generalize entre usuários, itens e situações. Eles são uma ferramenta fundamental para personalização e recomendação, permitindo que sistemas melhorem online enquanto equilibram exploração (aprender) e exploração (usar o que se sabe). Métodos lineares como LinUCB e amostragem de Thompson são amplamente usados devido à sua simplicidade e forte desempenho, enquanto variantes GLM e neurais lidam com relações mais ricas ao custo de estimativa de incerteza mais complexa e risco operacional.

Para conceitos adjacentes, veja Bandits de Múltiplos Braços, Avaliação Off-Policy e Aprendizado por Reforço.