前言

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

1、Motivating examples

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

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


下面做個總結(jié)：

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

第二種方法為：

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


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

2、state value

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

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

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

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

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

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

3、Bellman equation:Derivation

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

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

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

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

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

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

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

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

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

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



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

4、Bellman equation:Matrix-vector form

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

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

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

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

4、Bellman equation:Solve the state value

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

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

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

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

通過以上例子可以得出，我們可以計算state value來評價一個策略究竟是好還是壞。

5、Action value

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

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

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


下面通過一個例子來理解action value：
上圖中策略已經(jīng)通過綠色箭頭畫出來了。

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

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