Warum konvergiert der Richtlinieniterationsalgorithmus zur optimalen Richtlinien- und Wertfunktion?

10

Ich las Andrew Ngs Vorlesungsunterlagen über das Lernen der Verstärkung und versuchte zu verstehen, warum die Richtlinieniteration zur optimalen Wertfunktion und zur optimalen Richtlinie konvergierte .V.π

Die Iteration der Rückrufrichtlinie lautet:

Initialisieren π nach dem ZufallsprinzipWiederholen{L.et V.: =V.π \ Lösen Sie für die aktuelle Richtlinie die Bellman-Gleichungen und setzen Sie diese auf das aktuelle V.L.et π(s): =einrGmeinxeinEINs'P.sein(s')V.(s')}}

Warum führt ein Greedy-Algorithmus zu einer optimalen Richtlinie und einer optimalen Wertfunktion? (Ich weiß, dass gierige Algorithmen dies nicht immer garantieren oder in lokalen Optima stecken bleiben könnten, deshalb wollte ich nur einen Beweis für die Optimalität des Algorithmus sehen).

Außerdem scheint mir die Iteration von Richtlinien etwas Analoges zu Clustering oder Gradientenabstieg zu sein. Zum Clustering, weil wir mit der aktuellen Einstellung der Parameter optimieren. Ähnlich wie beim Gradientenabstieg, da nur ein Wert ausgewählt wird, der die Funktion zu erhöhen scheint. Diese beiden Methoden konvergieren nicht immer zu optimalen Maxima, und ich habe versucht zu verstehen, wie sich dieser Algorithmus von den zuvor erwähnten unterscheidet.


Das sind meine bisherigen Gedanken:

Angenommen, wir beginnen mit einer Richtlinie , und nach dem ersten Schritt haben wir für diese feste Richtlinie Folgendes:π1

V.π1(s)=R.(s)+γs'P.sπ1(s)(s')V.π1(s')

V.(1): =V.π1(s)

Wobei V ^ {(1)} die Wertfunktion für die erste Iteration ist. Dann wählen wir nach dem zweiten Schritt eine neue Richtlinie , um den Wert von zu erhöhen . Wenn wir nun mit der neuen Richtlinie den zweiten Schritt des Algorithmus ausführen, gilt die folgende Ungleichung:π2V.π1(s)π2

R.(s)+γs'P.sπ1(s)(s')V.π1(s')R.(s)+γs'P.sπ2(s)(s')V.π1(s')

Da wir im zweiten Schritt wählen , um die Wertfunktion im vorherigen Schritt zu erhöhen (dh um zu verbessern . Bisher ist klar, dass die Auswahl von nur V ^ {(1)} erhöhen kann. denn so wählen wir . Meine Verwirrung tritt jedoch im Wiederholungsschritt auf, denn sobald wir wiederholen und zu Schritt 1 zurückkehren, ändern wir die Dinge tatsächlich vollständig, weil wir für die neue Richtlinie neu berechnen . Welches gibt:π2V.(1)π2π2V.2π2

V.π2(s)=R.(s)+γs'P.sπ2(s)(s')V.π2(s')

aber es ist NICHT:

V.π1(s)=R.(s)+γs'P.sπ2(s)(s')V.π1(s')

Dies scheint ein Problem zu sein, da ausgewählt wurde, um zu verbessern , und nicht dieses neue . Grundsätzlich besteht das Problem darin, dass garantiert, dass verbessert wird, indem stattdessen wird von wenn die . Aber im Wiederholungsschritt ändern wir in , aber ich sehe nicht, wie dies garantiert, dass sich die Wertfunktion bei jeder Wiederholung monoton verbessert, da berechnet wurde, um die zu verbessern, wenn Die Wertfunktionen bleiben beiπ2V.(1)V.π2pich2R.(s)+γs'P.sπ1(s)(s')V.π1(s')π2pich1V.π1V.π1V.π2π2V.π1 V π 1, aber Schritt 1 ändert in (was schlecht ist, weil I nur die vorherige verbessert hat, die wir hatten).V.π1V.π2π2

Pinocchio
quelle
1
Nur eine Anmerkung: Gierig bedeutet nicht, dass ein Algorithmus im Allgemeinen keine optimale Lösung findet.
Regenschein
1
Die Wertiteration ist eher ein dynamischer als ein gieriger Algorithmus. Die beiden haben einige Gemeinsamkeiten, aber es gibt Unterschiede. Schauen Sie sich stackoverflow.com/questions/13713572/… an .
Francoisr
@francoisr das hat mir noch niemand gesagt. Vielleicht war es deshalb für mich so (unnötig) mysteriös. Ich kenne DP ziemlich gut. Trotzdem danke! :)
Pinocchio

Antworten:

4

Ich denke, der Teil, den Sie vermissen, ist, dass aus dem gleichen Grund garantiert ist, aus dem wir π 2π 1 bestellen können . Das ist im Wesentlichen die Definition, dass eine Politik besser ist als eine andere - dass ihre Wertfunktion in allen Staaten größer oder gleich ist. Sie haben dies durch Auswahl der Maximierungsaktionen garantiert - kein Statuswert kann möglicherweise schlechter sein als zuvor, und wenn sich nur eine Aktionsauswahl geändert hat, um eine bessere Maximierungsaktion auszuwählen, wissen Sie bereits (aber möglicherweise nicht berechnet), dass der V π 2 ( s ) für diesen Zustand wird höher sein als fürV.π2V.π1π2π1V.π2(s) .V.π1(s)

Wenn wir die Ergebnisse maximieren, um zu erzeugen , wissen wir nicht, wie die neuen V π 2 ( s ) für irgendeinen Zustand aussehen werden , aber wir wissen, dass s : V π 2 ( s ) V π ist 1 ( s ) .π2V.π2(s)s::V.π2(s)V.π1(s)

Wenn Sie also die Schleife durchlaufen und für die neue Richtlinie berechnen , haben Sie garantiert dieselben oder höhere Werte als zuvor. Wenn Sie die Richtlinie erneut aktualisieren, .V.π2π3π2π1

Neil Slater
quelle
4

Lassen Sie uns zunächst sehen, warum der Algorithmus-Iterationsalgorithmus funktioniert. Es hat zwei Schritte.

Schritt zur Richtlinienbewertung:

ist die allgemeine vektorielle Form des linearen Gleichungssystems.vn=rdn+γP.dnvn

Hier sind die Terme unmittelbare Belohnungen und entsprechende Zeilen der Übergangsmatrix.rdn,P.dn

Diese Bedingungen sind abhängig von der Richtlinie Πn

Durch Lösen des obigen Gleichungssystems können wir die Werte von vn

Schritt zur Verbesserung der Richtlinien:

Angenommen, wir konnten eine neue Richtlinie so dassΠn+1

rdn+1+γP.dn+1vnrdn+γP.dnvnrdn+1[ich- -γP.dn+1]]vnsagen, das ist Gl. 1

Basierend auf der neuen Richtlinie können wir nun v n + 1 = r d n + 1 + γ P d n + 1 v n + 1 finden , sagen wir, dies ist Gleichung 2.Πn+1vn+1=rdn+1+γP.dn+1vn+1

Wir werden zeigen, dass ;vn+1vn

dh im Wesentlichen für alle Staaten ergibt die neu gewählte Politik einen besseren Wert als die vorherige Politik Π nΠn+1Πn

Beweis:

Aus Gleichung 2 haben wir:

[ich- -γP.dn+1]]vn+1=rdn+1

Von haben wir1&2

vn+1vn

Im Wesentlichen steigen die Werte mit jeder Iteration monoton an.

Dies ist wichtig, um zu verstehen, warum die Richtlinieninteraktion nicht auf ein lokales Maximum beschränkt bleibt.

Eine Richtlinie ist nichts anderes als ein staatlicher Aktionsraum.

Bei jedem Schritt der Richtlinieniteration versuchen wir, mindestens eine Zustandsaktion zu finden, die sich zwischen und Π n unterscheidet, und prüfen, obΠn+1Πn . Nur wenn die Bedingung erfüllt ist, berechnen wir die Lösung für das neue System linearer Gleichungen.rdn+1+γP.dn+1vnrdn+γP.dnvn

Angenommen, und Π # sind das globale bzw. lokale Optimum.ΠΠ#

Impliziert, vv#

Angenommen, der Algorithmus steckt im lokalen Optimum fest.

Π#ΠΠ#vv#

oder mit anderen Worten,

[ich- -γP.d]]v[ich- -γP.d]]v#

rd[ich- -γP.d]]v#

rd+γP.dv#v#

rd+γP.dv#rd#+γP.d#v#

Daher hört die Richtlinieniteration nicht bei einem lokalen Optimum auf

Honig Dachs
quelle