Scalable Model-Free Algorithms for Influencer Marketing
Apprentissage séquentiel pour la diffusion d'information
Résumé
Motivated by scenarios of information diffusion and advertising in social media, we study an emph{influence maximization} (IM) problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In such a highly uncertain environment, one can focus on emph{multi-round diffusion campaigns}, with the objective to maximize the number of distinct users that are influenced or activated, starting from a known base of few influential nodes.During a campaign, spread seeds are selected sequentially at consecutive rounds, and feedback is collected in the form of the activated nodes at each round.A round's impact (reward) is then quantified as the number of emph{newly activated nodes}.Overall, one must maximize the campaign's total spread, as the sum of rounds' rewards.We consider two sub-classes of IM, emph{cimp} (CIMP) and emph{ecimp} (ECIMP), where (i) the reward of a given round of an ongoing campaign consists of only the extit{new activations} (not observed at previous rounds within that campaign), (ii) the round's context and the historical data from previous rounds can be exploited to learn the best policy, and (iii) ECIMP is CIMP repeated multiple times, offering the possibility of learning from previous campaigns as well.This problem is directly motivated by the real-world scenarios of information diffusion in emph{influencer marketing}, where (i) only a target user's emph{first} / unique activation is of interest (and this activation will emph{persist} as an acquired, latent one throughout the campaign), and (ii) valuable side-information is available to the learning agent.In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaigns.For CIMP, we describe and compare two methods of emph{contextual multi-armed bandits}, with emph{upper-confidence bounds} on the remaining potential of influencers, one using a generalized linear model and the Good-Turing estimator for remaining potential (glmucb), and another one that directly adapts the LinUCB algorithm to our setting (linucb).For ECIMP, we propose the algorithmlgtlsvi, which implements the extit{optimism in the face of uncertainty} principle for episodic reinforcement learning with linear approximation. The learning agent estimates for each seed node its remaining potential with a Good-Turing estimator, modified by an estimated Q-function.We show that they outperform baseline methods using state-of-the-art ideas, on synthetic and real-world data, while at the same time exhibiting different and complementary behavior, depending on the scenarios in which they are deployed.
Motivés par les scénarios de diffusion de l'information et de publicité dans le les réseaux sociaux, nous étudions un problème de maximisation de l'influence (MI) dans lequel on suppose que l'on en sait peu sur le réseau de diffusion ou sur le modèle qui détermine comment l'information peut se propager.Dans un tel environnement incertain, on peut se concentrer sur des campagnes de diffusion à plusieurs tours, avec l'objectif de maximiser le nombre d'utilisateurs distincts qui sont influencés ou activés, à partir d'une base de nœuds influents.Au cours d'une campagne, les graines de propagation sont sélectionnées séquentiellement lors de tours consécutifs, et les commentaires sont collectés sous la forme des nœuds activés à chaque tour.L'impact (récompense) d'un tour est alors quantifié par le nombre de nœuds nouvellement activés. En général, il faut maximiser la propagation totale de la campagne, comme la somme des récompenses des tours.Nous considérons deux sous-classes de d'IM, emph{cimp} (CIMP) et emph{ecimp} (ECIMP), où (i) la récompense d'un tour d'une campagne en cours consiste uniquement en de nouvelles activations (non observées lors des tours précédents de cette campagne),(ii) le contexte du tour et les données historiques des tours précédents peuvent être exploités pour apprendre la meilleure politique, et(iii) ECIMP est CIMP répété plusieurs fois, ce qui permet d'apprendre également des campagnes précédentes.Ce problème est directement motivé par les scénarios du monde réel de la diffusion de l'information dans le marketing d'influence, où (i) seule la première / unique activation d'un utilisateur cible présente un intérêt (et cette activation persistera comme une activation acquise, latente, tout au long de la campagne).(ii) de précieuses informations secondaires sont disponibles pour l'agent d'apprentissageDans ce contexte, une approche d'exploration-exploitation pourrait être utilisée pour apprendre les principaux paramètres de diffusion sous-jacents, tout en exécutant les campagnes.Pour CIMP, nous décrivons et comparons deux méthodes de bandits à bras multiples contextuels, avec des limites supérieures de confiance sur le potentiel restant des influenceurs, l'une utilisant un modèle linéaire généralisé et l'estimateur de Good-Turing pour le potentiel restant, et l'autre adaptant directement l'algorithme LinUCB à notre cadre.Pour ECIMP, nous proposons l'algorithmelgtlsvi qui implémente le principe d'optimisme face à l'incertitude pour l'apprentissage par renforcement, avec approximation linéaire.L'agent d'apprentissage estime pour chaque nœud de départ son potentiel restant avec un estimateur de Good-Turing, modifié par une fonction Q estimée. Nous montrons qu'ils surpassent les performances des méthodes de base utilisant les idées les plus récentes, sur des données synthétiques et réelles, tout en présentant un comportement différent et complémentaire, selon les scénarios dans lesquels ils sont déployés.
Origine : Version validée par le jury (STAR)