Q-Lernen

Q-Lernen ist eine Form des temporalen Differenzlernens. Als solche ist es eine modellfreie Methode des bestärkenden Lernens. Da sie zur optimalen Wertefunktion konvergiert, ist sie eine der verbreitetsten Algorithmen.

Definition

„Q-Lernen ist eine Form des zeitlichen Differenzlernens. Als solches ist es eine modellfreie Verstärkungslernmethode, die Elemente der dynamischen Programmierung mit Monte-Carlo-Schätzungen kombiniert. Unter anderem aufgrund des Beweises von Watkins (1989), dass es zur optimalen Wertfunktion konvergiert, gehört das Q-Lernen zu den am häufigsten verwendeten und bekanntesten Verstärkungslernalgorithmen.“

– Stone et al., 2010

$$\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} )]$$Der Alphawert liegt zwischen 0 und 1. Bei einem Wert von 1 würde der Q-Wert durch den neuen ersetzt werden. Bei einer Größe von 0 würde nur der alte Wert berücksichtigt werden. Der Diskontierungsfaktor Gamma bestimmt, ob der Agent nach schnellen Erfolgen streben soll oder eher langfristigere Belohnungen wichtig sind. Auch dieser Wert liegt zwischen 0 und 1. Bei einem Wert von 0 würden nur schnelle Erfolge zählen, bei einem Wert von 1 würden eher zukünftige Belohnungen ins Gewicht fallen. Der Wert kann bei endlichen Episoden den Wert 1 annehmen. Ansonsten sollte der Wert unter 1 liegen, da die Menge an Belohnungen ansonsten gegen unendlich konvergiert.

s ist der gegenwärtige Zustand, a die gegenwärtige Handlung. R gibt den gegenwärtigen Belohnungswert wieder, wogegen der zweite Faktor die maximal mögliche Belohnung im Folgezustand ist. Die direkte Belohnung im Folgezustand kann zwar 0 sein, allerdings erhält dieser Belohnungswert auch wieder die Erwartung auf eine zukünftige Belohnung. Durch wiederholte Anpassung wird so die beste Handlung in jedem Zustand gefunden.

Q-Learning ist ein Algorithmus, der strategiefern lernt. Er verwendet nämlich einen Epsilon-Greedy-Algorithmus. Epsilon sorgt dafür, dass der Agent auch randomisierte Züge nimmt. Dadurch folgt er nicht der Greedy-Strategie, mit der er den Q-Wert aktualisiert.

Unterschiede zu SARSA

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:

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

Variationen

Tiefes Q-Lernen

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.

Doppeltes Q-Lernen

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

Nash Q-Lernen

Beim Nash Q-Lernen werden die Aktionen von anderen Agenten berücksichtigt. Sie eignet sich hervorragend für Multiagenten-Umgebungen.$$\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 })$$

Literatur

• 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.