Das Speichern jeder 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.

On-Policy-Monte-Carlo-Kontrolle

Für die On-Policy-Methode ähnelt die Aktualisierungsstrategie der Strategie, die in MAB-Algorithmen verwendet wird:

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)$.

Pseudocode

Off-Policy Monte-Carlo-Kontrolle

Für die Off-Policy-Methode mit gewöhnlichem Importance Sampling bleibt alles wie bei der On-Policy-Methode.

Eine interessantere Situation ergibt sich beim gewichteten Importance Sampling. Die Gleichung sieht gleich aus:

aber $\displaystyle \alpha = \frac{1}{N(s, a)}$ kann nicht verwendet werden, weil:

1. Jede Rückgabe mit $\rho$ gewichtet wird;
2. Die abschließende 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, ist gleich $\displaystyle \frac{W}{C(s,a)}$, wobei:

• $W$ ein $\rho$ für die aktuelle Trajektorie ist;
• $C(s, a)$ gleich $\sum \rho(s, a)$ ist.

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

Pseudocode