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