Summary  
This chapter covers incremental computation strategies for on-policy and off-policy Monte Carlo control, showing how to update action-value estimates online—using simple averaging for ordinary sampling and weighted updates for importance sampling—without storing full return histories.

General domain of usage  
Reinforcement learning

**Das Speichern jeder einzelnen Rückgabe** für jedes Zustand-Aktions-Paar kann den **Speicher schnell erschöpfen** und die **Rechenzeit erheblich erhöhen** – insbesondere in großen Umgebungen. Diese Einschränkung betrifft sowohl On-Policy- als auch Off-Policy-Monte-Carlo-Kontrollalgorithmen. Um dem entgegenzuwirken, werden **inkrementelle Berechnungsstrategien** verwendet, ähnlich wie bei Multi-Armed-Bandit-Algorithmen. Diese Methoden ermöglichen es, Wertschätzungen **dynamisch zu aktualisieren**, ohne vollständige Rückgabeverläufe zu speichern.

Für die On-Policy-Methode ähnelt die Aktualisierungsstrategie der Strategie, die in MAB-Algorithmen verwendet wird:
$$
Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a)) 
$$

wobei $$\displaystyle \alpha = \frac{1}{N(s, a)}$$ für die Mittelwertschätzung gilt. Die einzigen Werte, die gespeichert werden müssen, sind die aktuellen Schätzungen der Aktionswerte $$Q(s, a)$$ und die Anzahl der Besuche des Zustand-Aktions-Paares $$(s, a)$$, also $$N(s, a)$$.

Für das Off-Policy-Verfahren mit **gewöhnlichem Importance Sampling** bleibt alles wie beim On-Policy-Verfahren.

Eine interessantere Situation ergibt sich beim **gewichteten Importance Sampling**. Die Gleichung sieht gleich aus:
$$
Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a)) 
$$

aber $$\displaystyle \alpha = \frac{1}{N(s, a)}$$ kann nicht verwendet werden, weil:
1. Jede Rückgabe mit $$\rho$$ gewichtet wird;
2. Die endgültige Summe nicht durch $$N(s, a)$$, sondern durch $$\sum \rho(s, a)$$ geteilt wird.

Der Wert von $$\alpha$$, der in diesem Fall tatsächlich verwendet werden kann, entspricht $$\displaystyle \frac{W}{C(s,a)}$$, wobei:
- $$W$$ das $$\rho$$ für die aktuelle Trajektorie ist;
- $$C(s, a)$$ gleich $$\sum \rho(s, a)$$ ist.

Und jedes Mal, wenn das Zustand-Aktions-Paar $$(s, a)$$ auftritt, wird das $$\rho$$ der aktuellen Trajektorie zu $$C(s, a)$$ addiert:
$$
C(s, a) \gets C(s, a) + W
$$

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.

Inkrementelle Implementierungen

On-Policy-Monte-Carlo-Kontrolle

Pseudocode

Off-Policy Monte-Carlo-Kontrolle

Pseudocode