# Reinforcement Learning: An Introduction_Chapter 4 Dynamic Programming
###### tags: `Reinforcement Learning` `Second Edition`
[相關連結_Sutton_2nd](http://incompleteideas.net/book/the-book-2nd.html)
[David Silver_bilibili_簡中字幕](https://www.bilibili.com/video/BV1kb411i7KG/)
[程式碼參考_ShangtongZhang](https://github.com/ShangtongZhang/reinforcement-learning-an-introduction)
[程式碼參考_dennybritz](https://github.com/dennybritz/reinforcement-learning)
[程式碼參考_弱弱的我](https://github.com/shaoeChen/Reinforcement-Learning-An-Introduction-Record)
:::warning
env：environment縮寫
sweep：查字典可以翻譯[拂掠](http://terms.naer.edu.tw/detail/13865724/)，也有掃描、遍歷的意思
:::
Dynamic Programming(DP)可用於在給定完美環境模型作為馬爾可夫決策過程(MDP)的情況下計算最佳策略(optimal policies)。不過DP的應用在這邊是有限的，主要原因在於：
(1)它假設你擁有一個完整的模型(就是你知道env的全貌)，
(2)需要很大的計算開銷。儘管如此，它仍然是一個很重要的理論基礎。
這一章雖然談的是DP，但對後續章節而言也是很重要的基礎，不要跳過(我就是跳過又回來看)。事實上所有的方法都可以視為是試著去擁有跟DP一樣的效能，只是計算開銷更少，然後也沒有對env完整模型的假設。
:::warning
DP的一個特性，就是可以把一個問題拆解成很多的子問題，然後子問題處理之後合併起來就得到一個完整的答案。而Bellman equation就有著這樣的特性，它是遞迴的組合，它將optimal value function拆分為兩個部份，也就是當下的最佳行為，以及下一個狀態的最佳行為，最終組合起來就是整體的最佳。
而value function就是暫存我們目前找到的最佳值(optimal value)，你從value function你可以找到你從任意一個狀態出發的解決方案，你並不需要每次重覆計算一次來得到任意狀態的值(value)。
:::
這一章我們通常假設env是finite MPD。意思就是state、action、reward sets，$\mathcal{S}, \mathcal{A}, \mathcal{R}$都是finite，然後它們的動態性的給定是來自於$p(s',r\vert s, a)$，$\forall s \in \mathcal{S}, a \in \mathcal{A}, r \in \mathcal{R}, s'\in \mathcal{S}^+$($\mathcal{S}^+$是$\mathcal{S}$再加上一個terminal state(如果該問題是episodic))。雖然DP的想法也可以用在continusous state、action spaces，但只有在特殊案例上才會有精確的解。常見處理這種連續型任務的方式就是去離散化其state與action spaces，處理之後再來用finite-state DP methods。
強化學習中，DP的核心思想就是使用value functions去找出一個好的policies。這章就會用DP來實作Chapter 3提出的value functions。如Chapter 3所討論，一旦我們得到一個滿足Bellman optimality equations的optimal value functions，$v_*$或$q_*$，那就可以很輕易的得到optimal policies，$\forall s \in \mathcal{S}, a \in \mathcal{A}, s'\in \mathcal{S}^+$($\mathcal{S}^+$：
$$
\begin{align}
v_*(s) &= \max_a \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \vert S_{t}=s, A_t=a] \\
&= \max_a \sum_{s', r}p(s', r \vert s, a)[r + \gamma v_*(s')]
\end{align} \tag{4.1}
$$
或者
$$
\begin{align}
q_*(s,a) &= \mathbb{E}[R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \vert S_{t}=s, A_t=a] \\
&= \sum_{s', r}p(s', r \vert s, a)[r + \gamma \max_{a'} q_*(s', a')]
\end{align} \tag{4.2}
$$
如上所見，我們利用將Bellman equations轉化為近似理想的value functions的更新規則，我們就得到DP演算法。
:::warning
上面的公式搭配Chapter 3的backup diagram來看會比較有感覺
:::
:::warning
簡單說，policy evaluation就是單純的想知道我們的policy有多好，在每次的轉移過程中我們能得到多少的reward。而control的問題就是一個優化的問題，你有那麼多的policy，我們想知道那一個是最好的policy，那一個policy可以讓我們得到最大的rewards。
:::
## 4.1 Policy Evaluation (Prediction)
首先我們考慮如何對任意的policy $\pi$計算其state-value function $v_\pi$。這在DP文獻中稱為policy evaluation。也把它稱為預測問題(prediction problem)。回想Chapter 3的公式，$\forall s \in \mathcal{S}$，
$$
\begin{align}
v_\pi(s) & \dot{=} \mathbb{E}_\pi[G_t \vert S_{t}=s] \\
&= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} \vert S_{t}=s] \tag{3.9} \\
&= \mathbb{E}_\pi[R_{t+1} + \gamma v_\pi (S_{t+1}) \vert S_{t}=s] \tag{4.3} \\
&= \sum_a \pi(a\vert s) \sum_{s', r}p(s', r\vert s, a)[r + \gamma v_\pi(s')] \tag{4.4}
\end{align}
$$
其中$\pi(a\vert s)$是用著policy $\pi$在給定state $s$的情況下選擇action $a$的機率，然後期望值的下標$\pi$就說明著是以$\pi$來做為條件的。只要$\gamma <1$或者所有的state在policy $\pi$下都能保證最後會終止(termination)，那就可以保證$v_\pi$的存在性與唯一性。
:::warning
3.9到4.4的部份可以參考[Chapter 3](https://hackmd.io/lxtiMhuuRTiAjlQKI8fsWw#35-Policies-and-Value-Functions)的3.9推論到3.14，不過終究這還是回到backup diagram，你計算的就是在這個state $s$的情況下的所有action $a$的可能的機率($\sum_a\pi(a\vert s)$)去乘上你在給定這個state-action pair情況下的所有可能的next state $s'$與reward $r$的期望值$\sum_{s', r}p(s', r\vert s, a)[r + \gamma v_\pi(s')]$。
:::
如果env的動態性完全已知，那(4.4)就只是一個線性方程式。原則上它求解過程是一個簡單而乏味的計算。對我們的需求而言，迭代求解的方法比較適合。考慮一系列的approximate value functions $v_0, v_1, v_2, v_3, \cdots,$，每一個都是把$\mathcal{S}^+$映射到$\mathbb{R}$(實數)。initial approximation，$v_0$是亂挑的(除非有terminal state，那就要賦值0)，每個後續的approximation都可以用4.4(Bellman equation for $v_\pi$)來做為更新的規則，$\forall s \in \mathcal{S}$：
$$
\begin{align}
v_{k+1}(s) &\dot{=} \mathbb{E}[R_{t+1} + \gamma v_k(S_{t+1}) \vert S_{t}=s] \\
&=\sum_a \pi(a \vert s) \sum_{s',r} p(s', r\vert s, a)[r + \gamma v_k(s')] \tag{4.5}
\end{align}
$$
很明顯的，$v_k=v_\pi$是這個更新規則的一個fixed point，因為$v_k$的Bellman equation確保在這種情況下的等式是成立的。確實，在保證$v_k$存在的條件下，序列$\left\{ v_k \right\}$在$k\to\infty$的時候會收斂到接近$v_\pi$。這種演算法稱為iterative policy evaluation。
:::warning
policy evaluation，評估的就是某一個state的value有多好，所以你就是用著你手上的policy去看你在state $s$的時候，每一個action會得到什麼樣的結果，從$v_k \to v_{k+1}$就是一次迭代，你會不斷的迭代，當你的迭代次數可以趨近無限的時候，你就可以收斂到$v_\pi$，而這個$v_\pi$就最終你停止迭代的時候的那一個policy。後面會提到，當整個更新過程的變動不再超過某一個我們所設置的閥值的時候，這個迭代過程就會停止。
線性解的說明可以參考[3.5_Policies-and-Value-Functions](https://hackmd.io/@shaoeChen/Hkm3mMjL_#35-Policies-and-Value-Functions)
:::
為了從$v_k$生成每一個後續的approximation $v_{k+1}$，迭代策略評估(iterative policy evaluation)對每一個state $s$做相同的操作：它用一個從$s$的後續狀態的舊值所獲得的新值來替換掉$s$的舊值，與在所評估的策略下的所有可能一步的轉換(one-step transitions)所得到的預期的立即性報酬(expected immediate rewards)。這樣的操作稱為expected update。迭代策略評估的每一次迭代都會去更新一次每個狀態(state)的值(value)，以此產生一個新的近似的價值函數(approximate value function)$v_{k+1}$。expected updates的方式有很多種，取決於用state還是state-action pairs來更新，或是取決於後續狀態(successor states)的估測價值的精確組合方式。所有在DP演算法中更新完成的都稱為expected updates，因為它們是基於所有可能的下一個狀態的期望值，而不是基於一個採樣的下一個狀態(a sample next state)。Chapter 3的backup diagram可以說明這些。
:::warning
你從$v_k \to v_{k+1}$，上面提到它用一個從$s$的後續狀態的舊值所獲得的新值來替換掉$s$的舊值，這邊說的應該是公式4.5的部份，它的$s'$是由舊的policy $v_k$來計算，最終得到的結果做為$v_{k+1}$的計算基礎。
:::
為了能夠實現4.5這個iterative policy evaluation，我們可以使用兩個array，一個記錄舊值，$v_k(s)$，一個記錄新值，$v_{k+1}(s)$。有了這兩個arrays，新值可以在舊值不被更動的情況下更新。當然你也可以用一個array來做in-place的更新，還是可以收斂到$v_\pi$，只是計算過程中有些許的不同。而且，收斂速度還比較快，因為新的資料是可以立即使用的。我們認為這個update是掃過整個update space。對於in-place的這種演算法，掃描過程中狀態(state)值更新的順序對收斂速度有明顯的影響。基本上當你考慮使用DP的時候就會想到這種in-place的版本。
下面給出in-place的iterative policy evaluation的pseudocode：
可以注意一下它如何處理終止。通常迭代策略評估只在極限的時候才有辦法收斂，不過實務上不大可能。可以看的在到這個pseudocode每次掃過之後就會測一下$\max_{s \in \mathcal{S}} \vert v_{k+1}(s) - v_k(s) \vert$，然後當它夠小的時候就停止。
:::warning
手動寫完[程式](https://github.com/shaoeChen/Reinforcement-Learning-An-Introduction-Record)之後會發現，在這邊的$v_k$指的是第$k$次迭代之後得到的value，那$v_{k+1}$的值是利用$v_k$去推出來就比較能夠直觀的理解。因為prediction problem談的是這個policy有多好。
:::
:::info
Example 4.1
* nonterminal states：$\mathcal{S} = \left\{ 1,2,\cdots, 14 \right\}$
* 每個state都有4個actions：$\mathcal{A}=\left\{\text{up, down, right, left}\right\}$，如果選擇的action會讓agent超出這個網格，那就原地不動，舉例來說，$p(6, -1 \vert 5, \text{right})=1, p(7, -1 \vert 7, \text{right})=1, p(10, r \vert 5, \text{right})=0, \text{ for all } r \in \mathcal{R}$
* 這是一個沒有discount的episode類型的任務
* 在到達terminal state之前，每次的狀態轉移都會造成reward -1
* 圖片上的陰影區就是terminal state
* expected reward function為$r(s,a,s')=-1, \text{ for all state } s, s' \text{, actions } a$
* 假設agent的policy是一個等機率的隨機策略，意思就是所有的actions有著相同的機率
Figure 4.1的左邊說明著利用迭代策略評估計算的價值函數$\left\{ v_k \right\}$的序列。最終估測的其實就是$v_\pi$，計算的就是每個state到終止的步數的期望值取負。
Figure 4.1：在小的網格上，迭代策略評估的收斂情況。左邊是隨機策略下(所有的action機率相等)的state-value function的近似值的序列。右邊則是對應value function estimates的greedy policies的序列(箭頭指的是能夠到達最大值的actions，數值則是四捨五入兩位數)。最後的policy只能保證對random policy的改進，但這種情況下，在經過第三次的迭代之後，所有的policies都會是optimal。
:::
:::warning
上面的範例實作之後可以有很好的理解，為什麼會是公式4.5的結果，假設現在是$k=3$，然後你計算的是(1, 1)這個索引的新的value，$-2.9$就是利用$k=2$的value，搭配上、下、左、右各計算一次之後所得，$-2.9 = 0.25 * 1 * (-1 - 1.7) * 2 + 0.25 * 1 * (-1 - 2.0) * 2$，其中$0.25$是每個action被選中的機率，$*2$是兩個action的$s'$都是一樣的，$*1$是因為沒有discount，$-1.7, -2.0$分別是選定action之後的$s'$的value，最終得到的是$-2.85$，四捨五入之後$-2.9$
:::
## 4.2 Policy Improvement
之所以計算policy的value function，就是為了能夠找到更好的policies。假設，我們對任意確定性的policy $\pi$已經確定其value function $v_\pi$。對於某些的state $s$，我們想知道是否應該改變policy選擇的action，也就是$a \neq \pi(s)$。我們知道從state $s$用著當前的policy有多好，也就是$v_\pi(s)$，但我們並不知道換一個policy會不會比較好還是比較不好。回答這個問題的一個方法就是在$s$的時候選擇$a$，然後用著現有的policy $\pi$。這種行為方式的value為：
$$
\begin{align}
q_\pi(s,a) & \dot{=}\mathbb{E}[R_{t+1}+\gamma v_\pi(S_{t+1}) \vert S_{t}=s, A_{t}=a] \\
&= \sum_{s', r} p(s',r \vert s, a)[r + \gamma v_\pi(s')]
\end{align}\tag{4.6}
$$
這關鍵的准則在於這會比$v_\pi(s)$還要好還是不好：
* 如果值比$v_\pi(s)$來的大，也就是，如果用著$\pi$在$s$的時候選擇$a$是比較好的，那後面就會通通都用$\pi$，我們就會預期每次遇到$s$都選擇$a$都會比較好，那我們就會說這個新的policy整體來說是比較好的
這是一個稱為policy improvement theorem的特例。假設$\pi$與$\pi'$是任意一對的確定性的policies，也就是對於所有的$s \in \mathcal{S}$，
$$q_\pi(s, \pi'(s)) \geq v_\pi(s) \tag{4.7}$$
那麼policy $\pi'$就要比$\pi$好，或是一樣好。意思就是說，它必須獲得更高或相等的expected return($\forall s \in \mathcal{S}$)：
$$v_{\pi'}(s) \geq v_\pi(s) \tag{4.8}$$
此外，如4.7在任意的state有[嚴格的不等式](http://terms.naer.edu.tw/detail/958156/)，那麼該state在4.8就必需是嚴格的不等式。
:::warning
4.6到4.8，我用$\pi'$決定的action的q value如果比$v_\pi(s)$來的好(base on 4.6、4.7)，那就代表$\pi'$是比$\pi$還要好，既然如此，那$v_{\pi'}(s) \geq v_\pi(s)$(4.8)，因為你4.6已經說了，如果$q_\pi(s, a)$比$v_\pi(s)$好，那這個$\pi$就是一個好$\pi$ ，我們就用它，下面會有相關證明。
:::
策略改進定理應用到我們在這一章開始說的兩個polocies，也就是原始的$\pi$跟改進的$\pi'$，除了$\pi'(s)=a\neq \pi(s)$之外，它們是一樣的。除了$s$以外的states，4.7都是成立的，因為兩邊是相同的。因此，如果$q_\pi(s,a) > v_\pi(s)$，那改進後的policy $\pi'$就一定會比$\pi$來的好。
策略改進定理背後的想法很簡單。我們從4.7開始，然後一直用4.6來擴充$q_\pi$那邊，然後重覆4.7一直到我們得到$v_{\pi'}(s)$：
$$
\begin{align}
v_\pi(s) & \leq q_\pi(s, \pi'(s)) \\
&= \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \vert S_{t}=s, A_{t}=\pi'(s)] \tag{4.6} \\
&= \mathbb{E}_{\pi'}[R_{t+1} + \gamma v_\pi(S_{t+1}) \vert S_{t}=s] \\
& \leq \mathbb{E}_{\pi'}[R_{t+1} + \gamma q_\pi(S_{t+1}, \pi'(S_{t+1})) \vert S_{t}=s] \tag{4.7} \\
&= \mathbb{E}_{\pi'}[R_{t+1} + \gamma \mathbb{E}[R_{t+2} + \gamma v_\pi(S_{t+2}) \vert S_{t+1}, A_{t+1}=\pi'(S_{t+1})] \vert S_{t}=s] \\
&= \mathbb{E}_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) \vert S_{t}=s] \\
& \leq \mathbb{E}_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 v_\pi(S_{t+3}) \vert S_{t}=s] \\
& \vdots \\
& \leq \mathbb{E}_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \vert S_{t}=s] \\
&= v_{\pi'}(s)
\end{align}
$$
:::warning
這邊就把4.6到4.8推論證明給你看
:::
目前為止我們已經看到，給定一個policy與其value function，我們可以很簡單的在policy中估測單一個state的改變。很自然的你就可以把這一點擴展成所有的states，然後根據$q_\pi(s, a)$在每一個state選擇最好的action。換句話說，考慮新的greedy policy $\pi'$，給出：
$$
\begin{align}
\pi'(s) & \dot{=} \arg\max_a q_\pi(s, a) \\
&= \arg\max_a \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1})\vert S_{t}=s, A_{t}=a] \\
&= \arg\max_a \sum_{s', r}p(s', r \vert s, a)[r + \gamma v_\pi(s')]
\end{align} \tag{4.9}
$$
其中$\arg\max_a$意味著能夠讓這個表達式最大的那個$a$(相等則任取其中一個)。greedy policy會採取短時間內看起來是最好的action，也就是根據$v_\pi$向前一步。這樣構造出來的greedy policy滿足策略改進理論(4.7)的條件，因此我們知道它會比原本的policy還要好，或是一樣好。這種利用原始的policy的value functio來做greedy然後弄出一個更好的policy的作法就稱為policy improvement。
假設這個新的policy $\pi'$跟原本的policy $\pi$一樣好，但沒有比它好。這樣的話，$v_{\pi'}=v_\pi$，從公式4.9我們知道，$\forall s\in\mathcal{S}$：
$$
\begin{align}
v_{\pi'}(s) &= \max_a\mathbb{E}[R_{t+1} + \gamma v_{\pi'}(S_{t+1}) \vert S_{t}=s, A_{t}=a] \\
&=\max_a \sum_{s', r}p(s', r \vert s, a)[r + \gamma v_{\pi'}(s')]
\end{align}
$$
上面那個式子跟Bellman optimality equation(4.1)是一樣的，因此$v_{\pi'}$一定會是$v_*$，而且$v_\pi, v_{\pi'}$都是optimal policies。因此，除非原本的policy已經是optimal，不然根據policy improvement必然給我們一個更好的policy。
:::warning
$$
\begin{align}
v_*(s) &= \max_a \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \vert S_{t}=s, A_t=a] \\
&= \max_a \sum_{s', r}p(s', r \vert s, a)[r + \gamma v_*(s')]
\end{align} \tag{4.1}
$$
:::
:::warning
另一種角度來看，DP就是一種將問題切割成子問題的作法，子問題是optimal，那總體來看就會是一個optimal的結果。根據Bellman equation，我們看的就是這一步跟下一步，這一步是最佳，下一步也是最佳，每一個子問題都符合這個結果，那總結來看我們就可以得到最佳解。
直觀來看，根據4.9，反正你的policy就是greedy，根據上一次迭代得到的$v_\pi$，那邊好就往那邊去。所以上面範例可以看的到，當$k=0$的時候，好像四面八方都可以走，可是當$k=1$的時候已經有一點區別了，而到$k=3$的時候也已經可以看的出來，雖然value function還會變動，但action已經固定了。
:::
:::warning
另外就是，我們在policy evaluation的時候是用著上一個policy $\pi$來估測，在做improvement的時候是確定那一個action可以得到更好的value，我們就會在這個時候去變更我們的policy為$\pi'$，這從下面的policy iteration就可以看的出來。
:::
目前為止我們考慮的都是確定性策略(deterministic policies)這種特殊情況，但事實上我們可以很輕易的把它泛化到一般情況，也就是隨機策略( stochastic policy)。特別是策略改進理論在隨機策略也是成立的。此外，如果在類似4.9的策略改進步驟中有著多個actions可以得到最大值，在隨機情況下我們並不需要從中選擇一個。相反的，每個能夠得到最大值的action在新的greedy policy都會有一定的機率被選中。什麼都可以，只要給定其它submaximal actions機率0就好了。
Figure 4.1最後一個row：
Figure 4.1的最後一個row給出一個用於隨機策略(stochastic policies)的策略改進(policy improvement)的範例。原始的policy $\pi$是一個等機率的隨機策略(equiprobable random policy)，而新的policy $\pi'$則是一個對應於$v_{\pi}$的greedy policy。左邊的部份是value function $v_\pi$，右邊則是$\pi'$可能情況的集合。看的到，右邊圖中，一個格子(state)內有多個箭頭，這意味著這幾個actions在4.9這式子中都可以得到最大值；隨便你怎麼分攤機率給這些actions都是可以的。對於任意這類的policy，它的state value $v_{\pi'}(s)$透過檢查你可以看到就是-1、-2或-3($\forall s\in\mathcal{S}$)，但是在原始的policy $\pi$，最多就是-14。因此，$v_{\pi'}(s) \geq v_\pi(s), \forall s\in\mathcal{S}$，這說明了策略的改進。
## 4.3 Policy Iteration
一旦一個policy $\pi$利用$v_\pi$來生成一個更好的policy $\pi'$，那我們可以計算$v_{\pi'}$來生成更好的$\pi''$。因此我們可以得到一個不斷改進的policies與value functions的序列：
$$\pi_0 \space \xrightarrow{E} \space v_{\pi_o} \space \xrightarrow{I} \space \pi_1 \space \xrightarrow{E} v_{\pi_1} \space \xrightarrow{I} \space \pi_2 \space \dots \space \xrightarrow{I} \space \pi_* \space \xrightarrow{E} \space v_{*}$$
其中$\xrightarrow{E}$表示策略評估(policy evluation)，而$\xrightarrow{I}$則是策略改進(policy improvement)。每個policy都保證能夠得到比前一個policy更好的policy(除非前一個已經是optimal)。因為finite MDP的policy也是finite的，因此這個過程在有限的迭代次數中必然會收斂到optimal policy與optimal value function。
:::warning
計算出一個新的value，然後再根據這個value function來改進我們的policy，再利用這個policy得到新的value，然後再改進，最終保證收斂得到optimal policy。
:::
這樣子去找出optimal policy的方式稱為policy iteration。下面給完整的演算法：
注意到，每一次的策略評估都是一個迭代計算(從前一個policy的value function開始計算)。這通常會讓策略評估的收斂速度加快(應該是因為從一個policy到下一個policy的value function的變化比較小)。
策略迭代通常可以在很少次數的迭代就收斂，如下面Example 4.2與Figure 4.1所顯示。Figure 4.1的左下圖說明著這種等機率隨機策略(equiprobable random policyle random policy)的價值函數(vlue function)(value function)，右下圖則說明這種value function的greedy policy。策略改進理論保證了每個新的策略都會比原本的隨機策略還要好。在這個範例中，這些policies不只是好，而是最好的，能在最少步數中到達終止狀態(terminal states)。在這個範例中，策略迭代僅需一次迭代就可以找到optimal policy。
:::info
Example 4.2: Jack’s Car Rental
範例說的是，jack管理一家有兩個地點的汽車租賃公司，每天都會有人來租車。只要有車可以出租，每租一台出去就得到10元，沒車就沒搞頭。還車後的第二天，那台還回來的車就可以拿來出租。為了兩邊都有車可以用，jack會利用晚上來移動車子，每次的移動都需要2元的成本。我們假設每一個地點需求的汽車與歸還的汽車為Possion random variables([卜瓦松](https://zh.wikipedia.org/wiki/%E5%8D%9C%E7%93%A6%E6%9D%BE%E5%88%86%E5%B8%83)隨機變數)，意思就是數量$n$的機率為$\dfrac{\lambda^n}{n!}e^{-\lambda}$，其中$\lambda$是期望的數值。假設，兩地的出租需求$\lambda$是3跟4，然後歸還的是3與2。為了稍微簡化問題，我們再假設，每個地點最多就是20台車，多的就退回總公司，因此這個問題就是最多20台，然後一個晚上最多能移動的就是5台車。我們設置discount rate $\gamma = 0.9$，然後把這個問題弄成continuing finite MDP，time steps就是天(days)，state就是一天結束的時候每個地方擁有的汽車數量，然後actions就是晚上兩地移動的汽車的數量。Figure 4.2說明著從沒有移動任何車子的policy開始的policy iteration所找出的一系列的策略。
Figure 4.2：Jack汽車出租問題利用策略迭代找出來的一系列的策略與最終的state-value function。前五張圖說明的是，每天結束時，每一個地點的汽車數量從一個點被移到另一個點(負值就代表從sencond location移往first location，反之，正就是從first location移到second location)。每個後續的策略(successive policy)都是從前一個策略(previous policy)嚴格改進(strict improvement)而來的，然後最後一個是optimal。
:::
## 4.4 Value Iteration
策略迭代(policy iteration)的一個缺點就是每次的迭代都涉及策略評估(policy evaluation)，這需要多次掃過state set來迭代計算。如果策略評估是迭代處理的，那要確實的收斂到$v_\pi$就只有迭代無限次才有可能。不過，Figure 4.1已經顯示出，我們是可以截斷迭代，不用讓它一直跑下去。在該範例中也指出，三次迭代之後基本上對greedy policy已經沒有影響了。
事實上，策略迭代的策略評估步驟可以有多種方式可以截斷而不會失去策略迭代的收斂保證。有一種特殊的情況就是，只對每個state掃過更新一次就停止迭代。這樣子的演算法稱為value iteration。我們可以把它寫成一個結合策略改進與截斷策略評估步驟的式子，$\forall s\in\mathcal{S}$：
$$
\begin{align}
v_{k+1}(s) & \dot{=} \max_a \mathbb{E}[R_{t+1} + \gamma v_k(S_{t+1})\vert S_{t}=s, A_{t}=a] \\
&=\max_a\sum_{s',r}p(s', r\vert s, a)[r + \gamma v_k(s')]
\end{align} \tag{4.10}
$$
對於任意的$v_0$，相同條件下，也就是只要保存$v_*$存在的情況下，那序列$\left\{ v_k \right\}$就能夠收斂到$v_*$。
:::warning
從4.10來看，value iteration對每個state只做一次更新，而這一次的更新就只針對那個可以得到最大value的action的結果來更新。如果是先前的gridworld範例，我們要計算上、下、左、右然後加總計算四個action的value，但如果是value iteration的話就單純的是以最大value的那個action的結果來做為新的value。
:::
另一種瞭解value iteration的方式就是透過參照Bellman optimality equation 4.1。value iteration就只是把Bellman optimality equation轉為update rule。另外，value iteration update跟policy evaluation update(4.5)是一樣的，除了value iteration update要求的是所有的action都要是最大值的那一個。另一個方法就是去比較backup diagrams(policy evaluation)跟Figure 3.4左邊部份(value iteration)。這兩種方式是計算$v_\pi, v_*$很自然的一種倒推(回溯?)操作(backup operation)。
:::warning
* backup diagram
* Figure 3.4
:::
最後，要考慮的就是怎麼讓value iteration終止。如同policy evaluation，理論上value iteration需要無限次的迭代來確實的收斂到$v_*$，不過實際上如果value function只剩一咪咪的變動，那我們就會停止計算。下面給出這種終止條件完整的演算法：
在每次掃過所有資料的同時，value iteration會很效的結合policy evaluation sweep與policy improvement sweep。通常在每次的policy improvement sweep的時候插入多次的policy evaluation sweep可以收斂的更快。普遍來說，這整類的截斷策略迭代算法(truncated policy iteration algorithms)可以被想成是掃描序列，其中一些用policy evaluation更新，一些使用value iteration更新。因為這些更新的唯一差別就在於max的這個操作(4.10)，意思就是policy evaluation的某些掃描就加入這個max的操作就可以了。所有這些演算法在discounted finite MPDs都可以收斂到optimal policy。
:::info
**Example 4.3: Gambler’s Problem**
Figure 4.3: The solution to the gambler’s problem for ph = 0.4. The upper graph shows the value function found by successive sweeps of value iteration. The lower graph shows the final policy.
這範例說明的是一個賭徒去猜一系列的拋硬幣的結果。如果硬幣朝上，那賭徒就得到跟他這次下注一樣多的錢；如果硬幣朝下，那就輸了這次下注的錢。當賭徒贏100元或是輸到脫褲那就結束。每次拋硬幣，賭徒都需要決定要下注多少，而且是整數。這可以描述成一個undiscounted、episodeic、finite MDP的問題：
* state：賭徒的資金，$s\in \left\{1,2,3,...,99 \right\}$
* action：下注的金額，$a\in\left\{0,1,...,\min(s, 100-s) \right\}$
* reward：達到目標(贏100元)的時候+1，其它狀態轉移的時候皆為0
state-value function會給出每一個state賭徒會贏的機率。這邊的policy是賭徒資金到下注的映射。optimal policy會最大化達到目標的機率。
假設，$p_h$表示硬幣會是正面的機率。如果$p_h$已知，那整個問題就可以求解了，像是用value iteration來求解。Figure 4.3說明了value iteration連續掃描過程中的value function的變化，以及找到最終的policy($p_h=0.4$)。policy是最佳的(optimal)，但並非是唯一的。事實上optimal policies有一堆，具體取決於能夠最大化value function的那個action的選擇(argmax action)。
:::
### 4.5 Asynchronous Dynamic Programming
先前提過DP的一個缺點就是，它的操作涉及MDP的整個state，也就是說DP需要掃過狀態集合(state set)。如果這個state set非常大，那就算只做一次的掃描所費的計算成本也是非常高。像是雙陸棋就有$10^{20}$個state，就算可以每秒做一百萬個state的value iteration update，你還是需要一千多年的時間才能完成一次的掃描。
非同步的DP演算法是一種in-place iterative DP algorithms，而不是那種系統性按序掃過整個state set的作法。這種演算法用任意可用的其它的狀態值來以任意順序更新狀態值。這種作法可能有的狀態的值只被更新一次，但其它的狀態的值可能已經被更新很多次。不過為了能夠正確的收斂，非同步演算法要能夠持續的更新所有狀態的值(value of states)：計算中經過幾個點的時候，它就不能忽略任一個狀態。也因此，非同步動態規劃演算法在選擇那一個狀態要更新的這部份有很大的靈活性。
舉例來說，asynchronous value iteration的一種作法就是使用公式4.10，在每個step $k$的時候就用in-place的方式只更新一個state $s_k$。如果$0\leq \gamma < 1$，只要所有的state都能夠出現在序列$\left\{ s_k \right\}$中無限次，那就保證可以漸近的收斂到$v_*$。類似的，混合policy evaluation與value iteration updates來產生一個新的asynchronous truncated policy iteration(非同步截斷策略迭代?)也是有可能的。不過這超出本書範圍，因此後續不會再有深入討論。不過很明顯可以看的出來，不同的更新方式可以在各種sweepless DP algorithm中靈活的搭配使用。
:::warning
這邊說的似乎是在每個time step $k$的時候就更新在這個time step遇到的state $s_k$。最後說的應該是更新方式可以在不需要遍歷整個狀態集的情況下搭靈使用。
:::
當然，避免整個掃描並不代表我們可以減少一些計算。這只是意謂著演算法不用去卡在那個長時間掃描的情況才能讓policy得到一些改進。我們可以試著透過選擇我們要更新的那個狀態(state)來更新，利用這種靈活性從而提高演算法的的速度。我們也可以試著去排序更新的順序，讓值信息(value information)可以更有效的在狀態間傳播。有些state可能不是那麼需要那麼常更新。如果某些state與最佳行為無關，或許我們也可以試著完全跳過更新它們。後續Chapter 8會有說明。
非同步的演算法讓計算與實時交互的結合變的簡單。為了求解給定的MDP，我們可以在agent實際經歷MDP的同時執行一個迭代動態規劃演算法(iterative DP algorithm)。agent的經驗可以用來決定DP演算法要去更新那一個state。同時，來自DP演算法的last value(最新的值)與policy information(策略信息)就可以用來指導agent的決策。舉例來說，我們可以在agent visits某一個state的時候去更新它(被visit的那個state)。這樣就可以讓你的DP演算法的更新聚焦在與agent最相關的狀態集合(state set)身上。這樣的聚焦是強化學習中不斷重覆的主題。
## 4.6 Generalized Policy Iteration
policy iteration包含兩個同時交互的過程，一個讓value function與當前的policy是一致的(policy evaluation)，另一個讓policy根據當前的value function做出greedy的的選擇(policy improvement)。在policy iteration中，這兩個過程的進行是交互的，也就是一個開始之前另一個要先結束，不過這並不是一定要的。舉例來說，在value iteration中，每次的policy improvement過程之間只做一次的策略評估(policy evaluation)的迭代。在非同步的動態規劃方法中，評估(evaluation)與改進(improvement)的過程以更細的粒度(finer grain)在交互的。有些情況下甚至在一個程序中只會更新一個state就跳到另一個執行程序。只要兩個流程都持續的更新所有的states，最終的結果通常還是一致的，也就是收到到optimal value function與optimal policy。
剛剛我們用generalized policy iteration(GPI)這個術語來表示policy-evaluation與policy-improvement這兩個交互過程的一個籠統的想法，這個兩個流程的粒度與其它細節無關。幾乎所有的強化學習方法都可以被描述為GPI。意思是說，所有的方法都存在合理的policies與value functions，policy根據value function改進，然後value function會向著policy的value function前進，如下圖所示：
如果evaluation與improvement這兩個流程都穩定且不再變化，那value function與policy就會是optimal。value funciton的穩定只會發生在它與當前的policy是一致的情況，而policy也只有在它對當前value function是採取greedy的時候才會穩定。因此，兩個流程的穩定只有在policy發現它對自己的evaluation function是greedy的才會發生。這明顯說明了Bellman optimality equation(4.1)是成立的，然後policy與value function都是optimal。
GPI中，evaluation與improvement這兩個流程可以視為是競合關係。競爭說的是它們朝著不同方向前進，所以互相拉扯。通常你讓policy對value function變成greedy會讓value function與變動後的policy無法匹配，而你讓value function與policy變的一致也會讓policy不再是greedy。不過長時間來看，這兩個交互過程會找到一個單一的聯合解，也就是optimal value function與optimal policy。
我們也許可以把GPI中evaluation與improvement之間的交互作用視為兩個約束或是目標，如下二維空間中的兩條線所示：
雖然實際的情況可能更為複雜，但也足以用來說明了。每一次的流程都驅動著value function或是policy往代表其中一個目標的線前進。因為這兩條線並不是正交的(orthogonal)，所以兩個目標就是會交互作用。你往一邊去就會遠離另一邊的目標，但是最終，整個聯合過程就是會讓你接近optimal這個總體目標。圖上的箭頭就說明著policy iteraion的行為，每個箭頭說明的是每次迭代都會把系統帶往完全實現兩個目標的其中一個。當然在GPI中我們可以走小步一點，部份的完成其中一個目標。無論如何，盡管沒有直接去實現它，但這兩個過程還是會共同去實現最佳的總的目標。
## 4.7 Efficiency of Dynamic Programming
這一章在下只挑三撿四的簡單說明。總體來說，雖然DP不適合用於大規模的問題，但實際上它的效率與其它解MDP的方法相比是快多的。DP有時候會受限於維度問題，也就是維度災難的問題，這問題來自於state的總數量過於龐大所造成，但這並非是DP這種解決方法本身的問題，而是任務本身的問題。實際應用中，現今的計算能力來採用DP的話，可以處理擁有數百萬states的MDP問題。而對於有比較大的state space的問題，採用非同步動態規劃方法是一個不錯的選擇。
## 4.8 Summary
這一章我們已經瞭解用動態規劃來解MPD的基本想法。policy evaluation意謂著給定一個policy情況下迭代計算value function。policy improvement則意謂著給定一個策略(policy)的value function情況下計算其改進的策略(policy)。把這兩個計算放在一起，我們就得到policy iteration與value iteration，也是兩個最常用的DP方法。這兩個方法的任一個都可以在給定MPD完整信息情況下計算finite MPD的optimal policies與value function。
傳統的DP方法會掃過整個state set，然後在每一個state都做expected update(期望更新?)的操作。這類的更新操作(更新state的value)都是基於後續所有可能的state與它們可能出現的機率。expected updates與Bellman equation息息相關：只是將等號轉為賦值語句。當updates不再有值的變化的時候，那就代表已經收斂，而且已滿足Bellman equation。就像你有四個主要的value functions，$v_\pi, v_*, q_\pi, q_*$，有四個相對應的Bellman equation與四個相對應的expected updates。backup diagrams給出DP更新操作的一個直觀表述。
當你把DP以GPI(generalized policy iteration)的角度來看的時候，你就可以深入瞭解DP跟幾乎所有的強化學習方法。GPI的想法是圍繞在近似策略(approximate policy)與近似值函數(approximate value function)的兩個交互過程。一個流程是依據給定的policy來做某種形式的policy evaluation，讓value function變的更像是這個policy實際的value function。另一個流程則是依據給定的value function來做某種形式的policy improvement，在假設這個value function就是這個policy的value function情況下，讓這個policy愈來愈好。
:::warning
| Problem | Bellman Equation | Algorithm |
| -------- | -------- | -------- |
| Prediction | Bellman Expectation Equation | Iterative Policy Evaluation |
|Control|Bellman Expectation Equation + Greedy Policy Improvement| Policy Iteration|
|Control|Bellman Optimality Euqation|Value Iteration|
這一章節談的都是planning的問題，因為案例中的MDP都是已知的。
Prediction談的是，給定一個policy，我們希望知道我們可以得到多少的reward，這一部份我們使用Bellman Expectation Equation，最終可以得到$v_\pi$，這就是policy evaluation。
Control有兩種方式，policy iteration、value iteration。兩種方式想做的都是希望可以讓reward愈大愈好，目標是找到$v_*$。
:::
:::warning
更多關於Poisson distribution可以參考翁秉仁老師的[Poisson 分配、指數分配與排隊理論](http://episte.math.ntu.edu.tw/applications/ap_poisson/index.html)
:::
Sign in with Wallet
Connect another wallet