Résumé Technique : Diviser les Différences, Regrouper le Reste

Énoncé du Problème

Ce travail traite de l'Apprentissage par Imitation Multi-Objectif (MOIL) dans le cadre des Processus de Décision de Markov Multi-Objectifs (MOMDP). Le défi central consiste à retrouver des politiques situées sur le front de Pareto à partir de démonstrations provenant de plusieurs experts, où chaque expert optimise une fonction d'utilité distincte sur une récompense vectorielle partagée.

Les auteurs identifient deux modes d'échec critiques dans les approches existantes :

1. Échec I (Inefficacité Échantillonnaire) : Traiter chaque jeu de données d'expert indépendamment (par exemple, entraîner des modèles de Clonage Comportemental séparés pour chacun) ignore le recouvrement structurel entre les experts. Étant donné que les politiques optimales au sens de Pareto partagent souvent des accords substantiels sur les états-actions, l'apprentissage indépendant exige que la taille de chaque jeu de données évolue linéairement avec la cardinalité de l'espace d'états ($N_\ell = \Omega(|X|)$), entraînant une inefficacité échantillonnaire sévère.
2. Échec II (Violation de Pareto) : Regrouper naïvement toutes les trajectoires d'experts dans un seul jeu de données et entraîner un modèle conjoint (Clonage Comportemental à Sortie Unique) peut aboutir à des politiques dominées. L'analyse théorique (Théorème 2.2) démontre que la politique moyenne de deux experts optimaux au sens de Pareto n'est pas nécessairement optimale au sens de Pareto. Dans des environnements non linéaires, cette agrégation provoque un « affaissement » de la politique apprise vers l'intérieur du polytope des retours, empêchant l'optimisation d'une fonction d'utilité cohérente, même avec des données infinies.

Méthodologie : Clonage Comportemental Augmenté Multi-Sorties (MA-BC)

Pour résoudre ces échecs, les auteurs proposent le Clonage Comportemental Augmenté Multi-Sorties (MA-BC). L'algorithme repose sur une nouvelle propriété structurelle des MOMDP : l'Existence de Chemins de Pareto (Théorème 2.1). Ce théorème établit que deux politiques voisines du front de Pareto différant dans $k$ états peuvent être connectées par une séquence de $k$ politiques intermédiaires optimales au sens de Pareto, où chaque étape diffère exactement par une paire état-action.

Étapes Algorithmiques :

1. Partitionnement : L'algorithme identifie les états divergents ($D_{div}$) où les experts exhibent des actions conflictuelles. Inversement, il définit un ensemble d'états communs ($D_{common}$) où tous les experts s'accordent sur l'action.
2. Curation des Données : Pour chaque expert cible $\ell$, l'algorithme construit un jeu de données curaté $D_\ell \cup D_{common}$. Cela permet à l'apprenant de :
   • Utiliser les données spécifiques de l'expert ($D_\ell$) pour les états divergents.
   • Regrouper les données de tous les experts pour les états communs, réutilisant ainsi efficacement les échantillons là où aucun conflit n'existe.
3. Entraînement : $L$ politiques séparées sont entraînées par Clonage Comportemental sur ces jeux de données curatés.

Extension aux Espaces Continus :
Pour les espaces d'états-actions continus, MA-BC est étendu en augmentant le jeu de données de chaque expert avec des paires état-action compatibles provenant d'autres experts. La compatibilité est définie par une tolérance spatiale $\delta$ et la constante de Lipschitz de la politique de l'expert, créant un compromis biais-variance contrôlé par $\delta$.

Contributions Clés

1. Caractérisation Structurelle (Chemin de Pareto) : L'article introduit une caractérisation géométrique novatrice des MOMDP (Théorème 2.1), démontrant que les politiques optimales au sens de Pareto sont structurellement similaires et connectées par des changements d'état unique, même lorsque plusieurs politiques correspondent au même vecteur de retour (aliasing).
2. Solution Algorithmique (MA-BC) : Les auteurs introduisent MA-BC, qui partitionne systématiquement les données divergentes tout en regroupant les données non conflictuelles.
3. Garanties Théoriques :
   • Convergence : Le Théorème 3.1 prouve que MA-BC converge vers des politiques $\epsilon$-optimales au sens de Pareto. Crucialement, la complexité échantillonnaire pour le jeu de données conjoint évolue avec le nombre total d'états $|X|$, tandis que les tailles des jeux de données individuels des experts n'ont besoin d'évoluer qu'avec le nombre d'états divergents $K$ (où $K \ll |X|$). Cela améliore l'exigence de $\Omega(|X|)$ des apprenants indépendants.
   • Optimalité Minimax : Une nouvelle borne inférieure (Théorème 3.2) est établie pour le MOIL hors ligne, démontrant que MA-BC est optimal au sens minimax. La borne souligne que le gain de performance dépend du coefficient de concentrabilité ($C_{\pi_{data}}$), qui mesure le recouvrement de l'occupation des états entre les experts.
4. Gestion de Données Non Partitionnées : Le cadre est étendu aux scénarios où les identités des experts sont latentes (données non partitionnées), en utilisant un Graphique de Cohérence pour regrouper les paires état-action divergentes (Annexe D).

Résultats Expérimentaux

Les auteurs valident MA-BC sur quatre domaines :

• Benchmarks Discrets : Deep Sea Treasure, Resource Gathering et Slippery Y-Maze.
  • Résultats : Le BC naïf échoue systématiquement à converger vers le front de Pareto (validant l'Échec II). Le BC isolé converge mais présente une mauvaise efficacité échantillonnaire (validant l'Échec I). MA-BC converge vers le front de Pareto significativement plus vite, exploitant les connaissances structurelles partagées.
• Analyse de Concentrabilité : Les expériences montrent que lorsque le recouvrement entre les trajectoires d'experts augmente (abaissant le coefficient de concentrabilité), l'écart de performance entre MA-BC et les apprenants isolés s'élargit, s'alignant avec les prédictions théoriques.
• Contrôle Continu : Une tâche LQR de quadricoptère à 6 degrés de liberté.
  • Résultats : L'étude démontre un « compromis biais-données ». Dans les régimes à faible quantité de données, un seuil de regroupement $\delta$ plus large améliore les performances en partageant agressivement les données. Dans les régimes à forte quantité de données, un $\delta$ plus petit est optimal pour minimiser le biais. L'algorithme récupère avec succès la politique de l'expert Économique avec une efficacité échantillonnaire supérieure par rapport aux références.

Signification et Revendications

L'article revendique être le premier à fournir un cadre prouvablement efficace pour l'apprentissage par imitation hors ligne dans les MOMDP. Sa signification principale réside dans le comblement du fossé entre la nécessité théorique de l'optimalité de Pareto et les contraintes pratiques de l'efficacité des données.

Les auteurs soutiennent que les stratégies d'agrégation standard sont fondamentalement défectueuses dans les contextes multi-objectifs car elles détruisent la structure géométrique du front de Pareto. En exploitant la propriété du Chemin de Pareto, MA-BC atteint un résultat « meilleur des deux mondes » : il maintient les garanties théoriques de l'imitation à expert unique (évitant les politiques dominées) tout en réalisant l'efficacité échantillonnaire de l'apprentissage regroupé (utilisant les recouvrements d'états-actions partagés). Le travail établit que les données de plusieurs experts peuvent effectivement être utilisées pour apprendre efficacement des politiques optimales au sens de Pareto, à condition que les données soient partitionnées en fonction des conflits comportementaux plutôt qu'agrégées aveuglément ou traitées entièrement de manière indépendante.