Summary  
Value iteration is a dynamic programming method that repeatedly applies the Bellman optimality update to merge policy evaluation and policy improvement into a single step, directly converging to the optimal value function from which the optimal policy is derived.

General domain of usage  
Reinforcement learning

Obwohl **Policy Iteration** ein effektiver Ansatz zur Lösung von **MDPs** ist, weist sie einen erheblichen Nachteil auf: Jeder Iterationsschritt beinhaltet eine separate **Policy Evaluation**. Wird die **Policy Evaluation** **iterativ** durchgeführt, sind mehrere Durchläufe über den gesamten **State Space** erforderlich, was zu erheblichem Rechenaufwand und längeren Berechnungszeiten führt.

Eine gute Alternative ist die **Value Iteration**, eine Methode, die Policy Evaluation und Policy Improvement in einem **einzigen Schritt** zusammenführt. Diese Methode aktualisiert die Value Function direkt, bis sie zur **optimalen Value Function** konvergiert. Nach der Konvergenz kann die **optimale Policy** direkt aus dieser optimalen Value Function abgeleitet werden.

Die **Value Iteration** arbeitet, indem sie während der Policy Evaluation nur ein Backup durchführt, bevor die Policy Improvement erfolgt. Dies führt zur folgenden Aktualisierungsformel:

$$
v_{k+1}(s) \gets \max_a \sum_{s',r}p(s',r|s,a)\Bigl(r+\gamma v_k(s')\Bigr) \qquad \forall s \in S
$$

Durch die Umwandlung der Bellman-Optimalitätsgleichung in eine Aktualisierungsregel werden Policy Evaluation und Policy Improvement in einem einzigen Schritt zusammengeführt.

Basierend auf dem Pseudocode: Wann endet die Wertiteration?

Reinforcement Learning (RL) ist ein leistungsstarker Zweig des maschinellen Lernens, der sich auf das Training intelligenter Agenten durch Interaktion mit ihrer Umgebung konzentriert. In diesem Kurs lernen Sie, wie Agenten durch Versuch und Irrtum schrittweise effektive Verhaltensweisen entdecken. Beginnend mit grundlegenden Konzepten wie Markow-Entscheidungsprozessen und Multi-Armed Bandits arbeiten Sie sich durch dynamische Programmierung, Monte-Carlo-Methoden und Temporal-Difference-Lernen.

Erfahren Sie, wie Agenten durch Versuch und Irrtum optimale Entscheidungen treffen. Erkunden Sie die Grundlagen der Theorie des Reinforcement Learning. Praktische Erfahrung mit der Einrichtung und Ausführung einer Gymnasium-Umgebung.

Beherrschung des Erkundungs-Ausnutzungs-Dilemmas anhand des Multi-Armed-Bandit-Problems. Implementierung von Aktionswertschätzung, ε-gierigen, Upper-Confidence-Bound- und Gradient-Bandit-Methoden. Bewertung der Leistungsfähigkeit von Algorithmen bei simulierten Aufgaben zur Belohnungsmaximierung.

Dynamische Programmierung für modellbasiertes RL beherrschen. Entdecken, wie Bellman-Gleichungen zur Bewertung und Verbesserung von Policies eingesetzt werden können. Implementierung von Policy- und Value-Iteration-Algorithmen. Untersuchung der generalisierten Policy-Iteration als theoretische Grundlage für modellfreie Methoden.

Monte-Carlo-Methoden für modellfreies RL beherrschen.
Schätzverfahren für Wertfunktionen und Ableitung optimaler Politiken aus vollständigen Episoden.
Implementierung von On-Policy- und Off-Policy-Monte-Carlo-Kontrollalgorithmen.
Erkundungsstrategien zur Optimierung des modellfreien Lernens entdecken.

Beherrschung des Zeitdifferenzlernens für modellfreies RL. Schätzung von Wertfunktionen aus Teilfolgen mithilfe von TD(0)-Aktualisierungen. Implementierung der On-Policy-SARSA- und Off-Policy-Q-Learning-Algorithmen. Kombination von Monte-Carlo-Methoden und Zeitdifferenzlernen in n-Schritt-TD und TD(λ) entdecken.

Wertiteration

Funktionsweise

Pseudocode

Wertiteration

Funktionsweise

Pseudocode