Reinforcement Learning

Einer der drei großen Haupttypen für maschinelles Lernen ist Reinforcement Learning. Hier habe viel dazu geschrieben: https://www.herr-rau.de/wordpress/2023/03/ki-reinforcement-learning-1.htm (Teil 1 von 4).

Zwei einfache Beispiele und eine Erklärung

• Tic-Tac-Toe: Es gibt jeweils mehrere Zugmöglichkeiten (am Anfang mehr, am Ende weniger), es gibt eine Belohnung fürs Gewinnen und eine Strafe fürs Verlieren. Damit kann das System lernen, Tic-Tac-Toe erfolgreich zu spielen.
• Autofahren: Das Auto hat mindestens drei Zugmöglichkeiten (links drehen, rechts drehen, geradeaus fahren), es gibt eine Belohnung fürs Vorankommen und eine Strafe für das Verlassen der Fahrbahn. Damit kann das System lernen, Auto zu fahren.

Der Kern des Algorithmus ist dabei folgender: In jedem Systemzustand (also aktuelle Belegung des Spielfelds bei Tic-Tac-Toe, oder Abstand zur Straße nach vorn/rechts/links beim einfachen Autobeispiel) gibt es mehrere Möglichkeiten. Diese Möglichkeiten erhalten eine Bewertung. Wenn das System austrainiert ist, wählt es in jedem Zustand den Zug mit der höchsten Bewertung für diesen Zustand.

Die Bewertung entsteht nach und nach: Wenn ein Zug in einem Zustand zu einer Belohnung führt, wird dieser Zug höher bewertet; führt er zu einer Strafe, wird er niedriger bewertet. Führt ein Zug zwar nicht zu einer Strafe, aber zu einem Zustand mit lauter schlecht bewerteten Zügen (also quasi eine Sackgasse, wo man schon verloren hat, aber es noch nicht weiß), wird er gleichfalls reduziert.

Roberta auf Apfelsuche

Im folgenden Beispiel gibt es für die Figur (Roberta) links oben eine Belohnung beim Erreichen des Apfel rechts unten oder rechts oben, worauf Roberta dann wieder von vorn startet. Der Zustand Robertas ergibt sich ganz einfach aus den x/y-Koordinaten(mit 0, 0 links oben); in jedem Zustand gibt es vier Möglichkeiten (N, O, S, W) – aber den Weg zu einem Ziel kennt Roberta am Anfang nicht, weshalb das auch erst einmal langweilig aussieht:

Nach einer Zeit des Umherirrens stößt Roberta zufällig auf einen Apfel, und wenn sich das ein paar Mal wiederholt hat, kennt Roberta auch den Weg dorthin. Aber wie geschieht das?

Roberta auf Apfelsuche, visualisiert

Im folgenden Video wird für die gleiche Situation angezeigt, welchen Wert die Entscheidung für N, O, S, W im jeweiligen Zustand hat. War Roberta noch nicht in diesem Zustand, gibt es auch keine Informationen darüber. Und am Anfang ist in jedem Zustand jede Entscheidung gleich bewertet, nämlich mit 0, woran sich erst nach einer Weile etwas ändert:

Nach einer Weile stößt Roberta auf den Apfel rechts oben, und zwar von links kommenden. In diesem Zustand „links vom Apfel“ erhält der Zug „O“ eine Belohnung von 256. Später ist Roberta einmal im Zustand „zwei Felder links“ vom Apfel und geht zufällig nach Osten und befindet sich in einem Zustand, dessen Maximalbewertung 256 ist. Deshalb wird im Zustand „zwei Felder links“ vom Apfel der Zug „O“ auch bewertet, und zwar mit 128. (Warum nur halb so viel? Das liegt am Diskontierungsfaktor und der ist im Beispiel auf 0,5 eingestellt; es könnte auch ein anderer Wert kleiner 1 sein.)

Den Apfel rechts unten hat Roberta bei diesem Durchgang übrigens gar nicht entdeckt! Wenn man möchte, dass Roberta auch einmal den einmal gelernten, aber vielleicht gar nicht optimalen Weg verlässt, muss man eine Explorationsrate hinzufügen, also eine gewisse Wahrscheinlichkeit, dass Roberta beim Training nicht den besten Zug macht, sondern einen zufälligen anderen.

Ein Vergleich mit Tic-Tac-Toe

Warum das Beispiel so anschaulich ist

1. Weil der Zustandsraum, in dem sich Roberta bewegt, schön zweidimensional darstellbar ist. Es gibt im Beispiel maximal 9*7 Zustände, nicht alle davon erreichbar, und die lassen sich zweidimensional schön nebeneinander anordnen, so dass ein Zustandsübergang immer zu einem Nachbarfeld geht.
2. Weil es pro Zustand nur 4 Optionen gibt, die sich schön kompakt darstellen lassen.

Wie das bei Tic-Tac-Toe aussähe

1. Es gibt mehr Zustände, aber das ist nicht der Punkt: sie lassen sich vor allem nicht so zweidimensional anzeichnen, dass die Übergänge sinnvoll visualisiert werden. Ich hab’s versucht.
2. Pro Zustand gibt es am Anfang 9 Zugmöglichkeiten, mehr als gut anzeichenbar sind, auch wenn die sinnvollen Züge immer weniger werden.
3. Aber eigentlich wäre das das gleiche.

Was beim Beispiel fehlt

1. Sackgassen. Beim Apfelsuchen gibt es von jedem Zustand (=Ort) einen Weg in einen Gewinn-Zustand, und es gibt von den Wänden abgesehen keinen Verloren-Zustand. Bei Tic-Tac-Toe ist das anders, da gibt es Zustände, in die man gar nicht erst kommen sollte, weil die früher oder später zum Verlieren führen. Das würde so aussehen:

Roberta auf Apfelsuche, mit Netz statt Tabelle

In der Praxis gibt es meist so viele Zustände, dass man mit einer Tabelle für Zugbewertungen je Zustand (Q-Table) nicht weit kommt. Außerdem möchte man ja, dass ähnliche Zustände ähnlich bewertet werden, selbst wenn sie bislang unbekannt waren. Deshalb nimmt man statt der Tabelle ein neuronales Netz. Der Input ist der Zustand (hier also: ein x-Wert, ein y-Wert), die vier Outputs geben die Werte für die vier Optionen N, O, S, W an:

Selbst für Zustände, die noch nicht erreicht wurden, die sogar nie erreicht werden können, spuckt das Netz Wahrscheinlichkeiten aus, weil es ja nicht anders kann, als Ergebnisse zu liefern. Dass die am Anfang nicht sinnvoll sind, ist klar, erst mit dem Training wird das Netz so justiert, dass es sinnvolle Wahrscheinlichkeiten ausgibt.