Warum überschätzt Q-Learning die Aktionswerte?

8

Ich habe Schwierigkeiten, eine Erklärung dafür zu finden, warum Standard-Q-Learning dazu neigt, Q-Werte zu überschätzen (was durch die Verwendung von doppeltem Q-Learning behoben wird). Die einzigen Quellen, die ich gefunden habe, erklären nicht genau, warum diese Überschätzung auftritt.

Zum Beispiel sagt der Wikipedia-Artikel über Q-Learning:

Da der maximale angenäherte Aktionswert im Q-Learning-Update verwendet wird, kann Q-Learning in lauten Umgebungen manchmal die Aktionswerte überschätzen und das Lernen verlangsamen.

Was bedeutet das? Ich verstehe Q-Learning, aber nicht das oben genannte. Warum führt die Verwendung des maximalen q-Werts zu einer Überschätzung?

Vielen Dank!

Karnivaurus
quelle

Antworten:

4

Q(s,a)=r+γmaxa[Q(s,a)]

Da die Q-Werte sehr verrauscht sind, erhalten Sie wahrscheinlich einen überschätzten Wert, wenn Sie das Maximum für alle Aktionen festlegen. Denken Sie so, der erwartete Wert eines Würfelwurfs ist 3,5, aber wenn Sie die Würfel 100 Mal werfen und das Maximum über alle Würfe nehmen, nehmen Sie sehr wahrscheinlich einen Wert, der größer als 3,5 ist (denken Sie, dass jeder mögliche Aktionswert bei Zustand s in einem Würfelwurf).

Wenn alle Werte gleichermaßen überschätzt würden, wäre dies kein Problem, da es auf den Unterschied zwischen den Q-Werten ankommt. Wenn die Überschätzungen jedoch nicht einheitlich sind, kann dies das Lernen verlangsamen (da Sie Zeit damit verbringen, Zustände zu erkunden, die Sie für gut halten, aber nicht).

Die vorgeschlagene Lösung (Double Q-Learning) besteht darin, zwei verschiedene Funktionsapproximatoren zu verwenden, die an verschiedenen Stichproben trainiert werden, einen zur Auswahl der besten Aktion und einen zur Berechnung des Werts dieser Aktion, da die beiden Funktionsapproximatoren unterschiedliche Stichproben gesehen haben unwahrscheinlich, dass sie die gleiche Aktion überschätzen.

lgvaz
quelle
Warum helfen "Approximatoren mit zwei Funktionen, die unterschiedliche Beispiele gesehen haben"?
Albert Chen
1
Weil einer der Funktionsapproximatoren möglicherweise Beispiele sieht, die die Aktion a1 überschätzen, während der andere Beispiele sieht, die die Aktion a2 überschätzen. Das Wichtigste ist, die gleiche Aktion nicht zu überschätzen
lgvaz
3

Ich bin mit dem verstärkten Lernen nicht sehr vertraut, aber die nächste Zeile in dem Wikipedia-Artikel, den Sie (derzeit) zitieren, bezieht sich auf das Papier Double Q-Learning (NIPS 2010) . Die Zusammenfassung zu diesem Papier sagt

Diese Überschätzungen resultieren aus einer positiven Verzerrung, die eingeführt wird, weil Q-Learning den maximalen Aktionswert als Annäherung für den maximal erwarteten Aktionswert verwendet.

Zusammen scheinen diese zu sagen, dass, wenn die Q Funktion ist in Wirklichkeit stochastische, beobachtete Belohnungen r^ resultierend aus einem State-Action-Paar (s,a) wird mit etwas (0-Mittelwert) Rauschen verbunden sein, z r^=r+ϵ. Dann weilQ wird basierend auf aktualisiert maxaQoldwird der Maximalwert tendenziell eine Kombination aus hoher Belohnung und / oder großen positiven Rauschrealisierungen . Wenn und ignoriert wird , ist der Wert von tendenziell eine Überschätzung.r ϵrmaxr^maxϵQ

(Wie bereits erwähnt, bin ich mit diesem Bereich nicht vertraut und habe nur einen Blick auf Wikipedia und die obige Zusammenfassung geworfen, sodass diese Interpretation falsch sein könnte.)

GeoMatt22
quelle
0

Zunächst möchte ich aus dem Buch von Sutton und Barto zitieren

... Bei diesen Algorithmen wird implizit ein Maximum über den geschätzten Werten als Schätzung des Maximalwerts verwendet, was zu einer signifikanten positiven Verzerrung führen kann. Um zu sehen, warum, betrachten Sie einen einzelnen Zustand s, in dem es viele Aktionen a gibt, deren wahre Werte q (s, a) alle Null sind, deren geschätzte Werte Q (s, a) jedoch unsicher sind und daher einige über und einige verteilt sind unter Null.

Es ist ein bisschen vage. Hier ist ein einfaches Beispiel. wobei Q1 (s, X) = Q2 (s, X) = 0 ist, aber in der Praxis können die Werte unsicher sein.

Q1 (s, A) = 0,1, Q1 (s, B) = 0, Q1 (s, C) = -0,1

Q2 (s, A) = -0,1, Q2 (s, B) = 0,1, Q2 (s, C) = 0

Wenn Sie Q1 nur selbst aktualisieren, wird immer A at s zum Aktualisieren ausgewählt. Wenn Sie jedoch max_a Q2 (s, a) auswählen, um Q1 zu aktualisieren, kann Q2 die Situation kompensieren. Außerdem müssen Sie Q1 verwenden, um Q2 auf die andere Weise zu trainieren. Das Rauschen in Q2 ist unabhängig von dem in Q1, da Q1 und Q2 unter Verwendung unterschiedlicher Datensätze getrennt trainiert werden.

Albert Chen
quelle