Résumé Technique : History Matters: Meta-Policy Delegation with Heterogeneous Multi-Agent Reinforcement Learning

1. Formulation du Problème

Le document traite du défi de la délégation de tâches au sein de systèmes multi-agents (SMA) hétérogènes, plus précisément ceux composés d'agents IA (par exemple, des Large Language Models) possédant des capacités, des structures de propriété et des coûts opérationnels variés. Le problème central est de déterminer quel agent doit exécuter une étape spécifique d'une tâche et comment les agents doivent se déléguer les tâches afin de minimiser les coûts totaux d'exécution tout en maintenant une performance de tâche efficace.

Les auteurs modélisent cela comme un Jeu de Markov Collaboratif (MG) construit sur une couche de politiques de tâches pré-entraînées ($\mu_i$). Contrairement aux approches existantes qui reposent sur des routeurs centralisés ou des cascades de modèles statiques, ce travail traite la délégation comme une couche de décision séquentielle explicite où les agents choisissent d'exécuter, de déléguer ou de rester inactifs. Le système doit naviguer à travers trois contraintes structurelles spécifiques :

1. Contraintes de Gestion : Un contrôle hiérarchique unidirectionnel où les supérieurs peuvent imposer la délégation à des subordonnés.
2. Contraintes de Délégation : Un graphe dirigé général permettant à n'importe quel agent de déléguer à n'importe quel autre, supprimant la hiérarchie stricte.
3. Échange d'Argent : Un mécanisme par lequel les agents incitent leurs pairs à accepter des tâches déléguées coûteuses grâce à une monnaie interne transférable.

Une lacune théorique critique identifiée est que l'apprentissage par renforcement multi-agent (MARL) traditionnel dans les environnements pleinement observables restreint souvent les politiques à dépendre uniquement de l'état actuel (politiques de Markov). Le document soutient que les politiques dépendantes de l'historique — qui conditionnent les actions sur les actions conjointes et les interactions passées — sont nécessaires pour soutenir la réciprocité, la confiance et les incitations intertemporelles, même lorsque l'état de l'environnement est pleinement observable.

2. Méthodologie

2.1. Cadres de Collaboration

Le document propose deux nouveaux cadres pour faciliter la délégation :

A. Formulation de Politique Dépendante de l'Historique
Au lieu des politiques de Markov standard $\pi(s)$, les auteurs définissent des politiques $\pi(h_t)$ qui dépendent de l'historique public $h_t = (x_1, a_1, \dots, x_t)$, incluant les actions conjointes précédentes.

• Motivation : Dans un exemple de jeu en deux étapes, les auteurs démontrent que les politiques dépendantes de l'historique peuvent atteindre un équilibre de Nash avec des rendements plus élevés (par exemple, l'Agent A supporte un coût tôt, et l'Agent B réciproque plus tard) ce qui est impossible sous les restrictions de Markov.
• Algorithme : Un Algorithme d'Itération de la Valeur de Nash en deux étapes est développé pour trouver des équilibres de Nash déterministes et de sous-jeu qui favorisent des agents spécifiques. Cela est étendu aux jeux de $n$ étapes par induction.

B. Mécanisme de Transfert d'Argent Virtuel
Pour rendre les politiques dépendantes de l'historique pratiques en MARL sans dépendre de normes sociales complexes, les auteurs introduisent un système d'argent transférable.

• Augmentation de l'État : L'état de chaque agent est augmenté d'un solde d'argent $w_i$, formant $\tilde{s}_i = (s, w_i)$.
• Séparation des Préoccupations : L'« argent » est distinct de la récompense environnementale. L'argent sert de registre interne enregistrant les interactions passées et facilitant la délégation, tandis que l'objectif reste la maximisation des récompenses environnementales.
• Mécanisme : Les agents choisissent des actions physiques et des actions de transfert d'argent ($p_{ij}$). Les transferts sont contraints par le solde actuel de l'agent. Si un agent manque de fonds, l'action conjointe souhaitée devient irréalisable. Cela crée un environnement contraint par le budget qui encourage naturellement le comportement coopératif au fil du temps.

2.2. Configuration Expérimentale

Les auteurs valident leur approche en utilisant le benchmark GSM8K (problèmes mathématiques de niveau primaire) avec une « pile de solveurs gelée » :

• Agents : Trois solveurs LLM hétérogènes avec différents coûts et capacités :
  • Solver A : Nemotron 3 Ultra (Haute capacité, coût élevé).
  • Solver B : Llama 3.2 3B (Capacité moyenne, coût moyen).
  • Solver C : Llama 3.2 1B (Faible capacité, faible coût).
• Entraînement : Un coordinateur DQN centralisé est entraîné pour gérer la délégation, tandis que les solveurs restent gelés. Le système utilise la mise en cache hors ligne des réponses pour assurer la reproductibilité et éliminer la variance des coûts d'API pendant l'entraînement.
• Baselines : Des comparaisons sont faites avec une baseline « Always-Ultra » (envoyer toutes les tâches à l'agent le plus capable) et une baseline « Management » (délégation hiérarchique).

3. Contributions Clés

1. La Délégation comme Problème de Décision Séquentielle : Ce travail formule la délégation non pas comme une règle de routage statique mais comme un problème de décision multi-agent séquentiel où des agents dotés de capacités pré-entraînées hétérogènes choisissent dynamiquement les chemins d'exécution ou de délégation.
2. Théorie de la Politique Dépendante de l'Historique : Le document introduit et valide théoriquement une formulation de politique dépendante de l'historique pour les environnements pleinement observables. Il démontre que le conditionnement sur les actions conjointes passées peut soutenir des équilibres de réciprocité avec des rendements plus élevés que les politiques de Markov standard.
3. Cadre d'Argent Virtuel : Un mécanisme pratique est proposé où un solde d'argent transférable et contraint par le budget agit comme un résumé compact de l'historique des interactions. Cela permet aux agents d'inciter la coopération et la délégation sans modifier la fonction de récompense environnementale primaire.
4. Validation Empirique : L'étude fournit des preuves numériques que les politiques de délégation apprises surpassent significativement les baselines statiques en termes d'efficacité des coûts et de rendement.

4. Résultats

4.1. Contraintes de Gestion (Hiérarchique)

Dans le cadre hiérarchique (A $\to$ B $\to$ C) :

• Performance : Le coordinateur appris par MARL a obtenu un rendement de 27,56 contre 23,90 pour la baseline « Always-Ultra ».
• Coût : La politique apprise a réduit le coût par épisode à 0,033 $ (environ 31,1 $ cumulés sur 1000 épisodes) contre 0,063 $ pour la baseline (environ 60,8 $ cumulés).
• Précision : La politique apprise a maintenu une précision élevée (0,982) par rapport à la baseline (0,971).
• Comportement : La politique a appris à s'appuyer fortement sur le Solver B (coût moyen), n'utilisant le Solver A que lorsque nécessaire, et utilisant rarement le Solver C (le moins cher).

4.2. Contraintes de Délégation (Basées sur un Graphe)

Dans le cadre du graphe non restreint (tout agent peut déléguer à n'importe quel autre) :

• Performance : Le coordinateur du graphe a obtenu un rendement de 25,20, surpassant « Always-Ultra » (23,31) mais sous-performant légèrement la politique hiérarchique gelée (28,70).
• Coût : Le coût est tombé à 0,043 $ par épisode (45,5 $ cumulés), soit une réduction d'environ 37 % par rapport à « Always-Ultra » (66,7 $).
• Compromis : La politique du graphe a utilisé le Solver C plus fréquemment et a permis à plusieurs agents de répondre simultanément. Bien que cela ait augmenté la flexibilité, cela a entraîné une précision légèrement inférieure (0,961) par rapport à la politique hiérarchique (0,986), suggérant un compromis entre la réduction des coûts et l'optimisation stricte de la performance en l'absence de hiérarchie.

4.3. Mécanisme de Transfert d'Argent

Dans un jeu séquentiel synthétique à deux agents :

• Sans Argent : Les agents utilisant le Q-learning indépendant ont échoué à coopérer, résultant en un rendement environnemental de 0 car les deux agents ont choisi « Null » (non-coopération).
• Avec Argent : L'introduction de soldes transférables a permis un équilibre pleinement coopératif. Les agents ont réussi à transférer des fonds pour inciter l'action « Yes », atteignant un rendement environnemental de 990 par épisode.

5. Signification et Revendications

Le document affirme qu'un système multi-agent efficace doit dépasser le routage statique et les simples politiques basées sur l'état. En formulant la délégation comme un jeu séquentiel et en introduisant des politiques dépendantes de l'historique et de l'argent virtuel, les auteurs démontrent que les agents peuvent apprendre à se coordonner, à se faire confiance et à allouer les ressources efficacement, même dans des scénarios contraints par les coûts.

La signification réside dans :

• Réduction des Coûts : Démontrer que la délégation apprise peut réduire les coûts opérationnels d'environ la moitié tout en maintenant ou en améliorant la performance des tâches.
• Aperçu Théorique : Montrer que la dépendance à l'historique n'est pas seulement pour les environnements partiellement observables, mais qu'elle est cruciale pour établir la réciprocité et la confiance dans les contextes multi-agents pleinement observables.
• Mécanisme Pratique : Fournir un mécanisme d'argent concret, contraint par le budget, qui facilite la collaboration sans nécessendre de façonnage complexe des récompenses externes.

Les auteurs reconnaissent modestement les limites, notant que le travail ne traite pas encore de la tarification dynamique des actions conjointes basée sur l'historique et que des algorithmes plus efficaces sont nécessaires pour trouver les équilibres de Nash dans des espaces plus vastes dépendant de l'historique.