强化学习的数学基础 - Chapter 4

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

背景来自 XHS 马大可

Overview

Outline：

• 值迭代算法（Value iteration algorithm）
• 策略迭代算法（Policy iteration algorithm）
• 截断策略迭代算法（Truncated policy iteration algorithm）

---

Lec 12 值迭代算法

算法来源

回顾上一节，如何求解贝尔曼最优方程？

$$v = f(v) = \max_\pi (r_\pi + \gamma P_\pi v)$$

压缩映射定理给出了一个迭代算法：

$$v_{k+1} = f(v_k) = \max_\pi (r_\pi + \gamma P_\pi v_k),\quad k = 1,2,3,\ldots$$

其中，$v_0$ 可以任意选取。

该算法最终能找到最优状态值和最优策略。这就是 值迭代算法！

两步分解

算法 $v_{k+1} = f(v_k) = \max_\pi (r_\pi + \gamma P_\pi v_k)$ 可分解为两步：

• 步骤1：策略更新

  $$\pi_{k+1} = \argmax_\pi (r_\pi + \gamma P_\pi v_k)$$

  其中 $v_k$ 已知。

• 步骤2：值更新

  $$v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k$$

问题：$v_k$ 是一个真实的 state value 吗？

• 不是，这里的 $v_k$ 就只是一个单纯的向量，就是一个值，并不是 state value！因为不能保证 $v_k$ 满足贝尔曼方程。

元素形式

步骤1：策略更新

原方程 $\pi_{k+1} = \argmax_{\pi} \big( r_\pi + \gamma P_\pi v_k \big)$ 的元素形式为，

$$\pi_{k+1}(s) = \argmax_\pi \sum_a \pi(a|s) \underbrace{\left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_k(s^\prime) \right]}_{q_k(s,a)}, \quad s \in \mathcal{S}$$

最优策略为

$$\color{lightblue}{\pi_{k+1}(a|s) = \begin{cases} 1 & a = a_k^\star(s) \\ 0 & a \neq a_k^\star(s) \end{cases}}$$

其中，$\color{lightblue}{a_k^\star(s) = \argmax_a q_k(s,a)}.$ $\pi_{k+1}$ 称为 贪心策略（greedy policy），因为它简单地选择最大的 $q$ 值。

步骤2：值更新

原方程 $v_{k+1} = f(v_k) = \max_\pi (r_\pi + \gamma P_\pi v_k)$ 的元素形式为，

$$\begin{align*} v_{k+1}(s) &= \sum_a \pi_{k+1}(a|s) \underbrace{\left[ \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_k(s^\prime) \right]}_{q_k(s,a)}, \quad s \in \mathcal{S} \\ &= \max_a q_k(s,a) \end{align*}$$

最后一个等号是因为我们选取的 $\pi_{k+1}$ 是 贪心 的！

伪代码

整体过程：

$$\begin{align*} v_k(s) \rightarrow q_k(s,a) \rightarrow \text{贪心策略} \ \pi_{k+1}(a|s) \rightarrow \text{更新值} \ v_{k+1} = \max_a q_k(s,a) \end{align*}$$

值迭代算法

• 初始化：已知概率模型 $p(r|s,a)$ 和 $p(s^\prime|s,a)$，初始猜测 $v_0$。

• 目标：搜索求解贝尔曼最优方程的最优状态值和最优策略。

• 当 $v_k$ 未收敛时（$\|v_k - v_{k-1}\|>\epsilon$，$\epsilon$ 是预设阈值），
  执行第 $k$ 次迭代：

  • 对每个状态 $s \in \mathcal{S}$：
    • 对每个动作 $a \in \mathcal{A}(s)$：
      • 计算 q-value：$q_k(s,a) = \sum_r p(r|s,a)r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_k(s^\prime)$
    • 贪心策略：$a^\star_k(s) = \argmax_a q_k(s,a)$
    • 策略更新：$\pi_{k+1}(a|s) = 1$ 若 $a = a^\star_k$，否则为 0
    • 值更新：$v_{k+1}(s) = \max_a q_k(s,a)$

例子

继续沿用 $r_{\text{boundary}} = r_{\text{forbidden}} = -1$，$r_{\text{target}} = 1$，折扣率为 $\gamma = 0.9$。

(a) 策略；(b) 第一次迭代得到的策略；(c) 第二次迭代得到的策略

可以列出 Q-表： $q(s, a)$ 的表达式。

q-value	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$s_1$	$-1 + \gamma v(s_1)$	$-1 + \gamma v(s_2)$	$0 + \gamma v(s_3)$	$-1 + \gamma v(s_1)$	$0 + \gamma v(s_1)$
$s_2$	$-1 + \gamma v(s_2)$	$-1 + \gamma v(s_2)$	$1 + \gamma v(s_4)$	$0 + \gamma v(s_1)$	$-1 + \gamma v(s_2)$
$s_3$	$0 + \gamma v(s_1)$	$1 + \gamma v(s_4)$	$-1 + \gamma v(s_3)$	$-1 + \gamma v(s_3)$	$0 + \gamma v(s_3)$
$s_4$	$-1 + \gamma v(s_2)$	$-1 + \gamma v(s_4)$	$-1 + \gamma v(s_4)$	$0 + \gamma v(s_3)$	$1 + \gamma v(s_4)$

当 $k = 0$ 时

令 $v_0(s_1) = v_0(s_2) = v_0(s_3) = v_0(s_4) = 0$

q-value	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$s_1$	$-1$	$-1$	$\color{red}0$	$-1$	$\color{red}0$
$s_2$	$-1$	$-1$	$\color{red}1$	$0$	$-1$
$s_3$	$0$	$\color{red}1$	$-1$	$-1$	$0$
$s_4$	$-1$	$-1$	$-1$	$0$	$\color{red}1$

$k=0$ 时，对应的 $q(s_1,a)$ 在 $a_3$、$a_5$ 处同时取到最大，随便选取一个即可，此处取 $s_5$

步骤 1：策略更新

$$\pi_1(a_5|s_1) = 1, \quad \pi_1(a_3|s_2) = 1, \quad \pi_1(a_2|s_3) = 1, \quad \pi_1(a_5|s_4) = 1$$

步骤 2：值更新

$$v_1(s_1) = 0, \quad v_1(s_2) = 1, \quad v_1(s_3) = 1, \quad v_1(s_4) = 1$$

当 $k = 1$ 时

由于 $v_1(s_1) = 0, v_1(s_2) = 1, v_1(s_3) = 1, v_1(s_4) = 1$，我们有：

q-table	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$s_1$	$-1 + \gamma \cdot 0$	$-1 + \gamma \cdot 1$	$\color{red}0 + \gamma \cdot 1$	$-1 + \gamma \cdot 0$	$0 + \gamma \cdot 0$
$s_2$	$-1 + \gamma \cdot 1$	$-1 + \gamma \cdot 1$	$\color{red}1 + \gamma \cdot 1$	$0 + \gamma \cdot 0$	$-1 + \gamma \cdot 1$
$s_3$	$0 + \gamma \cdot 0$	$\color{red}1 + \gamma \cdot 1$	$-1 + \gamma \cdot 1$	$-1 + \gamma \cdot 1$	$0 + \gamma \cdot 1$
$s_4$	$-1 + \gamma \cdot 1$	$-1 + \gamma \cdot 1$	$-1 + \gamma \cdot 1$	$0 + \gamma \cdot 1$	$\color{red}1 + \gamma \cdot 1$

步骤 1：策略更新

$$\pi_2(a_3|s_1) = 1, \quad \pi_2(a_3|s_2) = 1, \quad \pi_2(a_2|s_3) = 1, \quad \pi_2(a_5|s_4) = 1$$

步骤 2：值更新

$$v_2(s_1) = \gamma \cdot 1, \quad v_2(s_2) = 1 + \gamma \cdot 1, \quad v_2(s_3) = 1 + \gamma \cdot 1, \quad v_2(s_4) = 1 + \gamma \cdot 1$$

该策略已经是最优策略！！

• $k = 2, 3, \dots$： 当 $\|v_k - v_{k+1}\|$ 小于预设阈值时停止。

---

Lec 13 策略迭代算法

算法描述

给定一个随机初始策略 $\pi_0$：

• 步骤 1：策略评估（Policy Evaluation，PE）

  计算 $\pi_k$ 的状态值：

  $$v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}$$

  注：这里的 $v_{\pi_k}$ 是一个 state value！

• 步骤 2：策略改进（Policy Improvement，PI）

  $$\pi_{k+1} = \argmax_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_k})$$

  该最大化是逐分量进行的！

整体算法按照如下序列进行，

$$\pi_0 \xrightarrow{\text{PE}} v_{\pi_0} \xrightarrow{\text{PI}} \pi_1 \xrightarrow{\text{PE}} v_{\pi_1} \xrightarrow{\text{PI}} \pi_2 \xrightarrow{\text{PE}} v_{\pi_2} \xrightarrow{\text{PI}} \cdots$$

关键问题

Q1：策略评估步骤中，如何通过求解贝尔曼方程得到状态值 $v_{\pi_k}$？

• 闭式解：

  $$v_{\pi_k} = (I - \gamma P_{\pi_k})^{-1} r_{\pi_k}$$

• 迭代解：

  $$v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}, \quad j = 0, 1, 2, \ldots$$

• 策略评估中嵌入了另一个迭代算法！

Q2：策略改进步骤中，为什么新策略 $\pi_{k+1}$ 比 $\pi_k$ 更好？

引理（策略改进）： 若 $\pi_{k+1} = \argmax_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_k})$，则 $v_{\pi_{k+1}} \geqslant v_{\pi_k}$ 对任意 $k$ 成立。

证明： 由于 $v_{\pi_{k+1}}$ 和 $v_{\pi_k}$ 都是状态值，它们分别满足下面的贝尔曼方程：

$$\begin{align*} v_{\pi_{k+1}} &= r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}, \\ v_{\pi_k} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}. \end{align*}$$

由于 $\pi_{k+1} = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_k})$，因此

$$r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k} \geqslant r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}.$$

因此

$$\begin{aligned} v_{\pi_k} - v_{\pi_{k+1}} &= (r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}) - (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) \\ &\leqslant (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) - (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) \\ &\leqslant \gamma P_{\pi_{k+1}} (v_{\pi_k} - v_{\pi_{k+1}}). \end{aligned}$$

反复调用上式可得

$$\begin{aligned} v_{\pi_k} - v_{\pi_{k+1}} &\leqslant \gamma^2 P_{\pi_{k+1}}^2 (v_{\pi_k} - v_{\pi_{k+1}}) \leqslant \cdots \leqslant \gamma^n P_{\pi_{k+1}}^n (v_{\pi_k} - v_{\pi_{k+1}}) \\ &\leqslant \lim_{n \to \infty} \gamma^n P_{\pi_{k+1}}^n (v_{\pi_k} - v_{\pi_{k+1}}) = 0. \end{aligned}$$

上式最右端极限等于 $0$ 是因为 $\gamma^n \to 0$ 且 $P_{\pi_{k+1}}^n$ 的每一个元素都在 $[0,1]$ 区间。

因此，$\pi_{k+1}$ 比 $\pi_k$ 更优。

Q3：为什么这样的迭代算法最终能到达最优策略？

• 由于每次迭代都会改进策略，所以

  $$v_{\pi_0} \leqslant v_{\pi_1} \leqslant v_{\pi_2} \leqslant \cdots \leqslant v_{\pi_k} \leqslant \cdots \leqslant v^\star$$

• 定理（策略迭代收敛性）： 策略迭代算法生成的序列 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 收敛到最优状态值 $v^\star$，从而策略序列 $\{\pi_k\}_{k=0}^{\infty}$ 收敛到最优策略。

证明： 为了证明 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 的收敛性，我们引入另一个序列 $\{v_k\}_{k=0}^{\infty}$，该序列由下面的迭代算法产生：

$$v_{k+1} = f(v_k) = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_k).$$

这个迭代算法实际上就是值迭代算法。我们已经知道，给定任意的初始值 $v_0$，$v_k$ 会收敛到 $v^\star$。

对任意的 $\pi_0$，总是能找到 $v_0$ 使得 $v_0 \leq v_{\pi_0}$。下面用递归法证明 $v_k \leq v_{\pi_k} \leq v^\star$ 对任意 $k \geqslant 1$ 都成立。

假设 $v_{\pi_k} \geqslant v_k$ 对某一个 $k$ 成立，那么对于 $k+1$ 有，

$$\begin{align*} v_{\pi_{k+1}} - v_{k+1} &= (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) - \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_k) \\ &\geqslant (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) - \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_k) \\ &\qquad\qquad\qquad\qquad (\text{因为 } v_{\pi_{k+1}} \geqslant v_{\pi_k} \text{ 并且 } P_{\pi_{k+1}} \geqslant 0) \\ &= (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) - (r_{\pi_k^\prime} + \gamma P_{\pi_k^\prime} v_k) \\ &\qquad\qquad\qquad\qquad (\text{令 } \pi_k^\prime = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_k)) \\ &\geqslant (r_{\pi_k^\prime} + \gamma P_{\pi_k^\prime} v_{\pi_k}) - (r_{\pi_k^\prime} + \gamma P_{\pi_k^\prime} v_k) \\ &\qquad\qquad\qquad\qquad (\text{因为 } \pi_{k+1} = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_k})) \\ &= \gamma P_{\pi_k^\prime} (v_{\pi_k} - v_k). \end{align*}$$

由于 $v_{\pi_k} - v_k \geqslant 0$ 并且 $P_{\pi_k^\prime}$ 非负，我们有 $P_{\pi_k^\prime}(v_{\pi_k} - v_k) \geqslant 0$，因此 $v_{\pi_{k+1}} - v_{k+1} \geqslant 0$。

由于 $v_{\pi_k} \geqslant v_k$ 对于 $k = 0$ 成立，那么通过递归可知 $v_{\pi_k} \geqslant v_k$ 对任意 $k \geqslant 0$ 成立。最后，因为 $v_k$ 能收敛到 $v^\star$，所以 $v_{\pi_k}$ 也必定能收敛到 $v^\star$。

Q4：值迭代和策略迭代算法之间有什么关系？

• 实际上二者都是截断策略迭代算法的特殊情况！（后面会讲到）

元素形式

步骤 1：策略评估

• Matrix-vector 形式：$v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}, \quad j = 0, 1, 2, \ldots$
• 元素形式：

  $$v_{\pi_k}^{(j+1)}(s) = \sum_{a} \pi_k(a|s) \left[ \sum_{r} p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_{\pi_k}^{(j)}(s^\prime) \right], \quad s \in \mathcal{S}$$

当 $j \to \infty$ 或 $j$ 足够大或 $\|v_{\pi_k}^{(j+1)} - v_{\pi_k}^{(j)}\|$ 足够小时停止。

步骤 2：策略改进

• Matrix-vector 形式：$\pi_{k+1} = \argmax_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_k})$
• 元素形式：

$$\pi_{k+1}(s) = \argmax_{\pi} \sum_{a} \pi(a|s) \underbrace{\left[ \sum_{r} p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_{\pi_k}(s^\prime) \right]}_{q_{\pi_k}(s,a)}, \quad s \in \mathcal{S}$$

其中，$q_{\pi_k}(s,a)$ 是策略 $\pi_k$ 下的动作值。令 $a_k^\star(s) = \argmax_{a} q_{\pi_k}(s,a)$，则贪心策略为

$$\pi_{k+1}(a|s) = \begin{cases} 1 & a = a_k^\star(s) \\ 0 & a \neq a_k^\star(s) \end{cases}$$

伪代码

策略迭代算法

• 初始化：已知概率模型 $p(r|s,a)$ 和 $p(s^\prime|s,a)$，初始策略 $\pi_0$。
• 目标：搜索最优状态值和最优策略。
• 当策略未收敛时，执行第 $k$ 次迭代：
  • 策略评估：
    • 初始化：任意初始猜测 $v_{\pi_k}^{(0)}$
    • 当 $v_{\pi_k}^{(j)}$ 未收敛时，执行第 $j$ 次迭代：
      • 对每个状态 $s \in \mathcal{S}$：

        $$v_{\pi_k}^{(j+1)}(s) = \sum_{a} \pi_k(a|s) \left[ \sum_{r} p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_{\pi_k}^{(j)}(s^\prime) \right]$$

  • 策略改进：
    • 对每个状态 $s \in \mathcal{S}$：
      • 对每个动作 $a \in \mathcal{A}(s)$：

        $$q_{\pi_k}(s,a) = \sum_{r} p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_{\pi_k}(s^\prime)$$

      • $a_k^\star(s) = \argmax_{a} q_{\pi_k}(s,a)$
      • $\pi_{k+1}(a|s) = 1$ 若 $a = a_k^\star(s)$，否则为 $0$

例 1

策略迭代 例子1 之示意图

• 奖励设置为 $r_{\text{boundary}} = -1$ 且 $r_{\text{target}} = 1$。折扣率为 $\gamma = 0.9$。
• 动作：$a_\ell, a_0, a_r$ 分别表示向左、保持不变和向右。
• 目标：使用策略迭代找出最优策略。

迭代 $k = 0$：

步骤 1：策略评估

$\pi_0$ 被选为图 (a) 中的策略。贝尔曼方程为

$$\begin{align*} v_{\pi_0}(s_1) &= -1 + \gamma v_{\pi_0}(s_1), \\ v_{\pi_0}(s_2) &= 0 + \gamma v_{\pi_0}(s_1). \end{align*}$$

• 直接求解方程：

$$v_{\pi_0}(s_1) = -10, \quad v_{\pi_0}(s_2) = -9.$$

• 迭代求解方程。选取初始猜测 $v_{\pi_0}^{(0)}(s_1) = v_{\pi_0}^{(0)}(s_2) = 0$：

$$\begin{align*} &\begin{cases} v_{\pi_0}^{(1)}(s_1) = -1 + \gamma v_{\pi_0}^{(0)}(s_1) = -1, \\ v_{\pi_0}^{(1)}(s_2) = 0 + \gamma v_{\pi_0}^{(0)}(s_1) = 0, \end{cases} \\ &\begin{cases} v_{\pi_0}^{(2)}(s_1) = -1 + \gamma v_{\pi_0}^{(1)}(s_1) = -1.9, \\ v_{\pi_0}^{(2)}(s_2) = 0 + \gamma v_{\pi_0}^{(1)}(s_1) = -0.9, \end{cases} \\ &\begin{cases} v_{\pi_0}^{(3)}(s_1) = -1 + \gamma v_{\pi_0}^{(2)}(s_1) = -2.71, \\ v_{\pi_0}^{(3)}(s_2) = 0 + \gamma v_{\pi_0}^{(2)}(s_1) = -1.71, \end{cases} \end{align*}$$

步骤 2：策略改进

$q_{\pi_k}(s, a)$ 的表达式：

$q_{\pi_k}(s, a)$	$a_\ell$	$a_0$	$a_r$
$s_1$	$-1 + \gamma v_{\pi_k}(s_1)$	$0 + \gamma v_{\pi_k}(s_1)$	$1 + \gamma v_{\pi_k}(s_2)$
$s_2$	$0 + \gamma v_{\pi_k}(s_1)$	$1 + \gamma v_{\pi_k}(s_2)$	$-1 + \gamma v_{\pi_k}(s_2)$

代入 $v_{\pi_0}(s_1) = -10, v_{\pi_0}(s_2) = -9$ 和 $\gamma = 0.9$ 得到

$q_{\pi_0}(s, a)$	$a_\ell$	$a_0$	$a_r$
$s_1$	$-10$	$-9$	$\color{red}{-7.1}$
$s_2$	$-9$	$\color{red}{-7.1}$	$-9.1$

通过寻找 $q_{\pi_0}$ 的最大值，改进后的策略为：

$$\pi_1(a_r|s_1) = 1, \quad \pi_1(a_0|s_2) = 1.$$

该策略在一次迭代后即达到最优！在编程中，应继续迭代直到满足停止准则。

例 2

策略迭代 例子2 之示意图

• 奖励设置为 $r_{\text{boundary}} = -1$ 且 $r_{\text{target}} = 1$。折扣率为 $\gamma = 0.9$。

我们可以注意到：越靠近目标的策略，越先变好！

• $\pi_0$：所有策略都很差
• $\pi_1$：target 的上下左右策略都变好！
• $\pi_2$：target 周围一圈的策略都变好！
• $\pi_3$：右下角附近的策略变好！
• $\cdots$
• $\pi_9$：只有起点附近的还差
• $\pi_{10}$：全部变好！

直观上的理解：

• 我在某状态 $s$ 下选择其 greedy action 严重依赖于其他状态的策略。如果其他状态 $s^\prime$ 有能够到达目标区域的策略，那我只需要让 $s$ 到 $s^\prime$ 就能到达目标区域，得到正的 reward。

---

Lec 14 截断策略迭代算法

比较值迭代与策略迭代

策略迭代：从 $\pi_0$ 开始

• 策略评估（PE）：$v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}$
• 策略改进（PI）：$\pi_{k+1} = \argmax_\pi (r_\pi + \gamma P_\pi v_{\pi_k})$

值迭代：从 $v_0$ 开始

• 策略更新（PU）：$\pi_{k+1} = \argmax_\pi (r_\pi + \gamma P_\pi v_k)$
• 值更新（VU）：$v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k$

两个算法非常相似。

$$\begin{align*} \text{Policy iteration：} \pi_0 \xrightarrow{\text{PE}} &v_{\pi_0} \xrightarrow{\text{PI}} \pi_1 \xrightarrow{\text{PE}} v_{\pi_1} \xrightarrow{\text{PI}} \pi_2 \xrightarrow{\text{PE}} v_{\pi_2} \xrightarrow{\text{PI}} \cdots \\ \text{Value iteration：} \quad \qquad &u_0 \xrightarrow{\text{PU}} \pi_1^\prime \xrightarrow{\text{VU}} u_1 \xrightarrow{\text{PU}} \pi_2^\prime \xrightarrow{\text{VU}} u_2 \xrightarrow{\text{PU}} \cdots \end{align*}$$

我们详细比较每一步骤：

	策略迭代算法	值迭代算法	备注
1) 策略：	$\pi_0$	N/A
2) 值：	$v_{\pi_0} = r_{\pi_0} + \gamma P_{\pi_0} v_{\pi_0}$	$\color{red}{v_0 \coloneqq v_{\pi_0}}$
3) 策略：	$\pi_1 = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_0})$	$\pi_1 = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_0)$	两个策略相同
4) 值：	$\color{lightblue}{v_{\pi_1} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}}$	$\color{lightblue}{v_1 = r_{\pi_1} + \gamma P_{\pi_1} v_0}$	$v_{\pi_1} \geq v_1$，因为 $v_{\pi_1} \geq v_{\pi_0}$
5) 策略：	$\pi_2 = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_1})$	$\pi_2^\prime = \argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_1)$
$\vdots$	$\vdots$	$\vdots$	$\vdots$

• 它们从相同的初始条件出发。
• 前三步是相同的。
• 第四步开始变得不同：
  • 在策略迭代中，求解 $v_{\pi_1} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}$ 需要一个迭代算法（无限次迭代）
  • 在值迭代中，$v_1 = r_{\pi_1} + \gamma P_{\pi_1} v_0$ 是一步迭代

截断策略迭代

考虑上面第四步求解 $\color{lightblue}{v_{\pi_1} = r_{\pi_1} + \gamma P_{\pi_1} v_{\pi_1}}$ 的过程，

截断策略（truncated policy iteration）迭代示意图

我们可以发现：

• 值迭代计算一次
• 策略迭代计算无穷次
• 截断策略迭代计算有限次（$j$ 次）

伪代码

截断策略迭代算法

• 初始化： 概率模型 $p(r|s,a)$ 和 $p(s^\prime|s,a)$ 对所有 $(s,a)$ 均已知。初始猜测 $\pi_0$。
• 目标： 搜索最优状态值和最优策略。
• 当策略尚未收敛时，执行第 $k$ 次迭代：
  • 策略评估：（PE）
    • 初始化： 选取初始猜测为 $v_k^{(0)} = v_{k-1}$。最大迭代次数设为 $j_{\text{truncate}}$。
    • 当 $j < j_{\text{truncate}}$ 时，执行：
      • 对每个状态 $s \in \mathcal{S}$，执行：

        $$v_k^{(j+1)}(s) = \sum_{a} \pi_k(a|s) \left[ \sum_{r} p(r|s,a) r + \gamma \sum_{s^\prime} p(s^\prime|s,a) v_k^{(j)}(s^\prime) \right]$$

    • 令 $v_k = v_k^{(j_{\text{truncate}})}$
  • 策略改进：（PI）
    • 对每个状态 $s \in \mathcal{S}$，执行：
      • 对每个动作 $a \in \mathcal{A}(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)$$

      • $a_k^*(s) = \arg\max_{a} q_k(s,a)$
      • $\pi_{k+1}(a|s) = 1$ 若 $a = a_k^*$，否则 $\pi_{k+1}(a|s) = 0$

但我们只计算有限步，是否会导致算法不再收敛？

从直观上看，截断策略迭代应介于值迭代和策略迭代之间。不用担心，收敛性从数学上可由以下定理保证！

命题（值改进）：考虑求解策略评估步骤的迭代算法：

$$v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}$$

若初始猜测选为 $v_{\pi_k}^{(0)} = v_{\pi_{k-1}}$，则有

$$v_{\pi_k}^{(j+1)} \geq v_{\pi_k}^{(j)}, \quad j=0,1,2,\ldots$$

证明： 一方面，因为 $v_{\pi_k}^{(j)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j-1)}$ 且 $v_{\pi_k}^{(j+1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(j)}$，所以有

$$v_{\pi_k}^{(j+1)} - v_{\pi_k}^{(j)} = \gamma P_{\pi_k}(v_{\pi_k}^{(j)} - v_{\pi_k}^{(j-1)}) = \cdots = \gamma^j P_{\pi_k}^j(v_{\pi_k}^{(1)} - v_{\pi_k}^{(0)}). \tag{4.5}$$

另一方面，因为 $v_{\pi_k}^{(0)} = v_{\pi_{k-1}}$，所以有

$$v_{\pi_k}^{(1)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(0)} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_{k-1}} \geq r_{\pi_{k-1}} + \gamma P_{\pi_{k-1}} v_{\pi_{k-1}} = v_{\pi_{k-1}} = v_{\pi_k}^{(0)},$$

上式不等号是因为 $\pi_k = \arg\max_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_{k-1}})$。

将 $v_{\pi_k}^{(1)} \geq v_{\pi_k}^{(0)}$ 代入 式(4.5)，可得 $v_{\pi_k}^{(j+1)} \geq v_{\pi_k}^{(j)}$。

值迭代、策略迭代、截断策略迭代三种算法的收敛速度示意图

可以看到：

• 策略迭代收敛最快；
• 值迭代收敛最慢；
• 截断策略迭代介于两者之间。

例子

在下图（左）的情境下使用截断策略迭代算法。

定义 $\|v_k - v^*\|$ 为时刻 $k$ 的状态值误差。停止准则为 $\|v_k - v^*\| < 0.01$。

• 横轴：迭代次数（iteration num）
• 纵轴：状态值误差（state value error）

截断策略迭代示例

可以发现：对 truncated policy iteration-x 算法：

• $x$ 值越大（策略评估中迭代次数越多），值估计收敛越快。
• 但当 $x$ 很大时，增加 $x$ 的收益迅速下降。
• 实践中，在策略评估步骤执行少量的迭代次数即可。

---

总结

• 值迭代：求解贝尔曼最优方程的迭代算法。给定初始值 $v_0$，

  $$v_{k+1} = \max_\pi (r_\pi + \gamma P_\pi v_k)$$

  等价于两步：$\begin{cases} \text{策略更新（PU）：} \pi_{k+1} = \argmax_\pi (r_\pi + \gamma P_\pi v_k) \\ \text{值更新（VU）：} v_{k+1} = r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k \end{cases}$

• 策略迭代：给定初始策略 $\pi_0$，

  由两步实现：$\begin{cases} \text{策略评估（PE）：} v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k} \\ \text{策略改进（PI）：} \pi_{k+1} = \argmax_\pi (r_\pi + \gamma P_\pi v_{\pi_k}) \end{cases}$

• 截断策略迭代：策略评估中执行有限步迭代