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

bookBellman-Gleichungen

Note
Definition

Eine Bellman-Gleichung ist eine Funktionalgleichung, die eine Wertfunktion in rekursiver Form definiert.

Zur Verdeutlichung der Definition:

  • Eine Funktionalgleichung ist eine Gleichung, deren Lösung eine Funktion ist. Bei der Bellman-Gleichung ist diese Lösung die Wertfunktion, für die die Gleichung formuliert wurde;
  • Eine rekursive Form bedeutet, dass der Wert im aktuellen Zustand in Bezug auf Werte in zukünftigen Zuständen ausgedrückt wird.

Kurz gesagt, das Lösen der Bellman-Gleichung liefert die gewünschte Wertfunktion, und die Herleitung dieser Gleichung erfordert die Identifikation einer rekursiven Beziehung zwischen aktuellen und zukünftigen Zuständen.

Zustandswertfunktion

Zur Erinnerung, hier ist eine Zustandswertfunktion in kompakter Form:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Um die Bellman-Gleichung für diese Wertfunktion zu erhalten, erweitern wir die rechte Seite der Gleichung und stellen eine rekursive Beziehung her:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

Die letzte Gleichung in dieser Kette ist eine Bellman-Gleichung für die Zustandswertfunktion.

Intuition

Um den Wert eines Zustands ss zu bestimmen:

  1. Berücksichtigung aller möglichen Aktionen aa, die von diesem Zustand aus durchgeführt werden können, gewichtet nach der Wahrscheinlichkeit, mit der diese Aktion gemäß der aktuellen Politik π(a∣s)\pi(a | s) gewählt wird;
  2. Für jede Aktion aa werden alle möglichen Folgezustände s′s' und Belohnungen rr betrachtet, gewichtet nach deren Wahrscheinlichkeit p(s′,r∣s,a)p(s', r | s, a);
  3. Für jedes dieser Ergebnisse wird die unmittelbare Belohnung rr plus der diskontierte Wert des nächsten Zustands γvπ(s′)\gamma v_\pi(s') addiert.

Durch das Aufsummieren all dieser Möglichkeiten ergibt sich der gesamte erwartete Wert des Zustands ss unter der aktuellen Politik.

Aktionswertfunktion

Hier ist eine Aktionswertfunktion in kompakter Form:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Die Herleitung der Bellman-Gleichung für diese Funktion ist der vorherigen sehr ähnlich:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

Die letzte Gleichung in dieser Kette ist eine Bellman-Gleichung für die Aktionswertfunktion.

Intuition

Um den Wert eines Zustands-Aktions-Paares (s,a)(s, a) zu bestimmen:

  1. Alle möglichen nächsten Zustände s′s' und Belohnungen rr betrachten, gewichtet nach ihrer Wahrscheinlichkeit p(s′,r∣s,a)p(s', r | s, a);
  2. Für jedes dieser Ergebnisse die unmittelbare Belohnung rr plus den diskontierten Wert des nächsten Zustands addieren;
  3. Um den Wert des nächsten Zustands s′s' zu berechnen, für alle möglichen Aktionen a′a' aus Zustand s′s' den Aktionswert q(s′,a′)q(s', a') mit der Wahrscheinlichkeit multiplizieren, a′a' im Zustand s′s' unter der aktuellen Politik π(a′∣s′)\pi(a' | s') zu wählen. Dann alles aufsummieren, um den endgültigen Wert zu erhalten.

Durch das Aufsummieren all dieser Möglichkeiten ergibt sich der gesamte erwartete Wert des Zustands-Aktions-Paares (s,a)(s, a) unter der aktuellen Politik.

question mark

Welche der folgenden Aussagen beschreibt die Funktion der Bellman-Gleichung am besten?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 2

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

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

Awesome!

Completion rate improved to 2.7

bookBellman-Gleichungen

Swipe um das Menü anzuzeigen

Note
Definition

Eine Bellman-Gleichung ist eine Funktionalgleichung, die eine Wertfunktion in rekursiver Form definiert.

Zur Verdeutlichung der Definition:

  • Eine Funktionalgleichung ist eine Gleichung, deren Lösung eine Funktion ist. Bei der Bellman-Gleichung ist diese Lösung die Wertfunktion, für die die Gleichung formuliert wurde;
  • Eine rekursive Form bedeutet, dass der Wert im aktuellen Zustand in Bezug auf Werte in zukünftigen Zuständen ausgedrückt wird.

Kurz gesagt, das Lösen der Bellman-Gleichung liefert die gewünschte Wertfunktion, und die Herleitung dieser Gleichung erfordert die Identifikation einer rekursiven Beziehung zwischen aktuellen und zukünftigen Zuständen.

Zustandswertfunktion

Zur Erinnerung, hier ist eine Zustandswertfunktion in kompakter Form:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Um die Bellman-Gleichung für diese Wertfunktion zu erhalten, erweitern wir die rechte Seite der Gleichung und stellen eine rekursive Beziehung her:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

Die letzte Gleichung in dieser Kette ist eine Bellman-Gleichung für die Zustandswertfunktion.

Intuition

Um den Wert eines Zustands ss zu bestimmen:

  1. Berücksichtigung aller möglichen Aktionen aa, die von diesem Zustand aus durchgeführt werden können, gewichtet nach der Wahrscheinlichkeit, mit der diese Aktion gemäß der aktuellen Politik π(a∣s)\pi(a | s) gewählt wird;
  2. Für jede Aktion aa werden alle möglichen Folgezustände s′s' und Belohnungen rr betrachtet, gewichtet nach deren Wahrscheinlichkeit p(s′,r∣s,a)p(s', r | s, a);
  3. Für jedes dieser Ergebnisse wird die unmittelbare Belohnung rr plus der diskontierte Wert des nächsten Zustands γvπ(s′)\gamma v_\pi(s') addiert.

Durch das Aufsummieren all dieser Möglichkeiten ergibt sich der gesamte erwartete Wert des Zustands ss unter der aktuellen Politik.

Aktionswertfunktion

Hier ist eine Aktionswertfunktion in kompakter Form:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Die Herleitung der Bellman-Gleichung für diese Funktion ist der vorherigen sehr ähnlich:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

Die letzte Gleichung in dieser Kette ist eine Bellman-Gleichung für die Aktionswertfunktion.

Intuition

Um den Wert eines Zustands-Aktions-Paares (s,a)(s, a) zu bestimmen:

  1. Alle möglichen nächsten Zustände s′s' und Belohnungen rr betrachten, gewichtet nach ihrer Wahrscheinlichkeit p(s′,r∣s,a)p(s', r | s, a);
  2. Für jedes dieser Ergebnisse die unmittelbare Belohnung rr plus den diskontierten Wert des nächsten Zustands addieren;
  3. Um den Wert des nächsten Zustands s′s' zu berechnen, für alle möglichen Aktionen a′a' aus Zustand s′s' den Aktionswert q(s′,a′)q(s', a') mit der Wahrscheinlichkeit multiplizieren, a′a' im Zustand s′s' unter der aktuellen Politik π(a′∣s′)\pi(a' | s') zu wählen. Dann alles aufsummieren, um den endgültigen Wert zu erhalten.

Durch das Aufsummieren all dieser Möglichkeiten ergibt sich der gesamte erwartete Wert des Zustands-Aktions-Paares (s,a)(s, a) unter der aktuellen Politik.

question mark

Welche der folgenden Aussagen beschreibt die Funktion der Bellman-Gleichung am besten?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 2
some-alt