Contextual Bandits for Maximizing Stimulated Word-of-Mouth Rewards

Resumen Técnico: Bandidos Contextuales para Maximizar las Recompensas del Boca a Boca Estimulado

Definición del Problema
El artículo aborda el desafío de optimizar el boca a boca (WOM, por sus siglas en inglés) estimulado en redes sociales. A diferencia del boca a boca orgánico, el boca a boca estimulado depende de incentivos (por ejemplo, recompensas, descuentos) para fomentar que los usuarios compartan información. El problema central es la heterogeneidad en el desbordamiento de red (network spillover): la probabilidad de que una recomendación realizada por un usuario activado por el sistema $v_i$ influya en un vecino $v_j$ para adoptar el producto varía significamente entre diferentes pares de usuarios y posiciones en la red.

La literatura existente a menudo asume que las probabilidades de desbordamiento son conocidas o se centra en la maximización de la influencia general sin aprender las probabilidades de las aristas individuales. Este artículo identifica una brecha donde las estrategias actuales de WOM estimulado pasan por alto estos efectos de desbordamiento variables, lo que conduce a un direccionamiento subóptimo. El problema específico formulado es la Predicción de la Probabilidad de Desbordamiento para la Recomendación de los Top-$k$ Vecinos: dada una red con atributos $G=(V, E)$, el sistema debe aprender la probabilidad de desbordamiento $e_{ij}.p$ para las aristas a lo largo de $T$ rondas para recomendar a los $k$ mejores vecinos con mayor probabilidad de activación, maximizando así las recompensas acumuladas.

Metodología: Marco de Trabajo SpillCB
Los autores proponen SpillCB, un nuevo marco de Bandidos Multibrazo Contextuales (CMAB) diseñado para aprender probabilidades de desbordamiento individuales en un entorno en línea.

• Modelo de Datos: La red se representa como un grafo bidireccional con atributos donde los nodos poseen vectores de atributos ($v.X$). El contexto para una arista $e_{ij}$ se define como la concatenación de los atributos del nodo de origen $v_i$, el vecino de destino $v_j$ y los atributos relevantes del producto.
• Formulación de Bandidos: El problema se modela como un bandido estocástico de 2 brazos para cada arista:
  • Brazo $a_0$: No recomendar al vecino.
  • Brazo $a_1$: Recomendar al vecino $v_j$ al nodo $v_i$ activado por el sistema.
  • Recompensa: Se genera una recompensa binaria (1 o 0) si el vecino recomendado $v_j$ es activado debido al desbordamiento. La recompensa es una función del vector de contexto y la acción, más ruido.
• Estrategia de Aprendizaje: El marco opera en dos fases a lo largo de $T$ rondas:
  1. Exploración: Durante una fracción inicial ($z\%$) de las rondas, se seleccionan $k$ vecinos aleatoriamente para diversificar las selecciones de las aristas y recopilar datos.
  2. Explotación: En las rondas subsiguientes, el algoritmo selecciona los $k$ mejores vecinos basados en las recompensas esperadas estimadas del brazo $a_1$, predichas por el algoritmo CMAB subyacente.
• Algoritmos: El marco es agnóstico al resolvedor de CMAB específico, pero se evalúa utilizando LinUCB y EENet. El objetivo es minimizar el arrepentimiento (regret) acumulado, definido como la diferencia entre las recompensas del conjunto óptimo de $k$ y el conjunto seleccionado.

Configuración Experimental y Resultados
Los autores evaluaron SpillCB en dos conjuntos de datos de redes con atributos del mundo real: Flickr y Facebook. Las probabilidades de desbordamiento se generaron sintéticamente basándose en una función ponderada de similitud de coseno, similitud de nivel, solapamiento topológico, importancia de difusión y producto de grado.

• Líneas Base (Baselines): El método propuesto se comparó contra:
  • Random: Selección aleatoria de $k$ vecinos.
  • Basado en Similitud: Selección basada en la distancia euclidiana de los vectores de atributos.
  • Regresión Ridge: Predicción del peso de la arista mediante regresión ridge en aristas etiquetadas.
  • GraphSage: Predicción del peso de la arista mediante embeddings de nodos y una función de puntuación de red neuronal.
• Métricas: El rendimiento se midió utilizando Recall@k (capacidad de identificar los verdaderos top-$k$ vecinos) y el Error Cuadrático Medio (RMSE) de las probabilidades de desbordamiento aprendidas.
• Hallazgos Clave:
  • Las variantes de SpillCB (SpillCBLinUCB y SpillCBEENet) superaron consistentemente a todos los métodos de la línea base en Recall@k para diversos valores de $k$ (5 a 25) en ambos conjuntos de datos.
  • El aumento de $k$ generalmente redujo el RMSE, ya que permitió la exploración de más aristas, acelerando el proceso de aprendizaje.
  • Se observó un compromiso entre la relación de exploración ($z$) y el rendimiento: aumentar la exploración del 0% al 20% redujo el RMSE (mejorando la precisión de la estimación de la probabilidad) pero disminuyó ligeramente el Recall@10 en la ronda final.
  • A medida que aumentaba el número de rondas ($T$), el Recall@10 mejoraba y el RMSE disminuía, demostrando la efectividad del enfoque de aprendizaje en línea.

Significancia y Reivindicaciones
El artículo afirma presentar un trabajo preliminar que aprovecha los bandidos multibrazo contextuales para estimar efectos de desbordamiento heterogéneos, un factor que a menudo se pasa por alto en la optimización del boca a boca estimulado. La contribución principal es un marco que aprende probabilidades de desbordamiento individuales en lugar de asumir que estas son conocidas.

Los autores sostienen que tener en cuenta la heterogeneidad del desbordamiento mejora la precisión del direccionamiento de los $k$ usuarios conectados, aumentando las recompensas y superando a los métodos que no aprenden los efectos de desbordamiento individuales. El trabajo busca mejorar la efectividad de los sistemas de recomendación entregando experiencias de usuario más personalizadas y maximizando las recompensas de WOM. Los autores mantienen la modestia respecto a sus afirmaciones, señalando que los resultados son preliminares y que el trabajo futuro implicará probar en más conjuntos de datos y líneas base para comprender mejor las fortalezas y limitaciones del enfoque.