Wyprowadzanie równania Bellmana w uczeniu się zbrojenia

Widzę następujące równanie w „ In Reinforcement Learning. An Introduction ”, ale nie do końca podążam za krokiem, który zaznaczyłem na niebiesko poniżej. Jak dokładnie pochodzi ten krok?

To jest odpowiedź dla każdego, kto zastanawia się nad czystą, ustrukturyzowaną matematyką (tj. Jeśli należysz do grupy ludzi, która wie, czym jest zmienna losowa i że musisz pokazać lub założyć, że zmienna losowa ma gęstość, to jest to odpowiedź dla ciebie ;-)):

Przede wszystkim musimy mieć pewność, że proces decyzyjny Markowa ma tylko skończoną liczbę , tzn. Potrzebujemy skończonego zbioru gęstości, z których każda należy do zmiennych , tj. dla wszystkich i mapy takie, że (tzn. w automatach stojących za MDP może istnieć nieskończenie wiele stanów, ale istnieje tylko skończenie wiele -rozkładów zależnych od możliwych nieskończonych przejść między stanami)$L^1$$E$$L^1$$\int_{\mathbb{R}}x \cdot e(x) dx < \infty$$e \in E$$F : A \times S \to E$

$$p(r_t|a_t, s_t) = F(a_t, s_t)(r_t)$$ $L^1$

Twierdzenie 1 : Niech (tj. Całkowita rzeczywista zmienna losowa) i niech będzie inną zmienną losową taką, że mają wspólną gęstość, a następnie $X \in L^1(\Omega)$$Y$$X,Y$

$$E[X|Y=y] = \int_\mathbb{R} x p(x|y) dx$$

Dowód : zasadniczo udowodniony tutaj przez Stefana Hansena.

Twierdzenie 2 : Niech i niech będą kolejnymi zmiennymi losowymi, tak aby miały wspólną gęstość, a następnie gdzie jest zakres .$X \in L^1(\Omega)$$Y,Z$$X,Y,Z$

$$E[X|Y=y] = \int_{\mathcal{Z}} p(z|y) E[X|Y=y,Z=z] dz$$ $\mathcal{Z}$$Z$

Dowód :

$$\begin{align*} E[X|Y=y] &= \int_{\mathbb{R}} x p(x|y) dx \\ &~~~~\text{(by Thm. 1)}\\ &= \int_{\mathbb{R}} x \frac{p(x,y)}{p(y)} dx \\ &= \int_{\mathbb{R}} x \frac{\int_{\mathcal{Z}} p(x,y,z) dz}{p(y)} dx \\ &= \int_{\mathcal{Z}} \int_{\mathbb{R}} x \frac{ p(x,y,z) }{p(y)} dx dz \\ &= \int_{\mathcal{Z}} \int_{\mathbb{R}} x p(x|y,z)p(z|y) dx dz \\ &= \int_{\mathcal{Z}} p(z|y) \int_{\mathbb{R}} x p(x|y,z) dx dz \\ &= \int_{\mathcal{Z}} p(z|y) E[X|Y=y,Z=z] dz \\ &~~~~\text{(by Thm. 1)} \end{align*}$$

Wstaw i wstaw wtedy można pokazać (wykorzystując fakt, że MDP ma tylko skończenie wiele -odardów), że zbieżny i że od funkcjijest wciąż w (tj. całkowalne), można również wykazać (używając zwykłej kombinacji twierdzeń o monotonicznej zbieżności, a następnie dominującej zbieżności na równaniach definiujących [rozkład na czynniki] oczekiwań warunkowych), że Teraz to pokazuje $G_t = \sum_{k=0}^\infty \gamma^k R_{t+k}$$G_t^{(K)} = \sum_{k=0}^K \gamma^k R_{t+k}$$L^1$$G_t^{(K)}$$\sum_{k=0}^\infty \gamma^k |R_{t+k}|$$L^1(\Omega)$

$$\lim_{K \to \infty} E[G_t^{(K)} | S_t=s_t] = E[G_t | S_t=s_t]$$ $$E[G_t^{(K)} | S_t=s_t] = E[R_{t} | S_t=s_t] + \gamma \int_S p(s_{t+1}|s_t) E[G_{t+1}^{(K-1)} | S_{t+1}=s_{t+1}] ds_{t+1}$$ przy użyciu , Thm. 2 powyżej to Thm. 1 na a następnie używając prostej wojny o marginalizację, pokazano, że dla wszystkich . Teraz musimy zastosować limit do obu stron równania. Aby przeciągnąć granicę do całki nad przestrzenią stanu , musimy przyjąć kilka dodatkowych założeń:$G_t^{(K)} = R_t + \gamma G_{t+1}^{(K-1)}$$E[G_{t+1}^{(K-1)}|S_{t+1}=s', S_t=s_t]$$p(r_q|s_{t+1}, s_t) = p(r_q|s_{t+1})$$q \geq t+1$$K \to \infty$$S$

Albo przestrzeń stanów jest skończona (wtedy i suma jest skończona) lub wszystkie nagrody są dodatnie (wtedy używamy zbieżności monotonicznej) lub wszystkie nagrody są ujemne (następnie umieszczamy znak minus przed znakiem równanie i ponownie skorzystamy z konwergencji monotonicznej) lub wszystkie nagrody zostaną ograniczone (wówczas użyjemy dominacji konwergencji). Następnie (stosując po obu stronach powyższego równania Bellmana częściowego / skończonego) otrzymujemy$\int_S = \sum_S$$\lim_{K \to \infty}$

$$E[G_t | S_t=s_t] = E[G_t^{(K)} | S_t=s_t] = E[R_{t} | S_t=s_t] + \gamma \int_S p(s_{t+1}|s_t) E[G_{t+1} | S_{t+1}=s_{t+1}] ds_{t+1}$$

a reszta to zwykła manipulacja gęstością.

UWAGA: Nawet w bardzo prostych zadaniach przestrzeń stanu może być nieskończona! Jednym z przykładów byłoby zadanie „równoważenia bieguna”. Stan to zasadniczo kąt bieguna (wartość w , zbiór niepoliczalnie nieskończony!)$[0, 2\pi)$

UWAGA: Ludzie mogą komentować ciasto, ten dowód można znacznie skrócić, jeśli użyjesz bezpośrednio gęstości i pokażesz, że '... ALE ... moje pytania brzmiałyby:$G_t$$p(g_{t+1}|s_{t+1}, s_t) = p(g_{t+1}|s_{t+1})$

1. Skąd w ogóle wiesz, że ma gęstość?$G_{t+1}$
2. Dlaczego w ogóle wiesz, że ma wspólną gęstość wraz z ?$G_{t+1}$$S_{t+1}, S_t$
3. Jak wywnioskować, że ? Jest to nie tylko właściwość Markowa: Właściwość Markowa mówi tylko coś o rozkładach krańcowych, ale niekoniecznie determinują cały rozkład, patrz np. Gaussianie na wielu odmianach!$p(g_{t+1}|s_{t+1}, s_t) = p(g_{t+1}|s_{t+1})$

Niech całkowita suma zdyskontowanych nagród po czasie będzie wynosić: $t$
$G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...$

Wartość użytkową począwszy od stanu, przy czasie jest równa oczekiwanej sumy od dyskontowane nagrody wykonywać polityki począwszy od stanu r. Z definicji Zgodnie z prawem liniowości Zgodnie z prawem$s$$t$
$R$$\pi$$s$
$U_\pi(S_t=s) = E_\pi[G_t|S_t = s]$
$\\ = E_\pi[(R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...)|S_t = s]$$G_t$
$= E_\pi[(R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...))|S_t = s]$
$= E_\pi[(R_{t+1}+\gamma (G_{t+1}))|S_t = s]$
$= E_\pi[R_{t+1}|S_t = s]+\gamma E_\pi[ G_{t+1}|S_t = s]$
$= E_\pi[R_{t+1}|S_t = s]+\gamma E_\pi[E_\pi(G_{t+1}|S_{t+1} = s')|S_t = s]$Całkowite oczekiwanie Z definicji Według zasady liniowości
$= E_\pi[R_{t+1}|S_t = s]+\gamma E_\pi[U_\pi(S_{t+1}= s')|S_t = s]$$U_\pi$
$= E_\pi[R_{t+1} + \gamma U_\pi(S_{t+1}= s')|S_t = s]$

Zakładając, że proces spełnia właściwość Markowa:
Prawdopodobieństwo, że skończy w stanie , rozpoczęło się od stanu i podjął działanie , i Nagroda za ukończenie w stanie rozpoczęta od stanu i podjęta akcja , $Pr$$s'$$s$$a$
$Pr(s'|s,a) = Pr(S_{t+1} = s', S_t=s,A_t = a)$
$R$$s'$$s$$a$
$R(s,a,s') = [R_{t+1}|S_t = s, A_t = a, S_{t+1}= s']$

Dlatego możemy ponownie zapisać powyższe równanie użyteczności jako:
$= \sum_a \pi(a|s) \sum_{s'} Pr(s'|s,a)[R(s,a,s')+ \gamma U_\pi(S_{t+1}=s')]$

Gdzie; : Prawdopodobieństwo podjęcia działań gdy w stan dla stochastycznego polityki. W przypadku polityki deterministycznej$\pi(a|s)$$a$$s$$\sum_a \pi(a|s)= 1$

Oto mój dowód. Opiera się na manipulowaniu rozkładami warunkowymi, co ułatwia śledzenie. Mam nadzieję, że to ci pomoże.

$$\begin{align} v_{\pi}(s)&=E{\left[G_t|S_t=s\right]} \nonumber \\ &=E{\left[R_{t+1}+\gamma G_{t+1}|S_t=s\right]} \nonumber \\ &= \sum_{s'}\sum_{r}\sum_{g_{t+1}}\sum_{a}p(s',r,g_{t+1}, a|s)(r+\gamma g_{t+1}) \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}\sum_{g_{t+1}}p(s',r,g_{t+1} |a, s)(r+\gamma g_{t+1}) \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}\sum_{g_{t+1}}p(s',r|a, s)p(g_{t+1}|s', r, a, s)(r+\gamma g_{t+1}) \nonumber \\ &\text{Note that $p(g_{t+1}|s', r, a, s)=p(g_{t+1}|s')$ by assumption of MDP} \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}p(s',r|a, s)\sum_{g_{t+1}}p(g_{t+1}|s')(r+\gamma g_{t+1}) \nonumber \\ &= \sum_{a}p(a|s)\sum_{s'}\sum_{r}p(s',r|a, s)(r+\gamma\sum_{g_{t+1}}p(g_{t+1}|s')g_{t+1}) \nonumber \\ &=\sum_{a}p(a|s)\sum_{s'}\sum_{r}p(s',r|a, s)\left(r+\gamma v_{\pi}(s')\right) \label{eq2} \end{align}$$ To słynne równanie Bellmana.

Co z następującym podejściem?

$$\begin{align} v_\pi(s) & = \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \\ & = \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_t = s\right] \\ & = \sum_a \pi(a \mid s) \sum_{s'} \sum_r p(s', r \mid s, a) \cdot \,\\ & \qquad \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_{t} = s, A_{t+1} = a, S_{t+1} = s', R_{t+1} = r\right] \\ & = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \left[r + \gamma v_\pi(s')\right]. \end{align}$$

Sumy są wprowadzane w celu uzyskania , i z . W końcu mogą być możliwe działania i możliwe następne stany. W tych dodatkowych warunkach liniowość oczekiwań prowadzi do wyniku prawie bezpośrednio.$a$$s'$$r$$s$

Nie jestem jednak pewien, jak rygorystycznie mój argument jest matematyczny. Jestem otwarty na ulepszenia.

To tylko komentarz / dodatek do zaakceptowanej odpowiedzi.

Byłem zdezorientowany na linii, w której stosuje się prawo całkowitego oczekiwania. Nie sądzę, aby główna forma prawa całkowitego oczekiwania mogła tu pomóc. Wariant tego jest w rzeczywistości potrzebny tutaj.

Jeśli są zmiennymi losowymi i przy założeniu, że istnieje całe oczekiwanie, zachowuje się następująca tożsamość:$X,Y,Z$

$E[X|Y] = E[E[X|Y,Z]|Y]$

W tym przypadku , i . Następnie$X= G_{t+1}$$Y = S_t$$Z = S_{t+1}$

$E[G_{t+1}|S_t=s] = E[E[G_{t+1}|S_t=s, S_{t+1}=s'|S_t=s]$ , które przez właściwość Markowa równoważy$E[E[G_{t+1}|S_{t+1}=s']|S_t=s]$

Stamtąd można śledzić resztę dowodu z odpowiedzi.

$\mathbb{E}_\pi(\cdot)$ zwykle oznacza oczekiwanie przy założeniu, że agent przestrzega zasad . W tym przypadku wydaje zakaz deterministyczny, czyli zwraca prawdopodobieństwo, że agent podejmuje działania kiedy w stan .$\pi$$\pi(a|s)$$a$$s$

Wygląda na to, że , małe litery, zastępuje , zmienną losową. Drugie oczekiwanie zastępuje nieskończoną sumę, aby odzwierciedlić założenie, że będziemy podążać przez całą przyszłość . jest wówczas oczekiwaną natychmiastową nagrodą w następnym kroku czasowym; Drugi oczekiwania, która staje -jest oczekiwaną wartość następnego stanu, ważonej przez prawdopodobieństwo zwijania się w stan wziąwszy od .$r$$R_{t+1}$$\pi$$t$$\sum_{s',r} r \cdot p(s′,r|s,a)$$v_\pi$$s'$$a$$s$

Zatem oczekiwanie uwzględnia prawdopodobieństwo polisy, a także funkcje przejścia i nagrody, tutaj wyrażone łącznie jako .$p(s', r|s,a)$

mimo że poprawna odpowiedź została już udzielona i minęło trochę czasu, pomyślałem, że może być przydatny następujący przewodnik krok po kroku:
Poprzez liniowość oczekiwanej wartości możemy podzielić na i . Przedstawię kroki tylko w pierwszej części, ponieważ w drugiej części następują te same kroki w połączeniu z prawem całkowitego oczekiwania.$E[R_{t+1} + \gamma E[G_{t+1}|S_{t}=s]]$$E[R_{t+1}|S_t=s]$$\gamma E[G_{t+1}|S_{t}=s]$

$$\begin{align} E[R_{t+1}|S_t=s]&=\sum_r{ r P[R_{t+1}=r|S_t =s]} \\ &= \sum_a{ \sum_r{ r P[R_{t+1}=r, A_t=a|S_t=s]}} \qquad \text{(III)} \\ &=\sum_a{ \sum_r{ r P[R_{t+1}=r| A_t=a, S_t=s] P[A_t=a|S_t=s]}} \\ &= \sum_{s^{'}}{ \sum_a{ \sum_r{ r P[S_{t+1}=s^{'}, R_{t+1}=r| A_t=a, S_t=s] P[A_t=a|S_t=s] }}} \\ &=\sum_a{ \pi(a|s) \sum_{s^{'},r}{p(s^{'},r|s,a)} } r \end{align}$$

Podczas gdy (III) ma postać:

$$\begin{align} P[A,B|C]&=\frac{P[A,B,C]}{P[C]} \\ &= \frac{P[A,B,C]}{P[C]} \frac{P[B,C]}{P[B,C]}\\ &= \frac{P[A,B,C]}{P[B,C]} \frac{P[B,C]}{P[C]}\\ &= P[A|B,C] P[B|C] \end{align}$$

Wiem, że istnieje już akceptowana odpowiedź, ale chcę podać prawdopodobnie bardziej konkretne pochodne. Chciałbym również wspomnieć, że chociaż sztuczka @Jie Shi ma sens, ale sprawia, że ​​czuję się bardzo nieswojo :(. Musimy wziąć pod uwagę wymiar czasu, aby ta praca działała. Ważne jest, aby pamiętać, że oczekiwanie jest w rzeczywistości przejął cały nieskończony horyzont, a nie tylko i . Załóżmy, że zaczynamy od (w rzeczywistości wyprowadzenie jest takie samo bez względu na czas rozpoczęcia; nie chcę zanieczyszczać równań innym indeksem dolnym ) $s$$s'$$t=0$$k$

$$\begin{align} v_{\pi}(s_0)&=\mathbb{E}_{\pi}[G_{0}|s_0]\\ G_0&=\sum_{t=0}^{T-1}\gamma^tR_{t+1}\\ \mathbb{E}_{\pi}[G_{0}|s_0]&=\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\\ &\times\Big(\sum_{t=0}^{T-1}\gamma^tr_{t+1}\Big)\bigg)\\ &=\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\\ &\times\Big(r_1+\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}\Big)\bigg) \end{align}$$ ODNOTOWUJE, ŻE POWYŻSZE RÓWNANIE JEST NAWET JEŚLI , FAKTEM BĘDZIE PRAWDĄ AŻ DO KOŃCA UNIWERSYTETU (być może trochę przesadzone :))$T\rightarrow\infty$
Na tym etapie uważam, że większość z nas powinna już pamiętać, w jaki sposób powyższe prowadzi do ostatecznego wyrażenia - musimy tylko zastosować zasadę sum-iloczyn ( ) . Zastosujmy prawo liniowości Oczekiwania do każdego terminu wewnątrz$\sum_a\sum_b\sum_cabc\equiv\sum_aa\sum_bb\sum_cc$$\Big(r_{1}+\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}\Big)$

Część 1

$$\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\times r_1\bigg)$$

Cóż, jest to raczej trywialne, wszystkie prawdopodobieństwa znikają (faktycznie sumują się do 1) oprócz tych związanych z . Dlatego mamy $r_1$

$$\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\times r_1$$

Część 2
Zgadnij co, ta część jest jeszcze bardziej trywialna - polega jedynie na zmianie kolejności sumowań.

$$\sum_{a_0}\pi(a_0|s_0)\sum_{a_{1},...a_{T}}\sum_{s_{1},...s_{T}}\sum_{r_{1},...r_{T}}\bigg(\prod_{t=0}^{T-1}\pi(a_{t+1}|s_{t+1})p(s_{t+1},r_{t+1}|s_t,a_t)\bigg)\\=\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\bigg(\sum_{a_1}\pi(a_1|s_1)\sum_{a_{2},...a_{T}}\sum_{s_{2},...s_{T}}\sum_{r_{2},...r_{T}}\bigg(\prod_{t=0}^{T-2}\pi(a_{t+2}|s_{t+2})p(s_{t+2},r_{t+2}|s_{t+1},a_{t+1})\bigg)\bigg)$$

I Eureka !! odzyskujemy wzór rekurencyjny z boku dużych nawiasów. Połączmy to z , a otrzymamy a część 2 staje się $\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}$$v_{\pi}(s_1)=\mathbb{E}_{\pi}[G_1|s_1]$

$$\gamma\mathbb{E}_{\pi}[G_1|s_1]=\sum_{a_1}\pi(a_1|s_1)\sum_{a_{2},...a_{T}}\sum_{s_{2},...s_{T}}\sum_{r_{2},...r_{T}}\bigg(\prod_{t=0}^{T-2}\pi(a_{t+2}|s_{t+2})p(s_{t+2},r_{t+2}|s_{t+1},a_{t+1})\bigg)\bigg(\gamma\sum_{t=0}^{T-2}\gamma^tr_{t+2}\bigg)$$
$$\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\times \gamma v_{\pi}(s_1)$$

Część 1 + Część 2

$$v_{\pi}(s_0) =\sum_{a_0}\pi(a_0|s_0)\sum_{s_1,r_1}p(s_1,r_1|s_0,a_0)\times \Big(r_1+\gamma v_{\pi}(s_1)\Big)$$

A teraz, jeśli uda nam się zmieścić w wymiarze czasu i odzyskać ogólne formuły rekurencyjne

$$v_{\pi}(s) =\sum_a \pi(a|s)\sum_{s',r} p(s',r|s,a)\times \Big(r+\gamma v_{\pi}(s')\Big)$$

Ostateczna spowiedź, roześmiałem się, gdy zobaczyłem, że ludzie powyżej wspominają o prawie całkowitego oczekiwania. A więc jestem tu

Istnieje już bardzo wiele odpowiedzi na to pytanie, ale większość zawiera kilka słów opisujących, co dzieje się w manipulacjach. Myślę, że odpowiem używając więcej słów. Zacząć,

$$G_{t} \doteq \sum_{k=t+1}^{T} \gamma^{k-t-1} R_{k}$$

jest zdefiniowany w równaniu 3.11 Sutton i Barto, ze stałym współczynnikiem dyskontowym i możemy mieć lub , ale nie oba. Ponieważ nagrody, , są zmiennymi losowymi, podobnie jak ponieważ jest to tylko liniowa kombinacja zmiennych losowych.$0 \leq \gamma \leq 1$$T = \infty$$\gamma = 1$$R_{k}$$G_{t}$

$$\begin{align} v_\pi(s) & \doteq \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \\ & = \mathbb{E}_\pi\left[R_{t+1} + \gamma G_{t+1} \mid S_t = s\right] \\ & = \mathbb{E}_{\pi}\left[ R_{t+1} | S_t = s \right] + \gamma \mathbb{E}_{\pi}\left[ G_{t+1} | S_t = s \right] \end{align}$$

Ta ostatnia linia wynika z liniowości wartości oczekiwanych. to nagroda, którą agent otrzymuje po podjęciu działania w kroku czasu . Dla uproszczenia zakładam, że może on przyjąć skończoną liczbę wartości . $R_{t+1}$$t$$r \in \mathcal{R}$

Pracuj przez pierwszy semestr. Innymi słowy, muszę obliczyć wartości oczekiwane biorąc pod uwagę, że wiemy, że obecny stan to . Wzór na to jest następujący$R_{t+1}$$s$

$$\begin{align} \mathbb{E}_{\pi}\left[ R_{t+1} | S_t = s \right] = \sum_{r \in \mathcal{R}} r p(r|s). \end{align}$$

Innymi słowy, prawdopodobieństwo pojawienia się nagrody zależy od stanu ; różne stany mogą mieć różne nagrody. Ten rozkład jest rozkładem krańcowym rozkładu, który zawierał również zmienne i , działanie podjęte w czasie oraz stan w czasie po działaniu, odpowiednio:$r$$s$$p(r|s)$$a$$s'$$t$$t+1$

$$\begin{align} p(r|s) = \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(s',a,r|s) = \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} \pi(a|s) p(s',r | a,s). \end{align}$$

Gdzie użyłem , zgodnie z konwencją książki. Jeśli ta ostatnia równość jest myląca, zapomnij o sumach, pomiń (prawdopodobieństwo wygląda teraz jak wspólne prawdopodobieństwo), skorzystaj z prawa pomnożenia i na końcu przywróć warunek na we wszystkich nowych kategoriach. Teraz łatwo zauważyć, że jest to pierwszy termin$\pi(a|s) \doteq p(a|s)$$s$$s$

$$\begin{align} \mathbb{E}_{\pi}\left[ R_{t+1} | S_t = s \right] = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} r \pi(a|s) p(s',r | a,s), \end{align}$$

jako wymagane. Przejdźmy do drugiego terminu, w którym zakładam, że jest zmienną losową, która przyjmuje skończoną liczbę wartości . Podobnie jak w pierwszym semestrze:$G_{t+1}$$g \in \Gamma$

$$\begin{align} \mathbb{E}_{\pi}\left[ G_{t+1} | S_t = s \right] = \sum_{g \in \Gamma} g p(g|s). \qquad\qquad\qquad\qquad (*) \end{align}$$

Po raz kolejny „marginalizuję” rozkład prawdopodobieństwa pisząc (ponownie prawo mnożenia)

$$\begin{align} p(g|s) & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(s',r,a,g|s) = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s', r, a, s) p(s', r, a | s) \\ & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s', r, a, s) p(s', r | a, s) \pi(a | s) \\ & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s', r, a, s) p(s', r | a, s) \pi(a | s) \\ & = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} p(g | s') p(s', r | a, s) \pi(a | s) \qquad\qquad\qquad\qquad (**) \end{align}$$

Ostatni wiersz pochodzi z nieruchomości Markowa. Pamiętaj, że to suma wszystkich przyszłych (zdyskontowanych) nagród, które agent otrzymuje po stanie . Właściwość Markovian polega na tym, że proces ten nie wymaga pamięci w odniesieniu do poprzednich stanów, działań i nagród. Przyszłe działania (i nagrody, które czerpią) zależą tylko od stanu, w którym działanie jest podejmowane, więc , z założenia. Ok, więc teraz jest drugi termin w dowodzie$G_{t+1}$$s'$$p(g | s', r, a, s) = p(g | s')$

$$\begin{align} \gamma \mathbb{E}_{\pi}\left[ G_{t+1} | S_t = s \right] & = \gamma \sum_{g \in \Gamma} \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} g p(g | s') p(s', r | a, s) \pi(a | s) \\ & = \gamma \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} \mathbb{E}_{\pi}\left[ G_{t+1} | S_{t+1} = s' \right] p(s', r | a, s) \pi(a | s) \\ & = \gamma \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} \sum_{a \in \mathcal{A}} v_{\pi}(s') p(s', r | a, s) \pi(a | s) \end{align}$$

w razie potrzeby, jeszcze raz. Połączenie dwóch terminów stanowi dowód

$$\begin{align} v_\pi(s) & \doteq \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \\ & = \sum_{a \in \mathcal{A}} \pi(a | s) \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} p(s', r | a, s) \left[ r + \gamma v_{\pi}(s') \right]. \end{align}$$

AKTUALIZACJA

Chcę zająć się czymś, co może wyglądać jak sztuczka w wyprowadzaniu drugiego semestru. W równaniu oznaczonym używam terminu a następnie w równaniu oznaczonym twierdzę, że nie zależy od , argumentując właściwość Markoviana. Można więc powiedzieć, że jeśli tak jest, to . Ale to nie jest prawda. Mogę wziąć ponieważ prawdopodobieństwo po lewej stronie tego stwierdzenia mówi, że jest to prawdopodobieństwo uwarunkowane na , , i$(*)$$p(g|s)$$(**)$$g$$s$$p(g|s) = p(g)$$p(g | s', r, a, s) \rightarrow p(g | s')$$g$$s'$$a$$r$$s$. Ponieważ albo znamy, albo zakładamy, że stan nie , żaden z pozostałych warunków nie ma znaczenia, z powodu własności Markowa. Jeśli nie wiesz, czy zakładamy stan , a następnie nagrody przyszłości (Sens ) zależeć będzie od którego stan zaczniesz na, bo to będzie określić (na podstawie polisy), które stwierdzają, uruchomieniu na przy obliczaniu .$s'$$s'$$g$$s'$$g$

Jeśli ten argument cię nie przekonuje, spróbuj obliczyć, czym jest :$p(g)$

$$\begin{align} p(g) & = \sum_{s' \in \mathcal{S}} p(g, s') = \sum_{s' \in \mathcal{S}} p(g | s') p(s') \\ & = \sum_{s' \in \mathcal{S}} p(g | s') \sum_{s,a,r} p(s', a, r, s) \\ & = \sum_{s' \in \mathcal{S}} p(g | s') \sum_{s,a,r} p(s', r | a, s) p(a, s) \\ & = \sum_{s \in \mathcal{S}} p(s) \sum_{s' \in \mathcal{S}} p(g | s') \sum_{a,r} p(s', r | a, s) \pi(a | s) \\ & \doteq \sum_{s \in \mathcal{S}} p(s) p(g|s) = \sum_{s \in \mathcal{S}} p(g,s) = p(g). \end{align}$$

Jak widać w ostatnim wierszu, nie jest prawdą, że . Oczekiwana wartość zależy od stanu, w którym zaczynasz (tj. Tożsamości ), jeśli nie znasz stanu lub go nie zakładasz .$p(g|s) = p(g)$$g$$s$$s'$