CHINESE  INSTITUTE  OF  COMMAND  AND  CONTROL

强化学习中无处不在的贝尔曼最优性方程，背后的数学原理知多少？

发表时间：2020-06-11 14:09来源：雷锋网

在星际争霸（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-无穷范数度量的实数完备度量空间上的闭映射。为此，我们首先说说不动点问题以及关于柯西序列的完整度量空间。
上一段听起来很吓人，但是一旦我们理解了每个基本术语的含义，它将变得非常容易和直观。所以别怕！我们接下来将一个一个地讨论上段标粗体的术语。让我们克服我们的恐惧，以一种自下而上的方法，学习每个概念：

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*，然后使用它来解决不动点问题，如下图所示：

求解不动点问题
这背后的直觉很简单，如果某个函数在某个点收敛，那么该函数在那个收敛点的值就是收敛点本身。因此，这个收敛点就是不动点。
也可以通过以下代码从经验上观察到函数收敛到不动点，代码链接如下：
  • https://gist.github.com/TimeTraveller-San/8e37399d4740928a258f395413bde2e7/raw/c48fecd50fa29634eea144917f92787c3ccd7bf3/Fixed%20point%20problem.ipynb

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的可能性），因此贝尔曼算子是压缩映射。
现在我们知道：
  • (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 的贝尔曼最优方程的唯一性和最优性。
分享到：