Was ist der Unterschied zwischen Wertiteration und Richtlinieniteration?

88

Was ist der Unterschied zwischen Richtlinieniteration und Wertiteration beim verstärkten Lernen ?

Soweit ich weiß, verwenden Sie bei der Wertiteration die Bellman-Gleichung, um die optimale Richtlinie zu ermitteln, während Sie bei der Richtlinieniteration zufällig eine Richtlinie π auswählen und die Belohnung für diese Richtlinie ermitteln.

Mein Zweifel ist, dass, wenn Sie eine zufällige Richtlinie π in PI auswählen, wie garantiert ist, dass diese die optimale Richtlinie ist, selbst wenn wir mehrere zufällige Richtlinien auswählen.

Arslán
quelle
13
Es wäre angemessener gewesen, diese Frage auf Websites wie ai.stackexchange.com , stats.stackexchange.com oder datascience.stackexchange.com zu stellen .
nbro

Antworten:

118

Schauen wir sie uns nebeneinander an. Die wichtigsten Teile zum Vergleich sind hervorgehoben. Die Zahlen stammen aus Sutton und Bartos Buch: Reinforcement Learning: Eine Einführung .

Geben Sie hier die Bildbeschreibung ein Wichtige Punkte:

  1. Die Richtlinieniteration umfasst: Richtlinienbewertung + Richtlinienverbesserung , und die beiden werden iterativ wiederholt, bis die Richtlinie konvergiert.
  2. Die Wertiteration umfasst: Finden einer optimalen Wertefunktion + eine Richtlinienextraktion . Es gibt keine Wiederholung der beiden, denn sobald die Wertefunktion optimal ist, sollte auch die daraus resultierende Richtlinie optimal sein (dh konvergieren).
  3. Das Finden einer optimalen Wertfunktion kann auch als eine Kombination aus Richtlinienverbesserung (aufgrund von max) und abgeschnittener Richtlinienbewertung (Neuzuweisung von v_ (s) nach nur einem Durchlauf aller Zustände unabhängig von der Konvergenz) angesehen werden.
  4. Die Algorithmen zur Richtlinienbewertung und zum Finden der optimalen Wertfunktion sind bis auf eine Maximaloperation (wie hervorgehoben) sehr ähnlich.
  5. In ähnlicher Weise sind die wichtigsten Schritte zur Verbesserung der Richtlinien und zur Extraktion der Richtlinien identisch, mit der Ausnahme, dass erstere eine Stabilitätsprüfung umfassen.

Nach meiner Erfahrung ist die Richtlinieniteration schneller als die Wertiteration , da eine Richtlinie schneller konvergiert als eine Wertfunktion. Ich erinnere mich, dass dies auch im Buch beschrieben ist.

Ich denke, die Verwirrung kam hauptsächlich von all diesen etwas ähnlichen Begriffen, die mich auch vorher verwirrten.

Zyxue
quelle
2
Ich bin damit einverstanden, dass die Richtlinieniteration in weniger Iterationen konvergiert, und ich habe an mehreren Stellen gelesen, dass sie schneller ist. Ich habe einige einfache Experimente zum Lösen von Boxwelten und Labyrinthen mit beiden Methoden in Sackleinen durchgeführt. Ich fand heraus, dass die Wertiteration mehr Iterationen durchführte, aber weniger Zeit brauchte, um Konvergenz zu erreichen. YMMV.
Ryan
1
@Chrom, du hättest das Gegenteil lesen sollen. Hier ist ein Zitat aus dem Buch " Richtlinieniteration konvergiert häufig in überraschend wenigen Iterationen. Dies wird durch das Beispiel in Abbildung 4.1 veranschaulicht. " Aus Seite 65 der 2017nov5- Version des Buches.
Zyxue
2
Ja, ich habe mit verschiedenen Geschmacksrichtungen der Grid-Welt gespielt. Ich wollte nur darauf hinweisen, dass "Schneller" in Bezug auf Iterationen wahrscheinlich PI begünstigen wird. Aber "Schneller" in Sekunden könnte tatsächlich VI bevorzugen.
Ryan
3
Zur Verdeutlichung benötigt die Richtlinieniteration weniger Iterationen, ist jedoch rechenintensiver als die Wertiteration. Welches schneller ist, hängt von der Umgebung ab.
RF Nelson
2
Ich weiß, dass dies ein alter Beitrag ist. Ich empfehle jedoch dringend, dies zu untersuchen ( medium.com/@m.alzantot/… ). Der Link enthält einen Code, der mich viel klarer gemacht hat.
Tandem
72

In Richtlinieniterationsalgorithmen beginnen Sie mit einer zufälligen Richtlinie, suchen dann die Wertfunktion dieser Richtlinie (Schritt zur Richtlinienbewertung) und suchen dann eine neue (verbesserte) Richtlinie basierend auf der vorherigen Wertfunktion usw. In diesem Prozess wird garantiert, dass jede Richtlinie eine strikte Verbesserung gegenüber der vorherigen darstellt (es sei denn, sie ist bereits optimal). Bei einer bestimmten Richtlinie kann ihre Wertefunktion mit dem Bellman-Operator abgerufen werden .

Bei der Wertiteration beginnen Sie mit einer Zufallswertfunktion und finden dann in einem iterativen Prozess eine neue (verbesserte) Wertfunktion, bis Sie die optimale Wertfunktion erreicht haben. Beachten Sie, dass Sie die optimale Richtlinie leicht aus der Funktion für den optimalen Wert ableiten können. Dieser Prozess basiert auf dem Optimalitäts-Bellman-Operator .

In gewissem Sinne haben beide Algorithmen dasselbe Arbeitsprinzip und können als zwei Fälle der verallgemeinerten Richtlinieniteration angesehen werden . Der Optimalitäts-Bellman-Operator enthält jedoch einen Max- Operator, der nicht linear ist und daher unterschiedliche Merkmale aufweist. Darüber hinaus können hybride Methoden zwischen reiner Wertiteration und reiner Richtlinieniteration verwendet werden.

Pablo EM
quelle
1
Schöne Beschreibung dazu. Lassen Sie mich dieses Ding in der Richtlinieniteration hinzufügen, es verwendet die Belman-Erwartungsgleichung und in der Wertiteration die Melman-Maximalgleichung. Bei der Wertiteration kann es weniger Iterationen geben, aber bei einer Iteration kann so viel Arbeit anfallen. Für die Richtlinieniteration weitere Iterationen
Shamane Siriwardhana
Gibt es nicht auch einen Maximaloperator in der Richtlinieniteration? Wie kann ich die Richtlinie ansonsten basierend auf der neuen Wertefunktion aktualisieren?
Huangzonghao
Nein, der SARSA-Algorithmus ist ein typisches Beispiel für die Iteration von Richtlinien. Wie Sie in diesem Pseudocode ( unvollständigideas.net / book/ebook/ node64.html ) sehen können, enthält die Wertfunktionsaktualisierung keinen Max-Operator. Wenn Sie jedoch einen Max-Operator für die Auswahl der besten Aktionen aus der Wertfunktion meinen (dh gierige Aktionen), gibt es in einem solchen Prozess eine Max-Operation.
Pablo EM
10

Der grundlegende Unterschied ist -

In Richtlinieniteration - Sie wählen zufällig eine Richtlinie aus und suchen die entsprechende Wertfunktion. Suchen Sie dann eine neue (verbesserte) Richtlinie basierend auf der vorherigen Wertfunktion. Dies führt zu einer optimalen Richtlinie.

In Wertiteration - Sie wählen zufällig eine Wertefunktion aus und suchen dann in einem iterativen Prozess eine neue (verbesserte) Wertfunktion, bis die optimale Wertfunktion erreicht ist. Anschließend leiten Sie aus dieser optimalen Wertfunktion eine optimale Richtlinie ab.

Die Richtlinieniteration basiert auf dem Prinzip „Richtlinienbewertung -> Richtlinienverbesserung“.

Die Wertiteration funktioniert nach dem Prinzip der „Optimalwertfunktion -> optimale Richtlinie“.

Himanshu Gupta
quelle
0

Für mich ist VI im Gegensatz zu @zyxues Idee im Allgemeinen viel schneller als PI.

Der Grund ist sehr einfach, wie Sie bereits wussten, wird die Bellman-Gleichung zum Lösen der Wertfunktion für eine bestimmte Richtlinie verwendet. Da wir die Wertfunktion für eine optimale Richtlinie direkt lösen können, ist das Lösen der Wertfunktion für eine aktuelle Richtlinie offensichtlich Zeitverschwendung.

Was Ihre Frage zur Konvergenz von PI betrifft, könnten Sie die Tatsache übersehen, dass Sie die Strategie für das gesamte Spiel verbessern, wenn Sie die Strategie für jeden Informationsstatus verbessern. Dies ist auch leicht zu beweisen, wenn Sie mit der Minimierung des kontrafaktischen Bedauerns vertraut waren - die Summe des Bedauerns für jeden Informationszustand hat die Obergrenze des allgemeinen Bedauerns gebildet, und somit minimiert das Bedauern für jeden Zustand das allgemeine Bedauern, was führt zur optimalen Politik.

Antwort777
quelle