强化学习基础 (3)：动态规划求解

2025-10-25 强化学习基础 #强化学习 #马尔可夫决策过程 #动态规划 #策略迭代 #值迭代 #巴拿赫不动点定理约 39 分钟 · 13327 字

引言

动态规划 (Dynamic Programming, DP) 是指用于求解MDP问题的最优策略的一系列算法。

在解决实际的强化学习问题时，使用动态规划的场景并不多。因为动态规划算法需要大量的计算开销，并且要求对环境有完美的建模。然而，DP算法是其他强化学习算法的理论基石。现代的强化学习算法（如策略梯度算法等），都可以是对DP算法的一个近似，利用较少的计算开销以及不完整的环境建模，来达到尽可能接近DP算法的效果。

DP算法的核心思想在于：利用 价值函数 来指导和描述能够得到最优策略的搜索方法。

从上一篇文章我们得知，当我们已知最优的价值函数（无论是状态价值函数 $v_{*}$ 还是动作价值函数 $q_*$ ），我们就可以轻易求出最优的策略。而最优价值函数满足以下的 贝尔曼最优方程：

(1)

下面我们将看到，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. 策略评估

我们已经知道，状态价值函数满足下面的 贝尔曼方程:

(2)

当 $\pi(a\mid s)$ 与 $p(s',r\mid s,a)$ 全部已知时，求解贝尔曼方程就相当于求解一个带有 $\lvert \mathcal{S}\rvert$ 个未知数的方程组，但求解所需的计算量极大。

因此，我们在实践中一般使用迭代求解方法来求得近似解。

根据贝尔曼方程，我们可以写出如下的迭代公式：

(3)

从策略评估的迭代公式我们可以看到，某个状态 $s$ 的新价值 $v_{k+1}(s)$ 是通过对所有可能的后续状态 $s'$ 的旧价值 $v_{k}(s')$ 以及瞬时奖励 $r$ 进行加权求和得到。这种迭代方式我们称为 期望更新 (expected update)。

1.2. 策略提升

在得到状态价值函数 $v_{\pi}$ 后，我们已经知道在当前策略 $\pi$ 下每个状态 $s$ “有多好”，我们想知道如果我们采取一个不同的动作 $a\ne\pi(s)$ ，这个状态的价值会不会变得更好。

我们知道，在状态 $s$ 下选择动作 $a$ 所带来的价值可以通过动作价值函数来描述，即

(4)

策略提升的关键在于，通过动作价值函数 $q_\pi(s,a)$ 进行贪婪选择，来生成新的策略 $\pi'$ ，即

(5)

下面的策略提升定理能够保证进行贪婪选择后，得到的新策略 $\pi'$ 总是优于旧策略 $\pi$ 。

Theorem 1 (policy improvement theorem). 设 $\pi$ 和 $\pi'$ 是任意两个确定性策略，且 $\forall s\in\mathcal{S}$ 都满足：

(6)

则策略 $\pi'$ 不会比 $\pi$ 更差，即 $\forall s\in\mathcal{S}$ 都满足：

(7)

回看公式 $(5)$ 我们发现，当无法找到一个更好的策略 $\pi'$ 时，此时的策略 $\pi$ 满足

(8)

这正是上一章中提到的 贝尔曼最优方程 的形式。

由于贝尔曼最优方程有且仅有唯一解，即最优的价值函数 $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_*$ ：

(9)

贝尔曼算子代表利用贝尔曼方程，对状态价值函数集 $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)$ 。整个值迭代算法可以用下面的迭代方程来描述：

(10)

对比可以发现，值迭代算法实际上就是根据贝尔曼最优方程进行迭代更新。因此，根据上面介绍的巴拿赫不动点定理，证明值迭代算法的收敛性就转为证明贝尔曼最优算子 $B_*$ 是某个完备度量空间上的一个压缩映射。具体的证明可以查看附录。

附录

Proof of Theorem 1

下面我们证明策略提升定理，即动作价值函数 $q_\pi(s,a)$ 进行贪婪选择后，得到的新策略 $\pi'$ 总是优于旧策略 $\pi$ 。

我们从公式 $(6)$ 出发：

(11)

当且仅当 $\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$ 次复合函数。

证明是显然的：

(12)

度量空间：一个度量空间 $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 \}$ 是一个柯西序列，当且仅当它满足：

(13)

压缩映射：一个映射 $f:X\mapsto X$ 是度量空间 $(X,d)$ 上的一个 $\gamma$ -压缩映射，当且仅当：

(14)

其中 $\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$ 是压缩映射，我们有：

(15)

因此，我们有：

(16)

对于任意的 $m,n\in\mathbb{N}$ ，不妨设 $m\gt n$ 。我们有：

(17)

当 $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_{*}$ 的距离：

(18)

移项得： $(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$ 时，有：

(19)

因此，对于一个固定的下标 $i$ ，都有：

(20)

即实数列 $\{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$ 。由于绝对值是连续函数，因此：

(21)

因此，对所有下标 $m$ ，我们有：

(22)

即序列 $\left\{ x^{(n)} \right\}_{n=1}^{\infty}$ 会收敛于 $x^{*}$ 。度量空间的完备性得证。

下面我们证明贝尔曼算子的迭代过程是收敛的。

根据巴拿赫不动点定理，我们只需要证明贝尔曼算子 $B_{\pi}$ 在完备度量空间 $(\mathbb{R}^{\lvert\mathcal{S}\rvert},d_{\infty})$ 上是一个压缩映射。

其中，贝尔曼算子的定义如下：

(23)

我们希望证明：对于任意的 $v_1,v_2\in\mathbb{R}^{\lvert\mathcal{S}\rvert}$ 都有：

(24)

其中，

(25)

首先，我们考察对于任意一个固定的状态 $s$ ，两个价值函数 $v_1$ 和 $v_2$ 经过贝尔曼算子作用后的差异：

(26)

根据绝对值三角不等式 $\lvert \sum x_i \rvert\le \sum\left| x_i \right|$ 得：

(27)

由无穷范数的定义我们可知：

(28)

由于上面的不等式对所有的状态 $s\in\mathcal{S}$ 都成立，因此对等式左侧取上确界：

(29)

得证。

贝尔曼最优算子（值迭代）收敛性证明

Lemma. 对于实函数 $f(x)$ 和 $g(x)$ ，有：

(30)

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$ ，我们有：

(31)

又由于 $g(x_0)\le B$ ，因此：

(32)

得证。

我们希望证明贝尔曼最优算子 $B_*$ 也是完备度量空间 $(\mathbb{R}^{\lvert\mathcal{S}\rvert},d_{\infty})$ 上是一个压缩映射。

其中，贝尔曼最优算子的定义如下：

(33)

我们的目标是证明对于任意的 $v_1,v_2\in\mathbb{R}^{\lvert\mathcal{S}\rvert}$ 都有：

(34)

同样，我们考虑任意一个固定的状态 $s$ ，两个价值函数 $v_1$ 和 $v_2$ 经过贝尔曼算子作用后的差异。

根据上面证明的引理，我们有：

(35)

根据三角不等式，有：

(36)

在上面的不等式左侧对所有状态 $s$ 取上确界得：

(37)

得证。