區(qū)分Continuing Task和Episodic Task
前一節(jié)我們已經(jīng)解釋了什么是episode，episode即為從初始的狀態(tài)到終止?fàn)顟B(tài)的整個(gè)過程。那么什么是Continuing Task？ 什么是Episodic Task呢？其實(shí)，兩者最根本的區(qū)別就是Continuing Task是無法確認(rèn)最終的終止?fàn)顟B(tài)，其動(dòng)作狀態(tài)會(huì)一直發(fā)生下去的即為Continuing Task。與此相反，Episodic Task是擁有有限長度的狀態(tài)，也就是知道最終的結(jié)束狀態(tài)。
強(qiáng)化學(xué)習(xí)分類
強(qiáng)化學(xué)習(xí)基本上可以分為兩大類。第一類是有模型的強(qiáng)化學(xué)習(xí)，另一類為無模型的強(qiáng)化學(xué)習(xí)。模型可以簡單地理解為transition-state probability。而動(dòng)態(tài)規(guī)劃(Dynamic Programming)就是一個(gè)基于有模型的強(qiáng)化學(xué)習(xí)方法。分類圖如下所示：
動(dòng)態(tài)規(guī)劃(Dynamic Programming)
根據(jù)前面推導(dǎo)出來的Value Functions的表達(dá)公式，我們可以看出當(dāng)前狀態(tài)的值可以通過接下來的狀態(tài)值計(jì)算出來。但是，這兩個(gè)狀態(tài)的值函數(shù)我們都不知道。因此，該算法也被稱為自舉(bootstrapping)。接下來我們先看看動(dòng)態(tài)規(guī)劃方法如何對policy來進(jìn)行評估的。
策略評估(Policy Evaluation)
如何來評估策略的好壞呢？這時(shí)候我們需要從數(shù)學(xué)的角度出發(fā)，也就是要通過數(shù)值的方式來對策略進(jìn)行評估。數(shù)值大代表策略好，數(shù)值小代表策略不是很好，我們很容易就會(huì)想到Value Functions。
根據(jù)Bellman Equation我們得到state value的計(jì)算公式如下：
于是，我們就可以通過一次次的迭代來得到該policy的state value了。其偽代碼如下：
從偽代碼中，我們可以知道Policy Evaluation是對一個(gè)Policy進(jìn)行計(jì)算的。當(dāng)我們更新的state value值幾乎不變時(shí)，就可以讓其停止迭代了。
列1:?我們有一個(gè)Gridworld的游戲，其中有2個(gè)終點(diǎn)，1-14數(shù)字分別代表14個(gè)不同的狀態(tài)(state)，我們可以朝四個(gè)方向走(上下左右)，也就是代表了我們的動(dòng)作(action)，每一次狀態(tài)的改變都會(huì)得到-1的獎(jiǎng)勵(lì)。游戲如下圖所示：
通過Iterative Policy Evaluation方法進(jìn)行迭代，我們得到前兩次迭代的state value矩陣。如下所示：
我們來看一下k=2時(shí)，-1.7是怎么計(jì)算出來的。因?yàn)槲覀兛梢圆扇?個(gè)動(dòng)作，所以每個(gè)動(dòng)作的概率都為0.25, 而在狀態(tài)1的位置上，其可以向左、向右、向下和原地不動(dòng)。因此，其state value就等于(0.0 * 0.25) + (-1 * 0.25) + (-1 * 0.25) + (-1 * 0.25) = -1.75，四舍五入即為-1.7。
策略提升(Policy Improvement)
我們進(jìn)行策略評估的目的就是為了找到最優(yōu)的策略。還是拿列1來舉例，當(dāng)k=2時(shí)，我們已經(jīng)計(jì)算出了各個(gè)狀態(tài)下的state value，比如我們在狀態(tài)2的情況下，為了轉(zhuǎn)換到更好的狀態(tài)，我們就朝四個(gè)方向觀察一番，發(fā)現(xiàn)通過向左走可以得到更多(-1.7 > -2.0)的獎(jiǎng)勵(lì)，于是我們便采取向左的動(dòng)作，使?fàn)顟B(tài)轉(zhuǎn)換到了狀態(tài)1。這就是策略提升。
通過例子，我們可以知道我們在狀態(tài)不好的情況下采取相應(yīng)行動(dòng)轉(zhuǎn)換到比較好的狀態(tài)的值(也就是action value)一定會(huì)大于當(dāng)前狀態(tài)不好的值(state value)。通過公式推導(dǎo)，我們只需要選擇state value值大的地方執(zhí)行策略即可。公式推導(dǎo)如下：
因此，我們可以使用貪婪策略(greedy policy)，也就是取其最大值，來得出最優(yōu)的策略(在當(dāng)前狀態(tài)下應(yīng)該采取的動(dòng)作)和最優(yōu)的state value。公式如下所示：
策略迭代(Policy Iteration)
策略迭代就是結(jié)合了策略評估和策略提升，通過一次次的迭代來得到最優(yōu)的策略。如圖：
其中E表示進(jìn)行一次Policy Evaluation，I表示進(jìn)行一次Policy Improvement，*表示最優(yōu)解，0-n表示進(jìn)行了多少次迭代。偽代碼如下所示：
值迭代(Value Iteration)
根據(jù)策略迭代算法，每一次迭代都要進(jìn)行策略評估和策略提升，直到二者都收斂?？晌覀兊哪繕?biāo)是選出最優(yōu)的策略，那么有沒有可能在策略評估值沒有收斂的情況下，最優(yōu)策略已經(jīng)收斂了呢？答案是有這個(gè)可能。我們還拿例1來看，迭代步驟如下所示：
可以看出當(dāng)?shù)谌螘r(shí)，policy已經(jīng)收斂了，因此無需再對其做策略評估。值迭代過程就是運(yùn)用了這一點(diǎn)的原理，使用縮減過的策略評估在每次迭代中，都會(huì)求最大的policy值，直到其策略收斂。其公式，偽代碼如下：
GridWorld 部分代碼
Reference
1. Reinforcement Learning An Introduction
2.強(qiáng)化學(xué)習(xí)入門 第二講 基于模型的動(dòng)態(tài)規(guī)劃方法?https://zhuanlan.zhihu.com/p/25580624
3.Github: Reinforcement Learning An Introduction?https://github.com/ShangtongZhang/reinforcement-learning-an-introduction
