因為準(zhǔn)備投入學(xué)習(xí) CS294，具體見知乎專欄，復(fù)習(xí)了下之前學(xué)習(xí) Udacity 和 CS181 中有關(guān)強(qiáng)化學(xué)習(xí)部分的筆記和資料，再看了遍 David Silver 課程的 PPT，整理成了這篇文章。
馬爾可夫決策過程（Markov Decision Processes,MDPs）
MDPs 簡單說就是一個智能體（Agent）采取行動（Action）從而改變自己的狀態(tài)（State）獲得獎勵（Reward）與環(huán)境（Environment）發(fā)生交互的循環(huán)過程。
MDP 的策略完全取決于當(dāng)前狀態(tài)（Only present matters），這也是它馬爾可夫性質(zhì)的體現(xiàn)。
其可以簡單表示為：
基本概念
- : 有限狀態(tài) state 集合，s 表示某個特定狀態(tài)
- : 有限動作 action 集合，a 表示某個特定動作
- Transition Model : Transition Model, 根據(jù)當(dāng)前狀態(tài) s 和動作 a 預(yù)測下一個狀態(tài) s’，這里的 表示從 s 采取行動 a 轉(zhuǎn)移到 s’ 的概率
- Reward :表示 agent 采取某個動作后的即時獎勵，它還有 R(s, a, s’), R(s) 等表現(xiàn)形式，采用不同的形式，其意義略有不同
- Policy : 根據(jù)當(dāng)前 state 來產(chǎn)生 action，可表現(xiàn)為 或 ，后者表示某種狀態(tài)下執(zhí)行某個動作的概率
回報（Return）：
與 折扣率（discount）
: U 代表執(zhí)行一組 action 后所有狀態(tài)累計的 reward 之和，但由于直接的 reward 相加在無限時間序列中會導(dǎo)致無偏向，而且會產(chǎn)生狀態(tài)的無限循環(huán)。因此在這個 Utility 函數(shù)里引入 折扣率這一概念，令往后的狀態(tài)所反饋回來的 reward 乘上這個 discount 系數(shù)，這樣意味著當(dāng)下的 reward 比未來反饋的 reward 更重要，這也比較符合直覺。定義
由于我們引入了 discount，可以看到我們把一個無限長度的問題轉(zhuǎn)換成了一個擁有最大值上限的問題。
強(qiáng)化學(xué)習(xí)的目的是最大化長期未來獎勵，即尋找最大的 U。（注：回報也作 G 表示）
基于回報（return），我們再引入兩個函數(shù)
- 狀態(tài)價值函數(shù)： ，意義為基于 t 時刻的狀態(tài) s 能獲得的未來回報（return）的期望，加入動作選擇策略后可表示為 ( )
- 動作價值函數(shù)： ，意義為基于 t 時刻的狀態(tài) s，選擇一個 action 后能獲得的未來回報（return）的期望
價值函數(shù)用來衡量某一狀態(tài)或動作-狀態(tài)的優(yōu)劣，即對智能體來說是否值得選擇某一狀態(tài)或在某一狀態(tài)下執(zhí)行某一動作。
MDP 求解
我們需要找到最優(yōu)的策略使未來回報最大化，求解過程大致可分為兩步,具體內(nèi)容會在后面展開
- 預(yù)測： 給定策略，評估相應(yīng)的狀態(tài)價值函數(shù)和狀態(tài)-動作價值函數(shù)
- 行動： 根據(jù)價值函數(shù)得到當(dāng)前狀態(tài)對應(yīng)的最優(yōu)動作
Bellman 期望方程
Bellman 方程的分析
為了更加了解方程中期望的具體形式，可以見下圖，第一層的空心圓代表當(dāng)前狀態(tài)（state），向下連接的實心圓代表當(dāng)前狀態(tài)可以執(zhí)行兩個動作，第三層代表執(zhí)行完某個動作后可能到達(dá)的狀態(tài) s’。
根據(jù)上圖得出公式：
其中，
上式中策略 是指給定狀態(tài) s 的情況下，動作 a 的概率分布，即
我們將概率和轉(zhuǎn)換為期望，上式等價于：
同理，我們可以得到動作價值函數(shù)的方程如下：
如上圖，Bellman 方程也可以表達(dá)成矩陣形式：
，可直接求出
；其復(fù)雜度為
，一般可通過動態(tài)規(guī)劃、蒙特卡洛估計與 Temporal-Difference learning 求解。
狀態(tài)價值函數(shù)和動作價值函數(shù)的關(guān)系
最優(yōu)方程
最優(yōu)價值函數(shù)（optimal state-value function）
其意義為所有策略下價值函數(shù)的最大值
Bellman最優(yōu)方程
- v 描述了處于一個狀態(tài)的長期最優(yōu)化價值，即在這個狀態(tài)下考慮到所有可能發(fā)生的后續(xù)動作，并且都挑選最優(yōu)的動作來執(zhí)行的情況下，這個狀態(tài)的價值
- q 描述了處于一個狀態(tài)并執(zhí)行某個動作后所帶來的長期最優(yōu)價值，即在這個狀態(tài)下執(zhí)行某一特定動作后，考慮再之后所有可能處于的狀態(tài)并且在這些狀態(tài)下總是選取最優(yōu)動作來執(zhí)行所帶來的長期價值
最優(yōu)策略（Optimal Policy）
關(guān)于收斂性：（對策略定義一個偏序）
定理：
對于任意 MDP：
- 總是存在一個最優(yōu)策略 ，它比其它任何策略都要好，或者至少一樣好
- 所有最優(yōu)決策都達(dá)到最優(yōu)值函數(shù)，
- 所有最優(yōu)決策都達(dá)到最優(yōu)行動值函數(shù)，
最優(yōu)策略可從最優(yōu)狀態(tài)價值函數(shù)或者最優(yōu)動作價值函數(shù)得出：
求解 Bellman 最優(yōu)方程
通過解 Bellman 最優(yōu)性方程找一個最優(yōu)策略需要以下條件:
- 動態(tài)模型已知
- 擁有足夠的計算空間和時間
- 系統(tǒng)滿足 Markov 特性
所以我們一般采用近似的辦法，很多強(qiáng)化學(xué)習(xí)方法一般也是研究如何近似求解 Bellman 方程，一般有下面幾種（后文會做具體講解）：
- Value Iteration
- Policy Iteration
- Q-learning
- Sarsa
MDPs 還有下面幾種擴(kuò)展形式：
- Infinite and continuous MDPs
- Partially observable MDPs
- Undiscounted, average reward MDPs
動態(tài)規(guī)劃求解 MDPs 的 Planning
動態(tài)規(guī)劃是一種通過把復(fù)雜問題劃分為子問題，并對自問題進(jìn)行求解，最后把子問題的解結(jié)合起來解決原問題的方法。「動態(tài)」是指問題由一系列的狀態(tài)組成，而且狀態(tài)能一步步地改變，「規(guī)劃」即優(yōu)化每一個子問題。因為MDP 的 Markov 特性，即某一時刻的子問題僅僅取決于上一時刻的子問題的 action，并且 Bellman 方程可以遞歸地切分子問題，所以我們可以采用動態(tài)規(guī)劃來求解 Bellman 方程。
MDP 的問題主要分兩類
- Prediction 問題
- 輸入：MDP 和策略（policy）
- 輸出：狀態(tài)價值函數(shù)
- Control 問題
- 輸入：MDP
- 輸出：最優(yōu)狀態(tài)價值函數(shù) 和最優(yōu)策略
解決也是分兩種，見下文
Policy Iteration
步驟：
- Iterative Policy Evaluation:
- 基于當(dāng)前的 Policy 計算出每個狀態(tài)的 Value function
- 同步更新：每次迭代更新所有的狀態(tài)的 v
- 矩陣形式：
- 左邊是第 k 次迭代每個 state 上狀態(tài)價值函數(shù)的值，右邊是通過貪心（greedy）算法找到策略
- 計算實例：
- k=2, -1.7 = -1.0 + 2 x (1/3) x (-1)
- k=3, -2.9 = -1.7 x (1/3) + 2 x (1/3) x (-2.0)
- Policy Improvement
- 基于當(dāng)前的狀態(tài)價值函數(shù)（value function），用貪心算法找到最優(yōu)策略
- 會一直迭代到收斂，具體證明如圖:
- 擴(kuò)展
- 事實上在大多數(shù)情況下 Policy evaluation 不必要非常逼近最優(yōu)值，這時我們通常引入 函數(shù)來控制迭代停止
- 很多情況下價值函數(shù)還未完全收斂，Policy 就已經(jīng)最優(yōu)，所以在每次迭代之后都可以更新策略（Policy），當(dāng)策略無變化時停止迭代
Value Iteration
- 最優(yōu)化原理：當(dāng)且僅當(dāng)狀態(tài) s 達(dá)到任意能到達(dá)的狀態(tài) s‘ 時，價值函數(shù) v 能在當(dāng)前策略（policy）下達(dá)到最優(yōu)，即 ，與此同時，狀態(tài) s 也能基于當(dāng)前策略達(dá)到最優(yōu)，即
- 狀態(tài)轉(zhuǎn)移公式為：
- 矩陣形式為：
- 下面是一個實例，求每個格子到終點的最短距離，走一步的 reward 是 -1:
同步動態(tài)規(guī)劃算法小結(jié)
- 迭代策略評估（Iterative Policy Evaluation）解決的是 Prediction 問題，使用了貝爾曼期望方程（Bellman Expectation Equation）
- 策略迭代（Policy Iteration）解決的是 Control 問題，實質(zhì)是在迭代策略評估之后加一個選擇 Policy 的過程，使用的是貝爾曼期望方程和貪心算法
- 價值迭代（Value Iteration） 解決的是 Control 問題，它并沒有直接計算策略（Policy），而是在得到最優(yōu)的基于策略的價值函數(shù)之后推導(dǎo)出最優(yōu)的 Policy，使用的是貝爾曼最優(yōu)化方程（Bellman Optimality Equation）
還有關(guān)于 Model-Free, Value Function Approximation, Policy Gradient 等等一堆內(nèi)容明天再弄。。。。
參考資料：
- 優(yōu)達(dá)學(xué)城（Udacity）納米學(xué)位增強(qiáng)學(xué)習(xí)部分
- Reinforcement Learning By David Silver
- UC Berkeley CS188 Intro to AI -- Course Materials
