Politikbewertung
Politikbewertung ist ein Verfahren zur Bestimmung der Wertfunktion einer gegebenen Politik.
Die Politikbewertung kann verwendet werden, um sowohl die Zustandswertfunktion als auch die Aktionswertfunktion zu schätzen. Für DP-Methoden wird jedoch die Zustandswertfunktion verwendet.
Wie bekannt, kann die Zustandswertfunktion einer gegebenen Politik durch Lösen einer Bellman-Gleichung bestimmt werden:
vπ(s)=a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))Wenn ein vollständiges Modell der Umgebung vorliegt (d. h. bekannte Übergangswahrscheinlichkeiten und erwartete Belohnungen für alle Zustands-Aktions-Paare), sind die einzigen verbleibenden Unbekannten in der Gleichung die Zustandswerte. Daher kann die obige Gleichung als ein System von ∣S∣ linearen Gleichungen mit ∣S∣ Unbekannten umformuliert werden.
Beispielsweise kann bei einer MDP mit 2 Zuständen (s1, s2) und 2 Aktionen (Wechsel zu s1, Wechsel zu s2) die Zustandswertfunktion wie folgt definiert werden:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))Dieses System kann mit Standardverfahren der linearen Algebra gelöst werden.
Eine eindeutige Lösung eines solchen linearen Gleichungssystems ist garantiert, wenn mindestens eine der folgenden Bedingungen erfüllt ist:
- Der Diskontfaktor erfüllt γ<1;
- Die Politik π stellt sicher, dass bei Befolgung aus jedem Zustand s die Episode schließlich terminiert.
Iterative Politikauswertung
Die Lösung kann direkt berechnet werden, jedoch wird aufgrund der einfachen Implementierung häufiger ein iteratives Verfahren verwendet. Diese Methode beginnt damit, allen Zuständen beliebige Anfangswerte zuzuweisen, außer den Endzuständen, die auf 0 gesetzt werden. Die Werte werden dann iterativ mithilfe der Bellman-Gleichung als Aktualisierungsregel angepasst:
vk+1(s)←a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Die geschätzte Zustandswertfunktion vk konvergiert schließlich zu einer echten Zustandswertfunktion vπ, wenn k→∞ gilt, sofern vπ existiert.
Strategien zur Wert-Backup
Beim Aktualisieren von Wertschätzungen werden neue Schätzungen auf Basis vorheriger Werte berechnet. Das Bewahren vorheriger Schätzungen wird als Backup bezeichnet. Es gibt zwei gängige Strategien zur Durchführung von Backups:
- Vollständiges Backup: Bei dieser Methode werden die neuen Schätzungen in einem separaten Array gespeichert, das sich von dem mit den vorherigen (gesicherten) Werten unterscheidet. Folglich werden zwei Arrays benötigt — eines zur Aufbewahrung der vorherigen Schätzungen und ein weiteres zur Speicherung der neu berechneten Werte;
- In-place-Backup: Bei diesem Ansatz werden alle Werte in einem einzigen Array verwaltet. Jede neue Schätzung ersetzt sofort den vorherigen Wert. Diese Methode reduziert den Speicherbedarf, da nur ein Array benötigt wird.
In der Regel wird die Methode des In-place-Backups bevorzugt, da sie weniger Speicher benötigt und aufgrund der sofortigen Verwendung der neuesten Schätzungen schneller konvergiert.
Wann sollte die Aktualisierung gestoppt werden?
Bei der iterativen Politikauswertung gibt es keinen exakten Zeitpunkt, an dem der Algorithmus gestoppt werden sollte. Obwohl die Konvergenz im Grenzwert garantiert ist, sind weitere Berechnungen über einen bestimmten Punkt hinaus in der Praxis unnötig. Ein einfaches und effektives Abbruchkriterium ist das Verfolgen des absoluten Unterschieds zwischen aufeinanderfolgenden Wertschätzungen, ∣vk+1(s)−vk(s)∣, und der Vergleich mit einem kleinen Schwellenwert θ. Wenn nach einem vollständigen Aktualisierungszyklus (bei dem die Werte für alle Zustände aktualisiert werden) keine Änderungen den Wert θ überschreiten, kann der Prozess sicher beendet werden.
Pseudocode
Danke für Ihr Feedback!
Fragen Sie AI
Fragen Sie AI
Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen
Can you explain the difference between full backup and in-place backup in more detail?
How does the choice of the discount factor γ affect convergence?
Can you walk me through the pseudocode for iterative policy evaluation?
Awesome!
Completion rate improved to 2.7
Politikbewertung
Swipe um das Menü anzuzeigen
Politikbewertung ist ein Verfahren zur Bestimmung der Wertfunktion einer gegebenen Politik.
Die Politikbewertung kann verwendet werden, um sowohl die Zustandswertfunktion als auch die Aktionswertfunktion zu schätzen. Für DP-Methoden wird jedoch die Zustandswertfunktion verwendet.
Wie bekannt, kann die Zustandswertfunktion einer gegebenen Politik durch Lösen einer Bellman-Gleichung bestimmt werden:
vπ(s)=a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))Wenn ein vollständiges Modell der Umgebung vorliegt (d. h. bekannte Übergangswahrscheinlichkeiten und erwartete Belohnungen für alle Zustands-Aktions-Paare), sind die einzigen verbleibenden Unbekannten in der Gleichung die Zustandswerte. Daher kann die obige Gleichung als ein System von ∣S∣ linearen Gleichungen mit ∣S∣ Unbekannten umformuliert werden.
Beispielsweise kann bei einer MDP mit 2 Zuständen (s1, s2) und 2 Aktionen (Wechsel zu s1, Wechsel zu s2) die Zustandswertfunktion wie folgt definiert werden:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))Dieses System kann mit Standardverfahren der linearen Algebra gelöst werden.
Eine eindeutige Lösung eines solchen linearen Gleichungssystems ist garantiert, wenn mindestens eine der folgenden Bedingungen erfüllt ist:
- Der Diskontfaktor erfüllt γ<1;
- Die Politik π stellt sicher, dass bei Befolgung aus jedem Zustand s die Episode schließlich terminiert.
Iterative Politikauswertung
Die Lösung kann direkt berechnet werden, jedoch wird aufgrund der einfachen Implementierung häufiger ein iteratives Verfahren verwendet. Diese Methode beginnt damit, allen Zuständen beliebige Anfangswerte zuzuweisen, außer den Endzuständen, die auf 0 gesetzt werden. Die Werte werden dann iterativ mithilfe der Bellman-Gleichung als Aktualisierungsregel angepasst:
vk+1(s)←a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Die geschätzte Zustandswertfunktion vk konvergiert schließlich zu einer echten Zustandswertfunktion vπ, wenn k→∞ gilt, sofern vπ existiert.
Strategien zur Wert-Backup
Beim Aktualisieren von Wertschätzungen werden neue Schätzungen auf Basis vorheriger Werte berechnet. Das Bewahren vorheriger Schätzungen wird als Backup bezeichnet. Es gibt zwei gängige Strategien zur Durchführung von Backups:
- Vollständiges Backup: Bei dieser Methode werden die neuen Schätzungen in einem separaten Array gespeichert, das sich von dem mit den vorherigen (gesicherten) Werten unterscheidet. Folglich werden zwei Arrays benötigt — eines zur Aufbewahrung der vorherigen Schätzungen und ein weiteres zur Speicherung der neu berechneten Werte;
- In-place-Backup: Bei diesem Ansatz werden alle Werte in einem einzigen Array verwaltet. Jede neue Schätzung ersetzt sofort den vorherigen Wert. Diese Methode reduziert den Speicherbedarf, da nur ein Array benötigt wird.
In der Regel wird die Methode des In-place-Backups bevorzugt, da sie weniger Speicher benötigt und aufgrund der sofortigen Verwendung der neuesten Schätzungen schneller konvergiert.
Wann sollte die Aktualisierung gestoppt werden?
Bei der iterativen Politikauswertung gibt es keinen exakten Zeitpunkt, an dem der Algorithmus gestoppt werden sollte. Obwohl die Konvergenz im Grenzwert garantiert ist, sind weitere Berechnungen über einen bestimmten Punkt hinaus in der Praxis unnötig. Ein einfaches und effektives Abbruchkriterium ist das Verfolgen des absoluten Unterschieds zwischen aufeinanderfolgenden Wertschätzungen, ∣vk+1(s)−vk(s)∣, und der Vergleich mit einem kleinen Schwellenwert θ. Wenn nach einem vollständigen Aktualisierungszyklus (bei dem die Werte für alle Zustände aktualisiert werden) keine Änderungen den Wert θ überschreiten, kann der Prozess sicher beendet werden.
Pseudocode
Danke für Ihr Feedback!