在上一篇文章中，我們介紹了一種最簡單的MDP——s與a都是有限的MDP的求解方法。其中，我們用到了動態規劃的思想，并且推出了“策略迭代”、“值迭代”這樣的方法。今天，我們要來講更加一般的最優控制問題——t、a與s都是連續的問題。我們仍然假定我們已經清清楚楚知道環境與目標。我們將介紹求解的方法，并引出Hamilton-Jacobi-Bellman方程（簡稱H-J-B方程）。其中，H-J-B方程是一個t連續定義下的方程，它的離散t的版本被稱作Bellman方程。這在強化學習中是極其重要的。

最優控制問題

在最優控制中，我們一般用x來代表狀態，用u來代表“控制”，即可以人為輸入的東西，和MDP中的動作a是同一個概念。另外，在最優控制中，我們一般不是嘗試“極大化獎勵”，而是嘗試“極小化損失”，也就是說，我們的目標往往是用一個求極小化的形式表現出來（只要加上一個負號就可以實現二者的轉化）。除此之外，最優控制與MDP最大的不同在于其t是連續的。在進行了概念的對應之后，最優控制的邏輯和MDP都是一樣的。

按理說，s與a是連續的時候，也可以將動作、狀態的轉移建立為一個概率方程。例如給出在

采取 之后，下一個狀態 的連續概率分布。但是在最優控制中，t是一個連續的變量，狀態轉移一般采用微分方程 的形式來表示。為簡單起見，我們本章中只討論沒有隨機性的情況。

一般的最優控制問題有如下幾部分組成（用x記狀態、用u記控制/動作）。首先是給定初始與終止的時間

（有些情況下終止時間不是給定的）、初始的狀態 ，然后，給出狀態的轉移關系：

如果問題是time-invariant的，則可以去掉t變量，即變成

。函數a記錄了狀態x與u之間的轉移關系，常常被稱為“動力系統”（Dynamic），和MDP中的“環境”相對應，不過沒有隨機性。這也就是說，對于確定的初始狀態 ，只要控制的路徑 是確定的，則整個過程中的 都是確定的。

問題的目標是極小化損失函數：

同理，對于time-invariant的問題，f中的t變量可以省略。作為目標的損失函數分成兩個部分，一個是在路徑上累積損失，用f記錄，另一個是最終狀態對應的損失，用H記錄。路徑上的累積損失意思是在時間微元

與 之間，損失為 記錄。最終狀態對應的損失則描述最終狀態的好壞。我們相信，最終狀態是重要的，所以不能只用一個微元來描述，而是要單獨用H來衡量。

很多問題可以轉化為最優控制問題。例如對于一個在平地上開汽車的問題，限定一定時間內（截止為

）從出發點到終點。狀態可以是當前位置、當前速度，以及當前加速度的三維向量。而控制可以是油門與剎車的二維向量。問題的Dynamic為位置、速度、加速度瞬時之間的轉移關系，可以用一個微分方程表示出來。而損失則考慮的是耗油量與耗費的時間——在路上的每一個瞬間，汽車的耗油量都與當前速度與加速度有關，總的耗油量由積分得出；另外，我們希望越早到達越好，越晚則損失越大。這個量是值得重視的，所以不能將其作為一個最終時刻 附近微元 內的損失，而應該將其特別拿出來專門討論。綜合以上，我們可以得到一個基本的最優控制問題：

有了最優控制問題之后，我們當然可以開始對其進行求解。這里的t、a與s都是連續的，而對于狀態轉移方程函數

以及表示損失的函數f與H，我們可能對其進行簡單的建模，例如認為位移、速度與加速度之間就是線性的關系。但是，我們也可以考慮更復雜的現實因素，例如汽車受到的阻力與速度有關、在各個速度檔位油門性能不一樣等等，繼而將問題建模為很復雜、高度非線性的、time-varing的模型。對于這樣的問題，我們恐怕根本無法求出其解析解，只能將x與u離散化，以求其數值解。
作為最優控制的例子，我們可以先考慮一種最簡單的、可以求出解析解的最優控制問題。那么，怎么才算是“最簡單”呢？
首先，我們希望Dynamic 是線性的，并且問題是time-invariant的。即Dynamic是 。某種意義上，如果讓Dynamic“稍微復雜一些”，比如是一個二次函數，問題就很可能求不出解析解。因為這會對應于一個ode理論中經典的里卡蒂方程（Ricatti Equation），有很大概率沒有解的解析式。所以，我們只能將Dynamic設定為線性的。

然后考慮損失函數

。由于這是我們要極小化的目標，如果它是線性的，就會存在沒有最小值的情況，所以說“不能太簡單了”。我們只能設定其為“次簡單”的正定二次函數的形式，并當然希望它也是time-invariant的。即 ，其中 是正定矩陣。一種更加簡單，也很常見的情況是忽略狀態與控制的交錯項 。此外，我們一般將最終狀態的損失函數設定為x的正定二次函數。

這種Dynamic是線性（Linear），而損失函數是二次函數（Quadratic）的情況是最簡單的一類最優控制問題，我們將其稱作LQR（Linear-Quadratic Regulator）。一個time-invariant的，并且沒有狀態與控制的交錯項的LQR，就是我們所找尋的“最簡單的”問題：

上述的LQR是最優控制中最簡單，同時也是最經典的一類問題，常常被作為最優控制教材的“入門問題”出現。對于這類問題，我們可以不對x與u進行離散化，而直接精確地求出其最優解的表達式。

針對不同的最優控制問題，或簡單，或復雜，我們同樣利用動態規劃的思想，可以有幾種不同的解法。其中最主要的問題是，我們是否要對連續的t進行離散化。如果對t進行離散化之后，對于簡單的LQR問題，我們有比較簡單的方法求出解析解（不用對x與u離散化）。而對于非線性的系統，我們則只能對x與u進一步離散化，求近似的數值解；如果我們選擇不對t進行離散化，則可以將問題轉化為一個偏微分方程，也就是我們今天的主題Bellman方程。（有許多非線性pde求不出解析解，同樣只能求數值解，但這又是另一個問題了）。這幾種情況中，核心的思想都是動態規劃。

下面，我們就來一一介紹這些方法。

離散化t求數值解

面對t連續的問題，尤其是非線性的、復雜的問題，我們無法求出精確的解析解。所以，將t離散化不失為一種明智之舉。

將t離散化之后，關于t的連續函數

變成了狀態序列 與決策序列 。一般的最優控制問題化為了如下形式：

我們首先來講LQR問題的求解方法。這個過程中要利用到我們上一章動態規劃的思想，以及對于“價值”的定義。我們不妨設t是從0到100的：
首先，我們已知在最終狀態下，狀態

的價值是 。
然后，我們考慮t=99的時候，已知狀態 處采取控制 ，則 故而會得到最終狀態的損失為 。在t=99的瞬間，我們還得到了瞬間的損失 。這就意味著，如果我們在 采取 ，接下來我們一共會獲得 的損失——這是一個關于與的正定二次函數。在固定的情況下，我們求 應該取值多少才能使其最小。易知這可以求得 關于 的一個線性表達式，我們將其記為。其中 是一個矩陣。將這個表達式代入 ，則可以將 化為一個關于 的正定二次函數，我們將其記為 。總的來說，我們在這一步中得到了兩個東西，一個是在 應該采取何種控制，表達式為 。另一個是 處的“價值”，或者說從 出發，其后面最小能夠獲得的懲罰是多少。其表達式為 。

接著，我們考慮t=98的時候，

處采取 ，則會讓 。所以， 處采取 會導致 的立即損失，以及 的后續損失。我們同樣可以仿照上面的方法，求出最佳控制 關于 的表達式 ，以及t=98時候， 的“價值” 。與t=99時候一樣，最佳控制關于狀態是一個線性表達式，而“價值”關于狀態則是一個正定二次函數。

接下來，我們可以不斷地重復這個過程。由于LQR的定義——Dynamic是線性，而懲罰函數是二次的這個性質，最佳控制

都是一個線性表達式 ，而 的價值也都是定二次函數 。要注意的是，迭代的每個步驟中，我們只有 以及“價值”關于 的表達式，而沒有 的具體值，所以我們也不知道$u_i$的具體值。我們必須將所有中間的表達式， 與 保留下來，才能重復向前迭代。

我們一直重復這個迭代過程，直到初始狀態

。而由于 是給定的，所以我們可以計算出 。然后同理可以依次計算出 ，繼而將整個路徑與決策序列計算出來。由于每一步中，我們所求的都是讓后續損失最小的控制，所以我們求出的決策路徑正是最佳的。

對于非線性的問題，我們也想要仿照上述的方法。但是，如果將過程中每一步的最佳控制與價值表達為狀態的解析表達式，可能會得到極其復雜的表達式。例如，如果將LQR中的Dynamic從線性的形式改為二次的形式，則我們會發現迭代了幾步之后就無法再迭代下去了。對于這樣的情況，我們無法求解析解，只能考慮通過離散化x與u來求數值解。

例如，我們將x、u離散化為10段得到一個狀態有共10種，控制有

共10種的問題（這里，我們 表示第8種狀態，而不表示t=8時候的狀態）。這樣，我們就可以將其化作上一節我們所說的s、a有限的MDP求解。要注意的是，這種情況事實上比上一節討論的問題要簡單。在上一節中，我們的模型是——如果在s采取a，就會“以一定的概率”進入下一個狀態。而在本節中，我們所討論的模型都是有確定性的。但是，對于高度非線性的復雜系統，離散化之后得到的模型同樣會十分復雜。例如Dynamic可能在x與u離散化之后變為一堆“在t=48時， 采取 會進入 ”，或者是“在t=36時， 采取 會進入 ”形式的規則，而懲罰函數也會同樣變得十分復雜。下面，我們說明求數值解的解法：

首先，考慮所有最終狀態對應的價值：

。這些價值代表的是，當t=100的時候，從 出發，還能獲得多少的獎勵。事實上，t=100時候，問題已經終止了，所以就只能獲得一個“最終狀態損失”。

然后，計算t=99的時候從所有狀態出發時能夠獲得的價值。我們應該遍歷能夠采取的控制u，來計算每個狀態的價值。例如對于狀態$x_1$，采取$u_1$控制會讓其進入$x_8$的狀態，那么它就能在t=99到t=100的瞬間內獲得$f(x_1,u_1,t)$的“累積損失”，并且獲得$H(x_8)$的“最終狀態損失”。我們對狀態$x_1$計算每一個$u_i$帶來的“累積損失”與“最終損失”之和，挑出其中最小的（注意最優控制問題的目的是要讓損失最小）。我們可以得到一個這樣的結論：在t=99的時候，對于狀態$x_1$，采取$u_3$是最好的，它可以讓后面發生的損失低至48.4。此時，我們就將48.4記作$x_1$的“價值”。

接著，計算t=98時候所有狀態x的價值，以及其對應的最佳控制u。這個過程要用到上一個步驟的數據，例如t=98時，在$x_1$采取$u_1$，除了會立即獲得一個“累積損失”之外，還會在t=99的時候就會進入$x_6$。而t=99的時候$x_6$到底好不好，我們就要參考上一個步驟計算出的各個$x_i$在t=99時候的價值。這個步驟結束后，我們可以得到形如這樣的結論：t=98時，對于狀態$x_1$，采取$u_2$是最好的。它可以讓后面發生的損失低至84.8。然后，我們就將84.8記作$x_1$的“價值”。
接下來，不斷向前迭代上述步驟。要注意的是，迭代的每個步驟中必須將所有的中間結果保留下來。例如在t=84的時候$x_1$的價值很大，也就是說t=84時候進入$x_1$后面會面臨很大的損失，所以不是一個好的選擇。但是你不能因此就將這條數據丟掉，因為說不定你的前半程可以只用很小的損失來到這個狀態。我們不斷向前迭代算法直到t=1的時刻。當我們算出t=1的時刻，各個狀態x對應的最優控制u與價值的時候，我們就可以考慮在t=0的初始狀態

中，該采取什么控制u，才能在t=1時候進入價值最小（最優控制中價值是越小越好）的x。然后，可以根據迭代過程中每一個步驟記錄的數據，將一路上各個時間點處于什么x、應該采取什么u都給反推出來，以找到最優的控制序列，兌現最小的價值。整個過程如下圖所示：

對于原本的問題，由于有100個回合，每個回合都有10種控制，所以有

種情況。但是我們的迭代方法中，由于利用了“價值”來保存并傳遞中間結果，每一步只需要計算10種x與10種u對應的情況，共計算100次。即使重復100步，一共也只需要10000次的計算量，將指數復雜度變成了線性復雜度。

細心的讀者可能發現了，我們上面講到的兩種迭代本質上是一樣的，都是要向前求出“最佳控制”與“價值”關于當前狀態的表達式。在LQR中，由于表達式是線性的，或者是二次的，所以我們可以真真切切地把解析表達式求出來。而在復雜的非線性問題中，由于我們求不出解析式，所以我們只能用離散化的方法，用一張表格的形式記錄狀態與“最佳控制”以及“價值之間”的對應關系?？梢韵胂?#xff0c;如果將表格記錄的內容可視化，我們會看到一個高度非線性、無法求出表達式的函數圖像。

上面所說的方法和我們上一章講的“井字過三關”的思路其實是一樣的，都是對狀態建立“價值”，然后向前迭代求解。并且，因為我們的模型是確定性的，所以每次計算價值的時候不用計算期望，所以計算過程事實上還要簡單很多（在“井字過三關”中，我們由于利用了畫圖求解的直覺，以及對稱性，所以省略了很多步驟。如果將其嚴謹寫出來會很繁瑣）。

對于LQR問題來說，我們采用解析式迭代的方法可以求出比較精確的解。但是對于非線性的問題來說，離散化的時候我們會面臨計算復雜度與精度的權衡取舍。因為在離散化的時候，我們可以人為地選擇將x分成10個不同的狀態，也可以分成100個不同的段。如果我們選擇將x與u均分為更多的段，這意味著結果的精度更高，但同時也意味著計算的時間復雜度會更多；如果將x與u只分成較少的段，計算的時間復雜度會降低，但是計算的精度卻會下降。并且由于算法是迭代的，這種誤差傳遞到后面可能會變得很大。如何權衡取舍這兩者得到綜合最佳？這并不是一個簡單的問題，需要視具體情況而定。

H-J-B方程

在上面一節中，我們首先對t進行了離散化，然后再針對問題簡單與復雜的情況，分別介紹了求解析解以及離散化求數值的方法，它們都是通過迭代而實現的。那么，我們現在的問題是，能不能不要對t進行離散化，而是把t作為連續變量來直接求解析解呢？答案是肯定，并且，這正是我們本節主題——H-J-B方程的內容。

事實上，推出H-J-B方程可以說和我們上一節思路是完全一樣的，只不過是將時間的差分

變得無限小，使之變成了微分。
定義一個價值函數 。這里的“價值” 代表的也是從指定時間t、指定狀態x出發，后續最小懲罰的表達式。這和我們上面所定義的“價值”——LQR問題中迭代到 時候的 ，非線性情況中迭代到 時候生成的x與V之間的表格——在邏輯上是一樣的，只是t變成了連續變量而已。

在最佳$u(t)$作用下，我們能夠獲得的總價值為

，即從初始時 開始算起的價值；另外，我們還有恒等式 。這條恒等式和我們上節迭代算法中第一步用到的初始條件——LQR問題中 ，以及非線性問題中最初 時候的表格——在邏輯上是一樣的。

根據

的定義，有公式：
對 進行泰勒展開，得：
將上面兩個式子相減，再除以$dt$，并且讓$dt$趨于0，得到以下方程：

這個過程可以類比于上一節中我們從后向前迭代推出V表達式的過程。本質上，V是一個關于x與t的二元函數。上一節中，我們迭代中將V拆分成了

時分別關于x的表達式。t相同時候，x不同對V的影響體現出了 。而按照時間順序迭代的過程體現的是 。所以說，這條微分方程事實上和上一節中，我們向前迭代的算法是相對應的。
將環境 代入，則得到最終的方程：

這個方程就是大名鼎鼎的H-J-B方程。我們將

稱作是一個“哈密頓量”（Hamiltonian），記作H。由于動力系統 與懲罰 的表達式已知，而 中不含 ，所以我們可以哈密頓量關于 的梯度，繼而求出能夠最小化哈密頓量的 ，得到它關于 的表達式。這個步驟和上一節迭代算法中求出 ，或者求出u與x的對應表格那個步驟相對應。
將 關于 的表達式代入方程之后，待求解的 是一個二元函數，并且方程中同時出現了它對于兩個變元x與t的偏導數。此外，我們還有邊界條件 ，所以這是一個非常典型的偏微分方程。
這里貼一個公開課上H-J-B方程的截圖。要注意其使用的符號可能與我們有所出入：

下面，我們來看一個求解H-J-B方程的簡單的例子：

環境方程為

；
懲罰函數為 ；
首先，我們有哈密頓量 。

它關于u的導數為：

解出H關于u的一個駐點為

。

然后，我們發現

，故而駐點 確實是H的全局極小點。

這也就意味著，

我們將

簡記為 ，把 簡記為 ，列出以下的H-J-B方程：

方程：

邊界條件：

這就是一個典型的關于二元函數

的pde。由于這個問題本身也是一個LQR問題，所以我們可以猜測其解具有 的形式（解pde時，我們常常會利用這種連蒙帶猜的方法）。將其帶回方程中進行化簡，可以得到：

這便是我們所求的最優控制問題的解析解。

細心的讀者可能想到，我們舉的這個例子其實也是一個“最簡單”的LQR問題。如果這不是一個LQR問題，而是一個更加復雜的非線性問題，我們還能這樣求解嗎？實話實說，我們只能保證可以按照H-J-B方程的定義將pde列出來，但是卻不能保證求出解析解，因為有許多pde是沒有辦法求解析解。對于這樣的pde，唯一的方法仍是求數值解。而一旦我們考慮求數值解，那又要離散化t。這也意味著，求H-J-B方程數值解的過程，事實上和上一節講的離散化t求迭代算法是完全等價的。所以說，離散與連續之間可以相互轉化——離散問題的極限情況有助于我們理解連續的方程是怎么推導出來的，而連續方程有時候又要借助離散化來求近似的數值解。

總的來說，只有在問題比較簡單，例如LQR問題的情況下，我們可以離散化t以求迭代的解析式，也可以不離散化t，直接求解H-J-B方程的解析解；而在問題比較復雜的問題中，我們只能求數值解。哪怕是列出了H-J-B方程，還是只能求方程的數值解。

這兩期的總結

最優控制中有兩大類算法，一類是動態規劃與H-J-B方程，另一類是變分法與龐特里亞金原理。在上一章與本章中，我們著重講了動態規劃與H-J-B方程。它有一個基本的思想，即把全局最優的解的每一個部分單獨挑出來也是最優解。根據這個原理，就可以將一個整體的問題給拆分成局部的小問題，依次求解，大大地節省計算量（從指數復雜度降低到線性復雜度）。用來連接“大問題”與“小問題”的量就是“價值”V。我們講到的所有算法都圍繞著“價值”的計算和極大化而展開。

在這兩章中，我們講的問題給人一種感覺——只有比較簡單的幾類的最優控制問題可以解決。第一類是s與a（或者x與u）都是離散的，它們之間具有確定性的轉移關系的。我們可以用本文中第二節的迭代方法解決；第二類是s與a都是離散的，它們之間具有隨機轉移關系的。這類方法和第一類差別并不大，只要加一個期望就行了。由于我們討論的是完全已知模型的情形，所以期望公式可以直接得到；第三類是s與a是連續的，但是其中的轉移關系是比較簡單的，比如LQR。其他的問題，例如s與a是連續的，并且轉移關系很復雜的情況，是沒有辦法求解的，只能通過離散化使之成為第一類來求近似的數值解。

在強化學習中，有兩種解決問題的思路，一種是基于價值的方法，另一種是基于policy的方法。其中，基于價值的方法正是從最優控制問題中動態規劃方法發展而來，它同樣也是通過擬合“價值”來求解最佳策略。不過，強化學習還將動態規劃的思路結合了深度學習的方法。在最優控制中，我們認為只有s與a之間關系是簡單的線性關系時才能求解析式，而當它們關系是復雜的非線性關系時，就只能先離散化s與a，再用一個表格的形式去記錄s與a的對應關系。但是，當我們有了神經網絡這個工具后，我們就可以嘗試去擬合任意復雜的非線性函數，無論是s與a之間或是s與V之間的關系。這也使得我們不必拘泥于上面三種簡單的情況，而可以考慮更加復雜的情況。

另一方面，強化學習也有十分困難的地方。例如在這兩章中，我們都假定完全已知模型。這才導致s與a之間的轉移關系具有隨機性的時候不會顯著增加問題的難度——因為我們已知轉移概率，可以直接列出期望的表達式。但是，當我們未知模型的時候，如何能夠準確地近似出V？如何減小估算的偏差與方差？如何避免局部收斂？這就涉及到探索-利用（explore-exploit），同策略-異策略（on-policy）之間的取舍，大大地增加了問題的復雜度。這些我們接下來都會慢慢講到。

總結

以上是生活随笔為你收集整理的运筹学状态转移方程例子_强化学习第4期：H-J-B方程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。