Lecture 6: Value Function Approximation

一跌穗、Introduction

（一）Large-Scale Reinforcement Learning

強(qiáng)化學(xué)習(xí)可用于解決較大的問(wèn)題，例如：

  • Backgammon: 10^{20} states
  • Computer Go: 10^{170} states
  • Helicopter: continuous state space
    在最近的兩堂課中艺智，我們?nèi)绾螖U(kuò)展無(wú)模型的預(yù)測(cè)和控制方法？

（二）Value Function Approximation

  • 到目前為止圾亏，我們已經(jīng)通過(guò)查找表（lookup table）表示了值函數(shù)
    • 每個(gè)狀態(tài)s都有一個(gè)條目V(s)
    • 或每個(gè)狀態(tài)-動(dòng)作對(duì)(s,a)都有有一個(gè)條目Q(s,a)
  • Problem with large MDPs:
    • states and/or actions太多十拣，無(wú)法存儲(chǔ)在內(nèi)存中
    • 單獨(dú)學(xué)習(xí)每個(gè)狀態(tài)的值太慢
      到目前為止，我們使用的是查表（Table Lookup）的方式志鹃，這意味著每一個(gè)狀態(tài)或者每一個(gè)狀態(tài)行為對(duì)對(duì)應(yīng)一個(gè)價(jià)值數(shù)據(jù)夭问。對(duì)于大規(guī)模問(wèn)題，這么做需要太多的內(nèi)存來(lái)存儲(chǔ)曹铃，而且有的時(shí)候針對(duì)每一個(gè)狀態(tài)學(xué)習(xí)得到價(jià)值也是一個(gè)很慢的過(guò)程
  • Solution for large MDPs:

    • 過(guò)函數(shù)近似來(lái)估計(jì)實(shí)際的價(jià)值函數(shù)


    • 把從已知的狀態(tài)學(xué)到的函數(shù)通用化推廣至那些未碰到的狀態(tài)中
    • 用MC或TD學(xué)習(xí)來(lái)更新函數(shù)參數(shù)缰趋。

（三）Types of Value Function Approximation

針對(duì)強(qiáng)化學(xué)習(xí)，近似函數(shù)根據(jù)輸入和輸出的不同陕见，可以有以下三種架構(gòu)：


  • 針對(duì)狀態(tài)本身秘血，輸出這個(gè)狀態(tài)的近似價(jià)值；

  • 針對(duì)狀態(tài)行為對(duì)评甜，輸出狀態(tài)行為對(duì)的近似價(jià)值灰粮；

  • 針對(duì)狀態(tài)本身，輸出一個(gè)向量蜕着，向量中的每一個(gè)元素是該狀態(tài)下采取一種可能行為的價(jià)值谋竖。

（四）Which Function Approximator?

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

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

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

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

所有和機(jī)器學(xué)習(xí)相關(guān)的一些算法都可以應(yīng)用到強(qiáng)化學(xué)習(xí)中來(lái)韧骗，其中線性回歸和神經(jīng)網(wǎng)絡(luò)在強(qiáng)化學(xué)習(xí)里應(yīng)用得比較廣泛，主要是考慮這兩類方法是一個(gè)針對(duì)狀態(tài)可導(dǎo)的近似函數(shù)零聚。

強(qiáng)化學(xué)習(xí)應(yīng)用的場(chǎng)景其數(shù)據(jù)通常是非靜態(tài)袍暴、非獨(dú)立均勻分布的，因?yàn)橐粋€(gè)狀態(tài)數(shù)據(jù)是可能是持續(xù)流入的隶症，而且下一個(gè)狀態(tài)通常與前一個(gè)狀態(tài)是高度相關(guān)的政模。因此，我們需要一個(gè)適用于非靜態(tài)蚂会、非獨(dú)立均勻分布的數(shù)據(jù)的訓(xùn)練方法來(lái)得到近似函數(shù)淋样。

下面分別從遞增方法和批方法兩個(gè)角度來(lái)講解價(jià)值函數(shù)的近似方法，其主要思想都是梯度下降胁住，與機(jī)器學(xué)習(xí)中的隨機(jī)梯度下降和批梯度下降相對(duì)應(yīng)趁猴。

二刊咳、Incremental Methods

（一）Gradient Descent

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

\alpha是一個(gè)步長(zhǎng)參數(shù)儡司，機(jī)器學(xué)習(xí)里稱為學(xué)習(xí)速率參數(shù)

用隨機(jī)梯度下降來(lái)近似價(jià)值函數(shù)

  • 目標(biāo)：找到參數(shù)向量w娱挨，最小化近似函數(shù)\widehat v(S,w)與實(shí)際函數(shù) v_{\pi}(S)的均方差：

  • 梯度下降能夠找到局部最小值：


  • 使用隨機(jī)梯度下降對(duì)梯度進(jìn)行更新，來(lái)近似差的期望：


（二）Linear Function Approximation

Feature Vectors

  • 用特征向量表示狀態(tài)


  • 例如：
    • 機(jī)器人到地標(biāo)的距離
    • 股市趨勢(shì)
    • 象棋棋子和棋子配置

Linear Value Function Approximation

  • 通過(guò)特征的線性組合表示值函數(shù)


  • 參數(shù)為w的目標(biāo)函數(shù)是二次函數(shù)


  • 隨機(jī)梯度下降收斂于全局最優(yōu)

  • 更新規(guī)則特別簡(jiǎn)單
    在線性函數(shù)逼近下捕犬，



    所以更新式可以簡(jiǎn)化為


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

Table Lookup Features

  • 查表是線性值函數(shù)逼近的一種特殊情況

  • 使用表格查詢特征


  • 參數(shù)向量w給出每個(gè)狀態(tài)的值



    每一個(gè)狀態(tài)看成一個(gè)特征跷坝，個(gè)體具體處在某一個(gè)狀態(tài)時(shí)，該狀態(tài)特征取1碉碉，其余取0探孝。參數(shù)的數(shù)目就是狀態(tài)數(shù)，也就是每一個(gè)狀態(tài)特征有一個(gè)參數(shù)誉裆。

（三）增量預(yù)測(cè)算法

  • 假設(shè)有監(jiān)督者給出了真正的值函數(shù)v_\pi(s)
  • 但是在RL中沒(méi)有監(jiān)督顿颅，只有rewards
  • 實(shí)際上，我們用一個(gè)target代替v_\pi(s)
    • 在MC中足丢，target是回報(bào)G_t
  • 在TD(0)中粱腻，target是TD targetR_{t+1}+\gamma\widehat v(S_t,w)
  • 在TD(\lambda)中，target是\lambda-return G_t^\lambda

1斩跌、Monte-Carlo with Value Function Approximation

  • returnG_t 是對(duì)真實(shí)值v_\pi(S_t)的無(wú)偏差绍些、無(wú)噪聲取樣

  • 因此可以將監(jiān)督學(xué)習(xí)應(yīng)用于“訓(xùn)練數(shù)據(jù)”：


  • 例如，使用線性蒙特卡洛策略評(píng)估


  • 蒙特卡洛評(píng)估收斂到局部最優(yōu)（為什么耀鸦？書(shū)上和老師都沒(méi)說(shuō)）
    有兩個(gè)原因：
  1. 蒙特卡洛算法并不能窮盡搜索所有的狀態(tài)柬批。由于它需要到episode結(jié)束才能進(jìn)行計(jì)算，效率并不算高袖订，樣本不夠多氮帐。
  2. G_t并不算是一個(gè)目標(biāo)（target）
  • 即使使用非線性值函數(shù)逼近

3、TD Learning with Value Function Approximation

  • TD-target R_{t+1}+\gamma\widehat v(S_{t+1},w)是對(duì)真實(shí)值v_\pi(S_t)的有偏差采樣洛姑。

  • 仍可以將監(jiān)督學(xué)習(xí)應(yīng)用于“ 訓(xùn)練數(shù)據(jù)”：



    例如上沐，使用線性TD(0)


  • 線性TD(0)收斂（接近）到全局最優(yōu)(以為教授證明得到)
  1. 一方面是TD每一個(gè)時(shí)間步就可以進(jìn)行更新，可取得的樣本更多
  2. TD target 是一個(gè)目標(biāo)楞艾，每次更新都朝著目標(biāo)前進(jìn)参咙，更容易收斂。

4硫眯、TD(\lambda) with Value Function Approximation

  • \lambda-return G_t^\lambda 也是對(duì)真實(shí)值v_\pi(S)的有偏差采樣蕴侧。

  • 可以再次將監(jiān)督學(xué)習(xí)應(yīng)用于“ 訓(xùn)練數(shù)據(jù)”：


  • Forward view linear TD(\lambda)
  • Backward view linear TD(\lambda)

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

5、 Control with Value Function Approximation

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



從一系列參數(shù)開(kāi)始净宵，得到一個(gè)近似的狀態(tài)行為對(duì)價(jià)值函數(shù)，在?-greedy執(zhí)行策略下產(chǎn)生一個(gè)行為，執(zhí)行該行為得到一個(gè)即時(shí)獎(jiǎng)勵(lì)塘娶，以此數(shù)據(jù)計(jì)算目標(biāo)值归斤，進(jìn)行近似函數(shù)參數(shù)的更新。再應(yīng)用這個(gè)策略得到后續(xù)的狀態(tài)和對(duì)應(yīng)的目標(biāo)值刁岸，每經(jīng)歷一次狀態(tài)就更新依次參數(shù)脏里，如此反復(fù)進(jìn)行策略的優(yōu)化，同時(shí)逼近最優(yōu)價(jià)值函數(shù)虹曙。

策略評(píng)估：是一個(gè)近似策略評(píng)估 \widehat q (\cdot ,\cdot,w) \approx q_\pi迫横，特別是早期誤差會(huì)較大，而且這種近似無(wú)法最終收斂于最優(yōu)策略對(duì)應(yīng)的行為價(jià)值函數(shù)酝碳，只能在其周圍震蕩矾踱，后文將講述改進(jìn)方法。

策略改進(jìn)：?-greedy策略進(jìn)行改進(jìn)

6疏哗、Action-Value Function Approximation

  • 近似action-value函數(shù)


  • 最小化近似作用值函數(shù)\widehat q(S,A,w)與真實(shí)作用值函數(shù)q(S,A)之間的均方誤差

  • 用隨機(jī)梯度下降方法找到局部最小值：


7呛讲、Linear Action-Value Function Approximation

  • 同樣我們介紹使用線性函數(shù)來(lái)近似狀態(tài)行為價(jià)值函數(shù)時(shí)的公式，狀態(tài)行為價(jià)值可以用特征向量表示：


  • 通過(guò)特征的線性組合表示作用值函數(shù)


  • 隨機(jī)梯度下降更新


8返奉、Incremental Control Algorithms

  • 與預(yù)測(cè)算法類似贝搁，我們找到真實(shí)行為價(jià)值的目標(biāo)值。
    • 對(duì)于MC算法芽偏，目標(biāo)值就是return G_t：

  • 對(duì)于TD(0)雷逆，目標(biāo)值就是TD目標(biāo)：


  • 對(duì)于前向認(rèn)識(shí)TD(λ)，目標(biāo)值是λ-return：


  • 對(duì)于后向認(rèn)識(shí)TD(λ)污尉，對(duì)應(yīng)的參數(shù)更新是：


（四）Mountain Car

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


小車爬山是一個(gè)經(jīng)典的強(qiáng)化學(xué)習(xí)示例。環(huán)境如圖左上角所示被碗，小車被困于山谷某宪，單靠小車自身的動(dòng)力是不足以在谷底由靜止一次性沖上右側(cè)目標(biāo)位置的，比較現(xiàn)時(shí)的策略是蛮放，當(dāng)小車加速上升到一定位置時(shí)缩抡，讓小車回落，同時(shí)反向加速包颁，使其加速?zèng)_向谷底，借助勢(shì)能向動(dòng)能的轉(zhuǎn)化沖上目標(biāo)位置⊙拐妫現(xiàn)在問(wèn)題是在模型位置的情況下娩嚼，如何用強(qiáng)化學(xué)習(xí)的方法找到小車沖上目標(biāo)位置的最優(yōu)策略。

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

最初的動(dòng)作是0，這是樂(lè)觀的（注意贵少，這個(gè)任務(wù)中所有的真實(shí)價(jià)值都是負(fù)數(shù)）呵俏，這使得即使試探參數(shù)\epsilon為0，也會(huì)引起廣泛的試探滔灶。這可以從圖的中間頂部為“step 428”的圖中可以看到普碎。盡管這時(shí)候一個(gè)episode都沒(méi)完成，但是車子在山谷里沿著狀態(tài)空間的弧形軌跡來(lái)回?cái)[動(dòng)录平。所有經(jīng)常訪問(wèn)的狀態(tài)的價(jià)值函數(shù)都比未試探到的狀態(tài)低麻车，這是因?yàn)閷?shí)際的收益比（不切實(shí)際的）預(yù)期的要差。這會(huì)不斷驅(qū)使智能體離開(kāi)其所在的地點(diǎn)斗这，去探索新的狀態(tài)动猬，直到找到最優(yōu)解決方案。

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


2赁咙、Study of \lambda Should We Bootstrap?

下圖顯示了幾種不同的任務(wù)，使用不同λ進(jìn)行的強(qiáng)化學(xué)習(xí)算法分析結(jié)果∈酰總的來(lái)說(shuō)λ=1的時(shí)候通常算法表現(xiàn)是很差的碎税，TD(0)是比MC好得多的方法，這說(shuō)明了Bootstrap的重要性猿涨；不同的任務(wù)對(duì)應(yīng)的最優(yōu)λ值是不太容易確定的。


五姆怪、Convergence（收斂）

1叛赚、預(yù)測(cè)算法的收斂性

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



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

從表中可以看出随闪，沒(méi)有函數(shù)近似時(shí)，各種算法都收斂骚勘；
線性函數(shù)近似時(shí)現(xiàn)時(shí)策略學(xué)習(xí)可以收斂铐伴，但離線策略時(shí)僅有MC收斂撮奏；
非線性函數(shù)近似時(shí)無(wú)論采用現(xiàn)時(shí)策略還是離線策略只有MC收斂。而MC算法在實(shí)際中是很少使用的当宴。這給強(qiáng)化學(xué)習(xí)的實(shí)際應(yīng)用帶來(lái)的挑戰(zhàn)畜吊。好在我們有一些改善TD算法的辦法。

2户矢、Gradient Temporal-Difference Learning

  • TD不遵循任何目標(biāo)函數(shù)的梯度
  • 這就是為什么當(dāng)off-policy或使用非線性函數(shù)逼近時(shí)TD可能會(huì)發(fā)散的原因

  • 我們可以通過(guò)修改TD算法使得它遵循Projected Bellman Error的梯度進(jìn)而收斂玲献。


3、Convergence of Control Algorithms

針對(duì)控制學(xué)習(xí)的算法逗嫡，其收斂性比較如下圖：



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

針對(duì)控制學(xué)習(xí)算法青自，大多數(shù)都能得到較好的策略，但是理論上只要存在函數(shù)近似驱证，就都不是嚴(yán)格收斂的延窜，比較常見(jiàn)的是在最優(yōu)策略上下震蕩，逐漸逼近然后突然來(lái)一次發(fā)散抹锄，再逐漸逼近等逆瑞。使用非線性函數(shù)近似的效果要比近似函數(shù)要差很多，實(shí)際也是如此伙单。

三获高、Batch Methods

（一）Batch Reinforcement Learning

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

前面所說(shuō)的遞增算法都是基于數(shù)據(jù)流的，經(jīng)歷一步吻育，更新算法后念秧，我們就不再使用這步的數(shù)據(jù)了，這種算法簡(jiǎn)單布疼，但有時(shí)候不夠高效摊趾。與之相反，批方法則是把一段時(shí)期內(nèi)的數(shù)據(jù)集中起來(lái)游两，通過(guò)學(xué)習(xí)來(lái)使得參數(shù)能較好地符合這段時(shí)期內(nèi)所有的數(shù)據(jù)砾层。這里的訓(xùn)練數(shù)據(jù)集“塊”相當(dāng)于個(gè)體的一段經(jīng)驗(yàn)。

（二）最小平方差預(yù)測(cè)

  • 假設(shè)存在一個(gè)價(jià)值函數(shù)的近似 \widehat v (s,w) \approx v_\pi(s)

  • 以及一段時(shí)期的贱案、包含<狀態(tài)肛炮、價(jià)值>的經(jīng)歷D：


  • 最小平方差算法要求找到參數(shù)w，使得下式值最斜ψ佟：v_t^\pi為目標(biāo)值

1侨糟、Stochastic Gradient Descent with Experience Replay

給出包含<state,value>對(duì)的經(jīng)驗(yàn)：



Repeat:

  1. Sample state, value from experience


  2. Apply stochastic gradient descent update



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


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

DQN使用experience replay和fixed Q-targets（再建立第二個(gè)神經(jīng)網(wǎng)絡(luò)肴沫，我們實(shí)際上是在用兩套神經(jīng)網(wǎng)絡(luò)運(yùn)行的粟害，因此也就是兩套完全不同的參數(shù)向量，我們一般會(huì)凍結(jié)老的神經(jīng)網(wǎng)絡(luò)颤芬，試圖存儲(chǔ)下所有看過(guò)的信息，之后我們就會(huì)用目標(biāo)對(duì)凍結(jié)的目標(biāo)一個(gè)引導(dǎo)輔助程序，我們并不是對(duì)新設(shè)立的目標(biāo)做輔助引導(dǎo)程序站蝠，這樣就能使得程序更加穩(wěn)定汰具。僅從字面意思上來(lái)看的話，我們對(duì)老的神經(jīng)網(wǎng)絡(luò)的幾千條信息進(jìn)行升級(jí)處理菱魔，逐步替換就能夠形成新的神經(jīng)網(wǎng)絡(luò)留荔。我們永遠(yuǎn)不會(huì)直接對(duì)目前的新目標(biāo)進(jìn)行輔助引導(dǎo)，因?yàn)槟鞘遣环€(wěn)定的澜倦。在你設(shè)立的目標(biāo)和你的實(shí)際價(jià)值之間是有一定聯(lián)系的聚蝶，這使得你的神經(jīng)網(wǎng)絡(luò)不受控制。）

  • 根據(jù)\epsilon-greedy策略產(chǎn)生行動(dòng)a_t
  • 將經(jīng)驗(yàn)以(s_t,a_t,r_{t+1},s_{t+1})的形式存儲(chǔ)到replay memery D
  • 從D中隨機(jī)抽樣一個(gè)mini-batch的經(jīng)驗(yàn)(s,a,r,s')
  • 用固定參數(shù)w^-計(jì)算Q-learning target藻治，維護(hù)兩個(gè)神經(jīng)網(wǎng)絡(luò)DQN1碘勉，DQN2,一個(gè)網(wǎng)絡(luò)固定參數(shù)專門(mén)用來(lái)產(chǎn)生目標(biāo)值，目標(biāo)值相當(dāng)于標(biāo)簽數(shù)據(jù)桩卵。另一個(gè)網(wǎng)絡(luò)專門(mén)用來(lái)評(píng)估策略验靡，更新參數(shù)。

  • 在Q-network 和 Q-learning targets之間優(yōu)化MSE


  • 使用隨機(jī)梯度下降的的方式更新參數(shù)雏节。

首先胜嗓，隨機(jī)采樣打破了狀態(tài)之間的聯(lián)系；第二個(gè)神經(jīng)網(wǎng)絡(luò)會(huì)暫時(shí)凍結(jié)參數(shù)钩乍，我們從凍結(jié)參數(shù)的網(wǎng)絡(luò)而不是從正在更新參數(shù)的網(wǎng)絡(luò)中獲取目標(biāo)值辞州，這樣增加了算法的穩(wěn)定性。經(jīng)過(guò)一次批計(jì)算后寥粹，把凍結(jié)參數(shù)的網(wǎng)絡(luò)換成更新的參數(shù)再次凍結(jié)產(chǎn)生新一次迭代時(shí)要用的目標(biāo)值变过。

3、DQN in Atari

  • 從像素s端到端學(xué)習(xí)值函數(shù)Q(s,a)
  • 輸入狀態(tài)s是最后4幀的原始像素堆棧
  • 輸出為Q(s,a)排作，用于18個(gè)操縱桿/按鈕位置

  • 獎(jiǎng)勵(lì)是該步驟的分?jǐn)?shù)變化



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

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

DQN Results in Atari

4罪针、 How much does DQN help?

用了一張表比較了在DQN中有沒(méi)有應(yīng)用固定參數(shù)彭羹、以及有沒(méi)有使用經(jīng)歷重現(xiàn)（批方法）兩個(gè)條件時(shí)在5款游戲中的表現(xiàn)，結(jié)果體現(xiàn)了這兩個(gè)條件聯(lián)合應(yīng)用的優(yōu)勢(shì)：


5泪酱、Linear Least Squares Prediction

通過(guò)比較發(fā)現(xiàn)使用批方法能夠找到最小平方差的解決方案派殷，提高算法的穩(wěn)定性还最，但是它需要多次迭代。我們可以設(shè)計(jì)一個(gè)價(jià)值函數(shù)的線性近似函數(shù)：


然后直接求解參數(shù)毡惜。求解思路是逆向思維拓轻，假設(shè)已經(jīng)找到這個(gè)參數(shù)，那么他應(yīng)該滿足最小LS(w)经伙，通過(guò)把LS展開(kāi)扶叉，可以直接得到w：

這種方法直接求解的時(shí)間復(fù)雜度是
使用Shermann-Morrison法求解復(fù)雜度是
n是特征數(shù)量，這意味著求解該問(wèn)題的難度與設(shè)計(jì)的特征數(shù)量多少有關(guān)帕膜，而與狀態(tài)空間大小無(wú)關(guān)枣氧，因此適合應(yīng)用與那些特征較少的問(wèn)題。

6垮刹、Linear Least Squares Prediction Algorithms

  • 我們不知道真正的value v_t^\pi
  • 實(shí)際上达吞，我們的“訓(xùn)練數(shù)據(jù)”必須使用 v_t^\pi的噪聲樣本或偏差樣本
  • 在每種情況下，直接求解MC / TD / TD(\lambda)的固定點(diǎn)

7危纫、Convergence of Linear Least Squares Prediction Algorithms

8宗挥、Least Squares Policy Iteration


策略評(píng)估使用 最小平方差Q學(xué)習(xí)
策略改善使用：Greedy 搜索策略

9、Least Squares Action-Value Function Approximation

  • 近似action-value 函數(shù)q_\pi(s,a)
  • 使用特征的線性組合x(s,a)
  • 最小化\widehat q(s,a,w)和q_\pi(s,a)之間的最小平方誤差
  • 使用policy \pi生成經(jīng)驗(yàn)

  • 包含<(state,action),value>對(duì)的


10种蝶、Least Squares Control

  • 對(duì)于策略評(píng)估契耿，我們希望有效利用所有經(jīng)驗(yàn)
  • 對(duì)于控制，我們也想改善政策
  • 這種經(jīng)驗(yàn)來(lái)自許多策略
  • 因此螃征，要評(píng)估q_\pi(s,a)搪桂，我們必須學(xué)習(xí)off-policy

  • 我們使用與Q學(xué)習(xí)相同的想法：


11、Least Squares Q-Learning

考慮以下線性Q學(xué)習(xí)更新


12盯滚、LSTDQ algorithm: solve for total update = zero

13踢械、Least Squares Policy Iteration Algorithm

  • 以下偽代碼使用LSTDQ進(jìn)行策略評(píng)估

  • 它反復(fù)評(píng)估不同策略的經(jīng)驗(yàn) D


14、Convergence of Control Algorithms

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末魄藕，一起剝皮案震驚了整個(gè)濱河市内列，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌背率，老刑警劉巖话瞧，帶你破解...
    沈念sama閱讀 218,036評(píng)論 6贊 506
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異寝姿，居然都是意外死亡交排，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,046評(píng)論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)饵筑，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)埃篓，“玉大人，你說(shuō)我怎么就攤上這事根资〖茏ǎ” “怎么了同窘？”我有些...
    開(kāi)封第一講書(shū)人閱讀 164,411評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)胶征。 經(jīng)常有香客問(wèn)我塞椎，道長(zhǎng)桨仿，這世上最難降的妖魔是什么睛低？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,622評(píng)論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮服傍，結(jié)果婚禮上钱雷，老公的妹妹穿的比我還像新娘。我一直安慰自己吹零，他們只是感情好罩抗，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,661評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著灿椅，像睡著了一般套蒂。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上茫蛹，一...
    開(kāi)封第一講書(shū)人閱讀 51,521評(píng)論 1贊 304
  • 城市分裂傳說(shuō)
    那天操刀，我揣著相機(jī)與錄音，去河邊找鬼婴洼。 笑死骨坑，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的柬采。 我是一名探鬼主播欢唾，決...
    沈念sama閱讀 40,288評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼粉捻！你這毒婦竟也來(lái)了礁遣？” 一聲冷哼從身側(cè)響起，我...
    開(kāi)封第一講書(shū)人閱讀 39,200評(píng)論 0贊 276
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤肩刃，失蹤者是張志新（化名）和其女友劉穎祟霍，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體树酪，經(jīng)...
    沈念sama閱讀 45,644評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡浅碾，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,837評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了续语。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片垂谢。...
    茶點(diǎn)故事閱讀 39,953評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖疮茄，靈堂內(nèi)的尸體忽然破棺而出滥朱，到底是詐尸還是另有隱情根暑，我是刑警寧澤，帶...
    沈念sama閱讀 35,673評(píng)論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布徙邻，位于F島的核電站排嫌，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏缰犁。R本人自食惡果不足惜淳地，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,281評(píng)論 3贊 329
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望帅容。 院中可真熱鬧颇象，春花似錦、人聲如沸并徘。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,889評(píng)論 0贊 22
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)麦乞。三九已至蕴茴，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間姐直，已是汗流浹背倦淀。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,011評(píng)論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留简肴，地道東北人晃听。 一個(gè)月前我還...
    沈念sama閱讀 48,119評(píng)論 3贊 370
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長(zhǎng)得像砰识，于是被迫代替她去往敵國(guó)和親能扒。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,901評(píng)論 2贊 355

推薦閱讀更多精彩內(nèi)容