Answer-Set-Programming-based Abstractions for Reinforcement Learning

Énoncé du Problème
L'apprentissage par renforcement (RL) permet aux agents d'apprendre des politiques par l'interaction, mais les applications réalistes souffrent souvent d'espaces d'états et d'actions énormes, rendant les approches d'apprentissage naïves intraitables. Bien que les méthodes d'approximation comme le Deep Q-Learning offrent une généralisation, elles nécessitent fréquemment de vastes quantités de données d'entraînement et peuvent présenter une certaine instabilité. L'Apprentissage par Renforcement Relationnel (RRL) répond à ces limitations en utilisant la logique du premier ordre pour raisonner sur des objets et leurs relations, facilitant ainsi la généralisation à travers des états similaires. Plus précisément, le cadre CARCASS (Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces) par van Otterlo (2004) modélise les processus de décision markoviens (MDP) en utilisant des abstractions logiques. Cependant, l'implémentation originale de CARCASS repose sur Prolog et la résolution SLDNF qui, bien que déclarative en principe, nécessite souvent des fonctionnalités procédurales (telles que l'ordre des règles ou les coupures/« cuts ») pour l'efficacité et manque de support natif pour l'inférence non monotone, l'optimisation et la gestion des préférences.

Méthodologie
Les auteurs proposent une méthode générale pour réimplémenter le cadre CARCASS en utilisant la programmation par ensembles de réponses (ASP). L'ASP est un langage de représentation de la connaissance basé sur la logique, entièrement déclaratif, qui supporte le raisonnement non monotone, l'optimisation et les contraintes.

1. Encodage ASP de CARCASS : Les auteurs définissent une fonction de marquage pour mapper les états abstraits et les paires état-action vers des termes de base. Ils construisent un encodage modulaire comprenant :

   • Des programmes ($P_{\hat{s}_i}$) qui encodent les états abstraits individuels sous forme de règles où le corps consiste en les littéraux définissant l'état abstrait.
   • Des programmes ($P_{\hat{s}_i, \hat{a}_{i,j}}$) qui encodent la relation de recouvrement pour les paires état-action abstraites, reliant les actions concrètes aux abstraites via des atomes aCov.
   • Un mécanisme de liste de décision ($P_{\hat{C}}$) utilisant une règle de choix pour sélectionner exactement un état de recouvrement abstrait par état concret et une contrainte pour garantir que la sélection suit la liste ordonnée (en privilégiant l'indice le plus bas).
   • Un état abstrait « vide » ($\hat{s}_\infty$) avec l'indice le plus élevé qui couvre tous les états non couverts par des règles spécifiques, assurant un repli par défaut (fallback).

2. Intégration de l'Apprentissage en Ligne : Les auteurs intègrent cet encodage dans une boucle de Q-learning en ligne (Algorithme 2). Pour un état concret donné, le solveur ASP calcule l'ensemble de réponses optimal pour déterminer l'état de recouvrement abstrait et l'ensemble des actions abstraites admissibles. L'agent sélectionne ensuite une action concrète parmi l'ensemble couvert par l'action abstraite choisie et met à jour la valeur Q de la paire état-action abstraite.

3. Connaissance de Fond : Le cadre permet l'inclusion de connaissances de fond ($P_B$) pour inférer des propriétés complexes (ex: recherche de chemin, complétude d'une tour) directement dans le processus d'abstraction, plutôt que de nécessiter qu'elles soient pré-calculées ou implémentées de manière procédurale.

Contributions Clés

1. Méthode d'Encodage Générale : Le papier introduit une méthode systématique pour encoder les abstractions CARCASS en ASP, démontrant comment un langage entièrement déclaratif peut réaliser des abstractions état-action relationnelles.
2. Adaptation de l'Apprentissage en Ligne : Les auteurs montrent comment utiliser les abstractions CARCASS basées sur l'ASP au sein d'un contexte de Q-learning en ligne, en gérant la sélection dynamique des états et des actions abstraits.
3. Évaluation Empirique : L'implémentation est évaluée dans deux domaines distincts :
   • Blocks World : Une tâche d'empilement de $n$ blocs où l'abstraction réduit l'espace état-action à une taille constante, quel que soit $n$.
   • MiniGrid : Une suite de tâches de navigation en grille (ex: Door Key, Multi Room) où les connaissances de fond sont utilisées pour inférer les configurations de pièces et les chemins les plus courts, construisant des états abstraits basés sur le nœud suivant dans le chemin.

Résultats
L'évaluation empirique compare le Q-learning abstrait au Q-learning concret à travers un monde de 20 blocs et trois environnements MiniGrid.

• Stabilité : Le Q-learning abstrait a démontré une stabilité constante, avec des rendements médians et des écarts interquartiles restant élevés après l'apprentissage initial, tandis que le Q-learning concret a montré des fluctuations significatives ou un échec de convergence dans des environnements complexes.
• Qualité : Le Q-learning abstrait a atteint des taux de succès élevés (ex: proche de 100 % dans les 500 derniers épisodes pour les tâches MiniGrid), surpassant nettement le Q-learning concret, qui a souvent échoué à obtenir des rendements positifs dans le même laps de temps.
• Efficacité d'Échantillonnage : L'approche abstraite a nécessité nettement moins d'épisodes pour apprendre des politiques de haute qualité par rapport à l'approche concrète. Par exemple, dans le monde de 20 blocs, l'apprentissage abstrait a atteint des rendements médians positifs dès l'épisode 376, tandis que l'apprentissage concret est resté au niveau du rendement négatif de base.
• Différences de Modélisation : Dans le cas d'étude MiniGrid, l'encodage ASP a permis une spécification compacte et déclarative de la recherche de chemin et des contraintes, alors que l'implémentation Prolog équivalente nécessitait une recherche algorithmique explicite (recherche en largeur/BFS), soulignant l'avantage de l'ASP pour séparer la spécification du problème de la logique de contrôle.

Signification et Revendications
Le papier conclut que CARCASS implémenté avec l'ASP constitue une approche prometteuse pour construire des abstractions en RL, particulièrement lorsque des connaissances du domaine sont disponibles. Les auteurs affirment que les abstractions basées sur l'ASP offrent une alternative flexible aux versions basées sur Prolog en supportant :

• La Généralisation : Grâce aux représentations relationnelles.
• La Restriction d'Actions : Via des contraintes déclaratives.
• La Décomposition de Problèmes : En encodant des motifs de raisonnement complexes (comme la recherche de chemin ou l'analyse de tour) directement dans les règles.
• Le Raisonnement Avancé : Incluant l'inférence non monotone, l'optimisation et le raisonnement sous connaissance incomplète.

Les auteurs notent modestement que bien que les politiques apprises soient d'une qualité acceptable et apprises avec moins d'échantillons, il n'y a aucune garantie de convergence vers une politique optimale en général, et que l'abstraction elle-même peut ne pas préserver la politique optimale pour les problèmes de planification NP-difficiles (comme vu dans le cas Blocks World où l'abstraction échange l'optimalité contre la tractabilité). Ce travail se positionne comme une étape vers des cadres guidés par la connaissance pour l'apprentissage relationnel par renforcement supportant un apprentissage de politique tolérant à l'élaboration.