自機(jī)器學(xué)習(xí)重新火起來，深度強(qiáng)化學(xué)習(xí)就一直是科研的一大熱點(diǎn)，也是最有可能實(shí)現(xiàn)通用人工智能的一個(gè)分支。然而對(duì)于沒有強(qiáng)化學(xué)習(xí)基礎(chǔ)的同學(xué)們，如果直接去學(xué)習(xí)深度強(qiáng)化學(xué)習(xí)，想必會(huì)碰到很多問題。本文嘗試普及一些最基礎(chǔ)的強(qiáng)化學(xué)習(xí)算法，并以一個(gè)小例子來輔助大家理解。
問題定義
強(qiáng)化學(xué)習(xí)究竟研究的是一個(gè)什么樣的問題，讓其具有實(shí)現(xiàn)通用人工智能的潛力？
這個(gè)問題與我們認(rèn)識(shí)世界的方式相關(guān)。我們都知道這個(gè)世界時(shí)刻在變化著，而每件事物的變化，勢(shì)必是由其他一系列事物導(dǎo)致的。這就是我們所普遍認(rèn)識(shí)的世界，一個(gè)由因果律定義的世界。由于因果律的存在，我們就有可能根據(jù)某個(gè)當(dāng)前世界的狀態(tài)，計(jì)算后一時(shí)刻世界的狀態(tài)。
而我們?nèi)祟悾鳛橐粋€(gè)智能體，通過觀察這個(gè)世界，并進(jìn)行各種各樣的自主行動(dòng)，在這個(gè)世界中生存，并對(duì)其產(chǎn)生影響。通用人工智能的實(shí)現(xiàn)，就是期望能通過計(jì)算機(jī)模擬人類這樣的智能體進(jìn)行各種各樣的行動(dòng)決策。
為了簡(jiǎn)化問題，我們可以像下面這樣建模這個(gè)世界和智能體。我們可以認(rèn)為在某一個(gè)時(shí)刻整個(gè)世界處于狀態(tài)S1，當(dāng)智能體進(jìn)行了某一個(gè)行動(dòng)之后，這個(gè)世界的狀態(tài)變化為了S2。智能體之所以能夠做出這一行動(dòng)，是因?yàn)槠湫闹杏幸粋€(gè)目標(biāo)，并且從這個(gè)世界中得到了一定的反饋。
舉個(gè)例子。比如我們想要喝水（目標(biāo)），身邊有一個(gè)杯子和一個(gè)飲水機(jī)（狀態(tài)S1），我們會(huì)觀察杯子和飲水機(jī)的位置，再伸手去拿取杯子（行動(dòng)），然后將杯子靠近（反饋）飲水機(jī)，到達(dá)飲水機(jī)出水位置之后（狀態(tài)S2），飲水機(jī)開始出水，之后我們?cè)賹⒈优e到嘴邊就能喝到水了。
這個(gè)簡(jiǎn)單的模型可以圖示如下：
智能體（Agent）通過觀察這個(gè)世界（Environment）的狀態(tài)（State: s），經(jīng)過智能決策，開展了一些行動(dòng)（Actions: a），這些行動(dòng)進(jìn)而引起了這個(gè)世界的狀態(tài)變化。智能體從這些變化的狀態(tài)中獲得關(guān)于之前行動(dòng)的反饋（Reward: r），從而指導(dǎo)后續(xù)的行動(dòng)決策。就這樣，整個(gè)世界周而復(fù)始的一直循環(huán)下去。
從這個(gè)模型出發(fā)，由于因果律的存在，是不是知道了S1這個(gè)初始狀態(tài)及智能體做出的行動(dòng)A之后，我們就可以直接計(jì)算下一狀態(tài)S2了呢？理論是可行的，但實(shí)際情況要更復(fù)雜一些，因?yàn)闋顟B(tài)實(shí)在太多太多了，我們通常無法直接建模所有的狀態(tài)。這時(shí)，我們可以用統(tǒng)計(jì)學(xué)的方式來解決這個(gè)問題。我們可以認(rèn)為在我們做出某一行動(dòng)之后，這個(gè)世界的狀態(tài)只是有一定概率會(huì)轉(zhuǎn)換為S2，同時(shí)也有一定的概率會(huì)轉(zhuǎn)換為S2_1等等。這樣就算我們建模的狀態(tài)不全，也可以相對(duì)較好的描述這個(gè)系統(tǒng)。
引入統(tǒng)計(jì)學(xué)的思維，也就引入了不確定性，雖然如此，但是卻帶來了更合理的描述系統(tǒng)的方式和系統(tǒng)層面的確定性。
以上描述的這一模型，在強(qiáng)化學(xué)習(xí)的世界里，我們稱作Markov決策過程，簡(jiǎn)稱MDP（Markov Decision Process）。這里面的不確定性也就是Markov特性。
有了這個(gè)模型之后，我們就可以從數(shù)學(xué)上來研究這個(gè)問題了。強(qiáng)化學(xué)習(xí)研究的正是如何在這樣的一個(gè)數(shù)學(xué)模型的基礎(chǔ)上去實(shí)現(xiàn)一個(gè)有效的算法，進(jìn)而實(shí)現(xiàn)智能決策。
一個(gè)小例子
我們可以設(shè)計(jì)一個(gè)簡(jiǎn)單的小游戲來輔助解決這個(gè)問題。
如上圖，機(jī)器人（智能體）可以在這樣的網(wǎng)格中移動(dòng)：
- 綠色格子代表機(jī)器人可以移動(dòng)到的位置
- 灰色格子表示有障礙物，機(jī)器人不能移動(dòng)到那個(gè)位置
- 紅色格子表示一個(gè)陷阱，如果機(jī)器人移動(dòng)到此，游戲失敗
- 黃色格子代表一個(gè)出口，如果機(jī)器人移動(dòng)到此，游戲成功
這個(gè)游戲中的MDP，可以描述為如下：
- 系統(tǒng)狀態(tài)：格子位置，機(jī)器人位置
- 機(jī)器人可執(zhí)行的動(dòng)作：向上下左右四個(gè)方向移動(dòng)
- 狀態(tài)轉(zhuǎn)換概率：如果機(jī)器人向某個(gè)方向移動(dòng)，它移動(dòng)到對(duì)應(yīng)方向的格子的概率假設(shè)為0.7（如果無法移動(dòng)到對(duì)應(yīng)方向的位置，則留在原格子的概率為0.7），移動(dòng)到其他位置的概率為0.3/n，n為其他可轉(zhuǎn)換到的狀態(tài)的數(shù)量。
狀態(tài)轉(zhuǎn)換概率舉例如下（假設(shè)我們對(duì)格子進(jìn)行編碼，編碼方式與excel表格的編碼方式一致，從A1到E3）：
- 假設(shè)機(jī)器人在位置A2，如果其向上移動(dòng)，有70%的概率會(huì)移動(dòng)到A1，分別有15%的概率會(huì)移動(dòng)到A2（留在原位）和A3
- 假設(shè)機(jī)器人在位置A2，如果其向左或向右移動(dòng)，有70%的的概率會(huì)留在原位A2，分別有15%的概率會(huì)移動(dòng)到A1和A3
我們的算法要解決的問題是，在任意綠色格子里面放置一個(gè)機(jī)器人，算法可以指導(dǎo)機(jī)器人一步一步到達(dá)位置E1（成功完成游戲）。
方案與算法
為了實(shí)現(xiàn)一個(gè)智能算法解決上述機(jī)器人走格子問題，我們可以考慮給每個(gè)格子定義一個(gè)價(jià)值。這個(gè)價(jià)值表示到達(dá)這個(gè)格子后有多大可能性能成功完成游戲。
觀察這個(gè)游戲可以發(fā)現(xiàn)，D1的價(jià)值應(yīng)該高于C1，C1的價(jià)值應(yīng)該高于B1。
如果可以計(jì)算出每個(gè)格子的價(jià)值，我們是不是就解決了這個(gè)問題了呢？因?yàn)?，無論機(jī)器人處于哪個(gè)位置，它只需要往價(jià)值比當(dāng)前格子更高的格子方向走即可。
現(xiàn)在問題轉(zhuǎn)化為如何定義和計(jì)算這個(gè)價(jià)值。
我們先將目標(biāo)數(shù)值化。由于到達(dá)出口格子即成功，如果機(jī)器人能到達(dá)此處，我們就給智能體反饋獎(jiǎng)勵(lì)1。同理，如果到達(dá)陷進(jìn)格子，反饋獎(jiǎng)勵(lì)-1，到達(dá)綠色格子則獎(jiǎng)勵(lì)0。
這個(gè)時(shí)候我們來看格子D1。如果機(jī)器人在此處，它可以往四個(gè)方向移動(dòng)。如果右移，有70%的概率可以到達(dá)出口，獲得獎(jiǎng)勵(lì)1。如果往其他三個(gè)方向走，則分別有10%的概率會(huì)到達(dá)出口，獲得獎(jiǎng)勵(lì)1。
經(jīng)過以上的分析可以發(fā)現(xiàn)，我們其實(shí)可以將概率與獎(jiǎng)勵(lì)相乘來代表某個(gè)移動(dòng)方向的價(jià)值。得到如下的價(jià)值數(shù)值：
- 向右移動(dòng)：0.7 * 1 = 0.7
- 向上/下/左移動(dòng)：0.1 * 1 = 0.1
這里的數(shù)值我們可以定義為動(dòng)作價(jià)值。有了這個(gè)動(dòng)作價(jià)值，要計(jì)算某個(gè)格子的價(jià)值，我們其實(shí)可以直接用最大的動(dòng)作價(jià)值來表示，即：max([0.7, 0.1, 0.1, 0.1]) = 0.7。
如果要計(jì)算格子C1的價(jià)值呢？這時(shí)，雖然達(dá)到格子D1的獎(jiǎng)勵(lì)為0，但是我們可以利用剛計(jì)算好的D1的價(jià)值。還是按照前面的方式進(jìn)行計(jì)算：
- 向右移動(dòng)：0.7 * (0 + 0.7) = 0.49
- 向上/下/左移動(dòng)：0.1 * (0 + 0.7) = 0.07
- 格子價(jià)值：max([0.49, 0.07, 0.07, 0.07]) = 0.49
到這里，一個(gè)簡(jiǎn)單的算法呼之欲出。我們只需要找到所有有獎(jiǎng)勵(lì)的位置，然后從那里開始去計(jì)算其他所有位置的獎(jiǎng)勵(lì)，好像這個(gè)問題就解決了。
實(shí)際情況會(huì)稍微復(fù)雜一些。因?yàn)槲覀兛赡苡泻芏鄠€(gè)位置都存在獎(jiǎng)勵(lì)，而且這些獎(jiǎng)勵(lì)的多少可能由于任務(wù)定義而不一樣。這里更實(shí)際一些的算法是利用多次迭代來實(shí)現(xiàn)。
為了不失一般性，我們可以定義公式：
（表示每個(gè)動(dòng)作的價(jià)值，其中：s表示當(dāng)前狀態(tài)；a表示動(dòng)作；s'表示下一個(gè)狀態(tài)；T(s, a, s')表示在狀態(tài)s，執(zhí)行動(dòng)作a轉(zhuǎn)換到狀態(tài)s'的概率；R(s, a, s')表示表示在狀態(tài)s，執(zhí)行動(dòng)作a轉(zhuǎn)換到狀態(tài)s'得到的獎(jiǎng)勵(lì)）
（表示每個(gè)格子的價(jià)值，其中：s表示當(dāng)前狀態(tài)，a表示動(dòng)作）
一般而言，我們會(huì)引入一個(gè)額外的γ參數(shù)，對(duì)下一個(gè)狀態(tài)的價(jià)值打一定的折扣，這是因?yàn)楫?dāng)前獲得的獎(jiǎng)勵(lì)一般會(huì)優(yōu)于下一個(gè)狀態(tài)的價(jià)值的，畢竟下一個(gè)狀態(tài)的價(jià)值只是一個(gè)估計(jì)值。這時(shí)，上述第一個(gè)公式變?yōu)椋?/p>
于是，我們的算法就可以描述為：
- 對(duì)每一個(gè)狀態(tài)，初始化 V := 0
- 循環(huán)，直到V收斂：
- 對(duì)每一個(gè)狀態(tài)，
這里為判斷V是否收斂，我們可以檢查當(dāng)前這次迭代是否會(huì)更新V的值。
用javascript代碼實(shí)現(xiàn)，主要代碼如下：
MDPVISolver.solve = function () {
var values = m.zeroArray([this.states.length]);
var valuesNew = values;
var iterations = 0;
do {
var qValuesAll = [];
values = valuesNew;
valuesNew = [];
for (var i = 0; i < this.states.length; i++) {
var state = this.states[i];
var qValues = this.qValues(values, state);
qValuesAll.push(qValues);
var value = this.value(qValues);
valuesNew.push(value);
}
console.log('finished iteration ' + (++iterations));
// console.log('values: ', values);
} while(!this.converged(values, valuesNew));
...
}
這里我已經(jīng)實(shí)現(xiàn)了上述的游戲的一個(gè)Demo，見這里，完整代碼見這里865行到890行。
上述算法就是強(qiáng)化學(xué)習(xí)里面的經(jīng)典算法 價(jià)值迭代 算法了。而我們上面定義V的迭代形式的公式就是著名的 Bellman 公式了，其最初由 Richard Bellman 提出。
另一個(gè)思路
上述算法存在一個(gè)問題，我們最后得到的是一系列狀態(tài)價(jià)值（每個(gè)格子的價(jià)值），為了得到我們想要的行動(dòng)，我們還需要根據(jù)根據(jù)狀態(tài)價(jià)值，計(jì)算行動(dòng)價(jià)值，即上述Q(s, a)。使用上有所不便。
那么有沒有辦法改進(jìn)呢？再來思考一下這個(gè)問題的目標(biāo)，實(shí)際上我們想要找到一種指導(dǎo)機(jī)器人行動(dòng)的策略。這里的策略可以表示為：在任意一個(gè)位置，算法可以給出一個(gè)恰當(dāng)?shù)男袆?dòng)。
我們能不能直接去衡量某一個(gè)策略的價(jià)值呢？因?yàn)橐坏┯辛诉@個(gè)策略的價(jià)值，我們就可以考慮直接去優(yōu)化這個(gè)策略，而不是去對(duì)所有的狀態(tài)計(jì)算價(jià)值。
對(duì)于某一策略，由于其可以基于當(dāng)前狀態(tài)指導(dǎo)我們作出行動(dòng)，我們可以定義它為一個(gè) 輸入為狀態(tài) 輸出為行動(dòng) 的函數(shù)，即π: a = π(s)
既然這樣，參考價(jià)值迭代算法中的狀態(tài)價(jià)值（格子價(jià)值）定義，我們可以定義策略價(jià)值函數(shù)為：
（策略π的價(jià)值，其中：s表示當(dāng)前狀態(tài)；a = π(s)表示動(dòng)作；s'表示下一個(gè)狀態(tài)；T(s, π(s), s')表示在狀態(tài)s，執(zhí)行動(dòng)作a=π(s)轉(zhuǎn)換到狀態(tài)s'的概率；R(s, π(s), s')表示在狀態(tài)s，執(zhí)行動(dòng)作a=π(s)轉(zhuǎn)換到狀態(tài)s'得到的獎(jiǎng)勵(lì)）
上面的公式是一個(gè)迭代形式的定義，既然如此，我們可以參考之前的狀態(tài)價(jià)值迭代算法，迭代計(jì)算這個(gè)策略的價(jià)值，最后這個(gè)價(jià)值可能會(huì)收斂到某個(gè)具體的值。
然而就算可以計(jì)算策略的價(jià)值，我們?nèi)绾蔚玫揭粋€(gè)有效的策略呢？如果沒有策略，其實(shí)也無從計(jì)算其價(jià)值。
能不能隨機(jī)初始化一個(gè)策略？在這基礎(chǔ)上計(jì)算其價(jià)值，進(jìn)而得到更好的策略。
對(duì)于以上解決問題的思路，我第一次看到的時(shí)候，也不禁暗暗贊嘆。事實(shí)上，這就是我這里想要給大家介紹的另一個(gè)強(qiáng)化學(xué)習(xí)經(jīng)典算法：策略迭代 算法。
如何根據(jù)一個(gè)策略尋找更優(yōu)策略？可以這樣做：
- 計(jì)算在當(dāng)前策略下，哪一個(gè)行動(dòng)能得到最大價(jià)值
- 選擇價(jià)值最大的行動(dòng)作為新策略的行動(dòng)
用公式表述如下：
（下一個(gè)（第i+1個(gè)）更優(yōu)策略π(i+1)，其中：s表示當(dāng)前狀態(tài)；a = π(s)表示動(dòng)作；s'表示下一個(gè)狀態(tài)；T(s, a, s')表示在狀態(tài)s，執(zhí)行動(dòng)作a轉(zhuǎn)換到狀態(tài)s'的概率；R(s, a, s')表示在狀態(tài)s，執(zhí)行動(dòng)作a轉(zhuǎn)換到狀態(tài)s'得到的獎(jiǎng)勵(lì)）
到這里，這個(gè) 策略迭代 算法就差不多完成了。用JavaScript代碼實(shí)現(xiàn)，主要代碼如下：
MDPPISolver.solve = function () {
var policy = this.randomPolicy();
var policyNew = policy;
do {
policy = policyNew;
values = this.solveForPolicy(policy);
policyNew = this.improvePolicy(values, policy);
} while (!this.converged(policy, policyNew));
...
}
完整代碼見這里932行到1024行。
擴(kuò)展
狀態(tài)空間降維
雖然我們可以用上述兩個(gè)經(jīng)典算法解決這個(gè)問題，但是它們的效率是很低的，算法復(fù)雜度用大O計(jì)算法可以表示為O(ass)。對(duì)于這個(gè)非常簡(jiǎn)單的問題，計(jì)算速度尚能接受，但是如果我們考慮一些更復(fù)雜的問題，就會(huì)發(fā)現(xiàn)這里的狀態(tài)s的取值空間可能會(huì)非常大。
比如對(duì)于下面這個(gè)吃豆子的游戲，這里的狀態(tài)數(shù)量為：
狀態(tài)數(shù)量 = 格子數(shù)量 * N (N為每個(gè)格子的可能狀態(tài)：比如是否有吃豆人、是否有豆子、是否有敵人及敵人的類型等等)
過大的狀態(tài)空間就導(dǎo)致上述經(jīng)典算法實(shí)際無法執(zhí)行，也就無法滿足實(shí)際需求。
一個(gè)可能的優(yōu)化手段是人為的設(shè)計(jì)一些特征來表示某個(gè)狀態(tài)s，這樣就實(shí)現(xiàn)了對(duì)s進(jìn)行降維的操作。比如對(duì)于上面吃豆子的游戲，我們可以建模這樣幾個(gè)特征：
- 離最近的豆子的方向和距離
- 離每個(gè)敵人的方向和距離
- 敵人的移動(dòng)速度和方向
有了這樣的很小的狀態(tài)空間，上述算法就可以執(zhí)行了。
深度強(qiáng)化學(xué)習(xí)DQN
有了上述狀態(tài)空間降維的辦法，我們可以考慮是不是可以用一個(gè)深度神經(jīng)網(wǎng)絡(luò)來替代人工特征的過程呢？當(dāng)然是可以的，這就是前幾年 Deep Mind 轟動(dòng)學(xué)界和產(chǎn)業(yè)界的關(guān)于 深度強(qiáng)化學(xué)習(xí) 的論文中的內(nèi)容了。
DQN的全稱是Deep Q-Network，它的核心是一個(gè)Q值迭代的算法。Q值迭代公式就是我們 價(jià)值迭代 公式中的關(guān)于行動(dòng)價(jià)值的公式的一個(gè)迭代形式。算法也是不斷迭代直到收斂。
我在另一篇文章中有關(guān)于DQN的更多內(nèi)容。詳情見這里。
更多的問題
考慮一個(gè)更實(shí)際的問題，上述經(jīng)典算法假設(shè)我們知道了狀態(tài)轉(zhuǎn)移函數(shù)T。但實(shí)際上當(dāng)前世界可能對(duì)于我們是全新的，T對(duì)于我們而言當(dāng)然也是未知的。這個(gè)時(shí)候有什么辦法呢？一個(gè)簡(jiǎn)單的思路是我們可以通過不斷在這個(gè)世界中進(jìn)行探索，去了解這個(gè)世界的運(yùn)作方式，也就是不斷的弄清了這個(gè)T函數(shù)。在強(qiáng)化學(xué)習(xí)的研究中，抽象一下這個(gè)過程，即通過不斷采樣來近似估計(jì)T函數(shù)。
另一個(gè)實(shí)際的問題是，有時(shí)候我們可能無法執(zhí)行這么多次探索，或者每次探索的成本太高以至于負(fù)擔(dān)不起。這時(shí)，一個(gè)有效的思路是，我們可以從別人的經(jīng)驗(yàn)中學(xué)習(xí)，或者通過看電影讀書進(jìn)行學(xué)習(xí)。當(dāng)前的強(qiáng)化學(xué)習(xí)方法也在這個(gè)方向上進(jìn)行了很多探索。
對(duì)于如何高效的進(jìn)行學(xué)習(xí)，還有一個(gè)思路，那就是我們能否模仿某個(gè)已有的不錯(cuò)的行動(dòng)策略呢？比如，假設(shè)我們希望訓(xùn)練機(jī)器人做家務(wù)，那么是不是可以通過演示一遍給機(jī)器人看，然后機(jī)器人通過模仿進(jìn)行學(xué)習(xí)呢？這就是模仿學(xué)習(xí)思路去解決這個(gè)問題。
關(guān)于這個(gè)領(lǐng)域，我們還可以想出更多的問題，比如，如何讓機(jī)器人自己去探索解決問題的方法？如何處理連續(xù)的動(dòng)作（文章開始時(shí)提到的喝水的例子，這里移動(dòng)雙手的過程其實(shí)就是連續(xù)動(dòng)作決策的過程）？如何自動(dòng)設(shè)置獎(jiǎng)勵(lì)甚至不設(shè)置獎(jiǎng)勵(lì)？很多越來越難問題被一個(gè)一個(gè)提出，同時(shí)又正在被不斷提出的新思路一個(gè)一個(gè)攻克。
總結(jié)
總結(jié)起來，強(qiáng)化學(xué)習(xí)其實(shí)就是關(guān)于如何學(xué)習(xí)的研究。這個(gè)領(lǐng)域發(fā)展至今能解決的問題還比較有限，我們離最終的通用人工智能的路還很長(zhǎng)。同時(shí)，很多新的有挑戰(zhàn)性的問題不斷被提出來，被大家研究，很多創(chuàng)新的解決問題的思路也不斷被發(fā)掘出來。正是我們對(duì)這個(gè)領(lǐng)域充滿熱情，才推動(dòng)了這個(gè)領(lǐng)域如此蓬勃的發(fā)展。相信終有一天這個(gè)問題能被我們?nèi)祟惞タ恕?/p>
相關(guān)文章：讓機(jī)器自己玩游戲
關(guān)注我：Github 個(gè)人博客 以往博客
原文鏈接：https://insights.thoughtworks.cn/reinforcement-learning/
文/ThoughtWorks 廖光明
更多精彩洞見，請(qǐng)關(guān)注微信公眾號(hào)：ThoughtWorks洞見
