Den Spatz in der Hand oder doch die Taube auf dem Dach

Oder: Reinforcement Learning


Intelligenz ist schwierig zu messen. Wenn wir eine Person beobachten, können wir aber oft deren Intelligenz durch ihr Verhalten abschätzen. Jemand, der in einer schwierigen Situation das "Richtige" tut, scheint erst einmal intelligent. Nur: Was ist das Richtige? Stellt man Kinder im Vorschulalter vor die Wahl entweder sofort eine kleine Belohnung zu bekommen oder später eine große, dann wählen sie in den meisten Fällen die sofortige Belohnung. Ein kleiner Mensch muss erst eben erfahren, dass auch das unangenehme Warten besser sein kann – je nachdem wie lange man wartet und welche Belohnung am Ende winkt.

Auch künstliche Intelligenzen sollten Zusammenhänge über größere Zeitintervalle verstehen können.

Denn in der Welt kann auch eine Roboter-Handlung weitreichende Folgen haben und erst nach einiger Zeit wirklich feststehen, ob eine vergangene Handlung "richtig" oder "falsch" war. Das Feld des Reinforcement Learning ist in der KI für eben diese sequenziellen Probleme zuständig – also für Aufgaben mit zeitlicher Dimension, bei denen die Reihenfolge von Ereignissen eine Rolle spielt.

Im Reinforcement Learning sprechen wir daher oft von einem Agenten, der sich in einer zeitlichen Welt bewegt. Das kann eine KI im Autorennspiel sein, aber – auch etwas abstrakter – eine Komponente, die die Motordrehzahl eines Modellhelikopters steuert, um zum Beispiel Loopings auszuführen. Die Zeit kann natürlich auch Zug-weise ablaufen, wie bei Backgammon oder Go.

Die Sicht des Agenten auf seine Umwelt ist in sogenannte Zustände gekapselt – eine mehr oder weniger grobe Repräsentation der für den Agenten relevanten Aspekte der Welt. Stellen wir uns einen Roboter in einem Labyrinth vor. Der Zustand, in dem er sich zu jedem Zeitschritt befindet, könnte seiner Position in der Welt entsprechen. Der Agent kann nun durch Aktionen seinen derzeitigen Zustand verlassen und in einen neuen übergehen, also im vorigen Beispiel durch einen Schritt nach vorn an einen anderen Ort in der Welt wechseln. In jedem Zustand gibt es oft mehrere mögliche Aktionen, so dass der Agent eben auch ein Entscheidungsproblem zu lösen hat.

Es ist – gerade bei komplexen Problemstellungen – oftmals nicht trivial, eine hinreichend genaue Modellierung der Welt zu finden. Zudem wird eine weitere Eigenschaft bei der Formulierung des Entscheidungsproblems gefordert: Die nächsten Zustände sollen nur vom aktuellen Zustand und der aktuellen Aktion abhängen, nicht aber zum Beispiel vom letzten oder vorletzten Zustand (Markov-Eigenschaft). Es ist also für den Agenten im Labyrinth irrelevant, welchen Weg er genommen hat, um auf seine aktuelle Position zu gelangen. Die Entscheidung, welche Aktion ihn zum Ausgang bringt, bleibt dieselbe.

Im eigentlichen Lernprozess wird dem Agenten nicht vorgegeben, welche Aktionen richtig oder falsch sind. Er kann nur durch die gewählten Aktionen Erfahrungen sammeln – gute wie schlechte. Dieser Reward ist eine quantitative Bewertung der letzten Aktion. Der Agent im Labyrinth würde also zum Beispiel dann einen großen Reward bekommen, wenn er mit einer bestimmten Aktion aus dem Labyrinth entkommt. Oftmals gibt man für Aktionen, die nicht direkt zum Ziel führen, kleine Bestrafungen, um dem Agenten einen Anreiz für möglichst kurze Lösungen zu geben (d. h. auf dem Weg zum Ziel möglichst wenige Schritte zu machen und damit möglichst wenige Bestrafungen einzusammeln). Die zentrale Aufgabe eines Agenten ist nun, in einem gegebenen Zustand die optimale Aktion auszuwählen, also die Aktion, die die Summe aller zukünftigen Belohnungen (den Gesamtreward) maximiert. Das Problem ist nur: Ohne Erfahrung wissen wir natürlich nicht, welche der möglichen Aktionen die beste ist.

In der Historie des Reinforcement Learning gibt es verschiedene, sich oft auch ergänzende Ansätze, wie genau eine gemachte Erfahrung Einfluss auf zukünftiges Verhalten nehmen soll. Eine der in der jüngsten Vergangenheit populären Spielweisen des Reinforcement Learning ist intuitiv gut zu erfassen: das Q-Learning. Im Fokus steht hier die sogenannte Q-Funktion, oder "utility function", die für einen gegebenen Zustand und eine gewählte Aktion angibt, wie hoch der Erwartungswert der Summe aller zukünftigen Belohnungen (der erwartete Gesamtreward) ist. Wenn der Agent sich also im Zustand s befindet und Aktion a1 einen Q-Wert von 10 verspricht, Aktion a2 jedoch nur 5 ergibt, dann würde sich der Agent logischerweise für die erste Aktion entscheiden.

In einfachen Problemen kann man diese Q-Funktion mit einer Tabelle darstellen: Jede Zeile korrespondiert zu einem Zustand und die Spalten stellen jeweils die möglichen Aktionen dar. In den Tabellenfeldern steht dann der Erwartungswert des zukünftigen Gesamtrewards. Oftmals könnte die Zukunft unendlich lang sein und damit die Berechnung der mittleren zukünftigen Belohnung schwierig. Durch eine abfallende Gewichtung der aufsummierten Belohnungsterme wird oft ein Zukunftshorizont definiert, über welchen hinaus der Agent nicht schauen kann (discounting). Wenn sich der Ausgang des Labyrinths links vom Agenten befindet, würde man also in der Tabelle die Zeile heraussuchen, die zu unserer derzeitigen Position korrespondiert und dann hoffentlich in der Spalte "nach links gehen" den größten Wert finden.

Aber wie füllt man diese Tabelle im Lernvorgang? Ganz am Anfang initialisieren wir die Tabelle mit zufälligen Werten oder Nullen. Der Agent sammelt jetzt Erfahrungen, indem er sich in jedem Zustand zufällig für eine Aktion entscheidet. Die Hoffnung ist, dass er mit dieser Strategie in möglichst allen Zuständen alle Aktionen oft genug ausprobiert.
Lernen ist nun ein einfacher Update-Vorgang: wenn der Agent aus dem Zustand s vorher eine zufällige Aktion az gemacht hat und in einem neuen Zustand s nachher eine Belohnung r bekommen hat, dann kann er ganz einfach die Zahl in der Q-Tabelle Q(svorher, az) anpassen. Der neue Wert ergibt sich aus dem alten und einer Änderung, die letztlich die Abweichung von der Erwartung beschreibt. Schauen wir es uns genauer an (die Notation habe ich etwas vereinfacht, Qalt ist Q(svorher, az) und Qneu ist Q(snachher, azz), also die erwartete zukünftige Belohnung nach der optimalen Aktion im nächsten Schritt):

Qalt = Qalt + (r + Qneu - Qalt)

Die Summe aus dem unmittelbaren Reward r und der erwarteten Belohnung im Folgezustand ist im besten Fall genau der Wert der Q-Tabelle, den wir gerade betrachten. Denn dieser lässt sich ja in eine Summe von Belohnungen aufsplitten, die der Agent auf seinem zukünftigen Weg einsammelt. Der Reward r in der Gleichung wäre also die Belohnung des ersten Schrittes und Qneu vereinigt alle restlichen Belohnungen der Zukunft. Wenn diese Summe exakt den schon in der Tabelle enthaltenen Wert Qalt ergibt, so ist unsere Q-Tabelle korrekt und es gibt keine Änderung. Am Anfang des Lernvorgangs wird es jedoch eine Diskrepanz geben und damit wird eine Änderung des Eintrags in Q berechnet.

Dieser Schritt funktioniert natürlich umso besser, je genauer die Tabelle bereits ist. Selbst wenn die Tabelle am Anfang nur Nullen enthält, wird sie nach und nach immer genauer und am Ende weiß der Agent ganz genau, was zu tun ist. Das geht natürlich nur in sehr einfachen Fällen, insbesondere für endliche Zustands- und Aktionsräume. Kompliziertere Probleme sprengen den einfachen Tabellenansatz. Wir müssen die Tabelle dann mit einer Technik ersetzen, die auch mit sehr vielen – oder sogar unendlich vielen – Zuständen arbeiten kann.

Oft benutzt man dafür dann ein neuronales Netzwerk. Es lernt, wieviel Belohnung die einzelnen Aktionen in den verschiedenen Zuständen für zukünftige Zeiten versprechen – also genau das, was vorher durch die Tabelle gelöst wurde. Das Netzwerk ist jetzt aber auch in der Lage, ähnliche Zustände zusammenzufassen. So ist es eventuell egal, ob im Autorennen das nächste Auto einen Meter oder 1,05 Meter nach links entfernt ist – in beiden Fällen muss Abstand gehalten werden. Und jetzt ist es auch nicht mehr wichtig, dass der Agent während des Lernens jede Situation oft genug gesehen hat. Wichtig ist, dass er zumindest einige ähnliche Situationen schon kennen gelernt hat.

Am Beispiel von Backgammon hat Gerald Tesauro Anfang der 90er Jahre beeindruckend gezeigt, dass es mit einer durch ein neuronales Netz approximierten Wertfunktion möglich ist, das Spielniveau eines menschlichen Weltmeisters zu erreichen.

Knapp ein Vierteljahrhundert später, im Jahre 2016, konnte Googles Firma DeepMind Schlagzeilen mit dem Sieg über den 18-fachen GO-Weltmeister Lee Sedong machen. Auch hier war eine Funktionsapproximation durch neuronale Netze zentral – diesmal von der Policy – und der Wertfunktion zusammen (auch dazu in einem anderen Artikel mehr). In beiden Fällen war der Zustand, der an die neuronalen Netze gegeben wurde, zu einem gewissen Grad manuell von Menschen vorverarbeitet.

Dass es auch anders geht, hat ebenfalls wieder DeepMind mit einem Reinforcement-Learning-System gezeigt, das in der Lage ist, klassische Atari-Spiele wie Space Invaders oder Breakout mit übermenschlicher Leistung zu spielen. Dort erhielt der Agent als Zustand die reinen Bildinformationen, die ein Mensch auch sehen würde, und lernte daraus eine Approximation der Q-Funktion – wieder mit neuronalen Netzen. Ohne vom Menschen angepasst zu werden, konnte dieser Agent lernen, eine ganze Reihe von Spielen nur anhand des eingeblendeten Punktestands zu meistern.

Es gibt viele weitere Spielarten von Reinforcement Learning, die wir hier nicht ansprechen konnten.

Dennoch: Lernen bedeutet im Reinforcement Learning immer viel Ausprobieren.

Das kann für komplexe Probleme allerdings sehr lange dauern. Wie andere Strömungen im Machine Learning ist daher auch das Reinforcement Learning durch eine über die Jahre immer größer werdende Rechenleistung zu mittlerweile ganz erstaunlichen Leistungen fähig. Um ein System in der realen Welt lernen zu lassen, nutzt man meist jedoch ein Vortraining in einer Simulation der Welt. Der Looping-fliegende Helikopter hätte sonst nicht nur viel negativen Reward eingesammelt, sondern eben auch viel Ärger bei den Ingenieuren produziert, wenn ein Looping auf dem Boden endete. Und auch wir Menschen haben durch unsere Imagination einen eingebauten Weltsimulator. Wenn wir also vor die Wahl gestellt werden, jetzt einen Euro oder morgen einen Goldbarren zu erhalten, so müssen wir noch nie eine entsprechende Erfahrung gemacht haben, um die "richtige" Entscheidung zu treffen.

Kommentare
Einen Kommentar schreiben
Entschuldigung

Ihr Browser ist leider nicht aktuell genug.
Um diese Webseite zu benutzen, benötigen Sie einen aktuellen Browser
Wir empfehlen einen der folgenden Browser in der aktuellsten Version zu installieren.

Auf iOS Geräten sollte mindestens die Betriebssystem Version iOS 9 installiert sein.

Mozilla Firefox Google Chrome Microsoft Edge Internet Explorer