Resumo Técnico: Identificação do Melhor Braço em Bandits Generalizados Lineares via Feedback Híbrido

Formulação do Problema

Este artigo aborda o problema de Identificação do Melhor Braço (BAI) com Confiança Fixa no âmbito dos Bandits Generalizados Lineares (GLBs) sob um modelo de feedback híbrido.

• Configuração: Um agente interage com $K$ braços, cada um associado a um vetor de características conhecido $x_i \in \mathbb{R}^d$ e um parâmetro latente desconhecido $\theta^*$. O objetivo é identificar o braço $i^*$ que maximiza a recompensa esperada $\mu_c(x_i^\top \theta^*)$ com probabilidade de pelo menos $1-\delta$, utilizando o número mínimo de amostras.
• Feedback Híbrido: Diferentemente dos cenários padrão de bandits que dependem de um único tipo de feedback, o agente pode escolher entre duas modalidades em cada rodada $t$:
  1. Recompensa Absoluta: Selecionar um braço $i$ e observar uma recompensa ruidosa $R_t \sim p_c(\cdot | x_i^\top \theta^*)$.
  2. Feedback Relativo (Duelo): Selecionar um par de braços $(j, k)$ e observar uma preferência binária $Y_t \in \{0, 1\}$ extraída de $p_d(\cdot | (x_j - x_k)^\top \theta^*)$, onde $Y_t=1$ indica preferência por $j$.
• Modelo Estatístico: Ambos os tipos de feedback são modelados como Modelos Lineares Generalizados (GLMs) que compartilham o mesmo parâmetro latente $\theta^*$, mas podem possuir diferentes funções de ligação, parâmetros de dispersão e perfis de curvatura. O objetivo é escolher adaptativamente a modalidade de feedback e os braços/pares específicos a serem consultados para minimizar o tempo de parada (ou custo total).

Metodologia

A solução proposta, HyTS-GLB (Track-and-Stop Híbrido para GLBs), integra inferência estatística com desenho experimental para lidar com a heterogeneidade do feedback.

1. Sequências de Confiança Unificadas

A contribuição estatística central é uma sequência de confiança baseada em razão de verossimilhança que unifica observações heterogêneas.

• Construção da Razão de Verossimilhança: Os autores estendem a estrutura de Lee et al. [2024] para observações híbridas. Eles definem uma log-verossimilhança negativa cumulativa $L_t(\theta)$ que agrega tanto as perdas de recompensa quanto as de duelo.
• Conjuntos de Confiança Elipsoidais: Sob a suposição de autoconcordância (uma propriedade das funções de ligação que garante derivadas de terceira ordem limitadas), os autores derivam um conjunto de confiança elipsoidal explícito $E_t(\delta)$.
  • O conjunto é definido como $\{ \theta : \|\theta - \hat{\theta}_t\|_{A_t}^2 \leq \beta_t(\delta) \}$, onde $\hat{\theta}_t$ é o Estimador de Máxima Verossimilhança (MLE) restrito.
  • A matriz $A_t$ é uma matriz de informação agregada que combina informações de curvatura de ambas as modalidades de feedback, ponderadas por suas frequências de amostragem e geometrias de características. Isso permite que o algoritmo trate o feedback absoluto e o relativo como uma fonte unificada de informação sobre o parâmetro latente.

2. Algoritmo Track-and-Stop Híbrido

Com base nos conjuntos de confiança, os autores propõem uma estratégia Track-and-Stop:

• Desenho Minimax-Ótimo: O algoritmo rastreia um vetor de proporção de amostragem $w$ que minimiza a largura de confiança no pior caso sobre todos os pares de braços. Especificamente, ele resolve um problema minimax para minimizar $\max_{i \neq \hat{i}^*_t} \|x_{\hat{i}^*_t, i}\|_{A(w, \hat{\theta}_t)^{-1}}^2$, onde $\hat{i}^*_t$ é o melhor braço empírico atual.
• Regra de Rastreamento: O agente seleciona ações para corresponder às proporções-alvo $w^*(t)$, incorporando um mecanismo de exploração forçada decrescente para garantir que a matriz de informação permaneça não degenerada.
• Regra de Parada: O algoritmo termina quando o melhor braço empírico atual é certificado como ótimo contra todos os concorrentes dentro do conjunto de confiança $E_t(\delta)$.

3. Extensão Consciente de Custos

A estrutura é estendida para um cenário consciente de custos onde consultas de recompensa e de duelo possuem diferentes custos de aquisição ($c_{reward}$ vs. $c_{dueling}$).

• O algoritmo otimiza um vetor de desenho normalizado por custo $p$ (intensidade de amostragem por unidade de custo) em vez de proporções de amostragem brutas.
• Isso permite que o agente troque ganho de informação contra custo monetário ou computacional, favorecendo adaptativamente a modalidade mais eficiente em termos de custo.

Principais Contribuições

1. Formulação Híbrida de GLM: O artigo formula a exploração pura com feedback de recompensa e de duelo sob uma parametrização GLM compartilhada. Diferentemente de modelos híbridos não estruturados, esta abordagem aproveita a estrutura latente compartilhada para transferir informação entre modalidades, acomodando diferentes verossimilhanças e curvaturas.
2. Sequências de Confiança Híbridas: Os autores desenvolvem uma única região de confiança elipsoidal explícita que agrega curvatura de Fisher heterogênea de ambos os canais de recompensa e duelo. Isso unifica a inferência e a parada, evitando a necessidade de reconciliar conjuntos de confiança separados.
3. Algoritmo Consciente de Geometria (HyTS-GLB): Eles propõem um algoritmo que rastreia um desenho minimax-ótimo sobre o espaço de ação conjunto de braços e pares de braços. O algoritmo é provado ser $\delta$-correto e fornece limites superiores de alta probabilidade para o tempo de parada.
4. Garantias Teóricas: O tempo de parada é mostrado como escalando com um tempo característico minimax $T^*(\theta^*)$, que captura a eficiência de informação conjunta do feedback híbrido. A variante consciente de custos alcança limites semelhantes para o custo total de aquisição.
5. Validação Empírica: Experimentos demonstram que a abordagem híbrida reduz significativamente a complexidade de amostragem em comparação com linhas de base de modalidade única (apenas recompensa ou apenas duelo). A variante consciente de custos adapta-se com sucesso a custos de consulta assimétricos.

Resultados e Desempenho

• Eficiência de Amostragem: Em experimentos sintéticos com modelos de observação logística, o HyTS-GLB supera consistentemente os métodos de base (Rage-GLM, ReTS-GLB, DuelTS-GLB) em várias dimensões. Ele alcança o menor tempo médio de parada na maioria das configurações, particularmente quando o feedback de recompensa e o de duelo fornecem informações complementares ao longo de direções diferentes.
• Adaptação de Custos: Quando os custos de feedback são assimétricos, a variante consciente de custos reduz o custo total em comparação com o HyTS-GLB padrão, deslocando a amostragem para a modalidade mais barata sem sacrificar a correção.
• Análise de Complexidade: A análise teórica mostra que a complexidade de amostragem é governada pelo tempo característico $T^*(\theta^*)$. O artigo fornece exemplos concretos onde o feedback de recompensa ou de duelo é mais informativo dependendo da geometria da instância, demonstrando que o algoritmo híbrido adapta-se dinamicamente a essas condições em vez de comprometer-se com uma única modalidade.

Significado e Afirmações

O artigo afirma fornecer uma estrutura estatística e algorítmica unificada para BAI com confiança fixa em bandits generalizados lineares com feedback híbrido.

• Integração Estatística: O trabalho vai além da fusão algorítmica (por exemplo, eliminação simples) para integração estatística, modelando feedbacks absoluto e relativo como observações distintas de uma utilidade latente compartilhada. Isso permite um uso mais eficiente dos dados ao aproveitar a estrutura de parâmetros compartilhada.
• Tratamento da Heterogeneidade: A sequência de confiança proposta lida com sucesso com os desafios estatísticos impostos por verossimilhanças heterogêneas e perfis de curvatura, fornecendo um único certificado de otimalidade que guia tanto a parada quanto a alocação.
• Relevância Prática: A estrutura aborda cenários do mundo real (por exemplo, RLHF, recomendadores conversacionais) onde os sistemas recebem feedback misto (classificações vs. preferências pareadas) e onde os custos de consulta podem variar.
• Modéstia na Otimalidade: Os autores reconhecem que, embora seu critério de desenho se alinhe com um relaxamento quadrático local do limite inferior teórico da informação, as garantias de tempo finito envolvem constantes conservadoras e fatores logarítmicos. Eles observam que obter algoritmos totalmente ótimos para instâncias gerais de GLMs permanece um problema em aberto, particularmente devido à não linearidade da divergência KL em GLMs.

Em resumo, o artigo estabelece que o feedback híbrido, quando processado através de uma estrutura GLM unificada com sequências de confiança autoconcordantes, pode superar estritamente estratégias de modalidade única em termos de eficiência de amostragem e de custo.