因?yàn)闇?zhǔn)備投入學(xué)習(xí) CS294，具體見知乎專欄，復(fù)習(xí)了下之前學(xué)習(xí) Udacity 和 CS181 中有關(guān)強(qiáng)化學(xué)習(xí)部分的筆記和資料，再看了遍 David Silver 課程的 PPT，整理成了這篇文章。

馬爾可夫決策過(guò)程（Markov Decision Processes,MDPs）

MDPs 簡(jiǎn)單說(shuō)就是一個(gè)智能體（Agent）采取行動(dòng)（Action）從而改變自己的狀態(tài)（State）獲得獎(jiǎng)勵(lì)（Reward）與環(huán)境（Environment）發(fā)生交互的循環(huán)過(guò)程。

MDP 的策略完全取決于當(dāng)前狀態(tài)（Only present matters），這也是它馬爾可夫性質(zhì)的體現(xiàn)。

其可以簡(jiǎn)單表示為：

基本概念

1. : 有限狀態(tài) state 集合，s 表示某個(gè)特定狀態(tài)
2. : 有限動(dòng)作 action 集合，a 表示某個(gè)特定動(dòng)作
3. Transition Model : Transition Model, 根據(jù)當(dāng)前狀態(tài) s 和動(dòng)作 a 預(yù)測(cè)下一個(gè)狀態(tài) s’，這里的 表示從 s 采取行動(dòng) a 轉(zhuǎn)移到 s’ 的概率
4. Reward :表示 agent 采取某個(gè)動(dòng)作后的即時(shí)獎(jiǎng)勵(lì)，它還有 R(s, a, s’), R(s) 等表現(xiàn)形式，采用不同的形式，其意義略有不同
5. Policy : 根據(jù)當(dāng)前 state 來(lái)產(chǎn)生 action，可表現(xiàn)為 或 ，后者表示某種狀態(tài)下執(zhí)行某個(gè)動(dòng)作的概率

回報(bào)（Return）：

與 折扣率（discount） : U 代表執(zhí)行一組 action 后所有狀態(tài)累計(jì)的 reward 之和，但由于直接的 reward 相加在無(wú)限時(shí)間序列中會(huì)導(dǎo)致無(wú)偏向，而且會(huì)產(chǎn)生狀態(tài)的無(wú)限循環(huán)。因此在這個(gè) Utility 函數(shù)里引入 折扣率這一概念，令往后的狀態(tài)所反饋回來(lái)的 reward 乘上這個(gè) discount 系數(shù)，這樣意味著當(dāng)下的 reward 比未來(lái)反饋的 reward 更重要，這也比較符合直覺。定義

由于我們引入了 discount，可以看到我們把一個(gè)無(wú)限長(zhǎng)度的問(wèn)題轉(zhuǎn)換成了一個(gè)擁有最大值上限的問(wèn)題。

強(qiáng)化學(xué)習(xí)的目的是最大化長(zhǎng)期未來(lái)獎(jiǎng)勵(lì)，即尋找最大的 U。（注：回報(bào)也作 G 表示）

基于回報(bào)（return），我們?cè)僖雰蓚€(gè)函數(shù)

• 狀態(tài)價(jià)值函數(shù)： ，意義為基于 t 時(shí)刻的狀態(tài) s 能獲得的未來(lái)回報(bào)（return）的期望，加入動(dòng)作選擇策略后可表示為 ( )
• 動(dòng)作價(jià)值函數(shù)： ，意義為基于 t 時(shí)刻的狀態(tài) s，選擇一個(gè) action 后能獲得的未來(lái)回報(bào)（return）的期望

價(jià)值函數(shù)用來(lái)衡量某一狀態(tài)或動(dòng)作-狀態(tài)的優(yōu)劣，即對(duì)智能體來(lái)說(shuō)是否值得選擇某一狀態(tài)或在某一狀態(tài)下執(zhí)行某一動(dòng)作。

MDP 求解

我們需要找到最優(yōu)的策略使未來(lái)回報(bào)最大化，求解過(guò)程大致可分為兩步,具體內(nèi)容會(huì)在后面展開

1. 預(yù)測(cè)： 給定策略，評(píng)估相應(yīng)的狀態(tài)價(jià)值函數(shù)和狀態(tài)-動(dòng)作價(jià)值函數(shù)
2. 行動(dòng)： 根據(jù)價(jià)值函數(shù)得到當(dāng)前狀態(tài)對(duì)應(yīng)的最優(yōu)動(dòng)作

Bellman 期望方程

Bellman 方程的分析

為了更加了解方程中期望的具體形式，可以見下圖，第一層的空心圓代表當(dāng)前狀態(tài)（state），向下連接的實(shí)心圓代表當(dāng)前狀態(tài)可以執(zhí)行兩個(gè)動(dòng)作，第三層代表執(zhí)行完某個(gè)動(dòng)作后可能到達(dá)的狀態(tài) s’。

根據(jù)上圖得出公式：

其中，

上式中策略 是指給定狀態(tài) s 的情況下，動(dòng)作 a 的概率分布，即

我們將概率和轉(zhuǎn)換為期望，上式等價(jià)于：

同理，我們可以得到動(dòng)作價(jià)值函數(shù)的方程如下：

，一般可通過(guò)動(dòng)態(tài)規(guī)劃、蒙特卡洛估計(jì)與 Temporal-Difference learning 求解。

狀態(tài)價(jià)值函數(shù)和動(dòng)作價(jià)值函數(shù)的關(guān)系

最優(yōu)方程

最優(yōu)價(jià)值函數(shù)（optimal state-value function）

其意義為所有策略下價(jià)值函數(shù)的最大值

Bellman最優(yōu)方程

• v 描述了處于一個(gè)狀態(tài)的長(zhǎng)期最優(yōu)化價(jià)值，即在這個(gè)狀態(tài)下考慮到所有可能發(fā)生的后續(xù)動(dòng)作，并且都挑選最優(yōu)的動(dòng)作來(lái)執(zhí)行的情況下，這個(gè)狀態(tài)的價(jià)值
• q 描述了處于一個(gè)狀態(tài)并執(zhí)行某個(gè)動(dòng)作后所帶來(lái)的長(zhǎng)期最優(yōu)價(jià)值，即在這個(gè)狀態(tài)下執(zhí)行某一特定動(dòng)作后，考慮再之后所有可能處于的狀態(tài)并且在這些狀態(tài)下總是選取最優(yōu)動(dòng)作來(lái)執(zhí)行所帶來(lái)的長(zhǎng)期價(jià)值

最優(yōu)策略（Optimal Policy）

關(guān)于收斂性：（對(duì)策略定義一個(gè)偏序）

定理：

對(duì)于任意 MDP：

• 總是存在一個(gè)最優(yōu)策略 ，它比其它任何策略都要好，或者至少一樣好
• 所有最優(yōu)決策都達(dá)到最優(yōu)值函數(shù)，
• 所有最優(yōu)決策都達(dá)到最優(yōu)行動(dòng)值函數(shù)，

最優(yōu)策略可從最優(yōu)狀態(tài)價(jià)值函數(shù)或者最優(yōu)動(dòng)作價(jià)值函數(shù)得出：

求解 Bellman 最優(yōu)方程

通過(guò)解 Bellman 最優(yōu)性方程找一個(gè)最優(yōu)策略需要以下條件:

• 動(dòng)態(tài)模型已知
• 擁有足夠的計(jì)算空間和時(shí)間
• 系統(tǒng)滿足 Markov 特性

所以我們一般采用近似的辦法，很多強(qiáng)化學(xué)習(xí)方法一般也是研究如何近似求解 Bellman 方程，一般有下面幾種（后文會(huì)做具體講解）：

• Value Iteration
• Policy Iteration
• Q-learning
• Sarsa

MDPs 還有下面幾種擴(kuò)展形式：

• Infinite and continuous MDPs
• Partially observable MDPs
• Undiscounted, average reward MDPs

動(dòng)態(tài)規(guī)劃求解 MDPs 的 Planning

動(dòng)態(tài)規(guī)劃是一種通過(guò)把復(fù)雜問(wèn)題劃分為子問(wèn)題，并對(duì)自問(wèn)題進(jìn)行求解，最后把子問(wèn)題的解結(jié)合起來(lái)解決原問(wèn)題的方法?！竸?dòng)態(tài)」是指問(wèn)題由一系列的狀態(tài)組成，而且狀態(tài)能一步步地改變，「規(guī)劃」即優(yōu)化每一個(gè)子問(wèn)題。因?yàn)镸DP 的 Markov 特性，即某一時(shí)刻的子問(wèn)題僅僅取決于上一時(shí)刻的子問(wèn)題的 action，并且 Bellman 方程可以遞歸地切分子問(wèn)題，所以我們可以采用動(dòng)態(tài)規(guī)劃來(lái)求解 Bellman 方程。

MDP 的問(wèn)題主要分兩類

• Prediction 問(wèn)題
• 輸入：MDP 和策略（policy）
• 輸出：狀態(tài)價(jià)值函數(shù)
• Control 問(wèn)題
• 輸入：MDP
• 輸出：最優(yōu)狀態(tài)價(jià)值函數(shù) 和最優(yōu)策略

解決也是分兩種，見下文

Policy Iteration

步驟：

• Iterative Policy Evaluation:
• 基于當(dāng)前的 Policy 計(jì)算出每個(gè)狀態(tài)的 Value function
• 同步更新：每次迭代更新所有的狀態(tài)的 v

• 矩陣形式：

• 左邊是第 k 次迭代每個(gè) state 上狀態(tài)價(jià)值函數(shù)的值，右邊是通過(guò)貪心（greedy）算法找到策略
• 計(jì)算實(shí)例：
• 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)價(jià)值函數(shù)（value function），用貪心算法找到最優(yōu)策略

• 會(huì)一直迭代到收斂，具體證明如圖:

• 擴(kuò)展
• 事實(shí)上在大多數(shù)情況下 Policy evaluation 不必要非常逼近最優(yōu)值，這時(shí)我們通常引入 函數(shù)來(lái)控制迭代停止
• 很多情況下價(jià)值函數(shù)還未完全收斂，Policy 就已經(jīng)最優(yōu)，所以在每次迭代之后都可以更新策略（Policy），當(dāng)策略無(wú)變化時(shí)停止迭代

Value Iteration

• 最優(yōu)化原理：當(dāng)且僅當(dāng)狀態(tài) s 達(dá)到任意能到達(dá)的狀態(tài) s‘ 時(shí)，價(jià)值函數(shù) v 能在當(dāng)前策略（policy）下達(dá)到最優(yōu)，即 ，與此同時(shí)，狀態(tài) s 也能基于當(dāng)前策略達(dá)到最優(yōu)，即
• 狀態(tài)轉(zhuǎn)移公式為：
• 矩陣形式為：
• 下面是一個(gè)實(shí)例，求每個(gè)格子到終點(diǎn)的最短距離，走一步的 reward 是 -1:
  

同步動(dòng)態(tài)規(guī)劃算法小結(jié)

1. 迭代策略評(píng)估（Iterative Policy Evaluation）解決的是 Prediction 問(wèn)題，使用了貝爾曼期望方程（Bellman Expectation Equation）
2. 策略迭代（Policy Iteration）解決的是 Control 問(wèn)題，實(shí)質(zhì)是在迭代策略評(píng)估之后加一個(gè)選擇 Policy 的過(guò)程，使用的是貝爾曼期望方程和貪心算法
3. 價(jià)值迭代（Value Iteration） 解決的是 Control 問(wèn)題，它并沒(méi)有直接計(jì)算策略（Policy），而是在得到最優(yōu)的基于策略的價(jià)值函數(shù)之后推導(dǎo)出最優(yōu)的 Policy，使用的是貝爾曼最優(yōu)化方程（Bellman Optimality Equation）

還有關(guān)于 Model-Free, Value Function Approximation, Policy Gradient 等等一堆內(nèi)容明天再弄。。。。

參考資料：

1. 優(yōu)達(dá)學(xué)城（Udacity）納米學(xué)位增強(qiáng)學(xué)習(xí)部分
2. Reinforcement Learning By David Silver
3. UC Berkeley CS188 Intro to AI -- Course Materials