Q-Learning ist ein Algorithmus aus dem Bereich des Reinforcement Learnings, der versucht, anhand der aktuellen Umwelt des Agenten die nächstbeste Aktion vorherzusagen. Er wird vor allem zum Erlernen von Spielen genutzt, in der eine erfolgsversprechende Strategie herausgebildet werden soll.

Was ist Reinforcement Learning?

Reinforcement Learning Modelle sollen darauf trainiert werden, eine Reihe von Entscheidungen selbstständig zu treffen. Angenommen wir wollen einen solchen Algorithmus, den sogenannten Agenten, darauf trainieren das Spiel PacMan möglichst erfolgreich zu spielen. Der Agent startet auf einer beliebigen Stelle im Spielfeld und hat eine begrenzte Anzahl an möglichen Aktionen, die er ausführen kann. In unserem Fall wären das die vier Richtungen (oben, unten, rechts oder links), die er auf dem Spielfeld gehen kann.

Die Umwelt in der sich der Algorithmus in diesem Spiel befindet ist das Spielfeld und die Bewegung der Geister, denen man nicht begegnen darf. Nach jeder Aktion, beispielsweise gehe nach oben, erhält der Agent ein direktes Feedback, den Reward. Bei PacMan sind dies entweder das Erhalten von Punkten oder die Begegnung mit einem Geist. Es kann auch vorkommen, dass nach einer Aktion kein direkter Reward erfolgt, sondern dieser erst in Zukunft stattfindet, also beispielsweise erst in ein oder zwei weiteren Zügen. Für den Agenten sind Rewards, die in der Zukunft liegen, weniger wert als unmittelbare Rewards.

Über die Zeit bildet der Agent eine sogenannte Policy aus, also eine Strategie von Aktionen, die ihm langfristig den höchsten Reward versprechen. In den ersten Runden wählt der Algorithmus komplett zufällige Aktionen aus, da er noch keinerlei Erfahrungen sammeln konnte. Mit der Zeit jedoch bildet sich eine erfolgsversprechende Strategie heraus.

Was ist Q-Learning?

Q-Learning ist ein Reinforcement Learning Algorithmus, der in jedem Schritt versucht den Reward in Abhängigkeit von möglichen Aktionen zu maximieren. Man spricht bei diesem Algorithmus davon, dass er „model-free“ und „off-policy“.

„model-free“ bedeutet, dass der Algorithmus nicht auf die Modellierung einer Wahrscheinlichkeitsverteilung zurückgreift, also versucht die Antwort der Umgebung vorherzusagen. Ein „model-based“ Ansatz in einem Spiel, wie beispielsweise PacMan, würde versuchen zu lernen, welchen Reward und welchen neuen State er erwarten kann, bevor er sich für eine Aktion entscheidet. Ein „model-free“ Algorithmus hingegen, blendet das komplett aus und lernt vielmehr nach dem „Trial and Error“ Prinzip, indem eine zufällige Aktion gewählt wird und erst danach bewertet wird, ob sie erfolgreich war oder nicht.

Die Eigenschaft „off-policy“ meint dabei, dass das Modell erstmal keiner Policy folgt. Das heißt das Modell entscheidet zu jedem Zeitpunkt, welche Aktion bei der aktuellen Umwelt die beste ist, unabhängig, ob das zur bisher verfolgten Policy passt oder nicht. Das bedeutet, dass sich keine Strategien ergeben, die mehrere Züge involvieren, sondern lediglich in Schritten gedacht wird, die nur eine einzige Aktion beinhalten.

Wie läuft der Prozess ab?

Im Verlauf des Q-Learning Algorithmus werden verschiedene Schritte durchlaufen. Im Mittelpunkt steht dabei die q-Tabelle, die dem Algorithmus bei der Auswahl der richtigen Aktionen hilft. Die Anzahl der Reihen sind dabei die möglichen Zustände des Spiels, also für PacMan beispielsweise, dass man einem Geist begegnet oder Punkte sammelt. Die Anzahl der Spalten sind die Aktionen, die vorgenommen werden können, also die Richtungen in die man die Figur bewegen kann.

Am Anfang werden die Werte der Tabelle auf 0 gestellt. Im Laufe des Trainings verändern sich diese Werte ständig. Folgende Schritte werden während des Lernens durchlaufen:

Erstellen der q-Tabelle

Die Tabelle, wie wir sie bereits gesehen haben, wird erstellt und die einzelnen Werte müssen befüllt, also initialisiert, werden. In unserem Fall schreiben wir dafür in jedes Feld eine 0. Es können jedoch auch andere Methoden genutzt werden, um die Felder zu initialisieren.

Wahl einer Aktion

Nun beginnt der Algorithmus in seinem jeweiligen Status (am Anfang also Start) eine der möglichen Aktionen auszuwählen. Dabei nutzt der Algorithmus zwei verschiedene Herangehensweisen:

1. Exploration: Am Anfang kennt das Modell noch keine Q-Werte und wählt die Aktionen zufällig aus. Dadurch erkundet es die einzelnen Statuse und erkennt neue Vorgehensweisen, die ansonsten unentdeckt geblieben wären.
2. Exploitation: Während der Exploitation-Phase wird versucht, das Wissen aus der Exploration-Phase auszunutzen. Wenn also in der q-Tabelle schon belastbare Werte vorhanden sind, wählt der Algorithmus für jeden State genau die Aktion aus, die den höchsten, zukünftigen Reward verspricht.

Wie oft sich das Modell in der Exploration oder Exploitation befinden soll, kann über den sogenannten Epsilon-Wert eingestellt werden. Er entscheidet über das Verhältnis der beiden Wahlarten von Aktionen.

Überschreiben der q-Werte

Mit jeder Aktion, die der Agent während des Q-Learnings wählt, verändern sich auch die Werte in der q-Tabelle. Dies passiert so lange, bis ein vorgegebener Endpunkt erreicht wird und somit das Spiel zu einem Ende kommt. In PacMan ist dieser Punkt entweder erreicht, wenn man einem Geist begegnet oder wenn man alle Punkte im Spielfeld aufgesammelt hat. Das nächste Spiel kann dann schon mit den bereits erlernten q-Werten gestartet werden.

Nachdem der Agent eine Aktion in seinem Ausgangsstatus gewählt hat, erhält er einen Reward. Der q-Wert für das Feld des entsprechenden Status und der Aktion berechnet man dann mithilfe der folgenden Formel:

\(\) \[Q(S_{t}, A_{t}) = (1 – \alpha) \cdot Q(S_{t}, A_{t}) + \alpha \cdot (R_{t} + \lambda \cdot max_{\alpha} Q(S_{t + 1}, \alpha))\]

Dies sind die Bedeutungen der einzelnen Bestandteile:

• S steht für den State. Der Index t ist dabei der aktuelle State und der Index t+1 der zukünftige Status.
• A ist die Aktion, die der Algorithmus wählt.
• R ist der Reward, also die Auswirkung der getätigten Aktion. Dieser kann entweder positiv, wie beispielsweise ein zusätzlicher Punkt, oder negativ, wie beispielsweise die Begegnung mit einem Geist, sein.
• α ist die Lernrate, wie wir sie bereits aus anderen Modellen im Bereich Machine Learning kennen. Sie entscheidet wie stark der jetzt errechnete Wert, den bereits vorhandenen Wert der Tabelle überschreibt.
• λ ist der Discount Factor, also ein Faktor, der zukünftige Ereignisse weniger stark wertet wie gegenwärtige. Dieser Faktor führt dazu, dass der Algorithmus kurzfristige Rewards höher gewichtet, als zukünftige.

Diese Schleife wird so oft durchgeführt, wie im Code definiert ist oder bei Erreichnung eines Kriteriums auch frühzeitig beendet. Die dadurch entstehende q-Tabelle ist dann das Ergebnis des Q-Learnings Algorithmus und kann dann befragt werden.

Woher kommt der Name?

Das Q in Q-Learning steht für Qualität. Diese misst, wie wertvoll die nächste Aktion ist, um im darauffolgenden Schritt oder in der Zukunft einen Reward zu erhalten. Die q-Werte stammen aus der sogenannten q-Tabelle und werden anhand einer gegebenen Formel errechnet. Der q-Wert entscheidet darüber, ob eine Aktion als nächstes ausgeführt wird.

Was ist der Unterschied zwischen Q-Learning und G-Learning?

Q-Learning und G-Learning sind zwei unterschiedliche Algorithmen des Reinforcement Learning, die zur Lösung von sequentiellen Entscheidungsproblemen eingesetzt werden. Obwohl sie gewisse Ähnlichkeiten aufweisen, gibt es bemerkenswerte Unterschiede in ihren Methoden und Anwendungsbereichen.

Q-Learning konzentriert sich in erster Linie auf die Schätzung des Wertes von Zustands-Aktions-Paaren, auch bekannt als Q-Werte, um eine optimale Strategie zu bestimmen. Dies wird durch das Lernen einer Aktionswertfunktion, Q(s, a), erreicht, die Zustände und Aktionen auf ihre erwarteten kumulativen Belohnungen abbildet. In einem iterativen Prozess werden die Q-Werte auf der Grundlage beobachteter Belohnungen und nachfolgender Zustände aktualisiert, wobei die Methode der zeitlichen Differenz (TD) verwendet wird.

Das Q-Learning berücksichtigt sowohl den aktuellen Zustand als auch die entsprechende Aktion, um die Q-Werte zu schätzen und ermöglicht es dem Agenten, Entscheidungen zu treffen, indem er Aktionen mit den höchsten Q-Werten in jedem Zustand auswählt. Dieser Algorithmus wird üblicherweise in Szenarien mit diskreten Aktionsräumen eingesetzt, wie z. B. bei Spielen oder in der Robotik.

Im Gegensatz dazu konzentriert sich G-Learning darauf, den Wert von Zuständen direkt zu schätzen, ohne explizite Berücksichtigung von Aktionen. Es zielt darauf ab, eine Zustandswertfunktion, G(s), zu lernen, die die erwartete kumulative Belohnung ausgehend von einem bestimmten Zustand darstellt. Ähnlich wie beim Q-Learning wird beim G-Learning die TD-Methode für iterative Aktualisierungen verwendet. Anstatt jedoch Zustand-Aktions-Paare zu aktualisieren, aktualisiert G-Learning direkt die Werte der Zustände. Es versucht, den Wert eines bestimmten Zustands zu verstehen und eignet sich daher für Anwendungen wie Finanzanalysen, medizinische Entscheidungen oder Ressourcenoptimierung.

Die Wahl zwischen Q-Learning und G-Learning hängt von der spezifischen Problemdomäne und den Lernzielen ab. Wenn die Aufgabe eine explizite Handlungsauswahl und die Bestimmung einer optimalen Strategie beinhaltet, wird in der Regel Q-Learning bevorzugt. Liegt der Schwerpunkt dagegen auf der Beurteilung des Wertes verschiedener Zustände und dem Verständnis ihres Wertes, ist G-Learning besser geeignet.

Zusammenfassend lässt sich sagen, dass Q-Learning und G-Learning zwar beides Algorithmen des Verstärkungslernens sind, sich aber in ihren Schätzungszielen (Q-Werte vs. G-Werte) und der betrachteten Granularität (Zustand-Aktionspaare vs. Zustände) unterscheiden. Das Verständnis ihrer Unterschiede und die Auswahl des geeigneten Algorithmus hängt von der jeweiligen Problemstellung und den gewünschten Lernergebnissen ab.

Das solltest Du mitnehmen

• Q-Learning ist ein leistungsfähiger Verstärkungslernalgorithmus, der zur Lösung sequentieller Entscheidungsprobleme eingesetzt wird.
• Er lernt eine Aktionswertfunktion (Q-Werte), um die erwarteten kumulativen Belohnungen von Zustands-Aktionspaaren zu schätzen.
• Q-Learning nutzt die temporale Differenzmethode (TD), um die Q-Werte auf der Grundlage der beobachteten Belohnungen und der nachfolgenden Zustände iterativ zu aktualisieren.
• Der Algorithmus ermöglicht es den Agenten, optimale Entscheidungen zu treffen, indem sie in jedem Zustand die Aktionen mit den höchsten Q-Werten auswählen.
• Q-Learning eignet sich gut für Anwendungen mit diskreten Aktionsräumen, wie z. B. Spiele oder Robotik.
• Es wurde bereits erfolgreich in verschiedenen Bereichen eingesetzt, darunter autonomes Fahren, künstliche Intelligenz im Spiel und Robotik.
• Q-learning bietet einen Rahmen für das Lernen und Optimieren von Strategien in komplexen Umgebungen.
• Durch ein Gleichgewicht zwischen Erkundung und Ausbeutung ermöglicht Q-Learning den Agenten, ihre Entscheidungsfindung im Laufe der Zeit zu verbessern.
• Das Verständnis des Q-Learnings und der ihm zugrundeliegenden Prinzipien ist entscheidend für die Beherrschung von Reinforcement-Learning-Techniken.
• Weitere Forschungen und Fortschritte im Bereich des Q-Learnings werden seine Anwendungsmöglichkeiten erweitern und seine Leistung verbessern.

Andere Beiträge zum Thema Q-Learning

Dieser Beitrag der Publikation Towards Data Science erklärt den Q-Learning Algorithmus ausführlich und implementiert ihn in Python.