Strukturiertes und kontinuierliches Verstärkungslernen

Im sogenannten Verstärkungslernen (engl. Reinforcement learning) versucht ein Agent, optimales Verhalten zu erlernen, indem er Rückmeldungen (üblicherweise quantifizierbare Auszahlungen) der Umgebung auf seine Aktionen auswertet. Eine positive Auszahlung kann auch verzögert erfolgen, sodass der Lerner zum Beispiel kurzfristig negative Auszahlungen in Kauf nehmen muss, um nach erfolgreicher Absolvierung einer Aufgabe, die die die koordinierte Abfolge von bestimmten Aktionen erfordert, mit einer hohen positiven Auszahlung belohnt zu werden. Obwohl für Beispielanwendungen zahlreiche Lernalgorithmen entwickelt wurden, blieb diesen Methoden bisher ein wirklicher Durchbruch verwehrt. Einer der Gründe dafür ist, dass Algorithmen unter dem in praktischen Anwendungen üblicherweise sehr großen Zustandsraum leiden, und sowohl Komplexität als auch der Verlust (engl. Regret), den ein Algorithmus im Vergleich zu einer optimalen Strategie erleidet, für typische Algorithmen linear oder gar polynomiell mit der Größe des Zustandsraumes wachsen. Zudem können diese Algorithmen anders als etwa Menschen Ähnlichkeiten oder andere Strukturen im zugrundeliegenden Problem weder erkennen noch ausnutzen. In einem Vorläuferprojekt gelang es in Zusammenarbeit mit Forschern am Inria Lille, allgemeine Ähnlichkeitsrelationen für Probleme des Verstärkungslernens zu definieren, und entsprechende Algorithmen zu entwickeln, für die unter Vorgabe von zugrundeliegenden Ähnlichkeitsstrukturen verbesserte theoretische Schranken hergeleitet werden konnten. Dies führte in weiterer Folge zu Algorithmen und Techniken, die auch auf Probleme mit kontinuierlichem Zustandsraum angewandt werden können. Für diese Algorithmen konnten auch die ersten allgemeinen theoretischen Schranken gezeigt werden. Das beantragte Projekt möchte nun die Forschung auf dem Gebiet des kontinuierlichen Verstärkungslernens vertiefen. Dabei sollen nicht nur die bekannten theoretischen Schranken verbessert werden, ein weiteres Augenmerk wird auf die Effizienz der zu entwickelnden Algorithmen gelegt. Darüber hinaus sollen allgemeinere Szenarien untersucht werden, in denen der Lerner keinen direkten Zugang zum zugrundeliegenden Zustandsraum hat, sondern nur über eine Menge von möglichen Modellen verfügt. Im Vorgängerprojekt wurden für dieses Szenario bereits die ersten theoretischen Resultate erzielt, allerdings unter der Voraussetzung, dass Zustandsräume endlich sind und sich unter den möglichen Modellen auch das korrekte Modell befindet. Im beantragten Projekt sollen diese Voraussetzungen abgeschwächt werden, das heißt, Resultate sollen ebenso für unendliche Zustandsräume gelten wie für den Fall, dass die Menge der möglichen Modelle nur eine gute Approximation des korrekten Modells enthält.

Im sogenannten Verstärkungslernen (engl. reinforcement learning) hat ein Lerner die Aufgabe, in einer ihm unbekannten Umgebung optimales Verhalten zu erlernen. Dies kann z.B. das Erreichen eines bestimmten Ziels oder das Ausführen einer komplexen Aufgabesein. Der Lernprozess wird dabei allein durch das Feedback der Umgebung gesteuert. D.h. der Lerner kann die Reaktion der Umgebung auf sein Verhalten beobachten und erhält etwa für das erfolgreiche Absolvieren einer Aufgabe eine Belohnung in Form einer Auszahlung. Da eine solche Auszahlung auch verzögert erfolgen kann, beispielsweise erst nach einer koordinierten Abfolge von bestimmten Aktionen, um ein Ziel zu erreichen, muss der Lerner oft kurzfristig negative Auszahlungen in Kauf nehmen, um nach erfolgreicher Absolvierung einer Aufgabe mit einer hohen positiven Auszahlung belohnt zu werden. Für diese Problemstellung gibt es zwar bereits einige Lernalgorithmen, für die gezeigt werden kann, dass sie im Prinzip jede Aufgabenstellung nach einer gewissen Zeit lösen können (sofern die Aufgabenstellung gewisse Bedingungen erfüllt), in der Praxis sind diese Algorithmen aber meist nicht einsetzbar, da die computergerechte Darstellung praktischer Problemstellungen so komplex ist, dass Lernalgorithmen selbst für einfache Aufgaben viel zu lange zur Lösung benötigen würden. Im vorliegenden Projekt wurden u.a. Lernalgorithmen für kontinuierliche Zustandsräume entwickelt, die in der Praxis höchst relevant sind, für die es bisher aber kaum theoretische Ergebnisse gab. Dabei konnte ein neuer Algorithmus entwickelt werden, für den in Aufgabenstellungen in Umgebungen, die sich brav verhalten, gezeigt werden kann, dass er schneller lernt als bisher bekannte Algorithmen. Weiters beschäftigte sich das Projekt mit der Frage, inwiefern Algorithmen einfachere Darstellungen einer Aufgabenstellung während des Lernprozesses selbst erlernen und verwenden können. Dabei hat der Algorithmus mehrere solcher Darstellungen zur Auswahl, weiß aber nicht, welche für das Erreichen seines Lernziels am besten geeignet ist. Im Rahmen des Projekts konnte gezeigt werden, dass Algorithmen auch dann erfolgreich lernen können, wenn keine der Darstellungen völlig korrekt ist, und es nur mindestens eine gute Approximation der Lernumgebung gibt. Dabei ist es für den Lernerfolg interessanterweise gar nicht nötig, dass der Lernalgorithmus diese gute Darstellung identifiziert. Tatsächlich ist dies im allgemeinen viel schwieriger und in manchen Fällen gar unmöglich.