增強學習reinforcementlearning經典算法梳理

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

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

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

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

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

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

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

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

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

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

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

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