Scalable Policy Maximization Under Network Interference

Resumen Técnico: Maximización de Políticas Escalable bajo Interferencia de Red

Enunciado del Problema
El artículo aborda el desafío de la toma de decisiones secuencial (maximización de políticas) en entornos caracterizados por interferencia de red, donde el estado de tratamiento de un individuo influye en los resultados de otros. Si bien los algoritmos de Bandidos Multi-Brazo (MAB) son estándar para el aprendizaje secuencial, generalmente dependen de supuestos de independencia que fallan en configuraciones de red (por ejemplo, ensayos clínicos, mercados en línea, redes sociales).

Los enfoques existentes para MAB bajo interferencia enfrentan dos limitaciones críticas:

1. Escalabilidad: Los métodos actuales luchan por escalar más allá de redes muy pequeñas (aproximadamente $n \approx 15$ nodos). A menudo intentan capturar patrones de interferencia arbitrarios, lo que conduce a un espacio de parámetros que crece exponencialmente con el grado del nodo ($d_{max}$) y linealmente con el tamaño de la red ($n$). Para una red con $n=1000$ y $d_{max}=10$, esto resulta en más de un millón de parámetros desconocidos, haciendo que la estimación sea computacionalmente inviable.
2. Supuestos Estáticos: Muchos algoritmos existentes requieren que la estructura de la red y la población de individuos permanezcan fijas en el tiempo, un supuesto que crea inconsistencias en entornos dinámicos donde los resultados dependen de los estados históricos de tratamiento.

Metodología
Los autores proponen un algoritmo de Muestreo de Thompson escalable que aprovecha supuestos estructurales comunes en la literatura de inferencia causal para lograr una parametrización lineal parsimoniosa de la función de recompensa.

• Supuestos Estructurales (SANIA): El método se basa en el Supuesto de Interferencia de Vecindad Simétrica y Aditiva (SANIA).

  • Interferencia de Vecindad (NIA): La recompensa de un nodo depende únicamente de su propio tratamiento y del estado de tratamiento de sus vecinos inmediatos.
  • Aditividad: Los efectos directos no interactúan con los efectos indirectos (de derrame).
  • Simetría: La recompensa de un nodo depende del número de vecinos tratados, no de sus identidades específicas.
    Bajo estos supuestos, el vector de recompensas a nivel de nodo puede reparametrizarse como un sistema lineal: $r_t = H(Z_t; A_t)\theta + \epsilon_t$, donde $\theta$ es un vector de parámetros de baja dimensión que contiene parámetros de efecto de tratamiento e interferencia.

• Diseño del Algoritmo:

  • El algoritmo mantiene una distribución posterior sobre el vector de parámetros $\theta$.
  • En cada paso de tiempo $t$, muestrea un vector de parámetros $\theta^{(t)}$ de la posterior y selecciona un vector de asignación de tratamiento $Z_t$ que maximiza la recompensa total esperada condicional a $\theta^{(t)}$.
  • El marco soporta parametrizaciones flexibles, incluyendo parámetros compartidos (todos los nodos comparten $\theta$), parámetros agrupados (nodos en grupos latentes u observados comparten $\theta_g$) y modelos de características latentes (donde las posiciones de los nodos en un espacio euclidiano influyen en las recompensas).
  • El algoritmo acomoda redes dinámicas (donde las matrices de adyacencia $A_t$ cambian) y restricciones de presupuesto (limitando el número de nodos tratados).

• Análisis de Arrepentimiento:

  • Los autores demuestran una cota superior para el arrepentimiento bayesiano de $O(D\sqrt{nT} \log(nT))$, donde $D$ es la dimensión de $\theta$, $n$ es el tamaño de la red y $T$ es el horizonte temporal.
  • Derivan una cota inferior coincidente de $\Omega(D\sqrt{nT})$, demostrando que el algoritmo es casi óptimo.
  • Las cotas de arrepentimiento reflejan la compensación entre la mayor información obtenida al observar $n$ nodos interdependientes y la mayor complejidad del espacio de acciones.

Contribuciones Clave

1. Parametrización Escalable: El artículo demuestra que los supuestos comunes de inferencia causal permiten expresar la función de recompensa como una función lineal de un vector de parámetros de baja dimensión, reduciendo la complejidad de exponencial a polinómica (específicamente, lineal en $n$ para modelos compartidos/agrupados).
2. Muestreo de Thompson Escalable: Los autores desarrollan un algoritmo capaz de manejar redes de órdenes de magnitud mayores que los métodos anteriores (demostrado hasta $n=1000$ en simulaciones), resolviendo la "maldición de la dimensionalidad" inherente a los problemas de interferencia.
3. Manejo de Redes Dinámicas: A diferencia de trabajos anteriores que requieren redes fijas, este marco permite que tanto los nodos como las aristas sean muestreados o cambien en cada período de tiempo, resolviendo las inconsistencias entre la independencia temporal y los supuestos de población fija.
4. Garantías Teóricas: El artículo proporciona cotas superiores e inferiores rigurosas para el arrepentimiento bayesiano, estableciendo la casi optimalidad del enfoque propuesto.

Resultados
Los experimentos de simulación validan el método a través de tres esquemas de parametrización:

• Parámetros Compartidos: El algoritmo aprende rápidamente y escala efectivamente para redes de tamaño $n \in \{100, 500, 1000, 2500\}$.
• Parámetros Agrupados: El método funciona bien incluso cuando las etiquetas de grupo son parcialmente latentes y deben estimarse utilizando un nodo "ancla" por grupo.
• Características Latentes: El algoritmo maneja con éxito efectos heterogéneos dependientes de características de nodos latentes en modelos de espacio latente.

Comparaciones:

• vs. Agarwal et al. (2024): El método propuesto supera significativamente al estado del arte existente (que utiliza análisis de Fourier e interferencia de red dispersa) en redes estáticas pequeñas. Crucialmente, el método propuesto permanece robusto y supera a Agarwal et al. incluso cuando los supuestos de SANIA están mal especificados (por ejemplo, cuando se viola la aditividad o la simetría). Esto se atribuye a la capacidad del método propuesto para aprender una aproximación efectiva con muchos menos parámetros, mientras que los métodos competidores sufren de alta varianza debido a la necesidad de estimar vectores de parámetros exponencialmente más grandes.
• vs. MAB Estándar: Los enfoques estándar de MAB fallan al escalar debido al crecimiento exponencial del espacio de acciones ($2^n$ brazos).

Significado
El artículo afirma cerrar una brecha de escalabilidad clave entre los métodos de inferencia causal para interferencia y los algoritmos prácticos de bandidos. Al permitir la optimización de políticas en sistemas de red a gran escala, el trabajo cierra la brecha entre la identificación causal teórica y la toma de decisiones dinámica. Los autores sugieren que este marco facilita la aplicación de algoritmos de bandidos a problemas del mundo real que involucran redes grandes y dinámicas, como la distribución de vacunas o intervenciones en mercados en línea, donde la interferencia es prevalente pero previamente demasiado compleja para modelar dinámicamente.