Braços, Puxadas, Recompensas
Uma Fileira de Máquinas Caça-Níqueis
Imagine K máquinas caça-níqueis alinhadas. Cada máquina paga uma recompensa média diferente, mas você não conhece nenhuma das médias. A cada passo você escolhe uma máquina, puxa sua alavanca & observa um pagamento. Seu objetivo: maximizar a recompensa total em muitas puxadas.
Essa configuração define um problema de multi-armed bandit. K = número de braços. Uma puxada escolhe um braço. A recompensa vem da distribuição oculta desse braço. A mean_reward(k) do braço k rastreia a média móvel nas puxadas de k.
Exploração vs Exploração
Duas pressões se opõem uma à outra:
Exploração puxa o braço com a maior média de recompensa observada. Gananciosa. Risco: um braço que parecia ótimo após 2 puxadas pode regredir para uma média verdadeira mais baixa.
Exploração puxa um braço menos testado para reduzir a incerteza. Risco: o tempo gasto explorando custa recompensas que você poderia ter coletado de um braço conhecido como bom.
Uma boa política mistura ambas. Exploração pura fixa os vencedores iniciais para sempre. Exploração pura nunca coleta uma recompensa.
Braços de ANDREA = Fontes de Dados
ANDREA enquadra o treinamento como um bandit. Cada fonte de dados (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, etc.) atua como um braço. Cada passo de treinamento puxa um braço: carrega um documento dessa fonte, executa uma passada forward, observa a redução de perda. Recompensa média por fonte rastreia quanto essa fonte melhora a perda em média.
Por que isso se encaixa: as necessidades do modelo mudam durante o treinamento. Passos iniciais se beneficiam de exposição ampla (muitas fontes). Passos posteriores se beneficiam de polimento direcionado (poucas fontes de alta recompensa). Um bandit se adapta; uma razão de amostragem fixa não pode.
Nomeando as Peças
A Pontuação UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer e colegas publicaram o UCB1 em 2002 como uma política de bandit de tempo finito com um limite de regret de O(log N). O UCB1 escolhe um braço combinando sua recompensa média atual com um bônus de exploração que diminui à medida que o braço é puxado.
A Fórmula
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Termo por termo:
- mean_reward(k): recompensa média observada para o braço k em suas n_k puxadas. Termo de exploração.
- N: puxadas totais em todos os braços até agora. Cresce a cada passo.
- n_k: puxadas do braço k especificamente. Cresce apenas quando k é escolhido.
- C: constante de exploração. Valor padrão de livro didático: 1.4 (sqrt(2)). ANDREA usa C=0.5.
- sqrt(ln(N) / n_k): raio de confiança. Um braço raramente puxado tem n_k pequeno e recebe um bônus grande; um braço bem puxado tem n_k grande e recebe um bônus pequeno.
Por que a Fórmula Funciona
ln(N) cresce lentamente (logarítmico), então o numerador sobe suavemente com a experiência total. n_k no denominador reduz o termo à medida que evidências se acumulam para um braço específico. Raiz quadrada suaviza a resposta, o que impede que um único braço subexplorado domine para sempre.
Escolher por argmax_k UCB(k) a cada passo equilibra automaticamente ambas as pressões. Sem parâmetro epsilon, sem cronograma, sem temperatura. A matemática cuida disso.
Calcular uma Pontuação UCB
Por que C=0.5 em vez de 1.4
O Valor do Livro-Texto
Auer, Cesa-Bianchi & Fischer derivam uma garantia de arrependimento assumindo que as recompensas estão em [0, 1]. A garantia vale para C = sqrt(2) approx 1.414. A maioria dos livros-texto ensina C=1.4 como um padrão seguro.
Magnitude das Recompensas do ANDREA
O ANDREA reporta melhorias de perda por passo como recompensa. As melhorias brutas ficam em torno de 0.001 (perda cai de 4.521 para 4.520). Após o fator de escala 1000x (coberto na atividade 78, atribuição de recompensa), as recompensas escaladas ficam próximas de 1.0 em magnitude. As recompensas médias ao longo da história de um braço se estabilizam em uma faixa de 0.5 a 3.0.
Agora considere o bônus de exploração com C=1.4, N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 está dentro da banda de recompensa. Tolerável. Agora n_k=10 (um braço raro):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 está ACIMA da maioria das mean_rewards observadas. Exploração domina: o braço raro vence independentemente de sua média real. Com muitas fontes e execuções de treinamento longas, isso inunda o cronograma com braços de baixa média.
A Solução: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 fica abaixo da maioria das médias de recompensa. A exploração ainda acontece (braços raros ainda recebem um bônus), mas mean_reward lidera. ANDREA explora mais, explora menos, & evita dominância de exploração.
Ajuste Fino como Engenharia, Não Teoria
A bound do livro didático assume recompensas em [0, 1]. As recompensas da ANDREA vivem aproximadamente em [0, 5]. Escalar a constante ajusta a constante à magnitude da recompensa. Mesmo algoritmo, ambiente calibrado.
Dominância de Exploração no Diagnóstico
Próximo
O Que Você Tem
UCB1 escolhe o braço com o maior limite superior de confiança. O limite combina mean_reward (explorar) com sqrt(ln(N) / n_k) escalado por C (explorar). ANDREA ajusta C=0.5 porque as recompensas por passo estão em uma faixa de 0.5 a 3.0, & o valor de 1.4 do livro didático inunda o cronograma com braços de baixa média.
O Que Resta
Vanilla UCB1 escolhe um braço por vez. ANDREA escolhe vários braços de foco por fase, mistura braços aleatórios primeiro, & mantém cada fase por 7 a 42 passos. Essa estrutura (atividade 77: fases de dados) impede que o UCB se comprometa excessivamente com vencedores iniciais, enquanto ainda permite concentrar o esforço.
Atribuição de recompensa (atividade 78) mostra de onde o mean_reward(k) realmente vem. Limites inferiores & penalidades de época (atividade 79) adicionam regras protetoras sobre a saída do UCB.
Referência
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- Whitepaper ANDREA, seções 3.1 & 3.4.