前言

本文來(lái)自西湖大學(xué)趙世鈺老師的B站視頻。本節(jié)課主要介紹貝爾曼公式。
本節(jié)課概要：本節(jié)課需要抓住兩個(gè)內(nèi)容，state value 和 the Bellman equation。本次大綱如下：

1、Motivating examples

return就是有多條軌跡，沿著這些軌跡可以得到很多的rewards，把這些rewards求和，就得到return。為什么return這么重要呢？通過(guò)上圖三個(gè)例子來(lái)做介紹，上面三幅圖的環(huán)境是一樣的，s4是目標(biāo)，s2是forbidden area，白色的是accessible area。這三幅圖不同的是在狀態(tài)s1上的策略是不同的，第一幅圖在s1會(huì)往下走，第二幅圖在s1會(huì)往右走，第三幅圖在s1有50%的概率往下走，50%的概率往右走，在其他位置上，它們的策略是一樣的。
因此，我們需要回答，從s1出發(fā)，哪一個(gè)策略是最好的，哪一個(gè)策略是最差的，從直觀上來(lái)說(shuō)，第一幅圖的策略是最好的，第二幅圖的策略是最差的，第三幅圖的策略不好也不差。因?yàn)榈谝环鶊D從s1出發(fā)不會(huì)進(jìn)入到forbidden area，第二幅圖會(huì)直接進(jìn)入forbidden area，第三幅圖有50%的概率進(jìn)入到forbidden area。那么我們可以用數(shù)學(xué)來(lái)描述這一種直觀，數(shù)學(xué)工具就是這個(gè)return。return之所以重要，是因?yàn)樗嬖V我們哪個(gè)策略好，哪個(gè)策略壞，即它能夠評(píng)估策略。
下面我們分別來(lái)計(jì)算這三個(gè)例子對(duì)應(yīng)的return：

對(duì)于第一幅圖，從s1到s3，得到的reward為0，從s3到s4得到的reward為γ乘以1，然后就會(huì)一直呆在s4，得到的結(jié)果如上圖。同樣的方法我們可以得到第二幅圖和第三幅圖對(duì)應(yīng)的return。策略3對(duì)應(yīng)的return實(shí)際上就是我們接下來(lái)要學(xué)的state value。


下面做個(gè)總結(jié)：

下面進(jìn)一步來(lái)講一下return如何計(jì)算。
考慮從不同狀態(tài)出發(fā)，計(jì)算的return。用vi表示從狀態(tài)si出發(fā)得到的return。有兩種方法，第一種方法為：

第二種方法為：

v1就是從s1出發(fā)，到達(dá)s2之后，就相當(dāng)于從s2出發(fā)了，從s2出發(fā)一定得到的是v2，因此v1可以寫(xiě)成上述形式，依次類推。
但同樣也面臨著一些問(wèn)題，在計(jì)算時(shí)我們要求解v，但還得事先知道v，這個(gè)好像陷入了一個(gè)不可能解決的問(wèn)題?？此坪孟駸o(wú)法解決，但如果我們用數(shù)學(xué)的話，就可以解決了，首先我們將上圖中的式子寫(xiě)成矩陣和向量的形式：


這是一個(gè)比較簡(jiǎn)單的，特別是針對(duì)確定性問(wèn)題的貝爾曼公式，后面會(huì)更加正式地介紹一般化地貝爾曼公式。但這個(gè)公式也告訴我們，一個(gè)狀態(tài)地value實(shí)際上依賴于其他狀態(tài)地value，這個(gè)就是bootstrapping想法；另外就是matrix-vector form也是非常重要地，就是我們只看一個(gè)公式是沒(méi)辦法解決的，但我們把所有的公式全都組合到一起，得到一個(gè)matrix-vector form就很容易求出來(lái)。
下面我們?cè)谧鲆粋€(gè)例子來(lái)加深理解：

2、state value

這一部分介紹state value概念。為了介紹state value，我們首先引入一些符號(hào)：

首先看單步的，St是當(dāng)前狀態(tài)，在當(dāng)前狀態(tài)下采取的動(dòng)作是At，得到的下一個(gè)reward是Rt+1，跳到下一個(gè)狀態(tài)是St+1。t指的是當(dāng)前時(shí)刻，t+1指的是下一時(shí)刻。

St、At、Rt+1都是隨機(jī)變量，這也就意味著我們可以求解它們的期望。這樣單步的過(guò)程可以推廣到多步的trajectory。下圖中的Gt也是一個(gè)隨機(jī)變量。

有了以上基礎(chǔ)，我們可以來(lái)定義state value了：

第一點(diǎn)：state value function 是關(guān)于狀態(tài)s的函數(shù)，從不同的s出發(fā)，得到的軌跡不同，顯然得到的discount return也不同，求平均也是不同的；第二點(diǎn)：state value function是一個(gè)策略的函數(shù)，顯然不同的策略會(huì)得到不同的軌跡，不同的軌跡又會(huì)得到不同的return，進(jìn)而會(huì)得到不同的state value。最后一點(diǎn)是，這個(gè)state value不僅僅是一個(gè)數(shù)值的value，它也代表一種價(jià)值，當(dāng)一個(gè)state value比較大的時(shí)候，就代表這個(gè)狀態(tài)是比較有價(jià)值的，因?yàn)閺倪@個(gè)狀態(tài)出發(fā)，我們會(huì)得到更多的return。
最后來(lái)回答這樣一個(gè)問(wèn)題：state value和return有什么區(qū)別？return是針對(duì)單個(gè)trajectory求的return，而state value是對(duì)多個(gè)trajectory得到的return再求平均值，如果我們從一個(gè)狀態(tài)出發(fā)，有可能得到多個(gè)trajectory，此時(shí)return和state value是有區(qū)別的，但是如果我們從一個(gè)狀態(tài)出發(fā)，一切都是確定性的，也就是說(shuō)只能得到一條trajectory，此時(shí)從那個(gè)狀態(tài)出發(fā)得到的return和state value是一樣的。
下面我們來(lái)看一個(gè)例子：

上述三幅圖分別對(duì)應(yīng)三個(gè)策略，假設(shè)從左到右分別是π1、π2、π3，接下來(lái)我們計(jì)算在這三個(gè)不同策略下，同一個(gè)狀態(tài)s1的state value。計(jì)算vπ1(s1)、vπ2(s1)、vπ3(s1)可知，第一幅圖對(duì)應(yīng)的策略是最好的。(上圖所舉例子是求確定性的trajectory下的state value)

3、Bellman equation:Derivation

我們首先來(lái)學(xué)習(xí)的是如何來(lái)推到貝爾曼公式。本小節(jié)重點(diǎn)如下：

總結(jié)：我們要學(xué)會(huì)用貝爾曼公式計(jì)算上節(jié)中提到的state value，貝爾曼公式用一句話可以概況來(lái)說(shuō)就是它描述了不同狀態(tài)的state value之間的關(guān)系。

首先考慮這樣一個(gè)trajectory，從狀態(tài)St出發(fā)，采取動(dòng)作At，得到Rt+1和St+1，以此類推，得到了上圖中的一個(gè)trajectory。這樣的一個(gè)trajectory可以計(jì)算它的discounted return Gt，從上圖推導(dǎo)后的公式來(lái)看，Gt就等于我立刻能得到的immediate reward Rt+1，再加上從下一時(shí)刻出發(fā)得到的Gt+1乘以discount rate γ。

從上圖可以看出，state value可以用藍(lán)色的兩個(gè)期望來(lái)表示，分別計(jì)算這兩個(gè)期望就能得到貝爾曼公式。下圖就是第一個(gè)期望的計(jì)算方法：

第一項(xiàng)期望實(shí)際上就是immediate rewards的mean，第二項(xiàng)的期望公式見(jiàn)下圖：

第二項(xiàng)是從當(dāng)前狀態(tài)s出發(fā)所得到的下一時(shí)刻的return的mean。從當(dāng)前狀態(tài)出發(fā)，可以有多個(gè)選擇，可以跳到s撇，跳到不同s撇的概率是p(s撇|s)，跳到s撇得到的期望值是E(Gt+1|St=s,St+1=s撇)，E(Gt+1|St=s,St+1=s撇)指的是當(dāng)前狀態(tài)是s，下一時(shí)刻狀態(tài)是s撇，計(jì)算從下一個(gè)狀態(tài)出發(fā)，所得到的return的mean。E(Gt+1|St=s,St+1=s撇)中的St=s是可以去掉的，因?yàn)槲乙呀?jīng)知道了下一個(gè)狀態(tài)是s撇，就不用關(guān)心之前是什么狀態(tài)了。E(Gt+1|St+1=s撇)就是針對(duì)s撇的state value，用vπ(s撇)。從s到s撇的概率p(s撇|s)就是從狀態(tài)s出發(fā)，選取不同的動(dòng)作a的概率，乘以當(dāng)前狀態(tài)下采取動(dòng)作a得到s撇的概率，不同動(dòng)作a求和就是p(s撇|s)。
總之，第二個(gè)期望就是未來(lái)rewards的一個(gè)均值。

至此，我們就可以給出貝爾曼公式的表達(dá)式了：

上圖中的公式就是貝爾曼公式，它實(shí)際上描述了不同狀態(tài)的state value之間的關(guān)系。公式左邊是s的state value，右邊是s撇的state value。另外，這個(gè)式子包含兩項(xiàng)，一項(xiàng)是immediate reward，另一項(xiàng)是future reward。上述式子應(yīng)該是對(duì)狀態(tài)空間中所有的狀態(tài)都成立的，所以，如果我們有n個(gè)狀態(tài)，我們就會(huì)有n個(gè)這樣的式子，通過(guò)n個(gè)這樣的式子，我們就可以把state value給求解出來(lái)，但我們通常就寫(xiě)上述一個(gè)式子，大家千萬(wàn)不要以為貝爾曼公式就只有這一個(gè)式子。

狀態(tài)值如何計(jì)算呢？vπ(s)依賴于vπ(s撇)，而vπ(s撇)又依賴于其它狀態(tài)值，看起來(lái)似乎沒(méi)辦法計(jì)算，這其實(shí)就是bootstrapping，我們可以用矩陣來(lái)進(jìn)行計(jì)算。另外，這個(gè)式子依賴于很多概率，π(a|s)是policy，貝爾曼公式是依賴于概率的，我們要把state value給計(jì)算出來(lái)，實(shí)際上我們現(xiàn)在正在做的事情就叫policy evaluation，就是去evaluation這個(gè)policy是好是壞。

上圖中的綠色箭頭就是策略π。



如果假設(shè)γ=0.9，得到的結(jié)果見(jiàn)上圖。state value實(shí)際上是代表了他的價(jià)值，如果一個(gè)狀態(tài)價(jià)值高，說(shuō)明了這個(gè)狀態(tài)是值得我們往那個(gè)方向走的，在上圖中，為什么s2，s3，s4的價(jià)值高呢，是因?yàn)樗麄冸xtarget area是比較近的，而s1離得較遠(yuǎn)。計(jì)算得到這個(gè)狀態(tài)值之后，我們就可以去改進(jìn)這個(gè)策略，慢慢的我們就可以得到最優(yōu)的策略。

4、Bellman equation:Matrix-vector form

在上節(jié)中，我們介紹了貝爾曼公式的推導(dǎo)，這節(jié)來(lái)介紹貝爾曼公式的矩陣和向量形式。

rπ(s)是從當(dāng)前狀態(tài)出發(fā)，得到了所有immediate reward的平均值。上式紅色畫(huà)的意思是展開(kāi)相乘。

上圖中，[Pπ]ij代表第i行第j列的元素是從si跳到sj的概率，[Pπ]ij這個(gè)矩陣也被稱為狀態(tài)轉(zhuǎn)移矩陣。

上圖是當(dāng)n=4時(shí)，我所得到的matrix-vector 形式，上圖中的Pπ就是狀態(tài)轉(zhuǎn)移矩陣。在舉一個(gè)例子，見(jiàn)下圖：

4、Bellman equation:Solve the state value

首先我們來(lái)回答一下為什么要求解state value，實(shí)際上給定一個(gè)policy，然后我會(huì)列出來(lái)它的一個(gè)貝爾曼公式，再進(jìn)一步求解貝爾曼公式得到state value，這樣的一個(gè)過(guò)程實(shí)際上叫做policy evaluation。policy evaluation是強(qiáng)化學(xué)習(xí)中非常關(guān)鍵的一個(gè)問(wèn)題，因?yàn)槲覀冎挥腥ピu(píng)價(jià)一個(gè)策略到底好還是不好，我們才能進(jìn)一步的去改進(jìn)它，最后在找到最優(yōu)的策略，所以求解貝爾曼公式進(jìn)而得到state value是非常重要的一個(gè)問(wèn)題。

求state value我們給出兩種解決方案，第一種就是用求逆矩陣的方法直接求解，但是這種方法通常不會(huì)使用，因?yàn)楫?dāng)狀態(tài)空間特別大的時(shí)候，矩陣的維度也會(huì)特別大，求逆的計(jì)算量也會(huì)特別大，所以實(shí)際當(dāng)中我們使用的是迭代的方法。iterative solution方法就是從一開(kāi)始隨機(jī)猜一個(gè)vπ，記為v0，把這個(gè)v0帶入到上圖紅色箭頭所指的式子中，因?yàn)閞π和Pπ都是可以事先知道的，所以可以計(jì)算得到v1，然后再把v1帶到右邊，就又可以得到v2，依次類推，就會(huì)得到序列{v0，v1，v2，…vk}，實(shí)際上我們可以證明當(dāng)k趨近于無(wú)窮的時(shí)候，vk就收斂到了vπ，這個(gè)vπ就是真實(shí)的state value。為什么vk會(huì)收斂到vπ呢？下面是證明。

證明的思路是定義vk與vπ之間的誤差，證明這個(gè)誤差趨近于0即可。下面我們通過(guò)例子來(lái)進(jìn)一步說(shuō)明。

上圖是兩個(gè)比較好的policy，可以看到得到的狀態(tài)值均為正，并且我們還可以看出，不同的策略可以得到相同的value值。下面我們?cè)诳磧蓚€(gè)不好的policy。

通過(guò)以上例子可以得出，我們可以計(jì)算state value來(lái)評(píng)價(jià)一個(gè)策略究竟是好還是壞。

5、Action value

在前幾節(jié)，我們介紹了state value，以及描述state value的貝爾曼公式，下面我們將從state value轉(zhuǎn)向action value。

state value和action value有什么區(qū)別與聯(lián)系呢？state value指的是agent從一個(gè)狀態(tài)出發(fā)，所得到的average return。action value指的是agent從一個(gè)狀態(tài)出發(fā)并且選擇一個(gè)action之后得到的average return。
為什么要關(guān)注action value：實(shí)際上我們一直討論的是強(qiáng)化學(xué)習(xí)中的策略，策略指的是在一個(gè)狀態(tài)我要選擇什么樣的action，action有很多，具體選擇哪一個(gè)action就是通過(guò)action value來(lái)判斷，action value大的意味著采取該action能夠得到更多的reward。

由上圖可知，state value可以和action value建立聯(lián)系。有很多個(gè)action，在當(dāng)前狀態(tài)下，采取其中一個(gè)action的概率為π(a|s)，乘以采取該動(dòng)作后得到的average return。與π(a|s)相乘的那一項(xiàng)就是action value。


下面通過(guò)一個(gè)例子來(lái)理解action value：
上圖中策略已經(jīng)通過(guò)綠色箭頭畫(huà)出來(lái)了。

下面做一個(gè)總結(jié)：

state value滿足貝爾曼公式，貝爾曼公式刻畫(huà)了state value之間的公式，是求解state value的一個(gè)工具，上圖是它的elementwise form，就是對(duì)每一個(gè)狀態(tài)都存在這樣一個(gè)式子。