1
在星際爭霸（AlphaStar）和圍棋（AlphaGO）游戲中，強化學習已取得了舉世矚目的成功。 而這些成功背后的核心則是用于求解馬爾可夫決策過程（MDP）的貝爾曼最優性方程（Bellman Optimality Equation）。
可以說，貝爾曼方程在強化學習（RL）中無處不在，了解此方程的數學基礎對于理解 RL 算法的工作原理必不可少。它是由美國應用數學家理查德·貝爾曼（Richard Bellman）提出，用于求解求解馬爾可夫決策過程。
文本對此方程背后的數學基礎的進行了詳盡介紹，通俗易懂而又不失數學上的嚴格性。
好文共賞之，以下譯出原文與大家分享：
在星際爭霸（AlphaStar）和圍棋（AlphaGO）游戲中，強化學習已取得了舉世矚目的成功。 而這些成功背后的核心則是用于求解馬爾可夫決策過程（Markov decision processes，MDP）的貝爾曼最優性方程。
貝爾曼最優性方程
貝爾曼最優性方程是一個遞歸方程，可由動態規劃（dynamic programming，DP）算法求解，通過求解該方程可以找到最優值函數和最優策略。
S 表示狀態空間。
V 表示值函數。
V* 表示最優值函數。
V(s) 表示值函數在狀態為 s時的取值。
π 表示策略。
π* 表示最優策略。
π(s) 返回在狀態為 s 時策略π所采取的行動。
P 表示轉移概率矩陣。
A 表示所有可能行動的集合。
盡管我盡力讓文章易懂，但限于篇幅且要同時確保分析的嚴格性，我還是假定讀者已經了解以下預備知識：
馬爾可夫決策過程（MDP）
貝爾曼方程式以及如何使用迭代法求解此方程
RL基礎，諸如價值函數，獎勵，策略，折現因子等概念
線性代數
向量求導
如果你對 RL 和 MDP 略有研究，想必你一定會遇到過此類說法：“對于每個MDP，總有至少一個策略優于或等于所有其他策略。“
在Sutton和Barto的經典教科書中以及David Silver的系列講座中讀到或聽到這些說法時似乎非常直觀，不證自明。但是，我們必得更深入地研究并以更具體的（當然，你懂得，作者意思是數學上的具體，而非常識上的直觀）方式理解為何這么說。因此，在本文中，我將在數學上證明以下定理：
對于任何有限的MDP，都存在一個最佳策略π*，滿足其他所有可能的策略π都不會比這個策略更好。
在尋找最佳策略之前，我們需要先了解一下策略的順序。即什么時候我們認為一項策略（π1）比另一項策略（π2）好？
如果對于狀態空間中的每個狀態，使用π1派生的值函數在此狀態的值都大于或等于使用π2派生的值函數在此狀態的值，則可以說策略π1優于策略π2。數學上，可以這樣寫：
策略間的比較
既然我們已經知道如何比較策略，接下來我們需要證明始終存在一個比所有其他策略都更好的策略。 我們將使用巴拿赫不動點定理證明這一點，方法是證明貝爾曼最優算子是對帶有L-無窮范數度量的實數完備度量空間上的閉映射。 為此，我們首先說說不動點問題以及關于柯西序列的完整度量空間。
上一段聽起來很嚇人，但是一旦我們理解了每個基本術語的含義，它將變得非常容易和直觀。 所以別怕！我們接下來將一個一個地討論上段標粗體的術語。 讓我們克服我們的恐懼，以一種自下而上的方法，學習每個概念：
我相信我們大多數人都熟悉方程求根問題。 我們求使函數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*，然后使用它來解決不動點問題，如下圖所示：
求解不動點問題
這背后的直覺很簡單，如果某個函數在某個點收斂，那么該函數在那個收斂點的值就是收斂點本身。 因此，這個收斂點就是不動點。
也可以通過以下代碼從經驗上觀察到函數收斂到不動點，代碼鏈接如下：
度量空間只是一個在其上定義了度量的集合，度量則是定義了集合中任何兩個元素之間的距離。 例如，歐幾里德空間是度量空間，其距離定義為歐幾里德距離。 因此，度量空間 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)
對于度量空間（X，d），集合X中的元素組成的序列（x1，x2，x3 .... xn）是柯西序列， 如果對于任意正實數ε, 存在一個整數N，使得以下等式成立：
柯西序列
這里的數學解釋有點小復雜，還不夠直觀（然而實際定義就是這樣的）。 用簡單的話說，度量空間元素組成的序列如果在某個點收斂（它們無限接近于某個點），這個序列就是柯西序列。
如果由集合X 中元素組成的每個可能的柯西序列都收斂到集合X中的元素，則度量空間(X, d) 是完備的。 也就是說，由集合元素組成的每個柯西序列的極限所對應元素也屬于該集合， 這也是為什么它被稱為“完備”的原因。
在度量空間 (X, d) 的元素上定義的函數（算子或映射）是一個壓縮映像（或壓縮子），如果存在某個常數γ∈[0,1)，使得對于度量空間中任意兩個元素x1 和x2，滿足以下條件：
壓縮映像
這也就意味著在將元素x1 和 x2上應用了映射 f(.) 之后，它們彼此之間的距離至少在小于1的一個乘數因子γ意義下更接近 。而且，該常數的最小值被稱為Lipschitz常數（這是生成對抗網絡的重要常數）。 另外，如果γ=1，則映射不再是壓縮映射，而是短映射。 直觀上來說，在應用壓縮映射后，元素之間序列值會越來越接近。
此定理是我們證明的靈魂。非正式地講，這個定理是說，對于一個完整的度量空間，將壓縮映射一遍又一遍地應用到集合的元素上，我們最終將得到唯一的一個最優值。我們知道：
壓縮映射將集合中元素聚集到一起。
不停地運用這個壓縮映射，我們會得到一個柯西序列。
完備度量空間中的柯西序列始終會收斂到自身中的一個值。
形式上，該定理可以表述為：
令(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的可能性），因此貝爾曼算子是壓縮映射。
現在我們知道：
(X, L-infinity) 是一個完備的度量空間
貝爾曼算子B是壓縮映射
因此，根據巴拿赫不動點定理，我們得出結論，對每個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 雷鋒網雷鋒網雷鋒網
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
