增強(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前言 前言就目前來看，深度增強(qiáng)學(xué)習(xí)（Deep Reinforcement Learning)中的很多方法都是基于以前的增強(qiáng)學(xué)習(xí)算法，將其中的 value function 價值函數(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ù)備知識 預(yù)備知識對增強(qiáng)學(xué)習(xí)有所理解，知道 MDP，Bellman 方程詳細(xì)可見：Deep Reinforcement Learning 基礎(chǔ)知識

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

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

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

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

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

8、ning。該文對于 Atari 游戲的效果得到大幅提升。5 小結(jié) 小結(jié)Reinforcement Learning 有很多經(jīng)典算法， 很多算法都基于以上衍生。 鑒于篇幅問題， 下一個 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)用，原因在于依然是偏于理想化的兩個算法，需要知道狀態(tài)轉(zhuǎn)移概率，也需要遍歷所有的狀態(tài)。對于遍歷狀態(tài)這個事，我們當(dāng)然可以不用做到完全遍歷，而只需要盡可能的通過探索來遍及各種狀態(tài)即可。而對于狀態(tài)轉(zhuǎn)移概率，也就是依賴于模型 Model，這是比較困難的事情。什么是狀態(tài)轉(zhuǎn)移？就比如一顆子彈，如果我知道它

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

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

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