💻 computer science

Active Reward Machine Inference From Raw State Trajectories

Cet article propose une méthode pour inférer des machines de récompense directement à partir de trajectoires d'états brutes sans accès aux récompenses ou aux étiquettes, en utilisant un apprentissage actif pour améliorer l'efficacité des données et du calcul.

Auteurs originaux : Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

Publié 2026-04-10

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

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

🤖 Le Défi : Apprendre à un robot sans lui donner le mode d'emploi

Imaginez que vous voulez apprendre à un robot à faire des tâches complexes, comme ranger une maison ou livrer des colis dans un entrepôt. Ces tâches ne sont pas juste "aller d'un point A à un point B". Elles ont des étapes : "Prendre l'objet", "Éviter les zones dangereuses", "Déposer l'objet", puis "Recommencer".

Dans le monde de la robotique, on utilise souvent des "Machines à Récompense" (Reward Machines). C'est un peu comme un livre de recettes ou un organigramme qui dit au robot : "Si tu as ramassé le colis, passe à l'étape suivante. Si tu touches la zone rouge, c'est une erreur."

Le problème ? Jusqu'à présent, un humain devait écrire ce livre de recettes à la main. C'est long, difficile, et si on fait une petite erreur, le robot peut devenir fou ou dangereux.

🕵️‍♂️ L'Idée Géniale : Deviner la recette en regardant le chef cuisiner

Les auteurs de ce papier se sont dit : "Et si on ne demandait pas à l'humain d'écrire la recette, mais qu'on apprenait au robot à la deviner tout seul en regardant un expert faire le travail ?"

Mais il y a un gros hic : le robot ne voit que les mouvements du robot expert (les états). Il ne voit pas :

Les points de récompense (les "bonbons" que l'expert reçoit).
Les étiquettes (il ne sait pas que cette zone s'appelle "Zone de dépôt").
Les étapes internes de la machine (il ne voit pas le "livre de recettes" ouvert).

C'est comme essayer de deviner les règles d'un jeu de société en regardant quelqu'un jouer, sans voir les dés, sans voir les cartes, et sans entendre les commentaires. On ne voit que les pions qui bougent sur le plateau.

🔍 La Solution : Le Détective de l'Histoire

Le papier propose une méthode pour reconstituer ce "livre de recettes" caché en utilisant deux idées principales :

1. Le "Test de l'Histoire" (La logique du détective)

Imaginez que vous observez deux robots experts.

Robot A a suivi le chemin : Entrée -> Cuisine -> Salon.
Robot B a suivi le chemin : Entrée -> Cuisine -> Garage.

Si, à la fin, le Robot A fait une action différente du Robot B (par exemple, A prend un café, B prend un outil), alors vous savez que la machine interne a dû changer d'état après le Salon ou le Garage.

Les chercheurs ont créé un algorithme mathématique (basé sur la logique booléenne, un peu comme un puzzle géant) qui dit : "Pour que ces deux robots aient des comportements différents, il faut que la machine cachée ait une structure précise." En accumulant des milliers de ces observations, l'algorithme élimine toutes les mauvaises hypothèses jusqu'à ne garder que la vraie structure (ou une version très proche).

2. L'Apprentissage Actif : Ne pas tout lire, mais lire les pages importantes

Voici le vrai tour de magie. Si vous essayez de regarder toutes les trajectoires possibles dans un grand monde, le nombre de possibilités explose (comme une forêt qui grandit exponentiellement). Votre ordinateur exploserait de mémoire avant de trouver la réponse.

L'algorithme utilise une stratégie de "Sondage Intelligent" (Active Learning) :

Au lieu de lire tout le livre page par page, il demande : "Quelle est la prochaine phrase qui va nous aider le plus à trancher entre les deux hypothèses restantes ?"
C'est comme un jeu de "Qui est-ce ?". Au lieu de demander "Est-ce qu'il a des cheveux ?", vous demandez "Est-ce qu'il porte un chapeau ?" parce que vous savez que cela va éliminer la moitié des suspects d'un coup.

L'algorithme choisit intelligemment quelles extensions de trajectoire observer pour éliminer le maximum de fausses solutions avec le minimum d'effort.

🎮 Les Résultats : Des expériences dans des mondes virtuels

Les chercheurs ont testé leur méthode dans des mondes virtuels (des grilles de type "jeu vidéo") :

Le dépôt de colis : Un robot doit aller chercher un objet et le déposer en évitant des pièges.
La patrouille : Un robot doit visiter des pièces dans un ordre précis (A, puis B, puis C...).

Les résultats sont impressionnants :

Précision : L'algorithme a réussi à retrouver exactement les règles cachées (la structure de la machine à récompense et les étiquettes des zones) en regardant seulement les mouvements.
Efficacité : Grâce à la méthode de "Sondage Intelligent", ils ont évité de devoir stocker des milliards de données. Au lieu de prendre 24 Go de mémoire (ce qui est énorme), ils ont utilisé moins de 0,2 Go. C'est comme passer d'un camion de déménagement à un petit sac à dos.
Vitesse : Ils ont trouvé la solution deux fois plus vite que les méthodes traditionnelles qui essaient de tout calculer.

💡 En résumé

Ce papier nous dit que nous n'avons pas besoin de programmer manuellement chaque règle complexe d'un robot. Si nous observons un expert, nous pouvons utiliser des mathématiques intelligentes pour reconstruire la logique cachée de sa réussite, même si nous ne savons pas ce qu'il pense ou ce qu'il ressent.

C'est comme si vous pouviez regarder un grand chef cuisiner préparer un plat complexe, et grâce à un logiciel, vous reconstruirez la recette exacte, les ingrédients et l'ordre des étapes, simplement en observant ses mouvements, sans jamais lui avoir demandé "Quelle est la recette ?".

C'est une étape majeure vers des robots qui peuvent apprendre des tâches complexes de manière autonome, sans que les humains aient à tout leur expliquer mot par mot.

1. Problématique

Le papier aborde le problème de l'apprentissage de Machines de Récompense (Reward Machines - RMs) à partir de trajectoires d'états brutes, dans un régime d'information très pauvre.

Contexte : Les tâches robotiques complexes sont souvent multi-étapes et séquentielles. Les RMs sont des automates finis qui capturent la mémoire nécessaire pour accomplir ces tâches en codant la progression via des transitions déclenchées par des événements de haut niveau (propositions atomiques).
Défi actuel : La spécification manuelle d'une RM (y compris la fonction d'étiquetage qui mappe les états bruts aux propositions) est laborieuse et sujette à des erreurs. Les méthodes existantes d'apprentissage de RMs nécessitent généralement l'accès à des récompenses, des étiquettes (labels) explicites, des nœuds de la machine, ou des démonstrations avec des étiquettes pré-définies.
Objectif du papier : Développer un cadre capable d'inférer à la fois la structure de la machine de récompense (les transitions) et la fonction d'étiquetage (mapping état $\to$ proposition), uniquement à partir de trajectoires d'états bruts et d'une politique d'agent optimale, sans aucune connaissance préalable des récompenses, des labels ou de la structure interne de la machine.

2. Méthodologie

L'approche proposée repose sur deux piliers principaux : une formulation par Satisfiabilité Booléenne (SAT) et une stratégie d'Apprentissage Actif.

A. Inférence par SAT (Apprentissage Passif)

Le problème est formulé comme un problème de satisfaction de contraintes (SAT) pour apprendre la fonction de transition $\delta_u$ et la fonction d'étiquetage $L$ .

Hypothèse de travail : On dispose d'une politique d'histoire $\pi_h$ (dérivée d'une politique optimale sur l'automate produit) qui est accessible.
Exemples Négatifs : Le cœur de la méthode réside dans l'identification de paires de trajectoires d'états $\{\tau, \tau'\}$ qui mènent à des comportements différents (c'est-à-dire que la politique choisit des actions différentes pour le même état final $s$ selon l'historique). Selon le Lemme 1, si $\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$ , alors les trajectoires étiquetées $L(\tau)$ et $L(\tau')$ doivent mener à des nœuds différents dans la RM.
Formulation SAT :
- Les variables binaires encodent les transitions de la RM et les étiquettes des états.
- Les contraintes garantissent que $\delta_u$ et $L$ sont des fonctions bien définies.
- Une contrainte cruciale impose que pour toute paire d'exemple négatif, les nœuds atteints dans la RM soient distincts.
Profondeur Suffisante : L'article démontre théoriquement (Proposition 1) qu'il existe une profondeur critique $l^* = |S| \cdot u_{max}^2$ (où $|S|$ est le nombre d'états MDP et $u_{max}$ le nombre maximal de nœuds) au-delà de laquelle l'ajout de données supplémentaires ne réduit plus l'ensemble des solutions possibles.

B. Extension Active (Active Learning)

Le problème de l'approche exhaustive (SAT sur toutes les trajectoires jusqu'à la profondeur $l^*$ ) est l'explosion combinatoire du nombre de trajectoires, rendant le stockage et le calcul impossibles pour des profondeurs modérées.

Stratégie : Au lieu d'explorer toutes les trajectoires, l'algorithme sélectionne activement des paires de trajectoires à interroger pour maximiser la réduction de l'espace des hypothèses.
Algorithme :
1. On maintient un ensemble de solutions SAT candidates.
2. On génère des paires de trajectoires $\{\tau, \tau'\}$ qui divisent l'ensemble des candidats : pour une moitié des modèles candidats, les trajectoires mènent au même nœud, et pour l'autre moitié, à des nœuds différents.
3. On interroge la politique d'histoire (ou l'environnement) pour vérifier si ces paires sont de véritables "exemples négatifs".
4. Si oui, on ajoute la contrainte au problème SAT et on résout itérativement.
Avantage : Cette approche "volume-removal" permet de converger vers la solution vraie avec beaucoup moins de données et de mémoire.

3. Contributions Clés

Inférence sans étiquettes : C'est la première méthode capable d'apprendre simultanément la structure de la RM et la fonction d'étiquetage à partir de trajectoires d'états bruts, sans aucune connaissance symbolique a priori.
Garantie Théorique : Preuve de l'existence d'une profondeur de trajectoire suffisante ( $l^*$ ) pour garantir l'identifiabilité de la RM (à une permutation près).
Efficacité par Apprentissage Actif : Développement d'un algorithme actif qui évite l'explosion combinatoire des trajectoires, réduisant drastiquement les besoins en mémoire et en temps de calcul tout en garantissant la convergence vers la solution.
Cadre Unifié : Intégration de l'apprentissage de la structure logique (automate) et de la sémantique (étiquetage) dans un seul problème d'optimisation.

4. Résultats Expérimentaux

Les expériences ont été menées sur des environnements de type "grille" (Grid World) avec deux tâches :

Pick_n_drop : Un robot doit aller chercher un objet puis le déposer, en évitant une zone dangereuse.
PatrolABCD : Un robot doit patrouiller dans une séquence de pièces A $\to$ B $\to$ C $\to$ D.

Résultats principaux :

Exactitude : L'algorithme a réussi à retrouver la RM et la fonction d'étiquetage exactes (à une permutation des noms de nœuds et d'étiquettes près) dans les deux tâches.
Performance de l'approche Active :
- Dans la tâche PatrolABCD, l'approche exhaustive nécessitait de stocker 414 millions d'exemples négatifs, consommant 24,76 Go de mémoire et prenant plus de 7100 secondes pour résoudre le SAT.
- L'approche active, en ne gardant que 0,292 million d'exemples négatifs, n'a utilisé que 0,147 Go de mémoire et a réduit le temps total d'exécution à environ 3544 secondes (un gain d'environ 2x).
- L'approche active a convergé vers la solution unique beaucoup plus rapidement (en profondeur 13) que l'approche aléatoire ou exhaustive, qui restait bloquée avec des centaines de solutions candidates.

5. Signification et Perspectives

Ce travail est une étape fondamentale pour l'apprentissage de tâches complexes en robotique sans supervision humaine explicite sur la logique de la tâche.

Impact : Il démontre qu'il est possible de découvrir la structure temporelle cachée d'une tâche (la "mémoire" nécessaire) uniquement en observant les états traversés par un agent compétent.
Limitations actuelles : La méthode suppose un espace d'états discret et fini. Elle nécessite également l'accès à la politique d'histoire (ou une estimation précise de celle-ci à partir de trajectoires état-action).
Futur : Les auteurs suggèrent d'étendre le cadre aux espaces continus (via des fonctions d'étiquetage apprises à partir de représentations perceptuelles), d'améliorer la robustesse au bruit dans les données, et d'intégrer des tests d'équivalence de politiques pour arrêter l'apprentissage plus tôt que la profondeur théorique maximale.

En résumé, ce papier propose une solution élégante et efficace au problème de l'inférence de structures logiques complexes à partir de données brutes, en combinant la puissance de la vérification formelle (SAT) avec l'efficacité de l'apprentissage actif.