Spectral bandits for smooth graph functions with applications in recommender systems

Resumen Técnico: Bandidos Espectrales para Funciones Suaves en Grafos

Formulación del Problema
Este artículo aborda un problema de bandido multi-brazo donde los brazos corresponden a los nodos de un grafo conocido $G=(V, E)$, y la recompensa esperada de accionar un brazo está determinada por una función suave definida sobre el grafo. En este contexto, se asume que la función de recompensa $f$ es una combinación lineal de los vectores propios del Laplaciano del grafo $L$. Específicamente, si $Q$ contiene los vectores propios de $L$ como columnas, la recompensa para el nodo $v$ es $f_\alpha(v) = \langle x_v, \alpha^* \rangle$, donde $x_v$ es la $v$-ésima fila de $Q$ y $\alpha^*$ es un vector de pesos desconocido.

El desafío central surge cuando el número de nodos $N$ (y por tanto la dimensión del espacio de características $D=N$) es muy grande, potencialmente excediendo el horizonte temporal $T$ del proceso de aprendizaje ($T < N$). Los algoritmos estándar de bandidos lineales, que típicamente escalan su arrepentimiento con la dimensión ambiental $D$ o el número de brazos $K$, tendrían un rendimiento deficiente en este régimen. El artículo asume que la función verdadera es "suave", lo que significa que los coeficientes $\alpha^*$ asociados a los vectores propios correspondientes a valores propios grandes son pequeños, mientras que aquellos asociados a valores propios pequeños son mayores.

Metodología
Los autores proponen dos algoritmos que aprovechan las propiedades espectrales del grafo para lograr cotas de arrepentimiento que escalan con una "dimensión efectiva" $d$ en lugar de la dimensión completa $N$.

1. Dimensión Efectiva ($d$): El artículo introduce una definición formal de la dimensión efectiva $d$ basada en el crecimiento de los valores propios del Laplaciano regularizado $\Lambda = \Lambda_L + \lambda I$. $d$ se define como el mayor entero tal que $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$. Esta métrica captura el número de dimensiones "relevantes" en el problema, que típicamente es mucho menor que $N$ en grafos del mundo real.

2. SpectralUCB: Este algoritmo es una modificación del algoritmo LinUCB. Emplea un estimador de mínimos cuadrados regularizado para $\alpha^*$ utilizando la base espectral. Crucialmente, construye cotas de confianza para las recompensas predichas utilizando la dimensión efectiva $d$ en lugar de la dimensión ambiental $D$. El algoritmo selecciona el nodo que maximiza la cota superior de confianza: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$, donde $c_t$ depende de $d$.

3. Muestreo de Thompson Espectral (SpectralTS): Este algoritmo utiliza un enfoque bayesiano. Mantiene una distribución posterior sobre $\alpha^*$, modelada como una Gaussiana $N(\hat{\alpha}_t, v^2 V_t^{-1})$. La covarianza previa se establece como el Laplaciano regularizado $\Lambda$, codificando la suposición de que las funciones suaves (componentes de bajo valor propio) son más probables. En cada paso, se extrae una muestra $\tilde{\alpha}$ de la posterior, y se selecciona el nodo que maximiza $x_v^T \tilde{\alpha}$.

Contribuciones Clave y Resultados Teóricos

• Marco Novel: Este es el primer trabajo que formaliza problemas de bandidos donde las recompensas son funciones suaves sobre un grafo, tendiendo un puente entre el aprendizaje de variedades/aprendizaje semi-supervisado con el aprendizaje en línea.
• Cotas de Arrepentimiento: El artículo demuestra que tanto SpectralUCB como SpectralTS alcanzan cotas de arrepentimiento acumulativo que escalan con la dimensión efectiva $d$:
  • SpectralUCB: $O(d\sqrt{T \ln T})$.
  • SpectralTS: $O(d\sqrt{T \ln N})$.
    Estas cotas son significativas porque $d$ a menudo es mucho menor que $N$, permitiendo que los algoritmos funcionen bien incluso cuando $T < N$.
• Eficiencia Computacional: Los autores destacan una ventaja computacional para SpectralTS. Mientras que SpectralUCB requiere calcular cotas de confianza para los $N$ brazos (conduciendo a una complejidad de $O(N^3)$ por paso en el peor caso donde $D=N$), SpectralTS solo requiere muestrear un vector de parámetros y encontrar el máximo, lo cual puede hacerse de manera más eficiente ($O(N^2)$ por paso).

Resultados Experimentales
Los autores evaluaron los algoritmos en conjuntos de datos sintéticos y del mundo real:

• Datos Sintéticos: Utilizando grafos Barabási-Albert ($N=250$) donde la función de recompensa verdadera era una combinación lineal de los primeros 3 vectores propios más suaves. En el régimen $T < N$, tanto SpectralUCB como SpectralTS superaron significativamente a sus contrapartes lineales (LinUCB y LinearTS) en términos de arrepentimiento acumulado. SpectralTS también demostró un tiempo computacional más rápido.
• Datos del Mundo Real: Se realizaron experimentos en el conjunto de datos MovieLens ($N=2019$ películas), modelando las preferencias de los usuarios como una función suave sobre un grafo de similitud construido a partir de calificaciones de películas. Los resultados reflejaron los hallazgos sintéticos: los algoritmos espectrales lograron un menor arrepentimiento acumulado que las líneas base de bandidos lineales. El artículo señala que un buen estimador de las preferencias de los usuarios para miles de artículos podría aprenderse a partir de apenas decenas de evaluaciones de nodos.

Significado y Afirmaciones
El artículo afirma que, al explotar la suavidad de las funciones en grafos mediante descomposición espectral, es posible resolver problemas de aprendizaje en línea con un gran número de brazos sin que el arrepentimiento escale mal con el número de nodos. La introducción de la dimensión efectiva $d$ permite que los algoritmos se adapten a la complejidad intrínseca de la estructura del grafo. El trabajo está motivado por aplicaciones en recomendación basada en contenido y publicidad dirigida en redes sociales, donde las preferencias o intereses de los usuarios tienden a cambiar suavemente a través de nodos conectados. Los autores enfatizan que su enfoque es particularmente relevante para escenarios donde el número de interacciones disponibles ($T$) es pequeño en comparación con el número de artículos disponibles ($N$).