Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5715
Main Title: Representation and generalization in autonomous reinforcement learning
Translated Title: Repräsentation und Generalisierung in autonomen belohnungsbasiertem Lernen
Author(s): Böhmer, Wendelin
Advisor(s): Obermayer, Klaus
Referee(s): Obermayer, Klaus
Toussaint, Marc
Opper, Manfred
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: This PhD thesis investigates the role of representations that generalize values in autonomous reinforcement learning (RL). I employ the mathematical framework of function analysis to examine inductive and deductive RL approaches in continuous (or hybrid) state and action spaces. My analysis reveals the importance of the representation’s metric for inductive generalization and the need for structural assumptions to generalize values deductively to entirely new situations. The thesis contributes to two related fields of research: representation learning and deductive value estimation in large state-action spaces. I emphasize here the agent’s autonomy by demanding little to no knowledge about (or restrictions to) possible tasks and environments. In the following I summarize my contributions in more detail. I argue that all isomorphic state spaces (and fully observable observation spaces) differ only in their metric (Böhmer et al., 2015), and show that values can be generalized optimally by a diffusion metric. I prove that when the value is estimated by a linear algorithm like least squares policy iteration (LSPI), slow feature analysis (SFA) approximates an optimal representation for all tasks in the same environment (Böhmer et al., 2013). I demonstrate this claim by deriving a novel regularized sparse kernel SFA algorithm (RSK-SFA, Böhmer et al., 2012) and compare the learned representations with others, for example, in a real LSPI robot-navigation task and in extensive simulations thereof. I also extend the definition of SFA to γ-SFA, which represents only a specified subset of “anticipated” tasks. Autonomous inductive learning suffers the curse of insufficient samples in many realistic tasks, as environments consisting of many variables can have exponentially many states. This precludes inductive representation learning and both inductive and deductive value estimation for these environments, all of which need training samples sufficiently “close” to every state. I propose structural assumptions on the state dynamics to break the curse. I investigate state spaces with sparse conditional independent transitions, called Bayesian dynamic networks (DBN). In difference to value functions, sparse DBN transition models can be learned inductively without suffering the above curse. To this end, I define the new class of linear factored functions (LFF, Böhmer and Obermayer, 2015), which can compute the operations in a DBN, marginalization and point-wise multiplication, for an entire function analytically. I derive compression algorithms to keep LFF compact and three the inductive LFF algorithms density estimation, regression and value estimation. As inductive value estimation suffers the curse of insufficient samples, I derive a deductive variant of LSPI (FAPI, Böhmer and Obermayer, 2013). Like LSPI, FAPI requires predefined basis functions and can thus not estimate values autonomously in large state-action spaces. I develop therefore a second algorithm to estimate values deductively for a DBN (represented by LFF, e.g., learned by LFF regression) directly in the function space of LFF. As most environments can not be perfectly modeled by DBN, I discuss an importance sampling technique to combine inductive and deductive value estimation. Deduction can be furthermore improved by mixture-of-expert DBN, where a set of conditions determines for each state which expert describes the dynamics best. The conditions can be constructed as LFF from grounded relational rules. This allows to generate a transition model for each configuration of the environment. Ultimately, the framework derived in this thesis could generalize inductively learned models to other environments with similar objects.
Diese Doktorarbeit untersucht die Rolle der Zustandsrepräsentation beim generalisieren der Valuefunktion im autonomen reinforcement learning (RL). Ich nutze mathematische Techniken der Funktionsanalysis um induktive und deduktive Ansätze für RL in kontinuierlichen Zustands- und Aktionsräumen zu analysieren. Meine Analyse offenbart den zentralen Einfluss der Repräsentationsmetrik auf induktive Generalisierung und die Notwendigkeit von strukturellen Annahmen um deduktiv values zu komplett neuen Situationen generalisieren zu können. Die Arbeit leistet Beiträge zu zwei verwandten Feldern: induktives Repräsentationslernen und deduktive Schätzung der aluefunktion in großen Zustands- und Aktionsräumen. Ich betone dabei die Autonomie des Agenten, indem ich die zu erlernenden Aufgaben nicht einschränke und kaum Vorwissen voraussetze. Im Detail sind meine Beiträge: Isometrische Zustands- und Beobachtungsräume unterscheiden sich nur in ihrer Metrik (Böhmer et al., 2015), und ich zeige dass values optimal durch eine Diffusionsmetrik generalisiert werden. Ich beweise dass, wenn values von einem linearen Algorithmus wie least squares policy iteration (LSPI) geschätzt werden, slow feature analysis (SFA) eine optimale Repräsentation für alle Aufgaben in der gleichen Umgebung approximiert (Böhmer et al., 2013). Ich demonstriere dies indem ich einen neuen regularized sparse kernel SFA Algorithmus herleite (RSK-SFA Böhmer et al., 2012) und diesen mit anderen erlernten Repräsentationen vergleiche, zum Beispiel anhand einer LSPI Navigationsaufgabe mit einem realen Roboter und in umfangreichen Simulationen. Zusätzlich erweitere ich SFA zu γ-SFA, welches eine optimale Repräsentation für eine vorher definierbare Teilmenge von “zu erwartenden” Aufgaben erzeugt. Autonomes induktives Lernen leidet unter dem curse of insufficient samples, da Umgebungen, welche durch viele Variablen beschrieben werden, oft exponentiell viele Zustände haben. Induktive Generalisierung ist aber darauf angewiesen dass jeder Zustand “in der Nähe” von Trainingsbeispielen liegt. Die vielen Zustände machen daher induktives Repräsentationslernen und sowohl induktive als auch deduktive Schätzung der Valuefunktion praktisch unmöglich. Der Ansatz dieser Arbeit ist diesem Problem durch strukturelle Annahmen an die Zustandsdynamik zu begegnen. Ich untersuche Zustandsräume mit bedingt unabhängigen Zustandsänderungen, welche Bayesian dynamic networks (DBN) genannt werden. Modelle dieser Dynamik können, im Unterschied zu Valuefunktion, induktiv gelernt werden ohne unter dem oben genannten Fluch zu leiden. Hierfür definiere ich die Funktionsklasse der linear factored functions (LFF, Böhmer and Obermayer, 2015), welche die notwendigen Operationen zur Berechnung eines DBN, Marginalisierung und punktweise Multiplikation, für die gesamte Funktion analytisch durchführen können. Ich leite Kompressionsalgorithmen, welche LFF kompakt halten, und drei induktive Lernalgorithmen her: Dichteschätzung, Regression und Valueschätzung. Da induktive Schätzung der Valuefunktion unter dem curse of insufficient samples leidet, leite ich eine deduktive Variante von LSPI her (FAPI, Böhmer and Obermayer, 2013). FAPI benötigt allerdings, genau wie LSPI, im voraus definierte Basisfunktionen, und kann daher die Valuefunktion in großen Zustands- und Aktionsräumen nicht ohne Vorwissen schätzen. Ich leite deshalb einen zweiten Algorithmus her, welcher die Valuefunktion direkt im Raum der LFF mittels eines DBN deduktiv schätzt. Dieses DBN kann z.B. durch LFF-Regression gelernt werden. Da sich jedoch viele Dynamiken nicht perfekt durch DBN modellieren lassen, führe ich ebenfalls eine importance sampling Technik ein, mit der man induktive und deduktive Schätzungsmethoden vereinen kann. Die deduktive Schätzung kann zusätzlich verbessert werden, indem man ein mixture-of-expert DBN nutzt. Hierbei bestimmt eine Reihe von Konditionen für jeden Zustand welcher Experte die Dynamik am besten beschreibt. Die Konditionen sind ihrerseits LFF, welche man aus grounded relational rules berechnen kann. Dies erlaubt für jede Konfiguration der Umgebung ein eigenes Modell der Dynamik zu erzeugen. Die in dieser Doktorarbeit vorgestellte Methodik sollte es daher erlauben induktiv erlernte Modelle der Dynamik auf unbekannte Umgebungen mit ähnlichen Objekten zu übertragen, um hiermit deduktiv die Valuefunktion zu schätzen.
URI: http://depositonce.tu-berlin.de/handle/11303/6150
http://dx.doi.org/10.14279/depositonce-5715
Exam Date: 16-Dec-2016
Issue Date: 2017
Date Available: 9-Feb-2017
DDC Class: DDC::000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::006 Spezielle Computerverfahren
Subject(s): reinforcement learning
representation learning
slow feature analysis
factored MDP
model based RL
belohnungsbasiertes Lernen
Repräsentationslernen
faktorisierende MDP
modellbasiertes RL
Sponsor/Funder: DFG, SPP 1527, value representation in large factored state spaces
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
boehmer_wendelin.pdf8,02 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.