Podstawy procesów decyzyjnych Markova

Definicja klasyczna. Prawdopodobieństwo warunkowe i całkowite. Zmienne losowe i ich parametry. Niezależność. Prawa wielkich liczb oraz centralne twierdzenia graniczne i ich zastosowania.
Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Podstawy procesów decyzyjnych Markova

Post autor: leg14 » 4 lis 2017, o 23:46

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 http://www.cs.princeton.edu/courses/arc ... s/0429.pdf na stronie 4). W 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 ).

Awatar użytkownika
Igor V
Użytkownik
Użytkownik
Posty: 1605
Rejestracja: 16 lut 2011, o 16:48
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 18 razy
Pomógł: 604 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: Igor V » 5 lis 2017, o 00:37

leg14 pisze:\(\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)}\) ?
leg14 pisze:Skąd to się bierze?
Z własności Markowa - wartości funkcji wzmocnienia i przejść zależą tylko od aktualnego stanu i akcji.

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: leg14 » 5 lis 2017, o 01:03

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ć?

Awatar użytkownika
Igor V
Użytkownik
Użytkownik
Posty: 1605
Rejestracja: 16 lut 2011, o 16:48
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 18 razy
Pomógł: 604 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: Igor V » 5 lis 2017, o 13:30

leg14 pisze: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.
leg14 pisze: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):
Igor V pisze:\(\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]}\)

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: leg14 » 5 lis 2017, o 13:33

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

Awatar użytkownika
Igor V
Użytkownik
Użytkownik
Posty: 1605
Rejestracja: 16 lut 2011, o 16:48
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 18 razy
Pomógł: 604 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: Igor V » 5 lis 2017, o 13:50

Oczywiście że nie jest prawda w ogólnym przypadku. Ale pisałem :
Igor V pisze:Z własności Markowa - wartości funkcji wzmocnienia i przejść zależą tylko od aktualnego stanu i akcji.
Igor V pisze: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)}\)

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: leg14 » 5 lis 2017, o 14:03

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ę.

Awatar użytkownika
Igor V
Użytkownik
Użytkownik
Posty: 1605
Rejestracja: 16 lut 2011, o 16:48
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 18 razy
Pomógł: 604 razy

Re: Podstawy procesów decyzyjnych Markova

Post autor: Igor V » 13 lis 2017, o 17:02

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ć.

ODPOWIEDZ