Resumo Técnico: Além do Viés Estático: Bandits Multi-Fidelidade Adaptativos com Proxies em Melhoria

Definição do Problema

Este trabalho aborda uma extensão específica do problema de bandit multi-braço estocástico (MAB) conhecida como Bandits Multi-Braço Multi-Fidelidade (MF-MAB). Em configurações padrão de MF-MAB, os braços podem ser avaliados usando múltiplas fontes de feedback (fidelidades) que equilibram custo e precisão. Estruturas tradicionais assumem um viés estático entre fontes de baixa fidelidade (baratas) e alta fidelidade (caras); a discrepância é fixa, independentemente de quantas vezes a fonte de baixa fidelidade é consultada.

No entanto, aplicações modernas envolvendo simuladores baseados em aprendizado e Modelos de Linguagem Grandes (LLMs) como avaliadores exibem uma dinâmica diferente: a fonte proxy de baixa fidelidade pode melhorar com calibração adicional ou uso repetido. O artigo investiga uma configuração de MF-MAB com restrição orçamentária onde:

1. Existem $K$ braços com uma média alvo de alta fidelidade estacionária $\mu^{(H)}_k$.
2. Uma fonte de baixa fidelidade fornece observações $Y^{(L)}_{k,\tau}$ que evoluem com base no número de consultas $\tau$ feitas a esse braço específico.
3. A fonte de baixa fidelidade começa com uma incompatibilidade em relação ao alvo de alta fidelidade, mas essa incompatibilidade diminui à medida que a fonte é consultada com mais frequência (por exemplo, via calibração).
4. O objetivo é minimizar o pseudo-arrependimento ponderado por custo, definido como o custo cumulativo incorrido ao selecionar braços subótimos, em vez de apenas o número de puxadas.

O desafio central é determinar quando parar de consultar a fonte de baixa fidelidade em melhoria e escalar para a fonte cara de alta fidelidade. Uma regra de limite estática pode escalar muito cedo, perdendo a oportunidade de a fonte de baixa fidelidade se tornar suficientemente precisa através da amostragem barata contínua.

Metodologia

Modelagem do Proxy em Melhoria

Os autores introduzem um limite de incompatibilidade de média selecionada para capturar a discrepância em evolução. Em vez de assumir um viés fixo $|\mu^{(L)}_k - \mu^{(H)}_k| \le \zeta$, eles assumem um certificado em evolução $U_k(n)$ tal que a incompatibilidade cumulativa é limitada:
$$\sum_{\tau=1}^n |\mu^{(L)}_k(\tau) - \mu^{(H)}_k| \le U_k(n)$$
Isso leva a um limite de incompatibilidade de média selecionada $B_k(n) = \sup_{s \ge n} U_k(s)/s$, que limita a discrepância entre a média empírica de baixa fidelidade e o alvo verdadeiro de alta fidelidade. À medida que $n$ aumenta, $B_k(n)$ diminui, refletindo a confiabilidade crescente do proxy.

O Algoritmo TACC

O artigo propõe o algoritmo Companheiro de Continuação Adaptativa Baseado em Limiar (TACC). O TACC opera em um modelo baseado em confiança, mas introduz uma nova regra de continuação limitada para a fonte de baixa fidelidade.

1. Limites de Confiança: O TACC constrói Limites Superiores de Confiança (UCB) para o alvo de alta fidelidade $\mu^{(H)}_k$ usando ambas as fidelidades.
   • UCB de alta fidelidade: Intervalo estatístico padrão.
   • UCB de baixa fidelidade: Intervalo estatístico padrão mais a correção de incompatibilidade $B_k(n)$.
2. Seleção de Braço: O algoritmo seleciona o braço com a pontuação otimista mais alta, definida como o mínimo dos UCBs de baixa e alta fidelidade.
3. Seleção de Fidelidade (A Inovação Central):
   • Pré-Limiar: Se a incerteza estatística de baixa fidelidade (raio) estiver acima de um limiar $\gamma$, o algoritmo continua amostrando em baixa fidelidade.
   • Pós-Limiar: Uma vez que o raio estatístico cai abaixo de $\gamma$, uma regra estática escalaria imediatamente para alta fidelidade. O TACC, no entanto, verifica se uma continuação limitada é custo-efetiva.
   • Regra de Continuação: O algoritmo calcula a diminuição antecipada na correção de incompatibilidade $V_{k,t}(s)$ se $s$ consultas adicionais de baixa fidelidade forem feitas. Se a redução na incompatibilidade for suficiente para potencialmente certificar a subotimidade do braço sem confirmação de alta fidelidade, e o custo dessas consultas adicionais for limitado (especificamente, $S_0 \lambda^{(L)} \le \lambda^{(H)}$), o TACC continua amostrando em baixa fidelidade. Caso contrário, ele escala para alta fidelidade.

Contribuições Principais

1. Formulação do Problema: O artigo formaliza a configuração de MF-MAB com fontes proxy em melhoria, indo além da suposição de viés estático prevalente na literatura anterior. Ele introduz o limite de incompatibilidade de média selecionada para modelar a redução dinâmica da discrepância.
2. Design do Algoritmo: O TACC é proposto como um algoritmo otimista que combina seleção padrão de braços com uma regra de continuação pós-limiar limitada. Essa regra decide explicitamente se a "melhoria" da fonte de baixa fidelidade justifica adiar a consulta cara de alta fidelidade.
3. Análise Teórica: Os autores derivam um limite de arrependimento dependente da instância. A análise particiona braços subótimos em três classes:
   • Braços fáceis ($A_\gamma$): Certificados por baixa fidelidade antes do limiar.
   • Braços intermediários ($C_\gamma$): Não certificados no limiar estático, mas tornam-se certificáveis após continuação limitada de baixa fidelidade.
   • Braços difíceis ($H_\gamma$): Requerem confirmação de alta fidelidade.
     O limite demonstra que, para braços intermediários detectados, o TACC substitui o custo de confirmação de alta fidelidade logarítmico por um custo de continuação de baixa fidelidade limitado.
4. Validação Empírica: Experimentos em bandits sintéticos e uma tarefa de avaliação de política controlada de LLM-como-juiz demonstram que o TACC reduz o arrependimento ponderado por custo em comparação com regras multi-fidelidade estáticas (MF-UCB) e baselines apenas de alta fidelidade (UCB).

Resultados

Experimentos Sintéticos

Em configurações sintéticas com 200 e 500 braços, o TACC consistentemente alcançou um arrependimento ponderado por custo menor do que UCB, MF-UCB e regras estáticas de duas fidelidades. A vantagem foi mais pronunciada em cenários com altos custos de alta fidelidade (por exemplo, $\lambda^{(H)} = 50$), onde evitar confirmações desnecessárias de alta fidelidade via continuação limitada gerou economias significativas.

Experimento LLM-como-Juiz

Os autores avaliaram o TACC em um pipeline de avaliação de política onde os braços eram políticas de prompt para Inferência de Linguagem Natural (NLI).

• Configuração: Baixa fidelidade foi um "juiz fraco" (um LLM menor) que melhorou com calibração; alta fidelidade foi um "verificador" (verdade fundamental).
• Descobertas: O TACC superou todas as baselines, incluindo uma ablação direta (DNC) que usava os mesmos limites de incompatibilidade, mas carecia da lógica de continuação. O TACC reduziu o arrependimento ponderado por custo final em aproximadamente 10-20% em comparação com as melhores baselines estáticas, confirmando que o mecanismo de continuação limitada aproveita efetivamente a natureza em melhoria do juiz fraco para evitar escalada prematura para o verificador caro.

Significado e Alegações

O artigo afirma que o principal significado deste trabalho reside em reconhecer que fontes proxy em sistemas de IA modernos não são estáticas. Ao tratar a fonte de baixa fidelidade como uma entidade em melhoria, os autores mostram que a estratégia ótima não é apenas alternar fidelidades com base na incerteza atual, mas continuar adaptativamente amostrando a fonte barata se for esperado que ela melhore o suficiente para resolver ambiguidades.

Os autores enquadram modestamente sua contribuição como um modelo canônico de duas fidelidades. Eles reconhecem limitações, observando que o trabalho atual assume um limite de incompatibilidade conhecido e foca na evolução local do braço (onde a melhoria ocorre apenas quando um braço específico é consultado), em vez de ajuste fino global do modelo que afeta todos os braços simultaneamente. O trabalho serve como um passo fundamental para estratégias de alocação de fidelidade mais complexas e dinâmicas em cenários envolvendo LLMs e simuladores baseados em aprendizado.