Podstawy procesów decyzyjnych Markova

[leg14]

Czytam troche o PDM i jest tam tzw równanie Bellmana. Czyli \(\displaystyle{ V(S_t) = \EE(R_{t+1} + \gamma \cdot V(S_{t+1})|S_t )}\) (np. tu ... s/0429.pdf na stronie 4). W

Kod: Zaznacz cały

https://www.youtube.com/watch?v=lfHX2hHRMVQ

typek mówi, że to wynika z "law of iterated expectations". Sprawdziłem co się kryje pod tą straszną nazwą i okazuje się, że chodzi o równość \(\displaystyle{ \EE(\EE(X|Y)) = \EE(X)}\). No ale w tej niesmowitej równości Bellmana mamy równość \(\displaystyle{ \EE(\EE(G_{t+1}|S_{t+1}|S_t)) = \EE(G_{t+1}|S_t)}\). Skąd to się bierze? (nie mamy założenia przecież, że \(\displaystyle{ \sigma(S_t) \subset sigma(S_{t+1})}\) lub na odwrót ).

[Igor V]

\(\displaystyle{ \EE(\EE(G_{t+1}|S_{t+1}|S_t)) = \EE(G_{t+1}|S_t)}\)

A nie :
\(\displaystyle{ \EE(\EE{\red (}G_{t+1}|S_{t+1}{\red )}|S_t) = \EE(G_{t+1}|S_t)}\) ?

Skąd to się bierze?

Z własności Markowa - wartości funkcji wzmocnienia i przejść zależą tylko od aktualnego stanu i akcji.

[leg14]

Igor V, znasz jakieś fajne źródło na ten temat?





Nie no nie rozumiem. Na razie mamy proces decyzyjny bez akcji. Mamy zmienne losowe \(\displaystyle{ R_t}\) - nagroda w czasie t i wiemy, że \(\displaystyle{ \EE(R_{t+1}|S_t=s) =r_s}\) (czyli to nie zależy od czasu). \(\displaystyle{ G_t = R_{t+1} +\gamma R_{t+2}+\gamma^2 R_{t+3} +...}\). Próbujemy pokazać, że \(\displaystyle{ \EE(\EE(R_{t+2}|S_{t+1})|S_t=s) = \EE(R_{t+2}|S_t=s)}\).

\(\displaystyle{ \EE(\EE(R_{t+2}|S_{t+1})|S_t=s)= \EE( \sum_{s'}^{} \EE(R_{t+2}|S_{t+1}=s')\11_{S_{t+1}=s'}|S_t=s)=\EE \sum_{s'}^{} r_{s'}\11_{S_{t+1}=s'}|S_t=s)= \sum_{s'}^{}r_{s'}p_{s,s'}}\)
Wygląda obiecująco, ale musimy wiedzieć ile wynosi \(\displaystyle{ \EE(R_{t+2} \cdot1_{S_{t+1}=s'} \cdot 1_{s_t =s})}\). Jak to policzyć?

[Igor V]

Igor V, znasz jakieś fajne źródło na ten temat?

Na temat procesów Markowa ? Stricte nie, swoją wiedzę czerpałem głównie z takiego przedmiotu Uczenie się maszyn, który robiłem jakiś czas temu i książki do niego. Plus internet ofc.

Próbujemy pokazać, że \(\displaystyle{ \EE(\EE(R_{t+2}|S_{t+1})|S_t=s) = \EE(R_{t+2}|S_t=s)}\).

Raczej (bo patrzysz z punktu widzenia obecnego stanu na następny):

\(\displaystyle{ \EE(\EE{\red (}G_{t+1}|S_{t+1}{\red )}|S_t) = \EE(G_{t+1}|S_t)}\)

I to nie jest do pokazania, tylko założenie z którego się korzysta. Proces stochastyczny mający własność Markowa jest procesem Markowa, którego to wszystko dotyczy.
\(\displaystyle{ V(s) = \EE[G_t|S_t = s] = \EE[R_{t + 1} + \gamma G_{t + 1} | S_t = s] = \\
\EE[R_{t + 1}|S_t = s] + \gamma\EE[G_{t + 1}|S_t = s] = \\
\EE[R_{t + 1}|S_t = s_t] + \gamma{\red \EE[\EE[G_{t + 1}|S_t = s_{t + 1}]|S_t = s_t]} = \\
\EE[R_{t + 1}|S_t = s_t] + \EE[\gamma V(S_{t + 1})|S_t = s_t] = \\
\EE[R_{t + 1} + \gamma V(S_{t + 1})|S_t = s]}\)
Skorzystałem z tego że \(\displaystyle{ \EE(X|H) = \EE[\EE[X|A]|H]}\)

[leg14]

No ale mi właśnie chodzi o tę równość \(\displaystyle{ \EE(X|H) = \EE[\EE[X|A]|H]}\). Skąd ona się bierze? Przecież to nie jest prawda w ogólnym przypadku - potrzeba, by \(\displaystyle{ H \subset A}\) - a czegoś takiego nie ma w założeniach tego tzw. procesu Markova z nagrodą.

Masz tylko tyle:
\(\displaystyle{ \PP(S_{t+1} = x| S_{t} =y,S_{t-1} =a,..,S_{0}=x_0) = \PP(S_{t+1} = x| S_{t} =y) = p_{y,x}}\) (czyli po prostu łańcuch Markova)
oraz \(\displaystyle{ r_s = \EE(R_{t+1}|S_{t}=s )}\)

(dodam, że uczyłem się jedynie o dyskretnych łańcuchach Markova nic więcej nie wiem o procesach stochastycznych itp.)

[Igor V]

Oczywiście że nie jest prawda w ogólnym przypadku. Ale pisałem :

Z własności Markowa - wartości funkcji wzmocnienia i przejść zależą tylko od aktualnego stanu i akcji.

Proces stochastyczny mający własność Markowa jest procesem Markowa

Taki system jest bez pamięci - w każdym kroku nagroda i następny stan zależą (w ogólności probabilistycznie) tylko i wyłącznie od aktualnego stanu i aktualnej akcji :
\(\displaystyle{ R(x,a) = \EE[\rho(x,a)]}\)
\(\displaystyle{ P_{xy}(a) = \PP(\delta(x,a) = y)}\)

[leg14]

Dziwna się robi ta dyskusja. Spróbuję ostatni raz zapytać - Wypisałem Ci post wyżej założenia. Czy da się z nich wyprowadzić równość, która mnie interesuje? Jeśli tak, to proszę o wskazówkę, jak to zrobić, bo tego nie widzę.

[Igor V]

Tutaj zamieszałem coś z indeksem : \(\displaystyle{ \EE[\EE[G_{t + 1}|S_t = s_{t + 1}]|S_t = s_t]}\)
\(\displaystyle{ \EE[\EE[G_{t + 1}|S_{t \red{+ 1}} = s_{t + 1}]|S_t = s_t]}\)

I tak, można. Nie wiem czy już do tego doszedłeś, ale żeby nie pozostawiać wątpliwości to ja znam takie wyjaśnienie :
\(\displaystyle{ \EE[G_{t + 1} | S_t = s] = \EE[\EE[G_{t + 1}|S_{t+1} = s_{t+1},S_{t} = s_{t}]|S_{t} = s_{t}]}\)
Widać że masz spełnione \(\displaystyle{ H \subseteq A}\), więc to przejście jest uzasadnione. Natomiast z własności Markowa wiesz że wartość oczekiwana \(\displaystyle{ G_{t + 1}}\) zależy tylko od \(\displaystyle{ S_{t+1} = s_{t+1}}\), więc \(\displaystyle{ S_{t} = s_{t}}\) jest redundantne i możesz je wywalić.