Resumo Técnico: Bandits Dueling Lineares e Neurais com Feedback Atrasado

1. Definição do Problema

O artigo aborda o problema de Bandits Dueling Contextuais (CDB) sob Feedback Atrasado Estocástico. Em configurações padrão de CDB, um agente seleciona um par de braços (candidatos) e recebe feedback binário de preferência imediato (por exemplo, $x_1 \succ x_2$) para aprender uma função de recompensa latente. No entanto, em aplicações do mundo real, como alinhamento de Modelos de Linguagem de Grande Escala (LLM), otimização de prompts e publicidade programática, o feedback é frequentemente assíncrono.

O cenário específico formalizado neste trabalho assume:

• Atrasos Estocásticos: O feedback para uma ação tomada na rodada $s$ chega após um atraso aleatório $D_s$.
• Limite Rígido: Existe uma janela de observação máxima $M$. Se $D_s > M$, o feedback é tratado como ausente (censurado).
• Probabilidade de Observação: A probabilidade de o feedback chegar dentro da janela é $\rho = P(D_s \le M)$.
• Desafio de Viés: Diferentemente dos bandits lineares, onde os estimadores possuem soluções de forma fechada (por exemplo, regressão ridge), os bandits dueling dependem da Estimativa de Máxima Verossimilhança (MLE) sob o modelo Bradley-Terry-Luce (BTL). A falta de soluções de forma fechada significa que adaptações ingênuas de técnicas padrão de feedback atrasado (como imputação simples ou ignorar dados ausentes) introduzem um viés sistemático que não pode ser facilmente limitado ou corrigido.

2. Metodologia

Os autores propõem dois algoritmos inovadores projetados para lidar com esses atrasos sem imputação heurística: Bandits Dueling Lineares com Feedback Atrasado (LDB-DF) e Bandits Dueling Neurais com Feedback Atrasado (NDB-DF).

Mecanismo Central: Ponderação por Probabilidade Inversa (IPW)

A inovação central é a integração de um mecanismo de Ponderação por Probabilidade Inversa (IPW) diretamente na função de perda.

• Estratégia de Ponderação: Para uma instância de feedback $y_s$ observada na rodada $t$ (onde $s < t$), o algoritmo atribui um peso $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$.
• Correção Sem Viés: Ao escalar a contribuição do feedback observado por $1/\rho$, o gradiente esperado da perda substituta torna-se um estimador não viesado do gradiente verdadeiro, neutralizando efetivamente o viés introduzido pelo mecanismo de observação estocástica e pelos dados ausentes.

Algoritmo 1: LDB-DF (Configuração Linear)

• Modelo: Assume uma função de recompensa linear $f(x) = \theta^\top \phi(x)$.
• Estimação: Minimiza uma perda logística regularizada por IPW usando apenas o feedback "chegado".
• Exploração: Utiliza uma estratégia de Limite Superior de Confiança (UCB). O primeiro braço é selecionado de forma gananciosa com base na estimativa atual $\theta_t$. O segundo braço é selecionado para maximizar o UCB da diferença de preferência em relação ao primeiro braço, incorporando um raio de confiança $\beta_t$ que leva em conta tanto o ruído estocástico quanto a incerteza induzida pelo atraso.
• Matriz de Informação: Atualizada imediatamente usando vetores de características dos pares selecionados, independentemente da latência do feedback.

Algoritmo 2: NDB-DF (Configuração Neural)

• Modelo: Aproxima a função de recompensa não linear usando uma rede neural totalmente conectada $h(x; \theta)$ com ativações ReLU.
• Estimação: Treina a rede online usando a mesma perda de entropia cruzada ponderada por IPW, aprendendo apenas com o subconjunto de feedback que chegou dentro da janela válida.
• Estrutura Teórica: A análise é conduzida no regime de Kernel Tangente Neural (NTK). O algoritmo assume que a rede é suficientemente larga ($m$) para que se comporte aproximadamente como uma função linear no espaço de características do gradiente na inicialização.
• Exploração: Similar ao caso linear, emprega uma estratégia UCB. O bônus de exploração é derivado do espaço de características do NTK, quantificando a incerteza epistêmica na diferença de preferência.

3. Contribuições Teóricas

O artigo fornece limites rigorosos de arrependimento para ambas as configurações, caracterizando explicitamente o impacto dos parâmetros de atraso ($M$ e $\rho$).

• Limite de Arrependimento Linear: O arrependimento cumulativo para LDB-DF é estabelecido como $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$.

  • O termo $\frac{M}{\rho}$ atua como uma penalidade multiplicativa. Uma menor probabilidade de observação $\rho$ (menos amostras) e um limite maior $M$ (atrasos potenciais mais longos) aumentam linearmente o arrependimento.
  • Quando $\rho=1$ e $M=1$ (sem atraso), o limite recupera o estado da arte $\tilde{O}(d\sqrt{T})$ para bandits dueling lineares padrão.

• Limite de Arrependimento Neural: O arrependimento cumulativo para NDB-DF é estabelecido como $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$, onde $\tilde{d}$ é a dimensão efetiva da matriz NTK.

  • A prova depende de uma técnica de decomposição "adicionar e subtrair" inovadora para separar o ruído da martingala do viés sistemático induzido pelos atrasos.
  • A análise confirma que a dificuldade fundamental do problema (trade-off entre a probabilidade de observação e a magnitude do atraso) persiste mesmo com aproximadores de função não lineares complexos.

4. Resultados Experimentais

Os autores avaliam LDB-DF e NDB-DF contra linhas de base que ignoram atrasos ou usam imputação heurística.

• Linhas de Base:
  • Ignorar: Usa a mesma arquitetura de modelo, mas descarta o feedback pendente até a chegada sem ponderação.
  • Heurística: Imputa feedback ausente usando a preferência prevista pelo modelo atual (proxy viesado).
• Conjuntos de Dados:
  • Sintético: Funções de recompensa Linear, Quadrática e Cúbica com atrasos geométricos estocásticos.
  • Mundo Real: Otimização Automatizada de Prompts usando o benchmark InstructZero (29 tarefas de indução de instruções).
• Descobertas:
  • Ambos os algoritmos propostos superam significativamente as linhas de base em termos de arrependimento cumulativo.
  • Em configurações não lineares, a linha de base Heurística frequentemente converge para regiões subótimas devido a erros de previsão de auto-reforço (alucinações), enquanto a linha de base Ignorar sofre com a escassez de dados.
  • LDB-DF e NDB-DF demonstram robustez à latência do feedback, navegando efetivamente pelo espaço de busca em tarefas de otimização de prompts.

5. Significado e Alegações

O artigo afirma preencher uma lacuna crítica na aprendizagem baseada em preferências ao fornecer o primeiro framework unificado que lida simultaneamente com:

1. Feedback de Preferência (Dueling): Resultados relativos binários em vez de recompensas absolutas.
2. Aproximação Não Linear (Neural): Paisagens de recompensa complexas via redes neurais.
3. Atrasos Estocásticos/Dados Ausentes: Latência de feedback realista e censura.

Os autores enfatizam que sua abordagem se afasta da imputação heurística, oferecendo uma solução principial e sem viés via IPW. A análise teórica estabelece os primeiros limites de arrependimento para esta configuração específica, demonstrando que a degradação de desempenho é previsível e depende linearmente das características do atraso ($M/\rho$). O trabalho é posicionado como um passo fundamental para melhorar a aprendizagem de preferências assíncrona em sistemas com humanos no loop, particularmente para alinhamento de LLMs e otimização de prompts.