ASP-based abstractions for reinforcement learning

Abstract

Die vorliegende Arbeit beschäftigt sich mit dem modellfreien, bestärkenden Lernen in relationalen Markov-Entscheidungsproblemen (RMDPs), die Zustände und Aktionen durch logische, atomare Formeln repräsentieren. Ein fundamentales Hindernis für viele interessante Anwendungsdomänen in diesem Bereich ist eine kombinatorische Explosion derer Zustands-Aktions-Räume, wodurch wertbasierte, tabulare Lernalgorithmen wie “Q-learning” schnell unbrauchbar werden. Praktikable Algorithmen überwinden dieses Hindernis, indem sie tabulare Lernalgorithmen mit Funktionsapproximationstechniken erweitern. Dies erlaubt die Darstellung von sowohl kompakten, als auch generalisierbaren Repräsentationen für Nutzenfunktionen und Strategien. Vorgeschlagene Techniken reichen von hochentwickelten, wie “Relational Reinforcement Learning”, “Deep Relational Reinforcement Learning” und “Neuro-Symbolic Reinforcement Learning”, zu konzeptuell einfacheren, aber immer noch relevanten Techniken, wie Zustands- und Zustands-Aktions-Paar-Abstraktionen. Solche Abstraktionen wurden bereits in Kombination mit einer Vielfalt an Wissensrepräsentationsformalismen untersucht. Allerdings ist das logische Programmieren mit Antwortmengen, das “Answer Set Programming” (ASP), nur spärlich im diesem Rahmen untersucht, obwohl es, dank seine Deklarativität und seiner Fähigkeit zur nichtmonotonen Inferenz, ein interessanter Kandidat für diese Anwendung ist. Um diese Forschungslücke zu füllen, untersucht diese Arbeit die Anwendung von ASP zur Repräsentation von Zustands- und Zustands-Aktions-Paar-Abstraktionen für RMDPs. Es wird eine generelle Methode konzeptualisiert, um Abstraktionen in ASP zu kodieren, und ein Prototyp derselben implementiert. Basierend darauf werden Abstraktionen in zwei konkreten Anwendungsdomänen modelliert und getestet, nämlich für Stapelaufgaben in Blockwelten und für Navigationsaufgaben in “Minigrid“-Umgebungen. Empirische Analysen zeigen, dass es, unter der Nutzung von “Q-learning” und mithilfe der Abstraktionen, möglich ist, Strategien mit akzeptabler Qualität stabil und reproduzierbar zu lernen, und zwar mit weniger Interaktionen als nötig sind, um vergleichbare Strategien ohne die Abstraktionen zu lernen. Diese Resultate sind im Einklang mit der betrachteten Abstraktions-Theorie und einer großen Menge an vorangegangenen empirischen Untersuchungen. Allerdings sind zusätzliche Studien nötig um die Brauchbarkeit unseres Zuganges in praktischen Anwendungen zu prüfen. Nach Wissen des Authors ist die vorliegende Arbeit die erste, die sich im vorgestellten Rahmen mit der Anwendung von ASP zur Repräsentation spezifisch von Zustands-Aktions-Paar-Abstraktionen befasst.

This thesis considers the problem of model-free reinforcement learning (RL) in relational Markov decision processes (RMDPs), where states and actions are represented by atoms, formed from predicates over a domain of objects. A fundamental issue for many interesting task environments in this setting is a combinatorial explosion of their state-action spaces, rendering value-based, tabular learning algorithms, such as Q-learning, intractable. Practical value-based learning algorithms have dealt with this issue by extending tabular learning algorithms with function approximation techniques, allowing for both compact and generalisable representations of learned value functions and policies. Proposed techniques range from highly sophisticated techniques, such as relational RL, deep relational RL, and neuro-symbolic RL, to the conceptually more simple but still relevant techniques of state- and state-action pair abstractions. Such abstractions have been represented in a variety of knowledge representation formalisms but we found answer set programming (ASP) to be under-explored in this use case, even though it is an interesting candidate due to its declarative knowledge processing and non-monotonic reasoning capabilities. In order to close this research gap, ASP is explored as a means of representing state- and state-action pair abstractions for RMDPs. To this end, a general method for encoding abstractions in ASP is devised and implemented as a proof of concept. Two specific abstractions are modelled and tested, one for blocks world stacking tasks and one for navigation tasks in grid worlds from the Minigrid library. An empirical analysis shows that, using Q-learning on the abstract representations, policies of acceptable quality can be learned with high consistency. These policies can also be obtained in a smaller number of samples than what is needed to learn comparable policies without the abstraction. These results are consistent with both the considered theory of abstraction and a large body of previous empirical research but additional studies are needed to test the viability of our approach in real-world applications. To the knowledge of the author, this thesis is the first piece of research to consider ASP as a representation method for state-action pair abstractions in this setting.