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

Résumé technique : Une méthode primale-duale distribuée pour l'apprentissage par renforcement multi-agent contraint avec paramétrisation générale

Formulation du problème
Cet article aborde le défi de l'apprentissage par renforcement multi-agent contraint et coopératif (CMARL) dans un contexte réseau. Le problème est formulé comme un jeu de Markov contraint (CMG) impliquant $N$ agents opérant dans un environnement partagé. Les agents visent coopérativement à minimiser une fonction objectif globale, définie comme la moyenne des coûts locaux espérés, sous réserve de $K$ contraintes globales. Ces contraintes sont également formulées comme la moyenne des coûts de contraintes locaux sur l'ensemble des agents.

Une distinction cruciale de ce travail est l'exigence d'un apprentissage en ligne entièrement décentralisé. Contrairement à l'entraînement centralisé ou aux méthodes nécessitant une coordination pendant l'exécution, l'approche proposée suppose que les agents agissent de manière indépendante en utilisant uniquement des informations locales et une communication locale avec leurs voisins. Le problème est compliqué par le fait que, contrairement à l'apprentissage par renforcement contraint à agent unique, le CMARL coopératif présente souvent un écart de dualité non nul, en particulier lors de l'utilisation d'approximation de fonction générale (politiques paramétrées). Cet écart introduit une complexité inhérente à la satisfaction des contraintes globales tout en optimisant l'objectif global.

Méthodologie
Les auteurs proposent un algorithme primale-duale distribué basé sur le cadre acteur-critique. L'innovation centrale réside dans la manière dont les agents gèrent les multiplicateurs de Lagrange associés aux contraintes globales.

1. Estimation locale des multiplicateurs : Au lieu de s'appuyer sur un coordinateur central pour calculer les multiplicateurs de Lagrange globaux, chaque agent $n$ maintient une estimation locale $\hat{\lambda}_n$ du vecteur de multiplicateur global $\lambda$.
2. Objectif décomposé : Le lagrangien global est reformulé à l'aide de ces estimations locales. Les agents optimisent un objectif lagrangien local qui dépend de leurs propres paramètres de politique $\theta_n$ et de leurs estimations locales de multiplicateurs $\hat{\lambda}_n$.
3. Mise à jour à trois échelles de temps : L'algorithme fonctionne sur trois échelles de temps distinctes pour assurer la convergence :
   • Échelle de temps la plus rapide (Critique) : Les agents mettent à jour leurs approximations locales de la fonction de valeur (critiques) en utilisant l'apprentissage par différence temporelle (TD) pour estimer le coût lagrangien local.
   • Échelle de temps intermédiaire (Acteur) : Les agents mettent à jour leurs paramètres de politique (acteurs) en utilisant un théorème du gradient de politique adapté au contexte multi-agent, en utilisant la fonction d'avantage estimée.
   • Échelle de temps la plus lente (Duale/Multiplicateurs) : Les agents mettent à jour leurs estimations locales de multiplicateurs de Lagrange. Cette mise à jour implique deux étapes : une étape de consensus où les agents moyennent leurs estimations avec leurs voisins (en utilisant une matrice de communication doublement stochastique), et une étape de montée basée sur la violation locale de la contrainte.
4. Mécanisme de consensus : L'algorithme impose un consensus entre les estimations locales de multiplicateurs $\hat{\lambda}_n$ à travers le réseau. L'analyse théorique prouve que ces estimations locales convergent vers une valeur commune, reconstruisant efficacement le multiplicateur global sans coordination centralisée.

Contributions clés
L'article apporte quatre contributions principales :

1. Formulation distribuée : Il introduit une formulation distribuée novatrice pour les multiplicateurs de Lagrange dans le CMARL coopératif, où chaque agent maintient et met à jour ses propres estimations locales en utilisant uniquement des informations locales et la communication avec les voisins.
2. Développement d'algorithmes : Il développe un algorithme primale-duale en ligne distribué utilisant des méthodes acteur-critique avec approximation de fonction générale (critiques linéaires et politiques paramétrées).
3. Garanties de convergence : Les auteurs fournissent des preuves théoriques démontrant que les multiplicateurs de Lagrange locaux atteignent un consensus presque sûrement et que l'algorithme global converge vers un point d'équilibre du système dynamique projeté.
4. Analyse de sous-optimalité et de faisabilité : L'article analyse la faisabilité des contraintes à l'équilibre et quantifie la sous-optimalité de la solution. Il dérive une borne supérieure sur l'écart de dualité pour le problème paramétré, tenant compte des erreurs introduites par la paramétrisation de la politique et du processus de consensus.

Résultats expérimentaux
Pour valider l'approche, les auteurs ont évalué l'algorithme sur un jeu de Cournot coopératif contraint avec des dynamiques stochastiques. Dans ce scénario, les agents agissent en tant que producteurs sur un marché, choisissant des niveaux de production pour maximiser le profit (minimiser le coût) tout en respectant des contraintes basées sur les prix.

• Consensus : Les résultats de simulation (Figure 1) démontrent que les multiplicateurs de Lagrange estimés localement pour différents agents convergent vers une valeur de consensus.
• Performance : Les courbes d'entraînement (Figure 2) montrent que l'algorithme minimise avec succès le coût de l'objectif global tout en maintenant les violations de contraintes globales proches de zéro.

Portée et affirmations
L'article prétend combler une lacune dans la littérature où peu de méthodes traitent les problèmes généraux de CMARL avec des coûts locaux couplés et des contraintes globales de manière entièrement décentralisée. Alors que les travaux existants reposent souvent sur un entraînement centralisé, un partage de paramètres avec des agents homogènes, ou une communication au moment de l'exécution, cette méthode permet un apprentissage en ligne entièrement décentralisé.

Les auteurs présentent modestement leur contribution comme une extension contrainte des méthodes existantes d'acteur-critique distribué sans contrainte (faisant spécifiquement référence à des travaux antérieurs sur le MARL sans contrainte). Ils reconnaissent que, en raison de l'écart de dualité non nul dans les contextes coopératifs paramétrés, l'algorithme converge vers un point d'équilibre qui peut être sous-optimal par rapport à la solution exacte du problème non paramétré. Cependant, la méthode proposée fournit une solution évolutive et décentralisée qui garantit la satisfaction des contraintes dans des scénarios complexes et réels tels que les réseaux électriques intelligents et les systèmes autonomes, sans les goulots d'étranglement d'évolutivité des approches centralisées.