Reinforcement Learning with Symbolic Reward Machines

Cet article propose les Machines de Récompense Symboliques (SRM) et leurs algorithmes d'apprentissage associés, QSRM et LSRM, pour surmonter les limites des Machines de Récompense traditionnelles en éliminant le besoin d'une fonction d'étiquetage manuelle tout en maintenant des performances supérieures et une interprétabilité des tâches dans les cadres d'apprentissage par renforcement standards.

L'essentiel

🤖 L'Agent, le Chef et le Guide Invisible

Imaginez que vous apprenez à un robot à cuisiner un plat complexe.

• Le problème classique : Dans l'apprentissage automatique traditionnel, le robot ne reçoit qu'un "bon" ou un "mauvais" (une récompense) à la fin. Si le robot met le sel avant d'avoir coupé les oignons, il ne sait pas pourquoi c'est raté. Il essaie des millions de combinaisons au hasard. C'est lent et inefficace.
• La solution précédente (les "Reward Machines") : Pour aider le robot, les chercheurs ont inventé des "machines à récompenses". C'est comme un guide invisible qui observe le robot et lui dit : "Ah, tu as coupé les oignons ? Super, tu passes au niveau 2 !" Mais pour que ce guide fonctionne, un humain doit le programmer manuellement pour chaque tâche. Il faut dire au guide : "Si le robot est dans la cuisine, dis-lui 'Oignons coupés'". C'est fastidieux et ça ne marche pas si on change de cuisine (de nouvel environnement).

🚀 La Nouvelle Idée : Les "Machines à Récompenses Symboliques" (SRM)

Les auteurs de ce papier (Thomas Krug et Daniel Neider) ont dit : "Stop ! Pourquoi demander à un humain de traduire tout ce que le robot voit en mots compliqués ?"

Ils proposent une nouvelle méthode appelée Symbolic Reward Machines (SRM).

L'analogie du "Filtre Intelligent"

Imaginez que le robot a des lunettes spéciales. Au lieu de voir des étiquettes magiques ("Oignons", "Sel"), il voit le monde tel qu'il est : des coordonnées, des vitesses, des couleurs.

• L'ancienne méthode (RM) : Le robot doit porter un casque qui transforme son image en étiquettes. Un humain doit programmer ce casque pour chaque pièce de la maison.
• La nouvelle méthode (SRM) : Le robot porte des lunettes qui ont des filtres logiques intégrés.
  • Au lieu de dire "Si étiquette = Oignon", le filtre dit : "Si la position X est entre 5 et 6, ET la position Y est entre 5 et 6, alors c'est la zone des oignons."
  • Le robot lit directement les chiffres de son environnement (la position, la vitesse) et les compare à des règles mathématiques simples (des "gardes").

Le gros avantage ? Vous n'avez plus besoin d'un humain pour créer des étiquettes. Le robot comprend directement le monde physique grâce à ces formules mathématiques.

🧠 Les Deux Super-Héros du Papier

Pour utiliser ces nouvelles lunettes, les auteurs ont créé deux algorithmes (des programmes d'apprentissage) :

1. QSRM (Le Chef avec le Plan) :

   • C'est comme si vous donniez au robot le plan de la recette dès le début.
   • Le robot apprend très vite car il sait exactement quelles étapes suivre grâce aux formules. Il est aussi efficace que les anciennes méthodes, mais beaucoup plus simple à installer car il n'a pas besoin d'étiquettes manuelles.

2. LSRM (Le Détective Autodidacte) :

   • C'est la vraie révolution. Ici, on ne donne aucun plan au robot.
   • Le robot commence à cuisiner au hasard. S'il fait une erreur (il reçoit une mauvaise récompense), il se dit : "Attends, pourquoi j'ai échoué ?"
   • Il observe ses erreurs et invente lui-même les formules (les règles) qui expliquent la récompense.
   • C'est comme si le robot, en cuisinant, découvrait tout seul : "Ah, je dois couper les oignons avant de les cuire !" et il écrit cette règle dans son carnet. À la fin, il vous montre non seulement comment cuisiner, mais aussi pourquoi il a appris cette règle.

🎯 Ce que les expériences ont prouvé

Les chercheurs ont testé leur méthode sur deux types de jeux :

1. Des jeux simples (mondes discrets) : Comme un robot qui doit aller dans des bureaux spécifiques dans un immeuble.
   • Résultat : Le robot a appris aussi vite que les méthodes précédentes, mais sans avoir besoin d'aide humaine pour définir les règles. Il a même réussi à deviner les règles lui-même avec LSRM.
2. Des jeux complexes (mondes continus) : Comme une voiture qui doit monter sur des collines (un environnement avec des valeurs infinies, comme la vitesse ou la position exacte).
   • Résultat : Là encore, ça marche ! Le robot a appris à naviguer dans un monde infini en utilisant ces formules mathématiques, ce que les anciennes méthodes peinaient à faire sans étiquettes précises.

💡 En résumé : Pourquoi c'est génial ?

• Moins de travail pour l'humain : Plus besoin de passer des heures à coder des étiquettes pour chaque nouveau jeu ou chaque nouveau robot.
• Plus de clarté : Le robot ne vous donne pas juste une solution, il vous donne la règle qu'il a apprise. C'est comme si, au lieu de vous dire "Fais ça", il vous disait "Voici la logique : si X est grand et Y est petit, alors fais ça". C'est très facile à comprendre pour un humain.
• Apprentissage de bout en bout : Le robot peut partir d'un environnement standard (comme ceux qu'on trouve dans les bibliothèques de jeux vidéo) et apprendre une tâche complexe sans aucune modification préalable.

En une phrase : Ce papier permet aux robots de comprendre la logique cachée derrière les récompenses en lisant directement les chiffres du monde réel, comme un détective qui déduit les règles du jeu en observant les parties, plutôt que de les lire dans un manuel écrit par un humain.

Résumé technique

1. Problématique

L'apprentissage par renforcement (RL) classique repose sur des fonctions de récompense markoviennes, où la récompense dépend uniquement de l'état actuel et de l'action prise. Cependant, de nombreuses tâches réelles impliquent des dépendances temporelles complexes (séquences d'étapes) qui nécessitent des fonctions de récompense non markoviennes.

L'approche existante pour gérer ces tâches est l'utilisation de Machines de Récompense (Reward Machines - RMs). Bien que efficaces, les RMs présentent deux limitations majeures :

1. Dépendance aux étiquettes (Labeling Function) : Elles nécessitent que l'environnement émette des événements de haut niveau (étiquettes) générés par une fonction d'étiquetage manuelle. Cette fonction doit être conçue par un expert pour chaque environnement et tâche, ce qui rend l'approche peu applicable aux frameworks RL standards (comme Gymnasium) et difficile à déployer « out-of-the-box ».
2. Manque de flexibilité : Sans une fonction d'étiquetage appropriée, même des tâches markoviennes simples ne peuvent pas être représentées correctement par une RM.

L'objectif de cet article est de surmonter ces limitations en éliminant le besoin d'une fonction d'étiquetage externe tout en conservant la capacité à modéliser des récompenses non markoviennes et à fournir des représentations interprétables.

2. Méthodologie

Les auteurs proposent les Machines de Récompense Symboliques (Symbolic Reward Machines - SRMs) et deux algorithmes d'apprentissage associés : QSRM et LSRM.

A. Machines de Récompense Symboliques (SRM)

Contrairement aux RMs qui prennent des étiquettes symboliques en entrée, les SRMs consomment directement l'état brut de l'environnement.

• Structure : Une SRM est définie comme un tuple $(L, Q, q_0, \delta, \sigma)$, où $L$ est une logique (ici, l'arithmétique linéaire réelle - LRA).
• Transitions : Les transitions ne sont pas déclenchées par des étiquettes, mais par des gardes ($\phi$) qui sont des formules logiques sur l'espace d'état. Une transition $(p, \phi, q)$ est prise si l'état actuel $s$ satisfait la formule ($s \models \phi$).
• Propriétés : Les SRMs sont déterministes (les gardes de transitions sortantes d'un même état sont mutuellement exclusives) et complètes (une transition existe pour tout état possible).
• Avantage : Elles respectent la définition standard des MDP (Markov Decision Processes) sans nécessiter de modification de l'interface d'interaction agent-environnement.

B. Algorithmes d'Apprentissage

1. QSRM (Q-learning with SRMs) :

   • C'est un algorithme qui suppose que la SRM est fournie par l'utilisateur (similaire à QRM mais sans étiquettes).
   • Il utilise un tableau Q pour chaque état de la SRM.
   • Il met à jour les valeurs Q en utilisant une approche de « multi-update » : il calcule la récompense et la transition de la SRM pour l'état observé et met à jour les Q-values correspondantes pour tous les états de la SRM possibles, accélérant ainsi l'apprentissage.
   • Théorème 1 : QSRM converge vers une politique optimale sous les mêmes conditions que le Q-Learning standard.

2. LSRM (Learning Symbolic Reward Machines) :

   • Cet algorithme apprend la SRM end-to-end à partir des expériences, sans supposer que la structure de la SRM est connue à l'avance.
   • Mécanisme : Il fonctionne par itérations. Il commence avec une hypothèse de SRM simple (un état). Il entraîne une politique via QSRM. Si la récompense observée dans l'environnement diffère de celle prédite par la SRM hypothétique, le trajet est ajouté à un ensemble de contre-exemples.
   • Inférence : LSRM utilise un solveur SMT (Satisfiability Modulo Theories, ici Z3) pour inférer une nouvelle SRM qui est cohérente avec tous les contre-exemples.
   • Deux variantes :
     • LSRM-GF (Given Formulas) : L'utilisateur fournit un ensemble de formules candidates pour les gardes. L'algorithme sélectionne et combine celles qui fonctionnent.
     • LSRM-FT (Formula Templates) : L'algorithme infère les formules à partir de modèles (templates) (ex: intervalles $x \ge a \land x < b$). Il apprend les paramètres des formules (les bornes des intervalles) sans aucune connaissance préalable de la structure de la récompense.

3. Contributions Clés

1. Introduction des SRMs : Une nouvelle représentation des fonctions de récompense non markoviennes qui opère directement sur les états bruts via des formules logiques, éliminant le besoin de fonctions d'étiquetage manuelles.
2. Algorithmes QSRM et LSRM :
   • QSRM permet d'utiliser des SRMs avec des garanties de convergence.
   • LSRM permet l'apprentissage end-to-end de politiques et de la structure de la récompense (la SRM elle-même) simultanément.
3. Interprétabilité : Les SRMs apprises fournissent une explication étape par étape de la tâche (sous forme de formules logiques et de transitions), offrant une transparence sur la structure de la récompense cachée.
4. Compatibilité Standard : La méthode fonctionne avec les environnements RL standards (comme Gymnasium) sans modification de l'API d'interaction.

4. Résultats Expérimentaux

Les méthodes ont été évaluées sur des environnements discrets (Office World) et continus (Mountain Car modifié).

• Comparaison avec les Baselines (RQ1 & RQ2) :
  • Les méthodes basées sur les SRMs (QSRM, DQSRM) surpassent nettement les méthodes de base (Q-Learning, DQN) qui échouent à apprendre les tâches non markoviennes.
  • Équivalence avec QRM : QSRM et QRM (avec étiquettes) atteignent exactement les mêmes performances optimales, confirmant que les SRMs sont une alternative valide et plus flexible aux RMs.
• Apprentissage End-to-End (RQ3) :
  • LSRM apprend des politiques optimales dans les environnements discrets et des politiques très performantes (bien que non optimales à cause de l'approximation fonctionnelle) dans les environnements continus.
• Inférence de la SRM (RQ4) :
  • LSRM-GF et LSRM-FT réussissent à inférer des SRMs qui sont presque sûrement équivalentes aux SRMs réelles utilisées dans l'environnement.
  • Même lorsque la structure inférée n'est pas identique (ex: nombre d'états différent ou gardes légèrement différentes), la politique apprise reste efficace, démontrant la robustesse de l'approche.
  • LSRM-FT a réussi à inférer des formules logiques (intervalles) correctes pour les gardes, fournissant une interprétation humaine de la tâche apprise.

5. Signification et Impact

Cet article représente une avancée significative pour l'application du RL à des tâches complexes et structurées :

• Réduction de la charge humaine : En supprimant le besoin de concevoir manuellement des fonctions d'étiquetage, les SRMs rendent le RL applicable à un plus large éventail d'environnements sans intervention d'experts.
• Explicabilité (XAI) : Contrairement aux réseaux de neurones profonds qui agissent comme des boîtes noires, les SRMs apprises offrent une représentation symbolique et compréhensible de la logique de récompense, ce qui est crucial pour les applications critiques (sécurité, robotique).
• Généralité : La capacité de fonctionner avec des espaces d'états continus et inférieurs grâce aux formules logiques (LRA) ouvre la voie à l'application de ces techniques dans des domaines physiques réels, au-delà des environnements discrets simulés.

En résumé, les auteurs démontrent qu'il est possible d'apprendre des politiques complexes et interprétables dans des environnements standards en utilisant des machines de récompense symboliques, comblant ainsi le fossé entre la théorie des récompenses non markoviennes et la pratique du RL moderne.