一、Introduction

（一）Large-Scale Reinforcement Learning

強化學習可用于解決較大的問題，例如：

Backgammon: $10^{20}$ states
Computer Go: $10^{170}$ states
Helicopter: continuous state space
在最近的兩堂課中，我們如何擴展無模型的預測和控制方法？

（二）Value Function Approximation

到目前為止，我們已經(jīng)通過查找表（lookup table）表示了值函數(shù)
- 每個狀態(tài)s都有一個條目V(s)
- 或每個狀態(tài)-動作對(s,a)都有有一個條目Q(s,a)
Problem with large MDPs:
- states and/or actions太多，無法存儲在內存中
- 單獨學習每個狀態(tài)的值太慢
  到目前為止，我們使用的是查表（Table Lookup）的方式，這意味著每一個狀態(tài)或者每一個狀態(tài)行為對對應一個價值數(shù)據(jù)。對于大規(guī)模問題，這么做需要太多的內存來存儲，而且有的時候針對每一個狀態(tài)學習得到價值也是一個很慢的過程
Solution for large MDPs:
- 過函數(shù)近似來估計實際的價值函數(shù)
- 把從已知的狀態(tài)學到的函數(shù)通用化推廣至那些未碰到的狀態(tài)中
- 用MC或TD學習來更新函數(shù)參數(shù)。

（三）Types of Value Function Approximation

針對強化學習，近似函數(shù)根據(jù)輸入和輸出的不同，可以有以下三種架構：

針對狀態(tài)本身，輸出這個狀態(tài)的近似價值；
針對狀態(tài)行為對，輸出狀態(tài)行為對的近似價值；
針對狀態(tài)本身，輸出一個向量，向量中的每一個元素是該狀態(tài)下采取一種可能行為的價值。

（四）Which Function Approximator?

有許多函數(shù)逼近器，例如

特征的線性組合
神經(jīng)網(wǎng)絡
決策樹
最近鄰
傅立葉/小波基
......

我們考慮可微函數(shù)逼近器，例如

$\color{#FF0000}{特征的線性組合}$
$\color{#FF0000}{神經(jīng)網(wǎng)絡}$
決策樹
最近鄰
傅立葉/小波基
......
此外，我們需要一種適用于 $\color{red}{非平穩(wěn)，非iid數(shù)據(jù)}$ 的訓練方法

所有和機器學習相關的一些算法都可以應用到強化學習中來，其中線性回歸和神經(jīng)網(wǎng)絡在強化學習里應用得比較廣泛，主要是考慮這兩類方法是一個針對狀態(tài)可導的近似函數(shù)。

強化學習應用的場景其數(shù)據(jù)通常是非靜態(tài)、非獨立均勻分布的，因為一個狀態(tài)數(shù)據(jù)是可能是持續(xù)流入的，而且下一個狀態(tài)通常與前一個狀態(tài)是高度相關的。因此，我們需要一個適用于非靜態(tài)、非獨立均勻分布的數(shù)據(jù)的訓練方法來得到近似函數(shù)。

下面分別從遞增方法和批方法兩個角度來講解價值函數(shù)的近似方法，其主要思想都是梯度下降，與機器學習中的隨機梯度下降和批梯度下降相對應。

二、Incremental Methods

（一）Gradient Descent

假定 $J(w)$ 是參數(shù)向量為 $w$ 的可微函數(shù)
定義 $J(w)$ 的梯度為
調整參數(shù) $w$ 超朝著負梯度的方向，尋找 $J(w)$ 的局部最小值

$\alpha$ 是一個步長參數(shù)，機器學習里稱為學習速率參數(shù)

用隨機梯度下降來近似價值函數(shù)

目標：找到參數(shù)向量 $w$ ，最小化近似函數(shù) $\widehat v(S,w)$ 與實際函數(shù) $v_{\pi}(S)$ 的均方差：
梯度下降能夠找到局部最小值：
使用隨機梯度下降對梯度進行更新，來近似差的期望：

（二）Linear Function Approximation

Feature Vectors

用特征向量表示狀態(tài)
例如：
- 機器人到地標的距離
- 股市趨勢
- 象棋棋子和棋子配置

Linear Value Function Approximation

通過特征的線性組合表示值函數(shù)
參數(shù)為w的目標函數(shù)是二次函數(shù)
隨機梯度下降收斂于全局最優(yōu)
更新規(guī)則特別簡單
在線性函數(shù)逼近下，

所以更新式可以簡化為

$Update = step-size\times prediction error\times feature value$

Table Lookup Features

查表是線性值函數(shù)逼近的一種特殊情況
使用表格查詢特征
參數(shù)向量w給出每個狀態(tài)的值

每一個狀態(tài)看成一個特征，個體具體處在某一個狀態(tài)時，該狀態(tài)特征取1，其余取0。參數(shù)的數(shù)目就是狀態(tài)數(shù)，也就是每一個狀態(tài)特征有一個參數(shù)。

（三）增量預測算法

假設有監(jiān)督者給出了真正的值函數(shù) $v_\pi(s)$
但是在RL中沒有監(jiān)督，只有rewards
實際上，我們用一個target代替
- 在MC中，target是回報 $G_t$
在TD(0)中，target是TD target $R_{t+1}+\gamma\widehat v(S_t,w)$
在TD( $\lambda$ )中，target是 $\lambda-return$ $G_t^\lambda$

1、Monte-Carlo with Value Function Approximation

return $G_t$ 是對真實值 $v_\pi(S_t)$ 的無偏差、無噪聲取樣
因此可以將監(jiān)督學習應用于“訓練數(shù)據(jù)”：
例如，使用線性蒙特卡洛策略評估
蒙特卡洛評估收斂到局部最優(yōu)（為什么？書上和老師都沒說）
有兩個原因：

蒙特卡洛算法并不能窮盡搜索所有的狀態(tài)。由于它需要到episode結束才能進行計算，效率并不算高，樣本不夠多。
$G_t$ 并不算是一個目標（target）

即使使用非線性值函數(shù)逼近

3、TD Learning with Value Function Approximation

TD-target $R_{t+1}+\gamma\widehat v(S_{t+1},w)$ 是對真實值 $v_\pi(S_t)$ 的有偏差采樣。
仍可以將監(jiān)督學習應用于“ 訓練數(shù)據(jù)”：

例如，使用線性TD(0)
線性TD(0)收斂（接近）到全局最優(yōu)(以為教授證明得到)

一方面是TD每一個時間步就可以進行更新，可取得的樣本更多
TD target 是一個目標，每次更新都朝著目標前進，更容易收斂。

4、TD( $\lambda$ ) with Value Function Approximation

$\lambda-return$ $G_t^\lambda$ 也是對真實值 $v_\pi(S)$ 的有偏差采樣。
可以再次將監(jiān)督學習應用于“ 訓練數(shù)據(jù)”：
Forward view linear TD( $\lambda$ )
Backward view linear TD( $\lambda$ )

前視圖和后視圖線性 TD( $\lambda$ ) 是等效的

5、 Control with Value Function Approximation

把近似函數(shù)引入到控制過程中,我們需要能夠近似狀態(tài)行為對的價值函數(shù)近似而不是僅針對狀態(tài)的價值函數(shù)近似。
如圖所示：

從一系列參數(shù)開始，得到一個近似的狀態(tài)行為對價值函數(shù)，在?-greedy執(zhí)行策略下產生一個行為，執(zhí)行該行為得到一個即時獎勵，以此數(shù)據(jù)計算目標值，進行近似函數(shù)參數(shù)的更新。再應用這個策略得到后續(xù)的狀態(tài)和對應的目標值，每經(jīng)歷一次狀態(tài)就更新依次參數(shù)，如此反復進行策略的優(yōu)化，同時逼近最優(yōu)價值函數(shù)。

策略評估：是一個近似策略評估 $\widehat q (\cdot ,\cdot,w) \approx q_\pi$ ，特別是早期誤差會較大，而且這種近似無法最終收斂于最優(yōu)策略對應的行為價值函數(shù)，只能在其周圍震蕩，后文將講述改進方法。

策略改進：?-greedy策略進行改進

6、Action-Value Function Approximation

近似action-value函數(shù)
最小化近似作用值函數(shù) $\widehat q(S,A,w)$ 與真實作用值函數(shù) $q(S,A)$ 之間的均方誤差
用隨機梯度下降方法找到局部最小值：

7、Linear Action-Value Function Approximation

同樣我們介紹使用線性函數(shù)來近似狀態(tài)行為價值函數(shù)時的公式，狀態(tài)行為價值可以用特征向量表示：
通過特征的線性組合表示作用值函數(shù)
隨機梯度下降更新

8、Incremental Control Algorithms

與預測算法類似，我們找到真實行為價值的目標值。
- 對于MC算法，目標值就是return $G_t$ ：
對于TD(0)，目標值就是TD目標：
對于前向認識TD(λ)，目標值是λ-return：
對于后向認識TD(λ)，對應的參數(shù)更新是：

（四）Mountain Car

1、山區(qū)汽車中帶有粗編碼的線性Sarsa

小車爬山是一個經(jīng)典的強化學習示例。環(huán)境如圖左上角所示，小車被困于山谷，單靠小車自身的動力是不足以在谷底由靜止一次性沖上右側目標位置的，比較現(xiàn)時的策略是，當小車加速上升到一定位置時，讓小車回落，同時反向加速，使其加速沖向谷底，借助勢能向動能的轉化沖上目標位置?，F(xiàn)在問題是在模型位置的情況下，如何用強化學習的方法找到小車沖上目標位置的最優(yōu)策略。

狀態(tài)空間是小車的位置和速度，其它幾張三維圖展示的是經(jīng)過不同步數(shù)（上中圖）以及不同Episode（其余幾張三維圖）的學習，小車位于某個位置同時具有某個速度的狀態(tài)價值。

最初的動作是0，這是樂觀的（注意，這個任務中所有的真實價值都是負數(shù)），這使得即使試探參數(shù) $\epsilon$ 為0，也會引起廣泛的試探。這可以從圖的中間頂部為“step 428”的圖中可以看到。盡管這時候一個episode都沒完成，但是車子在山谷里沿著狀態(tài)空間的弧形軌跡來回擺動。所有經(jīng)常訪問的狀態(tài)的價值函數(shù)都比未試探到的狀態(tài)低，這是因為實際的收益比（不切實際的）預期的要差。這會不斷驅使智能體離開其所在的地點，去探索新的狀態(tài)，直到找到最優(yōu)解決方案。

最后小車使用SARSA學習到了接近最優(yōu)策略的價值函數(shù)，如下圖：

2、Study of $\lambda$ Should We Bootstrap?

下圖顯示了幾種不同的任務，使用不同λ進行的強化學習算法分析結果?？偟膩碚fλ=1的時候通常算法表現(xiàn)是很差的，TD(0)是比MC好得多的方法，這說明了Bootstrap的重要性；不同的任務對應的最優(yōu)λ值是不太容易確定的。

五、Convergence（收斂）

1、預測算法的收斂性

MC使用的是實際價值的有噪聲無偏估計，雖然很多時候表現(xiàn)很差，但總能收斂至局部或全局最優(yōu)解。TD性能通常更加優(yōu)秀，是否意味著TD也是一直收斂的呢？答案是否定的。David給出了一個TD學習不收斂的例子，這里不再詳述，這里給出各種算法在使用不同近似函數(shù)進行預測學習時是否收斂的小結。

注：打鉤表示能收斂，打叉表示不收斂。

從表中可以看出，沒有函數(shù)近似時，各種算法都收斂；
線性函數(shù)近似時現(xiàn)時策略學習可以收斂，但離線策略時僅有MC收斂；
非線性函數(shù)近似時無論采用現(xiàn)時策略還是離線策略只有MC收斂。而MC算法在實際中是很少使用的。這給強化學習的實際應用帶來的挑戰(zhàn)。好在我們有一些改善TD算法的辦法。

2、Gradient Temporal-Difference Learning

TD不遵循任何目標函數(shù)的梯度
這就是為什么當off-policy或使用非線性函數(shù)逼近時TD可能會發(fā)散的原因
我們可以通過修改TD算法使得它遵循Projected Bellman Error的梯度進而收斂。

3、Convergence of Control Algorithms

針對控制學習的算法，其收斂性比較如下圖：

（對勾）代表在最佳值函數(shù)附近震蕩

針對控制學習算法，大多數(shù)都能得到較好的策略，但是理論上只要存在函數(shù)近似，就都不是嚴格收斂的，比較常見的是在最優(yōu)策略上下震蕩，逐漸逼近然后突然來一次發(fā)散，再逐漸逼近等。使用非線性函數(shù)近似的效果要比近似函數(shù)要差很多，實際也是如此。

三、Batch Methods

（一）Batch Reinforcement Learning

梯度下降很簡單而且很吸引人
但是不夠取樣是不夠高效的
批處理方法尋求找到最佳價值函數(shù)
根據(jù)智能體的經(jīng)驗（“訓練數(shù)據(jù)”）

前面所說的遞增算法都是基于數(shù)據(jù)流的，經(jīng)歷一步，更新算法后，我們就不再使用這步的數(shù)據(jù)了，這種算法簡單，但有時候不夠高效。與之相反，批方法則是把一段時期內的數(shù)據(jù)集中起來，通過學習來使得參數(shù)能較好地符合這段時期內所有的數(shù)據(jù)。這里的訓練數(shù)據(jù)集“塊”相當于個體的一段經(jīng)驗。

（二）最小平方差預測

假設存在一個價值函數(shù)的近似 $\widehat v (s,w) \approx v_\pi(s)$
以及一段時期的、包含<狀態(tài)、價值>的經(jīng)歷D：
最小平方差算法要求找到參數(shù)w，使得下式值最?。?img class="math-inline" src="https://math.jianshu.com/math?formula=v_t%5E%5Cpi" alt="v_t^\pi" mathimg="1">為目標值

1、Stochastic Gradient Descent with Experience Replay

給出包含<state,value>對的經(jīng)驗：

Repeat:

Sample state, value from experience
Apply stochastic gradient descent update

這將收斂至針對這段經(jīng)歷最小平方差的參數(shù):

2、Experience Replay in Deep Q-Networks (DQN)

DQN使用experience replay和fixed Q-targets（再建立第二個神經(jīng)網(wǎng)絡，我們實際上是在用兩套神經(jīng)網(wǎng)絡運行的，因此也就是兩套完全不同的參數(shù)向量，我們一般會凍結老的神經(jīng)網(wǎng)絡，試圖存儲下所有看過的信息，之后我們就會用目標對凍結的目標一個引導輔助程序，我們并不是對新設立的目標做輔助引導程序，這樣就能使得程序更加穩(wěn)定。僅從字面意思上來看的話，我們對老的神經(jīng)網(wǎng)絡的幾千條信息進行升級處理，逐步替換就能夠形成新的神經(jīng)網(wǎng)絡。我們永遠不會直接對目前的新目標進行輔助引導，因為那是不穩(wěn)定的。在你設立的目標和你的實際價值之間是有一定聯(lián)系的，這使得你的神經(jīng)網(wǎng)絡不受控制。）

根據(jù) $\epsilon-greedy$ 策略產生行動 $a_t$
將經(jīng)驗以 $(s_t,a_t,r_{t+1},s_{t+1})$ 的形式存儲到replay memery D
從D中隨機抽樣一個mini-batch的經(jīng)驗 $(s,a,r,s')$
用固定參數(shù) $w^-$ 計算Q-learning target，維護兩個神經(jīng)網(wǎng)絡DQN1，DQN2,一個網(wǎng)絡固定參數(shù)專門用來產生目標值，目標值相當于標簽數(shù)據(jù)。另一個網(wǎng)絡專門用來評估策略，更新參數(shù)。
在Q-network 和 Q-learning targets之間優(yōu)化MSE
使用隨機梯度下降的的方式更新參數(shù)。

首先，隨機采樣打破了狀態(tài)之間的聯(lián)系；第二個神經(jīng)網(wǎng)絡會暫時凍結參數(shù)，我們從凍結參數(shù)的網(wǎng)絡而不是從正在更新參數(shù)的網(wǎng)絡中獲取目標值，這樣增加了算法的穩(wěn)定性。經(jīng)過一次批計算后，把凍結參數(shù)的網(wǎng)絡換成更新的參數(shù)再次凍結產生新一次迭代時要用的目標值。

3、DQN in Atari

從像素s端到端學習值函數(shù)Q(s,a)
輸入狀態(tài)s是最后4幀的原始像素堆棧
輸出為Q(s,a)，用于18個操縱桿/按鈕位置
獎勵是該步驟的分數(shù)變化

網(wǎng)絡架構和超參數(shù)貫穿所有游戲

這里舉了一個應用DQN玩Atari類游戲的例子，算法直接對屏幕進行拍照，將最近4幀的屏幕圖像送入一個卷積神經(jīng)網(wǎng)絡，最終輸出針對游戲手柄的18個按鈕精細方位的Q(s,a)值算法直接獲取游戲屏幕的圖像信息，對應的近似函數(shù)類型好像是第三類，獎勵信息根據(jù)當時屏幕顯示的分數(shù)確定。這種設計在50中Atari類游戲中測試，表現(xiàn)很好。