TU Darmstadt / ULB / TUprints

Reinforcement Learning with Sparse and Multiple Rewards

Parisi, Simone (2020)
Reinforcement Learning with Sparse and Multiple Rewards.
Technische Universität Darmstadt
doi: 10.25534/tuprints-00011372
Ph.D. Thesis, Primary publication

Copyright Information: CC BY 4.0 International - Creative Commons, Attribution.

Download (8MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Reinforcement Learning with Sparse and Multiple Rewards
Language: English
Referees: Peters, Prof. Dr. Jan ; Boedeker, Prof. Dr. Joschka
Date: January 2020
Place of Publication: Darmstadt
Date of oral examination: 19 December 2019
DOI: 10.25534/tuprints-00011372

Over the course of the last decade, the framework of reinforcement learning has developed into a promising tool for learning a large variety of task. The idea of reinforcement learning is, at its core, very simple yet effective. The learning agent is left to explore the world by performing actions based on its observations of the state of the world, and in turn receives a feedback, called reward, assessing the quality of its behavior. However, learning soon becomes challenging and even impractical as the complexity of the environment and of the task increase. In particular, learning without any pre-defined behavior (1) in the presence of rarely emitted or sparse rewards, (2) maintaining stability even with limited data, and (3) with possibly multiple conflicting objectives are some of the most prominent issues that the agent has to face. Consider the simple problem of a robot that needs to learn a parameterized controller in order to reach a certain point based solely on the raw sensory observation, e.g., internal reading of joints position and camera images of the surrounding environment, and on the binary reward "success'' / "failure''. Without any prior knowledge of the world's dynamics, or any hint on how to behave, the robot will start acting randomly. Such exploration strategy will be (1) very unlikely to bring the robot closer to the goal, and thus to experience the "success'' feedback, and (2) likely generate useless trajectories and, subsequently, learning will be unstable. Furthermore, (3) there are many different ways the robot can reach the goal. For instance, the robot can quickly accelerate and then suddenly stop at the desired point, or it can slowly and smoothly navigate to the goal. These behaviors are clearly opposite, but the binary feedback does not provide any hint on which is more desirable. It should be clear that even simple problems such as a reaching task can turn non-trivial for reinforcement learning. One possible solution is to pre-engineer the task, e.g., hand-crafting the initial exploration behavior with imitation learning, shaping the reward based on the distance from the goal, or adding auxiliary rewards based on speed and safety. Following this solution, in recent years a lot of effort has been directed towards scaling reinforcement learning to solve complex real-world problems, such as robotic tasks with many degrees of freedom, videogames, and board games like Chess, Go, and Shogi. These advances, however, were possible largely thanks to experts prior knowledge and engineering, such as pre-initialized parameterized agent behaviors and reward shaping, and often required a prohibitive amount of data. This large amount of required prior knowledge and pre-structuring is arguably in stark contrast to the goal of developing autonomous learning.

In this thesis we will present methods to increase the autonomy of reinforcement learning algorithms, i.e., learning without expert pre-engineering, by addressing the issues discussed above. The key points of our research address (1) techniques to deal with multiple conflicting reward functions, (2) methods to enhance exploration in the presence of sparse rewards, and (3) techniques to enable more stable and safer learning. Progress in each of these aspects will lift reinforcement learning to a higher level of autonomy.

First, we will address the presence of conflicting objective from a multi-objective optimization perspective. In this scenario, the standard concept of optimality is replaced by Pareto optimality, a concept for representing compromises among the objectives. Subsequently, the goal is to find the Pareto frontier, a set of solutions representing different compromises among the objectives. Despite recent advances in multi-objective optimization, achieving an accurate representation of the Pareto frontier is still an important challenge. Common practical approaches rely on experts to manually set priority or thresholds on the objectives. These methods require prior knowledge and are not able to learn the whole Pareto frontier but just a portion of it, possibly missing interesting solutions. On the contrary, we propose a manifold-based method which learn a continuous approximation of the frontier without the need of any prior knowledge.

We will then consider learning in the presence of sparse rewards and present novel exploration strategies. Classical exploration techniques in reinforcement learning mostly revolve around the immediate reward, that is, how to choose an action to balance between exploitation and exploration for the current state. These methods, however, perform extremely poorly if only sparse rewards are provided. State-of-the-art exploration strategies, thus, rely either on local exploration along the current solution together with sensible initialization, or on handcrafted strategies based on heuristics. These approaches, however, either require prior knowledge or have poor guarantees of convergence, and often falls in local optima. On the contrary, we propose an approach that plans exploration actions far into the future based on what we call long-term visitation value. Intuitively, this value assesses the number of unvisited states that the agent can visit in the future by performing that action.

Finally, we address the problem of stabilizing learning when little data is available. Even assuming efficient exploration strategies, dense rewards, and the presence of only one objective, reinforcement learning can exhibit unstable behavior. Interestingly, the most successful algorithms, namely actor-critic methods, are also the most sensible to this issue. These methods typically separate the problem of learning the value of a given state from the problem of learning the optimal action to execute in such a state. The former is fullfilled by the so-called critic, while the latter by the so-called actor. In this scenario, the instability is due the interplay between these two components, especially when nonlinear approximators, such as neural networks, are employed. To avoid such issues, we propose to regularize the learning objective of the actor by penalizing the error of the critic. This improves stability by avoiding large steps in the actor update whenever the critic is highly inaccurate.

Altogether, the individual contributions of this thesis allow reinforcement learning to rely less on expert pre-engineering. The proposed methods can be applied to a large variety of common algorithms, and are evaluated on a wide array of tasks. Results on both standard and novel benchmarks confirm their effectiveness.

Alternative Abstract:
Alternative AbstractLanguage

Im Laufe des letzten Jahrzehnts hat sich Reinforcement Learning zu einem vielversprechenden Instrument für das Erlernen einer Vielzahl von Aufgaben entwickelt. Die Idee des Reinforcement Learning ist in ihrer Essenz sehr einfach, jedoch zugleich effektiv. Der lernende Agenten erkundet die Welt durch seine Aktionen, welche auf Beobachtungen des Umgebungszustands basieren. Dabei erhält er Belohnungen, welche die Zielgerichtetheit des Verhaltens bewerten. Jedoch wird das Lernen mit zuzunehmender Komplexität der Umgebung beziehungsweise Aufgabe schnell anspruchsvoll oder sogar unmöglich. Insbesondere zählen das Lernen ohne vorgegebenes Verhalten, (1) das Fehlen von informativen Belohnungen, (2) das Erhalten der Stabilität trotz begrenzter Daten, und (3) sich möglicherweise widersprechenden Ziele zu den bekanntesten Problemen die der Agent lösen muss.

Betrachten wir die Aufgabe dass ein Roboter einen parametrisierten Regler lernen soll welcher es ihm ermöglicht nur mithilfe von rohen Sensormessungen, wie beispielsweise Messungen der Gelenkwinkel des Roboters oder Kamerabilder der Umgebung, sowie den binären Belohnungen "Erfolg'' / "Misserfolg'' einen Punkt im Raum zu erreichen. Ohne vorheriges Wissen über die Dynamik der Umgebung oder einen Hinweis wie er sich zu verhalten hat, wird der Roboter mit zufälligen Aktionen beginnen. Eine solche Erkundungsstrategie wird den Roboter aller Wahrscheinlichkeit nach nicht näher an das Ziel bringen beziehungsweise dazu führen dass er die Rückmeldung "Erfolg'' erhält. Darüber hinaus hat die rein zufällige Exploration die Tendenz unsichere Trajektorien zu generieren, wodurch das Lernen instabil wird. Zudem gibt es viele verschiedene Wege auf denen der Roboter das Ziel erreichen kann. Zum Beispiel kann der Roboter schnell beschleunigen und dann plötzlich am Zielpunkt stoppen, oder es kann langsam und gleichmäßig zum Ziel fahren. Ein binäres Feedback allein ist nicht ausreichend um festzulegen welche diese offensichtlich gegensätzlichen Verhaltensweisen erwünscht ist.

Selbst einfache Aufgaben wie das erreichen eines Punkts im Raum können im Kontext des Reinforcement Learning zu einer Herausforderung werden. Eine mögliche Lösung ist das Problem vorzubearbeiten wie zum Beispiel vordefiniertes Explorationsverhalten mittels Imitation Learning, das Belohnungssignal proportional zu dem Abstand vom Ziel zu formulieren, oder eine zusätzliche Belohnung für Geschwindigkeit und Sicherheit einzuführen. Diesem Ansatz folgend wurde in den letzten Jahren ein großer Aufwand betrieben um Reinforcement Learning skalierbar zu machen, wodurch die Lösung von komplexen Problemen in der realen Welt ermöglicht wird. Beispiele hierfür sind Roboter-basierte Probleme mit vielen Freiheitsgraden oder Spiele wie Schach, Go und Shogi. Diese Fortschritte wurden jedoch weitgehend durch Vorwissen in Form von bereits initialisierten Verhalten oder einem bewusst hilfreich definiertem Belohnungssignal ermöglicht und benötigen zudem oft eine unerschwinglich große Menge an Daten. Das benötigte Vorwissen sowie das Vorstrukturieren der Aufgabe stellen stehen jedoch im starken Kontrast zu dem übergeordneten Ziel des selbständigen Lernens.

In dieser Arbeit werden wir Methoden präsentieren welche die Selbständigkeit von Reinforcement Learning Algorithmen verbessern indem wir die oben beschriebenen Probleme adressieren, das heißt Lernen ohne Vorbearbeitung durch Experten. Die zentralen Punkte unserer Forschung sind Methoden um (1) mit mehreren konkurrierenden Belohnungssignalen umzugehen, (2) die Erkundung der Umgehung in Abwesenheit von informativen Belohnungssignalen zu verbessern, und (3) ein stabileres und sichereres Lernen zu ermöglichen. Ein Fortschritt in jeder der drei genannten Aspekte wird die Lernmethoden des Reinforcement Learning auf eine höhere Ebene der Selbständigkeit heben.

Als erstes werden wir uns dem Problem der konkurrierenden Ziele aus Sicht eines darauf ausgelegten Optimierungsverfahrens widmen. In diesem Szenario wird das Standardkonzept der Optimalität durch die sogenannte Pareto-Optimalität, ein Konzept welches Kompromisse zwischen verschiedenen Zielen darstellt, ersetzt. Es wird danach gestrebt die sogenannte Pareto-Grenze, eine Menge an Lösungen welche Kompromisse zwischen den einzelnen Zielen repräsentiert, zu finden. Trotz kürzlicher Fortschritte im Bereich der Mehrzieloptimierung, ist die genaue Erfassung der Pareto-Grenze immer noch eine Herausforderung. In der Praxis verlassen sich die meisten Ansätze darauf dass Experten die Priorität order Schwellenwerte für die Erfüllung der individuellen Ziele manuell festlegen. Diese Ansätze benötigen fachspezifisches Wissen und sind nur in der Lage einen Ausschnitt der Pareto-Grenze zu lernen, wodurch sie aller Voraussicht nach interessante Lösungen übersehen. Im Gegensatz dazu, stellen wir einen auf Mannigfaltigkeiten basierenden Ansatz vor, der eine kontinuierliche Approximation der Pareto-Grenze lernt ohne dabei Wissen vorauszusetzen.

Im Anschluss befassen wir uns mit neuen Explorationstrategien sowie dem Lernen mit seltenen Belohnungen. Typische Explorationstrategien im Bereich des Reinforcement Learning fokussieren sich auf die instantane Belohnung im gegenwärtigen Zeitschritt, was gleichbedeutend mit der Frage nach einer Balance zwischen Erkundung aus Ausschöpfung des bisherigen Kenntnisstands ist. Diese Methoden versagen jedoch im Fall von seltenen Belohnungen beziehungsweise einem uninformativen Belohnungssignal. Zum gegenwärtigen Stand der Forschung verlassen sich Explorationstrategien daher entweder auf eine lokale Erkundung entlang des derzeitigen Verhaltensmusters mit sinnvoller Initialisierung, oder auf problemspezifische Heuristiken. Diese Vorgehensweisen setzen jedoch entweder Wissen oder haben schlechte Konvergenzgarantien und finden oft nur lokale Optima. Dem entgegen, schlagen wir eine Methode vor welche die Explorationsverhalten basierend auf dem sogenannten long-term visitation value weit in die Zukunft plant. Der long-term Visitation Value schätzt die Zahl der noch nicht entdeckten Zustände ab welche der Agent durch ausführen der gegebenen Aktion besuchen kann.

Abschließend adressieren wir das Problem der Stabilisierung des Lernvorgangs für den Fall dass nur wenige Daten zur Verfügung stehen. Selbst unter der Annahme von effizienten Explorationstrategien, eines informativen Belohnungssignals sowie eines einzigen wohldefinierten Ziels können Reinforcement Learning Algorithmen zu instabilem Verhalten führen. Interessanterweise sind die erfolgreichsten Algorithmen, besonders jene mit sogenannter Actor-Critic Architektur, auch diejenigen welche am empfindlichsten für das genannte Problem sind. Diese Architektur separiert das Lernen des Werts eines Zustands vom Lernen der optimalen Aktion gegeben eines Zustands. Ersteres geschieht durch den Critic, wohingegen der Actor für die zweite Aufgabe zuständig ist. In dieser Zusammensetzung entsteht die Instabilität durch das Wechselspiel der beiden Komponenten, insbesondere wenn dabei nichtlineare Funktionsapproximatoren wie beispielsweise künstliche neuronale Netzwerke verwendet werden. Um solche Probleme zu vermeiden, frühen wir eine Regularisierung des Lernziels für den Actor ein welches den Schätzfehler des Critic bestraft. Dies führt zu einer Stabilisierung des Lernvorgangs durch die Vermeidung von großen Veränderungen des Actor wenn der Critic sehr ungenau ist.

Insgesamt erlauben die einzelnen Beiträge dieser Arbeit den Reinforcement Learning Algorithmen sich weniger auf Expertenwissen beziehungsweise die Vorbearbeitung des Problems zu verlassen. Die vorgestellten Methoden sind auf eine große Vielfalt von Algorithmen anwendbar und wurden auf einem weiten Spektrum an Problemen evaluiert. Ihre Effektivität wird durch die dargelegten Ergebnisse auf bekannten sowie neuartigen Leistungsvergleichen bestätigt.

URN: urn:nbn:de:tuda-tuprints-113721
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science > Intelligent Autonomous Systems
Date Deposited: 21 Jan 2020 14:10
Last Modified: 09 Jul 2020 06:24
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/11372
PPN: 458045551
Actions (login required)
View Item View Item