Contextual Bandits for Maximizing Stimulated Word-of-Mouth Rewards

Resumo Técnico: Bandidos Contextuais para Maximizar Recompensas de Boca a Boca Estimulada

Definição do Problema
O artigo aborda o desafio de otimizar o boca a boca (WOM - Word-of-Mouth) estimulado em redes sociais. Diferente do boca a boca orgânico, o boca a boca estimulado depende de incentivos (ex: recompensas, descontos) para encorajar usuários a compartilhar informações. O problema central é a heterogeneidade no transbordamento (spillover) de rede: a probabilidade de que uma recomendação feita por um usuário $v_i$ ativado pelo sistema influencie um vizinho $v_j$ a adotar o produto varia significativamente entre diferentes pares de usuários e posições na rede.

A literatura existente frequentemente assume que as probabilidades de transbordamento são conhecidas ou foca na maximização de influência geral sem aprender as probabilidades individuais de cada aresta. Este artigo identifica uma lacuna onde as estratégias atuais de WOM estimulado negligenciam esses efeitos de transbordamento variáveis, levando a um direcionamento subótimo. O problema específico formulado é a Predição de Probabilidade de Transbordamento para Recomendação de Top-$k$ Vizinhos: dado um grafo atribuído $G=(V, E)$, o sistema deve aprender a probabilidade de transbordamento $e_{ij}.p$ para as arestas ao longo de $T$ rodadas para recomendar os top-$k$ vizinhos com maior probabilidade de ativação, maximizando assim as recompensas cumulativas.

Metodologia: Estrutura SpillCB
Os autores propõem o SpillCB, uma nova estrutura de Bandido Multi-Braços Contextual (CMAB - Contextual Multi-Armed Bandit) projetada para aprender probabilidades de transbordamento individuais em um ambiente online.

• Modelo de Dados: A rede é representada como um grafo bidirecionado atribuído onde os nós possuem vetores de atributos ($v.X$). O contexto para uma aresta $e_{ij}$ é definido como a concatenação dos atributos do nó de origem $v_i$, do vizinho de destino $v_j$ e dos atributos relevantes do produto.
• Formulação de Bandido: O problema é modelado como um bandido estocástico de 2 braços para cada aresta:
  • Braço $a_0$: Não recomendar o vizinho.
  • Braço $a_1$: Recomendar o vizinho $v_j$ ao nó $v_i$ ativado pelo sistema.
  • Recompensa: Uma recompensa binária (1 ou 0) é gerada se o vizinho recomendado $v_j$ for ativado devido ao transbordamento. A recompensa é uma função do vetor de contexto e da ação, acrescida de ruído.
• Estratégia de Aprendizado: A estrutura opera em duas fases ao longo de $T$ rodadas:
  1. Exploração: Durante uma fração inicial ($z\%$) das rodadas, $k$ vizinhos são selecionados aleatoriamente para diversificar as seleções de arestas e coletar dados.
  2. Explotação: Nas rodadas subsequentes, o algoritmo seleciona os top-$k$ vizinhos baseando-se nas recompensas esperadas estimadas do braço $a_1$, previstas pelo algoritmo CMAB subjacente.
• Algoritmos: A estrutura é agnóstica ao solver CMAB específico, mas é avaliada utilizando LinUCB e EENet. O objetivo é minimizar o regret cumulativo, definido como a diferença entre as recompensas do conjunto top-$k$ ideal e o conjunto selecionado.

Configuração Experimental e Resultados
Os autores avaliaram o SpillCB em dois conjuntos de dados de redes atribuídas do mundo real: Flickr e Facebook. As probabilidades de transbordamento foram geradas sinteticamente com base em uma função ponderada de similaridade de cosseno, similaridade de nível, sobreposição topológica, importância de difusão e produto de grau.

• Baselines (Linhas de Base): O método proposto foi comparado contra:
  • Random (Aleatório): Seleção aleatória de $k$ vizinhos.
  • Similarity-based (Baseado em Similaridade): Seleção baseada na distância euclidiana dos vetores de atributos.
  • Ridge Regression (Regressão Ridge): Predição de peso de aresta usando regressão ridge em arestas rotuladas.
  • GraphSage: Predição de peso de aresta usando embeddings de nós e uma função de pontuação de rede neural.
• Métricas: O desempenho foi medido usando Recall@k (capacidade de identificar os verdadeiros top-$k$ vizinhos) e o Erro Quadrático Médio (RMSE) das probabilidades de transbordamento aprendidas.
• Principais Descobertas:
  • As variantes do SpillCB (SpillCBLinUCB e SpillCBEENet) superaram consistentemente todos os métodos de baseline em Recall@k para diversos valores de $k$ (5 a 25) em ambos os datasets.
  • O aumento de $k$ geralmente reduziu o RMSE, pois permitiu a exploração de mais arestas, acelerando o processo de aprendizado.
  • Observou-se um compromisso (trade-off) entre a razão de exploração ($z$) e o desempenho: aumentar a exploração de 0% para 20% reduziu o RMSE (melhorando a precisão da estimativa de probabilidade), mas diminuiu ligeiramente o Recall@10 na rodada final.
  • À medida que o número de rodadas ($T$) aumentava, o Recall@10 melhorava e o RMSE diminuía, demonstrando a eficácia da abordagem de aprendizado online.

Significância e Alegações
O artigo afirma apresentar um trabalho preliminar que utiliza bandidos multi-braços contextuais para estimar efeitos de transbordamento heterogêneos, um fator frequentemente negligenciado na otimização de WOM estimulado. A principal contribuição é uma estrutura que aprende probabilidades de transbordamento individuais em vez de assumir que elas sejam conhecidas.

Os autores afirmam que considerar a heterogeneidade do transbordamento aumenta a precisão do direcionamento de usuários conectados top-$k$, impulsionando as recompensas e superando métodos que não aprendem os efeitos de transbordamento individuais. O trabalho visa melhorar a eficácia dos sistemas de recomendação ao entregar experiências de usuário mais personalizadas e maximizar as recompensas de WOM. Os autores mantêm-se modestos quanto às suas alegações, observando que os resultados são preliminares e que trabalhos futuros envolverão testes em mais datasets e baselines para compreender melhor as forças e limitações da abordagem.