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