Representation and generalization in autonomous reinforcement learning

dc.contributor.advisorObermayer, Klaus
dc.contributor.authorBöhmer, Wendelin
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeObermayer, Klaus
dc.contributor.refereeToussaint, Marc
dc.contributor.refereeOpper, Manfred
dc.date.accepted2016-12-16
dc.date.accessioned2017-02-09T10:31:18Z
dc.date.available2017-02-09T10:31:18Z
dc.date.issued2017
dc.description.abstractThis 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.en
dc.description.abstractDiese 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.de
dc.description.sponsorshipDFG, SPP 1527, value representation in large factored state spacesen
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/6150
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-5715
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc006 Spezielle Computerverfahrende
dc.subject.otherreinforcement learningen
dc.subject.otherrepresentation learningen
dc.subject.otherslow feature analysisen
dc.subject.otherfactored MDPen
dc.subject.othermodel based RLen
dc.subject.otherbelohnungsbasiertes Lernende
dc.subject.otherRepräsentationslernende
dc.subject.otherfaktorisierende MDPde
dc.subject.othermodellbasiertes RLde
dc.titleRepresentation and generalization in autonomous reinforcement learningen
dc.title.translatedRepräsentation und Generalisierung in autonomen belohnungsbasiertem Lernende
dc.typeDoctoral Thesisen
dc.type.versionacceptedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatikde
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
boehmer_wendelin.pdf
Size:
7.84 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
5.75 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections