Counterfactual Conditional Likelihood Rewards for Multiagent Exploration

1. Problématique : L'Exploration dans les Systèmes Multi-Agents à Récompenses Sparse

Le papier aborde le défi critique de l'exploration efficace dans les systèmes multi-agents coopératifs, en particulier dans des domaines ouverts (comme la recherche et le sauvetage ou l'exploration planétaire) où les récompenses sont rares (sparse).

• Le défi de la coordination : Dans les tâches à récompenses rares, un agent ne reçoit un signal de retour positif (récompense globale) que si l'équipe entière coordonne ses actions de manière précise.
• Limites des approches actuelles : Les méthodes d'exploration intrinsèque classiques (basées sur la nouveauté ou la maximisation de l'entropie) fonctionnent souvent au niveau de l'agent individuel.
  • Cela conduit à une exploration redondante : les agents explorent les mêmes zones sans se rendre compte des efforts de leurs coéquipiers.
  • L'approche par entropie de l'observation conjointe est difficile à mettre en œuvre car l'espace d'observation conjoint croît de manière combinatoire avec le nombre d'agents, et la non-stationnarité (les politiques des autres agents évoluent) rend les estimateurs de densité instables.
• Objectif : Développer un mécanisme de récompense intrinsèque qui encourage les agents à explorer des régions coordonnées de l'espace d'état, en isolant la contribution unique de chaque agent à l'exploration collective, tout en évitant la redondance.

2. Méthodologie : Récompenses de Vraisemblance Conditionnelle Contrefactuelle (CCL)

Les auteurs proposent une nouvelle fonction de récompense intrinsèque appelée Counterfactual Conditional Likelihood (CCL). Cette méthode s'inscrit dans le paradigme Centralized Training with Decentralized Execution (CTDE), utilisant l'algorithme MAPPO (Multiagent Proximal Policy Optimization).

Concept Clé

Au lieu de maximiser uniformément l'entropie de toutes les observations, le CCL récompense les agents pour les observations qui apportent une information unique à l'observation conjointe de l'équipe. Il compare la vraisemblance de l'observation réelle d'un agent à celle d'une observation « contrefactuelle » (où l'agent serait resté inactif ou aurait gardé son observation précédente).

Détails Techniques

1. Encodage Local : Pour éviter l'ingérable apprentissage d'un réseau d'encodage conjoint, chaque agent utilise un encodeur aléatoire fixe ($\phi$) pour projeter ses observations locales ($o^i_t$) dans un espace de faible dimension ($z^i_t$).
2. Représentation Conjointe : L'observation conjointe de l'équipe est formée par la concaténation des encodages locaux de tous les agents.
3. Calcul Contrefactuel :
   • Pour un agent $i$, on construit une observation contrefactuelle $\tilde{o}^i_t$ en utilisant son observation du pas de temps précédent ($o^i_{t-1}$).
   • On calcule deux vraisemblances conditionnelles dans l'espace des encodages conjoints :
     • $p(o^i_t | o^{-i}_t)$ : Vraisemblance de l'observation réelle étant donné les observations des autres.
     • $p(\tilde{o}^i_t | o^{-i}_t)$ : Vraisemblance de l'observation contrefactuelle étant donné les mêmes observations des autres.
4. Estimation par k-NN : Les vraisemblances sont estimées via des approximations de densité locales basées sur les $k$ plus proches voisins (k-NN) dans la mémoire des épisodes. Une rayon partagé ($\epsilon_{shared}$) est utilisé pour stabiliser la comparaison entre les deux scénarios (réel et contrefactuel).
5. Formule de la Récompense : La récompense intrinsèque $r^{CCL}_i$ est la différence de log-vraisemblance :
   $$r^{CCL}_i = \log p(o^i_t | o^{-i}_t) - \log p(\tilde{o}^i_t | o^{-i}_t)$$
   Cette valeur est ensuite transformée (Softplus) pour garantir la positivité et la stabilité, puis éventuellement pondérée par une valeur de saillance $V(s_t)$ si l'agent détecte un événement rare.

Récompense Mixte

Les auteurs proposent également une combinaison de la récompense CCL avec la maximisation de l'entropie locale (OEM - Local Observation Entropy Maximization) :
$$r^{mix}_t = r_{team} + V(s_t) (r^{CCL}_i + \alpha \cdot r^{Local}_{OEM})$$
Cela permet de combiner la diversité individuelle (OEM) et l'exploration coordonnée (CCL).

3. Contributions Principales

1. Nouvelle Mécanique de Récompense : Introduction du CCL, qui quantifie la contribution informationnelle marginale d'un agent à l'exploration conjointe, évitant ainsi la redondance.
2. Approche Évolutive et Stable : Utilisation d'encodeurs aléatoires locaux et de l'estimation par k-NN avec un rayon partagé pour contourner la malédiction de la dimensionnalité et la non-stationnarité des espaces d'observation conjoints.
3. Synergie Locale/Conjointe : Démonstration que la combinaison de l'entropie locale et de la récompense CCL (récompense mixte) offre un compromis optimal, accélérant l'apprentissage tout en maintenant une coordination élevée.
4. Validation Empirique : Tests rigoureux dans des environnements continus à récompenses rares, montrant une supériorité par rapport aux méthodes basées uniquement sur l'entropie locale.

4. Résultats Expérimentaux

Les expériences ont été menées sur deux types d'environnements : le domaine Multi-Rover (exploration de points d'intérêt avec facteurs de couplage) et les environnements Particle (avec un agent adversaire).

• Efficacité de l'Exploration :
  • Dans le domaine Multi-Rover avec un seul point d'intérêt (POI) et un fort facteur de couplage (nécessitant une coordination stricte), les agents utilisant uniquement l'entropie locale échouent à découvrir la solution (ils se regroupent inutilement).
  • Les agents CCL réussissent systématiquement à découvrir des stratégies coordonnées, atteignant des récompenses d'équipe élevées.
• Réduction de la Redondance : Les cartes thermiques (heat maps) montrent que le CCL favorise une couverture complémentaire de l'environnement, tandis que l'entropie locale conduit à des clusters d'agents explorant les mêmes zones.
• Performance de la Récompense Mixte :
  • La récompense mixte (CCL + OEM) converge plus rapidement dans les tâches moins complexes.
  • Cependant, dans les tâches très difficiles (couplage fort, POI unique), le CCL pur ou avec un faible poids $\alpha$ pour l'OEM est supérieur, car la coordination stricte prime sur la diversité locale.
• Généralisation : Le CCL surpasse l'entropie locale dans tous les scénarios Particle (Prédateur-Proie, Keep Away, Physical Deception), démontrant sa robustesse face à la présence d'adversaires et à la complexité de la tâche.

5. Signification et Conclusion

Ce travail apporte une avancée significative dans l'apprentissage par renforcement multi-agent (MARL) en résolvant le problème de la coordination sous récompenses rares.

• Changement de paradigme : Au lieu de chercher à couvrir uniformément l'espace d'état (ce qui est inefficace en multi-agent), le CCL cible spécifiquement les régions où les observations des agents sont fortement corrélées et nécessaires à la réussite de la tâche.
• Impact pratique : La méthode permet aux systèmes multi-agents de découvrir des comportements collaboratifs complexes sans nécessiter de récompenses de façonnage (reward shaping) spécifiques au domaine.
• Limites et Futur : Les auteurs notent que la précision des estimateurs de densité (k-NN) peut diminuer avec un nombre très élevé d'agents. L'intégration future de stratégies d'exploration basées sur des modèles est suggérée pour surmonter cette limite.

En résumé, le CCL offre une approche fondée sur des principes pour combiner les incitations à la nouveauté locale et la coordination globale, permettant une exploration plus efficace et moins redondante dans des environnements multi-agents complexes.