Q-learning ist ein modellfreier Reinforcement-Learning-Algorithmus, der einen Agenten darauf trainiert, seinen möglichen Aktionen basierend auf seinem aktuellen Zustand Werte zuzuweisen, ohne ein Modell der Umgebung zu benötigen. Er kann Probleme mit stochastischen Übergängen und Belohnungen bewältigen, ohne Anpassungen zu erfordern. Für jeden endlichen Markov-Entscheidungsprozess findet Q-learning eine optimale Politik im Sinne der Maximierung des erwarteten Werts der Gesamtbelohnung über alle aufeinanderfolgenden Schritte, ausgehend vom aktuellen Zustand, bei unendlicher Explorationszeit und einer teilweise zufälligen Politik. Das „Q“ bezieht sich auf die Funktion, die der Algorithmus berechnet: die erwartete Belohnung - das heißt, die Qualität - einer Aktion, die in einem gegebenen Zustand ausgeführt wird
In einem einfachen Beispiel lernt ein Agent in einem Gitter-Labyrinth, einen Ausgang zu erreichen, der 10 Punkte wert ist. An einer Weggabelung könnte Q-learning einem Rechtsbewegen einen höheren Wert zuweisen als einem Linksbewegen, wenn Rechts schneller zum Ausgang führt, und verbessert diese Wahl, indem es beide Richtungen im Laufe der Zeit ausprobiert. Dies veranschaulicht, wie der Algorithmus unmittelbare Belohnungen gegen langfristige Ergebnisse durch iterative Aktualisierungen abwägt
Reinforcement-Learning-Kontext
Reinforcement Learning beinhaltet einen Agenten, eine Menge von Zuständen \(\mathcal{S}\),und eine Menge \(\mathcal{A}\) von Aktionen pro Zustand. Durch die Ausführung einer Aktion \(a \in \mathcal{A}\),geht der Agent von einem Zustand zu einem anderen über. Die Ausführung einer Aktion in einem spezifischen Zustand liefert dem Agenten eine Belohnung, eine numerische Punktzahl. Das Ziel des Agenten ist es, seine Gesamtbelohnung zu maximieren, indem er die maximale Belohnung, die aus zukünftigen Zuständen erreichbar ist, zur Belohnung für das Erreichen seines aktuellen Zustands hinzufügt, was effektiv die aktuelle Aktion durch die potenzielle zukünftige Belohnung beeinflusst. Diese potenzielle Belohnung ist eine gewichtete Summe erwarteter Werte der Belohnungen aller zukünftigen Schritte, ausgehend vom aktuellen Zustand
Als Beispiel betrachte man das Einsteigen in einen Zug, wobei die Belohnung durch das Negative der gesamten Einsteigezeit gemessen wird. Eine Strategie ist es, durch die Zugtür einzusteigen, sobald sie sich öffnet, was die anfängliche Wartezeit minimiert. Wenn der Zug jedoch überfüllt ist, ist das Einsteigen langsam, da aussteigende Passagiere kämpfen, um herauszukommen. Die gesamte Einsteigezeit beträgt dann 0 Sekunden Wartezeit plus 15 Sekunden Kampfzeit. Am nächsten Tag, durch Zufall (Exploration),wartet der Agent und lässt andere zuerst aussteigen, was zu einer längeren Wartezeit, aber weniger Kampfzeit führt. Insgesamt hat dieser Weg eine höhere Belohnung, da die gesamte Einsteigezeit 5 Sekunden Wartezeit plus 0 Sekunden Kampfzeit beträgt. Durch Exploration, obwohl die anfänglich geduldige Aktion höhere Kosten verursacht als die durchsetzungsfähige Strategie, sind die Gesamtkosten niedriger, was eine belohnendere Strategie offenbart
Algorithmus-Mechanik
Nach \(\Delta t\) Schritten in die Zukunft wird der Agent einen nächsten Schritt entscheiden. Das Gewicht für diesen Schritt wird als \(\gamma^{\Delta t}\) berechnet, wobei \(\gamma\) (der Diskontierungsfaktor) eine Zahl zwischen 0 und 1 ist. Unter der Annahme \(\gamma < 1\),bewertet es früher erhaltene Belohnungen höher als später erhaltene, was den Wert eines guten Starts widerspiegelt. \(\gamma\) kann auch als die Wahrscheinlichkeit interpretiert werden, bei jedem Schritt \(\Delta t\) erfolgreich zu sein oder zu überleben.
Der Algorithmus hat eine Funktion, die die Qualität einer Zustands-Aktions-Kombination berechnet: \(Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\). Bevor das Lernen beginnt, wird \(Q\) auf einen möglicherweise willkürlichen festen Wert initialisiert, der vom Programmierer gewählt wird. Zu jedem Zeitpunkt \(t\),wählt der Agent eine Aktion \(A_t\),beobachtet eine Belohnung \(R_{t+1}\),tritt in einen neuen Zustand \(S_{t+1}\) ein (der von sowohl dem vorherigen Zustand \(S_t\)als auch der gewählten Aktion abhängen kann),und \(Q\) wird aktualisiert. Die Kernaktualisierung ist eine Bellman-Gleichung als eine einfache Wert-Iterations-Aktualisierung, die den gewichteten Durchschnitt des aktuellen Werts und der neuen Information verwendet:
\(Q_{new}(S_t, A_t) \leftarrow (1 - \alpha) \cdot Q(S_t, A_t) + \alpha \cdot [R_{t+1} + \gamma \max_a Q(S_{t+1}, a)]\)
wobei \(\alpha\) die Lernrate ist, die steuert, wie viel neue Information alte Information überschreibt.
Exploration und Exploitation
Der Algorithmus beruht auf einem Gleichgewicht zwischen Exploration (Ausprobieren neuer Aktionen, um ihre Belohnungen zu entdecken)und Exploitation(Wählen von Aktionen, die bekanntermaßen hohe Belohnungen erzielen. Eine teilweise zufällige Politik, wie Epsilon-Greedy, wählt die bekannteste Aktion die meiste Zeit, aber wählt gelegentlich eine zufällige Aktion, um zu explorieren. Dies stellt sicher, dass der Agent seine Schätzungen im Laufe der Zeit verbessern kann, wie im Zug-Einsteig-Beispiel gesehen, wo zufällige Exploration eine bessere Strategie offenbarte
Konvergenz und Optimalität
Für jeden endlichen Markov-Entscheidungsprozess konvergiert Q-learning zu einer optimalen Politik, die die erwartete Gesamtbelohnung von jedem Ausgangszustand maximiert, vorausgesetzt unendliche Explorationszeitund ein geeigneter Lernraten-Zeitplan. Der Algorithmus benötigt kein Modell der Übergangsdynamik der Umgebung, was ihn auf Probleme anwendbar macht, bei denen ein solches Modell unbekannt oder komplex ist. Diese Modellfreiheit unterscheidet ihn von modellbasierten Methoden, die explizite Übergangswahrscheinlichkeiten benötigen
Anwendungen und Erweiterungen
Q-learning wurde in Robotik, Spieleentwicklung,und autonomen Systemen angewendet. Seine tabellarische Form funktioniert für kleine Zustandsräume, aber für große oder kontinuierliche Räume haben Erweiterungen wie Deep-Q-Networks Q-learning mit Deep learningund Neural network Funktionsapproximatoren kombiniert. Diese Fortschritte haben Erfolge in Bereichen wie Artificial intelligence Spielagenten und Machine learning Steuerungsaufgaben ermöglicht. Die Prinzipien des Algorithmus unterliegen auch moderner Reinforcement learning Forschung an Institutionen wie BAIR (Berkeley AI Research)und MIT CSAIL.