Beginnen wir mit der Wiederholung eines bekannten Konzepts: der Zustandswertfunktion, bezeichnet als $v_\pi(s)$. Sie lässt sich wie folgt definieren:

Das Ziel in diesem Kapitel ist es, diese Funktion anhand von Daten zu schätzen, wobei eine feste Politik $\pi$ vorgegeben ist, jedoch kein Zugriff auf das Modell der Umgebung besteht.

Monte-Carlo-Schätzung

Monte-Carlo-Methoden nähern sich dieser Schätzaufgabe, indem sie Episoden von Erfahrungen unter der Politik $\pi$ sampeln und diese Stichproben zur empirischen Schätzung von $v_\pi(s)$ verwenden.

Im Allgemeinen lässt sich der Prozess in folgende Schritte unterteilen:

1. Generieren einer Episode mit der Politik $\pi$;
2. Speichern des erhaltenen Rückgabewerts für jeden Zustand, der in der Episode auftritt;
3. Wiederholen der Schritte 1-2 für eine bestimmte Zeit;
4. Berechnen der neuen Werte durch Mittelung der Rückgaben für jeden Zustand.

Sammeln der Rückgaben

Die Monte-Carlo-Schätzung der Wertfunktion erfordert das Sammeln der Rückgaben aus generierten Episoden. Zur Berechnung dieser Rückgaben können zwei Hauptansätze verwendet werden:

• First-visit: Für jeden Zustand $s$, der in einer Episode auftritt, wird nur die Rückgabe nach dem ersten Auftreten berücksichtigt. Weitere Vorkommen desselben Zustands innerhalb derselben Episode werden für Schätzungszwecke ignoriert;
• Every-visit: Jedes Vorkommen eines Zustands $s$ innerhalb einer Episode wird verwendet. Das heißt, die Rückgabe nach jedem Besuch des Zustands wird in die Schätzung einbezogen, auch wenn der Zustand mehrmals in derselben Episode erscheint.

Untersuchung von Starts

Stellen Sie sich eine einfache eindimensionale Welt vor, die durch eine Linie von -10 bis +10 dargestellt wird. Der Agent beginnt an Position 0, und seine aktuelle Strategie gibt vor, dass er bei jedem Zeitschritt immer nach rechts geht.

Wenn wir versuchen, unter dieser Strategie Episoden zu generieren, was passiert dann? Der Agent bewegt sich kontinuierlich zum positiven Ende der Linie – besucht Zustände wie 1, 2, 3 und so weiter – aber er wird niemals negative Zustände besuchen. Daher können wir keine Wertfunktionen für Zustände links vom Ursprung schätzen, einfach weil der Agent diese nie erlebt.

Das Hauptproblem ist also: Wenn bestimmte Bereiche des Zustandsraums nie erkundet werden, bleiben deren Wertschätzungen ungenau oder undefiniert. Eine gängige Lösung für dieses Problem ist der Einsatz von explorativen Starts.

Mit explorativen Starts beginnt jede Episode nicht in einem festen Startzustand wie 0, sondern in einem zufällig ausgewählten Zustand. Sobald die Episode beginnt, folgt der Agent wie gewohnt seiner aktuellen Strategie. Im Laufe der Zeit kann der Agent, indem er von vielen verschiedenen Punkten im Zustandsraum startet, alle Zustände besuchen – nicht nur diejenigen, zu denen ihn seine Strategie normalerweise führen würde. Dies ermöglicht es der Monte-Carlo-Methode, genauere und vollständigere Wertschätzungen für den gesamten Zustandsraum zu liefern.

Pseudocode

Dieser Pseudocode verwendet den Every-Visit-Ansatz zusammen mit Exploring Starts.