4.3-截断策略迭代

4.3 截断策略迭代¶

接下来，我们介绍一种更通用的算法，称为截断策略迭代。我们会看到，值迭代算法和策略迭代算法是截断策略迭代算法的两种特殊情况。

4.3.1 比较值迭代与策略迭代¶

首先，我们通过列出以下步骤来比较值迭代和策略迭代算法。

策略迭代：选择任意一个的初始策略 \(\pi_0\)。在第\(k\)次迭代中，执行以下两个步骤。
- 步骤 1：策略评估(PE)。给定\(\pi_k\)，求解\(v_{\pi_k}\)，满足
  
  \[v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}.\]
- 步骤 2：策略改进(PI)。给定\(v_{\pi_k}\)，从以下公式求解\(\pi_{k+1}\)：
  
  \[\pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_{\pi_k}).\]
值迭代：选择任意一个的初始值\(v_0\)。在第\(k\)次迭代中，执行以下两个步骤。
- 步骤 1：策略更新(PU)。给定\(v_k\)，从以下公式求解\(\pi_{k+1}\)：
  
  \[\pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_{\pi_k}).\]
- 步骤2: 值更新(VU)。给定\(\pi_{k+1}\)，从以下式子中求解\(v_{k+1}\)：
  
  \[v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{k}.\]

上述两个算法的步骤可以表示为:

\[\begin{aligned}\text{Policy iteration:} \quad \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 &v_0 \xrightarrow{\text{PU}} \pi_1^\prime \xrightarrow{\text{VU}} v_1 \xrightarrow{\text{PU}} \pi_2^\prime \xrightarrow{\text{VU}} v_2 \xrightarrow{\text{PU}} \cdots\end{aligned}\]

可以看出，这两种算法的步骤非常相似。

图\(4.6\): 策略迭代与值迭代的实现步骤比较。

我们更仔细地考察它们的价值步骤，以了解这两种算法之间的差异。特别地，让两种算法都从相同的初始条件开始：\(v_0 = v_{\pi_0}\)。两种算法的步骤列于表\(4.6\)中。在最初的三个步骤中，由于\(v_0=v_{\pi_0}\)，两种算法生成了相同的结果。它们在第四步变得有所不同。在第四步中，值迭代算法执行\(v_1=r_{\pi_1}+\gamma P_{\pi_1}v_0,\)，这是一个一步计算；而策略迭代算法求解\(v_{\pi_{1}}=r_{\pi_{1}}+\gamma P_{\pi_{1}}v_{\pi_{1}},\)，则需要进行无限次迭代。如果我们显式写出第四步中求解\(v_{\pi_1}=r_{\pi_1}+\gamma P_{\pi_1}v_{\pi_1}\)的迭代过程，一切就会变得清晰。通过令\(v_{\pi_1}^{(0)}=v_0\)，我们有

Note

注: 可以发现，\(v_1\)并不是真正的状态值，\(v_{\pi_1}\)却是状态值。

从上述过程可以得出以下观察结果。

如果迭代仅运行一次，则 \( v_{\pi_1}^{(1)} \) 实际上就是在值迭代算法中计算出的 \( v_1 \)。
如果迭代运行无限次，则 \( v_{\pi_1}^{(\infty)} \) 实际上就是在策略迭代算法中计算出的 \( v_{\pi_1} \)。
如果迭代运行有限次数（记为 \( j_{\text{truncate}} \)），则该算法称为截断策略迭代。之所以称为截断，是因为从 \( j_{\text{truncate}} \) 到 \( \infty \) 的剩余迭代被截断了。

因此，值迭代算法和策略迭代算法可以被视为截断策略迭代算法的两种极端情况：值迭代在\(j_{\text{truncate}}=1\)时终止，策略迭代在\(j_{\text{truncate}}=\infty\)时终止。需要注意的是，尽管上述比较具有说明性，但它基于\(v_{\pi_1}^{(0)} = v_0 = v_{\pi_0}\)的条件。如果没有这个条件，这两种算法就无法直接进行比较。

4.3.2 截断策略迭代算法¶

简而言之，截断策略迭代算法与策略迭代算法相同，只是在策略评估步骤中仅执行有限次数的迭代。其具体实现细节总结在算法\(4.3\)中。值得注意的是，算法中的\(v_k\)和\(v^{(j)}_k\)并不是状态值，而是对真实状态值的近似，因为在策略评估步骤中仅执行了有限次数的迭代。

如果\(v_k\)不等于\(v_{\pi_k}\)，算法是否仍然能够找到最优策略？答案是肯定的。直观上讲，截断策略迭代介于值迭代和策略迭代之间。一方面，由于在策略评估步骤中它执行了不止一次迭代，因此其收敛速度比值迭代算法更快；另一方面，由于它只执行有限次数的迭代，因此其收敛速度又比策略迭代算法慢。这种直观解释在图\(4.5\)中得到了说明。这种直观认识也得到了以下分析的支持。

图\(4.5\): 值迭代、策略迭代和截断策略迭代算法之间关系的示意图。

Note

命题4.1(价值改进)。考虑迭代算法中的评估评估步骤:

\[v_{\pi_k}^{(j+1)}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}^{(j)},\quad j=0,1,2,...\]

如果初始猜测选择为\(v^{(0)}_{\pi_k} = v_{\pi_{k−1}}\)，则有

\[v_{\pi_k}^{(j+1)}\geq v_{\pi_k}^{(j)},\quad j=0,1,2,...\]

值得注意的是，命题\(4.1\)要求假设\(v_{\pi_{k}}^{(0)}=v_{\pi_{k-1}}\)。然而，在实际中\(v_{\pi_{k−1}}\)是不可用的，只有\(v_{k−1}\)可用。尽管如此，命题\(4.1\)仍然为截断策略迭代算法的收敛性提供了启示。关于这一主题的更深入讨论可参见[2，第6.5节]。

到目前为止，截断策略迭代的优势很明显。与策略迭代算法相比，截断策略迭代算法仅需在策略评估步骤中进行有限次数的迭代，因此计算效率更高。与值迭代相比，截断策略迭代算法在策略评估步骤中多运行几次迭代，可以加快其收敛速度。