TD(0): Schätzung der Wertfunktion

Die einfachste Version des TD-Lernens wird als TD(0) bezeichnet. Sie aktualisiert den Wert eines Zustands basierend auf der unmittelbaren Belohnung und dem geschätzten Wert des nächsten Zustands. Es handelt sich um eine Ein-Schritt-TD-Methode.

Aktualisierungsregel

Gegeben sei ein Zustand $S_t$, eine Belohnung $R_{t+1}$ und der nächste Zustand $S_{t+1}$. Die Aktualisierungsregel lautet:

wobei

• $\alpha$ die Lernrate bzw. Schrittweite ist;
• $\delta_t = R_{t+1}+\gamma V(S_{t+1}) - V(S_t)$ der TD-Fehler ist.

Intuition

Die Zustandswertfunktion $v_\pi$ kann wie folgt definiert und erweitert werden:

Dies ergibt den ersten Teil von $\delta_t$ — die erfahrene Rückgabe $R_{t+1} + \gamma V(S_{t+1})$. Der zweite Teil von $\delta_t$ ist die erwartete Rückgabe $V(S_t)$. Der TD-Fehler $\delta_t$ ist somit die beobachtbare Abweichung zwischen dem, was tatsächlich passiert ist, und dem, was zuvor angenommen wurde. Die Aktualisierungsregel passt daher die bisherige Annahme bei jedem Schritt etwas an und bringt sie näher an die Wahrheit.

TD(0) vs Monte-Carlo-Schätzung

Sowohl TD(0) als auch die Monte-Carlo-Schätzung verwenden gesampelte Erfahrungen, um die Zustandswertfunktion $v_\pi(s)$ für eine Politik $\pi$ zu schätzen. Unter den üblichen Konvergenzbedingungen konvergieren beide Methoden gegen das wahre $v_\pi(s)$, wenn die Anzahl der Besuche jedes Zustands gegen unendlich geht. In der Praxis steht jedoch nur eine endliche Datenmenge zur Verfügung, und die beiden Methoden unterscheiden sich erheblich darin, wie sie diese Daten nutzen und wie schnell sie lernen.

Bias-Varianz-Abwägung

Aus der Perspektive des Bias-Varianz-Abwägung:

Monte-Carlo-Schätzung wartet bis zum Ende einer Episode und verwendet dann die vollständige Rückgabe, um Werte zu aktualisieren. Dies liefert unverzerrte Schätzungen – die Rückgaben spiegeln tatsächlich die zugrunde liegende Verteilung wider – aber sie können stark schwanken, insbesondere bei langen oder stark stochastischen Aufgaben. Hohe Varianz bedeutet, dass viele Episoden erforderlich sind, um das Rauschen auszugleichen und stabile Wertschätzungen zu erhalten.

TD(0) bootstrapped, indem jede Ein-Schritt-Belohnung mit der aktuellen Schätzung des Werts des nächsten Zustands kombiniert wird. Dies führt zu Bias – frühe Aktualisierungen basieren auf unvollständigen Schätzungen – hält jedoch die Varianz niedrig, da jede Aktualisierung auf einem kleinen, inkrementellen Fehler basiert. Niedrigere Varianz ermöglicht es TD(0), Belohnungsinformationen schneller durch den Zustandsraum zu propagieren, auch wenn anfänglicher Bias die Konvergenz verlangsamen kann.

Lerndaten vs Lernmodell

Eine weitere Möglichkeit, diese beiden Methoden zu betrachten, besteht darin, zu analysieren, was jede von ihnen tatsächlich lernt:

Monte-Carlo-Schätzung lernt direkt aus den beobachteten Rückgaben und passt ihre Wertschätzungen effektiv an die spezifischen Episoden an, die sie gesehen hat. Das bedeutet, dass sie den Fehler auf diesen Trainingsverläufen minimiert. Da jedoch nie eine explizite Sicht darauf aufgebaut wird, wie Zustände miteinander verbunden sind, kann es schwierig sein, auf neue oder leicht abweichende Situationen zu verallgemeinern.

TD(0) hingegen bootstrapped bei jedem Ein-Schritt-Übergang, indem es die unmittelbare Belohnung mit seiner Schätzung des Werts des nächsten Zustands kombiniert. Dadurch werden die Beziehungen zwischen den Zuständen effektiv erfasst – ein implizites Modell der Dynamik der Umgebung. Dieses modellähnliche Verständnis ermöglicht es TD(0), besser auf unbekannte Übergänge zu verallgemeinern und oft genauere Wertschätzungen für neue Daten zu liefern.

Pseudocode