# Reinforcement Learning: An Introduction_Chapter 8 Planning and Learning with Tabular 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)
[LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions](https://github.com/LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions)

這一章我們要來談談強化學習方法的一個統一觀點，我們知道方法有兩種：
1. 需要環境的模型的方法，像是DP、heuristic search([啟發式搜尋](http://terms.naer.edu.tw/detail/2117193/))
2. 不需要模型的方法，像是MC、TD

上面兩種方法各自稱為model-based、model-free的強化學習方法。model-based的方法依賴著planning來做為它們主要的組成，而model-free則是依賴著learning。雖然兩種方法有很大的不同，但還是有不少相似的地方。特別是，這兩種方法的核心都是價值函數(value function)的計算。而且，所有的方法都是基於向前看一下未來的事件，然後計算backed-up value，然後用這個來做為近似價值函數(approximate value function)的更新目標。這本書的前面我們把MC跟TD做為不同的替代方法，然後說明如何用$n-$step methods來統一MC、TD。這一章的目標就是要把model-based跟model-free這兩個方法做一個總成。它們的不同我們是知道了，所以現在要來探索看看能夠怎麼樣的混合它們。

## 8.1 Models and Planning
我們在說的環境模型指的就是agent可以用它(model)來預測環境會如何回應其actions的任何事情。給定一個state跟一個action，然後模型產生一個結果，預測(prediction)下一個state與reward。如果模型是隨機的，那就會存在很多可能的next states與next rewards，每一種都存在著可能發生的機率。有些模型產生的是所有可能的分佈跟它們的機率；這一種的模型稱為[分佈模型](https://terms.naer.edu.tw/search/?q=distribution+model&field=ti&op=AND&group=&num=10)(distribution models)。另一種模型只是單純的生成很多可能中的一個，根據機率採樣(sampled)；這種的模型稱為sample models(樣本模型?)。舉例來說，我們要來考慮弄一個一打骰子(dice)總合的模型。那如果是distribution model就會生成所有可能的總合跟它們發生的機率，那如果是sample model的話，它就會產生一個根據這個機率分佈抽(drawn)到的單個總和(就是從這個機率分佈中去sample一個出來就是了)。在DP中我們會去估測MPD的動態性，也就是$p(s', r\vert s, a)$，這種模型就屬於distribution model。然後Chapter 5的那個blackjack則是屬於sample model。distribution models比sample models還要來的強大(stronger)，因為distribution model始終可以拿來生成樣本。然而，在很多應用程式中，你要去得到一個sample model會比得到一個distribution model還要來的簡單。像剛剛說的那一打的骰子就是一個例子。你可以很簡單的寫個程式來模擬十八啦，然後得到那個總和，但是你要去得到所有可能的總和跟它們的機率是很難的，而且容易出錯。

models可以用來模仿或模擬經驗：
* 給定一個起始的state、action，sample model可以生成出一個可能的轉移，而distribution model則可以生成出由發生機率所加權的所有可能的轉移
* 給定一個起始的state、policy，sample model可以產生一個完整的episode，而distribution model則可以生成所有可能的episodes跟這些episodes的機率

不管是什麼情況，我們都會說model可以用來模擬環境並產生模擬經驗。

planning這個單字可以用在很多地方。在這邊我們用來泛指任何的計算過程，以model做為input，然後在與建模環境互動的過程中產生或是改進一個policy：

在AI的世界中，根據定義會有兩種不同的planning：
1. State-space planning，主要被視為從state space中搜尋optimal policy或是實現目標的optomal path。actions會導致state之間的轉移，然後value functions再依據states來計算
2. plan-space planning，planning則是在plan space中搜尋，Operators會導致plan之間的轉移，如果有value function的話，那它就是根據plan space來定義。plan-space planning包含evolutionary methods([調優法](http://terms.naer.edu.tw/detail/2932687/))跟partial-order([偏序](http://terms.naer.edu.tw/detail/2121468/)) planning，這在人工智慧中常見的一種planning，其steps的順序在planning的所有階段中是不完全確定的

Plan-space methods很難有效的用到強化學習所關注的stochastic sequential decision problems，所以我們不會進一步的去考慮，如果有興趣你可以參考Russell and Norvig, 2010。

我們在這邊要提出的一個統一觀點就是，所有的state-space planning methods有一個通用的架構，這個架構也存在於本書所介紹的學習方法中。這一章剩餘的部份我們會來好好的說說這個觀點，不過有兩個基本的概念：
1. 所有的state-space planning methods都涉及計算value functions來做為改進policy的關鍵中間步驟
2. 它們會透過用於模擬經驗的updates或是backup的操作來計算value function

下面可以喵一下這個通用架構：

DP很明顯的是符合這個架構：DP會掃過整個states space，然後生成每一個state可能轉移的分佈。每一個分佈再用來計算backed-up value(update target)，並更新state的估測值。接下來我們要來說說其它符合這個架構的state-space planning methods，不同方法之間就只是updates的類型、update的順序還有backed-up information保留的時間的一些小差異。用這樣的方法來看待planning methods就是為了強調planning methods跟我們提過的強化學習方法之間的關係。learning跟planning的核心利用backing-up update的操作來估測value function。它們的不同之處在於，planning用模型生成的模擬經驗，而learning則是用環境生成的實際經驗。當然啦，這樣子的差異就會造成更多的差異，像是效能該如何評估，還有應該如何靈活的生成經驗。不過既然說是通用架構，那就代表很多想法跟演算法可以在planning與learning之間轉移(transfer)。特別是，在許多情況下，learning algorithm可以取代掉planning method的關鍵更新步驟。learning methods只需要經驗做為輸入，而且很多情況下learning methods是既可以用於模擬經驗，也可以用於實際經驗的。下圖給出一個基於one-step tabular Q-learning的planning methosd，而且是從sample model中隨機採樣的範例：

這方法我們就稱為random-sample one-step tabular Q-planning，它可以在model情況下以與 one-step tabular Q-learning在真實環境收斂至optimal policy的相同條件來收斂至optimal policy(每一個state-action pair在Step 1都要能夠被無限次，而且$\alpha$隨著時間適當的減少)

除了統一planning與learning的觀點之外，另一個主題就是planning以較小的增量步長(incrmental steps)的好處。這讓planning可以在任意時間以很小很小的計算量來中斷或重新定向，這似乎是讓規劃與行動(acting)、模型學習有效混合的關鍵需求。即使是在pure planning的問題上，對那些問題太大而無法精確求解的任務，你都還是可以用非常小的steps來做planning，那可能會是最有效的方法。
## 8.2 Dyna: Integrated Planning, Acting, and Learning
當planning是線上(online)完成，在跟環境的互動過程中會有不少有趣的事情發生。從互過動過程產生的新的資訊增益也許會改變模型，從而就變成跟planning互動。可能會需要以某種方式根據當下正考慮或預期未來的state或是decisions(決策)來自定planning process(規劃過程)。如果決策的制訂與模型的學習都是計算密集過程的類型，那可能就要在它們之間去劃分可用的計算資源。為了開始探索這些問題，我們會介紹Dyna-Q，這是一個簡單的架構，集成online planning agent所需要的主要功能。每個函數在Dyna-Q都以極其簡單的形式出現。後面我們會來說每個功能的一些替代方法跟它們之間的權衡。不過現在我們只是聊聊，給你有個想法而以。

在planning agent中，真實經驗至少會扮演兩個角色：(1)可以用來改進模型(讓模型可以更精確的匹配實際經驗)，(2)可以用來直接改進value function與policy(用前面說過的強化學習方法)。前者我們稱為model-learning，後者則稱為direct reinforcement learning(direct RL)。經驗(experience)、模型(model)、價值(value)與策略(policy)的所有可能相關性都如下圖所示：

每個箭頭都說明著影響以及推定改善的相關性。可以注意到，經驗如何通過模型(model)直接(direct)或間接(indirect)的改進value function與policies。後者有時候也稱為indirect reinforcement learning，這涉及了planning。

* indirect: 更能充份有效的利用經驗，因此能夠以更少的與環境互動來實現更好的策略(policy)
* direct: 較為簡單，且不受模型設置偏差的影響

有人會覺得indirect methods是比direct methods還要來的好，但也有人會覺得direct methods比較合理，因為這是人類與動物的學習方式。相關深入探討可以參考Chapter 14。

Dyna-Q包含上可那張圖的所有過程，planning、acting、model-learning、direct RL，所有的過程都會持續的發生。其中planning methods是如下圖所示的random-sample on-step tabular Q-planning methods：

而direct RL methods則是one-step tabular Q-learning。model-learning也是table-based，並假設環境是確定性的(deterministic)。在每一次的轉換之後，$S_t, A_t \to R_{t+1}, S_{t+1}$，model會在它的table記錄所有$S_t, A_t$預測會發生的$R_{t+1}, S_{t+1}$。因此，如果以state-action pair來查詢model先前的經驗，那就會回傳最後觀察到的next state與next reward來做為它的預測。在planning期間，Q-planning algorithm只會從先前已經有過經驗的state-action pair來隨機採樣(Step 1)，因此model這輩子永遠不會被查詢到沒有信息的state-action pair。

Figure 8.1給出Dyna agents的整體架構，這也是Dyna-Q algorithm的一個範例：

Figure 8.1: The general Dyna Architecture. Real experience, passing back and forth between the environment and the policy, a↵ects policy and value functions in much the same way as does simulated experience generated by the model of the environment.

中間的column表示agent與env(環境)之間的基本互動。圖左的箭頭則表示direct RL在真實經驗上用以改進value function與policy的操作。右邊的部份都是model-based的流程。model從真實經驗學習，然後給出一些模擬經驗。我們用"search control"這個術語來代表利用model來生成模擬經驗(simulated experiences)的過程(選擇起始狀態(starting states)與actions的過程)。最後，planning透過將強化學習方法應用到模擬經驗來實現，就好像真的有發生這些事一樣。通常，就像是在Dyna-Q一樣，相同的強化學習方法概可以用於從真實經驗中學習，也可以用於從模擬經驗中做規劃(planning)。因此，強化學習是learning與planning最終共通的道路(進擊的巨人？)。learning跟planning可以做深度的整合，因為它們幾乎共享所有相同的機制，只是經驗來源不同罷了。

概念上來說，planning、acting、model-learning、與direct RL在Dyna agents中是同時而且並行發生的。然而，針對在[串列計算機](http://terms.naer.edu.tw/detail/13858082/)的具體實現，我們會完全的指定它們在一個time step發生的順序。在Dyna-Q中，acting、model-learning、與direct RL的過程需要一點點點的計算，我們假設這些過程只需要花費一點點點的時間。每個step的剩餘時間可以用到planning process，這本身是一個計算密集型的過程。我們假設在acting、model-learning與direct RL之後的每一個step中是有時間去完成Q-planning algorithm的$n$次迭代(Steps 1-3)。下面的pseudocode給出Dynq-Q：

其中$Model(s, a)$表示對state-action pair ($s, a$)的一個預測內容(next state、next reward)。direct RL、model-learning、planning各自在(d)、(e)、(f)中完成。如果把(e)、(f)忽略掉，那剩下的部份就是one-step tabular Q-learning。

:::info
Example 8.1: Dyna Maze

下面給出一個簡單的迷宮：

Figure 8.2: 一個簡單的迷宮(插圖)與Dyna-Q agent的平均學習曲線，每個real step不同的planning steps ($n$)計算而得。這個任務是要從$S$移動到$G$，愈快愈好。

1. 這47個states(6\*9-7個障礙物)都有四個actions，也就是上、下、左、右。如果碰到障礙物(深色的部份)或是邊緣那就停在原地，不然agent一樣是四面八方都可以隨便亂走
2. 每次的轉移得到的reward都是0，如果進入目標狀態那reward就是+1
3. 每次到達目標狀態$G$之後，agent就會回到起始狀態$S$來開始一個新的episode
4. discount，$\lambda = 0.95$

Figure 8.2的主要部份說明著應用Dyna-Q agents到這個迷宮任務的平均學習曲線：
* 初始的action values為0，
* step-size $\alpha=0.1$
* $\epsilon=0.1$

當我們貪燹(greediy)的選擇著actions的時候，ties were broken randomly(這邊翻不出來，是指相同機率的時候就隨機選擇嗎?)。agent的planning steps $n$會各自不同，會在每個real step執行。對每一個$n$，曲線說明著agent在每個episodes到達目標所採取的steps的數量，平均超過30次的反覆實驗。在每次的實驗過程中，random seed是維持不變的。因為這樣，不管你的$n$為何，第一個episode是完全相同的(約1700 steps)，所以它的資料就沒有呈現在圖表上。第一個episode之後，不管$n$值為何，效能都提升了，值得注意的是，對於$n$值較大的數值，效能提升的更快。回頭想想，當$n=0$的時候，agent就是一個nonplanning的agent，就只是一個direct RL(one-step tabular Q-learning)。這是就這問題上，當今世上最慢的agent，儘管它的參數($\alpha, \epsilon$)已經是最好的，依然如此。這個nonplanning agent大概需要25個episodes才能來到$(\epsilon-)$optimal，然後，當$n=5$的時候就大概需要5個episodes，$n=50$的時候就只需要3個episodes。

Figure 8.3說明著為什麼planning agent找出解的速度會比nonplanning agent還要來的快的原因。兩張圖各自是$n=0, n=50$在第二個episodes的途中找出來的解。沒有planning，也就是$n=0$的情況下，每個episodes就只會增加額外的一個step到policy，所以目前為止就只學到一個step，也就是最後那個step。不過當你用planning的時候，雖然第一個episode一樣是只學習到一個step，但是在第二個episode的過程中就已經弄出一個非常廣泛的策略(extensive policy)，你已經幾乎可以從目標狀態回到起始狀態了。到第三個episode結束的時候，你已經可以找到一個optimal policy，而且效能完美。


Figure 8.3: Dyna-Q agent在第二個episode途中所找到的policy(nonplanning、planning)。箭頭指出的是每個state的greedy action；如果某一個state沒有箭頭，那就代表所有的action values都是相等的。黑色區域代表agent的所在區域。
:::

在Dyna-Q中，learning與planning是以完全相同的演算法來完成的，以實驗經驗(real experience)做learning，以模擬經驗(simulated experience)做planning。因為planning的過程是漸進的，所以融合planning與acting是非常容易處理的。兩邊都會以最快的速度來進行。agent很敏感，所以通常會對最新的sensory information([感官資訊](http://terms.naer.edu.tw/detail/3268161/)?)很快的做出反應，也同時在背景(background)默默的做起planning。同時在背景執行的還有model-learning。隨著新的信息的取得，model也會不斷的更新來做更好的匹配。隨著model的變化，執行中的planning就會逐漸的計算出一種不同的行為(behaving)來匹配這個新的model。
## 8.3 When the Model Is Wrong
剛剛的範例只能算是小菜一碟，model的變化並不大。這model一開始是空的，然後就只填入完全正確的信息。一般來說，我們不會預期我們有這麼幸運，每次都是正確的。model是有可能不正確的，因為環境是存在隨機性的，而且你觀察到的就只是有限的樣本，或者因為model是用函數近似(function approximation)來學到的，而這個函數近似的泛化可能不是那麼樣的完美，又或者只是因為環境已經發生變化而它的新的行為還沒有被觀察到。當model不正確的時候，planning的過程就可能會計算出suboptimal policy。

某些情況下，透過planning計算而得的suboptimal policy會很快的發現並修正model的錯誤。當model預測出比實際可能更大的reward或是更好的狀態轉移(state transitions)的時候，往往會發生這種情況。由planing得到的policy會試著利用這樣的機會並在過程中發現事情並不是傻子想的那樣。

:::info
Example 8.2: Blocking Maze

Figure 8.4說明了一個相對較小的模型誤差(modeling error)並且從中恢復。最一開始障礙的右邊會有一個從開始到目標的短徑(short path)，如圖左上所示。然後在1000個time steps之後，這條短徑被河蟹了，你變成要從障礙物的左邊缺點去走這條更長的路徑，如圖右上所示。

Figure 8.4：Dyna agents在blocking task的平均效能。左圖是前1000個steps，右圖是剩下的steps。Dyna-Q+是鼓勵探索版本的Dyna-Q，有著探索獎勵。

Figure 8.4說明著Dyna-Q agent與Dyna-Q+ agent(後面就會說到)的average cumulative reward。第一個部份說明的是，兩個Dyna agents在1000個steps內找到最短路徑。當環境(environment)改變的時候，你會發現有一小段的average cumulative reward變的平坦，因為它們卡到了，在障礙物後面一直走來走去的。不過一段時間之後也可以看的到，它們又找到新的開口以及新的optimal behvaior。當環境變的比之前更好的時候，而先前正確的策略(policy)卻沒有顯示出有任何改善，就會出現更大的困難。這種情況下，modeling error會有很長的一段時間無法被偵測到(如果有的話)。
:::

:::info
Example 8.3: Shortcut Maze

Figure 8.5: Average performance of Dyna agents on a shortcut task. The left environment was used for the first 3000 steps, the right environment for the rest.

Figure 8.5說明上述環境變化所造成的問題。最一開始，最佳路徑就在障礙物的左邊(左上圖)。在3000個steps之後，右邊出現一個捷徑，這個捷徑並不干擾到原本較長的路徑(右上圖)。這圖說明著，regular Dyna-Q agent並沒有切換過去那條捷徑，never。事實上，它也從來沒有發現過有這條捷徑。它的模型(model)並不覺得有這麼一條捷徑，所以plan的愈多，就愈不可能往右，也就不可能去發現捷徑。即使你用$\epsilon-$greedy也不大可能讓agent做那麼多的探索行為(exploratory actions)來發現這條捷徑。

事實上這邊我們遇到的普遍問題是探索(exploration)與開發(exploitation)之間矛盾的另一種版本問題。在planning context中，探索意味著那些能夠改善model的actions，而開發則意味著當前model給出的最佳方式下的行為。我們希望agent能夠利用探索來發現環境的變化，但又不希望效能大幅的降低。這跟先前談論過的探索/開發(exploration/exploitation)的矛盾是一樣的，沒有特效藥，不過簡單的啟發式方法(heuristics)通常是有效的。

其實解決shortcut maze(捷徑迷宮)問題的Dyna-Q+ agent就是使用這種啟發式方法。這個agent持續的追蹤每一個state-action pair，它記錄從上次與環境的實際交互過程中嚐試這個pair已經經過多少個time steps。經過的時間愈長，我們就愈能推敲這個pair的動態性已經改變，而且模型也可能已經不正確。為了鼓勵測試長時間沒有試過的actions，只要在模擬經驗中有這些action，那就有一個特別的"bouns reward"。特別是，如果model對於轉移的reward是$r$，然後這個轉移在$\tau$個time steps中沒有被嚐試過，那planning updates的完成就好像是這個轉移產生了$r + k\sqrt{\tau}$的reward，其中$k$是比較小的數值。這鼓勵了agent持續的測試所有可能的state transitions(狀態轉移)，即使為了實現這樣的測試需要執行很多很多的actions。當然，這樣的測試是需要成本的，不過更多情況下，這種computational curiosity(好奇心)是值得的。

註：Dyna-Q agent以另外兩種方式改變。首先，允許在上面框框中的Tabular Dyna-Q algorithm的planning step ($f$)中考慮一個state中從來沒有出現過的actions。第二，這些actions的初始模型(initial model)會以0的reward回到相同的state。
:::

## 8.4 Prioritized Sweeping
前面介紹過的Dyna agents，其模擬轉移是起始於從所有先前所經歷過的pairs中隨機均勻選擇的state-action pairs。但是均勻選擇(uniform selection)通常不是最好的；如果轉擬轉移與更新關注在特定的state-action pairs上，那planning會更有效率。舉例來說，我們想想Figure 8.3這個迷宮任務在第二個episode發生什麼事。第二個episode的一開始，只有那些可以直接到達目標(goal)的state-action pair有正值(positive value)；其它的pairs仍然是0。這意味著你沿著所有的轉移過程做更新是沒營養的，因為它們只是帶著agent從一個value為0的state到另一個value為0的state，所以這個更新是無效的。只有在轉移到目標之前的state或從目標轉移到state的過程中做的更新才會有值(value)上面的異動。如果模擬轉移(simulated transitions)是均勻生成的，那麼在你真的發現到一些有效的轉移之前，你會做很多浪費性的更新。隨著planning的進展，有效的區域會一直增加，但是planning的效能仍然是遠不如將重點放在在最能發揮的地方。做為我們真正目標的更大問題中，states的數量是很多，多到沒朋友，以致於這種非聚焦的搜尋十分沒有效率。

上面的範例告訴我們一件事，那就是透過從目標狀態(goal state)反向作業，我們可以讓搜尋(search)這個動作可以比較聚焦(focused)。當然，我們並不是真的想要使用任何一種特定於"目標狀態"這個概念的方法。我們想要的是一個通用的reward function。而goal states只是一個用來激發想像的特例。一般來說，我們不止要從goal states反向回來，還要從任意一個值(value)改變的state反向回來。假設，給定model，然後最一開始這些value是正確的，就好像是在迷宮範例中，找到目標之前那樣子。假設，現在agent發現環境中的變化，並且改變一個state的估測值，向上或是向下。通常，這代表許多其它states的values也應該被改變，但是唯一有用的one-step updates是那些直接導致value改變的那個state的actions。如果這些actions的values被更新了，那麼前一個states的values可能就會陸續的改變。如果是這樣，導致進入這些states的actions就需要被更新，而且它們前面的states可能已經改變了。透過這樣的方式，我們可以從任意一個value有變化的的states反向作業(work backward)，要嘛做有效的更新或終止這個傳播(propagation)。這樣子的想法可以稱為backward focusing of planning computations(規劃計算的反向關注?)。

隨著有效更新的[邊界](http://terms.naer.edu.tw/detail/2116526/)反向傳播，它通常會快速的增長，然後產生很多可以被有效更新的state-action pairs。但並非所有這些都是同樣有效的。有些states的values也許會有很大的變化，而另一些可能就只改變一些些。那些發生很大變化的前面的pairs可能會變生很大的變化。在一個隨機環境中，估測的轉移機率的變化也會影響著改變的大小以及需求更新的state-action pairs急迫性的變化。很自然的，我們對於這些更新的優先順序就會根據它們所量測出來的急迫性，然後按順執行。這就是prioritized sweeping背後的想法。每個state-action pair都會維護一個隊列(queue)，如果這些pairs有更新，那它的估測值的變化就會很大，我們會根據變化大小做順序排列。當隊列中最上面的那個pair(top pair)被更新了，就會計算對它的前導(predecessor)的pairs的影響。如果影響大過某個小閥值，那這個pair就會以新的優先序被插入隊列中(如果隊列已存在這個pair，那就只保留有較高優先序的那個)。以這樣的方式，改變的影響就會有效的反向傳播直到靜止。下面給出完整的演算法：

:::info
Example 8.4: Prioritized Sweeping on Mazes

Prioritized sweeping可以明顯地提高在迷宮任務中找尋最佳路徑的速度，通常是5到10倍。一個常見的範例如下圖：

這些資料跟Figure 8.2看到的是完全相同的結構，就只有[網格的解析度](http://terms.naer.edu.tw/detail/389282/)不同。Prioritized sweeping比起非優先序的Dyna-Q有著明顯優勢。兩個系統在每次與環境互動中，最多就是做了$n=5$的更新。故事範例改編自Peng and Williams (1993)。
:::

將prioritized sweeping擴展到隨機環境是很簡單的一件事。這模型是利用持續的計算每個state-action pair被看過的次數以及下一個會是什麼state來維護。而且不是像之前一樣的用一個樣本來更新，而是考慮所有可能的下一個state以及它們可能發生的機率來更新，也就是expected update。

Prioritized sweeping就只是一種以分佈式計算來改進planning效率的一種方式，而且它可能不是最好的。prioritized sweeping的其中一種限制就是它使用expected updates，這在隨機環境中也許會浪費不少計算資源在一些較低機率轉移上。如我們在一章所說的那樣，儘管採樣會引起方差問題，但在很多情況下，樣本更新(sample updates)可以用較少的計算得而更接近true value function的結果。Sample updates的勝利是因為它們把整個backing-up的計算拆解的比較小(WBS的概念?)，也就是那些對應個別轉移的部份，它就可以更關注在那些會造成最大影響的部份。這種"small backups"是由van Seijen and Sutton (2013)所引入。這些是沿單一轉移的更新，如樣本更新(sample update)，但是是基於沒有採樣的轉移機率，像是expected update(期望更新?)。透過選擇完成那些小範圍更新的順序，我們可以大幅度的提升planning的效率，超過prioritized sweeping。

這一章我們已經指出，所有類型的state-space planning都可以被視為是value updates的順序，只有在更新類型(expected或是sample)、大或小、以及更新完成的順序上有所不同。我們也強調了backward focusing(反向關注?)，不過這只是一種策略。舉例來說，也許有一種方法是關注在states上，根據什麼？根據當下的policy從那些經常遇到的states到達它們有多麼容易，這可以稱為forward focusing(前向關注?)。後續會介紹一下一種極端的形式。

:::warning
如果你有去追蹤程式的執行的話，第一次你的priority會有值的是在你到達GOLE_STATE的時候，`priority=1`，然後`state=[1, 8], action=0`的這個pair的value會是0.5，因為你的$\alpha=0.5$，接著就會去看到達`[1, 8]`這個state之前是那一個state-action pair，也就是`state=[2, 8], action=0`，我們會去更新這個pair的`priority=0.475`，大於閥值，你會寫入Priority Queue，這時候你的Priority Queue又有新的一筆資料進去，迴圈會繼續執行，你會一路往前把相關走過的路計算一次它的priority，然後更新一次它的action value，直到計算出來的priority不再大於閥值。所以可能光是一個step你就會計算很多次的priority，下一個step你就會再根據新計算到的priority去取得queue裡面的那個root的資料出來再做一次計算更新。
:::
## 8.5 Expected vs. Sample Updates
前面的範例給出了結合learning與planning的可能性範圍的一些想法。本章剩下的部份，我們會分析一些所涉及到的組成，就讓我們從expected updates與sample updates的相對優勢開始聊起吧。

對於不同類型的value-function的更新(updates)我們已經談過很多種類型了。且讓我們關注一下one-step updates，它們的變化主要是沿著三個binary dimensions(二元維度?)。前兩個維度它們是否更新state values或是action values，以及它們是否是用optimal policy或是一個任意給定的policy來估測出這個value的。這兩個維度造就出四個類別(four classes)的更新，這更新即是用於近似四個value function，也就是$q_*, v_*, q_\pi, v_\pi$。剩下一個維度則是判斷這個更新(update)是否為expected updates(我們考慮所有可能也許會發生的事件)，或者這次的更新(update)是sample update，只考慮單一個樣本的情況。這三個binary dimensions產生八種情況，其中七種情況會對應於特定的演算法，而第八種則不對應任何有效的更新，如下所示：

Figure 8.6: Backup diagrams for all the one-step updates considered in this book.

這邊任一個one-step updates都可用在planning methods。我們前面談過的Dyna-Q agents就是用$q_*$ sample updates，但是它也可以用$q_*$ expected updates，以及$q_\pi$的expected、sample updates。Dyna-AC system則是使用$v_\pi$ sample updates以及learning policy structure(學習策略結構?)，這在Chapter 13會談到。而隨機問題的話，prioritized sweeping則總是使用expected updates的其中一種來完成更新。

當我們在Chapter 6介紹one-step sample updates的時候，我們是把它做為expected updates的一種替代方法。在你沒有[分散模型](http://terms.naer.edu.tw/detail/14368363/)(distribution model)的情況下，expected updates是不可能的，但是sample updates是可以利用使用來自環境或是樣本模型(sample model)的樣本轉移來完成的。這似乎在暗示我們，如果可能的話，expected updates是比sample updates還要來的好。但事實真的是這樣嗎？Expected updates當然會產生更好的一個估測值，這是因為它們並不會受到採樣誤差(sampling error)的影響，但它們同時需要更多的計算資源，而計算資源通常在planning中是有限的。為了可以好好的評估expected updates與sample updates對planning的相對優點，我們必需要控制它們不同的計算需求。

具體來說，讓我們來考慮一個近似$q_*$的expected updates與sample updates，這個特殊狀況中它的states與actions都是離散的，然後用[查表法](http://terms.naer.edu.tw/detail/2454694/)做為approximate value function $Q$的表示，模型估測的動態性則以$\hat{p}(s', r\vert s, a)$來表示。這樣，對於一個state-action pair $s, a$的expected update就是：
$$
Q(s, a) \leftarrow \sum_{s', r}\hat{p}(s', r \vert s, a)[r + \gamma \max_{a'} Q(s', a')] \tag{8.1}
$$

相對於sample update對於$s, a$，給定一個樣本的next state與reward，$S', R$(從模中取得)，則是一個Q-learning-like的更新：
$$
Q(s, a) \leftarrow Q(s, a) + \alpha[R + \gamma \max_{a'}Q(S', a') - Q(s, a)] \tag{8.2}
$$

其中$\alpha$通常是一個positive step-size parameter(正值)。

而兩者之間(expected update、sample update)的差異很明顯的是出於環境的隨機性，具體而言，從這點看來，給定一個state、action，很多可能的next states會以不同的機率來發生。如果只有一個next state是可能的，那上面給出的兩個式子的結果基本上會是相同的(採用$\alpha=1$)。如果有很多可能的next states，那可能就會有著很明顯的差異。有利於(In favor of)expected update的是，它是一個精確的計算，這生成了一個新的$Q(s, a)$，其正確性僅受到後續狀態$Q(s', a')$的限制。此外，sample update還會受到sampling error(樣本誤差)的影響。另一方面，sample update需要的計算力比較少，因為它只需要考慮next state，而不是所有可能的next state。實務上，這種更新操作(update operations)的計算需求通常是由你評估$Q$的state-action pairs的數量來決定的。對於特定的起始的state-action pair，$s, a$，我們假設$b$是[分支因素](http://terms.naer.edu.tw/detail/13763675/)(branching factor)，也就是所有可能的next states $s'$的數量，其中$\hat{p}(s'\vert s, a) > 0$。這樣，這個pair的expected update的計算量就大概是sample update計算量的$b$倍。

如果有足夠的時間完成一次的expected update，那麼得到的估測結果通常會比$b$個sample updates還要來的好，因為expected update並不存在樣本誤差。不過如果沒有足夠的時間可以完成expected update，那sample updates通常是比較合適的，因為sample updates或多或少還是可以改善一下估測值的部份(少於$b$次更新的情況下)。在一個有很多state-action pairs的大型問題中，通常是後面那種情況(sample update)。因為這種大型問題採用expected update會需要很長的時間才能完成(會看過所有可能的state-action pairs)。給定一個計算單位，那一種方法(expected update、$b$ times sample updates)會比較好？

Figure 8.7給出一個分析的結果，為這問題給出答案：

Figure 8.7: Comparison of efficiency of expected and sample updates.

上圖說明了，在不同的分支因素$b$的情況下，expected updates與sample updates的估測誤差與計算時間(computation time，次數?時間?)的函數之間的變化。這個情況考慮的是，所有$b$個後續的狀態(successor states)的發生機率是相等的，而且其初始估測誤差為1。我們假設下一個states的values是正確的，因此expected update在完成的時候會將誤差降低為0。這種情況下，sample updates則是根據$\sqrt{\dfrac{b-1}{bt}}$來降低誤差，其中$t$是sample updates已經被執行過的次數(假設是sample average，也就是$alpha = 1/t$)。這其中的關鍵就是，如果是大小適中的$b$，那誤差就會隨著$b$一小部份的更新而大幅度的下降。對於這些情況，很多的state-action pairs的values能夠顯著的提升，達到expected update的差不多的效果(要打一點折扣)，同時，單個state-action pair也可以得到預期的更新。

Figure 8.7說明的sample updates的優點很可能是實際效果被低估了。在實際問題中，後續狀態(scuuessor states)的values會是自身更新的估測值。透過讓估測的速度更快更凖確，sample updates就出現第二個優點，也就是來自後續狀態(successor states)backed up的values會更準確。
## 8.6 Trajectory Sampling
這一章節中，我們會比較兩種distributing updates的方法。來自動態規劃(DP)的一種經典方法就是掃過(sweep)整個state space(或state-action space)，在每一次的掃的過程中更新每一個state(或state-action pair)。這在大型問題中可能是有問題，因為你沒有那個命可以去掃過整個空間。在多數的任務中，絕大多數的states是不相關的，因為它們只有在非常爛的policy下才會有機會被喵過一次，不然就是被喵過的機率非常低。那這種完整的掃過一次的方式就變成是把時間平均的分給state space的所有pairs，而不是關注在所需要的地方。就如同我們在Chapter 4談過的，這樣的方式並不是動態規劃(DP)的必要屬性。原則上，更新是可以用你喜歡的任何方式來分配的(為了確保收斂性，所有的states或是state-action pairs都要在限制內被無限次的喵過；下面8.7會說說例外)，只是窮舉掃過一次(exhaustive sweeps)的這方式比較常用。

第二種方法就是根據某一個分佈來做採樣(從state space或是state-action space)。我們可以像在Dyna-Q agent那樣做均勻採樣，不過這可能會跟窮舉掃過一次的方式一樣遇到一些問題。比較有吸引力的方式就是根據on-policy distribution來分配更新(distribute updates)，也就是根據當下的policy所觀察到的分佈來做分配更新。這種分佈(distribution)的一個優點就是這很容易生成；只要用當下的policy跟model互動一下就行了。在episode類型的任務中，我們會從起始狀態(start state)(或是根據starting-state distribution)開始，然後模擬狀況一直到終止狀態(terminal state)。如果是連續型的任務(continuing task)，你就可以從你想要的state開始，然後模擬到你開心。不管是那一種類型的任務，樣本的state transitions與rewards都是由model所給出的，而樣本的actions則是由當下的policy所給出。換句話說，我們可以模擬，然後得到個別的軌跡(trajectories)，然後對沿路遇到的state或state-action pairs來做更新。我們把這種生成經驗並更新的方法稱之為trajectory sampling。

很難想像除了trajectory sampling之外，還有什麼有效的方法可以讓我們根據on-policy distribution來做分配更新(distributing updates)。如果我們已經很明確的知道on-policy distribution，那你就直接怒掃一發，全部看過一次，然後再根據on-policy distributiona對每個state的更新做加權計算，但這又回到我們一開始說過的，窮舉掃過所需要的計算成本。可能我們可以從分佈中做採樣，然後個別更新state-action pairs，不過，即使這可以很快的完成，但是對比simulating trajectories又有什麼好處呢？即使很明確的知道on-policy distribution也是不可能的。只要policy改變，distribution就會跟著改變，你去計算這個distribution所需要的計算資源跟做完成的policy evaluation是差不多的。考慮到其它的可能性，這讓trajectory sampling看起來美觀又大方(有效又優雅)。

這種on-policy distribution的updates真的是好的嗎？直覺上是一個不錯的選擇，至少比均勻分佈還要來的好。舉例來說，如果你學著去玩西洋棋，你學到的可能就是實際賽局中可能出現的位置，而不是棋子的隨機位置。後者可能是有效狀態(valid states)，但是能夠準確的評估它們跟評估真實遊戲中的位置是不同的技能。後面第二部份我們還會看到，當使用function approximation的時候，on-policy distribution有著明顯的優勢。無論是否使用function approximation，我們都會期待聚焦on-policy 可以顯著的提高planning的速度。

聚焦(關注)在on-policy distirbution也許可能是有一點點點的好處的，因為它導致大量空間中不重要的部份被忽略掉，或者也可能是有害的，因為它會導致空間中老樣子(same old)的部份一次又一次的更新。我們弄一個小實驗來評估相關影響。為了隔離更新分佈的影響，我們完全使用8.1所定義的one-step expected tabular updates。在均勻分佈的情況下(uniform case)，我們循環遍歷所有的state-action pairs，然後每個pair都以in-place的方式來更新，在on-policy的情況下，我們會模擬episodes，全都以相同的state來開始，接著更新當前$\epsilon-$greedy policy($\epsilon=0.1$)下發生的每一個state-action pair。這些任務都是undiscounted episodic類型，都是如下隨機生成。從$\vert \mathcal{S} \vert$的每個states，有兩個actions是可能的，每一個action都會導致$b$個下個states的其中一個，所有這些states的機率是相同的，只是說，每個state-action pair都會有不同的$b$ states的隨機選擇。所有的state-action pairs的branching factor，$b$都是相同的。另外，在所有的狀態轉移過程中，都會有0.1的機率終止狀態(terminal state)，然後就結束這個episode。每一個轉移的expected reward都是從均值為0且方差為1的高斯分佈中選擇。在planning process的任一個點，我們都可以停止，然後徹頭徹尾的計算$v_{\tilde{\pi}}(s_0)$，也就是greedy policy $\tilde{\pi}$下的起始狀態(start state)的真實值(true value)，由當下的action value function $Q$所給出，這可以做為agent在一個新的episode上greedy可以表現的多好的一個指標(都是建立在假設model的一切都是正確的前提下)。


Figure 8.8: Relative efficiency of updates distributed uniformly across the state space versus focused on simulated on-policy trajectories, each starting in the same state. Results are for randomly generated tasks of two sizes and various branching factors, b.

Figure 8.8的上圖呈現出200多個樣本任務的平均結果，其中這些任務有1000個states，然後它們的branching factors為1、3、10。The quality of the policies found is plotted as a function of the number of expected updates completed(翻不出來~"~)。在所有情況下，根據on-policy distribution來採樣(sampling)在初期的時候planning的速度是更快的，但長遠來看整個變化是遲緩的。結果來看，愈小的branching factors的效果更強，而且初期的那種飆速持續的更久。在其它實驗中，我們發現到，隨著狀態(state)數量的增加，這些影響就愈強烈。舉例來說，Figure 8.8就說明著任務擁有1000個states，且branching factor為1的結果。這種情況下，on-policy focusing的優勢是非常大，而且持久。

這些實驗結果都是有道理的。短時間內，根據on-policy distirbution來採樣有助於聚焦(focusing)接近起始狀態的後代(descendants)狀態。如果states很多，而且branching factor很小，那影響就會又大又持久。長遠來看，關注於on-policy distribution也許是有害的，因為常見的states都已經有它們所屬的正確的值(value)了。這時候你還去對他們做採樣是沒什麼用的，反而你去對其它states做採樣可能還會有一些實質上的幫助。這或許就是為什麼窮舉(exhaustive)、非聚焦(unfocused)的方法在長時間來看是這樣的。這些結果並不是最終的結論，因為它們只適用於以特定隨機方法生成的問題，但它們也確實說明了，根據on-policy distribution做採樣(sampling)對於大型問題有著很大的優勢，特別是針對在on-policy distribution下只有一小部份的state-action space會被看到的那種問題由其適用。
## 8.7 Real-time Dynamic Programming
Real-time dynamic programming，或稱RTDP，它是一種動態規劃(DP)value-iteration algorithm的on-policy trajectory-sampling。因為它跟傳統那種sweep-based policy iteration密切相關，因此，RTDP可以以特別清晰的方式來描述on-policy trajectory sampling能夠提供的一些優勢。RTDP用4.10這個方程式所定義的tabular value-iteration updates來更新那些實際或是模擬軌跡(simulated trajectories)中看過的那些states的values。基本上這演算法會產生如Figure 8.8中那個on-policy所生成的結果。

:::warning
$$
\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}
$$
:::

RTDP與傳統的DP之間的緊密連結讓我們可以利用一些已經存在的理論來推導出一些理論結果變成是有可能的。RTDP是一種非同步DP演算法(見[Section 4.5](https://hackmd.io/@shaoeChen/SydNt5G3_#45-Asynchronous-Dynamic-Programming))。非同步DP演算法並非以系統性掃過(sweep)狀態集合(state set)所組成；它們可以以任意的順序來更新state values，或是任何其它states可能發生的值來更新。在RTDP中，更新順序是由在實際或模擬軌跡(simulated trajectories)中遇到的states的順序來決定的。如果trajectories可以只從一組我們所指定的起始狀態(start state)開始，而且你也剛好對給定policy之後的預測問題(prediction problem)感興趣，那麼，on-policy trajectory sampling可以讓演算法完整的跳過(skip)那些給定policy之後從任意的start state無法到達的states：這類的states跟預測問題是無關的。對於控制問題(control problem)，其目標就是找出optimal policy，而不是評估一個給定的policy，很可能會有stats是任何的optimal policy從任意的start states都無法到達的，而且不需要去為這些不相關的states去指定optimal actions。你所需要的就是一個optimal partial policy，意思就是說，這個policy對於相關的states是optimal，而對那些不相關的states你可以指定任意的actions或者不定義也無所謂。


只是厚，你要用on-policy trajectory-sampling control methods來找出這樣一個optimal partial policy，像是用Sarsa([Section 6.4](https://hackmd.io/@shaoeChen/Byd6HbFa_#64-Sarsa-On-policy-TD-Control))，通常需要看過所有的state-action pairs，即使那些被證明是不相關的也要看過，如果真要說出一個要看幾次的數字，那就是無限次。這你可以用[Section 5.3](https://hackmd.io/@shaoeChen/rJ46Bsqu_#53-Monte-Carlo-Control)提出的那個exploring starts來完成。對RTDP也是如此：對於exploring starts的episodes類型的任務，RTDP就是一個非同步的value-iteration algorithm，它可以收斂到optimal policies(對於discounted類型的finite MDPs，以及部份條件下的undiscounted類型的finite MDPs)。跟預測問題的情況不同，如果收斂到optimal policy是重要的，那它通常不可能停止對任何的state或是state-action pair更新。

RTDP最有趣的結果就是，對於滿足合理條件的部份類型的問題，RTDP保證能夠相關狀態(relevant states)找到optimal policy，不需要無限次的去看過每一個state，甚至有些states連看它一眼都不需要。事實上，在某些問題中，你也只需要看過一小部份的states就夠了。這對state sets非常大的問題來說是很大的優勢，有些state set大到你連掃過一次都很難了。

如[Section 3.4](https://hackmd.io/@shaoeChen/Hkm3mMjL_#34-Unified-Notation-for-Episodic-and-Continuing-Tasks)所說，適用這個結果的任務是那些沒有折扣(undiscounted)的episode類型的任務(absorbing goal states，且reward=0)。在實際(real)或是模擬軌跡(simulated trajectory)的每一個step，RTDP選擇一個greedy action(機率相等就隨機選擇)，然後在當前的state中做expected value-iteration update的操作。這樣還可以在每一個step去更新其它states的任意集合的values；舉例來說，它可以從當前的狀態(current state)更新那些在有限範圍內(limited-horizon)用look-ahead search看過的states的value。

對於這些問題來說，每一個episode都是隨機從start states的集合中選擇一個state開始，然後到達目標狀態(goal state)之後結束，RTDP則是會以1的機率收斂到對所有相關states而言是optimal的policy，前提是：
1. 每一個目標狀態(goal state)的初始值為0
2. 存在最少一個policy可以保證，從任意的起始狀態(start state)到達目標狀態(goal state)的機率為1
3. 來自非目標狀態(non-goal states)的轉移報酬(reward)都是負值
4. 所有sates的初始值(initial values)都大於等於它們的最佳值(optimal value)，這條件你可以讓所有初始值皆為0就可以滿足

這個由Barto, Bradtke, and Singh (1995)結合非同步DP與Korf(1990)提出的learning real-time $A^*$，也就是heuristic search algorithm的結果來證明上面的結論。

隨機最佳路徑問題(stochastic optimal path problems)就有著上面那些特性，只是這個任務通常都是要成本最小化，而不是我們做的報酬最大化。不過你可以最大化負的returns就可以達成這個目標了。這類任務通常都是要最小化時間的控制任務，因此你在到達目標前的要且個time step都會產生1的reward，或是像[Section 3.5](https://hackmd.io/@shaoeChen/Hkm3mMjL_#Example-36-Golf)的那個高爾夫任務，以最少的擊球次數為目標。

:::info
Example 8.6: RTDP on the Racetrack
Exercise 5.12的賽車道(racetrack)問題是一個隨機最佳路徑題。利用這個範例來比較RTDP與傳統DP的value iteration，然後說說在on-policy trajectory sampling的一些優點。


回想一下練習中，agent要學著如何開車繞著像Figure 5.5的那個彎道，然後盡可能的快一點到達終點。start states都會是在起跑線上(starting line)，速度都是0；goal states是所有可以從賽道內以一個time step越過終點線(finish line)的所有states。不像Exercise 5.12，這邊對車子的速度是沒有限制的，因此它的state set可能是無限的。不過，通過任意的policy從start states的集合可以到達的states的集合是有限的，我們可以把它想成是問題的state set(狀態集合)。每一個episode都是從隨機選擇的start state開始，然後在車子越過終點線的時候結束。每個step的reward都是1，一直到車子超過終點線。如果車子撞到邊邊，那它就會回到一個隨機的start state，然後繼續這個episode。

Figure 5.5中，類似於它左邊那個小賽道就有著9115個states是你可以用任意的policy從start states到達的，但是這其中只有599個是相關的，這意味著它們是可以從某些start state通過某些optimal policy到達的(相關state的數量是經過七七四十九天在$10^7$個回合中以optimal actions所看過(visited)的states所估算的)。

下面的表給出用傳統的DP跟RTDP解這個任務的比較。這些結果是執行25次的平均結果，每次都是以不同的random number seed來開始。這種情況下，傳統DP採用的是窮舉(exhaustive)掃過(sweep)整個state set來做value iteration，每次都會in-place的更新一個state的value，這意味著每個state在更新的時候都會用著其它的states的最新的values(這屬於Gauss-Seidel版本的value iteration，在這問題上，它的速度會是Jacobi版本的兩倍，可參考[Section 4.8](https://hackmd.io/@shaoeChen/SydNt5G3_#48-Summary))。沒有特別的去處理更新的順序；其它的排序方式可以有更快的收斂速度。兩個方法的初始值全部都是0。DP的話，value的差異小於$10^{-4}$，那就當做它已經收斂完成(這部份可以從Chapter 4的實作中瞭解意思)，然後RTDP就看它在20個episodes越過終點線的平均時間趨於穩定的時候(以漸近的步數)，那就視為收斂。這個版本的RTDP單純的更新每個step的當前狀態(current state)的值(value)。


兩個方法產生的policies平均都需要14、15個steps之後才能成功的越過終點線，但是RTDP只需要大約DP一半的更新(updates)就可以成功。這歸功於RTDP的on-policy trajectory-sampling。儘管DP會在每一次掃過states的時候更新每一個state的value，但是RTDP只會關注在那些少數需要更新的states上。平均執行中，RTDP有98.45%的states更新不超過100次，而且有80.51%的states更新好超過10次；而且厚，還有290個states更本是完全沒有更新。

RTDP的另一個優點就是，當value function近似於optimal value function $v_*$的時候，agent用來生成trajectories的policy就會接近optimal policy，因為它對當下的value function永遠都是greedy的。這跟傳統的value iteration中的情況是相反的。實務上，value iteration的終止條件是當value function的改變只剩一咪咪的時候就停止迭代，上面表格內的結果也是這樣來的。這時候，value function會非常近似$v_*$，而且greedy policy也會接近optimal policy。然而，在value iteration終止之前，對最新一個value function做greedy actions的policy就或許可能也已經是optimal policy(這可以從Chapter 4中的[gridworld](https://hackmd.io/@shaoeChen/SydNt5G3_#41-Policy-Evaluation-Prediction)範例看的出來)。我們在value function收斂之前去檢查optimal policy是不是已經出現的這個部份，它並不是傳統DP演算法中的一部份，而且這需要大量額外的計算資源。(我們第四章練習value iteration也是收斂之後才開始做policy improvement。)

在這個賽道範例中，利用在每次DP掃過之後執行多個測試的episodes(test episodes)，並且會根據掃過的結果做greedy的選擇，這樣你就可以去估測在DP計算中那個近似最佳評估函數(optimal evaluation function)是足夠好的那個earliest point(最早的那個時間點?)，因此相對應的greedy policy就幾乎是最佳的了。對這個賽道任務來說，在15次的value iteration的掃描(sweep)之後，又或者是在136725次value-iteration的更新之後，聖光出現了，一個接近最佳的policy出現了。這遠低於DP要收斂到$v_*$的更新次數(252784次)，不過還是比RTDP需要的更新次數還要來的多(127600次)。

雖然這樣的模擬結果並不是兩種方法很明確的比較，但是還是可以說明on-policy trajectory sampling的一些優點。雖然傳統的value iteration會持續的更新所有states的value，而RTDP會強烈的關注在跟問題的目標相關的狀態的子集合。隨著不斷的學習，關注的範圍會愈來愈小。因為RTDP的[收斂定理](http://terms.naer.edu.tw/detail/3651021/)適用於模擬，我們知道RTDP終究會只關注在相關的狀態(states)上，也就是那些構成最佳路徑的states。RTDP只需要sweep-based value iteration 50%的計算資源就可以達到近乎optimal control。
:::
## 8.8 Planning at Decision Time
planning至少有兩種方式可以使用。一種是目前為止我們在這一章裡面聊過的，以DP、Dyna為代表，會根據那些從模型(model)獲得的模擬經驗，然後使用planning逐漸的改善policy或是value function。選擇actions是比較當前state的action values的問題(這個values來自目前為止我們已經考慮過的tabular case的表格)，或是評估我們在Part II中考慮的近似方法中的數學表達式(後面的內容)。在為任意的當前的state $S_t$選擇action之前，planning已經在改善table entries(表格條目?)或函數近似參數(function approximation parameters)起了一部份的作用，其中參數要替很多states選擇action，包含$S_t$。用這個方法，planning就不會關注在當下的state。我們稱這種方法的planning為background planning。

另一種planning的話就是，當我們遇到每一個新的state $S_t$之後，我們才開始然後完成這個planning，做為一個計算的話，它的輸出就是選擇一個action，也就是$A_t$；下個step的planning就會又一次的在$S_{t+1}$生成一個$A_{t+1}$，以此類推。這個planning的一個最簡單而且最腦殘的範例就是，當你只有state values能用的時候，那我們就拿每個action的下一個states由模型預測出來的values做比較。普遍來說，用這樣的方式使用planning可以看的比one-step-ahead還要深，而且對於評估action的選擇也會導致不同的預測狀態(state)與報酬(reward)的軌跡(trajectory)。跟上面說的那種不一樣，這邊的planning關注在特定的state。我們稱之為decision-time planning。

關於planning的兩種思考模式，使用模擬經驗來逐步的改善policy或是value function，或是使用模擬經驗來為當下狀態(current state)選擇action，我們可以很自然的把這兩種方式混合在一起，不過還是先分開來看，這會是瞭解它們的一個好的方法。讓我們靠近一點看看decision-time planning。

即使只會在decision time處理planning，我們還是可以像在Section 8.1做的那樣，從模擬經驗到updates與values，最終到policy。只不過現在這些values與policy是針對當下的state與可以選擇的actions，如此以至於透過planning過程所建立的values與policy通常會在被用於選擇當下的action之後被丟棄。在很多應用程式中，這並不是一個很大的損失，因為有很多的states，而且我們不大可能在一段時間之內回到相同的state。通常，我們會想要把兩者結合來執行：讓planning關注在當下的state，並保存planning的結果，這樣後面我們再回到相同的state的時候就可以更進一步的處理。decision-time planning在不需要快速回應的應用程式中是最有效的。在西洋棋的程式中，舉例來說，每個移動可能會允許有幾秒或幾分鐘的計算，而那些很強的程式就可能在這個時間中給出幾十個移動選項。另一方面，如果選擇action我們要的是低延遲的話，那麼最好在background做planning然後計算出一個policy可以快速應用在每一個新遇到的states上。
## 8.9 Heuristic Search
人工智慧中經典的state-space planning methods就是decision-time planning methods，統稱為heuristic search([啟發式搜尋](http://terms.naer.edu.tw/detail/2117193/))。在heuristic search中，對每一個遇到的state，我們都會把它想成是一個很大的tree，有這個state的後續的延申。然後我們會在leaf nodes(葉節點)用approximate value function(近似價值函數)，然後再backed up(回推)到當前的state(root)。這種search tree中的backing up跟我們在書上談過以最大值做expected update($v_*, q_*$)是一樣的。那，backing up會在當下的state七state-action nodes處停止。一旦計算完這些節點的backed-up values，我們就會選裡面最好的來做為這次的action，然後丟掉所有的backed-up values。

傳統的heuristic search是不會去利用改變approximate value function來保存backed-up values。事實上，value function通常是人設計的，所以不會因為search而改變。所以，我們可以自然的覺得value function會隨著時間而改善，不論是在heuristic search期間計算backed-up values還是書上談過的任一種方法。某種角度來說，我們一直在用這種方法。也就是greedy，$\epsilon-$greedy，跟UCB action-selection methods，這跟heuristic search並無不同，只是規模小了點。舉例來說，為了計算一個給定一個模型(model)與state-value function的greedy action，我們必需要從每一個可能的action往前看一步，看過每一個action之後的下一個state，然後考慮其報酬(rewards)與估測值(estimated values)，然後選一個最好的action。這就跟在傳統的heuristic search一樣，這個過程計算可能的actions的backed-up values，只是不會試著去保存它們而以。因此，heuristic search可以被視為是single step greedy policy的一種擴展應用。

比one step搜尋更深的一個重點就是為了得到更好的選擇(關於actions的選擇)。如果你有一個完美的模型跟一個不完美的action-value function，那更深的搜尋通常可以得到更好的policies。當然啦，如果搜尋(search)就是一路一直到episode的終點，那這個不完美的action-value function的影響就會被消除，而且用這方法確定的action一定、肯定、絕對就是optimal。如果我們search很深，就跟$k$一樣深，以至於$\gamma^k$就會很小，那actions就會相對的接近optimal。另一方面，愈深的搜尋(search)，你需要的計算資源就愈多，那你的反應時間就會慢。這在Section 16.1會有一個很好的範例，Tesauro的大師級[雙陸棋](https://zh.wikipedia.org/zh-tw/%E9%9B%99%E9%99%B8%E6%A3%8B)(我應該翻不到Orz)。這個系統用TD learning透過self-play的方式來學習afterstate value function，然後使用heuristic search來確定下那一子。做為模型，TD-Gammon用了丟骰子機率的先驗知識，然後假設對手一直都是選擇TD-Gammon認為是最好的那個actions。Tesauro發現，heuristic search的愈深，TD-Gammon下的棋就愈好，不過每一子的思考需要的時間就愈長。雙陸棋有很大的分支因素(branching factor)，但它必需要在幾秒內決定怎麼走。所以你也只能選擇性的向前看個幾步，不過即使如此，仍然會產生明顯更好的action的選擇。

我們不應該忽略掉heuristic search關注更新(focuses updates)最明顯的方式：也就是當前的狀態(on the current state)。heuristic search大部份的有效性都是由於它的[搜尋樹](http://terms.naer.edu.tw/detail/13855595/)(search tree)緊密的關注在那些緊跟在當前狀態(current state)之後的states與actions。你可能會花很多的生命在下西洋棋而不是跳棋，不過當你玩跳棋的時候，它會去關心一下跳棋跟你的特定的跳棋的位置、你可能的下一步跟後續的位置。不論你選那一個actions，這些states跟actions對更新(updates)而言都是有最高的優先序，也就是你急迫希望你的approximate value function能夠準確的地方。你的計算資源跟有限的記憶體資源都應該優先用於即將發生的這些事件。舉例來說，西洋棋中，有太多的可能位置而導致你無法去為每一個位置都各別的保存它們的估測值，但是基於heuristic search的西洋棋(chess)程式可以很輕鬆的保存各別的估測值(從一個單一的位置往前看數百萬個可能的位置)。這種記憶體與計算資源高度關注在當前的決策，大概就是heuristic search可以這麼有效的原因。

更新的分配(distribution)可以用類式的方式來改變，關注在當前的state與它可能的後續狀態(successors)。做為一個[極端的情況](http://terms.naer.edu.tw/detail/2118895/)，我們可能要完全的用heuristic search來建構search tree，然後各別的執行one-step updates(從下到上)，如Figure 8.9所示。如果更新(updates)的順序是用這個方法，並且使用tabular representation([表狀表式](http://terms.naer.edu.tw/detail/1287543/))，那我們就會得到跟depth-first heuristic search完全相同的整體更新(overall update)。任一個state-space search都可以用這種方式將之視為是將很大量的各別的one-step updates的拼湊。因此，以deeper searches所觀察到的效能的改善並非因為用了multistep updates。而是因為，更新(updates)是關注並集中在當前狀態(current state)的下游(downstream)的states與actions。透過投入大量與候選動作(candidate actions)特別有相關性的計算，decision-time planning可以產生比取決於unfocused updates更好的決策


Figure 8.9: Heuristic search can be implemented as a sequence of one-step updates (shownhere outlined in blue) backing up values from the leaf nodes toward the root. The ordering shown here is for a selective depth-first search
## 8.10 Rollout Algorithms
Rollout algorithms是decision-time planning based on Monte Carlo control的一種演算法，可以用於模擬軌跡(trajectories)，所有的軌跡都是起始於當前的環境狀態(current environment state)。這方法利用平均很多模擬軌跡的returns來估測一個給定policy的action values(這些軌跡會以每一個可能的action來做為開始，然後依著給定的policy執行)。當action-value的估測被認為準確度是足夠的時候，那有最高估測值的那個action(或是其中一個action)就會被執行，然後從產生的下一個state再重新執行一次這個過程。一如Tesauro與Galperin (1997)所解譯，他們做了個實驗，用rollout algorithms來玩雙陸棋，"rollout"這個術語是來自於利用playing out(結束遊戲?)來估測雙陸棋位置的value，也就是利用隨機生成的丟骰子序列，然後多次的"rolling out"當前位置到賽局的結束，其中兩個玩家的移動決定都是由某些固定的策略(policy)所決定的。

不同於Chapter 5所說的Monte Carlo control algorithms，rollout algorithm並不是估測給定一個policy的完整的optimal action-value function，$q_*$，或是完整的action value function，$q_\pi$。相反的，它們只對每一個當下的狀態(current state)生成用Monte Carlo估測的action value，然後對給定的policy則稱為rollout policy。如同decision-time planning algorithms，rollout algorithms會立即性的去使用這些action-value的估測值，然後就丟掉它們。這讓rollout algorithms的實現相對簡單，因為不需要去對每一個state-action pair做採樣，而且也不需在state space或是state-action space上去近似一個函數。

那，，到底rollout algorithms完成了什麼東西?[Section 4.2](https://hackmd.io/@shaoeChen/SydNt5G3_#42-Policy-Improvement)提到的策略改進理論(policy improvement theorem)跟我們說了一件事，給定任意兩個policies，$\pi$與$\pi'$，對於某些的state $s$來說，除了$\pi'(s)=a\neq\pi(s)$之外，它們是一樣的，如果$q_\pi(s, a) \geq v_\pi(s)$，那policy $\pi'$就會跟$\pi$一樣好，甚至比它更好。再者，如果不等式是嚴謹的(strict，或完全正確)，那麼$\pi'$就會比$\pi$還要來的好。這適用於rollout algorithms，其中$s$是當下的狀態(current state)，而$\pi$則是指rollout policy。平均模擬軌跡(simulated trajectories)產生的每個action $a' \in \mathcal{A}(s)$的估測值$q_\pi(s, a)$。然後policy會在state $s$的時候選擇一個最大化這些個估測值的action，然後我們就會依著那些好的policy的候選$\pi$來改進policy。這個結果就像是Section 4.3中討論的動態規劃(DP)的policy-iteration的一個步驟(雖然它看起來更像是Section 4.5中所討論的asynchronous value iteration，但因為它只改變當前狀態(current state)的action)。

換句話說，rollout algorithms的目的在於改進rollout policy，而不是找到一個optimal policy。從經驗來看，rolout algorithms出人意料的有效。舉例來說，Tesauro and Galperin (1997)就已經對於rollout methods能夠雙陸棋能力感到訝異。在某些應用程式中，即使rollout policy完全是隨機的，rollout algorithms一樣可以有好的效能。但是改善policy的效能是取決於rollout policy的特性與Monte Carlo value estimates所生成的action的排名。直觀來看，更好的rollout policy、更準確的估測值，那那生成的policy就可能愈好(參見Gelly與Silver, 2007)。

這涉及了重要性的權衡，因為更好的rollout policies通常意味著你需要更多的時間去模擬足夠多的trajectories(軌跡)，以此獲得更好的估測值。一如decision-time planning methods，rollout alrogithms通常需要滿足嚴格的時間限制。rollout algorithm所需要的計算時間是取決於每一次的決策(decision)所必需要評估的action的數量、模擬軌跡(simulated trajectories)中去獲得有效的樣本的returns的time steps的數量、rollout policy做決策所需要的時間、以及為了獲得好的Mote Carlo action-value estimates所需要的模擬軌跡的數量。

不管是什麼樣子的rollout methods的應用，你要去平衡這些因素都是很重要的，有幾種方法可以協助你。因為Monte Carlo的試驗彼此之間是獨立的(說的是每個episode?)，所以你是可以平行在不同的處理器之間做很多次的試驗。另一個方法就是去截斷那些沒有完整的episodes的simulated trajectories(模擬軌跡)，然後再利用那些保存的evaluation function的均值來校正這些被截斷的returns。當然也有可能像Tesauro and Galperin (1997)他們說的樣，監控Monte Carlo的模擬，然後修剪掉那些這輩子不可能是最佳的actions，或是幹掉那些跟當前最佳值很接近的那些actions，因為你選擇那些actions並不會有什麼明顯的差異。

通常來說，我們並不會將rollout algorithms視為是一種學習演算法，因為這演算法並不會去長時間的記錄其values或是policies。然而，這些演算法用了一些我們在書中強調的強化學習的一些特徵。一如Monte Carlo control的實例，它們利用平均一組sample trajectories的return來做為action values的估測值，這種情況下，這個trajectories是模擬與環境的樣本模型交互的trajectories。這種方法就跟強化學習演算法一樣，利用軌跡(trajectory)的採樣來避免像DP那樣的無止盡的描過整個空間，然後也利用sample updates而不是expected updates來避免對分佈模型(distribution models)的需求。最後，rollout algorithms會對action values的估測值greedy來選擇action，這有效的利用policy improvement的特性。
## 8.11 Monte Carlo Tree Search
Monte Carlo Tree Search (MCTS)是近期decision-time planning非常成功的一個案例。MCTS是上面說的那種rollout algorithms，只不過會利用一種手法來加強，我們會累積從Monte Carlo模擬中所獲得的估測值，然後依序地(successively)將整個模擬過程導向有更高報酬的軌跡(highly-rewarding trajectories)。MCTS主要負責將電腦圍棋從2005年的小學生水平拉到2015年的grandmaster(擁有最高棋段) level。已經有很多不同的基礎演算法已經被開發出來，包含Section 16.6會談到的部份，這對2016年的AlphaGo來說是非常、非常、非常重要的。MCTS已經被證明在各種競爭環境中都是有效的，像是遊戲，如果有一個環境模型簡單到可以快速的多步模擬(multistep simulation)，那就可以有效的解決single-agent sequential decision(單一代理序列決策?)的問題。

MCTS會在每次遇到一個新的state之後執行，為這個state決定agent要選擇的action；然後再次的執行，為下一個state選擇action，以此類推。就像是rollout algorithm，每次的執行都是一個迭代遇程，模擬很多從當下的狀態(current state)一直到終止狀態(terminal state)的軌跡(trajectories)，或者是一直到discount之後你可以忽略這個reward的軌跡。MCTS的核心思想就是依序地關注多個從當前的狀態(current state)開始的模擬軌跡(利用擴展那些在初期模擬過程中收到很高評價的軌跡的初始部份)。MCTS並不會去保留從一個action到選擇到下一個action的approximate value functions或policies，儘管在很實作中它會保留對它下次的執行而言是有用的那個選擇過的action value。

多數情況下，在模擬軌跡中的actions會是用一個簡單的policy來生成，通常稱為rollout policy。當rollout policy與model都不需要大量計算的時候，那就可以在很短的時間內生成很多的模擬軌跡。跟很多的tabular Monte Carlo methods一樣，它的state-action pair的value就是用這個pair在模擬軌跡中的returns的平均值來做為它的估測值。Monte Carlo value estimates只會針對那些最有可能在幾個步驟就到達的state-action pairs的subset來做維護，那就會形成一個以當前狀態(current state)為root的tree，如Figure 8.10所示。


Figure 8.10: Monte Carlo Tree Search. When the environment changes to a new state, MCTS executes as many iterations as possible before an action needs to be selected, incrementally building a tree whose root node represents the current state. Each iteration consists of the four operations Selection, Expansion (though possibly skipped on some iterations), Simulation, and Backup, as explained in the text and illustrated by the bold arrows in the trees. Adapted from Chaslot, Bakkes, Szita, and Spronck (2008).

MCTS會透過增加那些在模擬軌跡的結果中看起來還不錯的節點來表示states的方式逐漸的擴展這個tree。任一個模擬軌跡(simulated trajectory)都會通過tree，然後在某一個葉節點(leaf node)離開。在tree的外邊跟葉節點處，rollout policy用來做action的選擇，但是在tree內部的states的話，可能會有更好的選擇。對於這些states，我們至少有某些actions的估測值，因此，我們可以用informed policy在它們之間選擇，這稱為tree policy，這種policy可以平衡探索(exploration )與開發(exploitation)。舉例來說，tree policy可以用$\epsilon-$greedy或是UCB selection rule來選擇actions。

更多的細節，MCTS每次的迭代都包含Figure 8.10所說的四步驟：
1. Selection. 起始於root node(根節點)，基於附加到tree的邊緣(edge)的action values的tree policy，穿越(traverses)tree以選擇葉節點(leaf node)
2. Expansion. 在某些迭代中(取決於對用程式的細節)，會利用加入一個或多個子節點(child nodes)，這節點是由未經探索的actions從選定的節點所到達，然後從選定的葉節點來展開tree
3. Siumlation. 從選定的節點(node)，或從其新加入的子節點(child nodes)中的其中一個(如果有)，然後利用rollout policy所選定的actions模擬一個完整的episode。其結果就是一個Monte Carlo trial，首先利用tree policy來選定actions，然後利用rollout policy來選擇tree以外的actions
4. Backup. 利用simulated episode所生成的return去回推(backed up)更新，或利用MCTS在這次的迭代中的tree policy來初始化那些附加到tree的edges的action values。不會保存任何tree之外，rollout policy看過的那些states、actions的value。Figure 8.10利用backup從模擬軌跡的terminal state直接到tree那些由rollout policy開始的的state-action node來說明這一點(儘管通常來說，整個模擬軌跡的return都會反推(backed up)到該state-action node)

MCTS持續的執行著這四個步驟，每次都從tree的root node(根節點)，一直到沒有更多時間，或是其它計算資源耗盡為止。最終，根據某種取決於tree中的累積統計信息的機制來從root node選擇一個action(仍然表示為環境的當前狀態(current state))；舉例來說，它可能是root state所有可以用的actions中value最大的那一個，或是可能被看過的次數最多的那一個，這可以避免選擇到異常值。這就是MCST實際選擇的action。在環境轉移至新的state之後，MCST會再次的執行，有時候會從表示新的狀態(state)的單個根節點(single root node)的tree開始，不過通常會從包含該節點的任意子節點的tree開始，這個子節點會是由先前執行MCST在構建tree的時候所留下的；剩下的節點跟與其相關的action values都將被丟棄。

MCTS最初被提出來是用在像是圍棋的那種兩人遊戲，你一步我一步的這樣。那於遊戲來說，每一次的simulated episode就是你完整的玩過一輪，兩個玩家都是利用tree與rollout policies來選擇actions。Section 16.6就會提到關於MCTS的一種擴展應用，也就是AlphaGo，它結合MCTS的Monte Carlo evaluations以及利用深度人工神經網路通過自我對奕強化學習來學習action values。

把MCTS跟我們在這本書中所談過的強化學習原則關聯起來讓我們驚豔竟然可以得到這麼棒棒的結果。本質上來說，MCST是一種基於Monte Carlo control的decision-time planning algorithm，可以用在那些從root state開始的模擬狀況；也就是，它也是上一節所提到的rollout alogirthm的一種。它也受益於在線(on-line)、增量(incremental)、sample-based value estimation與policy improvement。除此之外，它還保存附加到tree edges的action-values的估測值，並且用sample updates的方式來做更新。這有助於讓Monte Carlo trials關注在某些特定的trajectories，這些trajectories的initial segments([初始段](http://terms.naer.edu.tw/detail/2117931/))跟先前所模擬的軌跡中具有較高return的initial segments是相同的。此外，透過逐步的擴展tree，MCTS會有效的增長一個lookup table([查找表](http://terms.naer.edu.tw/detail/13818585/))來保存部份的action-value function，然後，記憶體會分配給高收益(high-yielding)的sample trajecoties的初始段中看過的那些state-action pairs的估測值。就這樣，MCTS避免掉globally approximating(全域收斂?)action-value function，同時還保留使用過去經驗去指導探索的這個好處。

## 8.12 Summary of the Chapter
Planning需要一個描述環境的模型(model)。一個distribution model由下一個state的機率與可能的actions的rewards所組成；sample model會根據這些機率產生單一個狀態的轉移與rewards。動態規劃需要一個distribution model(分散模型?分佈模式?)，因為它用expected updates，這涉及計算所有可能的下一個states與rewards的期望值。另一方面，sample model是模擬與環境互動所需要的，過程中我們會做sample updates，就像是很多強化學習演算法使的那些updates。sample model通常比distribution models更容易獲得。

我們提出一個觀點，強調planning optimal behavior與learning optimal behavior之間的密切關係。兩者都涉及估測相同的value functions，而且都很自然地在一系列漫長backing-up(反推)的計算中逐步的更新這些估測值。這讓我們可以讓兩者透過更新所估測的value function來整合learning與planning。此外，任何的learning methods都可以透過模擬經驗(simulated experience)來轉為planning methods(非採用實際經驗，real experience)。這種情況下，learning與planning就會變的更加相似；它們是有可能在兩個不同經驗來源上執行相同的演算法。

整合incremental planning methods、acting、model learning是非常簡單的。這三個之間的循環如下圖所示：

三者各自產生對方改進自己所需要的東西；你並不需要去特別的禁止它們之間的其它互動。最自然的方式就是讓所有的processes通通非同步而且平行的進行。如果processes必需分享計算資源，你幾乎可以隨便亂劃分，反正就你爽或是讓正在執行的任務效率最高，都可以。

這一章裡面，我們已經觸及state-space planning methods之間不同的多個維度。一個是updates(更新)大小的變化。較小的更新(updates)，planning methods的增量幅度就愈大。其中最小的更新(updates)就是one-step sample updates，也就是Dyna。另一個重要的維度(dimension)就是更新(updates)的分配(distribution)，也就是搜尋的焦點。優先掃過那些最近values有變化的狀態的[前元素](http://terms.naer.edu.tw/detail/2122152/)(predecessors)。on-policy trajectory sampling就會關注在那些agent在控制其環境時候可能會遇到的states或state-action pairs。這讓我們可以跳過一些跟預測或控制問題無關的狀態空間(state space)的部份。realtime dynamic programming，一種on-policy trajectory sampling的value iteration，這說明了相對於傳統的sweep-based policy iteration，本身所存在的一些優勢。

planning也可以從相關狀態向前關注(focus forward)，像是在agent-environment互動過程中確實遇到的states。最重要的形式就是在決策時的規劃，也就是做為action-selection過程的一部份。人工智慧研究中，經典的heuristic search就是一個例子。其它的範例就像是rollout algorithms、Monte Carlo Tree Search也是得益於線上(online)、增益(incremental)、sample-based value estimation與policy improvement。

## 8.13 Summary of Part I: Dimensions
這章總結了這本書的第一部份。這邊我們試著不將強化學習以各別方法來呈現，而是一種跨越各種不同方法相呼應的呈現。每個想法都可以視為是方法變化的一個維度。這樣的維度集合跨越所有的可能方法。我們在維度層面探索這個空間，我們希望得到最廣泛、最深刻的瞭解。所以我們就用方法空間(method space)中的維度概念來概括這本書中的強化學習觀點。

目前為止我們所探討的方法有三個共同的關鍵思想：
1. 它們都在尋求estimate value function(估測價值函數)
2. 它們都利用沿著實際或可能的狀態軌跡(state trajectories)來反推(backing up)values
3. 它們都依循generalized policy iteration(GPI)的生成策略，這意味著它們會維護一個近似價值函數(approximate value function)與近似策略(approximate policy)，並在彼此的基礎上嚐試改善

這三個想法也是本書所涵蓋的主題的核心。我們說明了value functions、backing up value updates、與GPI都是非常強而有力的組織原則。可能跟任何的模型都有關，管他是人工還是自然的。

不同方法之間的兩個最重要的維度如Figure 8.11所示：

Figure 8.11: A slice through the space of reinforcement learning methods, highlighting the two of the most important dimensions explored in Part I of this book: the depth and width of the updates.

這些維度跟那些用於改進value function的更新類型是有關的。橫軸(horizontal dimension)說明的是，方法是屬於sample updates(based on a sample trajectory)還是expected updates(based on a distribution of possible trajectories)。expected updates需要一個distribution model，而sample updates只要一個sample model，或是從一個根本沒有model的實際經驗中完成(另一個變異的維度)。縱軸(vertical dimension)的話就是更新的深度，也就是自舉(bootstrapping)的程度(degree)。空間中四個角落的其中三個是估測值的三個主要方法：DP、TP、MC。沿著空間的左邊是sample-update methods，範圍是one-step TD一路到full-return Monte Carlo updates。兩個範圍之間包含$n-$step updates，在Chapter 12我們會把它擴展為混合的$n-$steps updates，像是利用eligibility traces所實作的$\lambda-$updates。

DP在空間中的右上角，因為DP是one-step expected updates。右下角則是expected updates的極端情況，這方法會把所有可能到terminal states的通通執行過(或者在continuing task中，一直到discounting之後的rewards可以忽略不計)。這就是一種[竭盡式搜尋](http://terms.naer.edu.tw/detail/13791447/)(exhaustive search)。沿著這個維度的中間就會有heuristic search與related methods，這些方法會在有限的深度或是選擇性的搜尋、更新。當然橫軸的中間還是有一些方法的。包含混合expected、sample updates的方法，以及在single update中混合samples與distributions的方法的可能性。圖上的那個正方形被填滿就代表有著這些方法。

這本書中我們強調的三個維度就是on-policy與off-policy兩個方法之間的[二元區分法](http://terms.naer.edu.tw/detail/3256566/)。on-policy的話，agent是從當前所依循的policy身上學習value function，而off-policy則是從不同的policy學習，那個不同的policy通常是agent當下認為最好的那一個。因為需要探索(explore)，所以policy所生成的行為通常跟當下認為最好的行為不同。在Figure 8.11中，這個第三個維度可以被視覺化為垂直頁面平面的維度。

除了剛剛聊過的三個維度之外，書中還有很多很多其它不同的維度：
* Definition of return，任務是episodic還是continuing，要discounted還是不要
* Action values vs. state values vs. afterstate values，應該估測什麼樣的值？如果是單純的估測state values，那action的選擇就需要model或是各別的策略(separate polciy)，像是actor-critic
* Action selection/exploration，actions該怎麼選擇才能確保滿足exploration與exploitation之間的權衡？最簡單的方法就是$\epsilon-$greedy、optimistic intilization of values、soft-max以及upper confidence bound
* Synchronous vs. asynchronous，所有states的更新是同時做還是依某一種順序來一個接著一個做
* Real vs. simulated，要基於實際經驗還是模擬經驗來更新？如果兩者都要，那佔比怎麼給
* Location of updates．那些states或是state-action pairs應該被更新？modelfree的方法只能選擇那些實際遇到的states或state-action pairs，但model-based就能夠任意選擇。這有很多可能性
* Timing of updates，updates應該是視為selecting actions的一部份來完成，還是只在選擇之後完成
* Memory for updates，更新之後的values應該保留多久？應該像永久乳一樣一直保存，還是只有在計算action selection的時候保留(就像在heruistic search一樣)

不少演算法是可以在不同維度的多個位置上來表示。像是Dyna就同時使用實際與模擬經驗來影響相同的value function。所以厚，這些維度構成一個無限想象的空間，去探索吧，所有的寶物就在那邊。

這邊還沒有提到的最重要的維度就是function approximation。function approximation可以被視為是一種可能性的orthogonal spectrum(正交光譜?)，不管如何，後續會繼續討論。

:::warning
恭喜我自己翻完第一部份
> [name=Shaoe.chen] [time= Sep 7, 2021] [color=#907bf7]
:::