Was genau ist Bootstrapping beim Reinforcement-Lernen?

Offensichtlich handelt es sich beim Verstärkungslernen bei der Zeitdifferenzmethode (TD-Methode) um eine Bootstrapping-Methode. Andererseits sind Monte-Carlo-Methoden keine Bootstrapping-Methoden.

Was genau ist Bootstrapping in RL? Was ist eine Bootstrapping-Methode in RL?

Bootstrapping in RL kann als "unter Verwendung eines oder mehrerer geschätzter Werte im Aktualisierungsschritt" gelesen werden für dieselbe Art von Schätzwert" .

In den meisten TD-Update-Regeln sehen Sie so etwas wie dieses SARSA (0) -Update:

Der Wert $R_{t+1} + \gamma Q(s',a')$ ist eine Schätzung für den wahren Wert von $Q(s,a)$ und wird auch als TD-Ziel bezeichnet. Dies ist eine Bootstrap-Methode, da wir teilweise einen Q-Wert verwenden, um einen anderen Q-Wert zu aktualisieren. Es gibt eine kleine Menge real beobachteter Daten in Form von $R_{t+1}$ , der unmittelbaren Belohnung für den Schritt, und auch im Zustandsübergang $s \rightarrow s'$ .

Im Gegensatz zu Monte Carlo könnte die entsprechende Aktualisierungsregel lauten:

Wobei $G_{t}$ die gesamte abgezinste Belohnung zum Zeitpunkt $t$ , unter der Annahme, dass es in Status $s$ begann, Aktion $a$ ausführte und dann der aktuellen Richtlinie bis zum Ende der Episode folgte. Technisch ist $G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$ wobei$T$ist der Zeitschritt für die endgültige Belohnung und den endgültigen Status. Insbesondere verwendet dieser Zielwert überhaupt keine vorhandenen Schätzungen (aus anderen Q-Werten), sondern nur eine Reihe von Beobachtungen (dh Belohnungen) aus der Umgebung. Somit ist garantiert, dass es sich um eine unvoreingenommene Schätzung des wahren Werts von $Q(s,a)$ , da es sich technisch um eine Stichprobe von $Q(s,a)$ .

Der Hauptnachteil von Bootstrapping ist, dass es in Richtung Ihrer Startwerte von $Q(s',a')$ (oder $V(s')$ ) voreingenommen ist. Diese sind höchstwahrscheinlich falsch, und das Aktualisierungssystem kann insgesamt instabil sein, da zu viel Selbstreferenz und nicht genügend reale Daten vorhanden sind. Dies ist ein Problem beim Lernen außerhalb der Richtlinien (z. B. Q-Learning) mithilfe neuronaler Netze.

Ohne Bootstrapping gibt es bei längeren Trajektorien häufig eine hohe Varianz , was in der Praxis bedeutet, dass Sie mehr Stichproben benötigen, bevor die Schätzungen konvergieren. Daher kann es trotz der Probleme mit dem Bootstrapping deutlich schneller lernen, wenn es zum Laufen gebracht werden kann, und es wird häufig Monte-Carlo-Ansätzen vorgezogen.

Sie können Kompromisse zwischen beprobten Monte-Carlo-Methoden und Einzelschritt-TD-Methoden eingehen, indem Sie eine Mischung von Ergebnissen aus Trajektorien unterschiedlicher Länge verwenden. Dies wird als TD ( $\lambda$ ) -Lernen bezeichnet, und es gibt eine Vielzahl spezifischer Methoden wie SARSA ( $\lambda$ ) oder Q ( $\lambda$ ).

In general, bootstrapping in RL means that you update a value based on some estimates and not on some exact values. E.g.

Incremental Monte Carlo Policy Evaluation updates:

$V(S_t) = V(S_t) + \alpha(G_t - V(S_t))$

TD(0) Policy Evaluation updates:

$V(S_t) = V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(S_t))$

In TD(0), the return starting from state $s$ is estimated (bootstrapped) by $R_{t+1} + \gamma V(S_{t+1})$ while in MC we use the exact return $G_t$.