Wie werden Afterstate-Value-Funktionen mathematisch definiert?

Question

In dieser Antwort werden Nachzustandswertfunktionen erwähnt, und dass Zeitdifferenz- (TD) und Monte-Carlo- (MC) Methoden auch diese Wertfunktionen verwenden können. Wie sind diese Wertefunktionen mathematisch definiert? Ja, sie sind eine Funktion des nächsten Zustands, aber wie lautet die Bellman-Gleichung hier? Ist es einfach definiert als$v(s') = \mathbb{E}\left[ R_t \mid S_t = s, A_t = a, S_{t+1} = s' \right]$? Wenn ja, wie können wir es in Bezug auf den Staat definieren?$v(s)$und staatliche Aktion, $q(s, a)$, Wertfunktionen oder als Bellman (rekursive) Gleichung?

Das Buch von Sutton & Barto (2. Auflage) beschreibt informell Afterstate-Value-Funktionen in Abschnitt 6.8, bietet jedoch keine formale Definition (dh Bellman-Gleichung in Bezug auf Belohnung oder andere Wertfunktionen). Deshalb stelle ich diese Frage.

Answer 1

Lassen Sie mich auf der Grundlage dieser und dieser Ressourcen eine Antwort auf meine eigene Frage geben, aber im Wesentlichen werde ich den Inhalt der ersten Ressource hier aus Gründen der Reproduzierbarkeit mit einigen geringfügigen Änderungen an der Notation neu schreiben (um mit Sutton & übereinzustimmen) Bartos Buch, 2. Auflage). Beachten Sie, dass ich nicht ganz sicher bin, ob diese Formulierung universell ist (dh es gibt möglicherweise andere Möglichkeiten, sie zu formulieren), aber der Inhalt der ersten Ressource scheint mit dem Inhalt der zweiten Ressource übereinzustimmen .

Konfiguration

Nehmen wir an, wir haben ein MDP mit unendlichem Horizont

$$\mathcal{M} = (\mathcal{S}, \mathcal{Y}, \mathcal{A}, \mathcal{T}, \mathcal{R}, \gamma),$$ wo

• $\mathcal{S}$ ist die Menge der Zustände
• $\mathcal{Y} \subseteq \mathcal{S}$die Menge ist afterstates (auch bekannt als post-Entscheidungs Zustände oder „Ende der Periode“ Zustände [ 1 ], die auch als geschrieben werden kann afterstates )
• $\mathcal{A}$ ist die Menge der Aktionen
• $\mathcal{T}$ ist die Übergangsfunktion
• $\mathcal{R}$ ist die Belohnungsfunktion
• $\gamma$ ist ein Abzinsungsfaktor

Lassen

• $y \in \mathcal{Y}$ ein Nachzustand sein
• $f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$eine deterministische Funktion sein (von State-Action-Paaren bis zu Afterstates), also haben wir$f(s, a) = y$

Die Übergangsfunktion $\mathcal{T}$ zum $\mathcal{M}$ ist definiert als

\begin{align} \mathcal{T}(s, a, s^{\prime}) &\doteq P ( s^{\prime} \mid f(s, a)) \\ &= P ( s^{\prime} \mid y) \end{align}

Ein Übergang besteht aus 2 Schritten

1. Ein deterministischer Schritt, bei dem wir die deterministische Funktion anwenden $f(s, a) = y$, was von einer Aktion abhängt $a$ im Staat genommen $s$, gefolgt von
2. Ein stochastischer Schritt, bei dem wir die Wahrscheinlichkeitsverteilung anwenden $P (s^{\prime} \mid y)$, was nicht von der Aktion abhängt $a$ mehr, aber nur noch $y$

Also habe ich Afterstates mit einem anderen Buchstaben bezeichnet, $y$, weil Nachzustände mit einer deterministischen Funktion erreicht werden $f$, während andere Staaten, $s$ oder $s'$sind erreicht mit $P$.

Nachdem Sie die Aktion ausgeführt haben $a$ im Staat $s$Wir erhalten eine Belohnung (dh wir erhalten eine Belohnung in Schritt 1), aber wir erhalten nach dem stochastischen Schritt keine Belohnung (vorausgesetzt, es werden keine Maßnahmen ergriffen).

So können wir die Belohnungsfunktion definieren $\mathcal{R}$ für dieses MDP wie folgt

$$ \mathcal{R} (s, a, s^{\prime} ) \doteq \mathcal{R}(s, a) $$

Die Situation wird durch das folgende Diagramm veranschaulicht

Also hier $P$ist die oben verwendete stochastische Übergangsfunktion (dh eine Wahrscheinlichkeitsverteilung). Beachten Sie, dass hier$r_t$ ist eine spezifische Realisierung von $R_t$ (die Zufallsvariable) in den folgenden Formeln.

Zustandswertfunktion

Erinnern wir uns an die Definition der Zustandswertfunktion $v_\pi(s)$ für eine bestimmte Politik $\pi$ (wie in Sutton & Barto, Abschnitt 3.5 definiert)

\begin{align} v_{\pi}(s) &\doteq \mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right] \\ &= \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \mid S_{t}=s\right], \end{align} für alle $s \in \mathcal{S}$ und

\begin{align} G_{t} &\doteq \sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \\ &= R_{t+1} + \gamma R_{t+2} + \gamma^{2} R_{t+3}+ \cdots \\ &= \mathcal{R}(s_t, a_t) + \gamma \mathcal{R}(s_{t+1}, a_{t+1})+\gamma^{2} \mathcal{R}(s_{t+2}, a_{t+2}) +\cdots, \end{align} wo $\pi(s_t) = a_t$ und $\mathcal{R}(s_t, a_t) = R_{t+1}$, zum $t=0, 1, 2, \dots$. (Beachten Sie also, dass$\mathcal{R} \neq R_t$: Die erste ist die Belohnungsfunktion, während die zweite eine Zufallsvariable ist, die die Belohnung darstellt, die nach dem Ergreifen von Maßnahmen erhalten wurde $a_t$ im Schritt $s_t$)

Die optimale Zustandswertfunktion ist definiert als

$$ v_{*}(s) \doteq \max _{\pi} v_{\pi}(s) $$

Afterstate-Wertfunktion

In ähnlicher Weise werden wir die Afterstate-Wertfunktion definieren, aber wir werden den Buchstaben verwenden $w$ nur um es zu unterscheiden $v$ und $q$.

\begin{align} w_{\pi}\left(y\right) &\doteq \mathbb{E}_{\pi}\left[G_{t+1} \mid Y_{t}=y\right] \\ &= \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+2} \mid Y_{t}=y\right] \\ &= \mathbb{E}_{\pi}\left[ R_{t+2} + \gamma R_{t+3}+\gamma^{2} R_{t+4} + \cdots \mid Y_{t}=y\right] \\ &= \mathbb{E}_{\pi}\left[ \mathcal{R}(s_{t+1}, a_{t+1})+\gamma \mathcal{R}(s_{t+2}, a_{t+2}) + \gamma^{2} \mathcal{R}(s_{t+3}, a_{t+3}) + \cdots \mid Y_{t}=y\right] , \end{align} wo $\mathcal{R}(s_{t+1}, a_{t+1}) = R_{t+2}$, für alle $t$.

Mit anderen Worten, der Wert eines Nachzustands $y$ (zum Zeitschritt $t$dh gegeben $Y_t = y$) ist definiert als die Erwartung der Rückkehr ab dem Zustand, in dem Sie nach dem Nachzustand gelandet sind$y$.

Dies erscheint mir vernünftig und ähnelt meinem Vorschlag zur Definition der Afterstate-Value-Funktion in der Frage, obwohl ich in einer möglichen Formulierung keine deterministischen Funktionen berücksichtigte und Afterstates auch nicht als Zwischenzustände betrachtete , die von erreicht wurden ein deterministischer Schritt zwischen den üblichen Zuständen.

Ähnlich wie bei der optimalen Zustandswertfunktion definieren wir auch die optimale Nachzustandswertfunktion

$$ w_{*}(y) \doteq \max _{\pi} w_{\pi}(y) $$

Afterstate-Wertfunktion, definiert als Zustandswertfunktion

Wir können die Afterstate-Value-Funktion in Begriffen definieren

$$ w_{*}(y) = \sum_{s^{\prime}} P (s^{\prime} \mid y ) v_{*} ( s^{\prime} ) $$ Mit anderen Worten, $w_{*}(y)$ ist definiert als eine Erwartung über den Wert der nächsten möglichen Zustände $s'$ aus dem Nachzustand $y$.

Dies scheint korrekt zu sein und mit den obigen Definitionen übereinzustimmen.

Weitere Gleichungen

In dieser und dieser Ressource wird die Zustandswertfunktion auch in Bezug auf die Nachzustandswertfunktion wie folgt definiert

$$v_{*}(s)=\max_{a}\left(\mathcal{R}(s, a)+\gamma w_{*}(f(s, a))\right)$$

Die Bellman-Gleichung für die Nachzustandswertfunktion (aus der eine Aktualisierungsregel abgeleitet werden kann) ist gegeben durch

$$ w_{*}(y) = \sum_{s^{\prime}} P(s^{\prime} \mid y ) \max_{a} ( \mathcal{R} (s^{\prime}, a) + \gamma w_{*}(f ( s^{\prime}, a ))), $$ Das ist der Bellman-Gleichung für die Zustandswertfunktion sehr ähnlich.

Schließlich können wir die State-Action-Value-Funktion auch als Afterstate-Value-Funktion ausdrücken

$$ q_\pi(s_t, a_t) = \mathcal{R}\left(s_{t}, a_{t}\right)+\gamma w_{\pi}\left(f\left(s_{t}, a_{t}\right)\right) $$

Da diese Antwort bereits ziemlich lang ist, finden Sie weitere Informationen in der Ressource (einschließlich eines Algorithmus, der auf der Bellman-Gleichung nach dem Zustand basiert).

Implementierung

Wenn Sie der Typ sind, der die Konzepte anhand des Codes versteht, kann dieses Github-Projekt nützlich sein, das eine Monte-Carlo-Methode implementiert, bei der Afterstates zum Spielen von Tic-Tac-Toe verwendet werden. Afterstates sind in Tic-Tac-Toe nützlich, da es sich um ein 2-Spieler-Spiel handelt, bei dem zwei Agenten nacheinander Aktionen ausführen, sodass wir die Aktion abschätzen können, die Sie deterministisch ausführen sollten (als ob es das wäre$f$ oben), bevor der andere Agent (wahrscheinlich) eine Aktion ausführt, ist dies zumindest meine aktuelle Interpretation der Nützlichkeit von Nachzuständen in diesem Spiel (und ähnlichen Spielen / Problemen).