增強(qiáng)學(xué)習(xí)reinforcementlearning經(jīng)典算法梳理

1、增強(qiáng)學(xué)習(xí) 增強(qiáng)學(xué)習(xí) Reinforcement Learning Reinforcement Learning 經(jīng)典算法梳理 經(jīng)典算法梳理 1：policy and value iteration policy and value iteration前言 前言就目前來(lái)看，深度增強(qiáng)學(xué)習(xí)（Deep Reinforcement Learning)中的很多方法都是基于以前的增強(qiáng)學(xué)習(xí)算法，將其中的 value function 價(jià)值函數(shù)或者 Po

2、licy function 策略函數(shù)用深度神經(jīng)網(wǎng)絡(luò)替代而實(shí)現(xiàn)。因此，本文嘗試總結(jié)增強(qiáng)學(xué)習(xí)中的經(jīng)典算法。本文主要參考：1Reinforcement Learning: An Introduction；2Reinforcement Learning Course by David Silver1 預(yù)備知識(shí) 預(yù)備知識(shí)對(duì)增強(qiáng)學(xué)習(xí)有所理解，知道 MDP，Bellman 方程詳細(xì)可見(jiàn)：Deep Reinforcement Learning 基礎(chǔ)知識(shí)

3、（DQN 方面）很多算法都是基于求解 Bellman 方程而形成：Value IterationPolicy IterationQ-LearningSARSA2 Policy Iteration 2 Policy Iteration 策略迭代 策略迭代Policy Iteration 的目的是通過(guò)迭代計(jì)算 value function 價(jià)值函數(shù)的方式來(lái)使 policy 收斂到最優(yōu)。Policy Iteration 本質(zhì)上就是直接使用 B

4、ellman 方程而得到的：那么 Policy Iteration 一般分成兩步：Policy Evaluation 策略評(píng)估。目的是更新 Value FunctionPolicy Improvement 策略改進(jìn)。使用 greedy policy 產(chǎn)生新的樣本用于第一步的策略評(píng)估。本質(zhì)上就是使用當(dāng)前策略產(chǎn)生新的樣本，然后使用新的樣本更新當(dāng)前的策略，然后不斷反復(fù)。理論可以證明最終策略將收斂到最優(yōu)。具體算法：那么問(wèn)題來(lái)了：Policy I

5、teration 和 Value Iteration 有什么本質(zhì)區(qū)別？為什么一個(gè)叫 policy iteration，一個(gè)叫 value iteration 呢？原因其實(shí)很好理解，policy iteration 使用 bellman 方程來(lái)更新 value，最后收斂的 value 即 vπ 是當(dāng)前 policy 下的value 值（所以叫做對(duì) policy 進(jìn)行評(píng)估），目的是為了后面的 policy improvement 得到新的

6、policy。而 value iteration 是使用 bellman 最優(yōu)方程來(lái)更新 value，最后收斂得到的 value 即 v 就是當(dāng)前 state 狀態(tài)下的最優(yōu)的 value 值。因此，只要最后收斂，那么最優(yōu)的 policy 也就得到的。因此這個(gè)方法是基于更新 value 的，所以叫value iteration。從上面的分析看，value iteration 較之 policy iteration 更直接。不過(guò)問(wèn)題也都是一

7、樣，需要知道狀態(tài)轉(zhuǎn)移函數(shù)p才能計(jì)算。 本質(zhì)上依賴于模型， 而且理想條件下需要遍歷所有的狀態(tài)， 這在稍微復(fù)雜一點(diǎn)的問(wèn)題上就基本不可能了。4 異步更新問(wèn)題 異步更新問(wèn)題那么上面的算法的核心是更新每個(gè)狀態(tài)的 value 值。 那么可以通過(guò)運(yùn)行多個(gè)實(shí)例同時(shí)采集樣本來(lái)實(shí)現(xiàn)異步更新。而基于異步更新的思想， DeepMind 出了一篇不錯(cuò)的 paper： Asynchronous Methods for Deep Reinforcement Lear

8、ning。該文對(duì)于 Atari 游戲的效果得到大幅提升。5 小結(jié) 小結(jié)Reinforcement Learning 有很多經(jīng)典算法， 很多算法都基于以上衍生。 鑒于篇幅問(wèn)題， 下一個(gè) blog 再分析基于蒙特卡洛的算法。增強(qiáng)學(xué)習(xí) 增強(qiáng)學(xué)習(xí) Reinforcement Learning Reinforcement Learning 經(jīng)典算法梳理 經(jīng)典算法梳理 2：蒙特卡洛方法 ：蒙特卡洛方法1 前言 前言在上一篇文章中， 我們介紹了基于

9、Bellman 方程而得到的 Policy Iteration 和 Value Iteration 兩種基本的算法， 但是這兩種算法實(shí)際上很難直接應(yīng)用，原因在于依然是偏于理想化的兩個(gè)算法，需要知道狀態(tài)轉(zhuǎn)移概率，也需要遍歷所有的狀態(tài)。對(duì)于遍歷狀態(tài)這個(gè)事，我們當(dāng)然可以不用做到完全遍歷，而只需要盡可能的通過(guò)探索來(lái)遍及各種狀態(tài)即可。而對(duì)于狀態(tài)轉(zhuǎn)移概率，也就是依賴于模型 Model，這是比較困難的事情。什么是狀態(tài)轉(zhuǎn)移？就比如一顆子彈，如果我知道它

10、的運(yùn)動(dòng)速度，運(yùn)動(dòng)的當(dāng)前位置，空氣阻力等等，我就可以用牛頓運(yùn)動(dòng)定律來(lái)描述它的運(yùn)動(dòng)，進(jìn)而知道子彈下一個(gè)時(shí)刻會(huì)大概在哪個(gè)位置出現(xiàn)。那么這個(gè)基于牛頓運(yùn)動(dòng)定律來(lái)描述其運(yùn)動(dòng)就是一個(gè)模型 Model，我們也就可以知道其狀態(tài)（空間位置，速度）的變化概率。那么基本上所以的增強(qiáng)學(xué)習(xí)問(wèn)題都需要有一定的模型的先驗(yàn)知識(shí)， 至少根據(jù)先驗(yàn)知識(shí)我們可以來(lái)確定需要多少輸入可以導(dǎo)致多少輸出。比如說(shuō)玩 Atari 這個(gè)游戲，如果輸入只有屏幕的一半，那么我們知道不管算法多么好

11、，也無(wú)法訓(xùn)練出來(lái)。因?yàn)檩斎氡幌拗屏?，而且即使是人類也是做不到的。但是以此同時(shí)，人類是無(wú)需精確的知道具體的模型應(yīng)該是怎樣的，人類可以完全根據(jù)觀察來(lái)推算出相應(yīng)的結(jié)果。所以，對(duì)于增強(qiáng)學(xué)習(xí)的問(wèn)題，或者說(shuō)對(duì)于任意的決策與控制問(wèn)題。輸入輸出是由基本的模型或者說(shuō)先驗(yàn)知識(shí)決定的，而具體的模型則可以不用考慮。所以，為了更好的求解增強(qiáng)學(xué)習(xí)問(wèn)題，我們更關(guān)注Model Free 的做法。簡(jiǎn)單的講就是如果完全不知道狀態(tài)轉(zhuǎn)移概率（就像人類一樣），我們?cè)撊绾吻蟮米顑?yōu)

12、的策略呢？本文介紹蒙特卡洛方法。2 蒙特卡洛方法 蒙特卡洛方法蒙特卡洛方法只面向具有階段 episode 的問(wèn)題。比如玩一局游戲，下一盤棋，是有步驟，會(huì)結(jié)束的。而有些問(wèn)題則不一定有結(jié)束，比如開(kāi)賽車，可以無(wú)限的開(kāi)下去，或者說(shuō)需要特別特別久才能結(jié)束。能不能結(jié)束是一個(gè)關(guān)鍵。因?yàn)橹灰芙Y(jié)束，那么每一步的 reward 都是可以確定的，也就是可以因此來(lái)計(jì)算 value。比如說(shuō)下棋，最后贏了就是贏了，輸了就是輸了。而對(duì)于結(jié)束不了的問(wèn)題，我們只能對(duì)于