🤖 AI

Composing Reinforcement Learning Policies, with Formal Guarantees

Cet article propose un nouveau cadre qui combine la synthèse réactive pour la planification de haut niveau avec une approche d'apprentissage par renforcement pour l'entraînement de politiques de bas niveau sur des structures latentes afin de composer des contrôleurs pour des environnements complexes à deux niveaux, tout en fournissant des garanties de performance formelles sans nécessiter de distillation de modèle.

Auteurs originaux : Florent Delgrange, Guy Avni, Anna Lukina, Christian Schilling, Ann Nowé, Guillermo A. Pérez

Publié 2026-08-06

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Florent Delgrange, Guy Avni, Anna Lukina, Christian Schilling, Ann Nowé, Guillermo A. Pérez

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'apprendre à un robot à naviguer dans un labyrinthe géant et mouvant. Ce n'est pas un simple labyrinthe ; c'est un monde où les murs peuvent bouger, le sol peut changer, et le robot doit prendre des décisions en une fraction de seconde pour éviter d'être percuté par des obstacles volants. C'est le monde de l'Apprentissage par Renforcement (RL - Reinforcement Learning), une branche de l'intelligence artificielle où les agents apprennent par essais et erreurs, tout comme un chien qui apprend à s'asseoir pour obtenir une friandise. L'objectif est de trouver une « politique » — un ensemble de règles qui dicte à l'agent quoi faire dans chaque situation pour obtenir le meilleur résultat possible.

Cependant, il y a un piège. Bien que le RL soit excellent pour apprendre de l'expérience, il est notoirement mauvais pour fournir des garanties. Si vous demandez à un robot RL standard : « Es-tu sûr à 100 % que tu ne vas pas percuter ce chariot élévateur ? », il ne pourra généralement pas répondre par un « oui » mathématique. Il dira peut-être : « Je pense que tout ira bien », mais dans des métiers critiques pour la sécurité, comme la conduite de voitures ou la gestion de réseaux électriques, le « je pense » ne suffit pas. C'est là qu'intervient la vérification formelle. C'est comme une preuve mathématique stricte qui dit : « Sous ces conditions spécifiques, cette action est garantie sûre ». Le défi auquel les scientifiques sont confrontés est que ces deux mondes — l'apprentissage par l'expérience et la preuve mathématique — ne s'entendent généralement pas. L'apprentissage nécessite des données massives et désordonnées, tandis que les preuves nécessitent des modèles nets et simples. Ce papier s'aventure dans cette intersection complexe pour voir si nous pouvons avoir le beurre et l'argent du beurre : un robot qui apprend les choses difficiles, mais qui possède tout de même un certificat de sécurité.

La Grande Idée : La Carte et les Pièces

Les auteurs, une équipe de chercheurs venant de Belgique, d'Israël, des Pays-Bas, du Danemark et du Royaume-Uni, proposent une manière astucieuse de diviser le problème en deux. Imaginez un immense entrepôt. La vue de haut niveau est une carte simple : une grille de pièces reliées par des portes. Vous connaissez parfaitement la carte. Vous savez que la Pièce A est reliée à la Pièce B, et que la Pièce B mène à la sortie. Mais à l'intérieur de chaque pièce ? C'est un mystère. La « dynamique » (la façon dont les choses bougent, l'emplacement des obstacles) est inconnue et chaotique.

Les auteurs appellent cela une structure à deux niveaux.

Le Haut Niveau (La Carte) : C'est la partie facile. Il s'agit simplement d'un graphe de pièces et de portes.
Le Bas Niveau (Les Pièces) : C'est la partie difficile. À l'intérieur de chaque pièce, l'agent doit esquiver des chariots élévateurs, des travailleurs ou d'autres robots en mouvement. Les règles ici sont complexes et inconnues.

L'astuce principale du papier est la « séparation des préoccupations ». Ils utilisent deux outils différents pour les deux niveaux. Pour la carte de haut niveau, ils utilisent la Synthèse Réactive. Voyez cela comme un planificateur logique super intelligent capable d'analyser la carte et un ensemble de règles (comme « Atteindre la sortie sans rien percuter ») et de prouver mathématiquement le meilleur chemin à suivre. C'est comme un GPS qui ne se perd jamais parce qu'il possède une carte parfaite.

Mais le GPS ne peut pas dire au robot comment esquiver un chariot élévateur à l'intérieur d'une pièce. Pour cela, ils utilisent l'Apprentissage par Renforcement (RL). Le robot apprend en simulant des passages à l'intérieur de chaque pièce, en comprenant comment aller de l'entrée à la sortie sans s'écraser. Le problème est que le RL standard est une « boîte noire » : vous ne savez pas exactement comment il fonctionne et vous ne pouvez pas prouver qu'il est sûr.

Le Tour de Magie : Le Raccourci « Latent »

C'est ici que le papier devient vraiment intéressant. Au lieu de laisser le robot apprendre un réseau de neurones géant et désordonné (un cerveau fait de mathématiques) pour chaque pièce, les auteurs apprennent au robot à apprendre un modèle latent concis.

Imaginez que vous essayiez de décrire une pièce chaotique remplie d'obstacles en mouvement à un ami. Vous pourriez essayer de décrire chaque mouvement de chaque objet, ce qui prendrait un temps infini et serait impossible à mémoriser. Ou bien, vous pourriez créer un croquis simplifié (le « modèle latent ») qui capture l'essence de la pièce : « Si je vais à gauche, je frappe généralement un mur ; si je vais à droite, je trouve généralement la porte. »

Les auteurs ont développé une nouvelle méthode d'entraînement appelée WAE-DQN. C'est le nom sophistiqué d'un processus où le robot apprend deux choses simultanément :

Comment agir (la politique).
Comment dessiner le croquis simplifié (le modèle latent).

Crucialement, ils ne se contentent pas de deviner le croquis ; ils calculent une garantie sur la qualité du croquis. Ils utilisent ce qu'on appelle les bornes PAC (Probablement Approximativement Correct). Voyez cela comme un « score de confiance ». Cela ne dit pas « Ce croquis est parfait ». Cela dit : « Nous sommes sûrs à 95 % que ce croquis est à moins de 1 % du comportement réel de la pièce. »

Mise en œuvre Globale : Le Planificateur

Une fois que le robot a appris ces croquis simplifiés et les « scores de confiance » pour chaque pièce, le planificateur de haut niveau entre en jeu. Le planificateur examine la carte et les croquis. Il demande : « Si j'envoie le robot dans la Pièce A et que je lui dis d'aller à droite, quelles sont les chances qu'il atteigne la porte ? » Il utilise les scores de confiance des croquis pour répondre mathématiquement.

Parce que le planificateur connaît la « marge de sécurité » de chaque croquis de pièce, il peut construire un plan global qui est mathématiquement garanti, même si le robot a appris les détails des pièces par essais et erreurs.

Les Expériences : Est-ce que ça marche ?

L'équipe a testé cette idée dans deux mondes très différents :

Un Monde de Grille (Grid World) : Un labyrille numérique avec des ennemis en mouvement.
ViZDoom : Un environnement de jeu vidéo (basé sur le classique Doom) où le robot doit naviguer en utilisant des entrées visuelles (comme une caméra) tout en esquivant des ennemis.

Dans le Grid World, ils ont créé un labyrinthe avec 9 pièces et 11 ennemis en mouvement. L'IA standard (utilisant une méthode appelée DQN) avait du mal à apprendre un bon chemin, se retrouvant souvent bloquée ou percutant des obstacles. Mais la nouvelle méthode ? Elle a appris à naviguer avec succès. Plus impressionnant encore, ils ont testé l'approche sur un labyrinthe beaucoup plus grand avec 49 pièces et 47 ennemis. Le robot, utilisant les mêmes « croquis » appris dans les petites pièces, a été capable de naviguer avec succès dans le labyrinthe géant. Cela prouve la « réutilisabilité » de leur approche : une fois que vous avez appris à gérer un type de pièce, vous pouvez utiliser ce savoir dans n'importe quelle pièce similaire, peu importe la taille de la carte.

Dans l'expérience ViZDoom, le robot devait gérer des entrées visuelles et tirer sur des ennemis. Les résultats ont montré que les « valeurs latentes » (les prédictions faites par les croquis simplifiés) étaient très proches de ce qui se passait réellement dans le jeu. Par exemple, quand le robot prédisait un taux de réussite de 24 % dans un scénario spécifique, le taux de réussite réel était d'environ 23 %. Cette proximité prouve que les « croquis » étaient assez précis pour être dignes de confiance.

Pourquoi est-ce important ?

La plus grande victoire ici n'est pas seulement que le robot est devenu meilleur au jeu. C'est qu'il est devenu meilleur avec un certificat de sécurité.

Par le passé, si vous vouliez qu'un robot navigue dans un environnement complexe, vous deviez choisir entre :

La Sécurité : Utiliser un modèle simple où vous pouvez prouver que tout est sûr, mais le robot est trop limité pour gérer le chaos du monde réel.
La Compétence : Utiliser un robot d'apprentissage puissant capable de gérer le chaos, mais vous n'avez aucune idée de s'il va s'écraser.

Ce papier montre une troisième voie. En séparant la « carte » des « pièces », et en apprenant au robot à créer des croquis simplifiés et vérifiés des pièces, ils ont créé un système qui est à la fois intelligent (capable de gérer des obstacles mobiles et des entrées visuelles) et sûr (doté de garanties mathématiques).

Les auteurs admettent que leur méthode nécessite encore une « carte » de l'environnement pour commencer. Ils ne peuvent pas simplement jeter un robot dans un monde totalement inconnu et espérer qu'il construise la carte de zéro. Mais pour les environnements dont on connaît la configuration (comme un entrepôt, une grille urbaine ou un système logiciel), mais dont on ignore les détails de ce qui s'y passe, cette approche offre un outil puissant. Elle transforme la « boîte noire » de l'apprentissage en une « boîte de verre » que nous pouvons inspecter, vérifier et en laquelle nous pouvons avoir confiance.

Résumé technique : Composition de politiques d'apprentissage par renforcement avec garanties formelles

Formulation du problème
L'article traite du défi de la construction de politiques de contrôle pour des environnements dotés d'une structure à deux niveaux : un graphe de haut niveau connu (« carte ») où chaque sommet est peuplé par un processus de décision markovien (MDP) aux dynamiques inconnues, appelé « pièce » (room). L'objectif est de satisfaire une tâche à long horizon spécifiée par une formule logique sur la carte de haut niveau (par exemple, « atteindre éventuellement le sommet $T$ ») tout en naviguant à travers ces pièces.

La difficulté centrale réside dans le compromis entre l'extensibilité (scalability) et les garanties formelles. La synthèse réactive traditionnelle peut fournir des garanties formelles pour les tâches de haut niveau mais nécessite des modèles explicites de l'ensemble de l'environnement, ce qui est irréalisable lorsque la dynamique des pièces est inconnue ou de haute dimension. À l'inverse, l'apprentissage par renforcement (RL) gère les dynamiques inconnues et de haute dimension, mais manque généralement de garanties formelles et peine face aux récompenses éparses dans les tâches à long horizon. Les auteurs proposent un cadre qui « sépare les préoccupations », en appliquant la synthèse réactive pour le planificateur de haut niveau et une nouvelle procédure de RL pour le contrôle de bas niveau, visant à combiner l'extensibilité du RL avec les garanties formelles de la synthèse.

Méthodologie
Le cadre produit un contrôleur à deux niveaux composé d'une collection de politiques de bas niveau ( $\Pi$ ) et d'un planificateur de haut niveau ( $\tau$ ).

Apprentissage de bas niveau (WAE-DQN) :
Au lieu d'entraîner directement une politique sur l'environnement brut puis de la distiller dans un modèle (une approche classique en deux étapes), les auteurs proposent une procédure unifiée en une seule étape appelée WAE-DQN. Cette méthode entraîne simultanément :
- Une politique latente ( $\pi$ ) utilisant des réseaux Q-profonds (DQN).
- Un modèle latent concis (un petit MDP) utilisant des auto-encodeurs variationnels de type Wasserstein (WAE-MDPs).
Le modèle latent abstrait l'espace d'états de la pièce via une fonction d'encodage $\phi$ . L'objectif d'entraînement minimise une perte de transition ( $L_P$ ), qui mesure l'écart entre la dynamique de transition de l'environnement d'origine et le modèle latent sous la politique. Ce processus produit des garanties « Probablement Approximativement Correctes » (PAC) sur la qualité de l'abstraction et la performance de la politique sans étape de distillation séparée.
Synthèse de haut niveau :
Étant donné une carte, un ensemble de politiques de bas niveau apprises (une pour chaque pièce et chaque direction de sortie) et une spécification de haut niveau, les auteurs synthétisent un planificateur.
- Ils construisent un MDP succinct ( $M^G_\Pi$ ) où les états représentent la direction d'entrée dans une pièce, et les actions représentent le choix de la direction de sortie suivante.
- Les probabilités de transition dans ce modèle succinct sont définies par les valeurs attendues (probabilités de succès) des politiques latentes de bas niveau.
- Un planificateur standard est synthétisé sur ce modèle succinct pour maximiser l'objectif de haut niveau.
Élévation des garanties (Lifting Guarantees) :
Une contribution théorique critique consiste à prouver que les garanties apprises localement pour chaque pièce peuvent être « élevées » vers le contrôleur global à deux niveaux. Les auteurs montrent que si la distribution initiale de chaque pièce fournit une couverture d'état suffisante pendant l'entraînement, les différences de valeur entre l'environnement réel et le contrôleur abstrait sont bornées. Cela permet aux bornes PAC des abstractions de pièces individuelles de se traduire en garanties formelles pour le planificateur global.

Contributions clés
L'article présente trois contributions théoriques majeures :

Garanties d'apprentissage pour les politiques de bas niveau : Les auteurs établissent une borne (Théorème 1) sur la différence entre les valeurs du modèle latent et de l'environnement réel basée sur la perte de transition ( $L_P$ ). Ils prouvent ensuite (Théorème 2) que ces bornes sont apprenables de manière PAC, fournissant une méthode pour calculer la complexité d'échantillonnage pour atteindre une précision donnée.
Garanties sur le contrôleur synthétisé : L'article démontre les bornes de mémoire pour le planificateur optimal de haut niveau (Théorème 3), montrant qu'un planificateur avec une taille de mémoire proportionnelle au nombre de sommets de la carte est suffisant. De plus, il démontre (Théorème 4) que trouver un planificateur optimal équivaut à résoudre un MDP dont la taille dépend uniquement de la structure de la carte, ignorant ainsi la taille potentiellement massive des pièces individuelles.
Garanties unifiées d'apprentissage et de synthèse : Les auteurs montrent (Théorème 5) que la minimisation de la fonction de perte pour apprendre les abstractions indépendamment pour chaque pièce garantit que les valeurs obtenues par le contrôleur composé à deux niveaux correspondent étroitement aux valeurs de l'environnement réel. Cela valide l'approche de « séparation des préoccupations ».

Résultats et études de cas
Les auteurs valident leur cadre à travers deux études de cas impliquant un agent naviguant dans des environnements avec des obstacles adverses en mouvement :

Grid World : Un environnement de grille scalable avec des nombres variables de pièces et d'adversaires. Le DQN standard avec façonnage de récompense (reward shaping) peinait à trouver des politiques, tandis que le WAE-DQN proposé a réussi à apprendre des objectifs de type « atteindre-éviter » (reach-avoid).
ViZDoom : Un environnement basé sur la vision utilisant le moteur de jeu Doom, présentant des entrées visuelles complexes et des comportements d'adversaires stochastiques.

Dans les deux études, le contrôleur à deux niveaux synthétisé a atteint des probabilités de succès élevées, démontant la capacité de l'approche à surmonter les défis des récompenses éparses. Les valeurs prédites dans les modèles latents correspondaient étroitement aux valeurs empiriques observées dans les environaux réels, confirmant la qualité des abstractions apprises. Notamment, les politiques de bas niveau se sont révélées réutilisables ; le même ensemble de politiques entraîné sur une configuration plus petite a fonctionné efficacement lors de l'augmentation de l'échelle de l'environnement (plus de pièces/adversaires) sans réentraînement des composants de bas niveau.

Signification
L'article affirme que son principal avantage est de fournir des garanties formelles pour les contrôleurs dans des environnements où la synthèse traditionnelle ne passe pas à l'échelle en raison de dynamiques de bas niveau inconnues ou complexes. En séparant la planification de haut niveau (gérée par la synthèse) du contrôle de bas niveau (géré par le RL avec des garanties PAC), le cadre réduit la charge d'ingénierie du façonnage de récompense aux seules tâches locales. Il offre un remède au problème des récompenses éparses du RL et permet la réutilisation des politiques de bas niveau à travers des pièces similaires ou des tâches de haut niveau changeantes. Ce travail comble le fossé entre l'extensibilité du deep RL et la rigueur des méthodes formelles, offrant une voie pour vérifier et synthétiser des contrôleurs pour des systèmes autonomes complexes à plusieurs étapes.