Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

1. Problema e Contexto

O problema central abordado é o Bandit de Múltiplos Braços (MAB), um framework clássico para tomada de decisão sequencial sob incerteza. Tradicionalmente, algoritmos de MAB dependem exclusivamente de dados online (recompensas observadas após a seleção de uma ação), o que pode ser escasso e custoso de coletar.

O artigo introduz um novo cenário onde o agente de decisão tem acesso a dados offline ricos (históricos) e informações laterais (covariáveis) antes de iniciar a fase online. A inovação reside no uso de Modelos de Aprendizado de Máquina (ML) pré-treinados para converter essas informações laterais em recompensas surrogadas (proxy rewards).

Desafios Principais:

• Viés (Bias): As recompensas surrogadas geradas por ML podem ser altamente enviesadas em relação às recompensas verdadeiras, especialmente quando o modelo precisa extrapolar para ambientes não vistos (novos parâmetros ou intervenções).
• Ranking Inadequado: A média das recompensas surrogadas pode não preservar a ordem das médias das recompensas verdadeiras, tornando inútil a simples seleção do braço com a maior recompensa surrogada média.
• Correlação: Embora enviesadas, as recompensas surrogadas geralmente são correlacionadas com as recompensas verdadeiras. O objetivo é explorar essa correlação para reduzir a variância da estimativa, sem depender do conhecimento prévio da matriz de covariância ou do viés exato.

2. Metodologia: Algoritmo MLA-UCB

Os autores propõem o algoritmo MLA-UCB (Machine Learning-Assisted Upper Confidence Bound), que integra a inferência impulsionada por previsão (Prediction-Powered Inference - PPI) ao framework clássico UCB.

A. Estimador de Média Assistido por ML

O núcleo do método é um novo estimador para a média de recompensa de cada braço $k$, denotado por $\hat{\mu}^{MLA}_{k,n}$. Ele combina:

1. Dados Online: Recompensas verdadeiras ($R$) e surrogadas ($\hat{R}$) observadas durante a exploração.
2. Dados Offline: Um conjunto estático de recompensas surrogadas ($\hat{R}^{off}$) disponíveis antes do início do processo.

O estimador é definido como:
$$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}^{off}_{k})$$
Onde:

• $\bar{R}_{k,n}$ é a média das recompensas verdadeiras online.
• $\bar{\hat{R}}_{k,n}$ e $\bar{\hat{R}}^{off}_{k}$ são as médias das recompensas surrogadas online e offline, respectivamente.
• $\hat{\lambda}_{k,n}$ é um coeficiente de ajuste (plug-in estimate) que minimiza a variância, atuando como um controle de variância.

Este estimador é matematicamente equivalente ao intercepto de uma regressão linear (OLS) onde a recompensa verdadeira é regredida contra a recompensa surrogada, centrada na média global (online + offline).

B. Construção do Limite de Confiança (Upper Confidence Bound)

Diferente do UCB clássico que assume variância conhecida ou usa limites conservadores baseados em sub-Gaussianos, o MLA-UCB:

• Não requer conhecimento prévio da variância das recompensas verdadeiras ou da covariância entre verdadeiras e surrogadas.
• Utiliza uma análise exata da distribuição finita (sob o pressuposto de Gaussianidade conjunta) para construir limites de confiança.
• Inverte um teste t de uma amostra com um nível de significância dependente da rodada ($t$) e uma estimativa de variância robusta.
• A cota superior (UCB) para o braço $k$ na rodada $t$ é:
  $$UCB_{k,t} = \hat{\mu}^{MLA}_{k,n_k,t} + q_{n_k,t-2}(\delta_t) \cdot \sqrt{\text{Variância Estimada}}$$
  Onde o termo de variância incorpora a redução de variância devido à correlação $\rho_k$.

C. Extensão para Recompensas em Lotes (Batched) e Não-Gaussianas

O artigo estende o método para cenários onde as decisões são aplicadas a lotes de indivíduos (comum em regulamentações ou logística).

• Assume-se que as recompensas individuais podem ser não-Gaussianas.
• Utiliza-se limites de grandes desvios moderados auto-normalizados (self-normalized moderate deviation bounds) para garantir a validade dos limites de confiança, aproveitando a normalidade aproximada induzida pelo Teorema do Limite Central em lotes grandes.

3. Principais Contribuições

1. Novo Setting de MAB: Formalização do uso de recompensas surrogadas geradas por ML que podem ser arbitrariamente enviesadas, mas correlacionadas com a verdade.
2. Algoritmo MLA-UCB: Desenvolvimento de um algoritmo que:
   • Funciona sem conhecimento prévio da matriz de covariância ou do viés.
   • É aplicável a qualquer modelo de previsão de recompensa e qualquer forma de dados auxiliares.
   • Garante melhoria teórica no arrependimento (regret) mesmo quando o viés é grande.
3. Análise Teórica Rigorosa:
   • Derivação de um limite superior de arrependimento (regret upper bound) que melhora estritamente o limite clássico do UCB quando a correlação $\rho_k \neq 0$.
   • Prova de optimalidade assintótica: O algoritmo atinge o limite inferior de arrependimento (lower bound) para políticas uniformemente boas, desde que o tamanho da amostra offline seja polilogarítmico.
   • Demonstração de que a redução de arrependimento é proporcional a $(1 - \rho_k^2)$, efetivamente reduzindo a variância da estimativa.
4. Generalização: Extensão para cenários de recompensas em lotes e distribuições não-Gaussianas, com garantias computáveis.

4. Resultados

Simulações Numéricas

• Cenário Gaussiano: O MLA-UCB demonstrou reduções significativas no arrependimento cumulativo em comparação com o UCB clássico. A melhoria aumenta com o tamanho da amostra offline ($N$) e a força da correlação ($\rho$).
• Cenário Não-Gaussiano (ML Real): Testes com modelos de ML reais (Regressão Linear, SVR, Redes Neurais, Árvores de Decisão) gerando recompensas surrogadas para funções não-lineares complexas. Mesmo quando a suposição de Gaussianidade é violada e modelos simples (como regressão linear) falham em capturar a não-linearidade, o MLA-UCB ainda superou o UCB clássico, mostrando robustez.
• Recompensas em Lotes: O algoritmo adaptado para lotes manteve a redução de variância e o desempenho superior.

Estudos de Caso do Mundo Real

1. Seleção de Modelos de Linguagem (LLMs):
   • Contexto: Escolher entre modelos proprietários caros (GPT-4, Claude) usando modelos open-source locais (Llama) como surrogados.
   • Resultado: O MLA-UCB reduziu o arrependimento ao identificar o modelo mais preciso mais rapidamente, utilizando a precisão do modelo open-source como proxy, mesmo com viés de ranking.
2. Recomendação de Vídeo:
   • Contexto: Maximizar o tempo de visualização (watch ratio) em uma plataforma de vídeo.
   • Resultado: Uso de features de usuários e itens para treinar um modelo de regressão e gerar surrogados. O algoritmo demonstrou ganhos consistentes sobre o UCB padrão, validando a eficácia em dados reais com distribuições complexas.

5. Significado e Impacto

Este trabalho é significativo porque ponteia a lacuna entre a inferência estática baseada em ML e a tomada de decisão dinâmica sequencial.

• Viabilidade Prática: Permite que organizações utilizem vastos conjuntos de dados históricos e modelos de IA modernos para acelerar a exploração em sistemas de recomendação, testes clínicos e otimização de preços, sem precisar esperar por recompensas verdadeiras (que podem ser caras ou demoradas).
• Robustez ao Viés: Ao contrário de abordagens anteriores que exigiam que os dados offline fossem não enviesados ou que o viés fosse limitado, o MLA-UCB é robusto a grandes viéses, explorando apenas a correlação para reduzir a incerteza.
• Eficiência de Amostragem: Demonstra que, com um número moderado de amostras offline, é possível alcançar uma eficiência de amostragem online muito superior, reduzindo custos operacionais e riscos em aplicações críticas.

Em resumo, o paper estabelece um novo paradigma onde o aprendizado de máquina não é apenas uma ferramenta de previsão, mas um componente integral e matematicamente fundamentado para otimizar a exploração em ambientes de decisão sequencial.