|
在星際爭(zhēng)霸和圍棋等游戲中，強(qiáng)化學(xué)習(xí)已取得了舉世矚目的成功。而這些成功背后的核心則是用于求解馬爾可夫決策過(guò)程（MDP）的貝爾曼最優(yōu)性方程（Bellman Optimality Equation）。可以說(shuō)，貝爾曼方程在強(qiáng)化學(xué)習(xí)中無(wú)處不在，了解此方程的數(shù)學(xué)基礎(chǔ)對(duì)于理解 RL 算法的工作原理必不可少。它是由美國(guó)應(yīng)用數(shù)學(xué)家理查德·貝爾曼（Richard Bellman）提出，用于求解求解馬爾可夫決策過(guò)程。 Towards Data Science 博主 Vaibhav Kumar 在本文中對(duì)此方程背后的數(shù)學(xué)基礎(chǔ)的進(jìn)行了詳盡介紹，通俗易懂而又不失數(shù)學(xué)上的嚴(yán)格性。在星際爭(zhēng)霸（AlphaStar）和圍棋（AlphaGO）游戲中，強(qiáng)化學(xué)習(xí)已取得了舉世矚目的成功。而這些成功背后的核心則是用于求解馬爾可夫決策過(guò)程（Markov decision processes，MDP）的貝爾曼最優(yōu)性方程。貝爾曼最優(yōu)性方程是一個(gè)遞歸方程，可由動(dòng)態(tài)規(guī)劃（dynamic programming，DP）算法求解，通過(guò)求解該方程可以找到最優(yōu)值函數(shù)和最優(yōu)策略。 一、本文將涉及到的數(shù)學(xué)符號(hào)二、預(yù)備知識(shí)盡管我盡力讓文章易懂，但限于篇幅且要同時(shí)確保分析的嚴(yán)格性，我還是假定讀者已經(jīng)了解以下預(yù)備知識(shí)：三、理解貝爾曼方程的幾大要點(diǎn)如果你對(duì) RL 和 MDP 略有研究，想必你一定會(huì)遇到過(guò)此類說(shuō)法：“對(duì)于每個(gè)MDP，總有至少一個(gè)策略優(yōu)于或等于所有其他策略?！?/span>在Sutton和Barto的經(jīng)典教科書中以及David Silver的系列講座中讀到或聽到這些說(shuō)法時(shí)似乎非常直觀，不證自明。但是，我們必得更深入地研究并以更具體的（當(dāng)然，你懂得，作者意思是數(shù)學(xué)上的具體，而非常識(shí)上的直觀）方式理解為何這么說(shuō)。因此，在本文中，我將在數(shù)學(xué)上證明以下定理：對(duì)于任何有限的MDP，都存在一個(gè)最佳策略π*，滿足其他所有可能的策略π都不會(huì)比這個(gè)策略更好。 在尋找最佳策略之前，我們需要先了解一下策略的順序。即什么時(shí)候我們認(rèn)為一項(xiàng)策略（π1）比另一項(xiàng)策略（π2）好？如果對(duì)于狀態(tài)空間中的每個(gè)狀態(tài)，使用π1派生的值函數(shù)在此狀態(tài)的值都大于或等于使用π2派生的值函數(shù)在此狀態(tài)的值，則可以說(shuō)策略π1優(yōu)于策略π2。數(shù)學(xué)上，可以這樣寫：既然我們已經(jīng)知道如何比較策略，接下來(lái)我們需要證明始終存在一個(gè)比所有其他策略都更好的策略。我們將使用巴拿赫不動(dòng)點(diǎn)定理證明這一點(diǎn)，方法是證明貝爾曼最優(yōu)算子是對(duì)帶有L-無(wú)窮范數(shù)度量的實(shí)數(shù)完備度量空間上的閉映射。為此，我們首先說(shuō)說(shuō)不動(dòng)點(diǎn)問(wèn)題以及關(guān)于柯西序列的完整度量空間。上一段聽起來(lái)很嚇人，但是一旦我們理解了每個(gè)基本術(shù)語(yǔ)的含義，它將變得非常容易和直觀。所以別怕！我們接下來(lái)將一個(gè)一個(gè)地討論上段標(biāo)粗體的術(shù)語(yǔ)。讓我們克服我們的恐懼，以一種自下而上的方法，學(xué)習(xí)每個(gè)概念：1. 不動(dòng)點(diǎn)問(wèn)題我相信我們大多數(shù)人都熟悉方程求根問(wèn)題。我們求使函數(shù)f(x) = 0的點(diǎn)x。在不動(dòng)點(diǎn)問(wèn)題中，我們則求解使得f(x) = x的點(diǎn)x。 顧名思義，點(diǎn)x是一個(gè)不動(dòng)點(diǎn)，就是說(shuō)即使在其上應(yīng)用函數(shù)f(x)，它的值也不會(huì)改變。通過(guò)構(gòu)造另一個(gè)函數(shù) g(x) = f(x)-x = 0，不動(dòng)點(diǎn)問(wèn)題可以轉(zhuǎn)化為方程求根的問(wèn)題。實(shí)際上，方程求根問(wèn)題也可以轉(zhuǎn)換回求不動(dòng)點(diǎn)問(wèn)題。但是（在特定情況下）解決不動(dòng)點(diǎn)問(wèn)題更容易，這使得不動(dòng)點(diǎn)問(wèn)題變得非常有趣和有用（節(jié)省了計(jì)算開銷）。要解決不動(dòng)點(diǎn)問(wèn)題，隨機(jī)選擇一個(gè)x的作為起始值，并無(wú)限次重復(fù)應(yīng)用f(x)。如果“函數(shù)是收斂的”，那么你將找到不動(dòng)點(diǎn)問(wèn)題的解。從數(shù)學(xué)上講，這很簡(jiǎn)單，讓我們先介紹一個(gè)符號(hào)：記號(hào)fn(x)表示在x點(diǎn)上連續(xù)應(yīng)用n次函數(shù)現(xiàn)在，如果函數(shù)是收斂的，那么它必須收斂到某個(gè)值，比方說(shuō)， x*。下面論證則是要說(shuō)明這個(gè)值 x*確實(shí)是不動(dòng)點(diǎn)問(wèn)題的解：讓我們選擇一任意值 x0并在其上無(wú)限次應(yīng)用函數(shù)f(.)以獲得 x*，然后使用它來(lái)解決不動(dòng)點(diǎn)問(wèn)題，如下圖所示：這背后的直覺很簡(jiǎn)單，如果某個(gè)函數(shù)在某個(gè)點(diǎn)收斂，那么該函數(shù)在那個(gè)收斂點(diǎn)的值就是收斂點(diǎn)本身。因此，這個(gè)收斂點(diǎn)就是不動(dòng)點(diǎn)。也可以通過(guò)以下代碼從經(jīng)驗(yàn)上觀察到函數(shù)收斂到不動(dòng)點(diǎn)，代碼鏈接如下：2. 度量空間度量空間只是一個(gè)在其上定義了度量的集合，度量則是定義了集合中任何兩個(gè)元素之間的距離。例如，歐幾里德空間是度量空間，其距離定義為歐幾里德距離。因此，度量空間 M 可表示為(X, d) ，其中X是集合，d 是某種度量。一個(gè)度量d 必須滿足以下四條性質(zhì)：3. 柯西序列對(duì)于度量空間（X，d），集合X中的元素組成的序列（x1，x2，x3 .... xn）是柯西序列， 如果對(duì)于任意正實(shí)數(shù)ε, 存在一個(gè)整數(shù)N，使得以下等式成立：這里的數(shù)學(xué)解釋有點(diǎn)小復(fù)雜，還不夠直觀（然而實(shí)際定義就是這樣的）。用簡(jiǎn)單的話說(shuō)，度量空間元素組成的序列如果在某個(gè)點(diǎn)收斂（它們無(wú)限接近于某個(gè)點(diǎn)），這個(gè)序列就是柯西序列。4. 完備度量空間如果由集合X 中元素組成的每個(gè)可能的柯西序列都收斂到集合X中的元素，則度量空間(X, d) 是完備的。也就是說(shuō)，由集合元素組成的每個(gè)柯西序列的極限所對(duì)應(yīng)元素也屬于該集合， 這也是為什么它被稱為“完備”的原因。5. 壓縮映像在度量空間 (X, d) 的元素上定義的函數(shù)（算子或映射）是一個(gè)壓縮映像（或壓縮子），如果存在某個(gè)常數(shù)γ∈[0,1)，使得對(duì)于度量空間中任意兩個(gè)元素x1 和x2，滿足以下條件：這也就意味著在將元素x1 和 x2上應(yīng)用了映射 f(.) 之后，它們彼此之間的距離至少在小于1的一個(gè)乘數(shù)因子γ意義下更接近 。而且，該常數(shù)的最小值被稱為L(zhǎng)ipschitz常數(shù)（這是生成對(duì)抗網(wǎng)絡(luò)的重要常數(shù)）。另外，如果γ=1，則映射不再是壓縮映射，而是短映射。直觀上來(lái)說(shuō)，在應(yīng)用壓縮映射后，元素之間序列值會(huì)越來(lái)越接近。6. 巴拿赫不動(dòng)點(diǎn)定理此定理是我們證明的靈魂。非正式地講，這個(gè)定理是說(shuō)，對(duì)于一個(gè)完整的度量空間，將壓縮映射一遍又一遍地應(yīng)用到集合的元素上，我們最終將得到唯一的一個(gè)最優(yōu)值。我們知道：令(X, d)是一個(gè)完備的度量空間，函數(shù)f: X->X是一個(gè)壓縮映射，則f具有唯一一個(gè)不動(dòng)點(diǎn) x*∈ X (即，f(x *)=x *) ，使得序列 f(f(f(…f(x))))收斂至x *。 現(xiàn)在，為了數(shù)學(xué)上證明這一點(diǎn)，我們需要證明x *的唯一性和存在性。唯一性：我們將通過(guò)反證法證明這一點(diǎn)。我們假設(shè)收斂值不是唯一的，并且x1*和x2 *是壓縮映射序列收斂的兩個(gè)值，那么我們會(huì)有：x1 *和x2 *是最優(yōu)值，壓縮映射已在這兩點(diǎn)收斂，距離不再會(huì)變。此外，注意到f是壓縮映射，因此必須具有以下性質(zhì)：
現(xiàn)在，由于γ∈[0,1)，無(wú)法同時(shí)滿足等式1和2，導(dǎo)出矛盾（因?yàn)榇颂幖俣▋牲c(diǎn)距離大于零）。因此，我們的假設(shè)是錯(cuò)誤的，x *必是唯一的。存在性 現(xiàn)在我們已經(jīng)證明x *是唯一的，我們還需要證明x *存在。令(x1, x2, x3, …. xn)為重復(fù)應(yīng)用壓縮映射所形成的序列。重復(fù)應(yīng)用壓縮映射所形成的序列的通項(xiàng)如果我們假設(shè)序列(x1, x2, x3, …. xn)是柯西序列，我們知道該序列將收斂到某個(gè)點(diǎn)，例如，x *。而且，由于度量空間是完整的，所以該收斂點(diǎn)x *屬于度量空間(X,d)?，F(xiàn)在，我們只需要證明此序列是柯西序列即可。我們?nèi)⌒蛄兄衳n和xm中兩個(gè)元素，使得m >> n，并使得m足夠大，然后通過(guò)重復(fù)應(yīng)用度量d的三角形不等式性質(zhì)來(lái)證明此序列是柯西序列， 我們有：我們可進(jìn)一步將d(xm, xn)化為如下形式 ：現(xiàn)在，通過(guò)選擇一個(gè)足夠大的n，我們可以使上式的右邊小于任何正實(shí)數(shù) ε 。因此，序列序列(x1, x2, x3, …. xn)是柯西序列，并且存在最優(yōu)的x *∈X。這就證明了巴拿赫不動(dòng)點(diǎn)定理。四、回到貝爾曼最優(yōu)性方程對(duì)于值函數(shù)V(s)，我們定義一個(gè)新的算子，即最優(yōu)貝爾曼算子B，它接受一個(gè)值函數(shù)并返回一個(gè)新的值函數(shù)。具體地，我們將此算子定義如下：可以很容易地觀察到， B是一個(gè)遞歸算子。因此，對(duì)初始值函數(shù)重復(fù)運(yùn)用此算子將生成一系列值函數(shù)。如果我們可以證明B確實(shí)是某個(gè)度量空間(X,d)上的壓縮映射，那么根據(jù)巴拿赫不動(dòng)點(diǎn)定理，我們可以得出結(jié)論，最優(yōu)貝爾曼算子的重復(fù)應(yīng)用最終將導(dǎo)出唯一的最優(yōu)值函數(shù)函數(shù)，通過(guò)值函數(shù)可以得到最優(yōu)策略。因此，我們的工作現(xiàn)在都簡(jiǎn)化為證明B是壓縮映射。首先，讓我們定義度量空間如下：度量空間(X,d)：集合X是值函數(shù)的取值空間，定義如下：值函數(shù)屬于實(shí)數(shù)集。下面的 X 表示整個(gè)值函數(shù)的集合，上面的 X表示值函數(shù)在單個(gè)狀態(tài)上的值域。（注：下文提到的所有 X 指的是下面的 X）對(duì)此度量空間，我們使用的L-無(wú)窮范數(shù)定義如下：
根據(jù)此度量空間范數(shù)的定義，兩個(gè)值函數(shù)之間的距離等于兩個(gè)值函數(shù)向量各方向絕對(duì)值之差的最大值。同樣，對(duì)于有限獎(jiǎng)勵(lì)的有限MDP，值函數(shù)將始終在實(shí)數(shù)空間中。因此，此有限空間是完備的。定理：貝爾曼算子B是有限空間(X, L-infinity)上的壓縮映射 證明：假設(shè)V1和V2是兩個(gè)值函數(shù)。則：在上面的第二步中，我們通過(guò)用a代替第二個(gè)值函數(shù)中的a'來(lái)引入不等式。這是因?yàn)橥ㄟ^(guò)將最優(yōu)動(dòng)作a替換為其他動(dòng)作 a'，我們降低了其總價(jià)值，從而引入了不等式。 在上面的第四步中，我們通過(guò)在狀態(tài)空間 s'上取最大值來(lái)移除L-無(wú)窮范數(shù)（回想一下在前面我們關(guān)于值函數(shù)的L-無(wú)窮范數(shù)的定義） 在最后一步中，因?yàn)楦怕屎褪冀K為1，我們消去了求和號(hào)。
最后，在貝爾曼最優(yōu)性方程中，由于γ∈[0,1)（現(xiàn)在暫時(shí)忽略γ= 1的可能性），因此貝爾曼算子是壓縮映射。因此，根據(jù)巴拿赫不動(dòng)點(diǎn)定理，我們得出結(jié)論，對(duì)每個(gè)MDP，存在唯一的最優(yōu)值函數(shù)V *，使用這個(gè)值函數(shù)，我們可以得到最優(yōu)策略π *。因此證明，對(duì)于任何有限的MDP，都存在一個(gè)最優(yōu)策略π *，不差于其他所有可能的策略π。那么，問(wèn)題來(lái)了，如何找到這種最優(yōu)的策略和值函數(shù)呢？一種方法就是在隨機(jī)初始值函數(shù)上重復(fù)運(yùn)用貝爾曼算子以獲得最佳函數(shù)。但是，這在計(jì)算上非常耗時(shí)，此法經(jīng)常是完全不可行的。因此，我們要使用諸如值和策略迭代之類的迭代方法或諸如Q-Learning或SARSA之類的時(shí)間差分方法。有關(guān)更多信息，請(qǐng)參閱：五、總結(jié)我們了解了一些基本的數(shù)學(xué)工具，例如度量空間，完備度量空間，柯西序列，壓縮映射和巴拿赫不動(dòng)點(diǎn)定理?；谶@些數(shù)學(xué)工具，我們?cè)跀?shù)學(xué)上證明了用于求解 MDP 的貝爾曼最優(yōu)方程的唯一性和最優(yōu)性。via https:///mathematical-analysis-of-reinforcement-learning-bellman-equation-ac9f0954e19f 直播預(yù)告【時(shí)間】2020年2月22日晚20:00
|
