Résumé technique : Une interprétation des Arbres de Comportement Temporels par les Réseaux de Petri à Récompenses

Énoncé du problème

L'apprentissage par renforcement (RL) est confronté à des défis importants dans les environnements à horizon long caractérisés par des récompenses éparses. Dans ces contextes, les agents peinent à effectuer un assignation de crédit et une exploration efficaces car le signal de récompense est retardé et peu fréquent. Bien que des langages de spécification (par exemple, la logique temporelle linéaire ou les automates) aient été utilisés pour dériver automatiquement des fonctions de récompense, ils manquent souvent de contrôle de l'utilisateur sur l'importance relative des sous-tâches. Inversement, le façonnage manuel des récompenses est difficile pour des tâches complexes possédant des structures hiérarchiques et des contraintes temporelles. Le problème central abordé est la manière de générer des fonctions de récompense denses et informatives à partir de spécifications de tâches formelles qui préservent l'intuition de l'utilisateur concernant la hiérarchie des tâches et la criticité des sous-tâches, particulièrement pour les tâches impliquant des séquences, des replis (fallbacks) et des contraintes temporelles.

Méthodologie

Les auteurs proposent un cadre qui interprète les Arbres de Comportement Temporels (TBT) comme des Réseaux de Petri à Récompenses (RPN) pour guider les agents de RL.

1. Arbres de Comportement Temporels (TBT)

Les TBT étendent les arbres de comportement (BT) conventionnels en incorporant des formules de Logique Temporelle Linéaire (LTL) dans les nœuds feuilles.

• Structure : Les TBT utilisent les opérateurs de BT standards : Sequence (exécution séquentielle), Fallback (tentative d'alternatives jusqu'à ce que l'une réussisse), et Parallel (exécution de plusieurs branches, nécessitant qu'un nombre spécifique réussisse).
• Nœuds feuilles : Au lieu de simples actions, les feuilles contiennent des formules LTL (par exemple, $\Diamond a$, signifiant « éventuellement $a$ »).
• Sémantique : L'arbre définit une condition de satisfaction de trace. Une trace satisfait le TBT si l'historique d'exécution satisfait les contraintes logiques définies par les opérateurs et les formules des feuilles.

2. Construction de Réseaux de Petri à Récompenses (RPN)

Le document formalise une traduction des spécifications TBT vers des RPN. Un RPN est un réseau de Petri étendu avec des gardes, des actions et des récompenses.

• Correspondance (Mapping) :
  • Places ($P$) : Représentent les nœuds du TBT (à la fois les nœaux de flux de contrôle et les nœuds feuilles).
  • Transitions ($T$) : Représentent la satisfaction ou la violation d'un nœud.
  • Tokens : Suivent la progression de l'agent vers la satisfaction du TBT.
  • Gardes ($G$) : Expressions booléennes basées sur la sortie des automates dérivés des formules LTL. Les transitions ne se déclenchent que si la garde est évaluée à vrai (par exemple, si la formule LTL d'un nœud feuille est satisfaite).
  • Actions ($Act$) : Gèrent le cycle de vie des automates sous-jacents (démarrage/arrêt) pour gérer le retour en arrière (backtracking). Si un nœud feuille échoue (retourne faux), l'automate est réinitialisé, ce qui permet à l'agent de réessayer, ce qui est crucial pour les propriétés non monotones.
• Déterminisme : La construction assure un comportement déterministe en utilisant des places de contrôle (ex: cT) pour gérer le flux de tokens dans les nœuds Fallback et Parallel, évitant ainsi les boucles infinies ou les états ambigus.

3. Assignation et Distribution de Récompense

Le cadre RPN permet une assignation automatique de la récompense basée sur la structure du TBT.

• Fonctions de distribution : Les auteurs définissent des fonctions récursives ($f_{nLeaf}, f_{nFback}, f_{nParM}, f_{nSeq}$) pour distribuer une récompense totale $r$ à travers l'arbre.
  • Nœuds feuilles : Assignent des récompenses positives pour la satisfaction ($R(t_\phi) = r$) et de petites pénalités pour l'échec ($R(t_{\neg\phi}) = -\alpha r$).
  • Nœuds de contrôle :
    • Fallback : Transmet la récompense complète aux sous-arbres ; l'agent est récompensé pour avoir satisfait n'importe quelle branche.
    • Sequence : Distribue les récompenses de telle sorte que les sous-tâches ultérieures puissent être pondérées plus ou moins fortement selon le schéma (par exemple, des récompenses de croissance monotone pour prioriser l'achèvement de la tâche).
    • Parallel : Distribue les récompenses en fonction du nombre de branches satisfaites.
• Intégration dans l'MDP : Le RPN est intégré dans le Processus de Décision Markovien (MDP). À chaque étape, l'état du RPN (marquage) est mis à jour en fonction des observations de l'agent et des verdicts des automates LTL. La récompense totale émise est la somme des récompenses de toutes les transitions déclenchées.

Principales Contributions

1. Traduction Formelle : Le document fournit une méthode de construction rigoureuse pour traduire les spécifications TBT en Réseaux de Petri à Récompenses, comblant le fossé entre les spécifications de logique temporelle de haut niveau et les signaux de récompense de bas niveau du RL.
2. Façonnage de Récompense Modulaire : En exploitant la structure hiérarchique des TBT, la méthode permet à l'utilisateur de contrôler intuitivement la distribution des récompenses (par exemple, prioriser certaines sous-tâches dans une séquence) sans concevoir manuellement des fonctions de récompense denses.
3. Gestion du Retour en Arrière (Backtracking) : L'intégration des automates avec les RPN permet un mécanisme de « backtracking » où les nœuds feuilles ayant échoué sont réinitialisés, permettant aux agents de réessayer les sous-tâches tout en recevant des pénalités appropriées, ce qui est essentiel pour l'apprentissage dans des environnements non déterministes.
4. Scalabilité : L'approche démontre que les récompenses basées sur les TBT peuvent passer à l'échelle vers des environnements de plus en plus complexes où le RL classique échoue, offrant un moyen structuré de gérer les contraintes hiérarchiques et temporelles.

Résultats Expérimentaux

Les auteurs ont évalué l'approche en utilisant le framework MiniGrid avec l'algorithme PPO à travers quatre environnements de difficulté croissante :

1. Unlock : Récupération séquentielle d'une clé et déverrouillage d'une porte.
2. UnlockPickup : Ajoute la récupération d'un objet cible après le déverrouillage.
3. BlockedUnlockPickup : Introduit des obstacles qui doivent être déplacés avant le déverrouillage.
4. ObstructedMaze-2Dlh & ObstructedMaze-1Q : Labyrinthes complexes avec plusieurs portes verrouillées, des obstacles et des horizons longs, connus pour être difficiles pour le PPO standard.

Approches Comparatives :

• Base Vanilla : Récompenses éparses standard.
• TBT-Baseline : TBT dans l'espace d'observation, récompense unitaire uniquement lors de l'achèvement complet de la tâche.
• TBT-Uniform : Récompense unitaire distribuée uniformément à travers tous les nœuds du TBT.
• TBT-MONINC : Récompense unitaire distribuée aux nœuds feuilles avec des valeurs strictement croissantes (priorisant les sous-objectifs ultérieurs).

Constats :

• Succès de l'apprentissage : Le RL vanilla a échoué à apprendre dans les environnements les plus difficiles (ObstructedMaze). Toutes les approches basées sur le TBT ont permis l'apprentissage.
• Efficacité d'échantillonnage : Les méthodes basées sur le TBT ont considérablement amélioré l'efficacité d'échantillonnage par rapport à la base vanilla.
• Impact de la distribution des récompenses : La variante TBT-MONINC a montré un léger avantage en vitesse d'apprentissage pour les environnements les plus complexes, suggérant que prioriser les sous-objectifs ultérieurs aide à guider l'agent vers l'achèvement de la tâche plus efficacement qu'une distribution uniforme.
• Robustesse : L'approche s'est avérée robuste aux variations de génération procédurale de l'environnement.

Signification et Revendications

Le document affirme que l'interprétation des TBT en tant que RPN offre un mécanisme flexible et intuitif pour la génération de récompenses en RL à long horizon.

• Expressivité : Les TBT offrent une expressivité strictement supérieure aux LTL ou STL (Signal Temporal Logic) standards en raison de leurs opérateurs hiérarchiques.
• Contrôle : Contra�irement à la dérivation automatique de récompense à partir d'automates, cette méthode préserve le contrôle de l'utilisateur sur la pondération des sous-tâches grâce à la structure du TBT et aux fonctions de distribution de récompense.
• Modularité : L'approche facilite la construction modulaire, permettant de construire des tâches complexes à partir de composants TBT plus simples et réutilisables.
• Directions Futures : Les auteurs notent que ce cadre est bien adapté au RL multi-agent (en raison de la gestion intrinsèque de la concurrence des réseaux de Petri) et prévoient d'explorer le façonnage automatique des récompenses via l'itération de valeur sur les RPN et l'utilisation des TBT comme « boucliers » (shields) pendant l'apprentissage.

Ce travail positionne les TBT non seulement comme un outil de spécification, mais comme un générateur direct de signaux de récompense denses et structurés qui surmontent les goulots d'étranglement de l'exploration et de l'assignation de crédit inhérents aux environnements à récompenses éparses.