Q-Learning

Linda Metzger und Erik Wolf, Praxissemester bei sidion

Wenn es um künstliche Intelligenz geht und genauer um das maschinelle Lernen, fällt oft der Begriff des Reinforcement-Learnings. Reinforcement Learning lässt sich jedoch auf verschiedene Weisen realisieren und eine besonders populäre ist Q-Learning.

Wozu dient Q-Learning?

Q-Learning ist ein Teil des Machine-Learnings, einem Bereich, der heutzutage immer mehr an Bedeutung gewinnt. Es dient dazu, für einen Agenten in einer fest definierten Umgebung eine möglichst gute Lösung oder ein Verhalten zu finden. Dabei werden keine Beispiellösungen benötigt, stattdessen lernt der Algorithmus selbst mit der Zeit, was gute Lösungen sind.

Inspiration für Q-Learning

Wenn man einem Tier etwas beibringen will, so stößt man schnell auf Schwierigkeiten. Das Tier kann die Sprache des Menschen nicht verstehen und somit braucht es eine andere Möglichkeit, sich zu verständigen. Das Tier versteht jedoch Emotionen und erkennt, wann es etwas gut oder schlecht gemacht hat. Deshalb ist der Trick nun, das Tier mit einer Umgebung interagieren zu lassen und genau dann zu belohnen, wenn das gewünschte Verhalten auftritt. Das Tier verbindet die durchgeführte Aktion mit der Belohnung und wird sich in Zukunft eher wieder so verhalten. Durch einige Wiederholungen festigt sich das Verhalten und das Tier hat gelernt, was der Mensch ihm beibringen wollte.

Dieses Prinzip lässt sich mit einigen Anpassungen auch auf den Computer übertragen.

Wie läuft Q-Learning ab?

Q-Learning ist eine Art des Reinforcement-Learnings, das bedeutet, es basiert auf dem Belohnungssystem. Kurz gesagt, wird der Agent zu Beginn zufällige Aktionen durchführen, welche dann bewertet werden. Der Agent merkt sich nun, ob die durchgeführte Aktion gut oder schlecht war und handelt das nächste Mal entsprechend. Da er, um eine gute Entscheidung zu treffen, jede mögliche Situation durchlaufen haben muss, kann es möglicherweise sehr lange dauern, bis der Agent zuverlässig gut handeln kann.

Die sogenannte Q-Matrix dient dazu, die bestmögliche Aktion zu finden und auszuführen.  Dabei kann man sich die möglichen Situationen als Zeilen der Matrix und die ausführbaren Aktionen als Spalten der Matrix vorstellen. Die Einträge der Q-Matrix heißen Q-Werte und sind die Bewertungen der einzelnen Aktionen in einer bestimmten Situation. Wenn der Agent nun eine Aktion durchführen soll, sucht er in der Matrix nach der Aktion mit dem maximalen Q-Wert für die momentane Situation.

Ist die Aktion dann durchgeführt, wird der Q-Wert für diese entweder direkt oder am Ende des Trainingsdurchlaufes aktualisiert. Dafür wird die folgende Funktion, die Q-Funktion, verwendet:

Q(s_t, a_t) = (1 - α) * Q(s_t, a_t) + α * (r + γ * max Q(s_t+1, a))

Hierbei steht α für den Lernfaktor, also dafür, wie schnell der Algorithmus aus den Auswirkungen einer Aktion Schlüsse ziehen soll. γ steht für den Diskontierungsfaktor, welcher bestimmt, welchen Einfluss die beste der möglichen Aktionen der nächsten Runde auf den neuen Q-Wert haben soll.

Somit beeinflusst die Auswirkung einer bestimmten Aktion die Auswahl, wenn der Q-Agent sich das nächste Mal in derselben Situation wiederfindet. Lässt man dieses Verfahren lange genug laufen, wird der Q-Agent immer besser lernen, was in einer bestimmten Situation die beste Strategie für ihn ist.

Q-Learning Implementierung

Bei der Implementierung gibt es mehrere Punkte, die besonders relevant sind.

Erstens wäre da das Mapping zu nennen, also das Umwandeln der Aktionen und der Situationen in Ganzzahlen. Dies ist wichtig, um die Aktionen und Situationen in der Q-Matrix darzustellen und auch eindeutig aus dieser wieder auslesen zu können.

Außerdem wichtig ist die Einbindung des Algorithmus in die Trainingsdurchläufe. Dabei muss unter anderem entschieden werden, wann die Belohnung erfolgt und wann und wie der Algorithmus die Auswahl für eine bestimmte Aktion trifft.

Für die Belohnung gibt es mehrere Möglichkeiten. Eine Möglichkeit wäre es, dass die Q-Matrix nach jeder ausgeführten Aktion aktualisiert wird. Dadurch können Kreisläufe verhindert werden, also Situationen, in denen mehrere Aktionen zyklisch unendlich lang wiederholt werden. Kreisläufe sind zwar aufgrund der zufälligen Auswahl eher unwahrscheinlich, im späteren Verlauf des Trainings wird aber oft die Wahrscheinlichkeit für eine zufällige Auswahl der Aktionen gesenkt, weshalb sie dann theoretisch vorkommen könnten.

Alternativ kann sich das Programm auch merken, in welcher Reihenfolge welche Aktion ausgeführt wurde und schließlich am Ende eines Trainingsdurchlaufs die Belohnung gebündelt durchführen. Diese Möglichkeit wird beispielsweise gewählt, wenn mehrere Trainingsdurchläufe parallel getätigt werden sollen. Bei einer ständigen Veränderung der Q-Matrix wären parallele Trainingsdurchläufe weniger effektiv und auch die Fusion zweier Matrizen wäre schwierig und nicht immer ohne Konflikte möglich. Durch das Belohnen am Ende ist der Zugriff jedes Trainingsdurchlaufs gebündelt.

Frameworks

Zum Einsatz von Q-Learning gibt es eine Vielzahl an verschiedenen Frameworks, welche ihre Schwerpunkte auf unterschiedliche Bereiche gelegt haben.

Ein besonders umfangreiches Framework ist das Catalano-Framework. Es ist ein umfangreiches Java-Framework nicht nur für Machine-Learning, sondern beispielsweise auch für Image-Processing, Mathematik und IO. Das Catalano-Framework kann auf Github gefunden werden und muss manuell eingebunden werden.

https://github.com/accord-net/java

Ein anderes Framework ist das Java Reinforcement Framework vom Github-User chen0040. Dieses Framework hat Implementierungen für Q-Learning, SARSA und R-Learning, drei Reinforcement-Algorithmen. Es kann über Maven in ein Projekt eingebunden werden. Positiv ist hierbei noch zu vermerken, dass direkt auf der Github-Seite Beispiele und Erklärungen bereitgestellt werden. Diese muss man beim Catalano-Framework erst suchen.

https://github.com/chen0040/java-reinforcement-learning

Fazit

Bevor man Q-Learning anwendet, sollte man sich darüber Gedanken machen, wie viel Optimierungspotential im Problem steckt und auch, wie viele unterschiedliche Situationen und Wege durch diese Situationen es gibt.

Da die Q-Matrix mit jeder Situation mindestens um eine Zeile und oft auch um eine Spalte wächst, steigt auch der Rechenaufwand zum Finden einer Lösung deutlich. Der Q-Learning-Algorithmus sollte möglichst die komplette Q-Matrix bearbeitet haben, weshalb das Training dadurch immer länger dauert.

Q-Learning eignet sich vor allem für Probleme, bei denen es schwierig oder gar unmöglich ist, durch einen Algorithmus ein festes Verhalten zu definieren. Je geringer die Komplexität dieses Problems nun ist, desto besser eignet sich der Einsatz von Q-Learning, um eine gute Lösung zu finden.