W jaki sposób funkcje wartości wtórnych są definiowane matematycznie?

Question

W tej odpowiedzi , funkcje Wartość afterstate są wymienione, i że różnica czasowa-(TD) i Monte Carlo (MC) metody mogą również korzystać z tych funkcji wartości. Jak matematycznie zdefiniowano te funkcje wartości? Tak, są one funkcją następnego stanu, ale jakie jest tutaj równanie Bellmana? Czy jest po prostu zdefiniowany jako$v(s') = \mathbb{E}\left[ R_t \mid S_t = s, A_t = a, S_{t+1} = s' \right]$? Jeśli tak, jak możemy to zdefiniować w kategoriach stanu,$v(s)$i działania państwa, $q(s, a)$, funkcje wartości, czy jako (rekurencyjne) równanie Bellmana?

W książce Suttona i Barto (wydanie drugie) nieformalnie opisano funkcje wartości wtórnych w sekcji 6.8 , ale nie zawierają one formalnej definicji (tj. Równania Bellmana w kategoriach nagrody lub innych funkcji wartości), dlatego zadaję to pytanie.

Answer 1

Opierając się na tych i tych zasobach, pozwolę sobie odpowiedzieć na moje własne pytanie, ale zasadniczo przepiszę tutaj zawartość pierwszego zasobu, aby zapewnić powtarzalność, z niewielkimi zmianami w zapisie (aby był zgodny z Sutton & Książka Barto, wydanie 2). Zwróć uwagę, że nie jestem do końca pewien, czy to sformułowanie jest uniwersalne (tj. Może są inne sposoby jego sformułowania), ale zawartość pierwszego zasobu wydaje się być zgodna z treścią zasobu drugiego .

Ustawiać

Załóżmy, że mamy MDP o nieskończonym horyzoncie

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

• $\mathcal{S}$ jest zbiorem stanów
• $\mathcal{Y} \subseteq \mathcal{S}$jest zbiorem stanów następczych ( zwanych również stanami po decyzji lub stanami „końca okresu” [ 1 ], które można również zapisać jako stany następcze )
• $\mathcal{A}$ jest zbiorem działań
• $\mathcal{T}$ jest funkcją przejścia
• $\mathcal{R}$ jest funkcją nagrody
• $\gamma$ jest czynnikiem dyskontowym

Pozwolić

• $y \in \mathcal{Y}$ być postacią
• $f: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{Y}$być funkcją deterministyczną (od par stan-akcja do późniejszych stanów), więc mamy$f(s, a) = y$

Funkcja przejścia $\mathcal{T}$ dla $\mathcal{M}$ jest zdefiniowany jako

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

Przejście składa się z 2 kroków

1. krok deterministyczny, w którym stosujemy funkcję deterministyczną $f(s, a) = y$, co zależy od działania $a$ podjęte w stanie $s$, śledzony przez
2. krok stochastyczny, w którym stosujemy rozkład prawdopodobieństwa $P (s^{\prime} \mid y)$, która nie zależy od akcji $a$ już, ale tylko dalej $y$

Więc oznaczyłem kolejne stany inną literą, $y$, ponieważ następstwa osiągane są z funkcją deterministyczną $f$podczas gdy inne państwa $s$ lub $s'$, są osiągane za pomocą $P$.

Po podjęciu działania $a$ w stanie $s$, otrzymujemy nagrodę (tj. otrzymujemy nagrodę w kroku 1), ale nie otrzymujemy nagrody po kroku stochastycznym (zakładając, że nie jest podejmowane żadne działanie).

Więc możemy zdefiniować funkcję nagrody $\mathcal{R}$ dla tego MDP w następujący sposób

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

Sytuację ilustruje poniższy diagram

Więc tu, $P$jest stochastyczną funkcją przejścia (tj. rozkładem prawdopodobieństwa), jak zastosowano powyżej. Zwróć uwagę, że tutaj$r_t$ jest specyficzną realizacją $R_t$ (zmienna losowa) we wzorach poniżej.

Funkcja wartości stanu

Przypomnijmy definicję funkcji wartości stanu $v_\pi(s)$ dla danej polisy $\pi$ (zgodnie z definicją w Sutton & Barto, sekcja 3.5)

\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} dla wszystkich $s \in \mathcal{S}$ i

\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} gdzie $\pi(s_t) = a_t$ i $\mathcal{R}(s_t, a_t) = R_{t+1}$, dla $t=0, 1, 2, \dots$. (Więc zwróć uwagę$\mathcal{R} \neq R_t$: pierwsza to funkcja nagrody, a druga to zmienna losowa reprezentująca nagrodę otrzymaną po wykonaniu działania $a_t$ w takt $s_t$)

Funkcja optymalna wartość stanu jest zdefiniowany jako

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

Funkcja wartości wtórnej

Podobnie zdefiniujemy funkcję wartości afterstate, ale użyjemy litery $w$ żeby to odróżnić $v$ i $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} gdzie $\mathcal{R}(s_{t+1}, a_{t+1}) = R_{t+2}$, dla wszystkich $t$.

Innymi słowy, wartość afterstate $y$ (w czasie krok $t$, czyli dane $Y_t = y$) definiuje się jako oczekiwanie zwrotu, począwszy od stanu, w którym znalazłeś się po stanie końcowym$y$.

Wydaje mi się to rozsądne i jest podobne do mojej propozycji definicji funkcji wartości wtórnej w pytaniu, chociaż nie rozważałem żadnych funkcji deterministycznych w ujęciu potencjalnym, a także nie myślałem o stanach wtórnych jako o stanach pośrednich , do których deterministyczny krok pomiędzy zwykłymi stanami.

Podobnie jak w przypadku funkcji optymalnej wartości stanu, definiujemy również optymalną funkcję wartości wtórnej

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

Funkcja wartości wtórnej zdefiniowana w postaci funkcji wartości stanu

Możemy zdefiniować funkcję wartości afterstate w terminach

$$ w_{*}(y) = \sum_{s^{\prime}} P (s^{\prime} \mid y ) v_{*} ( s^{\prime} ) $$ Innymi słowy, $w_{*}(y)$ definiuje się jako oczekiwanie względem wartości kolejnych możliwych stanów $s'$ z końca $y$.

Wydaje się, że jest to poprawne i zgodne z powyższymi definicjami.

Więcej równań

W tych i tych zasobach funkcja wartości stanu jest również zdefiniowana w kategoriach funkcji wartości wtórnej w następujący sposób

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

Równanie Bellmana do afterstate funkcji wartości (z których zasada zmiana może pochodzić) jest podana

$$ w_{*}(y) = \sum_{s^{\prime}} P(s^{\prime} \mid y ) \max_{a} ( \mathcal{R} (s^{\prime}, a) + \gamma w_{*}(f ( s^{\prime}, a ))), $$ co jest naprawdę podobne do równania Bellmana dla funkcji wartości stanu.

Wreszcie, możemy również wyrazić funkcję wartości działania stanu w terminach funkcji wartości po stanie

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

Biorąc pod uwagę, że ta odpowiedź jest już dość długa, zapoznaj się z zasobem, aby uzyskać więcej informacji (w tym algorytm oparty na równaniu Bellmana po stanie końcowym).

Realizacja

Jeśli jesteś typem osoby, która rozumie pojęcia, patrząc na kod, ten projekt Github , który implementuje metodę Monte Carlo, która używa afterstates do gry w kółko i krzyżyk, może być przydatny. Afterstates są przydatne w grze „kółko i krzyżyk”, ponieważ jest to gra 2-osobowa, w której dwóch agentów wykonuje kolejno akcje, dzięki czemu możemy oszacować akcję, którą należy podjąć w sposób deterministyczny (tak, jakby to był$f$ powyżej), zanim drugi agent podejmie działanie (prawdopodobnie), przynajmniej taka jest moja aktualna interpretacja przydatności wtórnych stanów w tej grze (i podobnych grach / problemach).