Resumo Técnico: Dueling Bandits Variância-Conscientes Neurais com Representação Profunda e Exploração Superficial

1. Formulação do Problema

O artigo aborda Dueling Bandits Contextuais (CDBs), um framework onde um agente observa um contexto, seleciona dois braços (ações) para comparar e recebe feedback binário de preferência (por exemplo, o braço $i$ é preferido ao braço $j$) em vez de recompensas numéricas. Embora a pesquisa existente em CDB frequentemente assuma funções de utilidade lineares, as preferências dos usuários do mundo real exibem frequentemente interações complexas e não lineares que modelos lineares não conseguem capturar.

Trabalhos recentes (Verma et al., 2024) tentaram abordar a não linearidade usando redes neurais, mas enfrentaram duas limitações críticas:

1. Ineficiência Computacional: Sua abordagem exigia a construção de uma matriz Gram usando gradientes de todos os parâmetros aprendíveis, levando a um sobrecarga computacional substancial ($O(p^3)$ onde $p$ é a contagem total de parâmetros).
2. Restrições Teóricas: A ausência de um estimador de forma fechada para o vetor de parâmetros $\hat{\theta}_{t-1}$ no cenário de duelos forçou trabalhos anteriores a assumir uma largura de rede neural extremamente grande ($m = \tilde{\Omega}(T^{14})$) para garantir arrependimento sublinear. Este requisito é inconsistente com resultados na literatura padrão de bandits neurais.

Além disso, os métodos existentes ignoram em grande parte a consciência de variância. Em bandits de duelo, o ruído do feedback (variância Bernoulli) é maximizado quando a diferença de utilidade entre os braços está próxima de zero (as comparações mais difíceis). Ignorar essa variância leva a um peso subótimo das observações.

2. Metodologia: NVLDB

Os autores propõem Dueling Bandits Lineares Variância-Conscientes Neurais (NVLDB), um framework que integra aprendizado de representação profunda com exploração superficial e ponderação consciente de variância.

2.1 Representação Profunda com Exploração Superficial

Em vez de usar o gradiente completo da rede neural, o NVLDB emprega uma estratégia de exploração superficial. Ele aproxima a função de utilidade não linear $u(x)$ usando uma rede neural profunda $f(x; \theta, W)$, mas constrói a matriz Gram $V_t$ usando apenas os gradientes dos parâmetros da camada final ($\theta$).

• Eficiência: Isso reduz a complexidade da inversão da matriz Gram de $\tilde{O}(p^3)$ para $\tilde{O}(d^3)$, onde $d$ é a dimensão do contexto, resultando em acelerações significativas.
• Tratamento de Viés: Tratar as camadas ocultas como extratores de características fixos introduz um viés de representação. Os autores contabilizam isso por meio de um termo de viés auxiliar em sua análise teórica.

2.2 Ponderação Consciente de Variância

O algoritmo estima a variância da distribuição subjacente de preferência Bernoulli, $\hat{\sigma}^2_t = g(\Delta f_t)(1 - g(\Delta f_t))$, onde $g$ é a função de ligação (por exemplo, Bradley-Terry-Luce).

• A função de perda é uma verossimilhança negativa ponderada, onde as observações são ponderadas por $1/\zeta_i^2$.
• $\zeta_i = \max\{\hat{\sigma}_i, \epsilon\}$ para variantes conscientes de variância, e $\zeta_i = 1$ para variantes agnósticas de variância.
• Essa ponderação atua como um filtro de informação, reduzindo o peso de observações incertas de pares com pequenas margens de utilidade (alta variância) para alcançar limites de arrependimento mais apertados.

2.3 Estratégias de Seleção de Braços

O NVLDB suporta tanto os frameworks de Limite Superior de Confiança (UCB) quanto de Amostragem de Thompson (TS) com três estratégias de seleção distintas:

1. Assimétrica (ASYM): Seleciona greedymente o primeiro braço e seleciona otimisticamente o segundo.
2. Simétrica Otimista (OSYM): Seleciona o par de braços que maximiza a soma das utilidades estimadas mais um bônus de exploração.
3. Simétrica Baseada em Candidatos (CSYM): Constrói um conjunto de confiança de candidatos fortes e seleciona o par com o bônus de exploração máximo.

• Novidade: As estratégias simétricas de TS (TS-OSYM, TS-CSYM) diferem dos trabalhos anteriores ao amostrar simultaneamente ambos os braços de uma posterior conjunta, em vez de sequencialmente.

3. Principais Contribuições Teóricas

A principal contribuição teórica do artigo é superar a falta de um estimador de forma fechada em bandits de duelo para reduzir a largura de rede necessária.

3.1 Abordagem Analítica Novel

Os autores introduzem um argumento de bootstrap combinado com análise espectral (usando o teorema Minimax de Courant-Fischer).

• Auto-melhoria Iterativa: Eles primeiro estabelecem um limite frouxo, dependente do tempo, sobre a norma do parâmetro $\|\theta_{t-1}\|_2$. Em seguida, substituem isso na análise para derivar um limite mais preciso, independente do tempo.
• Perturbação Espectral: Eles relacionam a matriz Gram das características atuais a uma matriz Gram perturbada, absorvendo o desvio de características em um fator multiplicativo.
• Resultado: Esta abordagem prova que a norma do estimador é limitada por uma constante independente do tempo, mesmo sem uma solução de forma fechada.

3.2 Limites de Arrependimento

Sob suposições padrão (contextos limitados, funções de ligação Lipschitz, espectro mínimo positivo do Kernel Tangente Neural), os autores provam arrependimento médio cumulativo sublinear:

• Consciente de Variância: $\tilde{O}\left(\sqrt{dT} + d\sqrt{\sum_{t=1}^T \sigma_t^2}\right)$.
• Agnóstico de Variância: $\tilde{O}(d\sqrt{T})$.
• Requisito de Largura de Rede: A análise reduz a largura de rede necessária para $m = \tilde{\Omega}(T^6)$, uma melhoria substancial sobre os $m = \tilde{\Omega}(T^{14})$ exigidos por Verma et al. (2024). Isso aproxima o requisito dos resultados padrão de bandits neurais ($\tilde{\Omega}(T^3)$), embora a lacuna permaneça devido aos desafios específicos do cenário de duelos.

4. Resultados Experimentais

Os autores validam o NVLDB em conjuntos de dados sintéticos e do mundo real.

• Tarefas Sintéticas: Usando funções de utilidade não lineares (cosseno, quadrado, matriz), as variantes do NVLDB superaram consistentemente as linhas de base (bandits de duelo lineares VACDB/ColSTIM e bandits de duelo neurais NDB) no arrependimento médio cumulativo.
• Conjuntos de Dados do Mundo Real: Experimentos em conjuntos de dados UCI (Statlog, Magic, Covertype) confirmaram arrependimento sublinear e desempenho superior. Notavelmente, no conjunto de dados Statlog com um modelo de preferência determinístico (baixa variância), as variantes conscientes de variância alcançaram arrependimento próximo de zero, superando significativamente as contrapartes agnósticas de variância.
• Escalabilidade: O método manteve arrependimento sublinear com dimensões mais altas ($d=100$) e redes mais amplas ($m=1000$).
• Eficiência: O NVLDB demonstrou uma aceleração massiva sobre métodos de gradiente completo (NDB), completando 2.000 rodadas em ~1,7 minutos, comparado a ~48,8 minutos para o NDB no mesmo hardware.

5. Significado e Alegações

O artigo afirma ser o primeiro a introduzir bandits de duelo neurais conscientes de variância utilizando uma estratégia de exploração superficial. Seu significado reside em:

1. Avanço Teórico: Resolve um gargalo crítico na análise teórica de bandits de duelo neurais provando arrependimento sublinear sob uma condição de largura de rede significativamente mais fraca ($T^6$ vs. $T^{14}$) através de uma combinação novel de argumentos de bootstrap e análise espectral.
2. Eficiência Prática: Ao aproveitar a exploração superficial, torna os bandits de duelo neurais computacionalmente viáveis para aplicações em grande escala, reduzindo os custos de inversão de matriz Gram em ordens de magnitude.
3. Consciência de Variância: Demonstra que incorporar estimativas de variância (ponderação por inverso da variância) leva a limites de arrependimento mais apertados e desempenho empírico superior, particularmente em regimes de baixa variância.

Os autores reconhecem que, embora $m = \tilde{\Omega}(T^6)$ seja uma melhoria significativa, fechar a lacuna para o requisito de $\tilde{\Omega}(T^3)$ encontrado em CMABs neurais padrão permanece uma direção para trabalho futuro, principalmente devido à dificuldade inerente do estimador de forma fechada no cenário de duelos.