Cooperative Bandit Learning in Directed Networks with Arm-Access Constraints

Título: Aprendizaje de Bandidos Cooperativo en Redes Dirigidas con Restricciones de Acceso a Brazos

1. Planteamiento del Problema

El trabajo aborda el problema de los bandidos multi-brazo multi-agente (MAMAB) en entornos distribuidos y descentralizados. El escenario se caracteriza por dos limitaciones fundamentales que difieren de la literatura clásica:

• Redes Dirigidas y Asimétricas: Los agentes se comunican a través de un grafo dirigido, lo que implica un flujo de información asimétrico y desequilibrado. A diferencia de las redes no dirigidas, los promedios simples no se conservan en la dinámica de consenso, lo que puede sesgar las estimaciones globales.
• Restricciones de Acceso a Brazos (Arm-Access Constraints): Cada agente solo puede seleccionar (tirar) un subconjunto específico de los brazos disponibles en el entorno. No todos los agentes tienen acceso a todos los brazos, y el brazo óptimo global puede no ser accesible para un agente individual.

El objetivo es minimizar el arrepentimiento (regret) acumulado para cada agente. Dado que algunos agentes no pueden acceder al brazo óptimo global, el objetivo se redefine para minimizar el arrepentimiento respecto al mejor brazo accesible para cada agente individual, reconociendo que una pérdida estructural es inevitable si el óptimo global no es accesible.

2. Metodología Propuesta: Algoritmo A2C-UCB

Los autores proponen un algoritmo distribuido llamado A2C-UCB (Arm Access Constrained Cooperative Upper Confidence Bound). La metodología se basa en tres pilares técnicos:

• Consenso de Razón con Conservación de Masa (Running Ratio Consensus):
  Para manejar la asimetría de la red dirigida, el algoritmo utiliza un mecanismo de mezcla de información que preserva la masa total. Cada agente mantiene estimaciones locales de:

  1. La recompensa acumulada global ($\hat{s}_i^k(t)$).
  2. El número de tiradas acumuladas globales ($\hat{n}_i^k(t)$).
  3. La "masa de generación" ($\hat{u}_i^k(t)$), que estima cuántos agentes pueden acceder a un brazo específico.
  4. Un variable auxiliar ($\hat{y}_i(t)$) para corregir el sesgo de la distribución estacionaria en redes dirigidas.

  Los agentes actualizan estas variables mediante una matriz estocástica por columnas. Al tomar la razón entre estas variables (ej. $\hat{s}/\hat{n}$), los agentes recuperan asintóticamente la media empírica real de la red, eliminando el sesgo introducido por la topología dirigida.

• Estimación Distribuida de la Accesibilidad:
  Dado que los agentes no conocen de antemano qué otros agentes pueden acceder a qué brazos, el algoritmo utiliza un consenso de razón estático para estimar la masa de generación ($g_k$) de cada brazo (el número total de agentes que pueden muestrearlo). Esto es crucial para ajustar el término de exploración.

• Índice UCB Adaptado:
  El índice de confianza superior (UCB) para cada agente $i$ y brazo $k$ se construye como:
  $$Q_i^k(t) = \hat{\mu}_i^k(t) + \sqrt{\frac{\alpha \log(t \hat{g}_i^k(t))}{\hat{\nu}_i^k(t)}}$$
  Donde:

  • $\hat{\mu}_i^k(t)$ es la estimación de la media de recompensa obtenida vía consenso.
  • $\hat{\nu}_i^k(t)$ es la estimación del número total de tiradas globales.
  • $\hat{g}_i^k(t)$ es la estimación de cuántos agentes pueden acceder al brazo.

  El término $\hat{g}_i^k(t)$ en el numerador del logaritmo actúa como un factor de corrección: si un brazo es accesible por pocos agentes, el término de exploración aumenta para compensar la propagación más lenta de la información.

3. Contribuciones Clave

1. Marco de Accesibilidad Heterogénea: Se formaliza el problema de MAMAB donde la capacidad de aprendizaje está restringida por una matriz de incidencia agente-brazo. Se distingue entre la pérdida de rendimiento estructural (inevitable) y el arrepentimiento debido al aprendizaje.
2. Mecanismo de Consenso Sin Sesgo: A diferencia de algoritmos anteriores que usan promedios simples o matrices estocásticas por filas, este trabajo emplea un consenso de razón que garantiza que las estimaciones de las recompensas sean insesgadas, incluso en redes dirigidas y con restricciones de acceso.
3. Análisis de Regret Logarítmico: Se demuestra teóricamente que el algoritmo logra un arrepentimiento logarítmico ($O(\log T)$) para cada agente. El límite superior del regret depende explícitamente de las propiedades de mezcla de la red y de las restricciones de acceso estructural.
4. Validación en Escenarios Realistas: Se demuestra que el algoritmo supera a las estrategias no cooperativas y a métodos cooperativos existentes que no consideran restricciones de acceso parcial.

4. Resultados

• Simulaciones Numéricas:
  • Se evaluó el algoritmo en una red de 6 agentes con 7 brazos, donde cada agente tenía un subconjunto diferente de brazos accesibles.
  • Comparación con Baseline: El algoritmo A2C-UCB mostró una reducción significativa en el arrepentimiento acumulado en comparación con agentes que ejecutan UCB1 de forma independiente (sin comunicación). La cooperación permite identificar el brazo óptimo global más rápido y reduce la exploración redundante.
  • Comparación con Estado del Arte: En un escenario de acceso completo (todos los agentes pueden acceder a todos los brazos) con una red más grande (30 agentes), A2C-UCB superó al algoritmo de Zhu et al. [17], demostrando robustez incluso sin restricciones de acceso.
  • Escenarios Restringidos: En escenarios con acceso limitado, el método de Zhu et al. no es aplicable, mientras que A2C-UCB se adapta naturalmente, manteniendo un rendimiento eficiente.

5. Significado e Impacto

Este trabajo es significativo porque cierra una brecha importante en la teoría de aprendizaje multi-agente:

• Realismo en Sistemas Distribuidos: Reconoce que en aplicaciones reales (redes de sensores, sistemas robóticos, computación en el borde), los agentes tienen capacidades heterogéneas y la comunicación es a menudo asimétrica.
• Fundamentos Teóricos: Proporciona una base matemática rigurosa para el aprendizaje cooperativo en grafos dirigidos, demostrando que es posible lograr un rendimiento óptimo (arrepentimiento logarítmico) sin necesidad de un coordinador central ni de una red simétrica.
• Aplicabilidad: El algoritmo es directamente aplicable a sistemas donde la conectividad y los recursos de los nodos son limitados, permitiendo una toma de decisiones colectiva eficiente a pesar de la información parcial y el flujo de datos desequilibrado.

En resumen, el paper presenta una solución robusta y teóricamente fundamentada para el aprendizaje cooperativo en entornos complejos y realistas, donde la accesibilidad a la información y la estructura de la red son factores limitantes críticos.