A Distributed Primal-Dual Method for Constrained Multi-agent Reinforcement Learning with General Parameterization

Resumen Técnico: Un Método Primal-Dual Distribuido para Aprendizaje por Refuerzo Multiagente Constrained con Parametrización General

Formulación del Problema
Este artículo aborda el desafío del Aprendizaje por Refuerzo Multiagente Cooperativo con Restricciones (CMARL) en un entorno de red. El problema se enmarca como un Juego de Markov Constrained (CMG) que involucra a $N$ agentes operando en un entorno compartido. Los agentes cooperan para minimizar una función objetivo global, definida como el promedio de los costos locales esperados, sujeto a $K$ restricciones globales. Estas restricciones también se formulan como el promedio de los costos de restricción locales a través de todos los agentes.

Una distinción crítica de este trabajo es el requisito de aprendizaje en línea totalmente descentralizado. A diferencia del entrenamiento centralizado o de los métodos que requieren coordinación durante la ejecución, el enfoque propuesto asume que los agentes actúan de forma independiente utilizando únicamente información local y comunicación local con sus vecinos. El problema se complica por el hecho de que, a diferencia del RL con restricciones de agente único, el CMARL cooperativo a menudo exhibe una brecha de dualidad no nula, particularmente cuando se utiliza aproximación de funciones general (políticas parametrizadas). Esta brecha introduce una complejidad inherente en el cumplimiento de las restricciones globales mientras se optimiza la función objetivo global.

Metodología
Los autores proponen un algoritmo primal-dual distribuido basado en el marco actor-crítico. La innovación central radica en cómo los agentes manejan los multiplicadores de Lagrange asociados con las restricciones globales.

1. Estimación Local de Multiplicadores: En lugar de depender de un coordinador central para calcular los multiplicadores de Lagrange globales, cada agente $n$ mantiene una estimación local $\hat{\lambda}_n$ del vector de multiplicadores global $\lambda$.
2. Objetivo Descompuesto: El Lagrangiano global se reformula utilizando estas estimaciones locales. Los agentes optimizan un objetivo Lagrangiano local que depende de sus propios parámetros de política $\theta_n$ y de sus estimaciones locales de multiplicadores $\hat{\lambda}_n$.
3. Actualización a Tres Escalas de Tiempo: El algoritmo opera en tres escalas de tiempo distintas para garantizar la convergencia:
   • Escala de Tiempo Más Rápida (Crítico): Los agentes actualizan sus aproximadores locales de la función de valor (críticos) utilizando el aprendizaje de Diferencia Temporal (TD) para estimar el costo Lagrangiano local.
   • Escala de Tiempo Intermedia (Actor): Los agentes actualizan sus parámetros de política (actores) utilizando un teorema de gradiente de política adaptado al entorno multiagente, aprovechando la función de ventaja estimada.
   • Escala de Tiempo Más Lenta (Dual/Multiplicadores): Los agentes actualizan sus estimaciones locales de multiplicadores de Lagrange. Esta actualización implica dos pasos: un paso de consenso donde los agentes promedian sus estimaciones con los vecinos (utilizando una matriz de comunicación doblemente estocástica) y un paso de ascenso basado en la violación local de la restricción.
4. Mecanismo de Consenso: El algoritmo impone consenso entre las estimaciones locales de multiplicadores $\hat{\lambda}_n$ a través de la red. El análisis teórico demuestra que estas estimaciones locales convergen a un valor común, reconstruyendo efectivamente el multiplicador global sin coordinación centralizada.

Contribuciones Clave
El artículo presenta cuatro contribuciones principales:

1. Formulación Distribuida: Introduce una formulación distribuida novedosa para los multiplicadores de Lagrange en CMARL cooperativo, donde cada agente mantiene y actualiza sus propias estimaciones locales utilizando únicamente información local y comunicación con vecinos.
2. Desarrollo del Algoritmo: Desarrolla un algoritmo primal-dual en línea distribuido que utiliza métodos actor-crítico con aproximación de funciones general (críticos lineales y políticas parametrizadas).
3. Garantías de Convergencia: Los autores proporcionan pruebas teóricas que demuestran que los multiplicadores de Lagrange locales alcanzan consenso casi seguro y que el algoritmo general converge a un punto de equilibrio del sistema dinámico proyectado.
4. Análisis de Suboptimalidad y Factibilidad: El artículo analiza la factibilidad de las restricciones en el equilibrio y cuantifica la suboptimalidad de la solución. Deriva una cota superior para la brecha de dualidad del problema parametrizado, teniendo en cuenta los errores introducidos por la parametrización de la política y el proceso de consenso.

Resultados Experimentales
Para validar el enfoque, los autores evaluaron el algoritmo en un juego de Cournot cooperativo con restricciones con dinámicas estocásticas. En este escenario, los agentes actúan como productores en un mercado, eligiendo niveles de producción para maximizar la ganancia (minimizar el costo) mientras cumplen con restricciones basadas en precios.

• Consenso: Los resultados de la simulación (Figura 1) demuestran que los multiplicadores de Lagrange estimados localmente para diferentes agentes convergen a un valor de consenso.
• Rendimiento: Las curvas de entrenamiento (Figura 2) muestran que el algoritmo minimiza con éxito el costo de la función objetivo global mientras mantiene las violaciones de las restricciones globales cerca de cero.

Significado y Afirmaciones
El artículo afirma abordar una brecha en la literatura donde pocos métodos manejan problemas generales de CMARL con costos locales acoplados y restricciones globales de manera totalmente descentralizada. Mientras que los trabajos existentes a menudo dependen de entrenamiento centralizado, compartir parámetros con agentes homogéneos o comunicación durante la ejecución, este método permite el aprendizaje en línea totalmente descentralizado.

Los autores enmarcan modestamente su contribución como una extensión con restricciones de los métodos actor-crítico distribuidos existentes sin restricciones (refiriéndose específicamente a trabajos anteriores sobre MARL sin restricciones). Reconocen que, debido a la brecha de dualidad no nula en entornos cooperativos parametrizados, el algoritmo converge a un punto de equilibrio que puede ser subóptimo en comparación con la solución exacta del problema no parametrizado. Sin embargo, el método propuesto proporciona una solución escalable y descentralizada que garantiza el cumplimiento de las restricciones en escenarios complejos del mundo real, como redes eléctricas inteligentes y sistemas autónomos, sin los cuellos de botella de escalabilidad de los enfoques centralizados.