# Reinforcement Learning: An Introduction_Chapter 5 Monte Carlo Methods
###### 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)

這一章算是開始提到第一個量測value function的學習方法，還有如何尋找optimal policies。

Monte Carlo不需要完整的關於environment的先驗知識，它需要的是經驗(experience)，也就是利用與實際或模擬的environment互動過程中樣本的states、actions、reward的序列，儘管如此，它還是可以達到最佳行為(optimal behavior)。這種從模擬經驗中學習的方式也是很強的。雖然這種方法需要一個模型，不過它並不需要像DP一般的需要所有可能轉移的機率分佈，只需要樣本的轉移資訊。雖然多數情況下這很難以顯示形式得到分佈，但還是能夠依據期望的機率分佈生成經驗樣本。

Monte Carlo method解決強化學習的問題是基於平均樣本的returns。為了確保明確定義returns是可行的，這邊我們定義的Monte Carlo method只針對episodic tasks。也就是我們假設經驗可以分成episode，而且不管選擇怎麼樣的action，所有的episode都會終止。只有在episode完成的時候才會做價值(value)的估測與策略(policy)的改變。因此Monte Carlo methods的改進是episode-by-episode，而不是step-by-step(online)。這邊指出，Monte Carlo泛指任何包含大量隨機成份的估測方法。

Monte Carlo methods跟第二章提到的bandit methods類似，採樣，然後平均state-action pair的returns，然後平均每一個action的rewards。最大的差別在於，我們有多個states，每個state都像是一個不同的賭博機(bandit)問題，然後每個不同的賭博機問題都是相關的。意思就是，在一個state採取一個action之後得到的return是取決於在相同的episode中後續的states所採取的actions。因為所有actions的選擇都是在學習，因此從早期的state來看，這問題是不穩定的。

為了處理這個不穩定的問題，我們採用Chapter 4，用於動態規劃(DP)的general policy iteration(GPI)。不同的是，在DP中，我們是從MDP的知識(knowledge)中計算value functions，在Monte Carlo我們是從MDP的sample returns來學習value function。我們會先考慮預測問題(prediction problem)(以任意一個固定的policy $\pi$計算$v_\pi, q_\pi$)，再考慮策略改進(policy improvement)，最後才是控制問題，然後利用GPI求解。

:::warning
上面的說明會非常建議自己動手寫一次程式會對整個論述更有感覺，簡單來說，在Chapter 4中，我們會需要把在某一個state上的所有可能的action都利用bellman euqation計算過之後來得到這個state的value。但是在MC中我們不需要這麼做，我們會從sample到的經驗去學習。
:::
## 5.1 Monte Carlo Prediction
我們要開始來看看Monte Carlo在給定policy學習state-value function。state的value就是expected return(期望收益)，也就是從這個state開始我們所期望的累積未來折扣報酬(expected cumulative future discounted reward)。觀察到愈多的returns，那平均值就愈能收斂到期望值。這就是所有Monte Carlo的基礎。

假設我們要推估$v_\pi(s)$，按著policy $\pi$遇到state $s$的value，也就是給定依著$\pi$，然後經過state $s$所獲得的episodes的集合。在一個episode裡面，每次遇到state $s$就稱做對$s$的一個visit。而一個episode是可能對一個state $s$有多次的visit。一個episode內對$s$的第一次的visit稱為first visit。

這衍生出兩種方法：
* first-visit MC method
* 按著對state $s$的first visits來計算returns的平均的方式推估$v_\pi(s)$
* 已經被廣泛的研究，也是本章關注的部份
* every-visit MC method
* 按著對state $s$的all visits來計算returns的平均的方式推估$v_\pi(s)$
* 能夠更為自然的泛化到函數近似(function approximation)與eligibility traces(翻資格軌跡怪怪的?)

下面給出First-visit MC的pseudo code：

* Every-visit MC的唯一差別就是不需要確認$S_t$是否存在該episode的早期階段出現過
* 當$s$的出現次數(或first visit)趨近無限，兩種演算法都會收斂至$v_\pi(s)$，這對first-visit MC是顯而意見的一種結果
* 每一個return都是對$v_\pi(s)$獨立同分佈(i.i.d)的推估，並且變異數是有限的
* 根據大數理論，平均值最終會收斂至期望值
* 每次的均值都是一個無偏估計(unbiased estimate)，其誤差的標準差會以$1/\sqrt{n}$衰減，其中$n$代表被平均的returns的數量(計算returns裡面reward的長度?)，這個結論在Every-visit上不是那麼明顯，但它還是會被二次收斂到$v_\pi(s)$

:::info
### Example 5.1: Blackjack
以21點為例，雖然大家應該都知道怎麼玩，不過還是說明一下規則(假設每一個玩家跟庄家都是獨立在玩)：
1. 牌不能超過21
2. J、Q、K都是10
3. A可以當1也可以當11
4. 開場每人發兩張牌，各露一張牌、蓋一張牌
5. 如果玩家直接21點，那就是天胡，除非另一方也是天胡，不然就是直接贏了
6. 玩家不是天胡的情況下可以一直要牌，但牌點不能超過21
7. 換庄家要牌，直到大於等於17的時候停牌，如果庄家爆牌那就玩家贏

21點是一種典形的episodic finite MDP。每一張牌局都是一個episode，贏牌reward +1，和局 +0，輸了 -1。遊戲中的reward皆為0，並且這邊我們不計算discount，也就是$\gamma=1$，因此最終的reward也是returns。

玩家的actions有兩個：
1. 要牌
2. 停牌

state則是取決於玩家與庄家顯示的牌。我們假設這是一個無限牌堆(也就是抽完放回)，因此不需要記憶那些牌已經被抽。如果玩家有A，那不會爆的情況下可以把A視為11，我們稱這個A為usable。這時候通常將A視為11，如果視為1的話，那牌最多小於等於11(1+10)，這時候不用選擇，可以直接要牌，抽牌隨便抽都大於11，一定更好。因此，玩家會依據三個變數來做出決定：玩家當前的總合(12-21)，庄家顯示的牌組(A-10)，以及玩家是否有usable A。如此，總共有200個states(10x10x2?)。

考慮一種policy，當玩家的牌點總合為20或21的時候就停牌，不然就要牌。為了能夠利用MC(後續以MC表示Monte Carlo method)來找出這個policy的state-value function，我們用這個policy來模擬很多場21點的賽局，然後平均每一個state的returns。

最終我們得到如Figure 5.1(下圖)state-value function的推估結果。左上圖可以看的出來，有usable A的情況是較不穩定的，不過不管是那一種情況，在500000局之後，state-value function都得到很好的近似。


:::

雖然這個任務我們有著完整的環境知識，不過這種情況下即使使用DP也沒有辦法輕易的計算value function。因為DP需要知道next events的分佈，它們需要four-argument function $p$給出的環境動態(environments dynamics)，在這個任務中，這並不好確定。

:::warning
快速回憶$p$：
$$\sum_{s'\in\mathcal{S}} \sum_{r\in\mathcal{R}}p(s', r \vert s, a) = 1 \text{ for all } s \in \mathcal{S}, a\in\mathcal{A}(s) \tag{3.3}$$
:::

舉例來說，玩家有14點，然後選擇停牌，那根據庄家顯示的牌，玩家最終以reward +1結束的可能性有多少?使用DP之前我們必需要計算所有這些的機率。但這樣的計算通常是複雜而且容易出錯。相反的，利用MC來生成一些遊戲樣本是簡單的，即使有著環境動態的完整知識，MC處理sample episodes的能力也是有明顯的優勢。

我們是否可以將backup diagrams的想法泛化到MC algorithms?backup diagram的基本概念是最上面是預計更新的root node，其下面則是transitions(state的轉換)與leaf nodes，其rewards與推估的values則是更新的時候使用。

對於MC的$v_\pi$的推估，root的部份是state node，下面則是它的完整特定單一個episode的轉移軌跡(trajectory)，在terminal state的時候結束，如下圖所示：

這邊整理利用diagrams來看出兩種方式的差異：

| 方法 | transitions | diagram step |
| -------- | -------- | -------- |
| DP diagram | 所有可能的轉移 | one-step |
| MC diagram | 當前episode的那些轉移 | 到這個episode結束前的所有的轉移 |

有一個很重要的事實，那就是MC對每一個state的估測都是獨立的。意思就是一個state的估測跟其它的state是毫不相干的，這點與DP是一樣的。這跟前幾章所說的bootstrap是不一樣的。

值得注意的是，推估一個state的value的計算成本與state的數量是無關的。這讓MC在只需要一個state或是一個state的subset的時候特別有吸引力。我們可以從感興趣的states開始生成許多sample episodes，只從這些states計算平均的returns，而忽略所有其它的states。這就是MC比起DP所擁有的第三個優勢(另外兩個是從實際經驗與模擬經驗中學習)。

:::info
### Example 5.2: Soap Bubble
假設把一個閉合的線框泡在肥皂水中，然後它沿著邊緣形成一個肥皂泡泡。

這邊回頭再來看，先讀下去。
:::

## 5.2 Monte Carlo Estimation of Action Values
如果模型不可用，那估測action values(state-action pair)會比state values來的有效。使用模型的情況下，單靠state value就足以確定policy；如DP那章說過的，只需要向前看一步(one step)，然後選擇看那一個action可以得到最佳的組合(next state and reward pair)。但在沒有模型的情況下，單靠state value是不足的。我們必需要明確的估測每個action value，這樣這些values對policy才會有幫助。這邊我們就要用MC來估測$q_*$，為此我們要來考慮action values的策略評估問題。

action values的策略評估問題就是推估$q_\pi(s, a)$，也就是用著policy $\pi$，在state $s$的時候選擇action $a$的預期收益(expected return)。這問題的本質上跟剛才提的state values的問題是一樣的，差別就在一個是state，一個是state action pair。

如果在一個episode中，遇到state $s$的時候選擇了action $a$，那我們就說這個state-action pair $s, a$它們在這個episode被visited。所以一樣延伸出兩種模式：
* every-visit MC，用每一次，那個state-action pair被visit過的returns來計算平均
* first-visit MC，用每一個episode，那個state-action pair第一次被選到的returns來計算平均

一樣的，visits的次數愈多，多到無窮無盡的時候，這個平均值就會接近實際的期望值。

這邊比較有問題的是，有些state-action pair可能一輩子不會被看到，這問題大啦，沒看過的東西怎麼去利用經驗來優化，學習action value就是為了能夠在每個state的可用actions做選擇。為此，我們要估測來自每一個state的所有actions的values，而不只是只對當前偏好的action估測。

記得我們在Chapter 2說過的觀念，要maintaing exploration，也就是保持好奇心。為了能夠讓策略評估(policy evaluation)對action values可以發揮作用，我們要保持好奇心並且不斷探索。一種方法是指定state-action pair做為episode的開始，然後每一個pairs都有被選來當做開始的非零機率。這樣子，只要你的episodes是無窮無盡的，那所有的state-action pairs也會被看過(visited)無限次。這樣子的方法稱為exploring starts。

這種作法有效，但有時候也不是那麼有效，尤其是與環境互動直接學習的情況特別不好。另一種方法就是確保每一個state-action pair都可以有非零的機率被選到。這後面會有更詳細的說明。這邊會先以exploring starts做為說明，然後完成完整的Monte Carlo Control method。

## 5.3 Monte Carlo Control
我們已經準備在control問題中使用Monte Carlo estimation，就是近似最佳策略(approximate optimal policies)。總體來看就是使用DP(Chapter 4)中提過的generalized policy iteration(GPI)。在GPI，我們會同時去維護approximate policy與approximate value function。如下圖所示，value function會反覆的修正來更接近當前策略的近似價值函數(approximate value function)，然後策略(policy)會根據當前的價值函數(value function)來反覆的改進。這兩個過程某種程度上是互相影響的，但總體來說是會讓policy與value function趨於最佳。


現在先來看看MC版本經典的policy iteration。我們會執行策略評估(policy evaluation)與策略改進(policy improvement)的交替完成的步驟，從$\pi_0$開始到optimal policy與optimal action-value function結束：
$$\pi_0 \space \xrightarrow{E} \space q_{\pi_o} \space \xrightarrow{I} \space \pi_1 \space \xrightarrow{E} q_{\pi_1} \space \xrightarrow{I} \space \pi_2 \space \dots \space \xrightarrow{I} \space \pi_* \space \xrightarrow{E} \space q_{*}$$

其中$\xrightarrow{E}$表示完整的策略評估，$\xrightarrow{I}$表示完整的策略改進。策略評估就跟前幾章所說的一樣。經歷很多個episodes，這樣近似的動作價值函數(approximate action-value function)就會漸近的接近實際的動作價值函數。現在，我們假設我們確實的觀察到無限多的episodes，而且這些episodes是由exploring starts所產生的。在這種假設下，MC可以對任意的$\pi_k$精確的計算每一個$q_{\pi_k}$。

策略改進(policy improvement)可以用policy greedy來完成(對應當前的value function)。我們有一個action-value function，因此我們不需要模型來建構greedy policy。對於任意的action-value function $q$，對應的greedy policy就是，對每一個$s \in \mathcal{S}$，就是選擇那個最大的action-value：
$$\pi(s) \dot{=} \arg \max_a q(s, a) \tag{5.1}$$

:::warning
我們已經有action-value function，所以我們不需要像DP一樣需要一個model來做那麼多的計算，直接從action-value function中找出最大的那一個pair就是了。
:::

然後就可以利用將每一個$\pi_{k+1}$構建為對應於$q_{\pi_k}$的greedy policy來做策略改進。這樣，Section 4.2的策略改進定理可以用在$\pi_{k}$與$\pi_{k+1}$，因為，對於所有的$s \in \mathcal{S}$，
$$
\begin{align}
q_{\pi_k}(s, \pi_{k+1}(s)) &= q_{\pi_k}(s, \arg\max_a q_{\pi_k}(s, a)) \\
&= \max_a q_{\pi_k}(s, a) \\
& \geq q_{\pi_k}(s, \pi_k(s)) \\
& \geq v_{\pi_k}(s)
\end{align}
$$

:::warning
* 第一個等式是對應說明的第一句話，也就是『將每一個$\pi_{k+1}$構建為對應於$q_{\pi_k}$的greedy policy來做策略改進』，因為我們要做這樣的構建。這對應公式5.1，我的action本身就是根據action-value function來決定的
* 第二個等式，既然是greedy那一定是最好的
* 第三、第四可以從第四章的策略改進理論得證
:::

這樣我們就可以確保$\pi_{k+1}$一定比$\pi_k$好，不然就是會跟它一樣好，不管如何，這兩種情況都是最佳策略(optimal policies)。這保證整個過程是可以收斂到optimal policy與optimal value function。即使你只擁有sample episodes，沒有其它關於環境動態的其它知識，你也可以用MC來找到optimal policies。

上面我們也做了兩個不大可能的假設(強烈的假設)，這是為了能夠保證得到MC的收斂性：
1. episodes為exploring starts
2. 會有無限次的episodes來做policy evaluation

不過為了能夠得到一個實際可用的演算法，我們必需去除掉這兩個假設。我們先討論第2點，也就是會有無限次的episodes的這件事。相同的問題在DP中像是iterative policy evaluation也只是漸近的收斂到實際的value function。在DP跟MC有兩個方法可以解決這個問題：
1. 持續的在每一次的策略評估(policy evaluation)中去近似$q_{\pi_k}$，利用測量並假設可以獲得在估計值中誤差的大小與機率的界限，然後在每一次的策略評估中採取足夠多的steps來確保這些bounds(界限)夠小。這樣的方法可以得到令人滿意的近似，不過這個即使面對的問題(任務)不大，也需要有足夠多的episodes才能用。
2. 這種方法可以不需要無限多的episodes，也就是放棄在策略改進(policy improvement)之前完成策略評估(policy evaluation)。在每一個評估步驟(evaluation step)中，我們讓value function接近$q_{\pi_k}$，這需要很多次才能真正的接近(Section 4.6的GPI也是這樣的概念)。這個想法的一種極端形式就是value iteration(值迭代)，也就是在每一次的策略改進(policy improvement)的步驟(step)之間，我們只做一次的iterative policy evaluation。value iteration的in-place是更極端的版本；在單一狀態(single states)中交替做策略改進與評估。

MC policy iteration很自然的可以在episode-by-episode基礎上做evaluation與improvement之間的交替進行。在每個episode之後，觀察到的returns會用來做policy evaluation，然後在該episode內的所有看過(visited)的states做策略的改進。下面給出pseudo code，我們稱為Monte Carlo ES，也就是Monte Carlo with Exploring Starts：

在Monte Carlo ES中，每一個state-action pairs的所有的returns都會被累積與平均，不論觀察到的是那一個policy。很明顯的，Monte Carlo ES不會被收斂到任何一個suboptimal policy。如果會收斂到suboptimal policy，那value function最終就會收斂到那個policy的value function，進而導致policy的變化。只有在policy與value function都是optimal的時候才會達到穩定。由於action-value function的變化隨著時間的推移而減少，收斂到這個optimal fixed point看似必然，不過這點還沒有得到正式的證明。

:::info
### Example 5.3: Solving Blackjack
現在我們來把Monte Carlo ES用在剛剛的二十一點的範例，這很簡單。因為這些episodes都是模擬遊戲(simulated games)，因此很輕易的可以安排包含所有可能的exploring starts。這種情況下只需要簡單的隨機選擇發牌人員的牌，玩家的總合與玩家是否有usable ace。我們用上一個範例的policy來做為初始的policy(僅適用20或21點停牌)。所有的state-action pairs的初始皆為零。Figure 5.2給出利用Monte Carlo ES找出的optimal policy。基本上這個policy與Thorp(1966)的"basic" strategy是一樣的，唯一的例外是策略中用於usable ace最左邊的[凹口](http://terms.naer.edu.tw/detail/138699/)，這在Thorp的策略中是沒有的。我們不確定造成這個差異的原因，但我們確信這是我們描述的二十一點遊戲版本中的最佳策略(optimal policy)。


:::

## 5.4 Monte Carlo Control without Exploring Starts
這邊要說明的是如果避免使用exploring starts這個假設。唯一的方法就是確保agent會無限次的選擇所有的actions。有兩種方法可以實現：
1. on-policy
* 上面說到的Monte Carlo ES屬於這種方法
* 嚐試評估或改進用於決策的策略
2. off-policy
* 嚐試評估或改進的策略與用於生成資料的策略是不同的

下面整理說明：
* policy通常為soft，意謂著$\pi(a\vert s) > 0, \forall \space s \in \mathcal{S}, \space \forall \space a \in \mathcal{A}(s)$
* 會逐漸的接近確定性的optimal policy，第二章提過的很多方法都可以做到這一點，這一章會使用$\epsilon$-greedy policy，也就是大多時間都會選擇最大估值的那個action，但是會有$\epsilon$的機率採用隨機選擇。
* nongreedy的action會有$\dfrac{\epsilon}{\vert \mathcal{A}(s) \vert}$的機率被選中，選擇greedy action的機率為$1-\epsilon+\dfrac{\epsilon}{\vert \mathcal{A}(s) \vert}$
* $\epsilon$-greedy是$\epsilon$-soft的一種範例，其策略(policy)就是對某些$\epsilon>0$，對所有的states與actions都有$\pi(a\vert s) \geq \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert}$。
* 所有的$\epsilon$-soft裡面，就$\epsilon$-greedy最接近greedy
* on-policy Monte Control的整體概念仍然是GPI

:::warning
1. 所謂的soft policy，在[討論區]([https://](https://stats.stackexchange.com/questions/342379/what-are-soft-policies-in-reinforcement-learning))有看到有人說明如下：『A "soft" policy is one that has some, usually small but finite, probability of selecting any possible action.』，大概的意思就是人人有機會這樣子。搭配整理的第一點就很清楚，對每個state $s$的每個$action$的機率都是$\pi(a\vert s) > 0$
2. $\vert \mathcal{A}(s) \vert$指的就是該state下的action數量，假設$\epsilon=0.3, \vert \mathcal{A}(s) \vert=4$，那每一個action都會有$0.3/4=0.075$的機率被選中，然後最好的那一個action被選中的機率就是$1-0.3+0.075=0.775$，減$0.3$是因為這被拿去分了，加$0.075$是因為人人有機會，這是那個最好的action原本就會有的機會
3. 上面第四點的說明只是呼應第一點，每個人都有微小的機率會被選中
:::

如Monte Carlo ES，我們使用first-visit MC來對當前的policy估測action-value function。因為沒有exploring starts這個假設，所以我們沒有辦法就只是靠著對當前value function的greedy來改進policy，否則就無法進一步的對nongreedy的actions做嚐試。幸運的是，GPI沒有一定要一直採取greedy，而只是要求將其轉向greedy policy。在我們的on-policy方法中，我們只會讓它變成$\epsilon$-greedy policy。對於任意$\epsilon$-soft policy，$\pi$，關於$q_\pi$任意的$\epsilon$-greedy polciy都能保證比$\pi$還要好(或一樣好)。完整的演算法如下：


根據policy improvement theorem我們知道，任意$q_\pi$的$\epsilon-$greedy policy都是對任意$\epsilon-$soft policy $\pi$的改進。假設$\pi'$是$\epsilon-$greedy policy。那策略改進定理(policy improvement theorem)能夠適用是因為對於任意的$s\in\mathcal{S}$：
$$
\begin{align}
q_\pi(s, \pi'(s)) &= \sum_a \pi'(a\vert s)q_\pi(s,a) \\
&= \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_aq_\pi(s,a) + (1-\epsilon)\max_a q_\pi(s,a) \\
& \geq \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_a q_\pi(s, a) + (1 - \epsilon) \sum_a \dfrac{\pi(a\vert s)-\dfrac{\epsilon}{\vert \mathcal{A}(s) \vert}}{1-\epsilon} q_\pi(s,a) \\
&= \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_aq_\pi(s,a) - \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_aq_\pi(s,a) + \sum_a \pi(a\vert s)q_\pi(s, a)\\
&= v_\pi(s)
\end{align} \tag{5.2}
$$

(第三個公式有著說明：其總和是非負權重總和為1的加權平均值，因此它必須小於或等於最大平均值。)

根據策略改進定理，$\pi' \geq \pi$(即$v_{\pi'}(s) \geq v_\pi(s) \forall s \in \mathcal{S}$)。

現在我們證明只有在$\pi'$與$\pi$都是屬於$\epsilon-$soft policies的時候，這個等式才會成立，也就是當它們都比其它$\epsilon-$soft policies還要好、或更好的時候就會成立。

設想一個很像原始環境(original environment)的新環境，唯一的不同在於我們要求將屬於$\epsilon-$soft的policy"移入"environment。這個新的environment跟original environment有著想同的action與state set，並且有著下面的行為：
* 如果在state $s$選擇action $a$，new environment會有$1-\epsilon$的機率有著與original environment一樣的行為
* 會有$\epsilon$的機率重新隨機選擇一個action(以同等機率)，然後這個隨機選擇的action的行為在new、old environment都是一樣的
* 在這個具通用性策略(general policies)的new environment中能做最好的那個action跟具有$\epsilon-$soft policies的original environment的action是一樣的

我們以$\tilde{v}_x, \tilde{q}_x$來表示new environment的optimal value functions。然後在$v_\pi = \tilde{v}_*$的時候(若且為若)，policy $\pi$就會是$\epsilon-$soft policies中最好的那一個。從$\tilde{v}_*$的定義我們可以知道它的唯一解就是：
$$
\begin{align}
\tilde{v}_*(s) &= (1-\epsilon) \max_a \tilde{q}_*(s, a) + \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_a \tilde{q}_*(s,a) \\
&= (1-\epsilon)\max_a \sum_{s',r}p(s', r\vert s, a) \left[ r + \gamma \tilde{v}_*(s')\right] + \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_a\sum_{s', r}p(s', r \vert s, a)\left[ r + \gamma \tilde{v}_*(s')\right]
\end{align}
$$

當等式成立且$\epsilon-$soft policy $\pi$不再改善的時候，那從5.2我們就可以知道：
$$
\begin{align}
v_\pi(s) &= (1-\epsilon)\max_a q_\pi(s, a) + \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_a q_\pi(s, a) \\
&= (1-\epsilon)\max_a \sum_{s', r}p(s', r \vert s, a) \left[ r + \gamma v_\pi(s') \right] + \dfrac{\epsilon}{\vert \mathcal{A}(s) \vert} \sum_a\sum_{s', r}p(s', r \vert s, a) \left[ r + \gamma v_\pi(s') \right]
\end{align}
$$

基本上這個等式跟上面那個是一樣的，只是拿$v_\pi$去替代掉$\tilde{v}_*$。而因為$\tilde{v}_*$是唯一解，因此$v_\pi=\tilde{v}_*$一定成立。

就這樣，我們已經說完將policy iteration用於$\epsilon-$soft policies是可行的。把greedy policy的原生概念應用在$\epsilon-$soft policies上，除了可以發現最佳的policy存在於$\epsilon-$soft policies之外，還可以確保每一個step都可以改進。這種方析方式跟action-value functions如何在每一個階段被定義是無關的，但確實是假設它們都是被精確計算的。這跟上一章得到的結果差不多。雖然現在我們只得到$\epsilon-$soft policies中最好的policy，不過換個角度來看，我們已經不再需求exploring starts這個假設了。

## 5.5 Off-policy Prediction via Importance Sampling
所有的學習控制方法都面臨一個困境：他們希望可以學到一個可以讓後續的行為是最佳的action，但為了能夠探索所有的actions(為了找到optimal actions)，它們必需要去做non-optimally的action。他們如何能夠根據一個探索性的策略來學到最佳策略?前面章節所說的on-policy方法是一種妥協-它並不是從optimal policy學習action values，它是從一個接近最佳且能夠繼續探索的方式來學習。有一種更直接的方式，就是使用兩個policies，一個用來學習成為optimal policy，另一個則是更加擁有探索性，並且用它來生成agent的行為。用來學習policy的稱為target policy，而用來生成行為的則稱為behavior policy。這種情況我們說『learning is from data “off” the target policy』， 大致就是你並沒有直接的從資料去學習，那就是off policy。

On-policy通常比較簡單，容易聯想。off-policy則是需要額外的概念跟符號，而且因為資料是來自不同的policy，off-policy通常會有比較大的variance，收斂的比較慢，但是更通用。on-policy也可是off-policy的特例，就剛好target、behavior這兩個policy是一樣的。off-policy有多種應用，而且被視為是學習外部世界動態性的多步預測模型(multi-step predictive model)的關鍵。

我們會從prediction problem開始瞭解off-policy，然後先假設target與behavror這兩個policies都是固定的。意思是說，假設我們希望可以估測$v_\pi$或是$q_\pi$，但是我們手上有的就只有依著policy $b$得到的episodes的資料，重要的是$\pi \neq b$。這種情況下，$\pi$是target policy，而$b$是behavior policy，而且兩個policies都是固定而且已知的。

為了能夠用從$b$得到的episode資料來估測$\pi$的values，我們需要每一個在$\pi$選擇過的action都可以在$b$那邊偶爾也選擇一下，意思就是$\pi(a\vert s) > 0$，且$b(a\vert s) >0$。這種假設稱為coverage(覆蓋假設?)。從這假設我們可以知道，在$b$與$\pi$的state不同情況下，$b$就隨機選擇一個action。另一方面，target policy可能是確定性的，事實上這是控制應用(control applications)裡面一個有趣的特殊情況。控制過程中，target policy通常為確定性的貪心策略(deterministic greedy policy)，由action-value function依據當前估測所決定。這個策略(policy)在行為策略(behavior policy)保持隨機且更具探索性的時候會變為確定性的最佳策略(deterministic optimal policy)，像是$\epsilon-$greedy policy。不過這一章我們就只考慮$\pi$不變且已知的預測問題。

幾乎所有的off-policy的方法都採用[重要性抽樣](http://terms.naer.edu.tw/detail/3649635/)(importance sampling)，這是一種給定樣本的情況下去計算另一個分佈的期望值的作法。因此，我們把重要性抽樣用到off-policy learning上，根據依著target policy與behavior policy的trajectories所發生的相對機率來加權returns，這種作法稱為importance-sampling ratio。給定起始的state $S_t$，發生在任意的policy $\pi$之下，後續的state-action trajectory的機率，$A_t, S_{t+1}, A_{t+1},...,S_T$：
$$
P_r\left\{ A_t, S_{t+1}, A_{t+1},...,S_T \vert S_t, A_{t:T-1}\sim \pi \right\} \\
= \pi(A_t \vert S_t)p(S_{t+1}\vert S_t, A_t)\pi(A_{t+1}\vert S_{t+1})\cdots p(S_T\vert S_{T-1}, A_{T-1}) \\
= \prod_{k=t}^{T-1}\pi(A_k\vert S_k)p(S_{k+1}\vert S_k,A_k)
$$

其中$p$在這邊就是公式3.4所定義的狀態轉移機率函數(state-transition probability function)。

:::warning
$$p(s' \vert s, a) \dot{=} P_r\left\{S_t=s' \vert S_{t-1}, A_{t-1}=a\right\} = \sum_{r\in\mathcal{R}} p(s' , r\vert s, a) \tag{3.4}$$
:::

因此，依著target policy、behavior policy的trajectory的相機對率，也就是importance-sampling ratio為：
$$\rho_{t:T-1}\dot{=}\dfrac{\prod^{T-1}_{k=t}\pi(A_k\vert S_k)p(S_{k+1}\vert S_k, A_k)}{\prod^{T-1}_{k=t}b(A_k\vert S_k)p(S_{k+1}\vert S_k,A_k)}=\prod_{k=t}^{T-1}\dfrac{\pi(A_k\vert S_k)}{b(A_k\vert S_k)}\tag{5.3}$$

儘管trajectory probabilities是取決於MDP的轉移機率(transition probabilities)，但這轉移機率通常是未知的，但它們在分子、分母中是一樣的，因此可以直接消掉。所以我們可以看到，最終，這個importance-sampling ratio只跟兩個policy與樣本序列有關，與MDP無關。

我們想做的是估測target policy的expected returns，但我們有的就只來自behavior policy的returns $G_t$。但這邊得到的期望值$\mathbb{E}[G_t\vert S_t=s]=v_b(s)$是不正確的，因此無法利用它來得到$v_\pi$。這邊importance-sampling ratio閃亮亮登場。利用$\rho_{t:T-1}$將returns轉為正確的期望值：
$$\mathbb{E}[\rho_{t:T-1}G_t\vert S_t=s]=v_\pi(s)\tag{5.4}$$

現在我們已經準備好利用從behavior policy $b$觀測得到的一批episode來估測$v_\pi(s)$(使用Monte Carlo algorithm)。這邊我們把time steps編號，舉例來說，如果第一個episode的terminal state是在time=100，那下一個episode就會從101開始。這樣的作法讓我們可以用這個time-step的編號來參考特定episodes中的特定時刻。對於every-visit method，我們可以定義看的state $s$的所有time steps的集合，以$\mathcal{J}(s)$表示。如果是first-visit method，那$\mathcal{J}(s)$就只會包含第一次出現在episode的time steps。然後，$T(t)$表示在時間$t$之後的第一次終止，$G_t$表示$t$到$T(t)$所能得到的return。因此，$\left\{G_t \right\}_{t\in\mathcal{J}(s)}$就是屬於state $s$的returns，而$\left\{\rho_{t:T(t)-1} \right\}_{t\in\mathcal{J}(s)}$就是相對應的importance-sampling ratios。為了估測$v_\pi(s)$，我們利用重要性抽樣率來平均結果，以此調整returns：
$$V(s)\dot{=}\dfrac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_t}{\vert \mathcal{J}(s) \vert}\tag{5.5}$$

:::warning
如果是first-visit，那$\mathcal{J}(s)$裡面就只會有一個索引值，記錄state $s$第一次出現在episode的time step，如果every-visit就記錄每一次state $s$出現的time step，也因此$\left\{G_t\right\}_{t\in\mathcal{J}(s)}$就是一個集合，記錄state $s$的return。而$\left\{\rho_{t:T(t)-1} \right\}$就是state $s$在每個time step出現的重要性抽樣率的集合。最後$V(s)$的分子就是state $s$在每個time step的重要性抽樣率乘上每個time step的returns再除上state $s$出現的次數。所以如果我們是採用first-visit，那分母沒意外的話應該都會是1。
:::

如果你的重要性抽樣就只是用平均來計算，那就稱為ordinary importance sampling(普通重要性抽樣?)。

另外有一種為weighted importance sampling(加權重要性抽樣)，它使用加權平均，如下定義：
$$V(s)\dot{=}\dfrac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_t}{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}}\tag{5.6}$$

如果分母是0，那5.6這個式子的結果就是0。

:::warning
加權平均做的就是加總state $s$所有的重要性抽樣率來做分母。不單純的以出現次數來計算。
:::

下面我們來瞭解一下這兩個重要性抽樣有什麼不同，考慮下面情況，在觀察到state $s$的single return之後用first-visit methods來估測一下：
* weighted importance-sampling(5.6)
* 比例$\rho_{t:T(t)-1}$的這個部份在single return的情況下會分子、分母消掉(假設比例nonzero)，剩下$G_t$，因此估測值就會等於觀察值，也就是single return，而這個結果跟比例無關(因為已經消掉了)
* 因為這是一個single return，因此這是很合理的估測，不過這期望值是$v_b(s)$而不是$v_\pi(s)$，這在統計意義上代表它是有偏的(biased)
* ordinary importance-sampling(5.5)
* 得到的期望值總是$v_\pi(s)$，意謂著是無偏的(unbiased)
* 得到的結果可能是極端的，假設重要性抽樣比例為10，這代表被觀測到的trajectory按著target policy的機率是按著behavior policy的10倍。這時候估測出來的結果也會是觀測到的return的10倍。也就是說，即使episode的trajectory已經非常能夠代表target policy，但它估測出來的值與觀察到的return還是會差異很大

| method | bias | variance |
| -------- | -------- | -------- |
| ordinary importance sampling | unbiased | unbounded |
| weighted importance sampling | biased，但會漸近的收斂到0 | 任一個single return的最大權重都是1 |

事實上，假設return是有界限的(bound)，即使重要性抽樣比例的方差是無限大，加權重要性抽樣估測的方差依然可以收斂到0。實務上，加權估測有著較低的方差，因此大家比較愛用。不過課本後面第二部份的函數逼近(function approximation)的近似方法還是會用到ordinary importance sampling。

另外，這兩個方法用在every-visit methods都是有偏的(biased)，不過隨著樣本數的增加，偏差也會逐漸收斂到0。實務上，every-visit是首選，因為這方法不需要特別去跟蹤那些state已經遇過的，而且更容易擴展到近似值。

下面給出完整的every-visit MC algorithm(off-policy)的policy evaluation(使用加權重要性抽樣)的程式碼：

:::info
Example 5.4: Off-policy Estimation of a Blackjack State Value

這個範例我們要把剛剛提到的兩種重要性抽樣的方法用到Example 5.1上，我們要從off-policy的資料中去估測single blackjack state的value。想一下課本提過的MC的優點，就是可以在沒有其它state的情況下去估測single state的value。這個範例是這樣的：
1. 莊家亮出的牌點是2
2. 玩家的牌點總合是13，然後是usable ace，意思就是玩家的牌有A，然後2，然後A當11用，當然也有可能是3張A
3. 資料的生成就由上述狀態開始，以等機率的方式去選擇停牌還是要牌(behavior policy)
4. target policy只有在20或21點的時候才會停止要牌

如果你依著target policy的話，這個state的value會近似0.27726，這是利用target policy各自生成一億個episodes，然後計算return的平均所得。兩種off-policy的方法使用隨機策略(random policy)在經過1000個off-policy的episodes之後也得到差不多的結果。為了能夠確認得到的結果的可靠度，我們各自執行100次，每一次都是從都是從0開始，然後執行10000個episodes。Figure 5.3給出學習曲線，每一種方法估測的平方誤差做為episode數量的函數，然後計算這100次的平均。

Figure 5.3：加權重要性抽樣從off-policy episodes有較低的估測誤差

上圖也可以看的到，兩種演算法都可以收斂到接近0，加權重要性抽樣在開始的時候有著較低的誤差，這也是常見的結果。
:::

:::info
Example 5.5: Infinite Variance
當縮放過的returns有著無限方差的時候，普通重要性抽樣的估測方差通常是無限大的，因此那收斂性是讓人不滿意的，而且這種事情在trajectories包含loop的時候，你用off-policy是很容易會發生的。可以看Figure 5.4上面的小插圖，圖上只有一個nonterminal state $s$與兩個actions(右與左)。右的這個action是一個確定性的轉移，會直接往terminal state去，但左的這個action有90%的機率回去$s$，只有10%的機率會往terminal state去，如果它往terminal state去，那reward就+1，其餘的reward皆為0。考慮一種狀況，就是target policy總是選擇『左』這個action。所以，所有用這policy的episodes都會包含一定次數是轉移回到$s$的情況，接著到達終止狀態，得到reward+1。因此，用著這個target policy的state $s$的value就是1($\gamma = 1$)。假設我們使用behavior policy來估測這些off-policy的資料，然後選擇左、右的機率是一樣的。

Figure 5.4：普通重要性抽樣在小插圖中的one-step MDP表現的非常不穩定。在這裡的正確的估測值是1($\gamma=1$)，儘管這確實是樣本回報的期望值(在重要性抽樣之後)，樣本的方差依然是無限大的，估測值並不會收斂到1。這是off-policy first-visit MC的結果。

Figure 5.4下半部份說明著使用普通重要性抽樣的first-visit MC algorithm的十次各自執行的結果。即使經過百萬次的episodes，估測值依然無法正確的收斂到1。相對加權重要性抽樣演算法在第一個episode選擇左邊這個action做為結束之後就能夠精確的估測出1。所有不等於1的這些returns(也就是選擇right這個action做為結束)都跟target policy不相等，因此重要性抽樣比例$\rho_{t:T(t)-1}$為0，對5.6這個式子的分子、分母完全無貢獻。加權重要性抽樣演算法只對與target policy一致的returns做加權平均，而且這些returns都會是1。

我們可以簡單的計算來驗證在這個範例中經過重要性抽樣縮放的returns的方差都會是無限大。任意隨機變數$X$的方差是其均值$\bar{X}$的偏差(deviation)的期望值，可以寫為：
$$\text{Var}[X]\dot{=}\mathbb{E}[(X-\bar{X})^2]=\mathbb{E}[X^2-2X\bar{X}+\bar{X}^2]=\mathbb{E}[X^2]-\bar{X}^2$$

因此，在我們的範例中，如果均值是有限的，若且唯若當隨機變數的平方的期望值是無限的時候，方差就會是無限的。因此我們只需要證明經過重要性抽樣縮放過的return的預期平方是無限的：
$$\mathbb{E}\left[\left(\prod_{t=0}^{T-1} \dfrac{\pi(A_t\vert S_t)}{b(A_t\vert S_t)}G_0 \right)^2 \right]$$

為了能夠計算這個期望值，我們會依據episode的長度與終止情況來分割問題：
1. 任一個以右邊這個action結束的episode，其重要性抽樣比例為0，因為target policy永遠不會選擇這個action，因此這些episodes對期望值的貢獻為0(括號內為0)，我們可以忽略這種情況
2. 單純考慮包含一些(可能為0)向左然後回到非終止狀態，然後又接著一個向轉到終止狀態的episodes，這些episodes的return都是1，因此我們可以忽略$G_0$。為了得到期望的平方，我們只需要考慮episode的每一個長度，將episode發生的機率乘上其重要性抽樣比例的平方，然後加起來：

:::

## 5.6 Incremental Implementation
Monte Carlo prediction methods可以利用2.4中介紹過的，以episode-by-episode的方式逐步實現。只是說，在Chapter 2的時候我們是平均rewards，但是在MC我們平均的是returns。不止如此，Chapter 2中用的方法你完全可以以相同的方式用於on-policy MC methods。如果是off-policy Monte Carlo methods，我們就需要各自考慮是使用ordinary importance sampling還是weighted importance sampling。

在普通重要性採樣中(ordinary importance sampling)，其returns是經過重要性採樣比例，也就是$\rho_{t:T(t)-1}$(5.3)縮放過，然後再簡單的計算平均(5.5)。對於這些方法，我們可以同樣的使用Chapter 2提過的遞增法，只是用縮放過的returns來取代rewards。這就保留了使用加權重要性抽樣的off-policy的情況。這邊我們會對returns做一些加權平均，然後需要一個些許不同的遞增演算法。

:::warning
$$\rho_{t:T-1}\dot{=}\dfrac{\prod^{T-1}_{k=t}\pi(A_k\vert S_k)p(S_{k+1}\vert S_k, A_k)}{\prod^{T-1}_{k=t}b(A_k\vert S_k)p(S_{k+1}\vert S_k,A_k)}=\prod_{k=t}^{T-1}\dfrac{\pi(A_k\vert S_k)}{b(A_k\vert S_k)}\tag{5.3}$$
:::
:::warning
$$V(s)\dot{=}\dfrac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_t}{\vert \mathcal{J}(s) \vert}\tag{5.5}$$
:::
:::warning
下面給出[Chapter 2](https://hackmd.io/@shaoeChen/Sk7frzq4u#24-Incremental-Implementation)中所提的遞增法
$$
\begin{align}
Q_{n + 1} &= \dfrac{1}{n}\sum^n_{i=1}R_i \\
&=\dfrac{1}{n}\left(R_n + \sum_{i=1}^{n-1}R_i \right) \\
&=\dfrac{1}{n}\left(R_n + (n-1)\dfrac{1}{n-1}\sum_{i=1}^{n-1}R_i \right) \\
&=\dfrac{1}{n}\left(R_n + (n-1)Q_n \right) \\
&=\dfrac{1}{n}\left(R_n + nQ_n - Q_n \right) \\
&=Q_n + \dfrac{1}{n}\left[R_n - Q_n \right]
\end{align} \tag{2.3}
$$
:::

假設我們有一系列的returns，$G_1, G_2, G_3,...,G_{n-1}$，全都超始於同一個state，然後return都有相對應的權重$W_i$($W_i=\rho_{t_i:T(t_i)-1}$)。我們希望這樣估測：
$$V_n\dot{=}\dfrac{\sum_{k=1}^{n-1}W_kG_k}{\sum_{k=1}^{n-1}W_k}, n\geq 2 \tag{5.7}$$

並且在獲得一個額外return $G_n$的同時保持更新。

:::warning
公式5.7說明著，在every-visit情況下，我們會計算一個episode的trajectory內，同一個state它每次出現的expected returns，假設有3個好了，我們會把這3個returns乘上相對應的重要性抽樣率做加總，再除以這3個重要性抽樣率的總合，用這個計算結果來做為該state的估測值。
:::

為了能夠持續的跟蹤$V_n$，我們必需要為每一個state維持前$n$個returns對應的權重的累加和 $C_n$。$V_n$的更新規則為：
$$V_{n+1}\dot{=}V_n + \dfrac{W_n}{C_n}[G_n - V_n], n\geq 1 \tag{5.8}$$

以及

$$C_{n+1} = C_n + W_{n+1}$$

:::warning
這個公式說的就是前$n$個returns對應的權重的累加和，而且公式5.8很明顯的就是公式2.3的一個延伸，只是分母變成累加的權重。而$C$就是用來記錄該state或是state-action pair在所有episode的累加，而$W$就是該episode的權重記錄。
:::

其中$C_0\dot{=}0$(且$V_1$是任意的，因此不需要特別指定)。下面給出完整的用於Monte Carlo policy evaluation的episode-by-episode incremental algorithm：

這個演算法表面上是應用於off-policy，採用加權重要性抽樣，但是只要你讓target policy與behavior policy是一樣的，它就一樣適用於on-policy(這種情況就是$\pi=b$，且$W$始終為1)。近似值$Q$收斂至$q_\pi$(所有遇過的state-action pair)，儘管actions的選擇是根據可能不同的policy $b$。

## 5.7 Off-policy Monte Carlo Control
這邊要來說第二種學習控制的方法，也就是off-policy methods，基本上off-policy與on-policy的一點差異是這樣的：
* on-policy：用同一個policy來做估測以及控制
* off-policy：用於生成行為的稱為behavior policy，用於評估與改進的稱為target policy，而這個policy可能與behavior policy是不相關的

這種分開來處理的好處在於當behavior policy持續的sample所有可能的actions的同時，target policy可以是確定的(像是greedy)。

Off-policy Monte Carlo control methods會依著behavior policy然後同時讓target policy學習與改進。這樣的作法必需要讓behvaior policy能夠以非零的機率選擇所有target policy可能選擇的actions(覆蓋率)。為了探索所有的可能，我們必需要讓behvaior policy是soft，也就是每一個states的每一個actions都要有非零的機率被選中。

下面給出off-policy Monte Carlo control method，基於GPI與加權重要性抽樣，用於估測$\pi_*, q_*$：

target policy $\pi \sim \pi_*$是對應$Q$的greedy policy，$Q$為$q_\pi$的估測。behavior policy $b$可以是任意policy，但是為了確保$\pi$能夠收斂為optimal policy，我們必需要能夠得到每一個state-action pair無限次的returns。可以透過選擇$b$為$\epsilon-$soft來確保這個需求。即使actions是根據不同soft policy $b$所選擇，而且soft policy $b$可能會在episodes之間或之內有所變化，但policy $\pi$仍然可以在遇到所有的states情況下收斂為optimal。

這個方法的一個潛在問題就是，當episode中的所有剩餘的actions都是greedy的時候，那就只能從episodes的尾部來學習。如果比較多都是nongreedy actions，那學習就會比較慢，特別是當states只會在較長的episodes的早期部份出現的時候。目前對這部份的問題在off-policy Monte Carlo methods上的影響研究比較少。比較嚴重一點的話或許可以使用TD-learing(下一章)來處理。

:::info
todo: 有空再回來補Exercise 5.12
:::

## 5.8 \*Discounting-aware Importance Sampling

目前為止我們考慮的off-policy methods都是基於將returns視為單一整體來計算計算重要性抽樣的權重，沒有去考慮return的內部結構(即discounted rewards的總和)。這邊我們要簡要的介紹一些使用這種結構來降低off-policy estimators的方差的研究。

舉例來說，狀況是episodes非常長，而且$\gamma$明顯小於1。具體來說，episodes最少有100個steps，而且$\gamma=0$。這樣當$t=0$的時候，其return $G_0=R_1$，但是它的重要性抽樣比卻是100個因子(factor)的連乘積，也就是$\dfrac{\pi(A_0\vert S_0)}{b(A_0\vert S_0)}\dfrac{\pi(A_1\vert S_1)}{b(A_1\vert S_1)}\dots \dfrac{\pi(A_{99}\vert S_{99})}{b(A_{99}\vert S_{99})}$。在普通重要性抽樣中(ordinary importance sampling)，其return會被整個乘積縮放，但實際上它只需要依第一個因子(factor)來縮放，也就是$\dfrac{\pi(A_0\vert S_0)}{b(A_0\vert S_0)}$，跟其它99個因子是不相關的，因為第一個reward之後，它的return就決定了(因為$\gamma=0$)。後面的這些因子與return、期望值1無關；它們並不會改變預期的更新，但它們會極大的增加其方差。某些情況下，它們甚至可以讓方差無限大。因此我們要來想一下怎麼避免這種大量與預期更新無關的方差。

這個想法的本質是將discount想成是episode終止的機率，或者相當於部份終止的程度(degree)。對於任意的$\gamma \in [0, 1)$，我們可以把$G_0$這個return視為是一步內(in one step)以$1-\gamma$的程度部份終止，那它產生的return就是第一個reward，$R_1$，然後兩步之後又部份終止，這時候的終止程度為$(1 - \gamma)\gamma$，產生的return就是$R_1+R_2$，以此類推。後者的部份終止程度對應第二步的終止程度，$1-\gamma$，以及尚未在第一步終止的$\gamma$。因此，第三步的部份終止程度就是$(1-\gamma)\gamma^2$，其中$\gamma^2$反映出來的是前兩步還沒有終止的部份。這邊的partial returns稱為flat partial returns：
$$\bar{G}_{t:h}\dot{=}R_{t+1} + R_{t+2} + \cdots + R_h, 0\leq t < h \leq T$$

其中"flat"表示沒有discount，而"partial"則表示這些returns不會一路延申至終止，但會在$h$的時候停下來，這稱為"horizon"(而$T$是episode終止的時間)。傳統的full returns $G_t$可以視為是上面說的flat partial returns的總和：

:::warning
horizon應該可以想成是看的到的部份，不知道該不該翻為視界，所以就留英文
:::

現在我們要用重要性抽樣比例來縮放這個flat partial returns，這類似截斷(truncated)。因為$\bar{G}_{t:h}$所涉及到的rewards只到horizon $h$，所以我們需要的機率比就只需要到$h-1$。我們定義一個ordinary importance-sampling estimator，就像是公式5.5：
$$V(s)\dot{=}\dfrac{\sum_{t\in J(s)}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1} \rho_{t:h-1} \bar{G}_{t:h} + \gamma^{T(t)-t-1} \rho_{t:T(t)-1} \bar{G}_{t:T(t)} \right)}{\vert J(s) \vert}\tag{5.9}$$

:::warning
$$V(s)\dot{=}\dfrac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_t}{\vert \mathcal{J}(s) \vert}\tag{5.5}$$
:::

下面是類似公式5.6的weighted importance-sampling estimator：
$$V(s)\dot{=}\dfrac{\sum_{t\in J(s)}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1} \rho_{t:h-1} \bar{G}_{t:h} + \gamma^{T(t)-t-1} \rho_{t:T(t)-1} \bar{G}_{t:T(t)} \right)}{\sum_{t\in J(s)}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1} \rho_{t:h-1} + \gamma^{T(t)-t-1} \rho_{t:T(t)-1} \right)}\tag{5.10}$$

:::warning
$$V(s)\dot{=}\dfrac{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}G_t}{\sum_{t\in\mathcal{J}(s)}\rho_{t:T(t)-1}}\tag{5.6}$$
:::

我們把上面兩種估測器稱為discounting-aware importance sampling estimators。它們會把discount rate考慮進去，但是當$\gamma=1$的時候，那是沒影響的(如公式5.5的off-policy estimators)。

## 5.9 \*Per-decision Importance Sampling

還有一種方法可以在off-policy importance sampling中考慮作為rewards總和的return結構，這種方法即使在沒有discount的情況下也可以減少方差，即使$\gamma=1$。在5.5、5.6這兩個off-policy estimators中，分子中每個總和的項目就是它本身的和(each term of the sum in the numerator is itself a sum)：
$$
\begin{align}
\rho_{t:T-1}G_t &= \rho_{t:T-1}(R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1}R_t) \\
&= \rho_{t:T-1}R_{t+1} + \gamma \rho_{t:T-1}R_{t+2} + \cdots + \gamma^{T-t-1}\rho_{t:T-1}R_T \tag{5.11}
\end{align}
$$

off-policy estimators依賴這些項目的期望值，這可以寫的更簡單一點。我們注意到，5.11的每個子項目(sub-term)都是random reward與random importance-sampling ratio的乘積。舉例來說，第一個子項目可以用5.3寫成：
$$
\rho_{t:T-1}R_{t+1}=\dfrac{\pi(A_t\vert S_t)\pi(A_{t+1}\vert S_{t+1})\cdots \pi(A_{T-1}\vert S_{T-1})}{b(A_t\vert S_t)b(A_{t+1}\vert S_{t+1})\cdots b(A_{T-1}\vert S_{T-1})}R_{t+1}\tag{5.12}
$$

這邊我們可以看的出來，所有這些因子，只有第一個跟最後一個(reward)是相關的；其它都是在reward之後發生的事情。此外，所以其它因子的期望值都是1：
$$\mathbb{E}[\dfrac{\pi(A_k\vert S_k)}{b(A_k\vert S_k)}] \dot{=} \sum_a b(a \vert S_k)\dfrac{\pi(a\vert S_k)}{b(a\vert S_k)}=\sum_a\pi(a\vert S_k)=1 \tag{5.13}$$

再幾個步驟我們就可以證明，所以這些其它的因子都一如預期的沒有影響：
$$\mathbb{E}[\rho_{t:T-1}R_{t+1}]=\mathbb{E}[\rho_{t:t}R_{t+1}]\tag{5.14}$$

如果我們對公式5.11的第$k$個子項目重覆這個作法，那就會得到：
$$\mathbb{E}[\rho_{t:T-1}R_{t+k}]=\mathbb{E}[\rho_{t:t+k-1}R_{t+k}]$$

這樣一來，5.11的期望值就可以寫成：
$$\mathbb{E}[\rho_{t:T-1}G_t]=\mathbb{E}[\tilde{G_t}]$$

其中
$$\tilde{G}_t=\rho_{t:t}R_{t+1} + \gamma \rho_{t:t+1}R_{t+2} + \gamma ^2\rho_{t:t+2}R_{t+3} + \cdots + \gamma^{T-t-1} \rho_{t:T-1}R_{T}$$

我們把這個想稱為per-decision importance sampling。

緊接著，就是一個替代的重要性抽樣估測器，與普通重要性抽樣估測器(5.5)具有相同的無偏期望(first-visit)，使用$G_t$：
$$V(s)\dot{=}\dfrac{\sum_{t\in J(s)}\tilde{G}_t}{\vert J(s) \vert} \tag{5.15}$$

我們期望這個方式可以降低一些方差。

是否有per-decision版本的weighted importance sampling?這是個謎。目前為止，目前為止我們提出的估測器都不一致(也就是即使擁有無限的資料也無法收斂到真實值)。
## 5.10 Summary
這章介紹的Monte Carlo methods用著sample episodes，從經驗中來學習value function與optimal policies。這給了它們至少三個優於DP的優點：首先是，它們可以在沒有環境模型動態性的相關資訊情況下，直接從與環境的互動中學到最佳行為(optimal behavior)。第二，它們可以使用模擬的方式來或是採樣模型(sample model)的方式來學習。很多情況下你很難構建出一個DP需要的狀態機率轉移模型，但你可以很輕易的模擬sample episodes。最後，MC可以很簡單而且有效率的關注在states的subset(狀態的子集合)，可以準確的評估感興趣的部份，不需要理其它的狀態，這第八章還會有說明。

當然還有第四個優點，這後面會提到，MC在馬可夫性質不成立的時候，其效能損失較少。這是因為它不需要用後續的狀態(successor state)估測值來更新當前的估測值。意思就是它們並不需要自舉(bootstrap)。

在設計Monte Carlo control methods的時候，我們都依循著Chapter 4提到的generalized policy iteration(GPI)的總體架構。GPI涉及策略評估(policy evaluation)與策略改進(policy improvement)的交互過程。MC則是給出另一個策略評估過程的替代方案。與其像DP一樣去建立模型來計算每一個state的value，MC就只是簡單的計算從這個state開始得到多個的returns的平均即可。因為state的value就是expected return(預期的回報)，所以這個平均可以是一個很好的近似值(expected return的近似值)。在控制方法中(control methods)，我們對approximating action-value function特別感興趣，因為它們可以在不需要環境轉移動態性的模型情況下直接改進策略。MC在episode-by-episode的基礎上混合策略評估與策略改進的步驟，然後逐漸的實現。

維持足夠多的探索是MC control methods中的一個重要議題。它不能一直很貪心的選當前最好的而不選其它的，這會造成它無法發現其它更好的選擇。一種方法就是忽略這個問題，我們假設episode是從隨機選擇state-action pair開始，用這樣的方式來覆蓋所有可能。像exploring starts這種方式可以在具有simulated episodes(模擬情節)的應用程式中使用，但不大可能從實際經驗中學習。在on-policy的方法中，agent會持續的探索，然後試著找到能夠繼續探索的最佳策略(best policy)。off-policy的話，agent也是會探索，只是實際學習的可能是跟它在探索用的policy無關的另一個確定性的最佳策略(deterministic optimal policy)。

off-policy指的是，我們從不同的behavior policy生成的資料來學習target policy的value function。這類的學習方法是基於某些形式的重要性抽樣，也就是說，利用依著兩個policies採取觀察到的actions的機率比例來加權回報(weighting returns)，從而將behavior policy的期望值轉換為target policy的期望值。

另外，兩個重要性抽樣的差別：
* Ordinary importance sampling：
* 對weighted returns做簡單的平均
* unbiased estimates，無偏估計，但是其方差很大，大到可能是無限大
* weighted importance sampling：
* 對weighted returns做加權平均
* 其方差總是有限的，
* 實務上的首選作法

儘管它們的概念很簡單，但用於預測和控制的off-policy Monte Carlo methods仍然未解決，依然是個研究中的議題。

最後說一下MC與DP的差異，首先，MC是基於樣面經驗計算，因此可以在沒有模型的情況下直接學習。第二，MC不需要自舉(bootstrap)，也就是說，MC在更新它們的價值估測(value estimates)是不需要基於其它value estimates。這兩個差異並不非一定要在一起，是可以分開的。下一章會來談一個類似於MC的方法，一樣是從經驗中學習，但也同時像DP一樣是自舉的。