Double Q-Learning ist eine Variante des Q-Learning-Algorithmus im Bereich des bestärkenden Lernens (Reinforcement Learning), die entwickelt wurde, um die Überschätzung von Aktionswerten zu reduzieren, die beim standardmäßigen Q-Learning auftreten kann. Sie wurde 2010 von Hado van Hasselt eingeführt. Die Methode unterhält zwei unabhängige Q-Funktionen und verwendet sie abwechselnd bei Aktualisierungen, wodurch die positive Verzerrung gemildert wird, die aus der Verwendung des maximalen geschätzten Werts in der Bellman-Gleichung entsteht. Dies macht sie besonders nützlich in Umgebungen mit verrauschten oder stochastischen Belohnungen, in denen standardmäßiges Q-Learning aufgrund überhöhter Wertschätzungen zu suboptimalen Strategien konvergieren kann.
Der Algorithmus ist modellfrei, das heißt, er benötigt kein Modell der Umgebung, und er kann Probleme mit stochastischen Übergängen und Belohnungen ohne Anpassung bewältigen. Für jeden endlichen Markov-Entscheidungsprozess zielt Double Q-Learning, wie auch Q-Learning, darauf ab, eine optimale Strategie zu finden, die die erwartete Gesamtbelohnung über aufeinanderfolgende Schritte maximiert, gegeben unendliche Erkundungszeit und eine teilweise zufällige Strategie. Der Name „Q“ bezieht sich auf die Qualitätsfunktion, die die erwartete Belohnung einer Aktion in einem gegebenen Zustand berechnet.
Überschätzung beim Q-Learning
Standardmäßiges Q-Learning aktualisiert seine Wertfunktion unter Verwendung des maximalen geschätzten Q-Werts über alle möglichen Aktionen im nächsten Zustand. Diese Max-Operation führt eine systematische positive Verzerrung ein, da das Maximum verrauschter Schätzungen tendenziell das wahre Maximum übersteigt. In Umgebungen mit hoher Varianz bei Belohnungen oder Funktionsapproximation kann diese Überschätzung zu schlechter Leistung führen, da der Agent wiederholt Aktionen auswählen kann, die besser erscheinen, als sie tatsächlich sind. Beispielsweise könnte Q-Learning in einem Gitterlabyrinth, in dem ein Agent lernt, einen Ausgang mit 10 Punkten zu erreichen, dem Bewegen nach rechts einen höheren Wert zuweisen als nach links, wenn rechts schneller zum Ausgang führt, aber Überschätzung könnte dazu führen, dass ein suboptimaler Pfad bevorzugt wird, wenn Rauschen den Wert einer weniger effizienten Route aufbläht.
Double Q-Learning adressiert dies, indem es die Auswahl der Aktion von der Bewertung ihres Werts entkoppelt. Anstatt eine einzelne Q-Funktion zu verwenden, unterhält es zwei getrennte Schätzungen, Q_A und Q_B. Bei jeder Aktualisierung wird eine Funktion verwendet, um die beste Aktion im nächsten Zustand auszuwählen, und die andere, um ihren Wert zu schätzen. Dies reduziert die Verzerrung, da Auswahl und Bewertung auf unterschiedlichen, unabhängigen Schätzungen basieren.
Mechanik des Algorithmus
Die Kernaktualisierungsregel in Double Q-Learning beinhaltet zwei Q-Funktionen. Zu jedem Zeitschritt t wählt der Agent eine Aktion A_t aus, beobachtet eine Belohnung R_{t+1} und gelangt in einen neuen Zustand S_{t+1}. Mit gleicher Wahrscheinlichkeit aktualisiert der Algorithmus entweder Q_A oder Q_B. Beispielsweise verwendet er beim Aktualisieren von Q_A Q_B, um die beste Aktion im nächsten Zustand zu bestimmen, und verwendet dann Q_A, um den Wert dieser Aktion zu bewerten. Die Aktualisierung folgt einer Bellman-artigen Gleichung, gewichtet mit einer Lernrate alpha (zwischen 0 und 1) und einem Diskontierungsfaktor gamma (ebenfalls zwischen 0 und 1), der unmittelbare Belohnungen höher bewertet als zukünftige. Diese abwechselnde Aktualisierung stellt sicher, dass keine Funktion dominiert, und die Überschätzung wird reduziert, da die Max-Operation auf eine Funktion angewendet wird, während der Wert von der anderen gelesen wird.
Anwendungen und Erweiterungen
Double Q-Learning wurde im tiefen bestärkenden Lernen weitgehend übernommen, wo es die Grundlage des Double Deep Q-Network (Double DQN) Algorithmus bildet, der 2015 von van Hasselt und Kollegen eingeführt wurde. Double DQN kombiniert die Idee mit Deep learning-Techniken und verwendet neuronale Netze, um die Q-Funktionen zu approximieren, und hat verbesserte Stabilität und Leistung bei Aufgaben wie dem Spielen von Atari-Spielen gezeigt. Der Ansatz ist auch für breitere Bereiche wie künstliche Intelligenz und maschinelles Lernen relevant, wo wertbasierte Methoden für sequenzielle Entscheidungsfindung verwendet werden. Forscher haben das Konzept auf andere Umgebungen erweitert, wie Multi-Agenten-Systeme und kontinuierliche Aktionsräume, obwohl diese Erweiterungen oft zusätzliche Modifikationen erfordern.
Beziehung zu anderen Methoden
Double Q-Learning ist Teil einer Familie wertbasierter Reinforcement-Learning-Algorithmen, die standardmäßiges Q-Learning und SARSA umfasst. Im Gegensatz zu SARSA, das den Wert der verfolgten Strategie lernt, ist Double Q-Learning eine Off-Policy-Methode, das heißt, es kann eine optimale Strategie unabhängig von den Aktionen des Agenten lernen. Diese Eigenschaft macht es flexibler bei Erkundungsstrategien. Im Vergleich zu standardmäßigem Q-Learning tauscht Double Q-Learning eine leichte Erhöhung der Rechenkosten (aufgrund der Unterhaltung zweier Funktionen) gegen eine signifikante Reduktion der Verzerrung, was in der Praxis oft zu schnellerer Konvergenz zu optimalen Strategien führt. Die Technik ist auch mit Ensemble-Methoden verwandt, die mehrere Schätzungen mitteln, um die Varianz zu reduzieren, obwohl Double Q-Learning speziell auf Verzerrung abzielt und nicht auf Varianz.
Einschränkungen und Überlegungen
Während Double Q-Learning die Überschätzung reduziert, eliminiert es sie nicht vollständig, insbesondere wenn die beiden Q-Funktionen im Laufe der Zeit korreliert werden. In einigen Fällen kann es Unterschätzung einführen, was das Lernen in frühen Phasen verlangsamen kann. Der Algorithmus erfordert auch eine sorgfältige Abstimmung von Hyperparametern wie Lernrate und Diskontierungsfaktor. Im tiefen bestärkenden Lernen fügt die Verwendung von Zielnetzwerken, wie in Double DQN, weitere Komplexität hinzu, ist aber oft für Stabilität notwendig. Trotz dieser Herausforderungen bleibt Double Q-Learning eine grundlegende Technik im Feld, und seine Prinzipien haben viele nachfolgende Algorithmen beeinflusst, einschließlich derer, die in fortschrittlichen Systemen an Institutionen wie BAIR (Berkeley AI Research) und MIT CSAIL entwickelt wurden.
Infobox
- Typ: Konzept
- eingeführt: 2010
- eingeführt_von: Hado van Hasselt
- verwandt: q-learning
Kategorien
- reinforcement-learning
- algorithmus
- machine-learning
- wertbasierte-methoden