Resumen Técnico: Graph-SND: Agregación Escasa para la Diversidad Conductual en el Aprendizaje por Refuerzo Multiagente

1. Declaración del Problema

En el Aprendizaje por Refuerzo Multiagente (MARL), la Diversidad Neural del Sistema (SND) es una métrica utilizada para medir la heterogeneidad conductual entre agentes promediando las distancias de Wasserstein por pares entre sus distribuciones de acciones. Aunque la SND permite el control de la diversidad (por ejemplo, mediante el algoritmo DiCo), su cálculo presenta un cuello de botella severo de escalabilidad. Calcular la SND completa requiere evaluar todos los $\binom{n}{2}$ pares de agentes, resultando en una complejidad cuadrática $O(n^2)$ en función del número de agentes $n$. Este costo de agregación se vuelve prohibitivo para equipos a gran escala, limitando la aplicación práctica del entrenamiento y control conscientes de la diversidad. El artículo identifica el paso de "agregación de subgrupo a sistema" como el principal desafío abierto, señalando que las métricas existentes tratan el promedio de todos los pares como un requisito fijo e innegociable.

2. Metodología: Graph-SND

Los autores introducen Graph-SND, una generalización de la SND que reemplaza el promedio del grafo completo con un promedio ponderado sobre las aristas de un grafo arbitrario $G = (A, E, w)$.

Definición

Sea $d(i, j)$ la distancia conductual Monte Carlo entre los agentes $i$ y $j$. La Graph-SND se define como:
$$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$$
donde $W(G) = \sum_{\{i,j\} \in E} w_{ij}$ es el peso total de las aristas.

Tres Regímenes Operativos

El marco soporta tres regímenes distintos basados en la elección del grafo $G$:

1. Recuperación Exacta ($G = K_n$): Cuando $G$ es el grafo completo con pesos unitarios, Graph-SND recupera la SND original exactamente.
2. Diversidad Localizada (Grafos Escasos Fijos): Cuando $G$ es un grafo escaso fijo (por ejemplo, $k$-vecinos más cercanos, topología de comunicación), la métrica mide la diversidad solo sobre interacciones relevantes para la tarea. Esto reduce el costo computacional a $O(|E|)$.
3. Estimación Escasa (Grafos Aleatorios): Cuando las aristas se muestrean aleatoriamente (por ejemplo, muestreo Bernoulli), Graph-SND actúa como un estimador escaso de la SND completa.
   • Estimación Insesgada: Utilizando pesos de Horvitz-Thompson ($w_{ij} = 1/p$), el estimador es incondicionalmente insesgado.
   • Concentración: La media muestral normalizada (pesos uniformes) satisface límites de concentración tipo Hoeffding, convergiendo a la SND verdadera con una tasa de $O(1/\sqrt{m})$, donde $m$ es el número de aristas muestreadas.

Límites Teóricos

• Distorsión Determinista: Para grafos conexos fijos, el artículo deriva límites que relacionan $\text{SND}_G$ con $\text{SND}$ utilizando el índice de reenvío de aristas $\pi(G)$. Específicamente, $|\text{SND}_G - \text{SND}|$ está acotado por factores que involucran $\pi(G)$.
• Grafos Expansores: Para grafos expansores aleatorios $d$-regulares, el índice de reenvío escala como $O(n \log n / d)$. Los autores demuestran que con $d = \Theta(\log n)$, la distorsión relativa en el peor caso es $O(\log n)$.
• Refinamiento Espectral: Bajo estructuras de distancia de rango bajo (norma nuclear normalizada controlada), el límite de error para expansores mejora a $O(\rho^*/\sqrt{d})$, explicando las relaciones empíricas cercanas a la unidad.
• Límites Probabilísticos: Para grafos aleatorios $d$-regulares, se establece un límite probabilístico incondicional de $\tilde{O}(D_{\max}/\sqrt{n})$.

3. Contribuciones Clave

1. Definición de Graph-SND: Una capa de agregación escasa que recupera la SND en grafos completos y cuesta $O(|E|)$ en grafos precalculados.
2. Garantías Teóricas: Demostraciones de recuperación, no negatividad, invariancia bajo automorfismos de grafos, insesgamiento de Horvitz-Thompson e desigualdades de concentración (Hoeffding/Serfling). El artículo también establece límites de distorsión determinista para grafos fijos y límites probabilísticos incondicionales para grafos regulares aleatorios.
3. Validación Empírica:
   • Recuperación e Insesgamiento: Verificado en entornos VMAS, mostrando recuperación exacta en $K_4$ e insesgamiento del estimador de Horvitz-Thompson en $n=8$.
   • Escalabilidad: Se demostraron aceleraciones en tiempo real que escalan linealmente con $1/p$ (probabilidad de muestreo) hasta $n=500$.
   • Control en Bucle Cerrado: Graph-SND se integró en el controlador de diversidad DiCo. En $n=50$, Graph-SND Bernoulli-0.1 rastreó los puntos de ajuste con un error relativo inferior al 1% y produjo diferencias de recompensa indistinguibles de cero en comparación con la SND completa, reduciendo el costo de la métrica por llamada en $\sim 9.5\times$.
   • Rendimiento de Expansores: Los expansores aleatorios $d$-regulares lograron $\text{SND}_G/\text{SND} \in [0.9987, 1.0013]$ con $\Theta(n \log n)$ aristas, superando significativamente a otros baselines escasos en las relaciones distorsión-costo.

4. Resultados

• Eficiencia: En una ejecución de PPO de 500 iteraciones con $n=100$, Graph-SND Bernoulli-0.1 rastreó la SND completa mientras reducía el tiempo de métrica por llamada en aproximadamente $10\times$.
• Escalabilidad: La temporización en GPU con políticas congeladas hasta $n=500$ confirmó la aceleración predicha $\binom{n}{2}/|E|$, reduciendo el tiempo de métrica de ~15.5 segundos a ~1.5 segundos en $n=500$ con una densidad de aristas del 10%.
• Estabilidad de Control: En experimentos DiCo con $n=50$, el controlador escaso mantuvo el seguimiento de puntos de ajuste y produjo diferencias de recompensa emparejadas centradas cerca de cero en nueve celdas emparejadas, con una diferencia media de recompensa de $-6.2 \times 10^{-4}$.
• Robustez: El método se transfirió a configuraciones no gaussianas (PettingZoo MPE con políticas categóricas y Distancia de Variación Total), manteniendo un sesgo pequeño y reducciones de costos.

5. Significado y Afirmaciones

El artículo afirma que Graph-SND elimina con éxito el cuello de botella de agregación de la SND sin alterar la semántica de la métrica ni requerir cambios en las arquitecturas de políticas o algoritmos de entrenamiento.

• Alternativa de Inserción Directa: Proporciona una "alternativa escasa de inserción directa" que escala más allá de la SND de grafo completo, soportando tanto la medición pasiva como el control de diversidad en bucle cerrado.
• Flexibilidad Semántica: El grafo $G$ se presenta no como un parámetro molesto, sino como una elección deliberada que determina el objetivo de medición:
  • Utilizar muestreo Bernoulli para estimar la diversidad del sistema completo.
  • Utilizar grafos locales fijos (por ejemplo, comunicación, $k$-NN) para medir la diversidad relevante para estructuras de interacción específicas.
  • Utilizar grafos expansores para proxies escasos deterministas, casi lineales, con fuertes garantías estructurales en el peor caso.
• Limitaciones Modestas: Los autores reconocen que, aunque los límites teóricos para expansores son $O(\log n)$, las relaciones cercanas a la unidad observadas dependen de los datos y se explican parcialmente por las propiedades espectrales de las matrices de distancia en MARL. También señalan que los experimentos actuales se centran en PPO Independiente, dejando los algoritmos de crítico centralizado para trabajos futuros.

En resumen, Graph-SND replantea la agregación de diversidad como un problema de selección de grafos, ofreciendo un marco unificado que equilibra la eficiencia computacional con garantías teóricas para la diversidad conductual en MARL.