跳转至

4.3-截断策略迭代

本节将介绍一种更一般化的算法，称为截断策略迭代 (truncated policy iteration)。我们会看到，值迭代算法和策略迭代算法是截断策略迭代算法的两种特殊情况。

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}策略迭代算法: \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\\值迭代算法: \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}\]

可以看出，这两种算法的步骤非常相似。为了比较这两个算法，我们让它们从相同的初始条件开始，即选择\(v_0 = v_{\pi_0}\)(如果不从相同的初始条件开始，则无法定量比较)。两种算法的步骤列于表\(4.6\)中。在在最初的三个步骤中，两种算法生成了相同的结果。从第四步开始，它们开始表现出不同。具体来说，在第四步，值迭代算法执行\(v_1=r_{\pi_1}+\gamma P_{\pi_1}v_0,\)，这是仅需一步的计算。相比之下，策略迭代算法需要求解\(v_{\pi_{1}}=r_{\pi_{1}}+\gamma P_{\pi_{1}}v_{\pi_{1}},\)这是需要多次迭代的计算。

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

Note

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

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

  • 如果迭代仅运行一次，那么\( v_{\pi_1}^{(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_0 = v_{\pi_0}\)这两个条件。如果没有这个条件，这两种算法是不能直接进行量化比较的。

4.3.2 截断策略迭代算法

截断策略迭代算法的伪代码参见算法\(4.3\)。它与前面介绍的策略迭代算法的唯一区别在于它在策略评估步骤只运行了有限次迭代。

值得注意的是，算法中的\(v_k\)和\(v^{(j)}_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节]。

到目前为止，截断策略迭代的优势已经明确。与策略迭代算法相比，它在策略评估步骤中仅需要有限次迭代，因此计算效率更高，与值迭代算法相比，它在策略评估步骤中运行了多次迭代，因此可以得到更好得估计值。

评论