Warum wird der Abzinsungssatz im REINFORCE-Algorithmus zweimal angezeigt?

Ich las das Buch Reinforcement Learning: Eine Einführung von Richard S. Sutton und Andrew G. Barto (vollständiger Entwurf, 5. November 2017).

Auf Seite 291 wird der Pseudocode für die episodische Monte-Carlo-Policy-Gradient-Methode vorgestellt. Wenn ich mir diesen Pseudocode anschaue, kann ich nicht verstehen, warum der Abzinsungssatz anscheinend zweimal erscheint, einmal im Aktualisierungsstatus und ein zweites Mal innerhalb der Rückgabe. [Siehe Abbildung unten]

Es scheint, dass die Rückkehr für die Schritte nach Schritt 1 nur eine Kürzung der Rückkehr des ersten Schritts ist. Wenn Sie nur eine Seite oben im Buch betrachten, finden Sie eine Gleichung mit nur 1 Abzinsungssatz (der in der Rückgabe).

Warum scheint der Pseudocode dann anders zu sein? Ich vermute, dass ich etwas falsch verstehe:

Der Abzinsungsfaktor wird zweimal angezeigt, und dies ist korrekt.

Dies liegt daran, dass die Funktion, die Sie in REINFORCE für ein episodisches Problem maximieren möchten (indem Sie den Gradienten verwenden), die erwartete Rückkehr aus einem bestimmten (Verteilungs-) Startzustand ist:

Wenn Sie während der Episode die Renditen , usw. , sind diese daher für das zu lösende Problem weniger relevant und werden ein zweites Mal um den Rabattfaktor reduziert, wie Sie festgestellt haben. Im Extremfall mit einem episodischen Problem und REINFORCE nur eine optimale Richtlinie für die erste Aktion.G 2 γ = $G_1$$G_2$$\gamma = 0$

Andere Algorithmen, die bei kontinuierlichen Problemen arbeiten, wie z. B. Actor-Critic, verwenden andere Formulierungen für , haben also diesen Faktor von .γ $J(\theta)$$\gamma^t$

Neils Antwort liefert bereits eine gewisse Intuition darüber, warum der Pseudocode (mit dem zusätzlichen Term) korrekt ist.$\gamma^t$

Ich möchte nur zusätzlich klarstellen, dass Sie nichts falsch zu verstehen scheinen. Gleichung (13.6) im Buch unterscheidet sich tatsächlich vom Pseudocode .

Jetzt habe ich nicht die Ausgabe des Buches, die Sie hier erwähnt haben, aber ich habe einen späteren Entwurf vom 22. März 2018, und der Text zu diesem speziellen Thema scheint ähnlich zu sein. In dieser Ausgabe:

• Gegen Ende von Seite 326 wird ausdrücklich erwähnt, dass sie in ihrem Beweis für den Richtliniengradientensatz annehmen .$\gamma = 1$
• Dieser Beweis führt schließlich zu derselben Gleichung (13.6) auf Seite 329.
• Unmittelbar unterhalb des Pseudocodes auf Seite 330 wird der Unterschied zwischen der Gleichung und dem Pseudocode kurz angesprochen, wobei gesagt wird, dass dieser Unterschied auf die Annahme von im Beweis zurückzuführen ist.$\gamma = 1$
• Direkt darunter geben sie in Übung 13.2 einige Hinweise darauf, worauf Sie achten sollten, wenn Sie den modifizierten Beweis für den Fall ableiten möchten, in dem .$\gamma < 1$

Es ist ein subtiles Problem.

Wenn Sie sich den A3C-Algorithmus in der Originalarbeit ansehen (S.4 und Anhang S3 für Pseudocode), ist der Schauspieler-Kritiker-Algorithmus (der gleiche Algorithmus, sowohl episodische als auch anhaltende Probleme) um einen Gammafaktor im Verhältnis zum Schauspieler- Kritiker-Pseudocode für episodische Probleme im Sutton- und Barto-Buch (S.332, Ausgabe Januar 2019 von http://incompleteideas.net/book/the-book.html ). Das Sutton and Barto-Buch enthält das zusätzliche "erste" Gamma, wie auf Ihrem Bild angegeben. Also ist entweder das Buch oder das A3C-Papier falsch? Nicht wirklich.

Der Schlüssel ist auf S. 199 des Sutton and Barto-Buches:

Wenn es eine Diskontierung gibt (Gamma <1), sollte dies als eine Form der Kündigung behandelt werden, die einfach durch Einbeziehung eines Faktors von in den zweiten Term von (9.2) erfolgen kann.

Das subtile Problem ist, dass es zwei Interpretationen für den Abzinsungsfaktor Gamma gibt:

1. Ein multiplikativer Faktor, der fernen zukünftigen Belohnungen weniger Gewicht beimisst.
2. Eine Wahrscheinlichkeit, 1 - Gamma, dass eine simulierte Flugbahn zu jedem Zeitpunkt fälschlicherweise endet. Diese Interpretation ist nur für episodische Fälle sinnvoll und nicht für fortlaufende Fälle.

Wörtliche Implementierungen:

1. Multiplizieren Sie einfach die zukünftigen Belohnungen und zugehörigen Größen (V oder Q) in der Zukunft mit Gamma.
2. Simulieren Sie einige Trajektorien und beenden Sie sie bei jedem Zeitschritt zufällig (1 - Gamma). Abgebrochene Flugbahnen geben keine unmittelbaren oder zukünftigen Belohnungen.

Die beiden Interpretationen von Gamma sind gültig. Die Wahl des einen oder anderen bedeutet jedoch, dass Sie ein anderes Problem angehen. Die Mathematik ist etwas anders und Sie erhalten ein zusätzliches Gamma, das mit der zweiten Interpretation multipliziert . $G \nabla\ln\pi(a|s)$

Wenn Sie sich beispielsweise in Schritt t = 2 und gamma = 0,9 befinden, lautet der Algorithmus für die zweite Interpretation, dass der Richtliniengradient oder . Dieser Term hat 19% weniger Gradientenleistung als der Term t = 0, aus dem einfachen Grund, dass 19% der simulierten Trajektorien durch t = 2 abgestorben sind. $\gamma^2 G \nabla\ln\pi(a|s)$$0.81 G \nabla\ln\pi(a|s)$

Bei der ersten Interpretation von Gamma gibt es keinen solchen 19% igen Zerfall. Der Richtliniengradient ist nur bei t = 2. Aber Gamma ist immer noch in um die zukünftigen Belohnungen abzuzinsen.$G \nabla\ln\pi(a|s)$$G$

Sie können wählen, welche Interpretation von Gamma Sie verwenden möchten, müssen jedoch die Konsequenzen für den Algorithmus berücksichtigen. Ich persönlich halte mich lieber an Interpretation 1, nur weil es einfacher ist. Also verwende ich den Algorithmus im A3C-Papier, nicht im Sutton- und Barto-Buch.

Ihre Frage betraf den REINFORCE-Algorithmus, aber ich habe über Schauspieler-Kritiker gesprochen. Sie haben genau das gleiche Problem in Bezug auf die beiden Gamma-Interpretationen und das zusätzliche Gamma in REINFORCE.