Spectral bandits for smooth graph functions with applications in recommender systems

Resumo Técnico: Bandits Espectrais para Funções Suaves em Grafos

Formulação do Problema
Este artigo aborda um problema de bandit de múltiplos braços onde os braços correspondem aos nós de um grafo conhecido $G=(V, E)$, e o retorno esperado de puxar um braço é determinado por uma função suave definida no grafo. Neste cenário, a função de recompensa $f$ é assumida como uma combinação linear dos autovetores do Laplaciano do grafo $L$. Especificamente, se $Q$ contém os autovetores de $L$ como colunas, a recompensa para o nó $v$ é $f_\alpha(v) = \langle x_v, \alpha^* \rangle$, onde $x_v$ é a $v$-ésima linha de $Q$ e $\alpha^*$ é um vetor de pesos desconhecido.

O desafio central surge quando o número de nós $N$ (e, portanto, a dimensão do espaço de características $D=N$) é muito grande, potencialmente excedendo o horizonte temporal $T$ do processo de aprendizado ($T < N$). Algoritmos padrão de bandit linear, que tipicamente escalonam seu arrependimento com a dimensão ambiente $D$ ou o número de braços $K$, performariam mal neste regime. O artigo assume que a função verdadeira é "suave", significando que os coeficientes $\alpha^*$ associados aos autovetores correspondentes a grandes autovalores são pequenos, enquanto aqueles associados a pequenos autovalores são maiores.

Metodologia
Os autores propõem dois algoritmos que aproveitam as propriedades espectrais do grafo para alcançar limites de arrependimento que escalonam com uma "dimensão efetiva" $d$ em vez da dimensão completa $N$.

1. Dimensão Efetiva ($d$): O artigo introduz uma definição formal de dimensão efetiva $d$ baseada no crescimento dos autovalores do Laplaciano regularizado $\Lambda = \Lambda_L + \lambda I$. $d$ é definido como o maior inteiro tal que $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$. Esta métrica captura o número de dimensões "relevantes" no problema, que é tipicamente muito menor que $N$ em grafos do mundo real.

2. SpectralUCB: Este algoritmo é uma modificação do algoritmo LinUCB. Ele emprega um estimador de mínimos quadrados regularizado para $\alpha^*$ usando a base espectral. Crucialmente, constrói limites de confiança para as recompensas previstas usando a dimensão efetiva $d$ em vez da dimensão ambiente $D$. O algoritmo seleciona o nó que maximiza o limite superior de confiança: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$, onde $c_t$ depende de $d$.

3. Amostragem de Thompson Espectral (SpectralTS): Este algoritmo utiliza uma abordagem bayesiana. Mantém uma distribuição posterior sobre $\alpha^*$, modelada como uma Gaussiana $N(\hat{\alpha}_t, v^2 V_t^{-1})$. A covariância a priori é definida como o Laplaciano regularizado $\Lambda$, codificando a suposição de que funções suaves (componentes de baixo autovalor) são mais prováveis. Em cada passo, uma amostra $\tilde{\alpha}$ é retirada da posterior, e o nó que maximiza $x_v^T \tilde{\alpha}$ é selecionado.

Principais Contribuições e Resultados Teóricos

• Novo Framework: Este é o primeiro trabalho a formalizar problemas de bandit onde as recompensas são funções suaves em um grafo, conectando aprendizado de variedades/aprendizado semi-supervisionado com aprendizado online.
• Limites de Arrependimento: O artigo prova que tanto o SpectralUCB quanto o SpectralTS alcançam limites de arrependimento cumulativo que escalonam com a dimensão efetiva $d$:
  • SpectralUCB: $O(d\sqrt{T \ln T})$.
  • SpectralTS: $O(d\sqrt{T \ln N})$.
    Estes limites são significativos porque $d$ é frequentemente muito menor que $N$, permitindo que os algoritmos performem bem mesmo quando $T < N$.
• Eficiência Computacional: Os autores destacam uma vantagem computacional para o SpectralTS. Enquanto o SpectralUCB requer o cálculo de limites de confiança para todos os $N$ braços (levando a uma complexidade de $O(N^3)$ por passo no pior caso onde $D=N$), o SpectralTS requer apenas amostrar um vetor de parâmetros e encontrar o máximo, o que pode ser feito de forma mais eficiente ($O(N^2)$ por passo).

Resultados Experimentais
Os autores avaliaram os algoritmos em conjuntos de dados sintéticos e do mundo real:

• Dados Sintéticos: Usando grafos Barabási-Albert ($N=250$) onde a função de recompensa verdadeira era uma combinação linear dos primeiros 3 autovetores mais suaves. No regime $T < N$, tanto o SpectralUCB quanto o SpectralTS superaram significativamente seus equivalentes lineares (LinUCB e LinearTS) em termos de arrependimento cumulativo. O SpectralTS também demonstrou tempo computacional mais rápido.
• Dados do Mundo Real: Experimentos foram conduzidos no conjunto de dados MovieLens ($N=2019$ filmes), modelando preferências de usuários como uma função suave em um grafo de similaridade construído a partir de classificações de filmes. Os resultados espelharam as descobertas sintéticas: os algoritmos espectrais alcançaram menor arrependimento cumulativo do que as linhas de base de bandit linear. O artigo nota que um bom estimador de preferências de usuários para milhares de itens poderia ser aprendido a partir de apenas dezenas de avaliações de nós.

Significado e Alegações
O artigo alega que, explorando a suavidade de funções em grafos via decomposição espectral, é possível resolver problemas de aprendizado online com um grande número de braços sem que o arrependimento escale mal com o número de nós. A introdução da dimensão efetiva $d$ permite que os algoritmos se adaptem à complexidade intrínseca da estrutura do grafo. O trabalho é motivado por aplicações em recomendação baseada em conteúdo e publicidade direcionada em redes sociais, onde preferências ou interesses de usuários tendem a mudar suavemente através de nós conectados. Os autores enfatizam que sua abordagem é particularmente relevante para cenários onde o número de interações disponíveis ($T$) é pequeno comparado ao número de itens disponíveis ($N$).