Struktur in Problemen des Verstärkungslernens

Markov Entscheidungsprozesse (engl. Markov decision processes, MDPs) bieten eine allgemeine Möglichkeit zur Modellierung von stochastischen Problemstellungen und kamen seit ihrer Einführung in den 1950ern durch Richard Bellman in zahlreichen Anwendungen zum Einsatz. In den 1980ern entdeckte die Künstliche Intelligenz Forschung in MDPs ein Werkzeug zur Darstellung von Lernproblemen mit "verzögertem Feedback". Doch obwohl eine Vielzahl an Algorithmen für dieses sogenannte Verstärkungslernen (engl. reinforcement learning) entwickelt wurde, blieb diesen Methoden ein wirklicher Durchbruch bisher verwehrt, trotz einiger erfolgreicher Anwendungen wie etwa Gerald Tesauros Backgammon Algorithmus. Grund dafür ist vor allem, dass in praktischen Anwendungen der Zustandsraum der entsprechenden MDP-Repräsentation meist sehr groß ist, 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. Die meisten dieser Algorithmen sind allerdings - anders als etwa menschliches Lernen - nicht darauf ausgerichtet, Ähnlichkeits- und andere Strukturen im zugrundeliegenden Problem zu erkennen und auszunutzen. Dieses Projekt beschäftigt sich mit solchen Strukturen in MDPs und der Frage, wie diese durch Lernalgorithmen verwertet werden können. Die Entwicklung entsprechender Methoden würde den Einsatz von Verstärkungslernalgorithmen auch in Bereichen ermöglichen, wo bisher nur Heuristiken verwendet werden bzw. man auf Expertenwissen angewiesen ist. Entsprechende Algorithmen würden also nicht auf typische Bereiche wie etwa Lernen in Spielen beschränkt sein. Vielmehr kämen neue Bereiche wie etwa Robotik oder Logistik als Anwendungsgebiete in Frage. Das beantragte Projekt möchte sich auf folgende zwei Fragestellungen konzentrieren: Erstens sollen (Ähnlichkeits-)Strukturen auf MDPs untersucht werden, die es ermöglichen, den MDP zu vereinfachen, und dadurch in einem weiteren Schritt durch geeignete adaptive Algorithmen effizient zu erlernen. In Design und Analyse dieser Algorithmen sollen Konfidenzintervalle eine Schlüsselrolle spielen. Zweitens sollen diese Techniken auf MDPs mit kontinuierlichem Zustandsraum angewandt werden, ein Bereich, der speziell für potenzielle Anwendungen von großer Bedeutung ist. Das Projekt soll am INRIA Lille durchgeführt werden, das mit der SequeL-Gruppe ein interdisziplinäres Zentrum für Forschung auf dem Gebiet des Verstärkungslernens beherbergt. Die Zusammenarbeit soll aber nicht nur auf die SequeL-Gruppe beschränkt bleiben. Weitere Gruppen am INRIA Lille, die auf relevanten angrenzenden Forschungsgebieten wie Kontrolltheorie, Optimierung und Statistik arbeiten, können zum Erfolg des Projektes beitragen.