A Multi-Agent system for Multi-Objective constrained optimization

Cet article introduit MAMO, un cadre d'apprentissage par renforcement multi-agents qui apprend de manière autonome les poids de récompense optimaux pour équilibrer les objectifs primaires et les violations de contraintes dans des environnements dynamiques, surmontant ainsi les limites de la sélection manuelle des poids dans les approches traditionnelles basées sur le lagrangien.

L'essentiel

Imaginez que vous soyez le gérant d'un café très fréquenté. Vous avez deux objectifs principaux :

1. Maintenir les coûts bas : Ne pas embaucher trop de baristas ou acheter trop de lait, sinon vous perdrez de l'argent.
2. Satisfaire les clients : Ne pas embaucher trop peu de baristas, sinon la file d'attente sera trop longue et les gens partiront en colère (ou, en termes techniques, leurs commandes seront « rejetées »).

Dans le monde réel, le nombre de clients change constamment. Parfois, c'est un mardi matin calme ; parfois, c'est un coup de feu chaotique le vendredi.

L'ancienne méthode : deviner l'équilibre

Traditionnellement, les systèmes informatiques essayant de résoudre ce problème utilisent une méthode appelée « Apprentissage par renforcement » (Reinforcement Learning). Considérez cela comme l'entraînement d'un robot gestionnaire. Pour enseigner au robot, vous lui donnez une fiche d'évaluation. Mais voici le hic : la fiche est un chiffre unique obtenu en mélangeant vos deux objectifs.

• « Si vous économisez de l'argent, vous gagnez +10 points. »
• « Si un client part en colère, vous perdez -50 points. »

Le problème est : qui décide que -50 est le bon chiffre ? Avec l'ancienne méthode, un humain doit deviner et saisir manuellement ces chiffres (appelés « poids »).

• Si vous devinez que la pénalité est trop faible, le robot devient imprudent, économise de l'argent, mais met les clients en colère.
• Si vous devinez que la pénalité est trop élevée, le robot devient extrêmement nerveux, embauchant 20 baristas pour un seul client par mesure de sécurité, gaspillant ainsi de l'argent.

Dans un monde changeant (comme un café qui devient plus fréquenté à différents moments de la journée), le « chiffre parfait » change constamment. Les humains ne peuvent pas suivre en tapant de nouveaux chiffres chaque minute.

La nouvelle méthode : MAMO (Le système à deux agents)

Le document présente un nouveau système appelé MAMO. Au lieu d'un seul robot gestionnaire devinant les règles, MAMO utilise deux robots travaillant ensemble dans une hiérarchie.

1. L'« Exécutant » (Agent d'exécution des tâches)

C'est le robot sur le terrain. Son travail est simple : « Regarde la file d'attente, décide du nombre de baristas à embaucher, et essaie d'obtenir le meilleur score basé sur les règles que je te donne. » Il ne se soucie pas de savoir quelles sont les règles ; il se contente de les suivre.

2. Le « Coach » (Agent d'adaptation des poids)

C'est le robot dans le bureau. Il ne touche jamais à la machine à café. Son seul travail est de surveiller l'« Exécutant » et d'ajuster les règles.

• Le Coach observe les 300 dernières minutes de service.
• Il constate : « Hé, nous avons économisé beaucoup d'argent, mais 10 % des clients sont partis en colère. C'est trop risqué. »
• Alors, le Coach change la règle : « D'accord, je vais rendre la pénalité pour les clients en colère beaucoup plus élevée. »
• Il transmet ces nouvelles règles à l'« Exécutant ».
• L'« Exécutant » essaie à nouveau avec ces nouvelles règles.

Comment ils apprennent ensemble

Ce système fonctionne en boucle, comme un coach et un athlète :

1. Le Coach choisit un ensemble de règles (poids) et dit : « Allez ! »
2. L'Exécutant travaille pendant un certain temps, essayant de faire de son mieux avec ces règles.
3. Le Coach regarde les résultats. Avons-nous satisfait les clients ? Avons-nous économisé de l'argent ?
4. Le Coach ajuste légèrement les règles et commence le tour suivant.

Au fil du temps, le Coach apprend exactement comment équilibrer les règles afin que l'Exécutant trouve naturellement le « juste milieu » sans que le Coach ait besoin de micro-gérer chaque commande de café. Le système trouve l'équilibre parfait de lui-même, s'adaptant lorsque l'« heure de pointe » change.

L'expérience

Les chercheurs ont testé cela sur un système simulé d'« edge computing » (qui est essentiellement un réseau de petits serveurs, comme le café).

• Ils ont essayé de donner à l'« Exécutant » une règle fixe (ex: « Soyez toujours super prudent »). Cela a échoué lorsque la charge de travail est devenue intense.
• Ils ont essayé une autre règle fixe (« Soyez toujours économe »). Cela a échoué car les clients se sont mis en colère.
• Avec MAMO : Le « Coach » a commencé avec une règle aléatoire. Après un certain temps, il a trouvé l'équilibre parfait. Le système a maintenu le taux de clients mécontents (taux de rejet) juste en dessous de la limite (5 %) tout en maintenant les coûts aussi bas que possible, même lorsque la charge de travail était bruyante et imprévisible.

L'essentiel

MAMO est un moyen d'apprendre aux ordinateurs comment effectuer des compromis sans avoir besoin qu'un humain ajuste constamment les paramètres. Cela sépare l'action (faire le travail) de la stratégie (décider de ce qui est le plus important), permettant au système d'apprendre l'équilibre parfait par l'expérience, tout comme un gestionnaire chevronné le ferait.

Résumé technique

Résumé technique : MAMO – Un système multi-agents pour l'optimisation multi-objectif sous contraintes

1. Énoncé du problème

De nombreux problèmes de prise de décision dans les systèmes informatiques et de mise en réseau, particulièrement au sein du Continuum de Calcul (CC), peuvent être formulés comme des problèmes de minimisation de coûts soumis à des contraintes de performance (ex. : latence, débit ou budgets de ressources). Dans des environaux dynamiques caractérisés par des fluctuations de la charge de travail et de la disponibilité des ressources, l'apprentissage par renforcement (RL) est fréquemment employé pour résoudre ces problèmes au moment de l'exécution.

L'approche standard pour gérer les contraintes dans le RL repose sur des formulations d'inspiration lagrangienne, où les violations de contraintes sont agrégées avec le coût primaire en une récompense scalaire unique via des termes de pénalité pondérés choisis manuellement. Cet article identifie une limitation critique de ce paradigme : le comportement de la politique apprise dépend fortement de ces poids fixes.

• Le dilemme du compromis : La sélection de poids appropriés est difficile et spécifique à chaque problème. Des poids incorrects mènent à des politiques soit trop conservatrices (priorisant les contraintes au prix d'un coût élevé), soit trop agressives (minimisant les coûts tout en violant fréquemment les exigences de Qualité de Service (QoS)).
• Non-stationnarité : Dans les environnements dynamiques, l'importance relative des objectifs peut changer au fil du temps, rendant les poids statiques et ajustés manuellement sous-optimaux.

Le papier propose une solution pour découpler l'exécution des tâches de la conception de la fonction d'objectif, passant d'un réglage manuel des paramètres à un mécanisme autonome et adaptatif.

2. Méthodologie : Le cadre MAMO

Les auteurs proposent MAMO (Multi-Agent system for Multi-Objective constrained optimization), un cadre multi-agents hiérarchique conçu pour apprendre le compromis entre des objectifs conflictuels. MAMO traite la sélection des coefficients de pondération de la récompense comme un problème d'apprentissage plutôt que comme un choix de conception fixe.

Architecture

MAMO se compose de deux agents opérant à des échelles de temps et des niveaux d'abstraction différents :

1. Agent d'Exécution de la Tâche (TE - Task-Execution) :

   • Rôle : Interagit directement avec l'environnement pour apprendre une politique de contrôle.
   • Mécanisme : Utilise une fonction de récompense pondérée standard qui agrège le coût primaire et les pénalités de violation de contrainte.
   • Comportement : Pour un ensemble de poids fixes, l'agent TE se comporte comme un agent RL conventionnel, optimisant l'objectif composite.

2. Agent d'Adaptation des Poids (WA - Weight-Adaptation) :

   • Rôle : Opère à un niveau supérieur et à une échelle de temps plus lente. Il n'agit pas directement sur l'environnement.
   • Mécanisme : Sélectionne les valeurs des coefficients de pondération ($w$) qui régulent le compromis dans la fonction de récompense de l'agent TE.
   • Signal d'apprentissage : L'agent WA observe des indicateurs de performance agrégés (ex. : coût d'exécution moyen et probabilité de rejet moyenne) produits par l'agent TE.
     • Si la probabilité de rejet dépasse le seuil de tolérance, l'agent WA reçoit une récompense de zéro (pénalisant les violations de contraintes).
     • Si les contraintes sont respectées, la récompense correspond au coût d'exécution (encourageant des coûts plus bas).
   • Objectif : Apprendre une politique qui mappe les résumés de performance vers de nouvelles valeurs de poids, minimisant les coûts d'exécution tout en imposant les contraintes.

Flux de travail

Le système opère dans une boucle itérative en deux phases :

1. Sélection des poids et entraînement du TE : L'agent WA sélectionne une configuration de poids (initialement aléatoire) et la fixe pour un horizon d'entraînement. L'agent TE interagit avec l'environnement et met à jour sa politique pour optimiser la récompense pondérée.
2. Évaluation et Adaptation : À la fin de l'horizon, l'agent WA observe les indicateurs de performance de l'agent TE. Sur la base de ce retour, il sélectionne une nouvelle configuration de poids, et une nouvelle phase d'entraînement du TE commence.

Cette structure permet à MAMO d'affiner progressivement l'équilibre entre l'efficacité des coûts et la préservation de la QoS directement à partir de l'expérience, sans dépendre d'un réglage manuel.

3. Application de référence : Mise à l'échelle des répliques Edge-FaaS

Pour illustrer le cadre, les auteurs appliquent MAMO à un problème de mise à l'échelle de répliques dans un environnement de calcul de bord (Edge) de type Function-as-a-Service (FaaS).

• Contexte : Les nœuds Edge disposent de ressources limitées (mémoire, calcul) par rapport au cloud. Les applications sont décomposées en fonctions sans état instanciées à la demande.
• Objectif : Minimiser le coût d'initialisation et d'exécution des répliques de fonctions (incluant les surcoûts de démarrage à froid/cold-start) tout en garantissant que la probabilité de rejet des requêtes reste inférieure à une tolérance spécifique ($tol$).
• Défi : Les charges de travail sont non stationnaires (ex. : motifs diurnes) et la disponibilité des ressources fluctue en raison des services colocalisés. La modélisation précise de l'effet conjoint de ces facteurs sur la probabilité de rejet est difficile, ceant le RL sans modèle (model-free) particulièrement adapté.

4. Analyse Expérimentale

Les auteurs ont évalué MAMO dans une instance simplifiée impliquant une fonction unique avec une trace de charge de travail sinusoïdale (émulant des motifs diurnes) et ont ajouté un bruit uniforme pour simuler la non-stationnarité.

Configuration Expérimentale

• Référence (Baseline) : Le problème a été résolu hors ligne avec l'optimiseur Gurobi pour établir une borne inférieure de performance avec une connaissance parfaite.
• Cas de contrôle : L'agent TE a été entraîné avec des poids fixes ($w=0.99$ et $w=0.1$) pour démontrer des comportations extrêmes (sur-provisionnement vs sous-provisionnement).
• Configuration MAMO :
  • Agent TE : Deep Q-Learning avec un réseau entièrement connecté à trois couches.
  • Agent WA : Espace d'action discrétisé (pas de 0.01) pour la sélection des poids.
  • Cycle d'entraînement : Le TE s'entraîne pendant 15 000 itérations par poids ; le WA observe les 300 dernières étapes.
  • Contrainte : La probabilité de rejet doit rester inférieure à 0.05.

Résultats

• Convergence : À mesure que l'agent WA s'entraînait, la probabilité de rejet observée ($p$) s'est approchée du seuil de tolérance de 0.05, tandis que le poids $w$ a convergé vers des valeurs comprises entre 0.8 et 0.9.
• Performance : Bien que la politique apprise ait entraîné des coûts d'exécution légèrement plus élevés (plus de répliques) par rapport à la solution optimale hors ligne, elle a réussi à s'adapter à la charge de travail bruitée.
• Constat clé : MAMO a systématiquement maintenu la probabilité de rejet en dessous du seuil de 0.05, alors que les approches à poids fixes soit violaient les contraintes (faible $w$), soit entraînaient des coûts inutiles (poids élevé).

5. Contributions Clés

1. Découplage de l'exécution et de la conception de l'objectif : MAMO introduit une architecture hiérarchique qui sépare la politique de contrôle (TE) de la conception de la récompense (WA), permettant au système d'adapter sa notion d'"optimalité" à mesure que les conditions évoluent.
2. Adaptation autonome des poids : Contrairement aux approches traditionnelles où les poids sont ajustés manuellement ou optimisés via l'apprentissage méta basé sur le gradient, MAMO cadre la sélection des poids comme un problème de décision séquentielle résolu par un agent distinct.
3. Interprétabilité : L'approche limite l'adaptation à un vecteur de faible dimension de coefficients de scalarisation sur des objectifs prédéfinis, offrant une alternative plus structurée et interprétable aux modèles de récompense intrinsèque libres.
4. Compatibilité Model-Free : La boucle externe (agent WA) ne nécessite pas de différentiabilité à travers le solveur interne (TE), ce qui rend le cadre compatible avec n'importe quel solveur interne.

6. Signification et Travaux Futurs

Les auteurs affirment que MAMO représente une "première étape vers des solutions basées sur le RL plus autonomes et robustes" pour l'optimisation sous contraintes dans des environnements dynamiques. La signification réside dans sa capacité à gérer le compromis entre des objectifs conflictuels sans dépendre de paramètres statiques ajustés manuellement qui pourraient devenir obsolètes lors du changement de la dynamique du système.

Les auteurs restent modestes quant à la portée de l'étude actuelle, notant que l'analyse expérimentale est basée sur un "cas d'usage simple". Les recherches futures prévoient :

• L'évaluation de MAMO sur des problèmes provenant de différents domaines d'application.
• La comparaison de MAMO avec d'autres stratégies de sélection de poids, telles que les schémas de décomposition duale, l'optimisation bayésienne et les algorithmes multi-politiques (ex. : Optimistic Linear Support).