幫你們破除RL的神秘感，理清各算法發(fā)展的脈絡(luò)

前言

之前通過線上課程學(xué)習(xí)David Silver的《強(qiáng)化學(xué)習(xí)》，留下深刻印象的是其中一堆堆的公式。公式雖然嚴(yán)謹(jǐn)，但是對于我來說，遇到實(shí)際問題時(shí)，我需要在腦海中浮現(xiàn)出一幅圖或一條曲線，幫我快速定位問題。正所謂“一圖勝千言”嘛。

最近終于找到了這樣一幅圖。國外有大神用漫畫的形式講解了強(qiáng)化學(xué)習(xí)中經(jīng)典的Advantage-Actor-Critic（A2C）算法。盡管標(biāo)題中只提及了A2C，實(shí)際上是將整個(gè)RL的算法思想凝結(jié)在區(qū)區(qū)幾幅漫畫中。

我很佩服漫畫的作者，能夠從復(fù)雜的公式中提煉出算法的精髓，然后用通俗易懂、深入淺出的方式展示出來。能夠?qū)⒑駮x薄，才能顯現(xiàn)出一個(gè)人的功力。

有這樣NB的神作，不敢獨(dú)吞，調(diào)節(jié)一下順序，補(bǔ)充一些背景知識，加上我自己的批注，分享出來，以饗讀者。 原漫畫的地址見：Intuitive RL: Intro to Advantage-Actor-Critic (A2C)，英語好的同學(xué)可以科學(xué)上網(wǎng)看原版的。

基本概念

強(qiáng)化學(xué)習(xí)中最基礎(chǔ)的四個(gè)概念：Agent, State, Action, Reward

Agent：不用多說，就是你的程序，在這里就是這只狐貍。

Action: agent需要做的動作。在漫畫中，就是狐貍在岔路口時(shí)，需要決定走其中的哪一條路。

State: 就是agent在決策時(shí)所能夠掌握的所有信息。對于這只狐貍來說，既包括了決策當(dāng)時(shí)的所見所聞，也包括了它一路走來的記憶。

Reward：選擇不同的路，可能遇到鳥蛋（正向收益），也有可能遇到豺狼（負(fù)向收益）。

為什么Actor? 為什么Critic?

正如我之前所說的，Actor-Critic是一個(gè)混合算法，結(jié)合了Policy Gradient（Actor）與Value Function Approximation (Critic)兩大類算法的優(yōu)點(diǎn)。原漫畫沒有交待，一個(gè)agent為什么需要actor與critic兩種決策機(jī)制。所以，在讓狐貍繼續(xù)探險(xiǎn)之前，有必要先簡單介紹一下Policy Gradient （策略梯度，簡稱PG）算法，后面的內(nèi)容才好理解。

Policy Gradient看起來很高大上，但是如果類比有監(jiān)督學(xué)習(xí)中的多分類算法，就很好理解了。兩類算法的類比（簡化版本）如下表所示，可見兩者很相似

“分類有監(jiān)督學(xué)習(xí)”與“策略梯度強(qiáng)化學(xué)習(xí)”的對比

還是以狐貍在三岔路口的選擇為例

N就是樣本個(gè)數(shù)

就是每次決策前的信息，即特征

如果選擇哪條岔道是有唯一正確答案的，并且被標(biāo)注了，即?，則我們可以用“多分類算法”來學(xué)習(xí)它。

但是，在強(qiáng)化學(xué)習(xí)中，每次選擇沒有唯一正確的答案，而且每次選擇的收益也是延后的。既然我們不知道所謂“唯一正確答案”，我們就做一次選擇?(未必是最優(yōu)的)，再將這個(gè)選擇對最終loss或gradient的貢獻(xiàn)乘以一個(gè)系數(shù)，即上式中的?，有個(gè)學(xué)術(shù)的名字叫“Likelihood Ratio”

怎么理解Likelihood Ratio這個(gè)乘子？這個(gè)乘子必須滿足什么樣的要求？最簡單的形式，?可以是一次實(shí)驗(yàn)（如AlphaGo的一次對弈，狐貍一天的探險(xiǎn)）下來的總收益。從而PG可以寫成如下形式：

Policy Gradient公式

是優(yōu)化變量

公式左邊是平均收益

公式右邊中，N是總實(shí)驗(yàn)的次數(shù)，

是第n次實(shí)驗(yàn)

是第n次實(shí)驗(yàn)中，第t步時(shí)，在當(dāng)前state是的概率的情況下，選擇了動作

以上公式表明：

如果第n次實(shí)驗(yàn)的總收益是正的，則假定第n次實(shí)驗(yàn)中的每步?jīng)Q策都是正確的，應(yīng)該調(diào)節(jié)

如果第n次實(shí)驗(yàn)的總收益是負(fù)的，則假定第n次實(shí)驗(yàn)中的每步?jīng)Q策都是錯(cuò)誤的，應(yīng)該調(diào)節(jié)

基于“真實(shí)有效的決策，在成功實(shí)驗(yàn)出現(xiàn)的次數(shù)，比在失敗實(shí)驗(yàn)出現(xiàn)的次數(shù)，要多”這樣的假設(shè)，以上方法還是能夠?qū)W到東西的。

但是，以上算法中統(tǒng)一用做乘子，還是太簡單粗暴，有些“一榮倶榮，一損俱損”搞“連坐”的味道。因此，在實(shí)際算法中，圍繞著policy gradient前的那個(gè)乘子，衍生出多種變體，

比如考慮每步?jīng)Q策的直接收益的時(shí)間衰減，就是REINFORCE算法。

如果用V(S)，即“狀態(tài)值”state-value，來表示PG前的系數(shù)，并用一個(gè)模型來專門學(xué)習(xí)它，則這個(gè)擬合真實(shí)（不是最優(yōu)）V(s)的模型就叫做Critic，而整個(gè)算法就是Actor-Critic算法。

因?yàn)槠?，簡單介紹一下V(s)與Q(s,a)。它們是Value Function Approximation算法中兩個(gè)重要概念，著名的Deep Q-Network中的Q就來源于Q(s,a)。V(s)表示從狀態(tài)s走下去能夠得到的平均收益。它類似于咱們常說的“勢”，如果一個(gè)人處于“優(yōu)勢”，無論他接下去怎么走（無論接下去執(zhí)行怎樣的action），哪怕走一兩個(gè)昏招，也有可能獲勝。具體精確的理解，還請感興趣的同學(xué)移步David Silver的課吧。

重新回顧一下算法的脈絡(luò)，所謂Actor-Critic算法

Actor負(fù)責(zé)學(xué)習(xí)在給定state下給各候選action打分。在action空間離散的情況下，就類似于多分類學(xué)習(xí)。

因?yàn)榕c多分類監(jiān)督學(xué)習(xí)不同，每步?jīng)Q策時(shí)，不存在唯一正確的action，所以PG前面應(yīng)該乘以一個(gè)系數(shù)，即likelihood ratio。如果用V(S)，即state-value，來表示PG前的乘子，并用一個(gè)模型來專門學(xué)習(xí)它，則這個(gè)擬合V(s)的模型就叫做Critic，類似一個(gè)回歸模型。

如果用Critic預(yù)測值與真實(shí)值之間的誤差，作為likelihood ratio，則PG前的乘子就有一個(gè)專門的名稱，Advantage。這時(shí)的算法，就叫做Advantage-Actor-Critic，即A2C。

如果在學(xué)習(xí)過程中，引入異步、分布式學(xué)習(xí)，此時(shí)的算法叫做Asynchronous-Advantage-Actor-Critic，即著名的A3C。

狐貍的探險(xiǎn)

上一節(jié)已經(jīng)說明了狐貍(Agent)為什么需要actor-critic兩個(gè)決策系統(tǒng)。則狐貍的決策系統(tǒng)可以由下圖表示

state是狐貍做決策時(shí)所擁有的一切信息，包括它的所見所聞，還有它的記憶。

critic負(fù)責(zé)學(xué)習(xí)到準(zhǔn)確的V(s)，負(fù)責(zé)評估當(dāng)前狀態(tài)的“態(tài)勢”，類似一個(gè)回歸任務(wù)。

actor負(fù)責(zé)學(xué)習(xí)某狀態(tài)下各候選action的概率，類似一個(gè)多分類任務(wù)。

在第一個(gè)路口

狐貍的critic覺得當(dāng)前態(tài)勢不錯(cuò)，預(yù)計(jì)從此走下去，今天能得20分，即V(s)=20

狐貍的actor給三條路A/B/C都打了分

狐貍按照A=0.8, B=C=0.1的概率擲了色子，從而決定走道路A（沒有簡單地選擇概率最大的道路，是為了有更多機(jī)會explore）

沿A路走，采到一枚蘑菇，得1分

把自己對state value的估計(jì)值，采取的動作，得到的收益都記錄下來

在接下來的兩個(gè)路口，也重復(fù)以上過程：

狐貍的反思：更新Critic

畢竟這只狐貍還太年輕，critic對當(dāng)前狀態(tài)的估計(jì)可能存在誤差，actor對岔道的打分也未必準(zhǔn)確，因此當(dāng)有了三次經(jīng)歷后，狐貍停下來做一次反思，更新一下自己的critic和actor。狐貍決定先更新自己的critic。

之前說過了，critic更像是一個(gè)“回歸”任務(wù)，目標(biāo)是使critic預(yù)測出的state value與真實(shí)state value越接近越好。以上三次經(jīng)歷的state value的預(yù)測值，狐貍已經(jīng)記在自己的小本上了，那么問題來了，那三個(gè)state的真實(shí)state value是多少？

在如何獲取真實(shí)state value的問題上，又分成了兩個(gè)流派：Monte Carlo(MC)法與Temporal-Difference(TD)法。

MC法，簡單來說，就是將一次實(shí)驗(yàn)進(jìn)行到底，實(shí)驗(yàn)結(jié)束時(shí)的V(s)自然為0，然后根據(jù)Bellman方程回推實(shí)驗(yàn)中每個(gè)中間步驟的V(s)，如下圖所示（圖中簡化了Bellman方程，忽略了時(shí)間衰減）。MC法的缺點(diǎn)，一是更新慢，必須等一次實(shí)驗(yàn)結(jié)束，才能對critic/actor進(jìn)行更新；二是因?yàn)閂(s)是狀態(tài)s之后能夠獲得的平均收益，實(shí)驗(yàn)越長，在每個(gè)步驟之后采取不同action導(dǎo)致的分叉越多，但是MC法僅僅依靠上一次實(shí)驗(yàn)所覆蓋的單一路徑就進(jìn)行更新，顯然導(dǎo)致high variance。

Monte Carlo法

另一種方法，TD法，就是依靠現(xiàn)有的不準(zhǔn)確的critic進(jìn)行bootstrapping，逐步迭代，獲得精確的critic

現(xiàn)在狐貍要反思前三個(gè)狀態(tài)的state value，狐貍假定當(dāng)前critic（老的，尚未更新的）在當(dāng)前狀態(tài)（第4個(gè)狀態(tài)）預(yù)測出state value是準(zhǔn)確的，?=18

根據(jù)V(s)的定義，V(s)代表自s之后能夠獲得的平均收益，既然=18+2=20

同理，=?+=20+20=40

同理，=?+==40+1=41

Temporal-Difference法

如上圖中狐貍的記事本所示，對于以上三步，狐貍既有了自己對當(dāng)時(shí)state value的預(yù)測值，也有了那三個(gè)state value的“真實(shí)值”，上面的紅字就是二者的差，可以用類似“回歸”的方法最小化求解。

狐貍的反思：更新Actor

正如前文所述，critic的作用是為了準(zhǔn)確預(yù)測Policy Gradient前的那個(gè)系數(shù)，即Likelihood Ratio。

likelihood ratio>0，應(yīng)該調(diào)節(jié)actor的參數(shù)，提升的概率，即鼓勵(lì)當(dāng)時(shí)采取的動作

likelihood ratio<0，應(yīng)該調(diào)節(jié)actor的參數(shù)，降低抑制當(dāng)時(shí)采取的動作

那么critic應(yīng)該為PG貢獻(xiàn)一個(gè)什么樣的likelihood ratio呢？考慮以下的例子

在一個(gè)三岔路品，狐貍感受到的狀態(tài)是前路有狼、陷阱和破橋，哪條道都不好走，因此狐貍預(yù)測當(dāng)前“狀態(tài)值”極差，=-100

狐貍還是硬著頭皮選擇了一條稍微好走的路，中間丟失了許多食物，收益=-20

恰好過了橋之后，一天也就結(jié)束了，最終狀態(tài)的=0。根據(jù)critic bootstrapping進(jìn)行回推，當(dāng)初過橋前“真實(shí)狀態(tài)值”=-20

那么actor中，policy gradient之前的likelihood ratio應(yīng)該是多少？能不能選擇采取動作之后的直接收益，-20?如果是的話，因?yàn)檫x擇過橋，導(dǎo)致狐貍丟了20分，以后狐貍在相同狀態(tài)下（看見前路有狼、陷阱和破橋）選擇“過破橋”的概率應(yīng)該降低?。?！

以上結(jié)論顯然是不合適的，下次不選橋，難道要選狼與陷阱？！哪里出錯(cuò)了？

換個(gè)思路：

當(dāng)初在岔路口時(shí)，狐貍對當(dāng)時(shí)state value的預(yù)測是-100，

選擇了破橋之后，根據(jù)critic bootstrapping推導(dǎo)回去，發(fā)現(xiàn)之前在岔路口時(shí)的狀態(tài)還不至于那么差，“真實(shí)state value”=-20。

回頭來看，選擇“破橋”還改善了當(dāng)時(shí)的處境，有80分的提升。

因此，之后在相同狀態(tài)下（看見前路有狼、陷阱和破橋）選擇“破橋”的概率，不僅不應(yīng)該降低，反而還要提高，以鼓勵(lì)這種明智的選擇，顯然更合情合理。

這里，某個(gè)狀態(tài)s下的state value的“真實(shí)值”與預(yù)測值之間的差異，就叫做Advantage，拿advantage作為Policy Gradient之前的乘子，整個(gè)算法就叫做Advantage-Actor-Critic (A2C)。

Advantage

注意state value的“真實(shí)值”與預(yù)測值之間的差異在Actor與Critic上發(fā)揮的不同作用

在Actor中，這個(gè)差值就叫做Advantage，用來指導(dǎo)Actor應(yīng)該鼓勵(lì)還是抑制已經(jīng)采取的動作。動作帶來的Advantage越大，驚喜越大，下次在相同狀態(tài)下選擇這個(gè)動作的概率就應(yīng)該越大，即得到鼓勵(lì)。反之亦然。

在Critic中，這個(gè)差值就叫做Error，是要優(yōu)化降低的目標(biāo)，以使Agent對狀態(tài)值的估計(jì)越來越準(zhǔn)確。間接使Actor選擇動作時(shí)也越來越準(zhǔn)確。

其他

A2C的主要思路就這樣介紹完畢了。在原漫畫中，還簡單介紹了A3C、Entropy Loss的思想，就屬于旁枝末節(jié)，請各位看官們移步原漫畫。其實(shí)A3C的思路也很簡單（實(shí)現(xiàn)就是另一回事了），無非是讓好幾只狐貍并發(fā)地做實(shí)驗(yàn)，期間它們共享經(jīng)驗(yàn)教訓(xùn)，以加速學(xué)習(xí)。

A3C

小結(jié)

本篇算是一個(gè)半原創(chuàng)吧，在翻譯的同時(shí)，也增加了我對Actor-Critic的理解。

對于初學(xué)RL的同學(xué)，希望本文能夠幫你們破除RL的神秘感，理清各算法發(fā)展的脈絡(luò)，以后在David Silver課上看到那些公式時(shí)，能夠有“似曾相識”的感覺。

對于掌握了RL基本算法的同學(xué)，也希望你們能夠像我一樣，當(dāng)遇到實(shí)際問題時(shí)，先想到漫畫中的小狐貍，定位問題，再去有的放矢地去翻書找公式。

很佩服原漫畫的作者，能將復(fù)雜的公式、原理用如此通俗易懂、深入淺出的方式講明白。再次向原作者致敬，Excellent Job !!!