Contextual Bandits for Maximizing Stimulated Word-of-Mouth Rewards

Résumé Technique : Bandits Contextuels pour la Maximisation des Récompenses du Bouche-à-Oreille Stimulé

Définition du Problème
L'article traite du défi de l'optimisation du bouche-à-oreille (WOM - Word-of-Mouth) stimulé dans les réseaux sociaux. Contrairement au bouche-à-oreille organique, le bouche-à-oreille stimulé repose sur des incitations (ex. : récompenses, réductions) pour encourager les utilisateurs à partager des informations. Le problème central est l'hétérogénéité du débordement réseau (network spillover) : la probabilité qu'une recommandation faite par un utilisateur $v_i$ activé par le système influencera un voisin $v_j$ à adopter le produit varie considérablement selon les paires d'utilisateurs et les positions dans le réseau.

La littérature existante suppose souvent que les probabilités de débordement sont connues ou se concentre sur la maximisation de l'influence générale sans apprendre les probabilités de liens individuels. Cet article identifie une lacune où les stratégies actuelles de WOM stimulé négligent ces effets de débordement variables, menant à un ciblage sous-optimal. Le problème spécifique formulé est la Prédiction de la Probabilité de Débordement pour la Recommandation des Top-$k$ Voisins : étant donné un réseau attribué $G=(V, E)$, le système doit apprendre la probabilité de débordement $e_{ij}.p$ pour les arêtes sur $T$ tours afin de recommander les top-$k$ voisins les plus susceptibles d'être activés, maximisant ainsi les récompenses cumulées.

Méthodologie : Cadre SpillCB
Les auteurs proposent SpillCB, un nouveau cadre de Bandit Multi-Bras Contextuel (CMAB - Contextual Multi-Armed Bandit) conçu pour apprendre les probabilités de débordement individuelles dans un environnement en ligne.

• Modèle de Données : Le réseau est représenté par un graphe bidirectionnel attribué où les nœuds possèdent des vecteurs d'attributs ($v.X$). Le contexte pour une arête $e_{ij}$ est défini comme la concaténation des attributs du nœud source $v_i$, du voisin cible $v_j$, et des attributs pertinents du produit.
• Formulation du Bandit : Le problème est modélisé comme un bandit stochastique à 2 bras pour chaque arête :
  • Bras $a_0$ : Ne pas recommander le voisin.
  • Bras $a_1$ : Recommander le voisin $v_j$ au nœud $v_i$ activé par le système.
  • Récompense : Une récompense binaire (1 ou 0) est générée si le voisin recommandé $v_j$ devient activé suite au débordement. La récompense est une fonction du vecteur de contexte et de l'action, plus du bruit.
• Stratégie d'Apprentissage : Le cadre opère en deux phases sur $T$ tours :
  1. Exploration : Pour une fraction initiale ($z\%$) de tours, $k$ voisins sont sélectionnés aléatoirement pour diversifier les sélections d'arêtes et collecter des données.
  2. Exploitation : Dans les tours suivants, l'algorithme sélectionne les top-$k$ voisins basés sur les récompenses attendues estimées du bras $a_1$, prédites par l'algorithme CMAB sous-jacent.
• Algorithmes : Le cadre est agnostique quant au solveur CMAB spécifique utilisé, mais il est évalué via LinUCB et EENet. L'objectif est de minimiser le regret cumulé, défini comme la différence entre les récompenses du ensemble optimal de top-$k$ et l'ensemble sélectionné.

Configuration Expérimentale et Résultats
Les auteurs ont évalué SpillCB sur deux jeux de données de réseaux attribués réels : Flickr et Facebook. Les probabilités de débordement ont été générées synthétiquement sur la base d'une fonction pondérée de la similitude cosinus, de la similitude de niveau, du chevauchement topologique, de l'importance de diffusion et du produit de degré.

• Baselines (Référentiels) : La méthode proposée a été comparée à :
  • Random (Aléatoire) : Sélection aléatoire de $k$ voisins.
  • Similarity-based (Basé sur la similitude) : Sélection basée sur la distance euclidienne des vecteurs d'attributs.
  • Ridge Regression (Régression Ridge) : Prédiction du poids des liens via la régression ridge sur des arêtes étiquetées.
  • GraphSage : Prédiction du poids des liens utilisant des plongements de nœuds (embeddings) et une fonction de score neuronale.
• Métriques : La performance a été mesurée via le Recall@k (capacité à identifier les vrais top-$k$ voisins) et l'erreur quadratique moyenne (RMSE) des probabilités de débordement apprises.
• Résultats Clés :
  • Les variantes de SpillCB (SpillCBLinUCB et SpillCBEENet) ont systématiquement surpassé toutes les méthodes de référence en Recall@k pour différentes valeurs de $k$ (5 à 25) sur les deux jeux de données.
  • L'augmentation de $k$ réduit généralement la RMSE, car elle permet d'explorer plus d'arêtes, accélérant ainsi le processus d'apprentissage.
  • Un compromis a été observé entre le ratio d'exploration ($z$) et la performance : augmenter l'exploration de 0 % à 20 % a réduit la RMSE (améliorant la précision de l'estimation de la probabilité) mais a légèrement diminué le Recall@10 lors du dernier tour.
  • À mesure que le nombre de tours ($T$) augmentait, le Recall@10 s'améliorait et la RMSE diminuait, démontrant l'efficacité de l'approche d'apprentissage en ligne.

Signification et Revendications
L'article affirme présenter un travail préliminaire qui exploite les bandits multi-bras contextuels pour estimer les effets de débordement hétérogènes, un facteur souvent négligé dans l'optimisation du bouche-à-oreille stimulé. La contribution primaire est un cadre qui apprend les probabilités de débordement individuelles plutôt que de supposer qu'elles sont connues.

Les auteurs soutiennent que la prise en compte de l'hétérogénéité du débordement améliore la précision du ciblage des utilisateurs connectés de type top-$k$, augmentant ainsi les récompenses et surpassant les méthodes qui ne parviennent pas à apprendre les effets de débordement individuels. Ce travail vise à améliorer l'efficacité des systèmes de recommandation en offrant des expériences utilisateur plus personnalisées et en maximisant les récompenses du bouche-à-oreille. Les auteurs restent modestes quant à leurs affirmations, notant que les résultats sont préliminaires et que les travaux futurs impliqueront des tests sur plus de jeux de données et de bases de référence pour mieux comprendre les forces et les limites de l'approche.