optimal_policy.search();

本文最后更新于 2026年7月20日 晚上

赵老师开源的 Github 仓库、赵老师的 B站 课程视频

背景来自 XHS 特提恩聪明头

Overview

本章主要内容：

  • 核心概念：最优状态价值（optimal state value）和最优策略（optimal policy）
  • 一个基础工具：贝尔曼最优方程（Bellman Optimal Equation，BOE）

Outline：

  • 动机示例——如何改进 policy？
  • optimal policy 与 BOE
  • BOE 进一步的拓展
  • optimal policy 的性质

Lecture 8 动机示例——如何改进策略？

Example Example
例子

列出贝尔曼方程

vπ(s1)=−1+γvπ(s2)vπ(s2)=1+γvπ(s4)vπ(s3)=1+γvπ(s4)vπ(s4)=1+γvπ(s4)\begin{align*} v_\pi(s_1) &= -1 + \gamma v_\pi(s_2) \\ v_\pi(s_2) &= 1 + \gamma v_\pi(s_4) \\ v_\pi(s_3) &= 1 + \gamma v_\pi(s_4) \\ v_\pi(s_4) &= 1 + \gamma v_\pi(s_4) \\ \end{align*}

令 γ=0.9\gamma=0.9，可以计算出 state value，

vπ(s4)=vπ(s3)=vπ(s2)=10,vπ(s1)=8v_\pi(s_4) = v_\pi(s_3) = v_\pi(s_2) = 10, \quad v_\pi(s_1) = 8

然后可以得到 action value（以 s1s_1 为例）

qπ(s1,a1)=−1+γvπ(s1)=6.2qπ(s1,a2)=−1+γvπ(s2)=8qπ(s1,a3)=0+γvπ(s3)=9qπ(s1,a4)=−1+γvπ(s1)=6.2qπ(s1,a5)=0+γvπ(s1)=7.2\begin{align*} q_\pi(s_1,a_1) &= -1 + \gamma v_\pi(s_1) = 6.2 \\ q_\pi(s_1,a_2) &= -1 + \gamma v_\pi(s_2) = 8 \\ q_\pi(s_1,a_3) &= 0 + \gamma v_\pi(s_3) = 9 \\ q_\pi(s_1,a_4) &= -1 + \gamma v_\pi(s_1) = 6.2 \\ q_\pi(s_1,a_5) &= 0 + \gamma v_\pi(s_1) = 7.2 \end{align*}

可以注意到，上面的策略会进入 forbidden area s2s_2，这不是一个好的策略。

问题：当策略不够好时，如何改进？

  • 使用 action value 来选择动作！

刚刚我们的策略如下，

π(a∣s1)={1a=a20a≠a2\pi (a|s_1) = \begin{cases} 1 & a = a_2 \\ 0 & a \neq a_2 \end{cases}

如果选择最大的动作值，则得到新策略：

πnew(a∣s1)={1a=a⋆0a≠a⋆\pi_{\text{new}}(a|s_1) = \begin{cases} 1 & a = a^\star \\ 0 & a \neq a^\star \end{cases}

其中，a⋆=arg⁡max⁡aqπ(s1,a)=a3a^\star = \arg\max_a q_\pi(s_1,a) = a_3（在此情况下）。

为什么这样做可以改进策略？

  • 直观上：action value 可用于评估动作。
  • 数学上：将在本讲中介绍。

Lecture 9 最优策略与贝尔曼最优方程

9.1 最优策略的定义

状态值可用于评估策略的好坏：如果

vπ1(s)≥vπ2(s),∀s∈Sv_{\pi_1}(s) \geq v_{\pi_2}(s), \quad \forall s \in \mathcal{S}

则称 π1\pi_1 比 π2\pi_2 “更好”。

定义：如果对策略 π⋆\pi^\star，有

vπ⋆(s)≥vπ(s),∀s∈Sv_{\pi^\star}(s) \geq v_\pi(s), \quad \forall s \in \mathcal{S}

则称策略 π⋆\pi^\star 是最优的！

该定义引出许多问题：

  • 最优策略是否存在？
  • 最优策略是否唯一？
  • 最优策略是随机的还是确定性的？
  • 如何获得最优策略？

为了回答这些问题，我们需要研究贝尔曼最优方程。

9.2 贝尔曼最优方程（BOE）

Bellman optimality equation（元素形式）

v(s)=max⁡π∑aπ(a∣s)[∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)v(s′)],∀s∈S=max⁡π∑aπ(a∣s)q(s,a),∀s∈S\begin{align*} v(s) &= \color{lightblue}{\max_\pi} \sum_a \color{lightblue}{\pi(a|s)} \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a)v(s^\prime) \right], \quad \forall s \in \mathcal{S} \\ &= \max_\pi \sum_a \pi(a|s) q(s,a), \quad \forall s \in \mathcal{S} \end{align*}

说明：

  • 此处 p(r∣s,a)p(r|s,a)、p(s′∣s,a)p(s^\prime|s,a) 已知。
  • v(s)v(s)、v(s′)v(s^\prime) 未知，待计算。
  • π(s)\pi(s) 是已知还是未知？对 Bellman 方程，π\pi 是已知的；对于 BOE，π\pi 是未知的，是需要我们求解的。

Bellman optimality equation（矩阵-向量形式）

v=max⁡π(rπ+γPπv)\color{lightblue}{v = \max_\pi (r_\pi + \gamma P_\pi v)}

其中，元素对应于 ss 或 s′s^\prime：

[rπ]s≜∑aπ(a∣s)∑rp(r∣s,a)r[r_\pi]_s \triangleq \sum_a \pi(a|s) \sum_r p(r|s,a)r

[Pπ]s,s′=pπ(s′∣s)≜∑aπ(a∣s)p(s′∣s,a)[P_\pi]_{s,s^\prime} = p_\pi(s^\prime|s) \triangleq \sum_a \pi(a|s) p(s^\prime|s,a)

此处的 max⁡π\max_\pi 是逐元素进行的。

BOE 巧妙但棘手！

  • 为何巧妙？它以优雅的方式描述了最优策略和最优 state value。
  • 为何棘手？右侧是一个最优化问题，其计算方式并不简单直观。
  • 需回答的问题：
    • 算法：如何求解上述方程？
    • 存在性：方程的解是否存在？
    • 唯一性：方程的解是否存在？
    • 最优性：方程的解和最优 policy、最优 state value 有什么关系？

BOE 右侧的最大化

BOE 的元素形式如下，

v(s)=max⁡π∑aπ(a∣s)[∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)v(s′)],∀s∈S=max⁡π∑aπ(a∣s)q(s,a),∀s∈S\begin{align*} v(s) &= \color{lightblue}{\max_\pi} \sum_a \color{lightblue}{\pi(a|s)} \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a)v(s^\prime) \right], \quad \forall s \in \mathcal{S} \\ &= \max_\pi \sum_a \pi(a|s) q(s,a), \quad \forall s \in \mathcal{S} \end{align*}

对于右侧的最大化问题，考虑先固定初始值 v(s′)v(s^\prime)，由于模型 pp 已知，此时上式右侧：

v(s′) 已知  ⟹  q(s,a)=γ∑s′p(s′∣s,a)v(s′) 已知v(s^\prime) \ \text{已知} \implies q(s,a) = \gamma \sum_{s^\prime} p(s^\prime|s,a)v(s^\prime) \ \text{已知}

由于 ∑aπ(a∣s)=1\sum_a \pi(a|s) = 1，我们有：

max⁡π∑aπ(a∣s)q(s,a)⩽1×max⁡a∈A(s)q(s,a)\max_\pi \sum_a \pi(a|s) q(s,a) \leqslant 1 \times \max_{a \in \mathcal{A}(s)} q(s,a)

当 π(a∣s)={1a=a⋆0a≠a⋆\pi(a|s) = \begin{cases} 1 & a = a^\star \\ 0 & a \neq a^\star \end{cases} 时可以取到等号，达到最优，其中 a⋆=arg⁡max⁡aq(s,a)a^\star = \arg\max_a q(s,a)。

Lecture 10 贝尔曼最优方程拓展

10.1 求解贝尔曼最优方程

BOE 为 v=max⁡π(rπ+γPπv)v = \max_\pi (r_\pi + \gamma P_\pi v)。令

f(v)≔max⁡π(rπ+γPπv)f(v) \coloneqq \max_\pi (r_\pi + \gamma P_\pi v)

则贝尔曼最优方程可以重写为 v=f(v)v = f(v)，其中

[f(v)]s=max⁡π∑aπ(a∣s)q(s,a),∀s∈S[f(v)]_s = \max_\pi \sum_a \pi(a|s) q(s,a), \quad \forall s \in \mathcal{S}

接下来，如何求解该方程？

10.2 压缩映射定理

基本概念

  • 不动点：x∈Xx \in X 是 f:X→Xf: X \to X 的不动点，若 f(x)=xf(x) = x。
  • 压缩映射：ff 是压缩映射，若

    ∥f(x1)−f(x2)∥≤γ∥x1−x2∥\|f(x_1) - f(x_2)\| \leq \gamma \|x_1 - x_2\|

    其中，
    • γ∈(0,1)\gamma \in (0,1) 必须严格小于 11，这样会有 γk→0\gamma^k \to 0，k→∞k \to \infty
    • ∥⋅∥\|\cdot\| 可以是任何向量范数。

压缩映射定理

对于形如 x=f(x)x = f(x) 的方程，若 ff 是压缩映射，则：

  1. 存在性：存在不动点 x⋆x^\star 满足 f(x⋆)=x⋆f(x^\star) = x^\star。
  2. 唯一性：不动点 x⋆x^\star 唯一。
  3. 算法：考虑序列 {xk}\{x_k\} 其中 xk+1=f(xk)x_{k+1} = f(x_k)，则 xk→x⋆x_k \to x^\star 当 k→∞k \to \infty，且收敛速度是指数级的。

10.3 求解贝尔曼最优方程

回到贝尔曼最优方程：v=f(v)=max⁡π(rπ+γPπv)v = f(v) = \max_\pi (r_\pi + \gamma P_\pi v)

定理（映射 f(v)f(\boldsymbol{v}) 的压缩性质）：贝尔曼最优方程右侧的函数 f(v)f(\boldsymbol{v}) 是一个压缩映射。即对于任意的 v1,v2∈R∣S∣\boldsymbol{v}_1,\boldsymbol{v}_2 \in \mathbb{R}^{|S|}，满足

∥f(v1)−f(v2)∥∞⩽γ∥v1−v2∥∞,\left\|f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2)\right\|_\infty \leqslant \gamma \left\|\boldsymbol{v}_1 - \boldsymbol{v}_2\right\|_\infty,

其中 γ∈(0,1)\gamma \in (0,1) 为折扣因子，∥⋅∥∞\|\cdot\|_\infty 代表无穷范数（最大值范数），定义为向量全部元素中的最大绝对值。

证明： 任取两个向量 v1,v2∈R∣S∣\boldsymbol{v}_1,\boldsymbol{v}_2 \in \mathbb{R}^{|S|}，设二者的最优策略分别为 π1⋆\pi_1^\star 和 π2⋆\pi_2^\star，

π1⋆≜arg⁡max⁡π(rπ+γPπv1),π2⋆≜arg⁡max⁡π(rπ+γPπv2).\pi_1^\star \triangleq \arg\max_{\pi}\left(r_\pi + \gamma P_\pi \boldsymbol{v}_1\right),\quad \pi_2^\star \triangleq \arg\max_{\pi}\left(r_\pi + \gamma P_\pi \boldsymbol{v}_2\right).

于是有

f(v1)=max⁡π(rπ+γPπv1)=rπ1⋆+γPπ1⋆v1⩾rπ2⋆+γPπ2⋆v1,f(v2)=max⁡π(rπ+γPπv2)=rπ2⋆+γPπ2⋆v2⩾rπ1⋆+γPπ1⋆v2,\begin{align*} f(\boldsymbol{v}_1) &= \max_{\pi}\left(r_\pi + \gamma P_\pi \boldsymbol{v}_1\right) = r_{\pi_1^\star} + \gamma P_{\pi_1^\star}\boldsymbol{v}_1 \geqslant r_{\pi_2^\star} + \gamma P_{\pi_2^\star}\boldsymbol{v}_1,\\ f(\boldsymbol{v}_2) &= \max_{\pi}\left(r_\pi + \gamma P_\pi \boldsymbol{v}_2\right) = r_{\pi_2^\star} + \gamma P_{\pi_2^\star}\boldsymbol{v}_2 \geqslant r_{\pi_1^\star} + \gamma P_{\pi_1^\star}\boldsymbol{v}_2, \end{align*}

其中符号 “⩾\geqslant” 为逐元素比较。因此

f(v1)−f(v2)=rπ1⋆+γPπ1⋆v1−(rπ2⋆+γPπ2⋆v2)⩽rπ1⋆+γPπ1⋆v1−(rπ1⋆+γPπ1⋆v2)=γPπ1⋆(v1−v2).\begin{align*} f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2) &= r_{\pi_1^\star} + \gamma P_{\pi_1^\star}\boldsymbol{v}_1 - \left(r_{\pi_2^\star} + \gamma P_{\pi_2^\star}\boldsymbol{v}_2\right) \\ &\leqslant r_{\pi_1^\star} + \gamma P_{\pi_1^\star}\boldsymbol{v}_1 - \left(r_{\pi_1^\star} + \gamma P_{\pi_1^\star}\boldsymbol{v}_2\right) \\ &= \gamma P_{\pi_1^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right). \end{align*}

同理可证 f(v2)−f(v1)⩽γPπ2⋆(v2−v1)f(\boldsymbol{v}_2)-f(\boldsymbol{v}_1) \leqslant \gamma P_{\pi_2^\star}\left(\boldsymbol{v}_2 - \boldsymbol{v}_1\right)。联立两式得到

γPπ2⋆(v1−v2)⩽f(v1)−f(v2)⩽γPπ1⋆(v1−v2).\gamma P_{\pi_2^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right) \leqslant f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2) \leqslant \gamma P_{\pi_1^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right).

定义

z≜max⁡{∣γPπ2⋆(v1−v2)∣,  ∣γPπ1⋆(v1−v2)∣}∈R∣S∣,\boldsymbol{z} \triangleq \max\left\{ \left|\gamma P_{\pi_2^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right)\right|,\; \left|\gamma P_{\pi_1^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right)\right| \right\} \in \mathbb{R}^{|S|},

式中 max⁡(⋅)\max(\cdot) 与绝对值 ∣⋅∣|\cdot| 均为逐元素运算。由定义可知 z⩾0\boldsymbol{z} \geqslant \boldsymbol{0}。结合上面两个不等式可得

−z⩽γPπ2⋆(v1−v2)⩽f(v1)−f(v2)⩽γPπ1⋆(v1−v2)⩽z,-\boldsymbol{z} \leqslant \gamma P_{\pi_2^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right) \leqslant f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2) \leqslant \gamma P_{\pi_1^\star}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right) \leqslant \boldsymbol{z},

该式等价于

∣f(v1)−f(v2)∣⩽z.\left|f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2)\right| \leqslant \boldsymbol{z}.

进一步可推出

∥f(v1)−f(v2)∥∞⩽∥z∥∞,(3.5)\left\|f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2)\right\|_\infty \leqslant \|\boldsymbol{z}\|_\infty, \tag{3.5}

另一方面，设 ziz_i 为向量 z\boldsymbol{z} 的第 ii 个分量，piT\boldsymbol{p}_i^\mathrm{T}、qiT\boldsymbol{q}_i^\mathrm{T} 分别为矩阵 Pπ1⋆P_{\pi_1^\star}、Pπ2⋆P_{\pi_2^\star} 的第 ii 行，则

zi=max⁡{γ∣piT(v1−v2)∣,  γ∣qiT(v1−v2)∣}.z_i = \max\left\{ \gamma\left|\boldsymbol{p}_i^\mathrm{T}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right)\right|,\; \gamma\left|\boldsymbol{q}_i^\mathrm{T}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right)\right| \right\}.

由于行向量 pi\boldsymbol{p}_i 的所有元素非负且元素之和为1，因此有

∣piT(v1−v2)∣⩽piT∣v1−v2∣⩽∥v1−v2∥∞.\left|\boldsymbol{p}_i^\mathrm{T}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right)\right| \leqslant \boldsymbol{p}_i^\mathrm{T}\left|\boldsymbol{v}_1 - \boldsymbol{v}_2\right| \leqslant \left\|\boldsymbol{v}_1 - \boldsymbol{v}_2\right\|_\infty.

同理可得 ∣qiT(v1−v2)∣⩽∥v1−v2∥∞\left|\boldsymbol{q}_i^\mathrm{T}\left(\boldsymbol{v}_1 - \boldsymbol{v}_2\right)\right| \leqslant \left\|\boldsymbol{v}_1 - \boldsymbol{v}_2\right\|_\infty。于是 zi⩽γ∥v1−v2∥∞z_i \leqslant \gamma\left\|\boldsymbol{v}_1 - \boldsymbol{v}_2\right\|_\infty，进而

∥z∥∞=max⁡i∣zi∣⩽γ∥v1−v2∥∞.\|\boldsymbol{z}\|_\infty = \max_i |z_i| \leqslant \gamma\left\|\boldsymbol{v}_1 - \boldsymbol{v}_2\right\|_\infty.

将上式代入式(3.5)，得到

∥f(v1)−f(v2)∥∞⩽γ∥v1−v2∥∞.\left\|f(\boldsymbol{v}_1) - f(\boldsymbol{v}_2)\right\|_\infty \leqslant \gamma\left\|\boldsymbol{v}_1 - \boldsymbol{v}_2\right\|_\infty.

至此完成对映射 f(v)f(\boldsymbol{v}) 压缩性质的证明。

定理（存在性、唯一性与求解算法）：对于 BOE v=f(v)=max⁡π(rπ+γPπv)v = f(v) = \max_\pi (r_\pi + \gamma P_\pi v)，总是 存在 解 v⋆v^\star 且该解 唯一。该解可通过迭代求解：

vk+1=f(vk)=max⁡π(rπ+γPπvk)v_{k+1} = f(v_k) = \max_\pi (r_\pi + \gamma P_\pi v_k)

给定任意初值 v0v_0，序列 {vk}\{v_k\} 以指数速度收敛到 v⋆v^\star，收敛速度由 γ\gamma 决定。

迭代算法

矩阵-向量形式：

vk+1=f(vk)=max⁡π(rπ+γPπvk)v_{k+1} = f(v_k) = \max_\pi (r_\pi + \gamma P_\pi v_k)

元素形式：

vk+1(s)=max⁡π∑aπ(a∣s)[∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)vk(s′)]=max⁡aqk(s,a)v_{k+1}(s) = \max_\pi \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_k(s^\prime) \right] = \max_a q_k(s,a)

过程总结

  1. 对于任意 ss，当前估计值 vk(s)v_k(s)
  2. 对于任意 a∈A(s)a \in \mathcal{A}(s)，计算 qk(s,a)=∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)vk(s′)q_k(s,a) = \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_k(s^\prime)
  3. 计算 ss 的贪心策略 πk+1\pi_{k+1}：

    πk+1(a∣s)={1a=ak⋆(s)0a≠ak⋆(s)\pi_{k+1}(a|s) = \begin{cases} 1 & a = a_k^\star(s) \\ 0 & a \neq a_k^\star(s) \end{cases}

    其中 ak⋆(s)=arg⁡max⁡aqk(s,a)a_k^\star(s) = \arg\max_a q_k(s,a)
  4. 计算 vk+1(s)=max⁡aqk(s,a)v_{k+1}(s) = \max_a q_k(s,a)

该算法实际上就是下一讲要介绍的值迭代算法。

手动求解 BOE

Example
使用迭代算法计算最优策略
  • 动作定义：aℓ,a0,ara_\ell, a_0, a_r 分别代表：向左移动、原地停留、向右移动。
  • 奖励规则
    • 进入目标区域：奖励 +1+1
    • 试图走出边界：奖励 −1-1
  • 折扣因子 γ=0.9\gamma = 0.9

首先我们可以列出动作价值 q(s,a)q(s,a) 表

Q值表 左移 aℓa_\ell 停留 a0a_0 右移 ara_r
s1s_1 −1+γv(s1)-1 + \gamma v(s_1) 0+γv(s1)0 + \gamma v(s_1) 1+γv(s2)1 + \gamma v(s_2)
s2s_2 0+γv(s1)0 + \gamma v(s_1) 1+γv(s2)1 + \gamma v(s_2) 0+γv(s3)0 + \gamma v(s_3)
s3s_3 1+γv(s2)1 + \gamma v(s_2) 0+γv(s3)0 + \gamma v(s_3) −1+γv(s3)-1 + \gamma v(s_3)

目标： 求解最优状态值 v⋆(si)v^\star(s_i) 与最优策略 π⋆\pi^\star

迭代第0步：k=0k=0

状态值初始化：v0(s1)=v0(s2)=v0(s3)=0v_0(s_1) = v_0(s_2) = v_0(s_3) = 0

代入上表得到第0轮Q值：

aℓa_\ell a0a_0 ara_r
s1s_1 −1-1 00 11
s2s_2 00 11 00
s3s_3 11 00 −1-1

采用贪婪策略（选取当前最大Q值对应的动作）

π(ar∣s1)=1,π(a0∣s2)=1,π(aℓ∣s3)=1\pi(a_r|s_1)=1,\quad \pi(a_0|s_2)=1,\quad \pi(a_\ell|s_3)=1

更新状态值，最优状态值取当前状态下最大Q值：v1(s)=max⁡aq0(s,a)v_1(s) = \max_a q_0(s,a)

v1(s1)=v1(s2)=v1(s3)=1v_1(s_1) = v_1(s_2) = v_1(s_3) = 1

该策略是否有效？有效！

迭代第1步：k=1k=1

在此情境下，根据贝尔曼最优方程，

q1(s,a)=R(s,a)+γv1(s′)q_1(s,a) = R(s,a)+ \gamma v_1(s^\prime)

以状态为s1s_1为例，

q1(aℓ,s1)=−1+γv1(s2)=1+0.9∗1=−0.1q1(a0,s1)=0+γv1(s2)=1+0.9∗1=0.9q1(ar,s1)=1+γv1(s2)=1+0.9∗1=1.9\begin{align*} q_1 (a_\ell,s_1) = -1 + \gamma v_1(s_2) = 1 + 0.9 * 1 = -0.1 \\ q_1 (a_0,s_1) = 0 + \gamma v_1(s_2) = 1 + 0.9 * 1 = 0.9 \\ q_1 (a_r,s_1) = 1 + \gamma v_1(s_2) = 1 + 0.9 * 1 = 1.9 \\ \end{align*}

本轮Q值计算结果：

aℓa_\ell a0a_0 ara_r
s1s_1 −0.1-0.1 0.90.9 1.91.9
s2s_2 0.90.9 1.91.9 0.90.9
s3s_3 1.91.9 0.90.9 −0.1-0.1

然后继续使用贪婪策略（选取当前最大Q值对应的动作）

π(ar∣s1)=1,π(a0∣s2)=1,π(aℓ∣s3)=1\pi(a_r|s_1)=1,\quad \pi(a_0|s_2)=1,\quad \pi(a_\ell|s_3)=1

当前策略与上一轮完全一致，说明该策略已经是最优策略。更新状态值，

v2(s1)=max⁡{−0.1,0.9,1.9}=1.9v2(s2)=max⁡{0.9,1.9,0.9}=1.9v2(s3)=max⁡{1.9,0.9,−0.1}=1.9\begin{align*} v_2(s_1) &= \max\{−0.1, 0.9, 1.9\}=1.9 \\ v_2(s_2) &= \max\{0.9, 1.9, 0.9\}=1.9 \\ v_2(s_3) &= \max\{1.9, 0.9, −0.1\}=1.9 \\ \end{align*}

计算 v⋆v^\star

由上面过程可知，最优策略为：

  • s1s_1 执行 ara_r
  • s2s_2 执行 a0a_0
  • s3s_3 执行 aℓa_\ell

于是可以列出 Bellman 最优方程，

v⋆(s1)=1+γv⋆(s2)v⋆(s2)=1+γv⋆(s2)v⋆(s3)=1+γv⋆(s2)\begin{align*} v^\star(s_1) = 1 + \gamma v^\star(s_2) \\ v^\star(s_2) = 1 + \gamma v^\star(s_2) \\ v^\star(s_3) = 1 + \gamma v^\star(s_2) \end{align*}

解出，

v⋆(s1)=v⋆(s2)=v⋆(s3)=10v^\star(s_1) = v^\star(s_2) = v^\star(s_3) = 10

10.4 BOE 解的最优性证明

设 v⋆v^\star 是贝尔曼最优方程的解，满足，

v⋆=max⁡π(rπ+γPπv⋆)v^\star = \max_\pi (r_\pi + \gamma P_\pi v^\star)

设

π⋆=arg⁡max⁡π(rπ+γPπv⋆)\pi^\star = \arg\max_\pi (r_\pi + \gamma P_\pi v^\star)

则

v⋆=rπ⋆+γPπ⋆v⋆v^\star = r_{\pi^\star} + \gamma P_{\pi^\star} v^\star

因此 π⋆\pi^\star 是一个策略，v⋆=vπ⋆v^\star = v_{\pi^\star} 是对应的状态值。

定理（策略最优性）： 设 v⋆v^\star 是方程 v=max⁡π(rπ+γPπv)v = \max_\pi (r_\pi + \gamma P_\pi v) 的唯一解，vπv_\pi 是任意给定策略 π\pi 的状态价值函数，满足 vπ=rπ+γPπvπv_\pi = r_\pi + \gamma P_\pi v_\pi，则

v⋆≥vπ,∀π.v^\star \geq v_\pi, \quad \forall \pi.

证明： 设 π\pi 为任意可行策略，该策略对应的贝尔曼方程为：

vπ=rπ+γPπvπ.v_\pi = r_\pi + \gamma P_\pi v_\pi.

由 v⋆v^\star 的定义，

v⋆=max⁡π(rπ+γPπv⋆)=rπ⋆+γPπ⋆v⋆⩾rπ+γPπv⋆,v^\star = \max_{\pi}\left(r_\pi + \gamma P_\pi v^\star\right) = r_{\pi^\star} + \gamma P_{\pi^\star} v^\star \geqslant r_\pi + \gamma P_\pi v^\star,

移项整理可得，

v⋆−vπ⩾(rπ+γPπv⋆)−(rπ+γPπvπ)=γPπ(v⋆−vπ).\begin{align*} v^\star - v_\pi &\geqslant \left(r_\pi + \gamma P_\pi v^\star\right) - \left(r_\pi + \gamma P_\pi v_\pi\right) \\ &= \gamma P_\pi \left(v^\star - v_\pi\right). \end{align*}

反复使用上述不等式，

v⋆−vπ⩾γPπ(v⋆−vπ)⩾γ2Pπ2(v⋆−vπ)⩾⋯⩾γnPπn(v⋆−vπ).v^\star - v_\pi \geqslant \gamma P_\pi\left(v^\star - v_\pi\right) \geqslant \gamma^2 P_\pi^2\left(v^\star - v_\pi\right) \geqslant \dots \geqslant \gamma^n P_\pi^n\left(v^\star - v_\pi\right).

因此有，

v⋆−vπ⩾lim⁡n→∞γnPπn(v⋆−vπ)=0.v^\star - v_\pi \geqslant \lim_{n \to \infty} \gamma^n P_\pi^n \left(v^\star - v_\pi\right) = \boldsymbol{0}.

上式极限为零向量的原因：折扣因子满足 γ∈(0,1)\gamma \in (0,1)，且转移矩阵幂 PπnP_\pi^n 的所有元素取值在 [0,1][0,1] 中。

贪心最优策略

定理（贪心最优策略）：对任意 s∈Ss \in \mathcal{S}，确定性贪心策略

π⋆(a∣s)={1a=a⋆(s)0a≠a⋆(s)\pi^\star(a|s) = \begin{cases} 1 & a = a^\star(s) \\ 0 & a \neq a^\star(s) \end{cases}

是求解 BOE 的最优策略。其中：

a⋆(s)=arg⁡max⁡aq⋆(a,s)a^\star(s) = \arg\max_a q^\star(a,s)

q⋆(s,a):=∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)v⋆(s′)q^\star(s,a) := \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v^\star(s^\prime)

Lecture 11 最优策略的性质

11.1 最优策略的决定因素

贝尔曼最优方程，

v(s)=max⁡π∑aπ(a∣s)(∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)v(s′))\color{red}{v(s)} = \max_\pi \sum_a \color{lightblue}{\pi(a|s)} \left(\sum_r \color{red}{p(r|s,a)} r + \color{red}{\gamma} \sum_{s^\prime} \color{red}{p(s^\prime|s,a)} v(s^\prime)\right)

从 BOE 可以清晰看出，决定最优策略的三个因素：

  1. 奖励设计：rr
  2. 系统模型：p(s′∣s,a)p(s^\prime|s,a)、p(r∣s,a)p(r|s,a)
  3. 折扣因子：γ\gamma
  • v(s)v(s)、v(s′)v(s^\prime)、π(a∣s)\pi(a|s) 是待计算的未知量。
Example Example
设置如 图(a) 的 reward。图(a)(b) 的左边是在此 reward+折扣因子 下计算出的最优 policy，右边是对应的 state value。
Example Example
图(c) 与 图(a)(b) 类似，但折扣因子设置为 0.
图(d) 其他参数与 图(a) 一致，但将 forbidden area 的 reward 调低

之前提到：γ\gamma 较大则会远视，较小则短视。

Gt=Rt+1+γRt+2+γ2Rt+3+…G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots

  • γ=0.9\gamma = 0.9：最优策略敢于冒险（进入禁区），因为长远奖励更重要。
  • γ=0.5\gamma = 0.5：最优策略变得短视，避开所有禁区。
  • γ=0\gamma = 0：最优策略极度短视，选择即时奖励最大的动作，无法到达目标区域。
  • 增加惩罚（rforbidden=−1→−10r_{\text{forbidden}} = -1 \to -10）：最优策略也会避开禁区。

如果我们对 reward 进行仿射变换：r→ar+br \to ar + b，最优策略会有变化吗？

  • 并不会！

定理（最优策略不变性）： 考虑一个 MDP，其最优状态值 v⋆v^\star 满足 v⋆=max⁡π(rπ+γPπv⋆)v^\star = \max_\pi (r_\pi + \gamma P_\pi v^\star)。若每个奖励 rr 经历仿射变换 ar+bar + b（a,b∈Ra,b \in \mathbb{R}，a≠0a \neq 0），则对应的最优状态值 v′v^\prime 也是 v⋆v^\star 的仿射变换：

v′=av⋆+b1−γ1v^\prime = a v^\star + \frac{b}{1-\gamma} \mathbf{1}

其中，γ∈(0,1)\gamma \in (0,1) 为折扣率，1=[1,…,1]T\mathbf{1} = [1,\ldots,1]^T。因此，最优策略对奖励信号的仿射变换保持不变。

证明： 对于任意策略 π\pi，定义 return 向量 rπ=[…,rπ(s),… ]T\boldsymbol{r}_\pi = \left[\dots, r_\pi(s), \dots\right]^\mathrm{T}，其中，

rπ(s)=∑a∈Aπ(a∣s)∑r∈Rp(r∣s,a) r,s∈Sr_\pi(s) = \sum_{a\in\mathcal{A}} \pi(a|s) \sum_{r\in\mathcal{R}} p(r|s,a) \ r, \quad s \in \mathcal{S}

若对 immediate reward 做线性变换 r→αr+βr \to \alpha r + \beta，则单状态 return 满足 rπ(s)→αrπ(s)+βr_\pi(s) \to \alpha r_\pi(s) + \beta，向量形式写作 rπ→αrπ+β1\boldsymbol{r}_\pi \to \alpha \boldsymbol{r}_\pi + \beta \boldsymbol{1}，其中 1=[1,…,1]T\boldsymbol{1} = [1,\dots,1]^\mathrm{T} 为全1列向量。

此时对应的贝尔曼最优方程变为：

v′=max⁡π∈Π(αrπ+β1+γPπv′).(3.9)v^\prime = \max_{\pi\in\Pi}\big(\alpha \boldsymbol{r}_\pi + \beta \boldsymbol{1} + \gamma P_\pi v^\prime\big). \tag{3.9}

下面证明：式(3.9) 的解具有形式 v′=αv⋆+c1v^\prime = \alpha v^\star + c \boldsymbol{1}，其中常数 c=β1−γc = \dfrac{\beta}{1-\gamma}。

将 v′=αv⋆+c1v^\prime = \alpha v^\star + c \boldsymbol{1} 代入 式(3.9)，

αv⋆+c1=v′=max⁡π∈Π(αrπ+β1+γPπv′)=max⁡π∈Π(αrπ+β1+γPπ(αv⋆+c1))=max⁡π∈Π(αrπ+β1+αγPπv⋆+cγ1).\begin{align*} \alpha v^\star + c \boldsymbol{1} &= v^\prime \\ &= \max_{\pi\in\Pi}\big(\alpha \boldsymbol{r}_\pi + \beta \boldsymbol{1} + \gamma P_\pi v^\prime \big) \\ &= \max_{\pi\in\Pi}\big(\alpha \boldsymbol{r}_\pi + \beta \boldsymbol{1} + \gamma P_\pi \big(\alpha v^\star + c \boldsymbol{1}\big)\big) \\ &= \max_{\pi\in\Pi}\big(\alpha \boldsymbol{r}_\pi + \beta \boldsymbol{1} + \alpha \gamma P_\pi v^\star + c\gamma \boldsymbol{1}\big). \end{align*}

最后一个等号成立是因为转移矩阵满足 Pπ1=1P_\pi \boldsymbol{1} = \boldsymbol{1}。

将方程重新整理，

αv⋆=max⁡π∈Π(αrπ+αγPπv⋆)+β1+cγ1−c1.\alpha v^\star = \max_{\pi\in\Pi}\big(\alpha \boldsymbol{r}_\pi + \alpha \gamma P_\pi v^\star\big) + \beta \boldsymbol{1} + c\gamma \boldsymbol{1} - c \boldsymbol{1}.

由最优值函数定义 v⋆=max⁡π∈Π(rπ+γPπv⋆)v^\star = \max_{\pi\in\Pi}\big(\boldsymbol{r}_\pi + \gamma P_\pi v^\star\big)，代入后等式成立的充要条件为：

β1+cγ1−c1=0.\beta \boldsymbol{1} + c\gamma \boldsymbol{1} - c \boldsymbol{1} = \boldsymbol{0}.

代入 c=β1−γc = \dfrac{\beta}{1-\gamma} 可验证上式恒成立，因此 v′=αv⋆+c1v^\prime = \alpha v^\star + c \boldsymbol{1} 确实是式(3.9)的解。

又由于贝尔曼最优方程存在唯一解，故 v′v^\prime 是式(3.9)的唯一解。

最后，v′v^\prime 是 v⋆v^\star 的仿射变换，变换前后各动作价值的相对大小关系保持不变。因此由 v′v^\prime 导出的贪婪最优策略与由 v⋆v^\star 导出的策略完全一致，即：

arg⁡max⁡π∈Π(rπ+γPπv′)=arg⁡max⁡π(rπ+γPπv⋆).\arg\max_{\pi\in\Pi}\big(\boldsymbol{r}_\pi + \gamma P_\pi v^\prime\big) = \arg\max_{\pi}\big(\boldsymbol{r}_\pi + \gamma P_\pi v^\star\big).

11.2 无意义绕路问题

依旧设置 rwhite=0r_{white} = 0，rboundary=−1r_{boundary} = -1，rtarget=1r_{target} = 1

问题：最优策略是否会无意义绕路？

如下图(b)，从右上角出发，从一个白色区域到另一个白色区域，反正这样又不会受到负 reward 惩罚。我们需不需要对步数进行惩罚？比如每走一步，给一个 reward =−1= -1，进而保证不绕路。

  • 不需要，最优策略不会进行无意义绕路！——这是因为折扣率的存在。绕路会延迟获得正奖励，从而降低折扣回报。
Example Example
图(a) ：最优策略及其对应的 state value。
图(b) ：修改右上角的策略，不是最优。

计算一下右上角的 return：

  • Policy(a) 之 return =1+γ1+γ21+⋯=11−γ=10= 1 + \gamma 1 + \gamma^2 1 + \cdots = \frac{1}{1-\gamma} = 10
  • Policy(b) 之 return =0+γ0+γ21+⋯=γ21−γ=8.1= 0 + \gamma 0 + \gamma^2 1 + \cdots = \frac{\gamma^2}{1-\gamma} = 8.1

总结

贝尔曼最优方程：

  • 元素形式：v(s)=max⁡π∑aπ(a∣s)[∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)v(s′)]v(s) = \max_\pi \sum_a \pi(a|s) \left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a)v(s^\prime) \right]
  • 矩阵-向量形式：v=max⁡π(rπ+γPπv)v = \max_\pi (r_\pi + \gamma P_\pi v)

关于 BOE 的问题：

  • 解的存在性：是（由压缩映射定理保证）
  • 解的唯一性：是（由压缩映射定理保证）
  • 求解方程的算法：压缩映射定理得到的迭代算法
  • 最优性：BOE 的解对应于最优状态值和最优策略

请注意：最优 state value 是唯一的，但其对应的最优 policy 不一定是唯一的！

个人学习笔记 > AI Notes > Reinforcement Learning > 强化学习的数学基础
#强化学习
强化学习的数学基础 - Chapter 3
http://dbqdss.github.io/2026/07/20/个人学习笔记/AI Notes/Reinforcement Learning/强化学习的数学原理/MathFoundationRL-Ch03/
作者
失去理想的獾
发布于
2026年7月20日
许可协议