- 强化学习基础 (1) 多臂赌博机
- 强化学习基础 (2) 有限马尔可夫过程
- 强化学习基础 (3) 动态规划求解
引言
动态规划 (Dynamic Programming, DP) 是指用于求解MDP问题的最优策略的一系列算法。
在解决实际的强化学习问题时，使用动态规划的场景并不多。因为动态规划算法需要大量的计算开销，并且要求对环境有完美的建模。然而，DP算法是其他强化学习算法的理论基石。现代的强化学习算法（如策略梯度算法等），都可以是对DP算法的一个近似，利用较少的计算开销以及不完整的环境建模，来达到尽可能接近DP算法的效果。
DP算法的核心思想在于：利用 价值函数 来指导和描述能够得到最优策略的搜索方法。
从上一篇文章我们得知，当我们已知最优的价值函数（无论是状态价值函数 $v_{}$ 还是动作价值函数 $q_$），我们就可以轻易求出最优的策略。而最优价值函数满足以下的 贝尔曼最优方程：
\[\begin{equation} \begin{aligned} v_{*}(s) &=\max_a\mathbb{E}_\pi[ R_{t+1} + \gamma v_{*}(S_{t+1}) \mid S_t=s,A_t=a]\\ &=\max_a\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{*}(s') \right]\\ q_{*}(s,a) &=\mathbb{E}_\pi[ R_{t+1} + \gamma \max_{a'}q_*(S_{t+1},a') \mid S_t=s,A_t=a]\\ &=\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\max_{a'}\gamma q_*(s',a') \right]\\ \end{aligned} \end{equation}\]下面我们将看到，DP算法实际上就是以贝尔曼最优方程作为状态更新的规则，通过多次迭代来逼近最优的价值函数。
最常用的DP算法有两种，分别称为 策略迭代 和 值迭代。
一、策略迭代
策略迭代 (policy iteration) 是一种求解最优策略 $\pi_*$ 的一种迭代方法。在每一步迭代中，主要包含两个步骤：
- 策略评估 (policy evaluation)：求解当前策略 $\pi_i$ 的状态价值函数 $v_{\pi_i}$；
- 策略提升 (policy improvement)：根据状态价值函数，找到更好的策略 $\pi_{i+1}$。
下面我们将会说明，经过一轮策略迭代后得到的新策略 $\pi_{i+1}$ 总是会比旧策略 $\pi_i$ 更好（除非 $\pi_i$ 已经是最优策略）。
由于在有限MDP中策略的总数是有限的，因此只要迭代步数足够多，策略迭代总能够收敛到最优的策略和最优的价值函数。
1.1. 策略评估
我们已经知道，状态价值函数满足下面的 贝尔曼方程:
\[\begin{equation} \begin{aligned} v_{\pi}(s) &:=\mathbb{E}_\pi[G_t\mid S_t=s]\\ &=\mathbb{E}_\pi[ R_{t+1} + \gamma G_{t+1} \mid S_t=s]\\ &=\mathbb{E}_\pi[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t=s]\\ &=\sum_{a}\pi(a\mid s)\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{\pi}(s') \right]\\ \end{aligned} \end{equation}\]当 $\pi(a\mid s)$ 与 $p(s’,r\mid s,a)$ 全部已知时，求解贝尔曼方程就相当于求解一个带有 $\lvert \mathcal{S}\rvert$ 个未知数的方程组，但求解所需的计算量极大。
因此，我们在实践中一般使用迭代求解方法来求得近似解。
根据贝尔曼方程，我们可以写出如下的迭代公式：
\[\begin{equation} \begin{aligned} v_{k+1}(s) &=\mathbb{E}_\pi[ R_{t+1} + \gamma v_k(S_{t+1}) \mid S_t=s]\\ &=\sum_{a}\pi(a\mid s)\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_k(s') \right]\\ \end{aligned} \end{equation}\]从策略评估的迭代公式我们可以看到，某个状态 $s$ 的新价值 $v_{k+1}(s)$ 是通过对所有可能的后续状态 $s’$ 的旧价值 $v_{k}(s’)$ 以及瞬时奖励 $r$ 进行加权求和得到。这种迭代方式我们称为 期望更新 (expected update)。
1.2. 策略提升
在得到状态价值函数 $v_{\pi}$ 后，我们已经知道在当前策略 $\pi$ 下每个状态 $s$ “有多好”，我们想知道如果我们采取一个不同的动作 $a\ne\pi(s)$，这个状态的价值会不会变得更好。
我们知道，在状态 $s$ 下选择动作 $a$ 所带来的价值可以通过动作价值函数来描述，即
\[\begin{equation} \begin{aligned} q_\pi(s,a) &=\mathbb{E}_\pi[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t=s,A_t=a]\\ &=\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{\pi}(s') \right]\\ \end{aligned} \end{equation}\]策略提升的关键在于，通过动作价值函数 $q_\pi(s,a)$ 进行贪婪选择，来生成新的策略 $\pi’$，即
\[\begin{equation} \begin{aligned} \pi'(s)&=\arg\max_aq_\pi(s,a)\\ &=\arg\max_a\mathbb{E}_\pi[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t=s,A_t=a]\\ &=\arg\max_a\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{\pi}(s') \right]\\ \end{aligned} \end{equation}\]下面的策略提升定理能够保证进行贪婪选择后，得到的新策略 $\pi’$ 总是优于旧策略 $\pi$。
Theorem 1 (policy improvement theorem). 设 $\pi$ 和 $\pi’$ 是任意两个确定性策略，且 $\forall s\in\mathcal{S}$ 都满足：
\[\begin{equation} q_\pi(s,\pi'(s))\ge v_{\pi}(s) \end{equation}\]则策略 $\pi’$ 不会比 $\pi$ 更差，即 $\forall s\in\mathcal{S}$ 都满足：
\[\begin{equation} v_{\pi'}(s)\ge v_{\pi}(s) \end{equation}\]回看公式 $(5)$ 我们发现，当无法找到一个更好的策略 $\pi’$ 时，此时的策略 $\pi$ 满足
\[\begin{equation} \begin{aligned} v_{\pi}(s) &=\mathbb{E}_\pi[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t=s,A_t=a]\\ &=\max_a\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_{\pi}(s') \right]\\ \end{aligned} \end{equation}\]这正是上一章中提到的 贝尔曼最优方程 的形式。
由于贝尔曼最优方程有且仅有唯一解，即最优的价值函数 $v_{*}$ 。因此我们可以知道，策略提升一定能够收敛得到最优价值函数，此时的策略 $\pi$ 就是最优策略。
1.3. 策略迭代的收敛性
https://www.cnblogs.com/moonout/p/17804874.html
https://zhuanlan.zhihu.com/p/419208786
在这一小节中，我们将证明策略迭代的收敛性，即：策略迭代算法在有限次迭代下即可收敛。
这个结论事实上说明了两件事情：
- 策略评估过程能够收敛
- 策略提升过程能够收敛到最优策略
其中第二点我们已经在上一小节中说明了，因此这里我们证明第一点，即策略评估的收敛性。
1.3.1. 巴拿赫不动点定理
首先我们介绍一下证明用到的数学工具：巴拿赫不动点定理 (Banach fixed point theorem)，又被称为压缩映射定理 (Contraction mapping theorem)。
Theorem 2 (Banach fixed point theorem). 令 $(X,d)$ 是一个完备的度量空间，函数 $f:X\mapsto X$ 是一个压缩映射，则 $f$ 有且仅有唯一的不动点 $x_{*}\in X$。
定理2的证明在附录中。
1.3.2. 贝尔曼算子及其收敛性证明
根据贝尔曼方程和贝尔曼最优方程，我们可以分别定义下面的贝尔曼算子 $B_{\pi}$ 以及贝尔曼最优算子 $B_*$：
\[\begin{equation} \begin{aligned} B_{\pi} v(s)&:=\mathbb{E}_\pi\left[ r + \gamma \mathbb{E}_{s'\sim p(s'\mid s,a)}[v(s')]\right]\\ B_* v(s)&:=\max_a\left( r + \gamma \mathbb{E}_{s'\sim p(s'\mid s,a)}[v(s')]\right)\\ \end{aligned} \end{equation}\]贝尔曼算子代表利用贝尔曼方程，对状态价值函数集 $V={v(s_1),\cdots,v(s_n) }$ 进行更新。这里价值函数集 $V$ 是一个长度为 $\lvert \mathcal{S}\rvert$ 的向量。
策略评估的过程，实际上就是不断地将贝尔曼算子 $B_{\pi}$ 作用在价值函数集 $V$ 上，最终我们会得到一个序列：${V,B_{\pi} V,\cdots,B_{\pi}^nV }$。我们要证明策略评估过程能够收敛，就需要证明这个由贝尔曼算子所产生的序列会收敛到一个不动点上，即存在价值函数集 $V_{}\in\mathbb{R}^{\lvert\mathcal{S}\rvert}$，满足 $B_{\pi} V_{}=V_{*}$。
证明所用到的工具就是巴拿赫不动点定理。根据定理的表述，我们的证明思路如下：
- 找到一个完备的度量空间 $(X,d)$，这里我们选择的度量空间是 $\left(\mathbb{R}^{\lvert\mathcal{S}\rvert},d_{\infty}\right)$；
- 证明贝尔曼算子 $B_{\pi}$ 是这个完备度量空间上的一个压缩映射。
具体的证明见附录。
二、值迭代
我们已经知道，策略迭代算法的每一次迭代包括两个步骤：策略评估、策略提升。然而，这两步本身就是一个漫长的迭代过程。比如说，策略评估过程需要足够多的迭代次数，才能够收敛到精确的状态价值函数 $v_{\pi}(s)$。
一个自然的问题是：策略评估是否必须收敛到 $v_{\pi}(s)$ 才能停止呢？我们是否可以在中间的某一步停止迭代，但最终也能够得到最优的策略 $\pi$ 呢？
这个问题的回答是肯定的。事实上，策略评估可以在达到一定步数之后停止，同时也能够保证整个策略迭代算法的收敛性。我们将要介绍的值迭代 (value iteration) 算法就是基于这样的思想。
在值迭代算法中，我们在策略评估时针对每个状态 $s$ 只更新一次其价值函数 $v(s)$。整个值迭代算法可以用下面的迭代方程来描述：
\[\begin{equation} \begin{aligned} v_{k+1}(s) &=\max_a\mathbb{E}\left[ R_{t+1}+\gamma v_k(S_{t+1})\mid S_t=s,A_t=a \right]\\ &=\max_a\sum_{s'}\sum_{r}p(s',r\mid s,a)\left[ r+\gamma v_k(s') \right] \end{aligned} \end{equation}\]对比可以发现，值迭代算法实际上就是根据贝尔曼最优方程进行迭代更新。因此，根据上面介绍的巴拿赫不动点定理，证明值迭代算法的收敛性就转为证明贝尔曼最优算子 $B_*$ 是某个完备度量空间上的一个压缩映射。具体的证明可以查看附录。
附录
Proof of Theorem 1
下面我们证明策略提升定理，即动作价值函数 $q_\pi(s,a)$ 进行贪婪选择后，得到的新策略 $\pi’$ 总是优于旧策略 $\pi$。
我们从公式 $(6)$ 出发：
\[\begin{equation} \begin{aligned} v_{\pi}(s) &\le q_\pi(s,\pi'(s))\\ &=\mathbb{E}[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t=s,A_t=\pi'(s)]\\ &=\mathbb{E}_{\pi'}[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t=s]\\ &\le\mathbb{E}_{\pi'}[ R_{t+1} + \gamma q_\pi(S_{t+1},\pi'(S_{t+1})) \mid S_t=s]\\ &=\mathbb{E}_{\pi'}[ R_{t+1} + \gamma \mathbb{E}_{\pi'}[ R_{t+2} + \gamma v_{\pi}(S_{t+2}) \mid S_{t+1},A_t=\pi'(S_{t+1})]) \mid S_t=s]\\ &\le\mathbb{E}_{\pi'}[ R_{t+1} + \gamma R_{t+2}+\gamma^2v_{\pi}(S_{t+2}) \mid S_t=s]\\ &\vdots\\ &\le\mathbb{E}_{\pi'}[ R_{t+1} + \gamma R_{t+2}+\gamma^2R_{t+3}+\cdots \mid S_t=s]\\ &=v_{\pi'}(s) \end{aligned} \end{equation}\]当且仅当 $\forall s,q_\pi(s,\pi’(s))= v_{\pi}(s)$ 时，等号成立。
得证。
DP算法收敛性的相关证明
https://zhuanlan.zhihu.com/p/419208786
下面，我们先证明巴拿赫不动点定理，然后利用这个定理来证明两个DP算法的收敛性。
巴拿赫不动点定理证明
巴拿赫不动点定理表明，如果 $(X,d)$ 是一个完备的度量空间，且函数 $f:X\mapsto X$ 是一个压缩映射，则 $f$ 有且仅有唯一的不动点。
这里涉及不少数学概念，下面顺带解释一下。
不动点：一个函数 $f$ 的不动点是指方程 $f(x)=x$ 的解。
函数不动点可以从复合函数的形式定义，即如果 $x_{}$ 是 $f$ 的不动点，则 $\forall x_{0},x_{}=\lim_{n\rightarrow \infty} f^{n}(x_{0})$。其中 $f^{n}(x)=f(f(\cdots f(x)))$ 表示 $f$ 的 $n$ 次复合函数。
证明是显然的：
\[\begin{equation} \begin{aligned} f(x_{*}) &=f(\lim_{n\rightarrow \infty} f^{n}(x_0))\\ &=\lim_{n\rightarrow \infty} f(f^{n}(x_0))\\ &=\lim_{n\rightarrow \infty} f^{n+1}(x_0)\\ &=x_{*} \end{aligned} \end{equation}\]度量空间：一个度量空间 $M$ 是一个二元组 $(X,d)$，其中 $X$ 是一个集合，$d:X\times X\mapsto\mathbb{R}$ 是定义在集合 $X$ 上的一个距离度量。
由于 $d$ 是一个距离度量，则 $\forall x, y, z\in X$，下面的性质均成立：
- 非负性：$d(x,y)\ge 0$，当且仅当 $x=y$ 时等号成立；
- 对称性：$d(x,y)=d(y,x)$；
- 三角不等式：$d(x,z)\le d(x,y)+d(y,z)$。
完备的度量空间：一个度量空间 $(X,d)$ 是完备的，当且仅当 $X$ 中所有柯西序列的极限值依旧在 $X$ 中。
$X$ 中的元素组成的一个序列 ${ x_1,x_2,\dots,x_N }$ 是一个柯西序列，当且仅当它满足：
\[\begin{equation} \forall\varepsilon\gt 0,\exists n\in\mathbb{N},\forall a,b\gt n,d(x_a,x_b)\lt\varepsilon \end{equation}\]压缩映射：一个映射 $f:X\mapsto X$ 是度量空间 $(X,d)$ 上的一个 $\gamma$-压缩映射，当且仅当：
\[\begin{equation} \forall x_1,x_2\in X, d(f(x_1),f(x_2))\le \gamma d(x_1,x_2) \end{equation}\]其中 $\gamma\in[0,1)$。
Proof of Theorem 2.
我们先证明不动点的存在性。我们只需要证明序列 ${x,f(x),f^2(x),\cdots }$ 是一个柯西序列，那么就能够证明其极限的存在性。
将序列改写为 ${x_0,x_1,x_2,\cdots }$，其中 $x_i=f^i(x)$。
首先我们估计序列中相邻两项的距离。由于 $f$ 是压缩映射，我们有：
\[\begin{equation} \begin{aligned} d(x_2,x_1) &=d(f(x_1),f(x_0))\\ &\le \gamma d(x_1,x_0)\\ d(x_3,x_2) &\le \gamma d(x_2,x_1)\\ &\le \gamma^2 d(x_1,x_0)\\ \end{aligned} \end{equation}\]因此，我们有：
\[\begin{equation} d(x_{k+1},x_k)\le\gamma d(x_k,x_{k-1})\le\cdots\le\gamma^k d(x_1,x_0) \end{equation}\]对于任意的 $m,n\in\mathbb{N}$，不妨设 $m\gt n$。我们有：
\[\begin{equation} \begin{aligned} d(x_m,x_n) &\le d(x_m,x_{m-1})+d(x_{m-1},x_{m-2})+\cdots+d(x_{n+1},x_n)\\ &=\sum_{k=n}^{m-1}d(x_{k+1},x_k)\\ &\le \sum_{k=n}^{m-1}\gamma^k d(x_1,x_0)\\ &=d(x_1,x_0)\cdot \sum_{k=n}^{m-1}\gamma^k\\ &=d(x_1,x_0)\cdot \gamma^n\cdot\sum_{k=0}^{m-n-1}\gamma^k\\ &\le d(x_1,x_0)\cdot \gamma^n\cdot\sum_{k=0}^{\infty}\gamma^k\\ &= d(x_1,x_0)\cdot \frac{\gamma^n}{1-\gamma} \end{aligned} \end{equation}\]当 $n\rightarrow\infty$ 时，$\gamma^n\rightarrow 0$。因此对于任意的 $\varepsilon\gt 0$，存在 $N$，使得当 $m\gt n\ge N$ 时，$d(x_m,x_n)\lt \varepsilon$。
这就证明了 ${x_n}$ 是一个柯西序列，因此必然存在一个极限 $x_{*}$。
我们再证明不动点的唯一性。假设 $y_{}$ 也是 $f$ 的不动点，即 $f(y_{})=y_{*}$。
我们考虑 $x_{}$ 和 $y_{}$ 的距离：
\[\begin{equation} \begin{aligned} d(x_{*},y_{*}) &=d(f(x_{*}),f(y_{*}))\\ &\le \gamma d(x_{*},y_{*}) \end{aligned} \end{equation}\]移项得：$(1-\gamma)\cdot d(x_{},y_{})\le 0$。
由于 $1-\gamma\gt 0$，因此 $d(x_{},y_{})\le 0$。又由于距离度量的非负性，因此 $d(x_{},y_{})=0$，即 $x_{}=y_{}$。
这就证明了不动点的唯一性。
至此，巴拿赫不动点定理得证。
贝尔曼算子（策略迭代）收敛性证明
根据巴拿赫不动点定理，我们只需要证明贝尔曼算子是某个完备度量空间下的压缩映射，就能够证明贝尔曼算子的收敛性。
**Lemma. ** 度量空间 $\left(\mathbb{R}^{d},d_{\infty}\right)$ 是完备的，其中 $d_{\infty}(x,y)=|x-y|_{\infty}=\max\lvert x_i-y_i\rvert$ 表示向量的无穷范数。
Proof of Lemma. 考虑 $\mathbb{R}^d$ 上的任意柯西序列 ${ x^{(n)} }_{n=1}^{\infty}$，其中 $x^{(n)}\in\mathbb{R}^d$。
由柯西序列的性质，对于任意 $\varepsilon\gt 0$，存在一个正整数 $N$，使得当 $m,n\gt N$ 时，有：
\[\begin{equation} d_\infty\left(x^{(m)},x^{(n)}\right)=\max_{1\le i\le d}\left| x^{(m)}_i-x^{(n)}_i \right|\lt \varepsilon \end{equation}\]因此，对于一个固定的下标 $i$，都有：
\[\begin{equation} \left| x^{(m)}_i-x^{(n)}_i \right|\lt \varepsilon \end{equation}\]即实数列 ${x^{(n)}i}{n=1}^{\infty}$ 是在 $\mathbb{R}$ 上的一个柯西序列。
| 由于实数空间 $(\mathbb{R}, | \cdot | )$ 是完备的，因此每一个柯西序列 ${x^{(n)}i}{n=1}^{\infty}$ 均收敛，记其极限为 $x_i^{*}$。 |
下面我们证明柯西序列 ${ x^{(n)} }_{n=1}^{\infty}$ 会收敛于 $\mathbb{R}^d$ 中的一个点，记为 $x^{}=(x_1^{},\cdots,x_d^{*})$。
我们固定下标 $m$，让另一个下标 $n\rightarrow \infty$。由于绝对值是连续函数，因此：
\[\begin{equation} \begin{aligned} \lim_{n\rightarrow \infty}\left| x^{(m)}_i-x^{(n)}_i \right| &=\left| x^{(m)}_i-\lim_{n\rightarrow \infty}x^{(n)}_i \right|\\ &=\left| x^{(m)}_i-x^{*}_i \right|\\ &\lt \varepsilon \end{aligned} \end{equation}\]因此，对所有下标 $m$，我们有：
\[\begin{equation} d_{\infty}\left( x^{(m)},x^{*} \right) =\max_{1\le i\le d}\left| x^{(m)}_i-x^{*}_i \right|\lt \varepsilon \end{equation}\]即序列 $\left{ x^{(n)} \right}_{n=1}^{\infty}$ 会收敛于 $x^{*}$。度量空间的完备性得证。
下面我们证明贝尔曼算子的迭代过程是收敛的。
根据巴拿赫不动点定理，我们只需要证明贝尔曼算子 $B_{\pi}$ 在完备度量空间 $(\mathbb{R}^{\lvert\mathcal{S}\rvert},d_{\infty})$ 上是一个压缩映射。
其中，贝尔曼算子的定义如下：
\[\begin{equation} B_{\pi} v(s)=\sum_{a}\pi(a\mid s)\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)v(s') \right] \end{equation}\]我们希望证明：对于任意的 $v_1,v_2\in\mathbb{R}^{\lvert\mathcal{S}\rvert}$ 都有：
\[\begin{equation} d_\infty\left( B_{\pi} v_1,B_{\pi} v_2 \right)\le\gamma\cdot d_\infty\left( v_1,v_2 \right) \end{equation}\]其中，
\[\begin{equation} d_\infty\left( v_1,v_2 \right)=\sup_{s\in\mathcal{S}}\left| v_1(s)-v_2(s) \right| \end{equation}\]首先，我们考察对于任意一个固定的状态 $s$，两个价值函数 $v_1$ 和 $v_2$ 经过贝尔曼算子作用后的差异：
\[\begin{equation} \begin{aligned} \left| B_{\pi} v_1(s)-B_{\pi} v_2(s) \right| &=\left| \sum_{a}\pi(a\mid s)\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)v_1(s') \right]-\sum_{a}\pi(a\mid s)\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)v_2(s') \right] \right|\\ &=\left| \sum_{a}\pi(a\mid s)\left[ \gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)(v_1(s')-v_2(s'))\right]\right|\\ \end{aligned} \end{equation}\]| 根据绝对值三角不等式 $\lvert \sum x_i \rvert\le \sum\left | x_i \right | $ 得： |
由无穷范数的定义我们可知：
\[\begin{equation} \begin{aligned} \left| B_{\pi} v_1(s)-B_{\pi} v_2(s) \right| &\le \gamma\sum_{a}\pi(a\mid s)\left[ \sum_{s'\in\mathcal{S}}p(s'\mid s,a)\left|v_1(s')-v_2(s')\right|\right]\\ &\le \gamma\sum_{a}\pi(a\mid s)\left[ \sum_{s'\in\mathcal{S}}p(s'\mid s,a)\cdot d_{\infty}(v_1,v_2) \right]\\ &\le \gamma\cdot d_{\infty}(v_1,v_2)\cdot \sum_{a}\pi(a\mid s)\left[ \sum_{s'\in\mathcal{S}}p(s'\mid s,a) \right]\\ &=\gamma\cdot d_{\infty}(v_1,v_2) \end{aligned} \end{equation}\]由于上面的不等式对所有的状态 $s\in\mathcal{S}$ 都成立，因此对等式左侧取上确界：
\[\begin{equation} \begin{aligned} d_\infty\left( B_{\pi} v_1,B_{\pi} v_2 \right) &=\sup_{s\in\mathcal{S}}\left| B_{\pi} v_1(s)-B_{\pi} v_2(s) \right|\\ &\le\gamma\cdot d_{\infty}(v_1,v_2) \end{aligned} \end{equation}\]得证。
贝尔曼最优算子（值迭代）收敛性证明
Lemma. 对于实函数 $f(x)$ 和 $g(x)$，有：
\[\begin{equation} \left| \max_xf(x)-\max_xg(x) \right|\le \max_x\left| f(x)-g(x) \right| \end{equation}\]Proof of Lemma. 记 $A=\max_xf(x)$，$B=\max_xg(x)$。不失一般性，我们设 $A\ge B$。
我们设 $f(x)$ 的最大值点为 $x_0$，即 $f(x_0)=A$。考虑 $x=x_0$，我们有：
\[\begin{equation} \begin{aligned} f(x_0)-g(x_0) &=A-g(x_0)\\ &\le |f(x_0)-g(x_0)|\\ &\le \max_x|f(x)-g(x)| \end{aligned} \end{equation}\]又由于 $g(x_0)\le B$，因此：
\[\begin{equation} \begin{aligned} \text{LHS} &=|A-B|\\ &=A-B\\ &\le A-g(x_0)\\ &\le \max_x|f(x)-g(x)|\\ &=\text{RHS} \end{aligned} \end{equation}\]得证。
我们希望证明贝尔曼最优算子 $B_*$ 也是完备度量空间 $(\mathbb{R}^{\lvert\mathcal{S}\rvert},d_{\infty})$ 上是一个压缩映射。
其中，贝尔曼最优算子的定义如下：
\[\begin{equation} B_* v(s)=\max_{a}\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)v(s') \right] \end{equation}\]我们的目标是证明对于任意的 $v_1,v_2\in\mathbb{R}^{\lvert\mathcal{S}\rvert}$ 都有：
\[\begin{equation} d_\infty\left( B_* v_1,B_* v_2 \right)\le\gamma\cdot d_\infty\left( v_1,v_2 \right) \end{equation}\]同样，我们考虑任意一个固定的状态 $s$，两个价值函数 $v_1$ 和 $v_2$ 经过贝尔曼算子作用后的差异。
根据上面证明的引理，我们有：
\[\begin{equation} \begin{aligned} \left| B_* v_1(s)-B_* v_2(s) \right| &=\left| \max_{a}\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)v_1(s') \right]-\max_{a}\left[ R(s,a)+\gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)v_2(s') \right] \right|\\ &\le \max_a\left| \gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)(v_1(s')-v_2(s')) \right| \end{aligned} \end{equation}\]根据三角不等式，有：
\[\begin{equation} \begin{aligned} \left| B_* v_1(s)-B_* v_2(s) \right| &\le \max_a\left| \gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)(v_1(s')-v_2(s')) \right|\\ &\le \max_a\left[ \gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)\left|v_1(s')-v_2(s')\right| \right]\\ &\le \max_a\left[ \gamma\sum_{s'\in\mathcal{S}}p(s'\mid s,a)d_\infty(v_1,v_2) \right]\\ &\le \max_a\left[ \gamma\cdot d_\infty(v_1,v_2)\cdot \sum_{s'\in\mathcal{S}}p(s'\mid s,a) \right]\\ &\le \gamma\cdot d_\infty(v_1,v_2) \\ \end{aligned} \end{equation}\]在上面的不等式左侧对所有状态 $s$ 取上确界得：
\[\begin{equation} \begin{aligned} d_\infty\left( B_* v_1,B_* v_2 \right) &=\sup_{s\in\mathcal{S}}\left| B_* v_1(s)-B_* v_2(s) \right|\\ &\le\gamma\cdot d_{\infty}(v_1,v_2) \end{aligned} \end{equation}\]得证。
