Reinforcement Learning An Introduction 讀書筆記

第一章表格法

首先颤霎，為什么叫做Tabular Solution蛤虐，實際上党饮，翻譯作表格，不算和恰當驳庭，它應(yīng)該是一種存儲過去（包括state刑顺，action，reward等內(nèi)容）的方式饲常，在這一章里蹲堂，比較常用的存儲容器，list就用來存儲這些內(nèi)容不皆。此外贯城，在做關(guān)于策略的估計，更新迭代的時候霹娄，基本沒有使用到什么復(fù)雜函數(shù)能犯，這也是它叫做表格法的原因，沒什么技術(shù)犬耻，就是列表格踩晶，找極值而已。

第二節(jié) 多臂賭博機 Multi-arm bandits

這一節(jié)的關(guān)鍵詞應(yīng)該是 Evaluative
評估是強化學(xué)習(xí)里面非常重要的概念枕磁，評估的對象渡蜻，是做出的決策行動。為什么要評估這些過去做出的選擇呢计济？因為這相當于一種反饋茸苇，而反饋，就是實現(xiàn)自動控制的基礎(chǔ)沦寂⊙埽可以說，就是這些對于狀態(tài)传藏，行為做出的評估腻暮，為后續(xù)的行為提供了有效的指導(dǎo)，使得目標能更快更好的達到毯侦。

多臂賭博機的抽象模型：
你持續(xù)不斷的面臨 $k$ 種選擇哭靖，每選擇一次，將獲得依選擇而異的一個獎勵值侈离。你的目標是在有限的次數(shù)（例如1000次）之內(nèi)试幽，得到最多的獎勵。

探索還是剝削霍狰？
什么是剝削（Exploit）和探索（Explore）的矛盾抡草？如果一味剝削饰及，使用從前的實驗帶來的成果，就不能發(fā)現(xiàn)新的康震，沒有遇到過的更好的行為燎含，而如果一味探索，就像沒頭蒼蠅胡亂選擇腿短，則會帶來獎勵（reward）不高的后果屏箍。
這組矛盾是強化學(xué)習(xí)里非常重要的一組矛盾，后面也提出了一些辦法來平衡它們橘忱。
這里作者提出的觀點是：
是選擇探索還是剝削赴魁，取決于對價值估計的準確性，不確定性钝诚，以及后續(xù)剩下的步數(shù)颖御。

有節(jié)制的貪心算法
采樣平均（sample-average）方法計算一個行為的價值：
${Q_t}(a) = \frac{{\sum\nolimits_{i = 1}^{t - 1} {{R_i} \times {1_{{A_i} = a}}} }}{{\sum\nolimits_{i = 1}^{i - 1} {{1_{{A_i} = a}}} }}$
即 $t$ 時刻之前采取這個行為獲得的平均獎勵數(shù)（平均每次得到多少獎勵）
使用貪心算法選擇行為：
${A_t} = \arg {\max _a}{Q_t}(a)$

而進一步的， $\varepsilon - greedy$ 方法凝颇，以 $\varepsilon$ 的概率任意選擇行為潘拱， $1 - \varepsilon$ 的概率選擇貪心行為，加入了一些探索拧略，而非一味剝削芦岂，在后期，往往能取得更好的reward垫蛆。

探索性行為往往在后期表現(xiàn)更好

樂觀的初始值
樂觀的初始值也能在初期帶來更多的探索行為禽最，從而使后期有更好的表現(xiàn)。

樂觀初始值帶來的好處

第三節(jié) MDP 有限馬爾科夫決策過程

這一章關(guān)鍵詞即標題：馬爾科夫決策過程
可以說強化學(xué)習(xí)的目的袱饭，就是對于一個馬爾科夫決策過程川无，找到最優(yōu)策略，即每一步采取什么行動虑乖，使得過程結(jié)束后舀透，能取得最多的回報。（Reinforcement learning is about learning from interaction how to behave in order to achieve a goal.）因此决左，需要搞清楚什么是馬爾科夫決策過程，它包含一些什么內(nèi)容走贪，有什么特性等等問題佛猛。
agent(智能體)：做決策的主體，agent內(nèi)部的一切都是已知坠狡，可控的继找。
environment（環(huán)境）：除了agent以外的，未知不能控的部分逃沿。
policy（策略）：action=f(state)婴渡，policy 表示的就是這種對應(yīng)關(guān)系幻锁。agent做出的決策就依賴這種隨機的對應(yīng)關(guān)系。
action（行為）:agent做出的選擇边臼。
state（狀態(tài)）:選擇的基礎(chǔ)哄尔。通常是從環(huán)境中觀測到的內(nèi)容，有時候也叫（observation）
reward（獎勵）:評估選擇的基礎(chǔ)柠并，通常是執(zhí)行一個action得到的一個數(shù)值岭接。
return（回報）:將來能獲得的總獎勵的函數(shù)，表示的是包含后期在內(nèi)的綜合情況臼予。

馬爾可夫決策過程中的個體 - 環(huán)境交互

馬爾科夫性：如果一個環(huán)境的狀態(tài)可以完整的總結(jié)過去鸣戴，并且不降低預(yù)測未來的能力，就稱之滿足馬爾科夫性粘拾。換一種說法窄锅，如果一個環(huán)境未來的狀態(tài)僅僅取決于當前時刻的狀態(tài)，而不取決于過去做過什么缰雇，就是具有馬爾科夫性入偷。既往不咎，當下決定未來寓涨。
這里多提一句盯串，狀態(tài)應(yīng)該怎么表達，選擇哪些變量也是有講究的戒良，我們應(yīng)該在選擇狀態(tài)表達的時候体捏，盡可能的使之滿足馬爾科夫特性。不過這門學(xué)問糯崎，不在本書的討論范疇几缭。
擁有有限個數(shù)的狀態(tài)和行為（state&action）的MDP稱之為有限馬爾科夫決策過程。

第四節(jié) 動態(tài)規(guī)劃 Dynamic Programming

動態(tài)規(guī)劃指的是給定一個環(huán)境的完整模型的前提下沃呢，計算得到最優(yōu)策略的一系列算法年栓。通過前面概念的鋪墊，這里開始進入算法的層面薄霜，遵循循序漸進的原則某抓，首先介紹的就是算法上最完備，最直覺的惰瓜，完全掌握環(huán)境特性的情況否副。
這一章里面，非常重要而且貫穿后面章節(jié)的兩個概念是策略評估和策略提升，從控制的角度來說，就是一個反饋-控制的過程腔寡。
策略評估
評估的對象是一個policy绅项，而評估的結(jié)果曲尸，其實應(yīng)該是一個表格赋续，表格里包含了不同的state對應(yīng)的價值，這么一套對應(yīng)關(guān)系另患，就是基于策略 $\pi$ 的policy value ${V_\pi }$
${V_\pi }(s)$ 的計算纽乱，遵循以下公式：
$\begin{array}{l} {V_\pi }(s) = {E_\pi }[{G_t}|{S_t} = s]\\ = {E_\pi }[{R_{t + 1}} + \gamma {G_{t + 1}}|{S_t} = s]\\ = {E_\pi }[{R_{t + 1}} + \gamma {V_\pi }({S_{t + 1}})|{S_t} = s]\\ = \sum\limits_a {\pi (a|s)\sum\limits_{s',r} {p'(s',r|s,a)[r + \gamma {V_\pi }(s')]} } \end{array}$
（格式有點不好調(diào)，后面有時間再修修）

這個想法就是說柴淘，在當前系統(tǒng)狀態(tài)是 $s$ 的情況下迫淹，后續(xù)直到過程結(jié)束，獲得的回報的期望为严。因為環(huán)境是完全已知的敛熬，即狀態(tài)轉(zhuǎn)移概率 $p(s',r|a,s)$ 都是已知的， $\pi (a|s)$ 由策略 $\pi$ 決定第股，也是已知的应民，所以，我們可以準確的求到后續(xù)能得到的回報的期望夕吻，用更文學(xué)的表達的話诲锹，應(yīng)該是這個狀態(tài)包含的潛力。

怎么把這個公式落實到方法上來呢涉馅？對于比較小型的問題归园，狀態(tài)和行為數(shù)量都是有限的，硬算也可以稚矿，但是問題要是比較復(fù)雜庸诱，狀態(tài)空間維數(shù)較高，硬算就行不通了晤揣。所以桥爽，書里推出了一個以貝爾曼公式作為迭代準則的迭代的方法，步驟上比較簡單昧识，也能在一定的條件下收斂到真實值钠四。
貝爾曼公式如下：
$\begin{array}{l} {V_{k + 1}}(s) = E[{R_{t + 1}} + \gamma {V_k}({s_{t + 1}})|{S_t} = s]\\ = \sum\limits_a {\pi (a|s)\sum\limits_{s',r} {p(s,r|s,a)[r + \gamma {V_k}(s)]} } \end{array}$
步驟如下圖：

迭代的策略評估方法

策略提升
首先，需要計算state-action value：
$\begin{array}{l} {q_\pi }(s,a) = E[{R_{t + 1}} + \gamma {V_\pi }({S_{t + 1}})|{S_t} = s,{A_t} = a]\\ = \sum\limits_{s',r} {p(s',r|s,a)[r + \gamma {V_\pi }(s')]} \end{array}$
這里 ${V_\pi }(s')$ 就是前面策略評估得到的結(jié)果跪楞，前面的系數(shù)來自環(huán)境模型缀去。
接著，策略更新準則由下面的公式作為準則：
$\pi '(s) = \arg {\max _a}{q_\pi }(s,a)$
實際上甸祭，就是圍繞價值的貪心算法朵耕。這樣一次迭代能把所有state對應(yīng)的action都更新一遍。
補充一句淋叶， $\pi$ 是一種策略，一種state與action的對應(yīng)關(guān)系，反應(yīng)到數(shù)據(jù)結(jié)構(gòu)上來說煞檩，就是一種2行n列的表格处嫌，n是state的數(shù)量。所以一次更新就是把整個表都刷新一遍斟湃。

策略迭代
綜合前面的兩部分熏迹，策略迭代描述的是一種整體交替更新的過程和方法。如圖所示：

策略迭代

E-策略評估凝赛，I-策略提升

廣義策略迭代GPI
我們用GPI來代指策略評估和策略提升交替進行的一般概念注暗，而不依賴兩個過程的粒度和其他細節(jié)。幾乎所有強化學(xué)習(xí)方法都可以被描述為GPI墓猎。

GPI

當評估過程和提升過程都穩(wěn)定捆昏，即更新后和更新前的差別小到一定程度，就可以推斷價值函數(shù)和策略達到最優(yōu)了毙沾。

交替的過程

這個圖揭示了策略評估和策略提升兩者的關(guān)系骗卜，策略評估使得向真實的價值靠攏的同時，使得策略遠離了最好的貪心策略左胞，策略提升使策略向貪心策略靠攏的同時寇仓，使策略的價值，遠離了它的真實價值烤宙。當真實的價值和貪心算法交匯到一處的時候遍烦，就達到的最好的狀態(tài)：價值是準確的價值，策略是貪心（收獲最多）的策略

第五節(jié) 蒙特卡洛（MC）方法

將上一節(jié)的問題進一步復(fù)雜化：沒有完整的環(huán)境模型了躺枕，狀態(tài)轉(zhuǎn)移率沒有了服猪，怎么辦？
概率論里有一個東西叫大數(shù)定律屯远，粗略來說蔓姚，這個定律揭示的內(nèi)容就是：當采樣數(shù)量足夠多，就能夠足夠逼近一個分布
我們不能知道環(huán)境的具體模型慨丐，但通過采樣,來逼近狀態(tài)轉(zhuǎn)移率坡脐。舉個例子，以policy $\pi$ 做了一輪（one episode）實驗房揭，得到一個state-action-reward的序列备闲。那么，對于序列中出現(xiàn)過的state捅暴，可以用 ${G_t} = \sum\limits_{i = t}^T {{\gamma ^{i - t}}{r_i}}$ 表示恬砂。其中 $t$ 是該狀態(tài)第一次出現(xiàn)的時刻，T是該輪結(jié)束的時刻（也可以是每一次出現(xiàn)的時刻蓬痒，方法上有細微的差別泻骤，想法和結(jié)果其實是一樣的）。實驗的次數(shù)足夠多，就能夠足夠逼近 ${V_\pi }$

我們以采樣取平均代替策略評估狱掂，但依然有問題演痒。沒有狀態(tài)轉(zhuǎn)移率，state-action value的無法計算的趋惨。怎么辦呢鸟顺？直接對state-action value做采樣代替state value采樣，就可以解決了器虾。

策略提升方面讯嫂，與DP沒有什么顯著的差別。其余的技術(shù)細節(jié)這里限于篇幅不再細說兆沙，還有一個關(guān)于Importance Sampling 的部分欧芽，用到的地方不僅限于MC方法，它是一個使用非常廣泛的off-policy技巧挤悉，后續(xù)會寫一個關(guān)于off-policy的專題渐裸。

第六章時序差分（Temporal-Difference Learning）

MC問題將沒有模型的問題已經(jīng)基本得到解決了，但是装悲，MC方法有諸如大量的存儲消耗昏鹃，更新較慢，方差大的問題诀诊，TD問題有效的解決了這些問題洞渤，相當于MC的一個進化版。
$V({S_t}) \leftarrow V({S_t}) + \alpha [{R_{t + 1}} + \gamma V({S_{t + 1}}) - V({S_t})]$
這是TD方法的核心公式属瓣。無模型（model-free）和自舉（bootstrap）是TD方法的兩個重要特性载迄。自舉，書中給出的解釋是：update estimate based in part on other learned estimates, without waiting for a final outcome.給一個文學(xué)的解釋的話抡蛙，就是道生一护昧，一生二，二生三粗截，三生萬物惋耙，有點夸張，大體上應(yīng)該就是這么個意思熊昌。用后續(xù)state的價值估計绽榛，作為前一個state價值估計的一部分。
這樣做的好處是顯而易見的婿屹，價值的更新更快了灭美，計算，存儲需求更小了昂利，數(shù)據(jù)的方差也變小了届腐。
Sarsa,Q-learning,Expected Sarsa都是基于TD的方法铁坎，限于篇幅，只放核心公式在這里犁苏。

Sarsa
$Q({S_t},{A_t}) \leftarrow Q({S_t},{A_t}) + \alpha [{R_{t + 1}} + \gamma Q({S_{t + 1}},{A_{t + 1}}) - Q({S_t},{A_t})]$
Q-learning
$Q({S_t},{A_t}) \leftarrow Q({S_t},{A_t}) + \alpha [{R_{t + 1}} + \gamma {\max _a}Q({S_{t + 1}},a) - Q({S_t},{A_t})]$
Expected Sarsa
$Q({S_t},{A_t}) \leftarrow Q({S_t},{A_t}) + \alpha [{R_{t + 1}} + \gamma \sum\limits_a {\pi (a|{S_{t + 1}})} Q({S_{t + 1}},a) - Q({S_t},{A_t})]$

第七章多步自舉 Multi-Step Bootstrapping

多步自舉就是介于MC和TD的一種方法厢呵，可以說MC和TD分別是MB方法的兩種極端。TD方法的限制在于傀顾，單布必須更新，更新的頻率是不能控制的碌奉，MB方法就解決了這個問題短曾。自舉在有重要，可辨識的狀態(tài)變更的一段時間里赐劣，有最好的效果嫉拐。（bootstrapping works best if it is over a length of time in which a significant and recognizable state change has occurred.）

$\begin{array}{l} {G_t}^{(1)} = {R_{t + 1}} + \gamma {V_t}({S_{t + 1}})\\ {G_t}^{(2)} = {R_{t + 1}} + \gamma {R_{t + 1}} + {\gamma ^2}{V_t}({S_{t + 2}})\\ {G_t}^{(n)} = {R_{t + 1}} + \gamma {R_{t + 1}} + ... + {\gamma ^{n - 1}}{R_{t + n}} + {\gamma ^n}{V_{t + n - 1}}({S_{t + n}}) \end{array}$
迭代規(guī)則如下：
${V_{t + n}}({S_t}) = {V_{t + n - 1}}({S_t}) + \alpha [{G_t}^{(n)} - {V_{t + n - 1}}({S_t})],0 \le t < T$

從TD到MC方法的備份頻譜圖

這個圖很清晰的揭示了這三種方法的區(qū)別和聯(lián)系。白色○代表序列中的state魁兼，黑色·代表序列中的action婉徘。

到這里，表格法里核心的內(nèi)容差不多就都寫到了咐汞「呛簦總的來說，書里的這些內(nèi)容化撕，算是一個強化學(xué)習(xí)比較“規(guī)整的入門”几晤，是閱讀其他論文，了解其他方法的基礎(chǔ)植阴。這里打一個不是很恰當?shù)谋确叫否腴T內(nèi)容，與論文掠手，新式方法的關(guān)系憾朴，就像“道”和“術(shù)”的關(guān)系，術(shù)是從道里面生出來的喷鸽，所以众雷，理解這個“道”，對于術(shù)的理解和學(xué)習(xí)魁衙，是非常非常重要的报腔。另外，閱讀英文專業(yè)書的體驗剖淀，由一開始的生澀艱難纯蛾，到后來的流暢舒適，一步步的纵隔，我感受到了行業(yè)大牛對于“道”的深刻理解翻诉，也領(lǐng)略到了書中簡練炮姨，精確文字表達的魅力。這次的閱讀是一把鑰匙碰煌，打開一扇英文專業(yè)書閱讀的大門舒岸，總而言之，獲益匪淺芦圾。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末蛾派，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子个少，更是在濱河造成了極大的恐慌洪乍，老刑警劉巖，帶你破解...
沈念sama閱讀 211,265評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件夜焦，死亡現(xiàn)場離奇詭異壳澳，居然都是意外死亡，警方通過查閱死者的電腦和手機茫经，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,078評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門巷波，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人卸伞，你說我怎么就攤上這事抹镊。” “怎么了瞪慧？”我有些...
開封第一講書人閱讀 156,852評論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵髓考，是天一觀的道長。經(jīng)常有香客問我弃酌，道長氨菇，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,408評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任妓湘，我火速辦了婚禮查蓉，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘榜贴。我一直安慰自己豌研，他們只是感情好，可當我...
茶點故事閱讀 65,445評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布唬党。她就那樣靜靜地躺著鹃共，像睡著了一般。火紅的嫁衣襯著肌膚如雪驶拱。梳的紋絲不亂的頭發(fā)上霜浴，一...
開封第一講書人閱讀 49,772評論 1贊 290
城市分裂傳說
那天，我揣著相機與錄音蓝纲，去河邊找鬼阴孟。笑死晌纫，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的永丝。我是一名探鬼主播锹漱，決...
沈念sama閱讀 38,921評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼慕嚷！你這毒婦竟也來了哥牍？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,688評論 0贊 266
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤喝检，失蹤者是張志新（化名）和其女友劉穎砂心，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蛇耀，經(jīng)...
沈念sama閱讀 44,130評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,467評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年坎弯，在試婚紗的時候發(fā)現(xiàn)自己被綠了纺涤。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,617評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡抠忘，死狀恐怖撩炊，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情崎脉，我是刑警寧澤拧咳，帶...
沈念sama閱讀 34,276評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站囚灼，受9級特大地震影響骆膝，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜灶体，卻給世界環(huán)境...
茶點故事閱讀 39,882評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一阅签、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧蝎抽，春花似錦政钟、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,740評論 0贊 21
一樁弒父案养交，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至瓢宦，卻和暖如春碎连，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背刁笙。一陣腳步聲響...
開封第一講書人閱讀 31,967評論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工破花，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留谦趣，地道東北人。一個月前我還...
沈念sama閱讀 46,315評論 2贊 360
代替公主和親
正文我出身青樓座每，卻偏偏與公主長得像前鹅，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子峭梳，可洞房花燭夜當晚...
茶點故事閱讀 43,486評論 2贊 348

Reinforcement Learning An Introduction 讀書筆記

第一章 表格法