Q-Lernen

Q-Lernen ist eine Methode des maschinellen Lernens. Sie gehört zum Lernstil des bestärkenden Lernens und ist eine Form des temporalen Differenzlernens. Beim bestärkenden Lernen führt ein Agent Aktionen aus und erhält dafür Belohnungen. Er passt seine Strategie an, um die Belohnungen zu maximieren. Ein Agent mit einem TD-Learning-Algorithmus aktualisiert seine Schätzungen nach jeder Aktion auf Basis der gerade erhaltenen Belohnung und der geschätzten zukünftig zu erwartenden Belohnung.

Q steht für den langfristig erwarteten Wert einer Aktion. Q-Lernen ist modellfrei und baut auf dem Optimalitätsprinzip von Bellman auf.

Mit Q-Lernen kann ein Agent die optimale Strategie in einer Umgebung erlernen, die als Markow-Entscheidungsproblem beschrieben werden kann. 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. Eine Aktion führt zu einem Zustandsübergang, der mit einer Belohnung verbunden sein kann. Beim Q-Lernen müssen die Übergangswahrscheinlichkeiten und die Belohnungen zu Beginn des Lernvorgangs nicht bekannt sein.

Ziel des Agenten ist es, durch Versuch und Irrtum eine Strategie zu erlernen, 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}${\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]}${\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}${\displaystyle 0\leq \gamma <1}

Dabei ist ${\displaystyle r_{t+i}}${\displaystyle r_{t+i}} die Belohnung, die der Agent wahrscheinlich im Zeitschritt ${\displaystyle t+1}${\displaystyle t+1} erhält. Der Diskontierungsfaktor ${\displaystyle \gamma }${\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}${\displaystyle \gamma =0} zählt nur die direkte Belohnung einer Aktion, alle zukünftigen Belohnungen werden ignoriert. Für ${\displaystyle \gamma \rightarrow 1}${\displaystyle \gamma \rightarrow 1} erhalten zukünftige Belohnungen immer mehr Gewicht.^{[2] :487–491[3] :17} Typische Werte für ${\displaystyle \gamma }${\displaystyle \gamma } liegen zwischen 0,95 und 0,99.^{[4] :738}

Der Agent lernt eine Nutzenfunktion Q(s,a), die den kumulierten Reward maximiert.

${\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} )]}${\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} )]}

Durch wiederholtes Ausführen aller Aktionen in allen Zuständen mit darauf folgender Anpassung der Schätzwerte Q(s,a) wird die beste Aktion für jeden Zustand gefunden. Die Lernrate ${\displaystyle 0\leq \alpha \leq 1}${\displaystyle 0\leq \alpha \leq 1} bestimmt, wie stark die aktuelle Belohnung die letzte Schätzung verändert. Bei einem Wert von 1 würde der Q-Wert durch den neu berechneten ersetzt werden. Bei einer Größe bleibt der alte Wert erhalten.

Q-Learning ist ein Algorithmus, der strategiefern (englisch off policy) lernt. Er folgt beim Lernen nicht der Strategie mit den höchsten Q-Werten. Er muss alle Aktionen in allen Zuständen erkunden und verwendet dazu die ε-greedy policy als Erkundungs-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.^{[2] :494,495}

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 bestimmt:

$${\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} )]}$${\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} )]}

Tiefes Q-Lernen wurde von Google DeepMind 2013 entwickelt. Es verwendet ein neuronales Netz mit CNN-Schichten als Funktionsapproximator. Dadurch lassen sich auch Probleme lösen, die mit dem traditionellen Q-Lernen nicht hätte gelöst werden können. Mit Hilfe von Experience Replay werden (s,a,r,s') in einer Datenbank gespeichert. Dadurch lassen sich auch Spiele wie Go online trainieren. Die Aktualisierung von Q geschieht mit Hilfe Fehlerrückführung und einem Optimierer wie zum Beispiel dem stochastischen Gradientenverfahren.

Das Netz wird nach einer gewissen Zeit trainiert. Dabei kommt eine gemischte, randomisierte Teilmenge (Batch) der Daten zum Einsatz. Dies ist wesentlich performanter und verhindert Korrelation in den Daten.

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 {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} ))}$${\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 })}$${\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. ↑ Encyclopedia of Machine Learning. S. 819, doi:10.1007/978-0-387-30164-8 (springer.com [abgerufen am 17. August 2022]). 
2. ↑ ^{a b} 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. 
3. ↑ 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. 
4. ↑ Aurélien Géron: Praxiseinstieg Machine Learning. 3. Auflage. dpunkt Verlag, Heidelberg 2023, ISBN 978-3-96009-212-4. 

• Maschinelles Lernen