Résumé Technique : Apprentissage par Renforcement Multi-Agent Coopératif Conditionné par Automates (ACC-MARL)

1. Énoncé du Problème

L'article traite du défi de l'apprentissage de politiques multi-tâches et multi-agents pour des équipes coopératives opérant sous un régime d'entraînement centralisé et d'exécution décentralisée (CTDE). Le cadre spécifique implique des agents assignés à des tâches temporelles a priori inconnues au moment de l'exécution, qu'ils doivent accomplir sans communication explicite.

La difficulté fondamentale réside dans la généralisation à ces tâches dynamiques tout en satisfaisant des objectifs complexes à long horizon. Les approches existantes utilisant des spécifications formelles (comme les Automates à États Finis Déterministes, ou DFA) pour représenter les tâches sont souvent peu efficaces en termes d'échantillonnage et limitées aux scénarios à tâche unique, nécessitant un réentraînement pour de nouveaux objectifs. De plus, dans un contexte multi-agent, trois défis primordiaux entravent la faisabilité :

1. Dépendance à l'Historique : Les politiques doivent suivre la progression de la tâche (l'historique) pour prendre des décisions, ce qui brise la propriété de Markov et conduit à des politiques sous-optimales.
2. Attribution de Crédit : La récompense au niveau de l'équipe est éparse (n'est accordée qu'à l'achèvement total de la tâche), ce qui rend difficile pour les agents de discerner comment leurs actions individuelles contribuent à l'objectif global.
3. Goulot d'Étranglement de la Représentation : L'apprentissage simultané de représentations latentes des DFA et des politiques de contrôle crée un problème de passage à l'échelle, particulièrement pour les équipes de plus de deux agents.

2. Méthodologie : Cadre ACC-MARL

Les auteurs proposent l'Apprentissage par Renforcement Multi-Agent Coopératif Conditionné par Automates (ACC-MARL), un cadre qui conditionne les politiques décentralisées sur des représentations de tâches dérivées de DFA. L'approche répond aux trois défis via les mécanismes suivants :

A. Atténuation de la Dépendance à l'Historique via une Reformulation Markovienne

Au lieu de conditionner les politiques sur l'historique brut des observations, le cadre augmente l'espace d'état avec l'état minimal actuel du DFA pour chaque agent.

• Mécanisme : À chaque étape, l'état de l'environnement est étiqueté, et les DFA assignés progressent (sont mis à jour) sur la base de ces étiquettes. Les observations des agents sont augmentées des dernières représentations minimales des DFA.
• Résultat : Cela transforme le jeu non-markovien en un jeu markovien sur l'espace produit des états de l'environnement et des états de DFA ($S \times D^n$). Les auteurs prouvent (Théorème 3.1) que la maximisation du rendement dans ce jeu markovien reformulé est équivalente à la maximisation de la probabilité de satisfaire les objectifs temporels originaux lorsque le facteur de remise $\gamma \to 1$.

B. Résolution de l'Attribution de Crédit via le Façonnage de Récompense Basé sur le Potentiel (PBRS)

Pour surmonter la rareté des récompenses, les auteurs appliquent un façonnage de récompense basé sur le potentiel (PBRS).

• Mécanisme : Une fonction de potentiel $\Phi_i$ est définie pour chaque agent $i$, retournant 1 si son DFA assigné est satisfait et 0 sinon. La récompense est façonnée par la différence de potentiel entre l'état actuel et l'état suivant : $R_{PBRS} = R_{base} + \gamma \Phi_i(suivant) - \Phi_i(actuel)$.
• Résultat : Les agents reçoivent un feedback positif dense pour l'achèvement de leurs sous-tâches spécifiques tout en maintenant la garantie théorique que la politique optimale pour la récompense façonnée reste optimale pour l'objectif original.

C. Résolution du Goulot d'Étranglement de la Représentation avec les Plongements (Embeddings) RAD

Pour éviter d'apprendre les représentations latentes des DFA à partir de zéro pendant l'entraînement (ce qui provoque une dégradation des performances dans les équipes plus larges), le cadre utilise des plongements RAD (ReachAvoidDerived) pré-entraînés.

• Mécanisme : Un encodeur de type Réseau de Neurones à Attention sur Graphe (GATv2) gelé mappe les DFA vers des vecteurs latents (Plongements RAD). Ces plongements sont entraînés pour représenter de manière unique des DFA minimisés distincts et encoder les similitudes sémantiques à travers une large classe de tâches temporelles.
• Résultat : Les politiques se conditionnent sur ces plongements fixes plutôt que sur les DFA bruts ou des représentations apprises, découplant ainsi l'apprentissage de la représentation de l'apprentissage du contrôle. Cela permet un passage à l'échelle efficace vers des équipes plus grandes (ex: 4 agents).

D. Assignation Optimale des Tâches

Le cadre exploite les fonctions de valeur apprises pour assigner les tâches de manière optimale lors de la phase de test. En évaluant la performance attendue de l'équipe (somme des fonctions de valeur) pour différentes permutations d'assignation de tâches, le système peut sélectionner une assignation Pareto-optimale qui maximise le succès global de l'équipe, particulièrement dans les environnements asymétriques.

3. Principales Contributions

1. Introduction du Cadre : La proposition d'ACC-MARL, un cadre pour apprendre des politiques multi-tâches, multi-agents et égocentrées conditionnées par des DFA.
2. Garanties Théoriques : Preuve que la reformulation markovienne et le façonnage de récompense proposés préservent l'optimalité par rapport au problème non-markovien original.
3. Solution de Passage à l'Échelle : Démonstration que l'utilisation de plongements RAD pré-entraînés surmonte le goulot d'étranglement de la représentation, permettant un apprentissage efficace dans des équipes de plus de deux agents.
4. Assignation de Tâches : Une méthode pour utiliser les fonctions de valeur apprises afin de calculer des assignations de tâches optimales lors du test.
5. Chaîne d'Outils : Implémentation d'une chaîne d'outils basée sur JAX (DFAx) pour des opérations de DFA parallélisées et un package Python pour intégrer des tâches d'automates dans des applications de RL.

4. Résultats Expérimentaux

Le cadre a été évalué dans un environnement discret et entièrement observable appelé TokenEnv, présentant des variantes à deux et quatre agents avec des configurations impliquant des boutons, des portes et des jetons.

• Faisabilité et Passage à l'Échelle (Q1 & Q2) :
  • Les études d'ablation montrent que sans les solutions proposées (spécifiquement le PBRS et les plongements RAD), les politiques échouent à converger ou atteignent des taux de succès faibles (<0,5).
  • Dans les environnements à 2 agents, les encodeurs pré-entraînés et non entraînés affichent des performances similaires, bien que les plongements pré-entraînés offrent une variance plus faible.
  • Dans les environnements à 4 agents, les politiques utilisant les plongements RAD pré-entraînés surpassent significativement celles apprenant les représentations à partir de zéro, confirmant que le pré-entraînement est crucial pour la scalabilité.
• Généralisation (Q3) :
  • Les politiques entraînées sur des DFA RAD se généralisent à des classes de tâches non vues (Reach et ReachAvoid) ainsi qu'à des DFA hors distribution (OOD) possédant plus d'états que ceux vus durant l'entraînement.
  • Les plongements pré-entraînés améliorent spécifiquement les performances sur les tâches impliquant des contraintes d'évitement ("Avoid" - conditions irréversibles).
• Assignation de Tâches (Q4) :
  • Dans les environnements symétriques (Buttons), l'ordre d'assignation des tâches n'a eu qu'un impact négligeable.
  • Dans les environnements asymétriques (Rooms), l'assignation de tâche optimale dérivée des fonctions de valeur apprises a considérablement amélioré les probabilités de succès de l'équipe par rapport à une assignation aléatoire.
• Comportements Émergents (Q5) :
  • L'analyse qualitative révèle des compétences de coopération émergentes, telles que des agents tenant des portes pour leurs coéquipiers afin de gagner du temps, ou le "raccourcissement" de tâches (ex: un agent déverrouille une porte pour permettre à un autre de prendre un chemin plus court).

5. Signification et Revendications

L'article affirme être le premier travail à utiliser des spécifications formelles (DFA) dans un cadre de MARL coopératif multi-tâches où les tâches sont assignées au moment de l'exécution. Sa signification réside dans :

• Le Pont entre Méthodes Formelles et MARL : Il étend l'apprentissage par renforcement conditionné par automates du cas mono-agent au cas multi-agent, permettant la décomposition d'objectifs d'équipe complexes en sous-tâches.
• La Résolution du Défi de la Scalabilité : En découplant l'apprentissage de la représentation via des plongements pré-entraînés, il répond aux goulots d'étranglement de performance qui limitaient auparavant l'apprentissage par automates conditionné à de petites équipes.
• Optimalité : Il fournit une approche théoriquement fondée qui garantit un comportement d'équipe optimal tout en permettant une attribution de crédit et une généralisation efficaces.

Les auteurs notent des limites, notamment l'hypothèse de fonctions d'étiquetage fixes, l'observabilité complète et le coût computationnel de l'énumération des assignations de tâches pour des équipes très nombreuses. Ils suggèrent des travaux futurs concernant l'observabilité partielle, l'étiquetage dynamique et les domaines continus.