Résumé Technique : Identification des Agents Vulnérables dans l'Apprentissage par Renforcement Multi-Agents à Grande Échelle

1. Formulation du Problème

L'article aborde le problème de l'Identification des Agents Vulnérables (VAI) dans les systèmes d'Apprentissage par Renforcement Multi-Agents (MARL) à grande échelle. À mesure que les systèmes s'étendent à des milliers d'agents (par exemple, essaims de robots, réseaux électriques), les défaillances partielles d'agents deviennent inévitables en raison d'erreurs matérielles, de dangers environnementaux ou de contrôles adverses. Le défi central consiste à identifier le sous-ensemble spécifique de $K$ agents dont la compromission entraîne la dégradation maximale de la performance de l'ensemble du système.

Les auteurs cadrent cela comme un problème de Contrôle de Champ Moyen Décentralisé Hiérarchique Adversaire (HAD-MFC) :

• Niveau Supérieur : Une tâche d'optimisation combinatoire visant à sélectionner les $K$ agents les plus vulnérables parmi $N$ agents au total. Les auteurs prouvent que ce sous-problème est NP-difficile en le réduisant au problème généralisé de couverture maximale.
• Niveau Inférieur : Une tâche MARL de champ moyen où une politique adverse est entraînée pour les $K$ agents sélectionnés afin de minimiser l'espérance de récompense du système, en supposant que les agents restants suivent une politique coopérative fixe et bien entraînée.

La difficulté principale réside dans le couplage de ces deux niveaux : résoudre le niveau supérieur nécessite d'évaluer le niveau inférieur pour chaque sous-ensemble candidat, ce qui est computationnellement intraitable pour un $N$ élevé.

2. Méthodologie

Pour résoudre le problème couplé HAD-MFC, les auteurs proposent une stratégie de décomposition qui découple le processus hiérarchique et transforme la tâche de sélection NP-difficile en un Processus de Décision Markovien (MDP) traitable.

2.1 Découplage via la Transformée de Fenchel-Rockafellar

Les auteurs éliminent le besoin d'entraîner un adversaire de niveau inférieur au pire cas pour chaque ensemble candidat pendant la phase de sélection. Au lieu de cela, ils dérivent un opérateur de Bellman de champ moyen régularisé ($B^R_{\epsilon_i, \xi}$).

• En appliquant la transformée de Fenchel-Rockafellar à l'ensemble d'incertitude induit par les perturbations adverses, ils convertissent le problème min-max en une estimation de fonction de valeur régularisée.
• Cet opérateur estime la valeur potentielle au pire cas en utilisant uniquement des trajectoires coopératives. Il introduit des termes de régularisation basés sur le budget de perturbation de l'agent ($\epsilon_i$) et la perturbation de champ moyen ($\xi$), capturant ainsi les vulnérabilités individuelles et systémiques sans entraînement adverse explicite au stade de la sélection.
• Les auteurs prouvent que cette transformation est sans perte (exacte) sous l'hypothèse d'un ensemble d'incertitude convexe, propre et semi-continu inférieurement.

2.2 Reformulation en tant que MDP

Le problème combinatoire de niveau supérieur est reformulé comme un MDP avec des récompenses denses :

• État : L'ensemble actuel d'agents vulnérables sélectionnés et leurs budgets de perturbation.
• Action : Sélectionner le prochain agent à ajouter à l'ensemble d'attaque.
• Récompense : Définie comme la réduction de la valeur espérée du système lorsqu'un nouvel agent est ajouté à l'ensemble d'attaque, calculée efficacement à l'aide de la fonction de valeur régularisée dérivée à l'étape 2.1.

2.3 Algorithmes

Deux algorithmes sont proposés pour résoudre ce MDP :

1. VAI-Greedy : Un algorithme glouton qui sélectionne séquentiellement l'agent maximisant la récompense immédiate (réduction de valeur).
2. VAI-RL : Une approche d'Apprentissage par Renforcement (utilisant Q-learning/DQN) qui apprend une politique pour sélectionner des agents en considérant les retours à long terme et les interactions inter-agents.

Les auteurs prouvent que cette décomposition préserve la solution optimale du HAD-MFC original.

3. Contributions Clés

1. Définition du Problème : La formalisation du VAI dans le MARL à grande échelle comme un problème HAD-MFC et la preuve de sa NP-difficulté.
2. Décomposition Théorique : L'introduction d'une méthode pour découpler le problème hiérarchique en utilisant la transformée de Fenchel-Rockafellar, aboutissant à un opérateur de Bellman régularisé permettant un apprentissage indépendant à chaque niveau.
3. Solution Algorithmique : La formulation de la sélection de niveau supérieur comme un MDP avec des récompenses denses, soluble via des méthodes gloutonnes ou RL, avec des garanties théoriques de préservation de l'optimalité.
4. Validation Empirique : Démonstration que la méthode identifie efficacement les vulnérabilités critiques dans les environnements MARL à grande échelle et les systèmes basés sur des règles.

4. Résultats Expérimentaux

La méthode a été évaluée sur trois environnements : Battle (plateforme MAGENT), Taxi Matching, et Vicsek (un système basé sur des règles).

• Performance : Les méthodes VAI proposées (VAI-Greedy et VAI-RL) ont surpassé cinq lignes de base (Aléatoire, Centralité de Degré, RL Bi-niveau, PIANO, et RTCA) dans 17 tâches sur 18.
• Comparaison :
  • Les méthodes heuristiques (par exemple, Centralité de Degré) ont échoué dans le MARL à grande échelle car elles reposent sur des structures de graphe qui ne capturent pas les interactions non linéaires apprises des agents MARL.
  • Les méthodes existantes basées sur l'apprentissage (par exemple, RTCA, RL Bi-niveau) ont eu du mal en raison de la complexité computationnelle du problème hiérarchique couplé.
  • VAI-RL vs VAI-Greedy : VAI-RL a généralement surpassé VAI-Greedy, en particulier dans les scénarios avec un nombre plus élevé d'attaquants, car il modélise mieux les retours à long terme et les interactions synergiques entre les agents.
• Efficacité : Bien que VAI nécessite un entraînement unique de la fonction de valeur régularisée (~1 heure), le processus de sélection subséquent est hautement efficace. Le coût computationnel global est comparable ou inférieur à celui des lignes de base comme RTCA, qui souffre d'une surcharge élevée due à la recherche évolutionnaire.
• Précision Prédictive : La fonction de valeur régularisée a montré une forte corrélation de Pearson ($R=0,97$ pour Battle, $R=0,91$ pour Taxi) avec la récompense réelle obtenue en exécutant des attaques adverses complètes de niveau inférieur, validant son utilisation comme proxy.

5. Importance et Revendications

L'article revendique que sa contribution principale est de fournir un outil de diagnostic pour les développeurs et administrateurs de systèmes afin d'identifier les « points faibles » dans les systèmes MARL à grande échelle.

• Évaluation de la Robustesse : En identifiant les agents les plus vulnérables, les praticiens peuvent évaluer la robustesse au pire cas du système et potentiellement renforcer ces agents spécifiques.
• Évolutivité : La méthode adresse le goulot d'étranglement de l'évolutivité des travaux antérieurs sur le MARL adversaire, qui étaient limités à des systèmes à petite échelle.
• Applicabilité : L'approche est applicable non seulement aux politiques MARL apprises mais aussi aux systèmes basés sur des règles (comme le modèle Vicsek), à condition que les règles puissent être approximées via des fonctions de valeur.

Les auteurs adoptent une position modeste concernant les implications en matière de sécurité, notant que bien que les attaquants puissent théoriquement utiliser cette méthode, l'exigence d'un accès aux trajectoires du système la rend plus accessible aux défenseurs pour durcir les systèmes qu'aux attaquants pour les exploiter. Le travail suggère des orientations futures pour étendre le VAI à des domaines réels complexes tels que les réseaux sociaux et les modèles économiques basés sur des agents.