Resumen Técnico: Algoritmos de GNEP Distribuidos sin Intercambio de Multiplicadores y Aplicaciones a la Coordinación Multi-Robot y al Aprendizaje Activo Basado en Bandidos Contextuales

1. Planteamiento del Problema

La tesis aborda dos desafíos distintos pero significativos en la optimización distribuida y el aprendizaje automático:

Parte I: Problemas de Equilibrio de Nash Generalizado (GNEP)
En muchos sistemas multi-agente (por ejemplo, redes eléctricas, enrutamiento de tráfico, coordinación multi-robot), los agentes deben minimizar funciones de costo locales sujetas tanto a restricciones individuales como a restricciones de acoplamiento compartidas. Esta formulación conduce al Problema de Equilibrio de Nash Generalizado (GNEP). Los algoritmos distribuidos existentes para resolver GNEPs suelen depender de la imposición de un consenso entre los multiplicadores de Lagrange asociados con las restricciones compartidas. Este requisito requiere el intercambio de variables auxiliares y multiplicadores entre agentes, lo que aumenta la sobrecarga de comunicación y puede comprometer la privacidad. Además, la mayoría de los métodos existentes se restringen a computar Equilibrios de Nash Generalizados variacionales (v-GNE), una subclase específica de equilibrios, en lugar del conjunto completo de Equilibrios de Nash Generalizados (GNE).

**Parte II: Aprendizaje Activo Basado en Bandidos Contextuales
El aprendizaje activo tiene como objetivo reducir el costo de etiquetado en el aprendizaje supervisado mediante la consulta selectiva de los puntos de datos más informativos. Aunque existen numerosas estrategias diseñadas manualmente (por ejemplo, muestreo de incertidumbre, muestreo de diversidad), su rendimiento depende altamente de la distribución de los datos subyacentes, que a menudo es desconocida. Los marcos adaptativos existentes que combinan estas estrategias suelen utilizar algoritmos de bandidos adversarios. Estos métodos son excesivamente conservadores, manteniendo una exploración persistente sin aprovechar el contexto ambiental, lo que a menudo resulta en un rendimiento similar a la selección aleatoria.

2. Metodología

Parte I: Algoritmos Completamente Distribuidos para GNEPs

El autor propone un algoritmo de tiempo continuo completamente distribuido basado en la dinámica primal-dual que elimina la necesidad de compartir multiplicadores.

• Dinámica Primal-Dual: El algoritmo modela el sistema como un Sistema Dinámico Proyectado (PDS). Los agentes actualizan sus variables de decisión ($z_v$) y sus multiplicadores locales ($\lambda_v, \mu_v$) utilizando únicamente información local y datos intercambiados con los vecinos a través de grafos de interacción específicos (grafo de función de costo y grafo de restricción compartida).
• Transformación de Multiplicadores: Una innovación teórica clave es la transformación de los multiplicadores compartidos. En lugar de imponer un consenso ($\lambda_v = \lambda_u$), el método descompone los multiplicadores en un estado de referencia común y un término de desviación ($\Delta_v$). Se demuestra que la dinámica de los términos de desviación es constante o no creciente en el tiempo, dependiendo del tipo de restricción (igualdad vs. desigualdad).
• Análisis de Convergencia:
  • Restricciones de Igualdad: Para juegos con mapeos de costo fuertemente monotónicos y restricciones de igualdad lineales compartidas, el autor demuestra la estabilidad asintótica global. Las variables primales convergen a un v-GNE único, mientras que las variables duales convergen a un conjunto de multiplicadores válidos. El equilibrio límite depende de la inicialización de los términos de desviación.
  • Restricciones de Desigualdad: Para restricciones de desigualdad compartidas con costos convexos cuadráticos, el análisis utiliza argumentos de entrada acotada - salida acotada (BIBO) y la acotación de trayectorias para demostrar la convergencia a un GNE, incluso cuando la dinámica primal-dual inducida no es monótona.
• Discretización: Para permitir la implementación práctica, la tesis desarrolla tres esquemas de discretización:
  1. Tamaño de Paso Diminuido: Imita la dinámica continua asintóticamente pero converge lentamente ($O(1/\sqrt{k})$).
  2. Euler hacia Atrás (Resolvente): Utiliza un tamaño de paso fijo y requiere resolver un Problema de Equilibrio de Nash (NEP) interno en cada paso. Logra una tasa de convergencia de $o(1/k)$.
  3. División Forward-Backward: Un esquema híbrido que evita el requerimiento del solver interno al tratar partes del operador de forma explícita y otras de forma implícita. Requiere un tamaño de paso acordado globalmente pero ofrece un equilibrio entre el costo computacional y la tasa de convergencia.

Parte II: Aprendizaje Activo Adaptativo Contextual (CAAL)

La segunda parte introduce el Aprendizaje Activo Adaptativo Contextual (CAAL), un marco de meta-estrategia que utiliza bandidos contextuales para seleccionar dinámicamente la mejor estrategia de aprendizaje activo diseñada manualmente.

• Marco de Trabajo: El problema se modela como un bandido contextual donde las "armas" son diferentes estrategias de aprendizaje activo diseñadas manualmente (por ejemplo, K-Center, Diversidad Informativa).
• Contexto y Recompensa: A diferencia de los enfoques de bandidos adversarios, CAAL incorpora contexto externo (por ejemplo, el tamaño actual del conjunto de datos etiquetado) para predecir recompensas. La recompensa se define como la mejora relativa en el rendimiento del modelo (por ejemplo, el cambio en ROC-AUC) entre iteraciones, en lugar del rendimiento absoluto, para abordar la no estacionariedad.
• Algoritmo: El método emplea un algoritmo de Upper Confidence Bound lineal no estacionario (específicamente, Sliding Window LinUCB) para estimar la función de recompensa $\theta_a^\top c_k$. Esto permite que el agente explote la predictibilidad de las recompensas basada en el contexto, reduciendo el conservadurismo inherente a los métodos de bandidos adversarios.

3. Contribuciones Clave

Para GNEPs:

1. Primer Algoritmo Distribuido Sin Intercambio de Multiplicadores: Según el conocimiento del autor, este es el primer algoritmo distribuido que computa GNEs sin requerir consenso ni intercambio de multiplicadores de Lagrange. Esto reduce significativamente la sobrecarga de comunicación (en aproximadamente un tercio en configuraciones de grafos específicas) y mejora la privacidad.
2. Convergencia de GNE General: El método propuesto no se restringe a los v-GNEs. Converge a GNEs generales, donde el equilibrio alcanzado depende de la inicialización. Esto aborda la limitación de los métodos existentes que solo apuntan al v-GNE único.
3. Nuevas Técnicas de Demostración: La tesis desarrolla técnicas de prueba para manejar la dinámica inducida no monótona y los equilibrios no únicos, utilizando el análisis de estabilidad de Lyapunov y argumentos de trayectoria acotada.

Para el Aprendizaje Activo:

1. Adaptación Contextual: El trabajo propone incorporar información contextual en el aprendizaje activo basado en bandidos para reducir el conservadurismo de los marcos de bandidos adversarios.
2. Enfoque en Selección por Lotes: A diferencia de muchos trabajos previos que se centran en la selección de una sola muestra, este enfoque enfatiza la robustez a través de diferentes tamaños de lote, lo cual está más alineado con las aplicaciones industriales.
3. Enfoque de Meta-Aprendiz: El método se centra en la selección basada en meta-aprendiz en lugar de aprendizaje profundo activo, lo que lo hace más adecuado para datos tabulares, que dominan los conjuntos de datos industriales.

4. Resultados

Simulaciones de GNEP:

• Coordinación Multi-Robot: El algoritmo fue probado en problemas de colocación de múltiples robots y cobertura de semi-espacio. Los resultados demostraron la convergencia a GNEs desde diversas inicializaciones, resaltando la no unicidad de las soluciones. La discretización forward-backward (Algoritmo 4.10) mostró tasas de convergencia comparables a los métodos basados en consenso, pero con una comunicación significativamente reducida por iteración.
• Competencia de Cournot: El método se aplicó a un juego de Cournot con 20 agentes y 7 mercados. El algoritmo convergió con éxito a un GNE para cualquier inicialización, preservando la privacidad de los agentes y demostrando escalabilidad.

Experimentos de Aprendizaje Activo:

• Conjuntos de Datos: Los experimentos se realizaron utilizando conjuntos de datos públicos (ILPD, I vs J, Australian Credit, German Credit) empleando regresión logística como clasificador base.
• Rendimiento: CAAL se comparó contra la línea base adaptativa de última generación (ALBL) y estrategias diseñadas manualmente (K-Center, Diversidad Informativa).
  • CAAL superó a ALBL y a las estrategias individuales en la mayoría de los conjuntos de datos, particularmente para tamaños de lote mayores a 5.
  • El análisis de "Predicción de Recompensa" mostró que el modelo de regresión lineal podía predecir con precisión las tendencias de recompensa basadas en el contexto, validando la suposición de linealidad local.
  • El análisis de "Historial de Extracción" (Pull History) indicó que CAAL identificó y explotó con éxito la estrategia óptima tras una fase inicial de exploración, mientras que ALBL tendía a seleccionar las armas con una probabilidad casi igual debido a su naturaleza conservadora.
• Despliegue: El marco ha sido desplegado en los sistemas de producción internos de Amazon, aunque los resultados de los conjuntos de datos internos se omiten por razones de confidencialidad.

5. Significación y Reivindicaciones

La tesis afirma cerrar brechas críticas tanto en la teoría de juegos distribuida como en el aprendizaje automático adaptativo:

• En Optimización Distribuida: Al eliminar el requisito de compartir multiplicadores, el marco propuesto ofrece una solución más escalable y que preserva la privacidad para sistemas multi-agente a gran escala. La capacidad de converger a GNEs generales en lugar de solo v-GNEs expande la aplicabilidad de la computación de equilibrio distribuido a escenarios donde la fijación de precios uniforme o la coordinación centralizada no son factibles.
• En Aprendizaje Activo: El trabajo demuestra que aprovechar la información contextual puede mejorar significativamente la adaptabilidad de las estrategias de aprendizaje activo en comparación con los enfoques puramente adversarios. El marco CAAL proporciona una solución práctica y apta para la industria para el aprendizaje activo en modo lote, que se adapta a distribuciones de datos desconocidas sin requerir arquitecturas de aprendizaje profundo.

El autor señala que, si bien el análisis de tiempo continuo proporciona fuertes garantías teológicas, los esquemas de discretización introducen supuestos específicos (por ejemplo, continuidad de Lipschitz, compacidad) necesarios para la convergencia. Del mismo modo, para el componente de aprendizaje activo, la complejidad de exploración depende del número de estrategias candidatas (armas), y el marco depende actualmente de la experiencia de dominio para definir el conjunto inicial de estrategias diseñadas manualmente. Se propone como trabajo futuro extender los algoritmos de GNEP a restricciones convexas más generales y refinar el análisis teórico del marco de bandidos contextuales.