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

bookPolitikverbesserung

Note
Definition

Politikverbesserung ist ein Prozess zur Verbesserung der Politik auf Grundlage aktueller Schätzungen der Wertfunktion.

Note
Hinweis

Wie bei der Politikevaluation kann die Politikverbesserung sowohl mit der Zustandswertfunktion als auch mit der Aktionswertfunktion arbeiten. Für DP-Methoden wird jedoch die Zustandswertfunktion verwendet.

Nachdem Sie nun die Zustandswertfunktion für eine beliebige Politik schätzen können, ist der nächste logische Schritt zu untersuchen, ob es Politiken gibt, die besser als die aktuelle sind. Eine Möglichkeit besteht darin, in einem Zustand ss eine andere Aktion aa zu wählen und anschließend der aktuellen Politik zu folgen. Falls dies bekannt vorkommt, liegt das daran, dass dies der Definition der Aktionswertfunktion ähnelt:

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Wenn dieser neue Wert größer ist als der ursprüngliche Zustandswert vπ(s)v_\pi(s), deutet dies darauf hin, dass das Ausführen der Aktion aa im Zustand ss und das anschließende Fortsetzen mit der Politik π\pi zu besseren Ergebnissen führt als das strikte Befolgen der Politik π\pi. Da die Zustände unabhängig sind, ist es optimal, immer die Aktion aa auszuwählen, sobald der Zustand ss erreicht wird. Daher kann eine verbesserte Politik π′\pi' konstruiert werden, die mit π\pi identisch ist, außer dass sie im Zustand ss die Aktion aa wählt, was der ursprünglichen Politik π\pi überlegen wäre.

Satz zur Politikverbesserung

Die oben beschriebene Argumentation kann als Satz zur Politikverbesserung generalisiert werden:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

Der Beweis dieses Theorems ist relativ einfach und kann durch eine wiederholte Substitution durchgeführt werden:

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Verbesserungsstrategie

Das Aktualisieren von Aktionen für bestimmte Zustände kann zu Verbesserungen führen, jedoch ist es effektiver, die Aktionen für alle Zustände gleichzeitig zu aktualisieren. Insbesondere wird für jeden Zustand ss die Aktion aa gewählt, die den Aktionswert qπ(s,a)q_\pi(s, a) maximiert:

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

wobei arg max⁡\argmax (Kurzform für Argument des Maximums) ein Operator ist, der den Wert der Variablen zurückgibt, der eine gegebene Funktion maximiert.

Die resultierende gierige Politik, bezeichnet als π′\pi', erfüllt durch ihre Konstruktion die Bedingungen des Policy-Improvement-Theorems und garantiert, dass π′\pi' mindestens so gut wie die ursprüngliche Politik π\pi ist und typischerweise besser.

Falls π′\pi' genauso gut wie, aber nicht besser als π\pi ist, sind sowohl π′\pi' als auch π\pi optimale Politiken, da ihre Wertfunktionen gleich sind und die Bellman-Optimalitätsgleichung erfüllen:

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

Wie garantiert die Übernahme einer gierigen Politik eine Verbesserung gegenüber der vorherigen Politik?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 5

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

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

Suggested prompts:

Can you explain the policy improvement theorem in simpler terms?

How does the greedy policy guarantee improvement over the original policy?

What is the Bellman optimality equation and why is it important?

Awesome!

Completion rate improved to 2.7

bookPolitikverbesserung

Swipe um das Menü anzuzeigen

Note
Definition

Politikverbesserung ist ein Prozess zur Verbesserung der Politik auf Grundlage aktueller Schätzungen der Wertfunktion.

Note
Hinweis

Wie bei der Politikevaluation kann die Politikverbesserung sowohl mit der Zustandswertfunktion als auch mit der Aktionswertfunktion arbeiten. Für DP-Methoden wird jedoch die Zustandswertfunktion verwendet.

Nachdem Sie nun die Zustandswertfunktion für eine beliebige Politik schätzen können, ist der nächste logische Schritt zu untersuchen, ob es Politiken gibt, die besser als die aktuelle sind. Eine Möglichkeit besteht darin, in einem Zustand ss eine andere Aktion aa zu wählen und anschließend der aktuellen Politik zu folgen. Falls dies bekannt vorkommt, liegt das daran, dass dies der Definition der Aktionswertfunktion ähnelt:

qπ(s,a)=∑s′,rp(s′,r∣s,a)(r+γvπ(s′))q_\pi(s, a) = \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)

Wenn dieser neue Wert größer ist als der ursprüngliche Zustandswert vπ(s)v_\pi(s), deutet dies darauf hin, dass das Ausführen der Aktion aa im Zustand ss und das anschließende Fortsetzen mit der Politik π\pi zu besseren Ergebnissen führt als das strikte Befolgen der Politik π\pi. Da die Zustände unabhängig sind, ist es optimal, immer die Aktion aa auszuwählen, sobald der Zustand ss erreicht wird. Daher kann eine verbesserte Politik π′\pi' konstruiert werden, die mit π\pi identisch ist, außer dass sie im Zustand ss die Aktion aa wählt, was der ursprünglichen Politik π\pi überlegen wäre.

Satz zur Politikverbesserung

Die oben beschriebene Argumentation kann als Satz zur Politikverbesserung generalisiert werden:

qπ(s,π′(s))≥vπ(s)∀s∈S  ⟹  vπ′(s)≥vπ(s)∀s∈S\begin{aligned} &q_\pi(s, \pi'(s)) \ge v_\pi(s) \qquad &\forall s \in S\\ \implies &v_{\pi'}(s) \ge v_\pi(s) \qquad &\forall s \in S \end{aligned}

Der Beweis dieses Theorems ist relativ einfach und kann durch eine wiederholte Substitution durchgeführt werden:

vπ(s)≤qπ(s,π′(s))=E⁡π′[Rt+1+γvπ(St+1)∣St=s]≤E⁡π′[Rt+1+γqπ(St+1,π′(St+1))∣St=s]=E⁡π′[Rt+1+γE⁡π′[Rt+2+γvπ(St+2)]∣St=s]=E⁡π′[Rt+1+γRt+2+γ2vπ(St+2)∣St=s]...≤E⁡π′[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=vπ′(s)\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s))\\ &= \E_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\\ &\le \E_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma \E_{\pi'}[R_{t+2} + \gamma v_\pi(S_{t+2})] | S_t = s]\\ &= \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) | S_t = s]\\ &...\\ &\le \E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= v_{\pi'}(s) \end{aligned}

Verbesserungsstrategie

Das Aktualisieren von Aktionen für bestimmte Zustände kann zu Verbesserungen führen, jedoch ist es effektiver, die Aktionen für alle Zustände gleichzeitig zu aktualisieren. Insbesondere wird für jeden Zustand ss die Aktion aa gewählt, die den Aktionswert qπ(s,a)q_\pi(s, a) maximiert:

π′(s)←arg max⁡aqπ(s,a)←arg max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\begin{aligned} \pi'(s) &\gets \argmax_a q_\pi(s, a)\\ &\gets \argmax_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

wobei arg max⁡\argmax (Kurzform für Argument des Maximums) ein Operator ist, der den Wert der Variablen zurückgibt, der eine gegebene Funktion maximiert.

Die resultierende gierige Politik, bezeichnet als π′\pi', erfüllt durch ihre Konstruktion die Bedingungen des Policy-Improvement-Theorems und garantiert, dass π′\pi' mindestens so gut wie die ursprüngliche Politik π\pi ist und typischerweise besser.

Falls π′\pi' genauso gut wie, aber nicht besser als π\pi ist, sind sowohl π′\pi' als auch π\pi optimale Politiken, da ihre Wertfunktionen gleich sind und die Bellman-Optimalitätsgleichung erfüllen:

vπ(s)=max⁡a∑s′,rp(s′,r∣s,a)(r+γvπ(s′))v_\pi(s) = \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr)
question mark

Wie garantiert die Übernahme einer gierigen Politik eine Verbesserung gegenüber der vorherigen Politik?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 5
some-alt