Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lernen Optimalitätsbedingungen | 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
Was ist RL?RL Im Vergleich Zu Anderen LernparadigmenMarkow-EntscheidungsprozessEpisoden und ErträgeModell, Politik und WerteErkundung vs. AusnutzungGrundlagen von GymnasiumHerausforderung: Einrichtung Einer Umgebung
2. Multi-Armed-Bandit-Problem
ProblemeinführungAktionswerteEpsilon-Greedy-AlgorithmusAlgorithmus der Oberen VertrauensgrenzeGradient-Banditen-AlgorithmusHerausforderung: Multi-Armed Bandits
3. Dynamische Programmierung
Was ist Dynamische Programmierung?Bellman-GleichungenOptimalitätsbedingungenPolitikbewertungPolitikverbesserungGeneralisierte PolitikiterationPolitikiterationWertiterationHerausforderung: Dynamische Programmierung
4. Monte-Carlo-Methoden
Was Sind Monte-Carlo-Methoden?Schätzung der WertfunktionMonte-Carlo-KontrolleErkundungsansätzeOn-Policy-Monte-Carlo-SteuerungOff-Policy-Monte-Carlo-KontrolleInkrementelle ImplementierungenHerausforderung: Monte-Carlo-Methoden
5. Temporal-Differenz-Lernen
Was ist Zeitdifferenzielles Lernen?TD(0): Schätzung der WertfunktionSARSA: On-Policy-TD-LernenQ-Learning: Off-Policy-TD-LernenVerallgemeinerung des TD-LernensHerausforderung: Temporal-Difference-Learning

book
Optimalitätsbedingungen

Im vorherigen Kapitel hast du die Bellman-Gleichungen für Zustandswert- und Zustands-Aktionswertfunktionen kennengelernt. Diese Gleichungen beschreiben, wie Zustandswerte rekursiv durch die Werte anderer Zustände definiert werden können, wobei die Werte von einer gegebenen Politik abhängen. Allerdings sind nicht alle Politiken gleichermaßen effektiv. Tatsächlich liefern Wertfunktionen eine partielle Ordnung für Politiken, die wie folgt beschrieben werden kann:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Eine Politik π\pi ist besser als oder gleichwertig zu einer Politik π′\pi', wenn für alle möglichen Zustände der erwartete Ertrag der Politik π\pi nicht geringer ist als der erwartete Ertrag der Politik π′\pi'.

Note
Mehr erfahren

Eine partielle Ordnung folgt den üblichen Ordnungsregeln, erzwingt jedoch nicht, dass jedes Paar verglichen werden muss. In unserem Fall können wir zwei Politiken nur dann einordnen, wenn sie die gleichen Ergebnisse liefern oder eine eindeutig besser ist als die andere. In allen anderen Fällen bleiben die Politiken nicht vergleichbar.

Optimale Politik

Note
Definition

Für jedes MDP existiert mindestens eine Politik, die genauso gut oder besser ist als alle anderen Politiken. Diese Politik wird als optimale Politik π∗\pi_* bezeichnet. Obwohl es viele optimale Politiken geben kann, werden alle mit π∗\pi_* bezeichnet.

Warum existiert immer eine optimale Politik?

Sie fragen sich vielleicht, warum für jedes MDP immer eine optimale Politik existiert. Das ist eine berechtigte Frage, und die dahinterstehende Intuition ist überraschend einfach. Denken Sie daran, dass Zustände in einem MDP den Zustand der Umgebung vollständig erfassen. Das bedeutet, dass jeder Zustand unabhängig von allen anderen ist: Die in einem Zustand gewählte Aktion beeinflusst nicht die Belohnungen oder Ergebnisse, die in einem anderen Zustand erreichbar sind. Daher gelangt man, indem man in jedem Zustand die optimale Aktion separat auswählt, ganz natürlich zur insgesamt besten Abfolge von Aktionen im gesamten Prozess. Und diese Menge optimaler Aktionen in jedem Zustand bildet eine optimale Politik.

Darüber hinaus gibt es immer mindestens eine Politik, die sowohl optimal als auch deterministisch ist. Tatsächlich gilt: Wenn für einen Zustand ss zwei Aktionen aa und a′a' den gleichen erwarteten Ertrag liefern, beeinflusst die Auswahl nur einer dieser Aktionen die Optimalität der Politik nicht. Wendet man dieses Prinzip auf jeden einzelnen Zustand an, wird die Politik deterministisch, während ihre Optimalität erhalten bleibt.

Optimale Wertfunktionen

Optimale Politiken teilen sich die gleichen Wertfunktionen — eine Tatsache, die deutlich wird, wenn wir betrachten, wie Politiken verglichen werden. Das bedeutet, dass optimale Politiken sowohl die Zustandswertfunktion als auch die Aktionswertfunktion gemeinsam haben.

Zusätzlich besitzen optimale Wertfunktionen eigene Bellman-Gleichungen, die ohne Bezug auf eine spezifische Politik formuliert werden können. Diese Gleichungen werden als Bellman-Optimalitätsgleichungen bezeichnet.

Optimale Zustandswertfunktion

Note
Definition

Optimale Zustandswertfunktion V∗V_* (oder v∗v_*) bezeichnet den maximal erwarteten Ertrag, der von einem bestimmten Zustand aus durch Befolgen einer optimalen Politik erreichbar ist.

Es kann mathematisch wie folgt definiert werden:

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

Bellman-Optimalitätsgleichung für diese Wertfunktion kann wie folgt hergeleitet werden:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Wie bereits bekannt, existiert immer mindestens eine Politik, die sowohl optimal als auch deterministisch ist. Eine solche Politik würde für jeden Zustand konsequent eine bestimmte Aktion auswählen, die den erwarteten Ertrag maximiert. Daher beträgt die Wahrscheinlichkeit, diese optimale Aktion zu wählen, stets 1, während die Wahrscheinlichkeit, jede andere Aktion zu wählen, 0 ist. Aus diesem Grund benötigt die ursprüngliche Bellman-Gleichung keinen Summenoperator mehr. Da immer die bestmögliche Aktion gewählt wird, kann die Summe einfach durch das Maximum über alle verfügbaren Aktionen ersetzt werden.

Optimale Aktionswertfunktion

Note
Definition

Optimale Aktionswertfunktion Q∗Q_* (oder q∗q_*) bezeichnet den maximal erwarteten Ertrag, der durch Ausführen einer bestimmten Aktion in einem bestimmten Zustand und anschließendes Befolgen der optimalen Strategie erreichbar ist.

Sie kann mathematisch wie folgt definiert werden:

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

Bellman-Optimalitätsgleichung für diese Wertfunktion kann wie folgt hergeleitet werden:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

Ähnlich wie bei der Zustandswertfunktion kann die Summe durch das Maximum über alle verfügbaren Aktionen ersetzt werden.

question mark

Warum existiert für jeden Markov-Entscheidungsprozess immer eine optimale Politik?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 3

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
Was ist RL?RL Im Vergleich Zu Anderen LernparadigmenMarkow-EntscheidungsprozessEpisoden und ErträgeModell, Politik und WerteErkundung vs. AusnutzungGrundlagen von GymnasiumHerausforderung: Einrichtung Einer Umgebung
2. Multi-Armed-Bandit-Problem
ProblemeinführungAktionswerteEpsilon-Greedy-AlgorithmusAlgorithmus der Oberen VertrauensgrenzeGradient-Banditen-AlgorithmusHerausforderung: Multi-Armed Bandits
3. Dynamische Programmierung
Was ist Dynamische Programmierung?Bellman-GleichungenOptimalitätsbedingungenPolitikbewertungPolitikverbesserungGeneralisierte PolitikiterationPolitikiterationWertiterationHerausforderung: Dynamische Programmierung
4. Monte-Carlo-Methoden
Was Sind Monte-Carlo-Methoden?Schätzung der WertfunktionMonte-Carlo-KontrolleErkundungsansätzeOn-Policy-Monte-Carlo-SteuerungOff-Policy-Monte-Carlo-KontrolleInkrementelle ImplementierungenHerausforderung: Monte-Carlo-Methoden
5. Temporal-Differenz-Lernen
Was ist Zeitdifferenzielles Lernen?TD(0): Schätzung der WertfunktionSARSA: On-Policy-TD-LernenQ-Learning: Off-Policy-TD-LernenVerallgemeinerung des TD-LernensHerausforderung: Temporal-Difference-Learning

book
Optimalitätsbedingungen

Im vorherigen Kapitel hast du die Bellman-Gleichungen für Zustandswert- und Zustands-Aktionswertfunktionen kennengelernt. Diese Gleichungen beschreiben, wie Zustandswerte rekursiv durch die Werte anderer Zustände definiert werden können, wobei die Werte von einer gegebenen Politik abhängen. Allerdings sind nicht alle Politiken gleichermaßen effektiv. Tatsächlich liefern Wertfunktionen eine partielle Ordnung für Politiken, die wie folgt beschrieben werden kann:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Eine Politik π\pi ist besser als oder gleichwertig zu einer Politik π′\pi', wenn für alle möglichen Zustände der erwartete Ertrag der Politik π\pi nicht geringer ist als der erwartete Ertrag der Politik π′\pi'.

Note
Mehr erfahren

Eine partielle Ordnung folgt den üblichen Ordnungsregeln, erzwingt jedoch nicht, dass jedes Paar verglichen werden muss. In unserem Fall können wir zwei Politiken nur dann einordnen, wenn sie die gleichen Ergebnisse liefern oder eine eindeutig besser ist als die andere. In allen anderen Fällen bleiben die Politiken nicht vergleichbar.

Optimale Politik

Note
Definition

Für jedes MDP existiert mindestens eine Politik, die genauso gut oder besser ist als alle anderen Politiken. Diese Politik wird als optimale Politik π∗\pi_* bezeichnet. Obwohl es viele optimale Politiken geben kann, werden alle mit π∗\pi_* bezeichnet.

Warum existiert immer eine optimale Politik?

Sie fragen sich vielleicht, warum für jedes MDP immer eine optimale Politik existiert. Das ist eine berechtigte Frage, und die dahinterstehende Intuition ist überraschend einfach. Denken Sie daran, dass Zustände in einem MDP den Zustand der Umgebung vollständig erfassen. Das bedeutet, dass jeder Zustand unabhängig von allen anderen ist: Die in einem Zustand gewählte Aktion beeinflusst nicht die Belohnungen oder Ergebnisse, die in einem anderen Zustand erreichbar sind. Daher gelangt man, indem man in jedem Zustand die optimale Aktion separat auswählt, ganz natürlich zur insgesamt besten Abfolge von Aktionen im gesamten Prozess. Und diese Menge optimaler Aktionen in jedem Zustand bildet eine optimale Politik.

Darüber hinaus gibt es immer mindestens eine Politik, die sowohl optimal als auch deterministisch ist. Tatsächlich gilt: Wenn für einen Zustand ss zwei Aktionen aa und a′a' den gleichen erwarteten Ertrag liefern, beeinflusst die Auswahl nur einer dieser Aktionen die Optimalität der Politik nicht. Wendet man dieses Prinzip auf jeden einzelnen Zustand an, wird die Politik deterministisch, während ihre Optimalität erhalten bleibt.

Optimale Wertfunktionen

Optimale Politiken teilen sich die gleichen Wertfunktionen — eine Tatsache, die deutlich wird, wenn wir betrachten, wie Politiken verglichen werden. Das bedeutet, dass optimale Politiken sowohl die Zustandswertfunktion als auch die Aktionswertfunktion gemeinsam haben.

Zusätzlich besitzen optimale Wertfunktionen eigene Bellman-Gleichungen, die ohne Bezug auf eine spezifische Politik formuliert werden können. Diese Gleichungen werden als Bellman-Optimalitätsgleichungen bezeichnet.

Optimale Zustandswertfunktion

Note
Definition

Optimale Zustandswertfunktion V∗V_* (oder v∗v_*) bezeichnet den maximal erwarteten Ertrag, der von einem bestimmten Zustand aus durch Befolgen einer optimalen Politik erreichbar ist.

Es kann mathematisch wie folgt definiert werden:

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

Bellman-Optimalitätsgleichung für diese Wertfunktion kann wie folgt hergeleitet werden:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Wie bereits bekannt, existiert immer mindestens eine Politik, die sowohl optimal als auch deterministisch ist. Eine solche Politik würde für jeden Zustand konsequent eine bestimmte Aktion auswählen, die den erwarteten Ertrag maximiert. Daher beträgt die Wahrscheinlichkeit, diese optimale Aktion zu wählen, stets 1, während die Wahrscheinlichkeit, jede andere Aktion zu wählen, 0 ist. Aus diesem Grund benötigt die ursprüngliche Bellman-Gleichung keinen Summenoperator mehr. Da immer die bestmögliche Aktion gewählt wird, kann die Summe einfach durch das Maximum über alle verfügbaren Aktionen ersetzt werden.

Optimale Aktionswertfunktion

Note
Definition

Optimale Aktionswertfunktion Q∗Q_* (oder q∗q_*) bezeichnet den maximal erwarteten Ertrag, der durch Ausführen einer bestimmten Aktion in einem bestimmten Zustand und anschließendes Befolgen der optimalen Strategie erreichbar ist.

Sie kann mathematisch wie folgt definiert werden:

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

Bellman-Optimalitätsgleichung für diese Wertfunktion kann wie folgt hergeleitet werden:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

Ähnlich wie bei der Zustandswertfunktion kann die Summe durch das Maximum über alle verfügbaren Aktionen ersetzt werden.

question mark

Warum existiert für jeden Markov-Entscheidungsprozess immer eine optimale Politik?

Select the correct answer

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 3
some-alt