# Reinforcement Learning: An Introduction_Chapter 9 On-policy Prediction with Approximation
###### tags: `Reinforcement Learning` `Second Edition`

課本範圍：197~236

[相關連結_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)

這一章我們要開始來研究強化學習的[函數逼近](http://terms.naer.edu.tw/detail/2123125/)(function approximation)，我們思著將它用在從on-policy data中估測state-value function，也就是，用從已知的policy所生成的經驗來逼近state-value function $v_\pi$。這一章的特別之處在於，approximate value function並不是用table來表示，而是用有權重向量$\mathbf{w}\in\mathbb{R}^d$的參數化函數形式來表示。我們會把$\hat{v}(s, \mathbf{w}) \approx v_\pi(s)$表示為給定權重向量$\mathbf{w}$，state $s$的近似值(approximate value)。舉例來說，$\hat{v}$就可能是state的features內的一個linear function，而這個feature則有著feature weights，也就是$\mathbf{w}$。講白話一點的，$\hat{v}$也許就是一個multi-layer的神經網路，每個layer都有權重向量$\mathbf{w}$相互連接。透過調整權重(weights)，你的神經網路可以實現各種不同的函數(function)。又或者$\hat{v}$也可以是由決策樹(decision tree)計算而得的函數，其中$\mathbf{w}$就會是你定義tree的split points、leaf values的數值。通常來說，權重的數量($\mathbf{w}$的維度)會遠比states的數量還要來的小($\mathcal{d} \ll \vert \mathcal{S} \vert$)，而且你更新一個權重就就代表更新很多states的估測值(estimated value)。因此，當有一個state更新，就代表很多states也會跟著更新(這已經是神經網路的觀念)。這樣子的泛化效果讓學習可能更加的強大，但也更難理解(神經網路的黑盒子)。

讓人訝異的是，把強化學習擴展至函數逼近(function approximation)也讓它同時適用於那些部份可觀測的問題，也就是agent無法得到完整state的問題。如果$\hat{v}$的參數化函數形式無法由state的某些方面來決定其估測值，這個某些方面就像是上面說的不可觀察的部份。事實上，這本書的這一部(第二部)所用的函數逼近的方法的所有理論結果都適用於部份可觀測(partial observability)的情況。這樣子的話，有什麼是函數逼近無法做的?函數逼近無法做到利用過去觀測到的記憶來增強狀態的表示(state representation)。這後面Section 17.3會再提到。

## 9.1 Value-function Approximation
這本書所涵蓋的所有預測方法都被描述成是對所估測的價值函數(value function)的更新(updates)，也就是在特定的state將其value移向(shift)一個"backed-up value"(反推值)，或是該state的 更新目標(update target)。讓我們用$s \mapsto u$來表示一個各別的更新，其中$s$就是被更新的state，而$u$則是更新的目標，也就是state $s$的估測值所要移至的更新目標。舉例來說，value prediction的Monte Carlo的更新就可以寫成$S_t \mapsto G_t$，TD(0)的更新則是$S_t \mapsto R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t)$，$n-$step TD的更新為$S_t \mapsto G_{t:t+n}$。在DP中的policy evaluation updates(策略評估更新)為，$s \mapsto \mathbb{E}_\pi[R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t) \vert S_t=s]$，DP中任意一個state $s$都會被更新，而其它的情況則是只會在真的遇到的才會更新。

我們可以很自然的把每次的更新(update)都解釋為value function期望的輸入-輸出(input-output)行為的範本。某種意義來說，$s \mapsto u$這個更新意味著state $s$的估測值應該要能夠更接近更新的目標$u$。到目前為止，實際的更新(actual update)是簡單的：state $s$的估測值的table entry僅是一小部份移向$u$，而其它states的估測值則是維持不變。現在我們可以用任意複雜且先進方法來實作這個更新(update)，而且，在$s$的更新可以泛化到讓其它states的估測值也一起改變。這種學習模仿input-output樣本(example)的機器學習方法稱為監督式學習方法，當輸出是數值的時候，像是$u$，那這個過程通常就稱為函數逼近(function approximation)。function approximation會期望去接收到它們試著去逼近(approximate)的那個function所需要的input-output的樣本。我們用這些方法來做value prediction，反正就是把每次更新丟進去的資料$s \mapsto u$做為訓練樣本。然後我們再把它們所產生的近似函數(approximate function)稱為估測價值函數(estimated value function)。

用這種方式將每次的更新視為傳統的訓練樣本，這讓我們可以用任意一個現有的function approximation的方法來做value prediction。原則上，我們可以使用任何的方法來從樣本中做監督式學習，包含人工神經網路、決策樹、以及各種[多變量迴歸](http://terms.naer.edu.tw/detail/3651215/)。然而，並不是所有的function approximation都同樣適用於強化學習。最先進的人工神經網路與統計分析方法都假設你有一個靜態的訓練資料集，然後你多次的用這個資料集來訓練。然而，在強化學習中很重要的一點就是說，學習必需是要線上(online)的，同時agent會與其環境或是其環境模型互動。要做到這一點就需要那種可以從增量獲取的資料中有效學習的方法。此外，強化學習通常需要能夠處理非平穩(nonstationary)目標函數(target function)的函數逼近方法(function approximation methods)。舉例來說，在基於GPI的控制方法(control methods)中，我們通常找的是在$\pi$改變的同時學習$q_\pi$。即使policy是維持不變的，只要資料的生成是由[自助抽樣法](https://zh.wikipedia.org/wiki/%E8%87%AA%E5%8A%A9%E6%B3%95)所生成，那它們就是不平穩的。無法處理這種非平穩狀況的方法是不適用於強化學習的。

:::warning
這小節強調的就是，你可以用機器學習方法來做value evaluation，也就是預測問題，當然也要注意使用的方法是否適用於非平穩性(nonstationarity)的狀況。
:::
## 9.2 The Prediction Objective ($\overline{\mathrm{VE}}$)
目前為止我們都還沒有明確的確定一個預測目標。在表格(tabular)的情況中，我們並不需要去對預測品質做連續的量測，因為學習到的value function能夠精確地等於真正的value function。此外，每個state學習到的values都是[解耦](http://terms.naer.edu.tw/detail/2114307/)的(decoupled)，也就是每個state的更新並不會去影響其它的state。但是對於真正的近似(approximation)來說，一個state的更新會影響很多的states，而且你根本不可能得到所有states完全正確的values。根據假設，我們所擁有的權重數(weights)遠少於狀態數states，因此，讓一個state的估測值更準確就意味著會讓其它的states的估測值更不準確。所以，我們有義務說明我們最關心的是那些states。我們必需指定一個state distribution $\mu(s) \geq 0, \sum_s\mu(s)=1$，用這個來表示我們對每個state $s$的誤差的關心程度。而state $s$的誤差則表示近似值(approximate value) $\hat{v}(s, \mathbf{w})$與實際值$v_\pi(s)$之間的平方。利用$\mu$在state space上做加權，我們就得到一個很自然的目標函數，也就是均方誤差(mean square value error)，我們以$\overline{\mathrm{VE}}$來表示：
$$\overline{\mathrm{VE}}(\mathbf{w}) \dot{=}\sum_{s\in\mathcal{S}}\mu(s)\left[v_\pi(s) - \hat{v}(s, \mathbf{w}) \right]^2 \tag{9.1}$$

:::warning
公式9.1說明的很簡單，就是給定一個權重$\mathbf{w}$，用這組權重來計算花費在每一個state $s$的時間去乘上該state的預估值與實際值之間誤差的平方。
:::

上面這量測值的平方根，也就是$\overline{\mathrm{VE}}$，它給出一個近似值與實際值之間概略的差異，圖表上常常拿來使用。通用我們會選擇$\mu(s)$來做為花費在state $s$的時間的[一部份](http://terms.naer.edu.tw/detail/2116426/)。在on-policy訓練下，這稱為on-policy distribution；這一章我們就完全的關注這件。在連續任務中(continuing tasks)，on-policy distribution會是穩定的分佈(under $\pi$)。

如果是episodic tasks的on-policy distribution會有些許的不同，它取決於那些被選擇到的episodes的初始狀態(initial states)。假設$h(s)$是一個episode起始於每個state $s$的機率，然後$\eta(s)$則表示在單一個episode中的state $s$所花費的time steps的時間(平均計算)。這個state $s$花費的時間就是說，如果episodes起始於$s$，又或者從前一個state $\bar{s}$轉移至$s$，那對於所有的$s \in \mathcal{S}$：
$$\eta(s) = h(s) + \sum_{\bar{s}}\eta(\bar{s})\sum_a\pi(a\vert \bar{s})p(s\vert \bar{s}, a)\tag{9.2}$$

:::warning
把自己會做為初始狀態的機率$h(s)$加上下一個state會是state $s$的期望值，所以上面把所有可能進入state $s$的$\bar{s}$都拿出來計算
:::

這個方程組可以解期望看過(visits)的次數$\eta(s)$。然後，on-policy distribution就會是每一個state所花費時間的部份，正規化為總和為1，對所有的$s \in\mathcal{S}$：
$$\mu(s) = \dfrac{\eta(s)}{\sum_{s'}\eta(s')} \tag{9.3}$$

:::warning
上面翻譯不是很有信心翻正確，提供原文如下：
The on-policy distribution is then the fraction of time spent in each state normalized to sum to one:

不過對於公式9.3目前沒有一個比較直觀的感覺，只能先接受它。
:::

這就是沒有discounting下很自然的選擇。如果有存在discounting，$\gamma < 1$，那就應該將其視為一種終止的形式，這只需要在公式9.2的第二項加入一個因子(factor)即可。

這兩種情況，也就是continuing與episodic，行為相似，但如果是近似值的話，在形式分析中就必需要分開來處理，正如我們在這本書中的這一部份反覆看到的那樣。這樣子就完成學習目標(learning objective)的指定。

現在我們還不是那麼確定$\overline{\mathrm{VE}}$對於強化學習來說是不是就是那個[效能目標](http://terms.naer.edu.tw/detail/3815455/)。要記得嘿，我們的終極目標，也就是我們學習value function的原因，就是為了找出一個更好的policy。而且這一個終極目標下的最好的那個value function也不見得就是最小化$\overline{\mathrm{VE}}$的那個最好的value function。雖然如此，我們也還不知道有什麼可以比value prediction更好用的。所以我們會先專注在$\overline{\mathrm{VE}}$。

就$\overline{\mathrm{VE}}$來說，它的目標就是希望可以找出global optimum([全域最佳解](http://terms.naer.edu.tw/detail/152502/))，也就是一個權重向量(weight vector)$\mathbf{w}^*$，對所有可能的$\mathbf{w}$，其$\overline{\mathrm{VE}}(\mathbf{w}^*) \leq \overline{\mathrm{VE}}(\mathbf{w})$。有時候簡單的函數逼近器(function approximator)反而可以實現這個目標(像是線性函數逼近器(linear function approximator))，複雜一點的反而不行(像是人工神經網路與決策樹)。除此之外，複雜的函數逼近器也許會收斂到local optimum([局部最佳解](http://terms.naer.edu.tw/detail/151846/))，這時候的權重向量(weight vector)$\mathbf{w}^*$就變成是對於$\mathbf{w}^*$鄰域的所有$\mathbf{w}$，其$\overline{\mathrm{VE}}(\mathbf{w}^*) \leq \overline{\mathrm{VE}}(\mathbf{w})$。雖然這樣的保證只帶給我們一咪咪的信心，不過這對非線性的函數逼近器(nonlinear function approximators)來說已經足夠了。儘管如此，這對於強化學習中感興趣的很多情況來說都是無法保證收斂到最佳(optimum)，甚至無法保證收斂到最佳解的[有限距離](http://terms.naer.edu.tw/detail/690752/)內。事實上，有些方法可能會發散，造成$\overline{\mathrm{VE}}$會趨近無限。

最後兩節中，我們會概述一個框架，結合多種強化學習用於value prediction的方法與多種函數逼近(function approximation)的方法，取前者的updates來生成後者的訓練樣本(training example)。我們還會說明$\overline{\mathrm{VE}}$的效能度量，這些方法也許有機會可以最佳化$\overline{\mathrm{VE}}$。所有可能的function approximation methods太多了，所以我們只會考慮幾種可能性。所以剩餘的部份我們會關注在基於梯度原則的函數逼近方法，尤其是linear gradient-descent methods(線性梯度下降)。
## 9.3 Stochastic-gradient and Semi-gradient Methods
我們現在來詳細聊聊用於value prediction的function approximation的學習方法，這些方法基於隨機梯度下降，也就是stochastic gradient descent，SGD。SGD是所有function approximation中用最多的方法之一，特別適合online的強化學習。

在gradient-descent(梯度下降)方法中，權重向量是一個行向量(column vector)，它有固定數量的[實值](http://terms.naer.edu.tw/detail/3190431/)分量(real valued components)，$\mathbf{w}\dot{=}(w_1, w_2, \cdots, w_d)^T$，而且approximate value function(近似價值函數)$\hat{v}(s, \mathbf{w})$對$\mathbf{w}$是可微分的($\forall s \in \mathcal{S}$)。我們會在一系列的離散時步(discrete time steps)，$t=0,1,2,3,4,...$，更新$\mathbf{w}$，因此我們會需要一個符號$\mathbf{w}_t$來表示每個step的權重向量(weight vector)。現在，讓我們來假設一件事，在每一個step上，我們觀測到一個新的樣本(example)$S_t \mapsto v_\pi(S_t)$包含一個state $S_t$(這可能是隨機選擇的)，以及這個state按著policy所擁有的true value。這些states也許是與環境互動所產生的連續的states，不過我們現在不這麼假設。即使我們已經得到每個$S_t$準確的$v_\pi(S_t)$，這仍然是一個困難的問題，因為我們的function approximator的資料有限，因此你得到的精確度仍然是有限的。特別是，通常不會有$\mathbf{w}$可以完全正確的計算所有的states，更別說所有的樣本(examples)。此外，我們還需要泛外到那些從來沒有出現在樣本(examples)中的其它states。

我們假設出現在樣本中的那些states有相同的分佈，$\mu$，我們試著最小化公式9.1給出的$\overline{\mathrm{VE}}$。這種情況下有一個很好的策略，我們可以試著去最小化觀測到的樣本的誤差(error)。Stochastic gradient-descent (SGD)透過調整權重向量可以達到這個目的：
$$
\begin{align}
\mathbf{w}_{t+1} & \dot{=} \mathbf{w}_t - \dfrac{1}{2} \alpha \nabla [v_\pi(S_t) - \hat{v}(S_t, \mathbf{w}_t)]^2 \tag{9.4} \\
&= \mathbf{w}_t + \alpha[v_\pi(S_t) - \hat{v}(S_t, \mathbf{w}_t)]\nabla \hat{v}(S_t, \mathbf{w}_t) \tag{9.5}
\end{align}
$$

其中$\alpha$是一個positive step-size parameter(正數的步長參數)，而$\nabla f(\mathbf{w})$，對任意的[純量表示式](http://terms.naer.edu.tw/detail/13854612/) $f(\mathbf{w})$，它就是一個向量(這邊指的向量就是$\mathbf{w}$)的函數，求的行向量(column vector)對每一個向量分量(components)的偏導數(原文放在下方)
:::warning
denotes the column vector of partial derivatives of the expression with respect to the components of the vector.

另外，其實9.4、9.5兩個公式做的就是求導的一個部份，這是微積分的基礎，chain-rule，指數先下來，然後中間不動指數減一，最後再對中間的部份求導，所以指數下來，就是2拿下來，然後中間不動指數減一，所以2就變成1，再對中間求導，中間是對$\mathbf{w}$求導，所以不相關的項目就消掉，留下與權重$\mathbf{w}$相關的求導項目。
:::

$$
\nabla f(\mathbf{w}) \dot{=} \left(\dfrac{\partial f(\mathbf{w})}{\partial w_1}, \dfrac{\partial f(\mathbf{w})}{\partial w_2}, \cdots, \dfrac{\partial f(\mathbf{w})}{\partial w_d} \right)^T \tag{9.6}
$$

這個導數向量(derivative vector)就是求$f$相對於$\mathbf{w}$的梯度。SGD是一種梯度下降(gradient descent)方法，因為在$\mathbf{w}_t$中的整體步長(step)都是跟公式9.4所指的樣本平方誤差的負梯度(negative gradient)成比例。而這也是誤差下降最快的方向。會稱做隨機梯度下降(SGD)，是因為只對一個樣本做更新，而這個樣本也許是隨機選擇的。然後在很多的樣本中，採取很小的步長(small step)，總的來說，效果就是最小化一個平均效能度量，像是$\overline{\mathrm{VE}}$。

為什麼SGD就只會朝著梯度的方向走那麼一小步，這影響不是就很小嗎。我們難道不能就這樣往同一個方向直直走，然後就完全消除所有樣本的誤差?母湯喔!記得，我們並不期望能夠找到一個所有的states的樣本誤差皆為0的value function，找的只是一個在不同states之中能夠取得平衡的一個近似值。如果我們在每個step中都把樣本誤差弄到完美，那絕對找不到這樣的一個平衡，因為好了這個樣本，下一個step再調整，剛剛好的又歪了。事實上，對於SGD的收斂，我們是假設$\alpha$會隨著時間減少(學習效率的衰減，參數名稱一般是`decay`?)。如果$\alpha$的減少滿足公式2.7的標準隨機近似條件，那就可以保證公式9.5可以收斂到局部最佳(local optimum)

:::warning
$$\sum_{n=1}^\infty \alpha_n(a) = \infty \text{ and } \sum_{n=1}^\infty \alpha^2_n(a) < \infty \tag{2.7}$$
:::

我們現在來看一個情況，target output，也就是$U_t \in \mathbb{R}$，那個$t$指的就是第$t$個樣本，$S_t \mapsto U_t$，這邊估測出來的並不是實際值(true value)$v_\pi(S_t)$，而是一個隨機近似值。舉例來說，$U_t$也許是一個帶有噪點(noise-corrupted)的$v_\pi(S_t)$，又或者是如前一章所提到的，使用$\hat{v}$的bootstrapping targets(自舉的目標)。這些情況下，我們無法很精確的用公式9.5來更新，因為$v_\pi(S_t)$是未知的，但是我們可以用$U_t$取代$v_\pi(S_t)$來近似它。這就產生出一個用於state-value prediction的general SGD method：
$$
\mathbf{w}_{t+1} \dot{=} \mathbf{w}_t + \alpha \left[ U_t - \hat{v}(S_t, \mathbf{w}_t)\right] \nabla \hat{v}(S_t, \mathbf{w}_t) \tag{9.7}
$$

如果$U_t$是一個無偏(unbiased)估測值，也就是說，對每一個$t$，$\mathbb{E}[U_t \vert S_{t}=s] = v_\pi(s)$，那$\mathbf{w}_t$就能夠在$\alpha$隨時間減少且滿足隨機近似條件(公式2.7)的情況下，保證收斂到局部最佳(local optimum)。

舉例來說，假設樣本(example)中的states是用policy $\pi$在跟環境的互動過程中(或模擬過程)所生成的。因為state的實際值(true value)是在它之後的return的期望值，所以，Monte Carlo的目標式，$U_t \dot{=} G_t$，根據定義就是$v_\pi(S_t)$的[無偏估計](http://terms.naer.edu.tw/detail/955920/)(unbiased estimate)。有了這個選擇，我們就可以說，general SGD method(9.7)可以收斂到$v_\pi(S_t)$的局部最佳近似解(locally optimal approximation)。也因此，Monte Carlo state-value predction的梯度下降版本就可以保證可以找出一個局部最佳解。下面給出完整演算法的pseudocode：

不過要注意一下，如果你拿$v_\pi(S_t)$的bootstrapping estimate來做為公式9.7的target $U_t$的話，那就無法得到如上相同的保證。boostrapping targets，像是$n-$step returns $G_{t: t+n}$或是DP target $\sum_{a, s', r}\pi(a\vert S_t)p(s',r \vert S_t, a)[r + \gamma \hat{v}(s', \mathbf{w}_t)]$，這都是取決於權重向量$\mathbf{w}_t$的當前值(current value)，這意味著它們都會是有偏的(biased)，而且都不會產生一個真正的梯度下降方法。這意思就是說，從公式9.4到9.5的關鍵步驟所依賴的目標(target)是跟$\mathbf{w}_t$無關的。如果你用bootstrapping estimate來取代$v_\pi(S_t)$，那這個步驟就是無效的。實際上bootstrapping methods並不是一個真正的梯度下降的實例(Barnard, 1993)。bootstrapping methods雖然考慮了改變權重向量$\mathbf{w}_t$對估測值的影響，但是卻忽略對目標(target)的影響。也因為bootstrapping methods只包含一部份的梯度，因此我們就把它們稱為semi-gradient methods。

:::warning
DP與$n-$step TD的目標值(target)都是部份取決於權重$\mathbf{w}$，DP只看這個state的reward與下個state的估值，而$n-$step TD則是截斷式的估值，這兩個估值都是取決於權重$\mathbf{w}$。因此，它們的target並非完全的來自於與環境的互動，所以是有偏的。
:::

雖然semi-gradient(bootstrapping)的收斂不像gradient methods那麼樣的魯棒性，不過在一些重要情況下還是可以確實收斂的，像是後面要說的線性情況。此外，這方法有幾個優點讓它通常是我們實作的首選。原因之一就是它們通常可以很快的學習，如Chapter 6、7中所述，這邊不再說明。另外就是，它們能夠持續(continual)而且線上(online)的學習，不需要等episode結束才能學習。這一點讓它們能夠被用於連續型的問題，而且有著計算優勢。一個典型的semi-gradient method就是semi-gradient TD(0)，這方法以$U_t\dot{=}R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})$做為target。見下面pseudocode：

State aggregation(狀態聚合?)是一種廣義函數近似(function approximation)的簡單形式，其中states是分組聚在一起，每個群組都有一個估測值(對應權重向量$\mathbf{w}$的一個分量)。state的value會被估測來做為其群組的分量(component)，當state更新，相對應的那個分量就單獨的更新。State aggregation是SGD(9.7)的一個特例，其梯度$\nabla\hat{v}(S_t,\mathbf{w}_t)$對於$S_t$所在群組的分量為1，對其它的分量則為0。

:::warning
如果是state of aggregation就是[聚集狀態](http://terms.naer.edu.tw/detail/182803/)，但這邊是state aggregation就不硬翻了。
:::

:::info
Example 9.1: State Aggregation on the 1000-state Random Walk

我們來想一個1000-state版本的random walk task(就是Example 6.2、7.1)。states的編號從1到1000，從左到右，所有的episodes都是從中間開始，也就是編號500。然後，狀態的轉移(state transitions)範圍會是左右100個相鄰的狀態之一，大家的機率是一致的。當然啦，如果你是在邊邊的話那向左或是向右也許就沒有100個狀態可以選。這種情況下，原本應該平均的機率就會通通補到最邊邊那個，舉例來說，當你在state 1的時候就會有50%的機率進入terminal state，因為左邊50%、右邊50%，但是左邊已經沒有state給你了，就全部通通給terminal state，相同的概念，如果是state 950的話就會有25%的機率會終止。一如往常，左邊終止的話reward就-1，右邊終止的話reward就+1，其它的轉移的reward皆為0。

Figure 9.1說明這個任務的true value function $v_\pi$。

Figure 9.1： Function approximation by state aggregation on the 1000-state random walk task, using the gradient Monte Carlo algorithm (page 202).

很明顯的，true value function幾乎是一條直線，只有在兩個端點稍微的彎了一下。而且你還可以看到利用gradient Monte-Carlo algorithm with state aggregation在100,000個episodes(step size $\alpha = 2 x 10^{-5}$)之後學到的final approximate value function。對於state aggregation，這1000個states會分割為10組，每組100個states，也就是1~100、101~200、…以此類推。圖上的[階梯效應](http://terms.naer.edu.tw/detail/976997/)就是典型的state aggregation；在每個群組中，其近似值都是不變的，而且會在跳到下一組的時候突然的變化。這些近似值(approximate values)非常接近公式9.1中$\overline{\mathrm{VE}}$的全域最小值。

要觀察這個近似值細節最好的方法就是參考這個任務的狀態分佈(state distribution)$\mu$，這可以從Figure 9.1的下部右側看的出來。中間state 500是每個episode的第一個state，但它很少會再被看過。平均來看，大概會有1.37%的time steps是花在起始狀態(start state)。從start state一步能到的states(就是左右100個state內)是第二個最常被遇到的state，大概有0.17%的time steps都是花在這些state身上的。從那開始，這個$\mu$就幾乎是呈現線性下降，到左右兩邊(1、1000)就大概剩下0.0147%。這個分佈最明顯的影響是在最左邊的群組，這些群組的值(values)明顯高過群組內狀態(states)true values的未加權平均值，而最右邊的群組則是明顯的較低。這是因為這些區域中的states在$\mu$權重上有最大的不對稱性。舉例來說，在最左邊的群組中，state 100的權重就是state 1的3倍以上。因此，對群組的估測值會偏向於state 100的true value，而這個值它會比state 1的true value還要來的高。
:::
## 9.4 Linear Methods
function approximation裡面最重要的一個特殊情況就是近似函數(approximate function)$\hat{v}(\cdot,\mathbf{w})$是權重向量$\mathbf{w}$的線性函數。對應每一個state $s$，存在一個real-valued vector $\mathbb{x}(s)\dot{=}(x_1(s), x_2(s), \cdots, x_d(s))^T$，有相同數量的$\mathbf{w}$。它們的approximate state-value function就是計算$\mathbf{w}, \mathbb{x}(s)$的內積：
$$\hat{v}(s,\mathbf{w})\dot{=}\mathbf{w}^T\mathbb{x}(s)\dot{=}\sum_{i=1}^dw_ix_i(s)\tag{9.8}$$

:::warning
公式9.8是一個非常標準的線性函數的作法，這在Linear regression或是Logistic regression都會看到。$x_i$指的就是該state $s$的第$i$個特徵值，所以你計算權重向量與特徵值的內積就可以得到該state $s$的估測值。
:::

這種情況下我們可以說approximate value function是linear in the weights(權重線性?)，或是簡單說它就是線性的。我們把一個特徵(feature)想成是這些函數中的一個整體(entirety)，然後它的值向量$\mathbb{x}(s)$稱為特徵向量(feature vector)，也就用這個特徵向量來表示$s$。$\mathbb{x}(s)$的每個分量(component)$x_i(s)$都是一個映射函數$x_i:\mathcal{S} \to \mathbb{R}$的值，然後對於state $s$的值就是$s$的特徵。對線性方法來說，特徵就是[基函數](http://terms.naer.edu.tw/detail/397042/)，因為它們為近似函數的集合形成了線性基礎(linear basis)。用$d$維的特徵向量來表示states跟選擇一組$d$個基函數(basis functions)是一樣的。特徵有很多不同的方法可以定義，後面我們會討論一些。

很自然的，我們可以把SGD updates跟linear function approximation結合一起用。這種情況下這個approximation value function求$\mathbf{w}$的梯度就會是：
$$\nabla \hat{v}(s,\mathbf{w}) = \mathbb{x}(s)$$

:::warning
這也是微積分中的一個基礎，左微乘右加上右微乘左，左微之後權重$\mathbf{w}$為1，剩下$x(s)$，右微之後與權重無關，直接消掉，因此得到。

可參考在下拙作『[淺入淺出機器學習](https://hackmd.io/@shaoeChen/SJovXydcP)』
:::

因此，這種線性情況下，公式9.7的general SGD update就可以減化成一個特別簡單的形式：
$$\mathbf{w}_{t+1} \dot{=} \mathbf{w}_t + \alpha[U_t - \hat{v}(S_t,\mathbf{w}_t)]\mathbb{x}(S_t)$$

也因為它就這麼簡單，所以這種linear SGD也是最受歡迎的數學分析方式之一。要知道，這麼多的學習系統，幾乎所有有效的收斂結果都是線性函數近似方法(linear function approximation methods)得來的。

特別是，線性情況下只會有一個最佳值(或是退化情況下(degenerate case)會有一些一樣好的最佳值)，因此任一個保證能夠收斂到或接近局部最佳(local optimum)的方法都自動保證收斂到或接近全域最佳(global optimum)。舉例來說，剛剛提到的gradient Monte Carlo algorithm，只要$\alpha$根據[通常條件](http://terms.naer.edu.tw/detail/3191918/)隨時間減少，那就可以在線性函數近似情況下收斂到$\overline{\mathrm{VE}}$的全域最佳。

前面提到的semi-gradient TD(0) algorithm也可以用linear function approximation來收斂，不過這並不那麼符合SGD的一般結果；這需要單獨的定理來說明。我們所收斂到的那個權重向量也不是全域最佳(global optimum)，而是接近區域最佳(local optimum)的那個點。更詳細的來思考這情況是好的，尤其是對continuing case。在每個time $t$的更新為：
$$
\begin{align}
\mathbf{w}_{t+1} & \dot{=} \mathbf{w}_t + \alpha(R_{t+1} + \gamma \mathbf{w}_t^T\mathbb{x}_{t+1}-\mathbf{w}_t^T\mathbb{x}_t)\mathbb{x}_t \\
&=\mathbf{w}_t+\alpha(R_{t+1}\mathbb{x}_t - \mathbb{x}_t(\mathbb{x}_t-\gamma\mathbb{x}_{t+1})^T\mathbf{w}_t)
\end{align} \tag{9.9}
$$

這邊我們用了一個簡寫的符號，$\mathbb{x}_t=\mathbb{x}(S_t)$。一旦系統達到穩定狀態，那對於給定的任意的$\mathbf{w}_t$，其期望的下一個權重向量就可以寫成：
$$\mathbb{E}[\mathbf{w}_{t+1}\vert \mathbf{w}_t]=\mathbf{w}_t + \alpha(\mathbb{b}-\mathbf{A}\mathbf{w}_t)\tag{9.10}$$

其中
$$\mathbb{b}\dot{=}\mathbb{E}[R_{t+1}\mathbb{x}_t]\in\mathbb{R}^d \text{ and }\mathbf{A} \dot{=}\mathbb{E}[\mathbb{x}_t(\mathbb{x}_t - \gamma\mathbb{x}_{t+1})^T]\in\mathbb{R}^{d\times d}\tag{9.11}$$

從公式9.10很明顯的可以看出，如果系統收斂，它必然收斂到權重向量$\mathbf{w}_{TD}$滿足下面：

這個值稱為TD fixed point。事實上，linear semi-gradient TD(0)就是收斂到這個點。如果你有興趣，下面給出相關證明。

:::info
Proof of Convergence of Linear TD(0)
怎麼樣的一個特性保證了linear TD(0)(9.9)的收斂性？我們可以把9.10重寫，然後得到下面公式：
$$\mathbb{E}[\mathbf{w}_{t+1} \vert \mathbf{w}_t]=(\mathbf{I} - \alpha \mathbf{A})\mathbf{w}_t + \alpha \mathbb{b} \tag{9.13}$$

注意，矩陣$\mathbf{A}$是乘上權重向量$\mathbf{w}_t$，而不是$\mathbf{b}$；只有$\mathbf{A}$對收斂這件事是重要的。為了能夠直觀一點，我們想像一下$\mathbf{A}$是一個對角矩陣(diagonal matrix)。如果對角線上的元素有負值的，那麼相對應的$\mathbf{I}-\alpha\mathbf{A}$的對角線上的元素就會大於1，而且相對應的$\mathbf{w}_t$的分量(component)就會被放大，如果一直這樣的話那就會導致發散。另一方面，如果$\mathbf{A}$的對角元素通通是正值，那我們就可以選擇裡面第二大的來做為$\alpha$，這樣，$\mathbf{I}-\alpha\mathbf{A}$的對角元素就會通通是介於0到1之間的值了。這種情況下，我們更新的第一項(first term)就會傾向於讓$\mathbf{w}_t$縮小，並保證穩定性。一般來說，如果$\mathbf{A}$是一個[正定矩陣](http://terms.naer.edu.tw/detail/150834/)那$\mathbf{w}_t$就會一直減減減減至接近0，這意謂著對於任意的[實向量](http://terms.naer.edu.tw/detail/2123200/)(real vector)，其$y^T\mathbf{A}y>0$。[正定性](http://terms.naer.edu.tw/detail/3531284/)也保證逆，也就是$\mathbf{A}^{-1}$是存在的。

對於linear TD(0)來說，在continuing case且$\gamma < 1$，9.11的這個矩陣$\mathbf{A}$就可以寫成：
$$
\begin{align}
\mathbf{A} &=\sum_s\mu(s)\sum_a\pi(a\vert s)\sum_{r,s'}p(r,s'\vert s, a)\mathbf{x}(s)(\mathbf{x}(s)-\gamma\mathbf{x}(s'))^T\\
&=\sum_s\mu(s)\sum_{s'}p(s'\vert s)\mathbf{x}(s)(\mathbf{x}(s)-\gamma\mathbf{x}(s'))^T \\
&=\sum_s\mu(s)\mathbf{x}(s)\left(\mathbf{x}(s) - \gamma\sum_{s'}p(s'\vert s)\mathbf{x}(s') \right)^T \\
&=\mathbf{X}^T\mathbf{D}(\mathbf{I}-\gamma\mathbf{P})\mathbf{X}
\end{align}
$$

上面公式幾個整理如下：
* $\mu(s)$是$\pi$下的一個[平穩分配](http://terms.naer.edu.tw/detail/2125282/)
* $p(s'\vert s)$則是用著policy $\pi$，從state $s$轉移到$s'$的機率
* $\mathbf{P}$則是這些機率的$\vert \mathcal{S} \vert \times \vert \mathcal{S} \vert$的矩陣
* $\mathbf{D}$則是$\vert \mathcal{S} \vert \times \vert \mathcal{S} \vert$的對角矩陣，對角的值就是$\mu(s)$
* $\mathcal{X}$就是$\vert \mathcal{S} \vert \times d$的矩陣，$\mathbf{x}(s)$就是它的rows

到這邊已經很清楚了，裡面那個矩陣$\mathbf{D}(\mathbf{I}-\gamma\mathbf{P})$就是$\mathbf{A}$正定性的一個關鍵。

對於這種形式的關鍵矩陣，如果這個矩陣的所有columns的總和都是非負的，那它的正定性(positive definiteness)就可以得到保證。關於這點，Sutton (1988, p. 27)已經基於前面兩個定理證明這一點。其中一個理論提到的是，任意的矩陣$\mathbf{M}$是正定矩陣，若且唯若其對稱矩陣$\mathbf{S}=\mathbf{M} + \mathbf{M}^T$是正定矩陣 (Sutton 1988, appendix)。第二個理論則是，任意的對稱實數矩陣(real matrix)$\mathbf{S}$如果它的對角線都是正值而且大於相對應的非對角線元素的絕對值總和，那這個實數矩陣就是正定矩陣(Varga 1962, p. 23)。對於我們那個跟正定很相關的關鍵矩陣，$\mathbf{D}(\mathbf{I}-\gamma\mathbf{P})$，其對角線皆為正非對角線的部份皆為負，所以我們只需要說明每個row的總和加上相對應的column總和是正的，這樣就可以。而row的總和全部都會是正的，因為$\mathbf{P}$是一個[隨機矩陣](http://terms.naer.edu.tw/detail/2125407/)，而且$\gamma < 1$。因此，我們只需要再說明column總和是非負的。我們可以注意到，任意的矩陣$\mathbf{M}$的column sum的row vector可以寫成$\mathbf{1}^T\mathbf{M}$，其中$\mathbf{1}$指的就是column vector的所有分量(component)皆為1。假設$\mathbf{\mu}$表示$\mu(s)$所組成的$\vert \mathcal{S} \vert$-vector($\vert \mathcal{S} \vert$維的向量)，因為$\mu$是一個[平穩分配](stationary distribution)，所以$\mathbf{\mu}=\mathbf{P}^T\mathbf{\mu}$。最終，我們的關鍵矩陣的column sums就是會：
$$
\begin{align}
\mathbf{1}^T\mathbf{D}(\mathbf{I}-\gamma\mathbf{P}) &= \mathbf{u}^T(\mathbf{I} - \gamma\mathbf{P}) \\
&= \mathbf{\mu}^T - \gamma \mathbf{\mu}^T\mathbf{P} \\
&= \mathbf{\mu}^T - \gamma \mathbf{\mu}^T \text{ (because $\mathbf{\mu}$ is the stationary distribution) } \\
&= (1-\gamma)\mathbf{\mu}^T
\end{align}
$$

這個矩陣的所有的分量(components)皆為正。因此，關鍵矩陣與其矩陣$\mathbf{A}$都是[正定](http://terms.naer.edu.tw/detail/150834/)，並且on-policy TD(0)是穩定的。(如果要證明機率版本的收斂性，那就要再加入一些額外的條件，然後$\alpha$要能夠隨著時間減少)
:::
在TD fixed point(TD[定點](http://terms.naer.edu.tw/detail/2116246/))的地方，也已經證明$\overline{\mathrm{VE}}$會在最低可能誤差的擴展界限(bounded expansion)內：
$$\overline{\mathrm{VE}}(\mathbf{w}_{TD}) \leq \dfrac{1}{1 - \gamma}\min_\mathbf{w} \overline{\mathrm{VE}}(\mathbf{w}) \tag{9.14}$$

也就是說，TD的[漸近誤差](http://terms.naer.edu.tw/detail/2111502/)不會超過Monte Carlo極限內能夠得到的最小可能誤差的$\dfrac{1}{1 - \gamma}$倍。因為$\gamma$通常是接近1，這個[擴大因子](http://terms.naer.edu.tw/detail/2115776/)有可能是很大的，因此，TD的漸近效能是有明顯的潛在損失的。另一方面，我們回想一下Chapter 6、7，跟Monte Carlo相比，TD的方差明顯較少，因此速度更快。所以啊，那一種方法是最好的，這取決於近似(approximation)與問題(problem)的性質，以及學習能夠持續多久。

一個類似於9.14的bound也適用於其它的on-policy bootstrapping methods。舉例來說，根據on-policy distribution來更新的linear semi-gradient DP(公式9.7的$U_t\dot{=}\sum_a\pi(a\vert S_t)\sum_{s',r}p(s', r\vert S_t, a)[r + \gamma \hat{v}(s', \mathbf{w}_t)]$)也會收斂到TD定點(TD fixed point)。One-step semi-gradient action-value methods，像是下一章要談到的semi-gradient Sarsa(0)，它會收斂到一個類似的fixed point與bound。對於episodic tasks，有一個一咪咪的不同但是卻又相關的bound(see Bertsekas and Tsitsiklis, 1996)。這邊當然我們省略了一些技術條件(rewards、features、decrease in the step-size parameter)，完整資訊可以參考原始論文(Tsitsiklis and Van Roy, 1997)。

這些收斂結果的關鍵在於states的更新是根據on-policy distribution來進行的。對於其它的update distributions，，使用function approximation的bootstrapping methods實際上可能發散到無限大。這在Chapter 11會談到相關的案例與解決方案。

:::warning
Example 9.2: Bootstrapping on the 1000-state Random Walk

State aggregation(狀態聚合)是linear function approximation的一個特例，讓我們用1000-state random walk來說說本章的一些觀點。Figure 9.2左圖說明了semi-gradient TD(0)學到的final value function(跟Example 9.1一樣的狀態聚合)。我們可以看的到，near-asymptotic TD approximation確實的比Figure 9.1所呈現的Monte Carlo approximation還要來的更遠離true values。


Figure 9.2: Bootstrapping with state aggregation on the 1000-state random walk task. Left: Asymptotic values of semi-gradient TD are worse than the asymptotic Monte Carlo values in Figure 9.1. Right: Performance of n-step methods with state-aggregation are strikingly similar to those with tabular representations (cf. Figure 7.2). These data are averages over 100 runs.

儘管如此，TD methods在learning rate上仍然保有很大的潛在優勢，正如我們在Chapter 7中那麼樣的深入研究$n-$step TD methods所發現的，它泛化(generalize)了Monte Carlo methods。Figure 9.2的右圖則說明了在1000-state random walk這個範例中用狀態聚合(state aggregatio)的$n-$step semi-gradient TD methods的結果，這明顯的跟我們之前用tabular methods解19-state random walk(Figure 7.2)的結果雷同。為了獲得數量上類似的結果，我們把狀態聚合換成20組，每50個一組。這樣，這20個群組就數量上就非常接近tabular problem的19 states。特別是，我們回想一下狀態轉移最多就是向左或是向右100個states。比較典型的轉移就是向左或是向右50個states，這樣就數量上就類似於19-state tabular system的single-state的狀態轉移。為了能夠完整的比較，我們在這裡就使用相同的效能度量，我們用所有的states與前10個episodes所計算出來的RMS error的未加權平均，其中RMS error就是指均方根誤差，root-mean-square error，而不是$\overline{\mathrm{VE}}$(雖然function approximation比較適合用這個)。
:::

上面範例用的semi-gradient $n$-step TD algorithm就是從Chapter 7中所說明的tabular $n$-step TD algorithm延伸而來。下面給出其pseudocode：

這個類似於公式7.2的演算法的關鍵方程式就是
$$\mathbf{w}_{t+n} \dot{=}\mathbf{w}_{t+n-1} + \alpha[G_{t:t+n} - \hat{v}(S_t, \mathbf{w}_{t+n-1})]\nabla\hat{v}(S_t, \mathbf{w}_{t+n-1}), 0\leq t < T \tag{9.15}$$

其中的$n$-step return是源自公式7.1的一個延伸：
$$G_{t:t+n} \dot{=} R_{t+1} + \gamma R_{t+2} + \cdots \gamma^{n-1}R_{t+n} + \gamma^n\hat{v}(S_{t+n}, \mathbf{w}_{t+n-1}), 0\leq t\leq T-n \tag{9.16}$$
## 9.5 Feature Construction for Linear Methods
線性方法是有趣的，不僅是因為它們有收斂性的保證，還因為實務上它們在資料與計算上都是非常有效率的。關於這一點的話則是取決於states是如何的用特徵(features)來表示，我們會在這一大節中研究這一部份。幫忙task選擇一個適合的features是一種將先驗知識加到強化學習系統的重要方式。直觀來看，features應該是對應狀態空間(state space)的各個方面，同時用這些features來泛化應該是合適的。舉例來說，如果我們正在評估幾何物件(geometric objects)，那我們也許會希望用形狀、顏色、大小、或是功能來做為特徵。如果我們評估的是機器人的狀態(states)，那我們就會希望有位置、剩 電量、最近的聲納數直等等特徵，以此類推。

線性形式(linear form)的一個限制就是它並不能考慮特徵之間的任何[交互作用](http://terms.naer.edu.tw/detail/2118091/)(interactions)，就像是特徵$i$只有在特徵$j$不存在的時候才是好的這種情況。舉例來說，在pole-balancing task([Example 3.4](https://hackmd.io/@shaoeChen/Hkm3mMjL_#Example-34-Pole-Balancing))中，高[角速度](http://terms.naer.edu.tw/detail/2713958/)是好是壞取決於角度。如果角度太大，那高角速度就會有掉落的危機，這就是一種不好的狀態(bad state)，如果角度較小，那高角速度就意味著桿子(pole)正在自己調正，那就是一個好的狀態(good state)。如果我們的特徵是對角度與角速度各別的編碼，那linear value function就無法表示這一點。它必需要取代掉，或是用另外的特徵來結合這兩個底層狀態維度。下面我們就開始來看看各種方法。
### 9.5.1 Polynomials
很多問題的狀態(states)最初都是以數值來表示，像是pole-balancing task中的位置與速度(Example 3.4)，還有Jack's car rental problem的每個點的汽車數量(Example 4.2)，或是Example 4.3的賭徒問題。在這些類型的問題中，強化學習的函數近似(function approximation)其實跟我們熟悉的[插值](http://terms.naer.edu.tw/detail/2118159/)(interpolation)與迴歸任務中有很多共通之處。通常啊，用於插值與迴歸的各種特徵(features)也可以用於強化學習。那Polynomials(多項式)就是用於插值與迴歸中最簡單的特徵族(familes)之一。儘管我們這邊討論的基本的多項式特徵(polynomial features)在強化學習中並不如其它方式來的出色，不過它淺顯易懂，作為開場還不錯。

舉例來說，假設有一個強化學習問題，它有著兩個數值維度的狀態(state)。對單一個表示的state $s$，我們說它有兩個值數，也就是$s_1 \in mathbb{R}$與$s_2 \in mathbb{R}$。你也許會選擇簡單的用它的兩個state dimensions來表示$s$，這樣的話，$\mathbf{x}(s)=(s_1, s_2)^T$，但是這樣的話你可以無法考慮這些維度之間的任何相互作用。此外，如果$s_1$與$s_2$都是0，那近似值(approximate value)也會是0。這兩個限制(維度的相互作用與兩個特徵都是0)都可以透過改用四維特徵向量來表示state $s$來克服，也就是$\mathbf{x}(s) = (1, s_1, s_2, s_1s_2)^T$。最一開始的$1$這個特徵可以代表在原始狀態數值(original state numbers)中的仿射函數，而最後那個內積的特徵，$s_1s_2$，則能夠作為特徵之間的交互作用的考慮。或許，也許你選擇使用更高維度的特徵向量，像是$\mathbf{x}(s)=1, s_1, s_2, s_1s_2, s_1^2, s_2^2, s_1s^2_2, s^2_1s_2, s^2_1s^2_2)^T$來帶入更複雜的交互作用來做為考慮。這樣的特徵向量能夠讓近似值做為狀態數值(state numbers)的任意[二次函數](http://terms.naer.edu.tw/detail/579170/)，即使近似值那些需要學習的權重依然是線性的。把這個範例從兩個泛化到$k$個，我們就可以把問題的狀態維度之間表示為高度複雜的交互作用：

高階多項式基底允許對更複雜的函數做更準確的近似。但是因為$n$階多項式的特徵數量會隨落自然狀態空間(natural state space)的維度$k$而呈現指數型成長(如果$n>0$)，所以我們通常會選擇它的子集來做為函數近似使用。這可以用那些要被近似的函數性質的先驗知識(prior beliefs)來完成，然後用一些多式項迴歸所開發的自動選擇方法來適應強化學習的增量與不穩定的性質。
### 9.5.2 Fourier Basis
另一個線性函數近似的方法就是基於老字號的[傅立葉級數](http://terms.naer.edu.tw/detail/416932/)，它將[周期函數](http://terms.naer.edu.tw/detail/261814/)表示為不同頻率的sine、cosine[基本函數](http://terms.naer.edu.tw/detail/15267792/)(特徵)的加權和(如果對於所有的$x$與某個周期的$\tau$，其$f(x)=f(x + \tau)$，那我們就說函數$f$是週期性的。)。傅立葉級數與更為通用的傅立葉轉換在應用科學中已經被廣泛的使用，一部份的原因是因為，如果我們要去近似的那個函數是已知的，那麼，基本函數(basis function)的權重(weights)就可以由一個簡單的公式來給出，而且，基本上，只要有足夠的basis functions，那不管什麼函數就都可以準確的近似。在強化學習中，當那個要近似的函數是未知的時候，傅立葉基函數(Fourier basis functions)是有趣的，簡單新奇又好玩，它可以在一系列的強化學習問題中有很好的表現。

首先我們來考慮一維的情況。一個週期$\tau$的一維函數的常用的傅立葉級數表示會把這個函數表示為sine、cosine functions的線性組合(linear combination)，這個函數的週期性就是將$\tau$平均的切分(換言之，其頻率就是[基本頻率](http://terms.naer.edu.tw/detail/722235/)$1/\tau$的整數倍)。不過，如果你對定義在一個有界的區間內的近似的非週期性函數感興趣的話，你可以用這些Fourier basis features，然後將$\tau$設置為區間的長度。這樣，感興趣的函數就只會是sine、cosine features的週期性線性組合的一個週期。

此外，如果你把$\tau$設定為感興趣的區間長度的兩倍大，然後把注意力就放在半個區間$[0, \tau/2]$的近似值上，這種情況下你其實可以只用cosine features。這是有可能的，因為你可以只用cosine basis functions就可以表示任何的偶函數(even function)，也就是說，任何於原點對稱的函數。因此，這個half-period(半區間)$[0, \tau/2]$上的任何的函數都可以根據需求在擁有足夠的cosine features的情況下近似。(說任意函數並不是那麼精確，因為這個函數在數學上必需要有良好的行為特性，不過這邊我們就跳過這個技術細節。)或者，單純的使用sine features也是有可能的，反正就是反過來變成其線性組合始終為奇函數(odd functions)，也就是於原點反對稱的函數。不過通常只保留cosine features是比較好的，因為half-even functions會比half-odd functions來的容易近似，這是因為half-odd在原點處通常是不連續的。當然，這並不排除同時使用sine、cosine features來逼近區間$[0, \tau/2]$，這在某些情況下可能是有利的。

依著這個邏輯，然後我們假設$\tau=2$，這樣我們就可以在half-$\tau$區間$[0, \tau/2]$，也就是$[0, 1]$上定義特徵，這一維$n$階的Fourier cosine basis由$n+!$個特徵所組成，對於$i=0,\cdots, n$，
$$x_i(s) = \text{cos}(i\pi s), s\in[0,1],$$

Figure 9.3說明了一維的Fourier cosine features $x_i$，由左到右的$i=1,2,3,4$，而$x_0$則是一個常數函數。

Figure 9.3：One-dimensional Fourier consine-basis features $x_i, i=1,2,3,4$，在區間$[0,1]$上的近似情況。取自Konidaris et al. (2011)。

相同的推理用在multi-dimensional(多維的)Fourier cosine series approximation(傅立葉餘弦級數近似)，如下所述：
假設每個state $s$都對應一個$k$個數值的向量，$s=(s_1, s_2, \cdots, s_k)^T$，然後每個$s_i\in[0, 1]$。那麼，在$n$階的Fourier cosiene basis的第$i$個特徵就可以寫成如下：
$$x_i(s) = \cos(\pi \mathbf{s}^T\mathbf{c}^i) \tag{9.8}$$

其中$\mathbf{c}^i=(c_1^i, \cdots, c_k^i)^T$，對於$j=1,\cdots,k$與$i=1,\cdots,(n+1)^k$，其$c^i_j \in \left\{0,\cdots,n \right\}$。這對$(n+1)^k$個可能的整數向量$\mathbf{c}^i$各別定義一個特徵。內積$\mathbf{s}^T\mathbf{c}^i$有著把$\left\{0,\cdots,n \right\}$的整數分配到$\mathbf{s}$的每個維度的效果。跟在一維(one-dimensional)的情況一樣，這個整數會決定沿著這個維度的特徵頻率。這些特徵當然是可以移動(shifted)、縮放(scaled)來適應特定應用程式有限的狀態空間(state space)。

回頭來舉個例子，我們考慮$k=2$的情況，$\mathbf{s}=(s_1, s_2)^T$，其中，每一個$\mathbf{c}^i=(c^i_1, c^i_2)^T$。Figure 9.4就說明了六個選擇出來的Fourier cosine features，每一個都用定義它的向量$\mathbf{c}^i$來表示($s_1$是水平軸，而$\mathbf{c}^i$就以row vector省略索引$i$的方式來呈現)。$\mathbf{c}$裡面的任何0都意味著該特徵沿延該狀態維度(state dimension)都是常數(恆定)的。因此，如果$\mathbf{c} = (0,0)^T$，那該特徵在兩個維度上就都會是常數(恆定)；如果$\mathbf{c}(c_1, 0)^T$，那該特徵在第二個維度上就會是常數(constant)，但在第一個維度上就會隨著$c_1$的頻率來變化；類似的$\mathbf{c}=(0, c_2)^T$也是一樣的。當$\mathbf{c}=(c_1, c_2)^T$，而且沒有任何的$c_j=0$，那特徵就的沿著兩個維度來變化，代表兩個狀態變數(state variables)之間的交互作用。$c_1,c_2$的值決定了沿著每個維度的頻率，並且它們的比例就決定了交互作用的方向。

Figure 9.4： 我們選出來的六個two-dimensional Fourier consine features，每個特徵都由定義它的向量$c^i$來標記($s_1$是水平軸，而$\mathbf{c}^i$就以row vector省略索引$i$的方式來呈現)。

當我們使用Fourier cosine features結合學習演算法，像是公式9.7，semi-gradient TD(0)、或是semi-graidnet Sarsa，為每個特徵使用不同的step-size也許是有幫助的。如果$\alpha$是一個基本的step-size parameter，那Konidaris、Osentoski、與Thomas (2011)建議，為每個特徵$x_i$設置step-size為$\alpha_i = \alpha / \sqrt{(c^i_1)^2 + \cdots + (c^i_k)^2}$(除了當每個$c_j^i=0$，這種情況下就設定$\alpha_i=\alpha$)。

對比其它的基本函數的集合(像是polynomial、radial basis function)，Fourier cosine features結合Sarsa可以得到一個不錯的效能。不過厚，也不意外，Fourier features在不連續的任務上還是會卡到，除非它包含非常高頻率的基本函數(basis function)，不然的話它很難避免不連續點附近的"[振鈴效應](http://terms.naer.edu.tw/detail/275280/)(ringing)"。

$n$階的Fourier basis內的特徵數量會隨著狀態空間(state space)的維度而呈指數成長，不過如果那維度夠小，像是$k \leq 5$，那就可以選擇$n$，以便使用所有$n$階的Fourier featuers。這多少讓特徵的選擇有一點自動化的味道。不過對於高維度的狀態空間，你還是有必要選擇這些特徵的一個子集。這倒是可以用那個要被近似的函數的性質的先驗知識(prior beliefs)來完成，而且有些自動化選擇的方法其實是適用於處理強化學習的增量與不平穩性質的。Fourier basis features在這方面的話就是說，我們可以很輕易的透過設定$c_i$ vectors來說明狀態變數(state variables)之間疑似的交互作用來選擇特徵，然後利用限制$c_j$ vectors內的值讓近似值可以過濾掉那些被視為是噪點(noise)的高頻率分量(components)。另一方面，因為Fourier features(傅立葉特徵)在整個狀態空間(state space)上是非零(non-zero)的(除了少數零)，所以它們代表狀態(states)的[總體性質](http://terms.naer.edu.tw/detail/2116949/)(global property)，這也意味著我們很難找到表示[局部性質](http://terms.naer.edu.tw/detail/2119107/)(local property)的好方法。

Figure 9.5說明著Fourier與polynomial bases之間learning curves的比較結果，這是在1000-state random walk上做的結果。通常我們並不建議在online learning上使用polynomials。

Figure 9.5：Fourier basis vs polynomials on 1000-state random walk。呈現出來的是gradient Monte Carlo method使用Fourier與polynomial bases的learning curves(5、10、20階)。step-size parameters大致的最佳化：polynomial basis的話，$\alpha=0.0001$，而Fourier basis的話，$\alpha=0.00005$。y軸的話則為效能量測，計算的是root mean square value error(9.1)

### 9.5.3 Coarse Coding
考慮一個任務(task)，其狀態集合的自然表示(natural representation)為連續的二維空間(two dimensional space)。這種情況的一種表示方法就會是由狀態空間(state space)中特徵所對應的圓所組成，如下圖所示：
Figure 9.6： Coarse coding

如果state在圓圈圈的裡面，那對應的特徵值就是1，然後我們說它是存在的(present)；否則，特徵值為0，那就是不存在的(absent)。這種1-0-valued feature就稱為binary feature。給定一個state，有那些特徵是存在(present)的就表明了這個state會在那個圈圈裡面，我們就可以依其位置對其做粗編碼(coarsely code)。把狀態(state)用這種圈圈疊起來的特徵(不一定是圈圈，也沒有一定要是binary feature)來表示就稱為粗編碼(coarsely code)。

假設我們使用線性梯度下降函數近似(linear gradient-descent function approximation)，然後考慮圓的大小與密度的影響。每個圓都對應一個權重($\mathbf{w}$的一個分量(component))，這個權重會受到學習的影響。如果我們在一個state訓練，也就是空間中的一個點，這樣的話，跟那個state有相交的圈圈的權重就通通會受到影響。因此，透過公式9.8，approximate value function就會在受圓圈圈的聯集內的所有states的影響，一個點如果跟state"共同(in common)"的圓愈多，那影響就愈大，如Figure 9.6所示。如果那個圓是小小的，那泛化的效果就不大，如Figure 9.7的左圖，如果圓很大泛化的效果就會很大，如Figure 9.7的中間圖所示。此外，特徵的形狀也會決定泛化的性質。舉例來說，如果它們不是那種很嚴謹的圓形，而是在一個方向上拉長了，那泛化的效果也會受到類似的影響，如Figure 9.7的右圖。

Figure 9.7：linear function approximation methods的泛化效果是由特徵的接收域(receptive fields)的大小、形狀所決定。上圖三種情況有大致相同的特徵數量與密度。

有著較大[接受域](http://terms.naer.edu.tw/detail/3278959/)的特徵給出較寬廣的泛化，不過似乎也將學習到的函數限制為粗略的近似，它無法做出比接受域寬度更細緻的區別(discrimination)。也還好，事情不是我們想的那樣。從一個點到另一個點的初始泛化確實受到接受域的大小、形狀的控制，不過最終可能性的區別還是會受到特徵的總數量的控制。

:::warning
Example 9.3: Coarseness of Coarse Coding

這個範例會說明在粗編碼(coarse coding)中，其接受域大小對學習的影響。用基於粗編碼(coarse coding)與公式9.7的Linear function approximation來學習one-dimensional square-wave function，也就是一維[方形波](https:/[/](http://terms.naer.edu.tw/detail/954263/))函數，如Figure 9.8最上面的圖所示。這個函數的值我們拿做為目標(target)使用，也就是$U_t$。因為只有一維，所以接受域(receptive fields)就變成是區間，而不是圓形。範例上會以三種不同的區間大小來反複學習：有瘦的、剛好的、胖的，如Figure 9.8的最下面那張圖所示。這三種情況有著相同的特徵密度，函數範例內大概有50個特徵。訓練樣本是在這個範圍內隨機均勻的生成的。step-size $\alpha=\dfrac{0.2}{n}$，其中$n$為一次出現的特徵數。Figure 9.8就說明著函數在這三種情況下的學習過程。

Figure 9.8：特徵寬度對初始泛化的強烈影響(first row)以及對漸近精度的微弱影響(last row)。

注意到，特徵的寬度對初期的學習有很強烈的影響。比較寬的特徵會讓泛化的範圍也變寬；如果是比較窄瘦的特徵，那就只會改變每個訓練點周圍的鄰居，這會讓函數的學習不是那麼順利。然而，學習到的那個最終函數只會些許的受到特徵寬度的影響。接受域的形狀往往會對泛化有很強烈的影響，不過對漸近解的品質影響就比較小就是了。
:::
### 9.5.4 Tile Coding
Tile coding是一種用於多維度連續空間粗編碼(coarse coding)的一種形式，具有靈活、且高效率的特性。它可能是當代最實用的的特徵表示。

在tile coding中，特徵的接受域會被分組成狀態空間的分區。每個這樣的分區就稱為tiling，每個分區的元素則稱為tile。舉例來說，二維狀態空間中最簡單的tiling就是[均勻網格](http://terms.naer.edu.tw/detail/15554060/)，如Figure 9.9的左邊圖所示。這邊的tiles或是說接受域是正方形的，而不是剛剛看到的圓形。

Figure 9.9：在有限的二維空間中，多個、重疊的grid-tilings。這些tilings在每個微度上彼此的偏移量是相同的。

如果就這單個tiling被拿來使用，那麼白班點所指出的狀態(state)就會以它所在的那個tile的單一個特徵(single feature)來表示，那泛化就會影響這個tile內的所有的states，對這tile之外的state沒有任何影響。如果只有一個tiling，我們就不會粗編碼(coarse coding)，就只會產生狀態聚合的情況。

為了得到粗編碼(coarse coding)的優點，我們需要重疊(overlapping)接受域，然後根據定義，分區的tiles不重疊。為了使用tile coding來得到真正的coarse coding，我們要使用multiple tilings，每個tiling的偏移(offset)量都是tile width的一小部份。Figure 9.9的右邊給出一個帶有四個tilings的簡單案例。每一個state，像是用白班點指出的state，都很剛好的落在四個tilings的tile裡面。這四個tiles對應四個特徵會在這個state發生的時候變為有效。具體而言，特徵向量$\mathbf{x}(s)$在每一個tiling內的每一個tile的都會有一個分量(component)。在這個範例中就會有4x4x4=64個分量，除了$s$所落在的那四個對應的tiles有值之外，其餘皆為0。Figure 9.10就說明了在1000-state random walk範例中，multiple offset tiling(coarse coding)相較於single tiling的優點。

Figure 9.10：為什麼我們使用粗編碼(coarse coding)。上圖給出的是1000-state random walk的範例，使用gradient Monte Carlo algorithm，具有single tiling與multiple tilings的學習曲線。1000個states的空間被視為單個連續維度(single continuous dimension)，以每個大小為200個states寬的tiles來覆蓋。每個tilings彼此偏移4個states。step-sizes設置為，single tiling $\alpha=0.0001$，50 tilings $\alpha = 0.0001/50$。

tile coding的一個優點就是，它是分區在作業的，任何的state每一次活動(activate)的特徵總數都會是一樣的。每個tiling就只會存在(present)一個特徵，因此存在的特徵總數始終會與tilings的數量是相同的。這讓我們可以以簡單又直觀的方式來設置step-size $\alpha$。舉例來說，選擇$\alpha = \dfrac{1}{n}$，其中$n$為tilings的數量，這就會產生一種精確的一次學習(one-trial learning)。如果用範例$s \mapsto v$來訓練，無論先前的值測值$\hat{v}(s,\mathbf{w}_t)$是多少，新的估測值都會是$\hat{v}(s, \mathbf{w}_{t+1})=v$。通常我們會希望變化可以比這更小，這樣就可以讓目標(target)的輸出考慮到泛化性與隨機變化。舉例來說，我們可以選擇$\alpha = \dfrac{1}{10n}$，這種情況下，那個被訓練的狀態的估測值就會在一次的更新中往目標(target)移動十分之一，與之鄰近的狀態(state)的移動就會比較少一些，這跟它們共同擁有的tiles的數量成正比。

tile coding還可以從這種二進制的特徵向量(binary feature vector)中得到一些計算優勢。因為每一個分量(component)不是0就是1，構成公式9.8的近似值函數(approximate value function)的加權和計算就幾乎是微不足道了。我們並不需要執行$d$次的乘法或是加法，我們只需要簡單的計算$n << d$個活動特徵(active feature)的指數(indices)，然後再加上那$n$個相對應的權重向量的分量(component)即可。

如果這些states它們落在任何相同的tiles，那泛化就會發生在那個被訓練的state以外在相同tiles的其它states，會與共同擁有的tiles的數量成正比。甚至你連選擇tilings彼此之間怎麼樣的偏移(offset)也會影響到泛化性。如果它們在每個維度上很均勻的偏移(offset)，就像是Figure 9.9那樣，這樣，不同的states就可以以不同的方式來泛化，如Figure 9.11的上圖所示。

Figure 9.11：為什麼在tile coding中非對稱性的偏移(asymmetrical offsets)會是首選。上圖說明了來自被訓練的那個狀態(state)(小小的黑色加號表示)泛化到附近狀態(states)的強度，這是一個有8個tilings的範例。如果tilings均勻的偏移(上圖)，那泛化過程中就會存在對角的[假影](http://terms.naer.edu.tw/detail/6254566/)(artifact)與顯著的變化，而如果是不對稱的偏移tilings的話，那泛化過程呈現的就會是更加[球面狀](http://terms.naer.edu.tw/detail/3123321/)而且[齊性(均勻)](http://terms.naer.edu.tw/detail/2117257/)(homogeneous)。

上面八個子圖中，每一個都說明了從被訓練的那個狀態(黑色小加加)到附近點的泛化模式。這個範例中，有八個tilings，因此一個tile裡面有64個明顯的泛化子區域(subregions)，不過這都是根據這個八個模式之一泛化而來。注意到，均勻偏移(uniform offsets)是如何的在很多模式中(pattern)沿著對角線產生強烈的影響。如果tilings是不對稱地偏移，那我們就可以避免掉假影(artiface)，如上圖下半部所示。這些較低的泛化模式是比較好的，因為它們能夠很好的以被訓練的那個狀態(state)為中心點，並不會有明顯的不對稱性。

在所有的情況中，tilings在每個維度上彼此的偏移都是tile寬度的一小部份。如果$w$表示tile的寬度，然後$n$表示tilings的數量，這樣$\dfrac{w}{n}$就會是基本單位。在邊邊為$\dfrac{w}{n}$的小小正方形中，所有的狀態(states)都會activate(啟動?活化?激活?)相同的tiles數量，然後有相同的特徵表示(feature representation)，相同的近似值(approximated value)。如果有一個狀態(state)以$\dfrac{w}{n}$的大小在任意的迪卡爾方向(cartesian direction)上移動，那特徵表示的變化就會是component/tiles。所以我們說，均勻的偏移tilings，大家彼此之間的偏移量就會剛好是這個單位距離。如果是二維空間的話，我們說，tiling都是透過[位移向量](http://terms.naer.edu.tw/detail/203886/)$(1, 1)$來做偏移，這意思就是說，對比前一個tiling，其偏移量會是位移向量乘上$\dfrac{w}{n}$。這些項目中，Figure 9.11的下半部說明了，非對稱偏移的(asymmetrically offset)tilings，$n$是如何的被用著$(1, 3)$的位移向量來做偏移。

基本上已經有很多對於不同的位移向量對tile coding的泛化性影響的研究(Parks and Militzer, 1991; An, 1991; An, Miller and Parks, 1991; Miller, An, Glanz and Carter, 1990)，評估它們的同質性(homegeneity)與對角假影的趨勢，就像是你在$(1, 1)$位移向量中所看到的那樣。基於這個研究，Miller與Glanz(1996)就建議用由第一個為奇數所組成的位移向量(displacement vectors)。特別是，對於$k$維的連續空間，一個比較好的選擇就是使用第一個為奇數$(1,3,5,7,...,2k-1)$，然後$n$(tilings的數量)的話2的次方($2^x$之類的)，然後要大於或等於$4k$。這就是我們產生Figure 9.11下半部的tilings所做的事情，我們設置$k=2, n=2^3$，這樣$2^3=8 \geq 4 \times 2$，對了，這邊的位移向量為$(1, 3)$。三維情況的話，前四個tilings的偏移相對於基本位置的話會是$(0,0,0), (1,3,5), (2,6,10), (3,9,15)$。已經有不少開源軟體可以有效的對任意的$k$來做tilings的偏移。

在選擇tining strategy的時候，我們必需要選擇tilings的數量與tiles的形狀。tilings的數量以及tiles的大小決定了[漸近逼近](http://terms.naer.edu.tw/detail/2111487/)(asymptotic approximation)的解析度(resolution)與精細度，如general coarse coding(通用粗編碼?)與Figure 9.8所示。tiles的形狀則決定泛化的性質，如Figure 9.7所示。square tiles在每個維度上的泛化效果大致相同，如Figure 9.11下部所示。延著一個維度來拉長tiles，就像是Figure 9.12中間圖所示的那個stripe tilings，這會促始它延著該維度泛化。

Figure 9.12：tilings不一定是網格狀的。它們可以是任意形狀、非均勻的，而且在很多情況下仍然是可以高效計算出結果的。

Figure 9.12中間那個tilings，在左側的部份的tilings比較密集，也比較薄，這促進了延著水平軸(horzontal dimension)在該維度上較低值的區別(discrimination)。Figure 9.12的右邊那個diagonal stripe tiling就會促始沿著對角線來泛化。在一些更高維度中，使用這種軸對齊的條紋(axis-aligned stripes)會在某些tilings會忽略掉一些維度，也就是超平面切片(hyperplanar slices)。也會是像是Figure 9.12左圖的這種irregular tilings(不規則的)，儘管很少見。

實務上，我們通常希望在不同的tilings中使用不同形狀的tiles。舉例來說，可能可以有一些是垂直的(vertical stripe tilings)，然後一些水平的(horizontal stripe tilings)。這可以促始沿著任一維度來泛化。不過厚，單純的使用stripe tilings是不大可能學習到水平座標與垂直座標特定交界處所具有的獨特價值(不論學到什麼，它都會滲入(bleed into)具有相同水平、垂直座標的狀態(state))。為此，我們需要連結rectangular tiles，就像是Figure 9.9所呈現的那樣。透過多個tilings，一些水平的、一些垂直的、一些連接的，這樣你就可以得到任何你想要的事情了：我們可以根據偏好延著每一個維度來泛化，仍然可以學習到交界處的特定值(see Sutton, 1996 for examples)。tilings的選擇決定其泛化性，一直到這種選擇可以有效的自動化執行之前，til coding對於讓選擇變的靈活而且有意義的這一點是很重要的。

另外還有一個技巧可以降低記憶體用量，就是hashing，不過這一部份我就先不翻譯，後續有機會再回頭。
todo：這段沒有翻完，有空再回頭

### 9.5.5 Radial Basis Functions
[徑向基底函數](http://terms.naer.edu.tw/detail/15197305/)(radial basis function)是coarse coding(粗編碼)對連續值特徵(continuous-valued features)的一種自然的泛化。不過它的特徵不是0、1，而是一個介於$[0, 1]$之間的任意值，這反映出該特徵存在(present)的不同程度。典型的RBF feature，$x_i$，有著[高斯響應](http://terms.naer.edu.tw/detail/3476818/)(Gaussian response，bell-shaped)，$x_i(s)$，也就是鐘形分佈的那個形狀，其僅取決於狀態(state) $s$與特徵的原型(prototypical)或中心狀態$c_i$之間的距離，以及特徵的相對寬度，$\sigma_i$：

$$x_i(s) \dot{=} \exp \left(- \dfrac{\Vert s-c_i \Vert^2}{2\sigma_i^2} \right)$$

我們可以用任何看起來最適合當前狀態(state)與任務(task)的方式來選擇範數(norm)或是距離度量(distance metric)。下圖給出一維Euclidean distance metric(歐幾里德距離)的範例：

RBF相對於binary feature的主要優點在於，它們所產生的approximate functions的變化平滑而且可微。雖然這很引吸人，不過多數情況下並不具實際的意義。儘管如此，在tile coding背景下，也已經有很多像是RBFs這類的graded response functions(梯度反應函數?)的研究了(An, 1991; Miller et al., 1991; An et al., 1991; Lane, Handelman and Gelfand, 1992)。所有這些方法都需要大量額外的計算複雜度(超過tile coding)，而且只要你的狀態維度(state dimension)超過兩個，效能就會降低。在高維度的情況中，tiles的邊緣(edges)更為重要，已經證明很難在邊緣附近獲得良好控制的tile。

RBF network是一個線性函數逼近器(linear function approximator)，它使用RBF做為它的特徵(feature)。它的學習方式是由公式9.7、9.8所定義，跟其它的線性函數逼近器完全一樣。此外，RBF networks的一些學習方法也會改變特徵的中心與寬度，這把它們帶入非線性函數逼近器的領域。非線性的方法也許能夠更精確的擬合目標函數。RBF newwork，尤其是非線性的情況下，它的計算複雜度更高，而且在它學習到一定程度之前你要有很多的手動調整就是了。
## 9.6 Selecting Step-Size Parameters Manually
通常SGD methods需要設計人員去選擇一個適合的step-size parameter $\alpha$。理想上，這個選擇可以是自動的，而且某些情況下它確實是自動的，不過多數情況下，手動設置仍然是常見的作法。所以啊，我們為了更好的瞭解演算法，我們要來對step-size parameter的功能建立一些直觀的看法。不過我們能夠說說一般應該如何設置嗎?

很可惜的是，這種理論上的討論是沒有幫助的。隨機近似理論(2.7)給了我們一個慢慢減少step-size sequence來保證收斂的條件，不過這些條件通常會導致學習速度太慢。一個經典的選擇，$\alpha_t=1/t$，這在tabular MC methods中產生樣本均值，但並不適用於TD methods、非平穩的問題，或是任何使用函數逼近(function approximation)的方法。線性方法的話，存在著[遞迴最小平方](http://terms.naer.edu.tw/detail/56632/)(recursive least-squares)的方法來設置最佳矩陣步長(optimal matrix step size)，這些方法可以被擴展到TD learning，像是Section 9.8所說的LSTD method，不過這需要$O(d^2)$個step-size parameters或是我們正在學習的參數量的$d$倍多。因為這個原因，我們並不會在最需要函數近似的大型問題中使用這些方法。

:::warning
$$\sum_{n=1}^\infty \alpha_n(a) = \infty \text{ and } \sum_{n=1}^\infty \alpha^2_n(a) < \infty \tag{2.7}$$
:::

為了能夠對手動設置這些step-size parameter有更直觀的感受，我們暫時先回到tabular的案例。這邊我們會瞭解到，step-size $\alpha=1$的時候，會導致在一個目標完成之後，其樣本誤差完全的消除(見公式2.4且step-size=1的情況)。如討論，我們通常希望學習速度能夠比這慢一些。在tabular情況中，$\alpha=\dfrac{1}{10}$會需要約10次的經驗才能近似收斂至它們的平均目標(mean target)，如果我們希望的是在100次的經驗中學習，那我們就可以使用$\alpha = \dfrac{1}{100}$。不過，一般來說，如果$\alpha=\dfrac{1}{\tau}$，對一個state的tabular estimate(表估測值?)會在大約$\tau$次遇到該state的經驗之後收斂至其目標的平均值，而且最近一次的目標值會有最大的影響。

:::warning
$$\text{NewEstimate} \leftarrow \text{OldEstimate + StepSize [ Target - OldEstimate ]} \tag{2.4}$$
:::

一般函數近似的話(general function approximation)，對於一個state的經驗次數這件事，我們可能沒有那麼清楚的概念，因為每一個state也許在不同程度上跟其它的state相似或不相似。不過，在線性函數近似的情形中，有這麼一個規則給出了類似的行為。假設你希望在大約$\tau$次經驗中學習大致相同的特徵向量。那麼，在linear SGD methods中設置step-size parameter的一個經驗法則就是：
$$\alpha \dot{=} \left(\tau\mathbb{E}[\mathbf{x}^T\mathbf{x}]] \right)^{-1} \tag{9.19}$$

其中$\mathbf{x}$是與來自於SGD的輸入向量相同分佈中所選擇的一個隨機向量特徵(random feature vector)。如果特徵向量的長度變化不大，那這方法的效果是最好的；理想上$\mathbf{x}^T\mathbf{x}$是一個常數。

## 9.7 Nonlinear Function Approximation: Artificial Neural Networks

人工神經網路(Artificial neural networks (ANNs))廣泛的用了非線性函數近似(nonlinear function approximation)。ANN是一個由相互連接的單元所組成的網路，這些單元具有神經元的一些特性，而神經系統的主要組成就是神經元。ANNs已經有很長的歷史了，在deeply-layered ANNS(deep learning)在一些學習系統上有著令人印象深刻的能力，當然，包括強化學習系統。在Chaper 16會有一些使用ANN function approximation的強化學習系統的範例說明。


Figure 9.14就說明了一個通用的feedforward ANN，這意謂著網路中沒有loops(迴圈?)，也就是說，網路中沒有路徑可以讓單元的輸出影響到其輸入。圖中的網路有一個由兩個輸出單元組成的輸出層(output layer)，四個輸入單位(input unit)組成的輸入層(input layer)，以及兩個"隱藏層"(hiddey layers)：也就是不是輸入也不是輸出的那幾個層。real-valued weight(實數值權重)則是與每一個連結相關聯。如果ANN在它的連接中存在一個loop，那它就是recurrent，而不是feedforward ANN。不過兩個方法其實都用在強化學習了，只是說我們這邊只看feedforward。

那個Figure 9.14上的圈圖圖，也就是單元，通常是半線性(semi-linear unit)，這意味著它們會先計算其輸入信號的加權和，然後把這個加權和用到非線性函數(non-linear function)，這非線性函數稱為activation function(啟動函數、活化函數、激活函數)，以此產生單元的output或是activation。有很多不同的activation function可以使用，通常是S-shaped或是sigmoid function，像是logistic function，$f(x) = 1/(1 + e^{-x})$，或是ReLU(rectifier nonlinearity)，$f(x)=\max(0, x)$。step function([階梯函數](http://terms.naer.edu.tw/detail/2125361/))，像是$f(x)=1, \text{ if }x \geq \theta \text{ and $0$ otherwise}$，可以利用閥值$\theta$讓結果是一個二進次單元(binary unit)。網路輸入層(input layer)的單元(units)有些許的不同，它們的啟動(activation)設定為外部提供的值，這些值是網路要近似的那個函數的輸入。

feedforward ANN的每個output unit的activation是input units啟動模式(activation pattern)的非線性函數。這些函數被連接網路的權重給參數化。沒有hidden layers的ANN就只能表示一小部份的可能的input-output function。不過，沒有hidden layer的ANN只要有足夠大的有限數量的sigmoid units，它就可以在網路輸入空間的緊湊區域(compact region)上以任意精度來近似任意的連續函數(Cybenko, 1989)。這對其它滿足mild condition(溫合條件?)的非線性啟動函數也是一樣的，不過非線性不可少的條件就是：如果所有multi-layer feedforward ANN的units都有線性啟動函數，那整個網路就相當於一個沒有隱藏層的網路，因為就一路線性的啊。

儘管one-hidden-layer ANNs有這種"通用近似(universal approximation)"的特性，從經驗還有理論都再再的說明著，要近似人工智慧所需要的複雜函數，多個幾層可能還是比較好(See Bengio, 2009, for a thorough review.)。這種deep ANN的多層計算能夠讓網路原始輸入的表示更加的抽象，每個單元(unit)都提供一個特徵，這有助於網路的整體input-output的階層表示(hierarchical representation)。

因此，訓練ANN的hidden layers的方法就是自動地建立適合所給定的問題的特徵，這樣子，就可以在沒有人工手刻特徵的情況下生成hierarchical representations。這對人工智慧來說是一種持久的挑戰賽，而且這也解釋了為什麼有著隱藏層的ANNs學習演算法在近幾年這麼受到關注。ANNs通常是用隨機梯度來學習(Section 9.3)。每個權重都是朝著讓網路整體效能提高的方向在走，這個效能指的就是一個目標函數(objective function)，可能是最大化，也可能是最小化。在最常見的監督式學習中，目標函數通常就是一組標記好的訓練資料的預期的誤差(expected error)或是損失(loss)。在強化學習的話，ANNs可以用TD errors來學習value function，或者可以把目標放在像是Section 2.8說的gradient bandit，或是policy-gradient(策略梯度，Chapter 13)那樣子來最大化expected weward做為目標。剛剛說的這些情況，我們都有必要去估測每個連接權重的變化會如何影響網路的整體效能，換言之，就是在給定網路當前權重值的情況下，估測目標函數相對於每個權重的偏導數(partial derivative)。而梯度就是這些偏導數所組成的向量。

對於ANNs最成功的一個演算法(假設units為可微的啟動函數(activation functions))就是反向傳播(backpropagation)，forward、backward，交替執行所組成。每次的forward pass都會利用所給定的網路輸入單元(input units)的當前啟動來計算出每個unit的啟動(activation)輸出。在每次的forward pass之後，backward pass會很有效率的計算每個權重的偏導數(跟其它的隨機梯度學習演算法一樣，這些偏導數的向量就只是對真實梯度的一個估測值)。在Section 15.10中我們會討論用強化學習來練有隱藏層的ANNs，而不是用反向傳播。不過計算效率不是那麼好，只是它們可能更接近現實中神經網路學習的方式。

反向傳播演算法能夠在那種有1、2層隱藏層(hidden layer)的淺層網路有好的結果，不過可能不適合更深的ANNs。事實上，訓練一個有$k+1$個隱藏層的網路會比一個$k$個隱藏層的網路效能還要來的不好，儘管較深的網路能夠表示較淺的網路所有表示的所有函數(Bengio, 2009)。要解釋這樣的結果並不容易，不過有幾個重要的因素。首先，典型的deep ANN中會有大量的權重，這就造成難以避免過擬合(overfitting)的問題，也就是說，網路沒有訓練到的就沒有辦法正確的泛化。再來就是，backpropagation沒有辦法很好的在deep ANNs運作的原因就是，偏導數的計算是透過它的backward passes，偏導數(梯度)的消失與爆炸都會造成學習上的困難。不過近期許多成功的案例就是因為成功克服這問題。

過擬合是基於有限訓練資料來調整具有多個[自由度](http://terms.naer.edu.tw/detail/3647931/)(degrees of freedom)函數近似方法都會遇到的問題。這對沒有依賴有限訓練集的強化學習來說問題不大，怎麼樣有效地泛化仍然是一個重要的問題。過擬合通常是ANNs訓練中的一個問題，因為權重多嘛，所以已經有不少方法來減少過擬合了。幾個方法像是，在驗證資料的效能開始下降的時候停止訓練(cross validation)，調整目標函數限制近似的複雜度(正規化(regularization))，以及在權重之前引入依賴關係，以此減少自由度的數量(權值共享)。

一個降低overfitting還蠻有效的方法就是由Srivastava, Hinton, Krizhevsky, Sutskever, and Salakhutdinov (2014)所提出的dropout。訓練過程中會隨機的拿掉權重單元。這可以視為是訓練大量的"thinned"(稀疏)網路。最終再結合這些稀疏網路，這也是一種提高泛化效能的方法。(後面大概就是在稱讚dropout能降低overfitting就不翻了，總之dropout就是潮，不過有智權，要小心)

接下來這段談的是Hinton, Osindero, and Teh (2006)提出的deep belief networks的架構。在這架構中，他們用unsupervised learning algorithm從最深的那層開始一次訓練一層。在不依賴整體目標函數(overall objective function)的情況下，非監督式學習(unsupervised learning)可以補捉到[輸入流](http://terms.naer.edu.tw/detail/2117978/)(input stream)那些統計規律的特徵(就是補捉到一個模式，pattern)。最深的那層最先訓練，然後用訓練這一層的輸入來訓練下一層，以此類推，直到所有的權重或是多數權重訓練完畢，再拿這些訓練好的權重來做為監督式學習的權重初始值。然後再用backpropagation來微調(fine-tuned)。研究指出，這樣子的方法比隨機初始的效果還要來的好。這樣的方式可以得到較好的效能有很多種說法，不過其中一種就是，這方法將網路置於權重空間的區域中，gardient-based algorithm可以從中得到好的進展。

Batch normalization (Ioffe and Szegedy, 2015)是另一個可以讓我們更輕鬆的訓練deep ANNs的技術。大家都知道的一個八卦，就是，如果我們對網路的input做正規化(normalized)，ANN的學習就比較簡單一些，像是把每個input variable變成均值為零、方差為1(zero mean and unit variance)。訓練deep ANNs的batch normalization會把上一層的output在餵給下一層做為input之前做正規化的縮放。Ioffe and Szegedy (2015)用著來自訓練資料的子集，或是小批量(mini-batches)的方式來縮放這些層與層之間的信號，以此方式提高deep ANNs的學習率。

另一個技術就是deep residual learning (He, Zhang, Ren, and Sun, 2016)。有時候，學習function與identity function之間的差異比起學習函數(function)本身還要來的容易。把這個差異，或者我們說，把這個residual function(殘差函數)加到input來產生需要的函數。這一段要說的就是ResNet，我就不多翻了，有興趣可以看先前翻譯好的[論文](https://hackmd.io/@shaoeChen/SyjI6W2zB/https%3A%2F%2Fhackmd.io%2F%40shaoeChen%2FSy_e1mCEU)。後續Chapter 16談到的圍棋遊戲就有用到這個技術。

接下來這段要談的就是卷積神經網路，上面連結也有一些翻譯好的論文，就請直接點擊即可，pass。不過如果希望有基礎的話可以看吳恩達老師的相關課程。


## 9.8 Least-Squares TD
目前為止談到的方法在每個time step的計算都與其參數量成正比。這一節會提出一個線性函數逼近(linear function approximation)的方法，這可能是這一方法中能做到最好的一種。

正如我們在Section 9.4的TD(0)中所建立的那樣，線性函數逼近會漸近的收斂到TD fixed point(TD[不動點](http://terms.naer.edu.tw/detail/2116246/))：
$$\mathbf{w}_{TD}=\mathbf{A}^{-1}\mathbf{b}$$

其中

$$\mathbf{A} \dot{=} \mathbf{E}[\mathbf{x_t}(\mathbf{x}_t - \gamma \mathbf{x}_{t+1})^T] \text{ and } \mathbf{b} \dot{=} \mathbb{E}[R_{t+1}\mathbf{x}_t]$$

有人可能會問說，為什麼我們必需迭代計算這個解？這太浪費資料了。我們能不能直接計算$\mathbf{A},\mathbf{b}$的估測值，然後求出TD fixed point？Least-Squares TD algorithm(Least-Squares，[最小平方](http://terms.naer.edu.tw/detail/2118769/))，也就是眾所階知的LSTD，就是這麼做的。它形成一個自然的估測值
$$\hat{\mathbf{A}}_t \dot{=}\sum_{k=0}^{t-1} \mathbf{x}_k(\mathbf{x}_k - \gamma \mathbf{x}_{k+1})^T + \epsilon \mathbf{I} \text{ and } \hat{\mathbf{b}}_t \dot{=}\sum_{k=0}^{t-1} R_{k+1}\mathbf{x}_k\tag{9.20}$$

，其中$\mathbf{I}$是一個[單位矩陣](http://terms.naer.edu.tw/detail/152318/)(identity matrix)，然後$\epsilon\mathbf{I}$，只要你的$\epsilon > 0$，然後是小小的數值，這能夠確保$\hat{\mathbf{A}}_t$總是可逆(invertible)的。看起來這些估測值似乎都應該再除上$t$，也確實應該如此；如所定義，這些實際上是$t$乘上$\mathbf{A}$與$t$乘上$\mathbf{b}$的估測值。不過，當LSTD用這些估測值來估測TD fixed point的時候，額外的這個$t$是會被約分掉的：
$$\mathbf{w}_t \dot{=} \hat{\mathbf{A}}_t^{-1}\hat{\mathbf{b}}_t \tag{9.21}$$

這個演算法可以說是linear TD(0)中資料使用效率最高的一個形式，不過需要的計算成本也是也高的。回想一下semi-gradient TD(0)所需要的記憶體用量，而且每一個time step的計算複雜度也只是$O(d)$。

究竟LSTD的計算複雜度為何？上面來看，複雜度似乎是隨著$t$而增加，但是公式9.20中的兩個近似值可以用我們在Chapter 2中提到的增量學習來實作，這樣每個time step就可以以常數時間來完成。不過，儘管如此，$\hat{\mathbf{A}}_t$還是免不了要處理到[外積(outer product)](http://terms.naer.edu.tw/detail/3118065/)(column vector乘上row vector)，這會是一個矩陣更新；它的計算複雜度就會是$O(d^2)$，當然，它的計憶體用量也會是$O(d^2)$。

有個潛在的問題就是，最終的公式9.21用到了$\hat{\mathbf{A}}_t$的逆(inverse)，這個計算複雜度通常會是$O(d^3)$。幸運的是，我們這種特別形式的矩陣的逆，也就是外積的加總，可以用著$O(d^2)$的計算複雜度來做增量更新，對於$t>0$且$\hat{\mathbf{A}}_{0}\dot{=}\epsilon\mathbf{I}$的情況下：
$$
\begin{align}
\hat{\mathbf{A}}_t^{-1} &= \left(\hat{\mathbf{A}}_{t-1} + \mathbf{x}_{t-1}\left(\mathbf{x}_{t-1} - \gamma\mathbf{x}_t \right)^T \right)^{-1} \tag{from 9.20} \\
&= \hat{\mathbf{A}}^{-1}_{t-1} - \dfrac{\hat{\mathbf{A}}^{-1}_{t-1}\mathbf{x}_{t-1}(\mathbf{x}_{t-1} - \gamma\mathbf{x}_t)^T\hat{\mathbf{A}}^{-1}_{t-1}}{1 + (\mathbf{x}_{t-1} - \gamma\mathbf{x}_t)^T\hat{\mathbf{A}}_{t-1}^{-1}\mathbf{x}_{t-1}} \tag{9.22}
\end{align}
$$

雖然恆等式(identity)9.22，也就是[雪曼-莫尼森公式(Sherman-Morrison
formula)](http://terms.naer.edu.tw/detail/3165441/)表面上看起來非常複雜，不過它只涉及到vector-matrix與vector-vector的乘法計算，所以它的複雜度就只有$O(d^2)$。因此，我們可以用公式9.22來保存並維持逆矩陣$\hat{\mathbf{A}}^{-1}_t$，過程中，每個time step只需要花費你少少的$O(d^2)$的記憶體與計算複雜度。下面給出完整的演算法：

當然，$O(d^2)$的計算成本怎麼看都還是比semi-gradient TD的$O(d)$還要來的高。所以啊，LSTD對資料處理的高效率這個特點是否值得你投入就要看$d$到底有多大，學習效率的重要性有多少以及系統其它部份的花費是否允許你採用。事實上，LSTD不需要step-size parameter這件事有時候常被拿出來說嘴。對啦，LSTD是真的不需要step size，但它需要$\epsilon$啊，如果$\epsilon$設置太小，那逆序列(sequence of inverses)的變化就會很大，如果設置太大，那學習就會變的比較慢。另外，LSTD沒有step-size parameter就意謂著，它永遠不會忘記。這有時候是好事，不過，如果目標策略(target policy) $\pi$的改變是像強化學習與GPI那樣的話就會有點問題了。在控制應用中，LSTD通常必需結合其它的機制來誘發遺忘，用這樣的方式來說嘴自己不需要step-size parameter的優點。

## 9.9 Memory-based Function Approximation
目前為止我們已經談了不少的參數方法來近似value function。這種方法厚，就是學習演算法會調整函數形式的參數，然後在問題的整個狀態空間(state space)中近似value function。每一次的更新，$s\mapsto g$，都是學習演算法(learning algorithm)用來更新參數的訓練範例(training example)，目地就是減少近似誤差(approximation error)。更新之後，training example就可以丟掉了(雖然還是有機會被存下來再次的利用)。當我們需要state的approximate value(或者我們稱之為query state)的時候，就只需要用learning algorithm所產生的最新參數對著想知道的state評估其value function即可。

Memory-based的functino approximation很不一樣。它們就只是把training examples保存在記憶體中(或最少保存一個examples的子集)，沒有更新任何的參數。然後，在需要查詢(query)某個state的估測值的時候，我們才會從記憶體中檢索一組的examples，再用這組examples來計算其估測值。這方法有時候也稱為lazy learning，因為它處理training examples的過程是推遲的(postponed)，一直到系統查詢了才會給出一個output。

Memory-based function approximation methods是[非參數方法(nonparametric method)](http://terms.naer.edu.tw/detail/3651410/)的一個主要代表。跟參數方法不同，它近似函數的形式不限於固定的參數化的函數類(像是線性函數或是多項式)，它是由training examples本身以及用於結合它們來輸出query states的估測值的某些方法所決定。所以說，隨著記憶體中所累積的training example愈多，我們希望非參數方法能夠對任意的目標函數產生愈來愈精確的近似值。

這種memory-based methods有很多種，這取決於如何選擇那些保存的training examples以及如何回應查詢。我們這邊就先關注在local-learning methods，這方法僅於當前所查詢的狀態(current query state)的鄰近區域中局部地(locally)近似value function。這些方法會先從記憶體中檢索一組的training examples，相關training examples的states會被判斷是與被query的那組state最相關的，相關性的話通常是取決於兩個state之間的距離：愈接近被query的state就代表愈相關，當然有很多不同的方法可以定義距離(distance)。在query state被賦予一個值之後，這個local approximation(局部近似值)就會被丟掉。

memory-based中最簡單的範例就是nearest neighbor method(最近鄰方法)，你可以很輕易的在記憶體中找出與query state最相近的example，並回傳該example的value來做為query state的近似值(approximate value)。換句話說，如果query state是$s$，且$s'\mapsto g$是記憶體中的example，其中$s'$是最接近$s$的狀態(state)，然後$g$就會是做為$s$的近似值的回傳。比較複雜一點的方法是加權平均(weighted average)，它檢索一組最接近的樣本(examples)，然後回傳它們目標值(target values)的加權平均值，其中權重的部份通常會隨著它們之間(樣本與query state)的距離的增加與減少。Locally weighted regression(局部加權迴歸?)也是類似的，它是藉著參數近似的方法(parametric approximation)將[曲面(surface)](http://terms.naer.edu.tw/detail/2125824/)擬合一組到一組最近狀態(nearest states)的值(value)，它會像公式9.1一樣最小化[加權誤差(weightred error)](http://terms.naer.edu.tw/detail/2758125/)的量測，其權重也是取決於與query state之間的距離。回傳值則是query state對locally-fitted surface(局部擬合曲面)的評估值(evaluation，或稱計值?)，一樣的，在計值(evaluation)之後就會丟掉這個local approximation surface。

由於是非參數型(nonparametric)，基於記憶體(memory-based)的方法，相較於參數型(parametric)的方法的先天優勢在於，它並不限制你的approximations必需要是預先指定的函數形式。通常隨著你資料的累積愈多，準確度也會提高。Memory-based local approximation methods還有其它的特性，讓這方法非常適合應用在強化學習上面。因為軌跡(trajectory)的採樣在強化學習中是如此之重要(如Section 8.6所述)，memory-based local methods可以將函數近似(function approximation)關注在實際或是在模擬軌跡(simulated trajectories)中看過的states(或是state-action pair)的局部鄰域上(local neighborthoods)。你可能不需要做到global approximation，因為state space上的不少區域可能這輩子你也永遠不會(或幾乎不會)碰到。另外，相較於參數型的方法需要逐步調整全域近似(global approximation)的參數，memory-based methods可以讓agent的經驗對當前狀態(current state)的鄰近狀態的估測值有著相對立即性的影響。

避免全域近似(global approximation)同時也是解決維度災難的一個方法。舉例來說，如果有個state space有著$k$維，那tabular method要保存global approximation的樣本所需要的記憶體空間就會是$k$個指數多。另一方法，如果你要保存一個memory-based method的樣本，每個樣本(example)需要的記憶體與$k$成比例，保存$n$個樣本所需要的記憶體在$n$裡面是成線性的。並不需要$k$或是$n$的指數那麼多。當然，關鍵在於，momory-based methods是否能夠很快的回答query，從而對agent而言是有幫助的。一個相關的問題就是，回覆的速度會如何隨著記憶體用量的增長而降低。在大型資料庫中查詢最近鄰(nearest neighbors)可能需要花費很多時間，因此在很多應用程式中是不實用的。

memory-based methods的支持者們已經開發出加速最近鄰搜尋(nearest neighbor search)的方法。使用平行計算是一個方法；另一種方法是用特殊的多維資料結構來保存訓練資料。有一種用於這種應用程式的結構，就是$k-d$ tree($k$-dimensional tree的縮寫)，這種tree會遞迴把$k$維的空間拆分為binary tree的節點排列的區域。根據資料量及其於狀態空間(state space)上的分佈，使用$k-d$ tree的nearest-neighbor search能夠快速的消除鄰域搜尋空間中大量的區域，這樣子就可以在一些naive searches會花費較長時間的搜尋上變的可行。

Locally weighted regression還需要快速的方法來做局部迴歸(local regression)的計算，這些計算必需要能重複的執行來回答每一次的query。研究人員也已經開發出很多方法來解決這個問題，包含讓資料庫大小能夠維持在一定範圍內的forgetting entries。你也可以看這一章最後的參考文獻(我沒有翻)內的相關資料。
## 9.10 Kernel-based Function Approximation
上面談到的那個像是加權平均(weighted average)還是局部加權迴歸(locally weighted regression)的memory-based methods，都是取決於將權重分配給資料庫內的樣本，也就是$s' \mapsto g$，那這個權重的話就是以$s'$跟query state $s$之間的距離計算而得。分配這些權重的函數就稱為核函數(kernel function)，或簡稱為kernel。舉例來說，在weighted average跟locally weighted regression中，這個kernel function $k:\mathbb{R} \to \mathbb{R}$就是以states之間的距離來分配權重。一般來說，權重不一定要取決於距離；也可以是其它狀態(states)之間的相似度的量測。這種情況下，$k: \mathcal{S} \times \mathcal{S} \to \mathbb{R}$，因此，$k(s, s')$就會是$s'$在回答查詢關於state $s$的時候，其對於查詢結果影響性的權重。

我們從稍微不同的角度來看，$k(s, s')$就是一個從$s'$到$s$的一個泛化性強度的量測值。kernel functions用數值來表示關於任意狀態(state)與其它任意狀態(state)之間的相關程度。舉例來說，Figure 9.1中所給後個tile coding的泛化強度，這對應了uniform(均勻)與asymmetrical(非對稱)tile offsets所產生的不同的kernel functions。儘管tile coding在它的操作過程中並沒有很明確的使用kernel function，不過實際上它的泛化就是根據某一個kernel function在做的。事實上，如我們下面要討論所說的，用linear parametric function approximation所產生的泛化強度始終可以用kernel function來說明的。

[核迴歸(kernel regression )](http://terms.naer.edu.tw/detail/3650120/)是一種memory-based的方法，它會計算保存在記憶體中的所有樣本的目標(targets)的核加權平均(kernel weighted average)。如果$\mathcal{D}$是一個保存的樣本(example)集合，然後$g(s')$表示在保存的樣本中的狀態(state)$s'$的目標，那麼，kernel regression就會去近似(approximates)目標函數，這種情況下，取決於$\mathcal{D}$的那個value function就會是
$$\hat{v}(s, \mathcal{D}) = \sum_{s'\in\mathcal{D}}k(s,s')g(s')\tag{9.23}$$

上面說的那個加權平均方法是一個特例，其中$k(s, s')$只有在兩者之間非常接近的時候才會是非零，所以其實你並不需要在$\mathcal{D}$上面所有的狀態(states)做計算。

一個常見的kernel就是在Section 9.5.5中談到的RBF function approximation中所用到的Gaussian radial basis function(RBF)。在那邊我們談到過，RBFs是一種從一開始其中心與寬度就已經是固定的特徵，其中心會是在一個我們預期會有很多樣本集中落在某個地方的區域，或者會以某些方法在學習過程中調整。排除掉調整中心與寬度的方法不說，這是一種linear parametric method，其參數是每一個RBF的權重，通常會利用stochastic gradient descent或是semi-gradient descent來學習。近似的形式是一種預先確定的RBF的線性組合。使用RBF kernel的kernel regression在兩個方面上跟這個不同。首先，它是memory-based：RBF是以保存的樣本狀態(states)為中心。其次，它是非參數的(nonparametric)：沒有需要學習的參數；針對查詢(query)的回應(response)由公式9.23所給出。

當然，在實作kernel regression的時候肯定很多毛要處理，不過這已經超過這邊的範圍了，就不多說。不過，事實證明，任何一個像是我們在Section 9.4所談用著特徵向量$\mathbf{x}(s)=(x_1(s),x_2(s),\cdots,x_d(s))^T$來表示states的linear parametric regression method，都可以被改寫為kernel regression，其中$k(s, s')$是$s,s'$的特徵向量的內積，也就是：
$$k(s,s')=\mathbf{x}(s)^T\mathbf{x}(s') \tag{9.24}$$

使用這個kernel function的kernel regression產生的近似值與linear parametric methods使用這些特徵向量並使用相同的訓練資料學習所產生的近似值相同。

上面的數學證明我們直接pass掉，你可以在不少的機器學習文本中到相關證明，像是Bishop (2006)。我們可以直接構造kernel function，而不需要像是linear parametric function approximators那樣還需要構造特徵。並非所有的kernel functions都可以像是公式9.24那樣的以特徵向量的內積來表示，只不過阿，可以用這樣的方式來表示的kernel function跟等效的parametric method來看，確實是具有比較明顯的優勢。對於很多的特徵向量集合來說，公式9.24有著緊湊的(compace)[泛函(functional)](http://terms.naer.edu.tw/detail/2116578/)形式，你在這個$d$維空間中不需要任何的計算就可以對其做評估。這些情況下，kernel regression會比用這些特徵向量來表示狀態(state)的linear parametric method來的簡單的多。這就是人稱的"kernel trick"，這讓我們可以在擴張特徵空間的高維度中高效率的作業，而且實際上也只是使用保存的訓練樣本集在作業而以。這種kernel trick是很多機器學習方法的基礎，研究人員也已證明其對強化學習的益處。
## 9.11 Looking Deeper at On-policy Learning: Interest and Emphasis

我們目前為止談到的部份會把所有遇到的states看成是一樣重要的。不過，在某些情況下，我們也許會對某些states感興趣的程度高於其它的。舉例來說，在discounted episodic的問題中，我們可能會對episode中有準確地估值的早期狀態(early states)比較有興趣，而非後期狀態(later states)，因為後期狀態會因為折扣的計算(discount)讓reward對於起始狀態(start state)的value而言變的不是那麼重要。又或者說，如果正在學習一個action-value function，那我們去準確地評估values遠低於greedy action的poor action可能就不是那麼樣的重要。function approximation的資源始終是有限的，所以阿，如果我們能夠更有方向的來使用它們，那效能還是可以提高的。

我們必需要平等看到每一個遇到的states的一個理由就是，我們是依據on-policy distribution來更新的，為此，semi-gradient methods可以得到更強的理論結果。回想一下，on-policy distribution被定義是依著target policy，然後在MDP中遇到的狀態分佈(distribution of states)。現在我們來把這個概念泛化一下。我們會有很多的on-policy distribution，而不是只有一個。所以這些on-policy distribution都有一個共同性，也就是，它們是依著target policy，然後在軌跡中(trajectories)遇到的狀態分佈，不過，某種意義上，它們在軌跡(trajectories)的初始化上會有所不同。

我們現在引入新的概念。首先，我們隆重介紹non-negative scalar(非負純量？)，一個稱為interest的隨機變數，$I_t$，這個隨機變數指出我們對於在時間$t$準確地評估狀態(state)(或state-action pair)感興趣的程度。如果我們一點也不在乎這個state，那這個interest就應該是0；如果我們非常在意，那它就可能是1，雖然正式來說，它可以是任意的非負值。然後，在公式9.1中提到的$\overline{\mathrm{VE}}$中的分佈就定義為依著target policy所遇到的states的分佈，用interest來做加權。第二，介紹另一個非負純量的隨機變數，emphasis $M_t$。這個純量(scalar)會乘上learning update，以此emphasizes(著重)或是de-emphasizes(不著重)在時間$t$完成的learning。取代公式9.15的general $n-$step learning rule為：
$$\mathbf{w}_{t+n} \dot{=} \mathbf{w}_{t+n-1} + \alpha M_t[G_{t:t+n} - \hat{v}(S_t, \mathbf{w}_{t+n-1})]\nabla \hat{v}(S_t, \mathbf{w}_{t+n-1}), 0 \leq t < T \tag{9.25}$$

，用公式9.16所給的$n$-step的return，以及由interest遞迴(recurisvely)確定的emphasis為：
$$M_t = I_t + \gamma^nM_{t-n}, 0\leq t< T \tag{9.26}$$

對於所有的$t<0$，其$M_t\dot{=}0$。這些方程式也包含Monte Carlo的情況，其中$G_{t:t+n}=G_t$，所有的更新(updates)都會在episode的結束才執行，$n=T-t$且$M_t=I_t$

Example 9.4說明interest與emphasis如何能夠產出更準度的估測值。

:::info
Example 9.4: Interest and Emphasis

為了瞭解interest與emphasis的好處，考慮下面four-state Markov reward process：

episodes會從最左邊的state開始，然後轉移一個state到右邊，得到reward +1，一直走，直到最終到達terminal state。因此，第一個state的true value為4，然後就是3、2、1。這些就是state的true values；估測值也只能近似這些true values，因為它們已經被[參數化(parameterization)](http://terms.naer.edu.tw/detail/254345/)限制住。參數向量(parameter vector)有兩個分量(conponents)，$w=(w_1, w_2)^T$，參數化的部份就如裡面每個state所寫入的那般。因此，前兩個state的估測值是由$w_1$單獨所給出，而且即使它們的true values是不同的，它們的估測值也必需要是相同的。類似的，第三、第四個state的個估測值是由$w_2$單獨給出，即使true values不同，估測值也必需要是相同的。假設，我們只對最左邊那個state的準確評估值有興趣；我們就給這個state的interest設置為1，其它state的interest設置為0，如上圖中各state上面的$i$所示。

首先我們考慮用gradient Monte Carlo algorithms來解這個問題。前面我們討論這演算法(公式9.7)的時候並未考慮interest與emphasis，最終結果會收斂至參數向量$\mathbf{w}_{\infty}=(3.5, 1.5)$，這給出第一個state，也就是我們唯一感興趣的那一個state的估測值為3.5(即介於第一、第二個state的true values的中間)。另一方面，我們剛剛提到使用interest與emphasis的方法，它會完全正確地學到第一個state的value；$w_1$會收到至4，而$w_2$永遠不會被更新，因為除了最左邊的第一個state之外，其它的的state的emphasis都是0。

現在我們用two-step semi-gradient TD methods。一樣的，在公式9.15、9.16的時候我們並沒有考慮interest與emphasis，它也是收斂至$\mathbf{w}_{\infty}=(3.5, 1.5)$，而使用interest與emphasis的方法則是收斂至$\mathbf{w}_{\infty}=(4, 2)$。可以看的到，採用interest與emphasis的方法產生的第一、第三個state的value完全正確(由第一個state進行bootstraps)，而第二、第四個states是完全沒有做任何的更新。
:::
## 9.12 Summary
強化學習系統如果想要能夠用於人工智慧或是大型工程應用，就必需要能夠泛化。為了實現這一點，現有的監督式學習的函數逼近方法中的任一種都可以輕易地通過將每次更新作為訓練樣本(training example)來使用。

也許最合適的監督式學習方法是那些使用參數化函數近似的方法，那policy就會由權重向量$w$來參數化。儘管權重向量(weight vector)有著許多分量(components)，但狀態空間(state space)更大啊，所以我們仍然還是要滿足於得到的近似解。我們定義mean square value error(均方誤差)，$\overline{\mathrm{VE}}(\mathbf{w})$，來做為在on-policy distribution $\mu$下權重向量$\mathbf{w}$在$v_{\pi_{\mathbf{w}}}(s)$的誤差度量。$\overline{\mathrm{VE}}$也給了我們一個簡潔明瞭的方法，讓我們可以在on-policy的情形下衡量不同的value-function approximations。

為了找到一個好的權重向量，最受歡迎的就是stochastic gradient descent(SGD，隨機梯度)的各種不同版本的方法。這一章我們關注在有fixed policy的on-policy的情況，也就是policy evaluation或是prediction；這情形很自然的一個學習演算法就是$n$-step semi-gradient TD，這包含了gradient Monte Carlo與semi-gradient TD(0)，分別為$n=\infty$與$n=1$的特例。semi-gradient TD並不是真正的梯度(gradient)方法。在這類的bootstrapping methods中(包含DP)，權重向量會在update target中出現，不過在計算梯度的時候並沒有考慮這點，所以才會稱為semi-gradient methods。也因此，它們無法依賴傳統SGD產生的結果來分析。

不過，semi-gradient methods在linear function approximation的特殊情況中還是可以得到好的結果，其估測值是特徵乘上相對應的權重的總和。線性情況在理論上通常是最容易理解的，只要你有適當的特徵，實務上就可以很好的作業。選擇特徵是一種把領域的先驗知識加到強化學習系統最重要的方法之一。可以是多項式(polynomials)，只是在強化學習中通常會考慮使用的online-learning上它的泛化性就很差。比較好的像是根據Fourier basis選擇特徵，或是根據那些有著稀疏重疊接受域(sparse overlapping receptive fields)的粗編碼(coarse coding)。tile coding是一種在計算上特別高效率且靈活的粗編碼的形式。Radial basis functions對於一維、二維的任務非常有用，這種任務中平滑地變化反應(response)是很重要的。LSTD則是資料使用效率(data-efficient)最高的一個linear TD prediction方法，但是它的計算需求就會跟權重數量的平方成正比，其它的方法的複雜度則是與權重數量成線性關係。非線性方法(nonlinear methods)包含訓練人工神經網路在用的backpropagation(反向傳播)跟SGD的各種不同的版本；這些方法這幾年變的非常受歡迎，我們稱為深度強化學習。

Linear semi-gradient $n$-step TD在標準條件下對所有的$n$都能夠保證收斂到$\overline{\mathrm{VE}}$，也就是最佳誤差(optimal error)的範圍內(以Monte Carlo漸近的實現)。然而，太大的$n$會造成學習太慢，通常某種程度上的bootstrapping($n < \infty$)是比較可取的，這就跟我們在Chapter 7談的tabular $n-$step methods跟Chapter 6中比較tabular TD與Monte Carlo methods一樣。