Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lernen Politikbewertung | Dynamische Programmierung
Einführung in das Reinforcement Learning
course content

Kursinhalt

Einführung in das Reinforcement Learning

Einführung in das Reinforcement Learning

1. Kernprinzipien des RL
2. Multi-Armed-Bandit-Problem
3. Dynamische Programmierung
4. Monte-Carlo-Methoden
5. Temporal-Differenz-Lernen

book
Politikbewertung

Note
Definition

Politikbewertung ist ein Verfahren zur Bestimmung der Wertfunktion einer gegebenen Politik.

Note
Hinweis

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 eine Zustandswertfunktion einer gegebenen Politik durch Lösen der Bellman-Gleichung bestimmt werden:

vπ(s)=aπ(as)s,rp(s,rs,a)(r+γvπ(s))v_\pi(s) = \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

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|S| linearen Gleichungen mit S|S| Unbekannten umformuliert werden.

Beispielsweise, wenn ein MDP 2 Zustände (s1s_1, s2s_2) und 2 Aktionen (Wechsel zu s1s_1, Wechsel zu s2s_2) hat, könnte die Zustandswertfunktion wie folgt definiert werden:

{V(s1)=0.5(5+0.9V(s1))+0.5(10+0.9V(s2))V(s2)=0.7(2+0.9V(s1))+0.3(0+0.9V(s2))\begin{cases} V(s_1) = 0.5 \cdot (5 + 0.9 \cdot V(s_1)) + 0.5 \cdot (10 + 0.9 \cdot V(s_2)) \\ V(s_2) = 0.7 \cdot (2 + 0.9 \cdot V(s_1)) + 0.3 \cdot (0 + 0.9 \cdot V(s_2)) \end{cases}

Dies kann mit Standardmethoden der linearen Algebra gelöst werden.

Eine eindeutige Lösung für ein solches lineares Gleichungssystem ist garantiert, wenn mindestens eine der folgenden Bedingungen erfüllt ist:

  • Der Diskontfaktor erfüllt γ<1γ < 1;
  • Die Politik π\pi stellt sicher, dass bei Befolgung aus jedem Zustand ss 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 mit der Zuweisung von beliebigen Anfangswerten für alle Zustände, außer für Endzustände, die auf 0 gesetzt werden. Die Werte werden dann iterativ mithilfe der Bellman-Gleichung als Aktualisierungsregel angepasst:

vk+1(s)aπ(as)s,rp(s,rs,a)(r+γvk(s))v_{k+1}(s) \gets \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_k(s')\Bigr)

Die geschätzte Zustandswertfunktion vkv_k konvergiert schließlich zu einer echten Zustandswertfunktion vπv_\pi, wenn kk \to \infty gilt, sofern vπv_\pi existiert.

Strategien zur Wert-Backup

Beim Aktualisieren von Wertschätzungen werden neue Schätzungen auf Basis vorheriger Werte berechnet. Der Prozess der Beibehaltung vorheriger Schätzungen wird als Backup bezeichnet. Es gibt zwei gängige Strategien zur Durchführung von Backups:

  • Vollständiges Backup: Diese Methode beinhaltet das Speichern der neuen Schätzungen in einem separaten Array, 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, zu dem der Algorithmus gestoppt werden sollte. Obwohl die Konvergenz im Grenzwert garantiert ist, sind weitere Berechnungen über einen bestimmten Punkt hinaus in der Praxis nicht notwendig. Ein einfaches und effektives Abbruchkriterium besteht darin, den absoluten Unterschied zwischen aufeinanderfolgenden Wertschätzungen, vk+1(s)vk(s)|v_{k+1}(s) - v_k(s)|, zu verfolgen und mit einem kleinen Schwellenwert θ\theta zu vergleichen. Wenn nach einem vollständigen Aktualisierungszyklus (bei dem die Werte für alle Zustände aktualisiert werden) keine Änderungen den Wert θ\theta überschreiten, kann der Prozess sicher beendet werden.

Pseudocode

question mark

Welche der folgenden Aussagen trifft auf die Methode der iterativen Politikauswertung zu?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 4

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

course content

Kursinhalt

Einführung in das Reinforcement Learning

Einführung in das Reinforcement Learning

1. Kernprinzipien des RL
2. Multi-Armed-Bandit-Problem
3. Dynamische Programmierung
4. Monte-Carlo-Methoden
5. Temporal-Differenz-Lernen

book
Politikbewertung

Note
Definition

Politikbewertung ist ein Verfahren zur Bestimmung der Wertfunktion einer gegebenen Politik.

Note
Hinweis

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 eine Zustandswertfunktion einer gegebenen Politik durch Lösen der Bellman-Gleichung bestimmt werden:

vπ(s)=aπ(as)s,rp(s,rs,a)(r+γvπ(s))v_\pi(s) = \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

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|S| linearen Gleichungen mit S|S| Unbekannten umformuliert werden.

Beispielsweise, wenn ein MDP 2 Zustände (s1s_1, s2s_2) und 2 Aktionen (Wechsel zu s1s_1, Wechsel zu s2s_2) hat, könnte die Zustandswertfunktion wie folgt definiert werden:

{V(s1)=0.5(5+0.9V(s1))+0.5(10+0.9V(s2))V(s2)=0.7(2+0.9V(s1))+0.3(0+0.9V(s2))\begin{cases} V(s_1) = 0.5 \cdot (5 + 0.9 \cdot V(s_1)) + 0.5 \cdot (10 + 0.9 \cdot V(s_2)) \\ V(s_2) = 0.7 \cdot (2 + 0.9 \cdot V(s_1)) + 0.3 \cdot (0 + 0.9 \cdot V(s_2)) \end{cases}

Dies kann mit Standardmethoden der linearen Algebra gelöst werden.

Eine eindeutige Lösung für ein solches lineares Gleichungssystem ist garantiert, wenn mindestens eine der folgenden Bedingungen erfüllt ist:

  • Der Diskontfaktor erfüllt γ<1γ < 1;
  • Die Politik π\pi stellt sicher, dass bei Befolgung aus jedem Zustand ss 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 mit der Zuweisung von beliebigen Anfangswerten für alle Zustände, außer für Endzustände, die auf 0 gesetzt werden. Die Werte werden dann iterativ mithilfe der Bellman-Gleichung als Aktualisierungsregel angepasst:

vk+1(s)aπ(as)s,rp(s,rs,a)(r+γvk(s))v_{k+1}(s) \gets \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_k(s')\Bigr)

Die geschätzte Zustandswertfunktion vkv_k konvergiert schließlich zu einer echten Zustandswertfunktion vπv_\pi, wenn kk \to \infty gilt, sofern vπv_\pi existiert.

Strategien zur Wert-Backup

Beim Aktualisieren von Wertschätzungen werden neue Schätzungen auf Basis vorheriger Werte berechnet. Der Prozess der Beibehaltung vorheriger Schätzungen wird als Backup bezeichnet. Es gibt zwei gängige Strategien zur Durchführung von Backups:

  • Vollständiges Backup: Diese Methode beinhaltet das Speichern der neuen Schätzungen in einem separaten Array, 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, zu dem der Algorithmus gestoppt werden sollte. Obwohl die Konvergenz im Grenzwert garantiert ist, sind weitere Berechnungen über einen bestimmten Punkt hinaus in der Praxis nicht notwendig. Ein einfaches und effektives Abbruchkriterium besteht darin, den absoluten Unterschied zwischen aufeinanderfolgenden Wertschätzungen, vk+1(s)vk(s)|v_{k+1}(s) - v_k(s)|, zu verfolgen und mit einem kleinen Schwellenwert θ\theta zu vergleichen. Wenn nach einem vollständigen Aktualisierungszyklus (bei dem die Werte für alle Zustände aktualisiert werden) keine Änderungen den Wert θ\theta überschreiten, kann der Prozess sicher beendet werden.

Pseudocode

question mark

Welche der folgenden Aussagen trifft auf die Methode der iterativen Politikauswertung zu?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 4
some-alt