Q-Lernen

Q-Lernen ist eine Methode des bestärkenden Lernens. Beim bestärkenden Lernen führt ein Agent Aktionen in einer Umgebung aus und erhält dafür Belohnungen. Der Agent lernt eine Strategie, mit der er langfristig möglichst viele Belohnungen erhält. Beim Q-Lernen werden Q-Werte geschätzt. Ein Q-Wert steht für den langfristig erwarteten Wert einer Aktion. Q-Lernen ist eine Form des Temporal Difference Learnings, die Methode verbessert Schätzungen direkt nach dem Ausführen einer Aktion. Die Verbesserung erfolgt auf Basis der gerade erhaltenen Belohnung und der geschätzten zukünftig zu erwartenden Belohnung.

Q-Lernen ist modellfrei und baut auf dem Optimalitätsprinzip von Bellman auf. 1989 führte Chris Watkins diesen Algorithmus erstmals ein.^[1] Einen ausführlichen Konvergenzbeweis erbrachte er gemeinsam mit Peter Dayan im Jahr 1992.

Die Umgebung des Agenten kann als Markow-Entscheidungsproblem beschrieben werden. Die Umgebung besteht aus einer endlichen Zahl von Zuständen und Aktionen. In jedem Zustand s kann der Agent eine von mehreren Aktionen a auswählen. Die gewählte Aktion a führt mit einer Wahrscheinlichkeit p zu einem Zustandsübergang in einen Folgezustand s', der mit einer Belohnung r verbunden sein kann. Die Wahrscheinlichkeit p für den Folgezustand s' und die Belohnung r hängen nur von s und a ab. Wenn das Markow-Entscheidungsproblem vollständig bekannt ist und es nicht zu viele Zustände enthält, kann die optimale Strategie direkt mit dynamischer Programmierung berechnet werden, siehe auch Markow-Entscheidungsproblem#Algorithmen.

Die Aufgabe des Agenten ist nun, eine optimale Strategie für ein Markow-Entscheidungsproblem zu erlernen, dessen Übergangswahrscheinlichkeiten und Belohnungen zu Beginn des Lernvorgangs nicht bekannt sind. Dazu muss der Agent verschiedene Aktionen ausprobieren und aus den Rückmeldungen, die er zu s' und r erhält, eine Strategie lernen, die den insgesamt erwarteten Gewinn (englisch total discounted reward) maximiert.

Dieser Gewinn wird auch kumulierter Reward genannt. Er wird in der Regel als Summe aller Belohnungen ${\displaystyle r}$ über unendlich viele Zustandsübergänge berechnet:

${\displaystyle \mathbb {E} [G_{t}]=\mathbb {E} \left[\sum _{i=0}^{\infty }\gamma ^{i}\cdot r_{t+i}\right]}$ mit ${\displaystyle 0\leq \gamma <1}$

Dabei ist ${\displaystyle r_{t+i}}$ die Belohnung, die der Agent wahrscheinlich im Zeitschritt ${\displaystyle t+1}$ erhält. Der Diskontierungsfaktor ${\displaystyle \gamma }$ gewichtet Belohnungen, die kurzfristig erfolgen, höher als solche, die später erfolgen. Er sorgt auch dafür, dass die Summe für kontinuierliche Probleme (unendlich viele Zustandsübergänge) gegen einen Grenzwert konvergiert. Für ${\displaystyle \gamma =0}$ zählt nur die direkte Belohnung einer Aktion, alle zukünftigen Belohnungen werden ignoriert. Für ${\displaystyle \gamma \rightarrow 1}$ erhalten zukünftige Belohnungen immer mehr Gewicht.^{[3]:487–491[4]:17} Typische Werte für ${\displaystyle \gamma }$ liegen zwischen 0,95 und 0,99.^[5]:738

Beim Q-Lernen lernt der Agent Schätzwerte für eine Nutzenfunktion Q(s,a), auch Action-Value-Funktion genannt, die den kumulierten Reward für jede Aktion angibt:

${\displaystyle \mathrm {Q} (\mathrm {s} ,\mathrm {a} )\leftarrow \mathrm {Q} (\mathrm {s} ,\mathrm {a} )+\alpha [\mathrm {R} +\gamma \max \mathrm {Q} (\mathrm {s} ^{\prime },\mathrm {a} ^{\prime })-\mathrm {Q} (\mathrm {s} ,\mathrm {a} )]}$

Die Schätzwerte für die Action-Value-Funktion Q(s,a) geben den insgesamt erwarteten Nutzen an, wenn der Agent in Zustand s Aktion a wählt und in allen Folgezuständen s' jeweils die Aktion mit dem höchsten Q-Wert wählt, also der optimalen Strategie folgt. Der Ansatz des Q-Lernen besteht darin, die Schätzwerte unter Annahme der optimalen Strategie immer weiter zu verbessern. Dabei wird das Optimalitätsprinzip von Bellman angewendet. Es gilt für Probleme, bei denen sich die Optimallösung aus optimalen Teillösungen zusammensetzt.

Durch wiederholtes Besuchen aller Zustände s und Ausführen aller Aktionen a mit darauf folgender Anpassung der Schätzwerte für die Action-Value-Funktion Q(s,a) werden die Schätzwerte immer genauer. Die Lernrate ${\displaystyle 0\leq \alpha \leq 1}$ bestimmt, wie stark die letzte Schätzung angepasst wird. Bei einem Wert von 1 würde der Q-Wert durch den neu berechneten ersetzt werden. Bei einem Wert von 0 bleibt der alte Wert erhalten.

Q-Learning ist ein Algorithmus, der strategiefern (englisch off policy) lernt. Er folgt beim Lernen nicht der optimalen Strategie mit den höchsten Q-Werten, sondern verwendet zum Erkunden aller Aktionen in allen Zuständen eine Erkundungs-Policy, beispielsweise die ε-greedy policy. Hierbei ist der Agent entweder gierig (englisch greedy) und wählt die aus seiner Sicht erfolgversprechendste Aktion (gemäß seinem bereits erworbenen Wissen) oder er wählt eine zufällige Aktion. Der Parameter ε mit Werten zwischen 0 und 1 gibt die Wahrscheinlichkeit an, mit der er eine zufällige Aktion wählt.^[3]:494,495

Am Ende des Lernvorgangs besteht die optimale Strategie darin, in jedem Zustand s die Aktion a zu wählen, deren Q-Wert Q(s,a) am größten ist.

Q-Lernen ermittelt die optimale Strategie. Bei manchen Aufgabenstellungen führt die optimale Strategie über Zustände, bei denen das Risiko besteht, beim Abweichen von der optimalen Strategie hohe Verluste zu erfahren. Manchmal soll der Agent auch nach Abschluss der Trainingsphase weiter seine Umgebung erkunden, um sich an eine sich verändernde Umgebung anzupassen. Dann ist es besser, einer Strategie zu folgen, die weiter erkundet und dabei etwas Abstand von riskanten Zuständen hält. Eine solche Strategie kann mit SARSA optimiert werden.^{[3]:514–518}

SARSA (Algorithmus) ist auch eine Variation des temporalen Differenzlernens. Anders als Q-Lernen ist SARSA ein Algorithmus der strategiefolgend funktioniert. Formal ausgedrückt wird das Estimat des zukünftigen, diskontierten Q-Wertes anhand der Strategie verbessert, der der Agent folgt:

$${\displaystyle \mathrm {Q} (\mathrm {s} ,\mathrm {a} )\leftarrow \mathrm {Q} (\mathrm {s} ,\mathrm {a} )+\alpha [\mathrm {R} +\gamma \mathrm {Q} (\mathrm {s} ^{\prime },\mathrm {a} ^{\prime })-\mathrm {Q} (\mathrm {s} ,\mathrm {a} )]}$$

Einfache Aufgabenstellungen haben wenige diskrete Zustände und Aktionen. Dann kann jeder einzelne Schätzwert in einer Tabelle gespeichert und bearbeitet werden.

Bei vielen Aufgabenstellungen ist es nicht möglich, jeden einzelnen Q-Wert hinreichend genau abzuschätzen. Die Aufgaben haben entweder so viele Zustände, dass der Agent sie nicht alle wiederholt besuchen und erforschen kann oder sie haben kontinuierliche Zustände. Diese Aufgabenstellungen können dadurch gelöst werden, dass die Action-Value-Funktion approximiert wird, beispielsweise mit einem künstlichen neuronalen Netz.

Tiefes Q-Lernen (englisch Deep-Q-Learning) wurde von Google DeepMind 2013 entwickelt. Damit lassen sich auch Probleme lösen, die mit dem traditionellen Q-Lernen nicht hätten gelöst werden können. Tiefes Q-Lernen verwendet ein neuronales Netz mit CNN-Schichten als Funktionsapproximator. Zusätzlich werden alle Erfahrungen (s,a,r,s') zunächst in einem Replay-Memory gespeichert. Daraus werden anschließend zufällige Trainings-Batches erzeugt, die zum Lernen verwendet werden (englisch Experience Replay). Das ist wesentlich performanter als die direkte Verwendung der Erfahrungen und verringert Korrelationen zwischen ihnen. Die Aktualisierung von Q geschieht mit Hilfe einer Fehlerrückführung und einem Optimierer wie zum Beispiel dem stochastischen Gradientenverfahren.

Mit weiteren Optimierungen lassen sich auch Spiele wie Go online trainieren, siehe auch AlphaGo.

Q-Lernen ist nicht sonderlich gut in stochastischen Umgebungen, da der Aktionswert des Agenten überbewertet wird. Hasselt hat dies mit zwei Q-Lernfunktionen gelöst:$${\displaystyle \mathrm {Q} ^{\mathrm {A} }(\mathrm {s} ,\mathrm {a} )\leftarrow \mathrm {Q} ^{\mathrm {A} }(\mathrm {s} ,\mathrm {a} )+\alpha (\mathrm {s} ,\mathrm {a} )(\mathrm {R} +\gamma \mathrm {Q} ^{\mathrm {B} }(\mathrm {s} ^{\prime },\mathrm {a} ^{\prime })-\mathrm {Q} ^{\mathrm {A} }(\mathrm {s} ,\mathrm {a} ))}$$$${\displaystyle \mathrm {Q} ^{\mathrm {B} }(\mathrm {s} ,\mathrm {a} )\leftarrow \mathrm {Q} ^{\mathrm {B} }(\mathrm {s} ,\mathrm {a} )+\alpha (\mathrm {s} ,\mathrm {a} )(\mathrm {R} +\gamma \mathrm {Q} ^{A}(\mathrm {s} ^{\prime },\mathrm {a} ^{\prime })-\mathrm {Q} ^{\mathrm {B} }(\mathrm {s} ,\mathrm {a} ))}$$

Beim Nash Q-Lernen werden die Aktionen von anderen Agenten berücksichtigt. Sie eignet sich hervorragend für Multiagenten-Umgebungen.$${\displaystyle \mathrm {Nash~Q} _{\mathrm {t} -1}(\mathrm {s} ^{\prime })=\pi _{1}(\mathrm {s} ^{\prime })\cdot \pi _{1}(\mathrm {s} ^{\prime })\cdot \ldots \pi _{\mathrm {t} -1}(\mathrm {s} ^{\prime })}$$

• Watkins, Christopher. (1989). Learning From Delayed Rewards.
• B. Jang, M. Kim, G. Harerimana and J. W. Kim, "Q-Learning Algorithms: A Comprehensive Classification and Applications," in IEEE Access, vol. 7, pp. 133653-133667, 2019, doi:10.1109/ACCESS.2019.2941229.

1. ↑ Chris Watkins: Learning from Delayed Rewards. Ph.D. Thesis. 1989 (PDF [abgerufen am 26. April 2016]). 
2. ↑ Encyclopedia of Machine Learning. S. 819, doi:10.1007/978-0-387-30164-8 (springer.com [abgerufen am 17. August 2022]). 
3. ↑ ^{a b c} Jörg Frochte: Maschinelles Lernen: Grundlagen und Algorithmen in Python (= Hanser eLibrary). 3., überarbeitete und erweiterte Auflage. Hanser, München 2021, ISBN 978-3-446-46144-4. 
4. ↑ Uwe Lorenz: Reinforcement Learning: Aktuelle Ansätze verstehen – mit Beispielen in Java und Greenfoot. 2. Aufl. 2024. Springer Berlin Heidelberg, Berlin, Heidelberg 2024, ISBN 978-3-662-68310-1. 
5. ↑ Aurélien Géron: Praxiseinstieg Machine Learning. 3. Auflage. dpunkt Verlag, Heidelberg 2023, ISBN 978-3-96009-212-4.