Bandits contextuais

Tudo sobre o bandit contextual deste repositório está nesta página: a ideia, o índice de arquivos, os comandos, a interface, o que o Z3 prova, o porte em Haskell e a nota do vídeo. O código Z3 fica em z3-scala/. Padrão de escrita: gramatico, nível smart-note + descritivo. Versão em inglês: README.md.

Sumário

1. A ideia
2. Arquivos
3. Como rodar
4. A interface
5. O que o Z3 prova
6. O porte em Haskell
7. Ressalvas
8. Nota do vídeo
   • Mapa de cenas
   • Bloco 1. CMAB
   • Bloco 2. Teste A/B
   • Bloco 3. RSI
9. Fontes

1. A ideia

O sistema escolhe uma opção (um braço) para cada requisição. O sistema conhece alguns dados da requisição (o contexto). O sistema recebe a recompensa só do braço escolhido. A política é a regra que leva do contexto ao braço. O arrependimento (regret) é a soma, em todas as rodadas, da recompensa do melhor braço menos a recompensa do braço escolhido.

O bandit é uma regra de decisão sobre um modelo probabilístico. O modelo transforma o histórico em crenças. A regra transforma as crenças numa ação.

           contexto c
               │
               ▼
 histórico ─► RewardModel ──estimate(b, c, a) = (média, largura)──► DecisionRule ──► ação a
   ▲          (crença b)    sample(b, c, a)  ~ posteriori          gulosa / ε-gulosa /   │
   │                                                               UCB / Thompson        ▼
   └────────────── update(b, (c, a, r)) ◄────────────── recompensa r ◄──────────── ambiente

A regra de decisão vê só as estimativas de cada braço; a regra nunca vê o histórico nem o contexto. Por isso, qualquer modelo que dê uma média e uma incerteza funciona com qualquer regra. A afirmação policy_factors prova essa fronteira.

Figura 1. A camada de modelo, a camada de decisão e a spec em Z3 (archify; clique para abrir o diagrama interativo).

2. Arquivos

3. Como rodar

just z3                                  # toda afirmação em Z3 (nix develop .#scala); cada linha OK
cd haskell && cabal run examples         # verificação da spec e 4 simulações; ou: runghc -isrc app/Main.hs
cd haskell && cabal run video            # os experimentos do vídeo; escreve o results.md do roteiro
just liquid                              # LiquidHaskell; SAFE em cada módulo
just agda                                # as provas em Agda para todo K (nix develop .#agda)
just paper contextual-bandits            # o preprint (dentro de nix develop)
just script                              # o roteiro do vídeo

O primeiro bloco de cabal run examples compara o Haskell com Examples.scala e Video.scala. Toda linha precisa dizer OK.

4. A interface

5. O que o Z3 prova

O Z3 verifica cada afirmação por refutação (unsat), para K = 1 a 5 braços e todo valor real das estimativas.

O ucb_gap diz o que o modelo deve à camada de decisão: incerteza calibrada. Uma cota de arrependimento do LinUCB precisa do ucb_gap em cada rodada (feito), da calibração com probabilidade ≥ 1 − δ em todas as rodadas (uma cota de martingal, fora do que o Z3 decide) e de Σ larguras = O(√(d T log T)) (o lema do potencial elíptico). Os dois últimos itens ficam abertos.

O Agda prova as linhas da camada de decisão desta tabela (de greedy_valid a policy_factors) para todo K, por indução, sobre racionais exatos: agda/README.md. O Z3 continua a ser a especificação; os nomes em Agda são os do Z3 com - no lugar de _.

6. O porte em Haskell

O porte usa só base e containers e repete os nomes do Z3. O argmax fica com o primeiro máximo, como no Z3. Para ligar um modelo, implemente quatro funções ou embrulhe o modelo com fromPredictor:

fromPredictor
  :: Int                                   -- number of arms
  -> s                                     -- model state (weights, handle, ...)
  -> (s -> Obs c -> s)                     -- online update; `const` if frozen
  -> (s -> c -> Arm -> (Double, Double))   -- predictive (mean, std)
  -> RewardModel c s

• Forma fechada (Beta-Bernoulli, gaussiano, regressão linear bayesiana): update é a atualização da posteriori, estimate dá a média e o desvio da posteriori (betaBernoulli, bayesLinear em Models.hs).
• Treinado offline (regressão logística, gradient boosting, um ensemble): congele o modelo com const e retreine em lotes fora do ciclo.
• Qualquer regra: act m greedy, act m (epsGreedy 0.1), act m (ucb 2), thompsonArm m.

A width precisa ser uma incerteza honesta. Um modelo confiante demais quebra a premissa calibrated, e a UCB e a Thompson viram gulosas.

Saída de cabal run examples (arrependimento acumulado esperado, uma simulação pequena de cada, não é benchmark):

== 0. Spec check against Examples.scala and Video.scala ==   all OK
== 1. Beta-Bernoulli, 2 contexts x 3 arms, T=5000 (avg 20 runs)
greedy 41.1   eps-greedy 0.1 43.3   UCB beta=2 25.3   Thompson 32.8
== 2. Bayesian linear, d=3, 4 arms, T=2000 (avg 10 runs)
greedy 322.9  eps-greedy 0.1 62.0   LinUCB 25.3       LinTS 31.5

O LiquidHaskell verifica tipos refinados em ContextualBandit.hs e Models.hs: o argmax devolve um índice válido, cada regra devolve probabilidades em [0, 1] e o Beta-Bernoulli mantém as contagens em 1 ou mais. O LIQUIDHASKELL.md lista o que a verificação confia e o que fica de fora.

7. Ressalvas

• O Z3 prova sobre os reais e os racionais exatos. O Haskell usa Double, e as provas não cobrem o arredondamento de ponto flutuante. A verificação da spec mostra que os dois concordam no exemplo comum.
• O Z3 não tem indução: cada teorema vale para K = 1 a 5, não para todo K.
• A amostragem de Thompson é "a gulosa sobre uma amostra da posteriori". A aleatoriedade e o arrependimento dela não estão formalizados.
• O exemplo tabular usa largura 1/(n+1), um substituto racional de 1/√n, para os exemplos ficarem exatos.

8. Nota do vídeo

O vídeo tem três blocos de 10 minutos: CMAB, teste A/B e RSI. Cada parágrafo tem o número da cena do roteiro. Os números vêm de results.md, que cabal run video escreve. O estilo final do vídeo é o do roteiro (Manim, fundo escuro, azul para a crença, amarelo para a escolha, vermelho para o arrependimento); as figuras do archify dão a estrutura.

Mapa de cenas

As figuras estão em docs/diagrams/img/pt-BR/<nome>.png e, interativas, em docs/diagrams/pt-BR/<nome>.html. Os arquivos do Desmos estão em script/desmos/. Cada cena tem um take do Manim em script/animation/; just takes renderiza todos.

Bloco 1. CMAB

Tempo no vídeo: 0:00 a 10:00.

1.1 Gancho. O agente tem uma crença: a opção 0 agrada em 67 % das vezes, a opção 1 em 50 %. Chegam 4 sinais positivos para a opção 1 e 2 negativos para a opção 0. A crença nova diz 0,57 e 0,62, e a escolha muda para a opção 1. O agente muda por evidência, não por palpite.

Figura 2. Uma rodada: decidir, agir, aprender. Cenas 1.1, 2.5 e 3.4.

1.2 Linha do tempo. O roteiro chama a cena de steal like an artist, a partir do livro de Austin Kleon, de 2012.

O roteiro conferiu as fontes de 1952, de 2012, da globo.com e de 2026 (REFERENCES.md). ⚠ Esta nota não abriu de novo essas fontes. O amigo de 2018 não entra na figura: o roteiro ainda marca o nome e o mês como [a confirmar].

Figura 3. A linha do tempo da cena 1.2. As datas têm precisão de ano ou de mês; o archify mostra o dia 1.

1.3 π e você. Você é a recompensa. Com um braço (a série de Leibniz), o agente mostra π(N) de novo (aproveita) ou calcula mais um termo (explora). Você dá uma nota de 0 a 1 pela distância até π. Em 20 rodadas, com ε = 0,2, o agente aproveitou 9 vezes (nota média 0,14), explorou 11 vezes (nota média 0,76) e terminou em π(12). Com três braços, Gauss-Legendre dobra os dígitos a cada passo (3, 8, 19, 41) e Ramanujan acerta 7 dígitos com 1 termo e 48 com 6. O agente puxou Ramanujan 16 vezes, Gauss-Legendre 3 e Leibniz 1. Os dois empatam com nota 1,00; a gulosa fica com o primeiro máximo. O exemplo de π não tem contexto: é um MAB, e não um CMAB.

Figura 4. O ciclo do π. Cenas 1.3 e 1.4.

1.4 O nome. B de bandit (a caça-níquel é o one-armed bandit); M e A de multi-armed (várias alavancas, cada uma com um prêmio médio desconhecido); C de contextual (antes de puxar, o agente vê um dado da rodada, por exemplo manhã ou noite). Com contexto, a melhor alavanca muda a cada rodada, e a política aprende uma função do contexto para a alavanca: linear no LinUCB [6], uma tabela de duas linhas na sorveteria.

1.5 e 1.6. Ver a ideia: as duas camadas, o policy_factors e a tabela das regras. O modelo do vídeo é tabular: média = soma / contagem, largura = 1/(n+1). Com β = 0, a UCB é a gulosa (ucb_zero).

1.7 A Netflix. A Netflix escolhe a imagem de cada título para cada assinante, como descreve o post do Netflix Tech Blog de 2017-12, de Chandrashekar, Amat, Basilico e Jebara [1, 2]. Numa palestra de 2018, Jebara deu estes dados [3]: o contexto é o histórico de visualização e o país; o braço é a imagem; a recompensa é uma reprodução; o sistema usa aprendizado online e bandits contextuais; recebe cerca de 20 milhões de requisições de imagem por segundo no pico; a equipe usa replay para avaliar uma política nova offline. Nessa escala o modelo precisa generalizar, como o bayesLinear (média = contexto · pesos do braço). As fontes primárias são de 2017 e 2018. ⚠ Esta nota não achou fonte primária sobre o uso em 2026: não afirme que a Netflix usa bandits hoje.

Bloco 2. Teste A/B

Tempo no vídeo: 10:00 a 20:00.

2.1 e 2.2. Um teste A/B/n manda cada usuário para uma de K variantes por sorteio e depois fica com a melhor (explore-then-commit). O teste é simples de montar, de ler e de defender. Em termos de bandit:

1. O período de teste é a ε-gulosa com ε = 1 (epsGreedy_one_is_ab_test).
2. A fase de decisão é a ε-gulosa com ε = 0, a gulosa (epsGreedy_zero).
3. O teste completo é um ε que pula de 1 para 0 num dia marcado (R3: etc_before, etc_after).

A pergunta "A/B ou bandit?" vira outra: como ε deve cair ao longo do tempo?

Figura 5. O teste A/B e o ciclo do bandit. Cenas 2.1, 2.2 e 2.4.

2.3 e 2.4. O custo da espera. Uma sorveteria: três sabores, dois contextos (manhã e noite), 5.000 clientes, média de 20 sementes. O teste A/B usa metade dos clientes no sorteio.

O bandit manda mais tráfego para os braços que parecem melhores durante o teste. Jebara chama o ciclo "coletar dados por meses, treinar, depois testar" de "a massive amount of regret" [3]. Um teste A/B por segmento de usuários é um caso particular de bandit contextual.

2.5 O que o A/B faz melhor. A alocação aleatória fixa dá uma estimativa sem viés do efeito. O bandit muda a alocação, e a média simples dos registros fica com viés. Registre a probabilidade de cada escolha (a policy devolve a distribuição inteira) e use replay ou ponderação pelo inverso da propensão (IPW). A Netflix usou um teste A/B para aprovar o sistema de imagens antes da implantação [3]: o bandit substituiu o ciclo lento dentro do teste, não o teste.

2.6 Resumo. O teste A/B é uma política: sem contexto, alocação uniforme fixa, uma decisão no fim. O bandit contextual relaxa as três escolhas. Em produção, segundo as fontes:

• Billboard da Netflix: uma palestra de 2018, de Jaya Kawale e Elliot Chow, descreve um framework de bandit com a ε-gulosa, replay offline e testes A/B online, porque os modelos em lote se adaptam devagar demais ao catálogo [4, 5].
• globo.com: o serviço escolhe "uma foto" e "a melhor posição para colocar publicidade" [9].

Regra prática: teste A/B para uma decisão única que precisa ser defendida; bandit para uma decisão que se repete milhares de vezes por dia com erro barato; os dois juntos quando der.

Bloco 3. RSI

Tempo no vídeo: 20:00 a 30:00.

3.1 Três palavras.

A Anthropic define RSI como um sistema que "could fully autonomously design and develop its successor" [11].

3.2 O menor ciclo recursivo. O agente de dentro é a ε-gulosa da sorveteria. O agente de fora é outro bandit, com valores de ε como braços. Em cada um de 200 episódios, o agente de fora escolhe um ε, o de dentro atende 500 clientes, e o ganho médio é a recompensa de fora.

A mesma epsGreedy funciona nos dois níveis (R4: rsi_valid, outer_explores). O ε = 0,5 ganha porque o horizonte é curto e o modelo começa do zero.

Figura 6. O laço de fora escolhe o ε do laço de dentro. Cenas 3.1 a 3.3.

3.3 A RSI de verdade. O artigo SIA (2026) descreve um "Feedback-Agent" que escolhe entre editar o scaffold, os prompts e as ferramentas, ou atualizar os pesos, com um avaliador determinístico como recompensa [12]: um bandit. ⚠ O roteiro leu o SIA por uma resenha, não pelo PDF. A Anthropic relata uma aceleração de um código de treino de cerca de 3 vezes (maio de 2025) para cerca de 52 vezes (abril de 2026), e uma revisão automática de código que teria pegado cerca de um terço dos erros por trás de incidentes passados [11].

3.4 Crença atual contra crença nova. O Beta-Bernoulli guarda duas contagens por opção, sucessos e fracassos; cada sinal soma 1 numa das contagens. A crença nova soma os sinais novos aos antigos (0,67 e 0,50 viram 0,57 e 0,62, cena 1.1), e a largura cai nos dois braços.

3.5 O que não é bandit. Quando a escolha de hoje muda o estado de amanhã, o problema é de aprendizado por reforço completo. Uma recompensa fácil de enganar ensina o laço a enganar a recompensa: o ucb_gap depende da premissa calibrated. ⚠ O roteiro não cita um trabalho específico de reward hacking.

9. Fontes

1. Netflix Tech Blog, "Artwork Personalization at Netflix", 2017-12. https://netflixtechblog.com/artwork-personalization-c589f074ad76 (esta nota leu um resumo do post, não o texto completo)
2. Dezeen, "Netflix targets different film artworks to suit users' viewing habits", 2017-12-20. https://www.dezeen.com/2017/12/20/netflix-targets-film-artwork-depending-users-viewing-habits-design-technology/
3. Tony Jebara, "Artwork Personalization at Netflix", palestra de abertura, 2018. https://www.aicouncil.com/talks/artwork-personalization-at-netflix
4. Jaya Kawale e Elliot Chow, "A Multi-Armed Bandit Framework for Recommendations at Netflix", 2018. https://aicouncil.com/a-multi-armed-bandit-framework-for-recommendations-at-netflix
5. Slides de [4]. https://www.slideshare.net/slideshow/a-multiarmed-bandit-framework-for-recommendations-at-netflix/102629078
6. Li, Chu, Langford e Schapire, "A Contextual-Bandit Approach to Personalized News Article Recommendation" (LinUCB), 2010. https://arxiv.org/abs/1003.0146
7. Lattimore e Szepesvári, Bandit Algorithms, Cambridge University Press, 2020.
8. O roteiro do vídeo e o registro das fontes dele: script/, refs.bib, REFERENCES.md.
9. Tiago Motta, post sobre o serviço de bandit da globo.com, 2024-09-28. Chave motta2024bandit em [8].
10. Renan Moreira de Oliveira, "Machine Learning na globo.com", slides, 2018. Chave oliveira2018globo em [8].
11. Anthropic, "When AI builds itself", 2026. Chave anthropic2026builds em [8].
12. Resenha do artigo SIA (arXiv 2605.27276), 2026. Chave bhavsar2026sia em [8]; status partial.