[tel-01076437] Planification et apprentissage par renforcement avec modèles d'actions compacts

We study Markovian Decision Processes represented with Probabilistic STRIPS action models A first part of our works is about solving those processes in a compact way To that end we propose two algorithms A first one based on propositional formula manipulation allows to obtain approximate solutions in tractable propositional fragments such as Horn and 2-CNF The second algorithm solves exactly and efficiently problems represented in PPDDL using a new notion of extended value functions The second part is about learning such action models We propose different approaches to solve the problem of ambiguous observations occurring while learning Firstly a heuristic method based on Linear Programming gives good results in practice yet without theoretical guarantees We next describe a learning algorithm in the Knows What It Knows framework This approach gives strong theoretical guarantees on the quality of the learned models as well on the sample complexity These two approaches are then put into a Reinforcement Learning setting to allow an empirical evaluation of their respective performancesNous étudions les Processus de Décision Markoviens représentés de manière compacte via des langages de définition d'actions basés sur le langage STRIPS Probabiliste Une première partie de ce travail traite de la résolution de ces processus de manière compacte Pour cela nous proposons deux algorithmes Un premier basé sur la manipulation de formules propositionnelles permet de résoudre de manière approchée les problèmes dans des fragments propositionnels traitables du type Horn ou 2-CNF Le second algorithme quant à lui résout efficacement et de manière exacte les problèmes représentés en PDDL probabiliste via l'introduction d'une notion de fonction de valeur d'action étendue La seconde partie concerne l'apprentissage de ces modèles d'actions Nous proposons différentes méthodes pour résoudre le problème de l'ambiguïté des observations qui à lieu de lors de l'apprentissage Une première méthode heuristique basée sur la programmation linéaire donne de bons résultats en pratique mais sans garanties théoriques Par la suite nous décrivons une méthode d'apprentissage dans le cadre Knows What It Knows Cette approche donne quant à elle des garanties théoriques sur la qualité des modèles d'actions appris ainsi que sur le nombre d'exemples requis pour obtenir un modèle d'actions correct Ces deux approches sont ensuite incorporées dans un cadre d'apprentissage par renforcement pour une évaluation en pratique de leur performances



from HAL : Dernières publications http://ift.tt/1sOa9hs