Spectral bandits for smooth graph functions with applications in recommender systems

Résumé Technique : Bandits Spectraux pour Fonctions Lisses sur Graphes

Formulation du Problème
Cet article traite d'un problème de bandit à plusieurs bras où les bras correspondent aux nœuds d'un graphe connu $G=(V, E)$, et le gain espéré de l'activation d'un bras est déterminé par une fonction lisse définie sur le graphe. Dans ce cadre, la fonction de récompense $f$ est supposée être une combinaison linéaire des vecteurs propres du Laplacien du graphe $L$. Plus précisément, si $Q$ contient les vecteurs propres de $L$ comme colonnes, la récompense pour le nœud $v$ est $f_\alpha(v) = \langle x_v, \alpha^* \rangle$, où $x_v$ est la $v$-ième ligne de $Q$ et $\alpha^*$ est un vecteur de poids inconnu.

Le défi principal survient lorsque le nombre de nœuds $N$ (et donc la dimension de l'espace de caractéristiques $D=N$) est très grand, pouvant dépasser l'horizon temporel $T$ du processus d'apprentissage ($T < N$). Les algorithmes standards de bandits linéaires, qui font généralement évoluer leur regret avec la dimension ambiante $D$ ou le nombre de bras $K$, donneraient de mauvais résultats dans ce régime. L'article suppose que la fonction vraie est « lisse », ce qui signifie que les coefficients $\alpha^*$ associés aux vecteurs propres correspondant à de grandes valeurs propres sont petits, tandis que ceux associés aux petites valeurs propres sont plus grands.

Méthodologie
Les auteurs proposent deux algorithmes qui exploitent les propriétés spectrales du graphe pour obtenir des bornes de regret qui évoluent avec une « dimension effective » $d$ plutôt qu'avec la dimension complète $N$.

1. Dimension Effective ($d$) : L'article introduit une définition formelle de la dimension effective $d$ basée sur la croissance des valeurs propres du Laplacien régularisé $\Lambda = \Lambda_L + \lambda I$. $d$ est défini comme le plus grand entier tel que $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$. Cette métrique capture le nombre de dimensions « pertinentes » dans le problème, qui est typiquement beaucoup plus petit que $N$ dans les graphes réels.

2. SpectralUCB : Cet algorithme est une modification de l'algorithme LinUCB. Il emploie un estimateur des moindres carrés régularisé pour $\alpha^*$ utilisant la base spectrale. Crucialement, il construit des bornes de confiance pour les récompenses prédites en utilisant la dimension effective $d$ plutôt que la dimension ambiante $D$. L'algorithme sélectionne le nœud maximisant la borne de confiance supérieure : $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$, où $c_t$ dépend de $d$.

3. Échantillonnage de Thompson Spectral (SpectralTS) : Cet algorithme utilise une approche bayésienne. Il maintient une distribution a posteriori sur $\alpha^*$, modélisée comme une Gaussienne $N(\hat{\alpha}_t, v^2 V_t^{-1})$. La covariance a priori est fixée au Laplacien régularisé $\Lambda$, encodant l'hypothèse que les fonctions lisses (composantes à faible valeur propre) sont plus probables. À chaque étape, un échantillon $\tilde{\alpha}$ est tiré de la distribution a posteriori, et le nœud maximisant $x_v^T \tilde{\alpha}$ est sélectionné.

Contributions Clés et Résultats Théoriques

• Cadre Novel : Il s'agit du premier travail formalisant les problèmes de bandits où les récompenses sont des fonctions lisses sur un graphe, faisant le pont entre l'apprentissage de variétés/apprentissage semi-supervisé et l'apprentissage en ligne.
• Bornes de Regret : L'article prouve que SpectralUCB et SpectralTS atteignent des bornes de regret cumulatif qui évoluent avec la dimension effective $d$ :
  • SpectralUCB : $O(d\sqrt{T \ln T})$.
  • SpectralTS : $O(d\sqrt{T \ln N})$.
    Ces bornes sont significatives car $d$ est souvent beaucoup plus petit que $N$, permettant aux algorithmes de bien performer même lorsque $T < N$.
• Efficacité Computationsnelle : Les auteurs soulignent un avantage computationnel pour SpectralTS. Alors que SpectralUCB nécessite de calculer des bornes de confiance pour tous les $N$ bras (menant à une complexité de $O(N^3)$ par étape dans le pire des cas où $D=N$), SpectralTS nécessite uniquement de tirer un vecteur de paramètres et de trouver le maximum, ce qui peut être fait plus efficacement ($O(N^2)$ par étape).

Résultats Expérimentaux
Les auteurs ont évalué les algorithmes sur des données synthétiques et réelles :

• Données Synthétiques : Utilisation de graphes Barabási-Albert ($N=250$) où la fonction de récompense vraie était une combinaison linéaire des 3 vecteurs propres les plus lisses. Dans le régime $T < N$, SpectralUCB et SpectralTS ont nettement surpassé leurs équivalents linéaires (LinUCB et LinearTS) en termes de regret cumulatif. SpectralTS a également démontré un temps de calcul plus rapide.
• Données Réelles : Des expériences ont été menées sur l'ensemble de données MovieLens ($N=2019$ films), modélisant les préférences des utilisateurs comme une fonction lisse sur un graphe de similarité construit à partir des notes de films. Les résultats ont reflété les découvertes synthétiques : les algorithmes spectraux ont atteint un regret cumulatif inférieur par rapport aux références de bandits linéaires. L'article note qu'un bon estimateur des préférences des utilisateurs pour des milliers d'articles pourrait être appris à partir de seulement quelques dizaines d'évaluations de nœuds.

Signification et Affirmations
L'article affirme qu'en exploitant la lissité des fonctions sur les graphes via la décomposition spectrale, il est possible de résoudre des problèmes d'apprentissage en ligne avec un grand nombre de bras sans que le regret ne se dégrade avec le nombre de nœuds. L'introduction de la dimension effective $d$ permet aux algorithmes de s'adapter à la complexité intrinsèque de la structure du graphe. Le travail est motivé par des applications dans la recommandation basée sur le contenu et la publicité ciblée dans les réseaux sociaux, où les préférences ou les intérêts des utilisateurs ont tendance à changer de manière lisse à travers les nœuds connectés. Les auteurs soulignent que leur approche est particulièrement pertinente pour les scénarios où le nombre d'interactions disponibles ($T$) est faible par rapport au nombre d'articles disponibles ($N$).