4.2-策略迭代
本节介绍另一种重要的算法：策略迭代 (policy iteration)。策略迭代与值迭代有着密切的关系，不过它并非像值迭代那样直接求解贝尔曼最优方程。而是在策略评价和策略改进之间来回切换，这种思想在强化学习中广泛存在。
4.2.1 算法分析¶
策略迭代也是一种迭代算法。每次迭代包含两个步骤，具体来说，这两个步骤如下所述：
-
第一步是策略评估 (policy evaluation)步骤。顾名思义，这个步骤是用来评估上一次迭代得到的策略\(\pi_k\)。从书上雪上来说，该步骤就是求解下面的贝尔曼方程，从而得到\(\pi_k\)的状态值：
\[v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k},\tag{4.3}\]其中，\(\pi_k\)是上一次迭代中得到的策略，\(v_{\pi_k}\)是该策略对应的状态值。\(r_{\pi_k}\)和\(P_{\pi_k}\)可以根据系统模型得到。
-
第二个是策略改进 (policy improvement)。从数学上来说，在第一步得到\(v_{\pi_k}\)之后，此步骤就会利用下式得到新的策略\(\pi_{k+1}\)：
\[\pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_{\pi_k}).\]为了透彻理解该算法，我们需要回答下面三个问题：
-
在策略评估步骤中，如何计算状态值 \(v_{\pi_k}\)？
- 在策略改进步骤中，新策略\(π_{k+1}\)为什么比\(\pi_k\)更好？
- 为什么该算法最终能够收敛到最优策略？
接下来，我们将逐一回答这些问题。
Q1: 在策略评估步骤中，如何求解状态值 \(v_{\pi_k}\)？¶
我们在第\(2\)章中介绍了两种求解贝尔曼方程\((4.3)\)的方法。下面我们简要回顾这两种方法。第一种方法是直接给出解析解：\(v_{\pi_k}=(I-\gamma P_{\pi_k})^{-1}r_{\pi_k}\)。解析解对于理论分析很有用，但在实际应用中计算效率较低，这是因为需要使用其他数值方法来计算逆矩阵。第二种方法利用如下的数值迭代算法：
其中\(v^{(j)}_{π_k}\)表示对\(v_{π_k}\)第\(j\)次的估计值。从任意初始值\(v^{(0)}_{\pi_k}\)开始，随着\(j \rightarrow \infty\)，有\(v^{(j)}_{\pi_k}\rightarrow v_{\pi_k}\)，具体细节请参见第\(2.7\)节。
在策略迭代中我们会使用上面的第二种方法。此时策略迭代就成了一个嵌套了另一个迭代算法的迭代算法，即策略迭代本身是一个迭代算法，而每次迭代中的策略评价步骤需要调用另一个迭代算法\((4.4)\)。
从理论上讲，算法\((4.4)\)需要无限步(即\(j \to \infty\))才能收敛到真实的状态值\(v_{\pi_k}\)，在实际中，该算法并不能执行无限多步，而只能设置为有限多步，例如\(\| v_{\pi_k}^{(j+1)} - v_{\pi_k}^{(j)}\|\)小于预设的阈值或\(j\)超过预设的值，迭代就会终止，有的读者会问，如果无法执行无限次迭代，那么只能得到一个\(v_{\pi_k}\)的近似值，那么这个近似值将会用于随后的策略改进策略，那么是否会导致无法找到最优策略呢？答案是否定的，原因将在我们后面介绍的截断策略迭代算法(\(4.3\)节)的时候就会清楚。
Note
注: 这个地方需要重点理解一下这两个迭代之间的区别，避免后面弄混。
Q2: 在策略改进步骤中，为什么新策略\(π_{k+1}\)比\(\pi_k\)更优？¶
策略改进步骤可以改进给定的策略，如下所示。
Info
引理4.1(策略改进). 若 \(\pi_{k+1} = \arg\max_\pi(r_\pi + \gamma P_\pi v_\pi^k)\)，则\(v_{\pi_{k+1}} \geq v_{\pi_k}\)。
上述引理中，\(v_{\pi_{k+1}} \geq v_{\pi_k}\)是逐元素的比较，即对于任意状态\(s\)有\(v_{\pi_{k+1}}(s) ≥ v_{\pi_k}(s)\)。该引理的证明见Box 4.1。因此\(π_{k+1}\)比\(\pi_k\)更优。
Q3: 为什么策略迭代算法最终能够找到最优策略？¶
策略迭代算法会生成两个序列。第一个是策略序列：\(\{\pi_0,\pi_1,...,\pi_k, ...\}\)，第二个是状态值序列：\(\{v_{\pi_0}, v_{\pi_1},...,v_{\pi_k},...\}\)。假设\(v^*\)是最佳状态值，那么对于所有\(k\)都有\(v_{\pi_k}\leq v^*\)。根据引理4.1，我们知道策略在不断改进，因此有：
由于\(v_{\pi_k}\)是单调递增且有上界\(v^*\)，根据单调收敛定理[12]，当\(k\rightarrow\infty\) 时，\(v_{\pi_k}\)收敛到一个常数，记为 \(v_\infty\)。以下分析表明\(v_\infty=v^*\)。
Info
定理4.1. (策略迭代的收敛性)由策略迭代算法生成的状态值序列\(\{v_{\pi_k}\}_{k=0}^{\infty}\)收敛到最优状态值\(v^∗\)。因此，策略序列\(\{\pi_k\}^\infty_{k=0}\)收敛于一个最优策略。
该定理的证明见Box \(4.2\)。该证明不仅表明了策略迭代算法的收敛性，还揭示了策略迭代算法与值迭代算法之间的关系。值迭代的收敛性可以推出策略迭代的收敛性。换句话说，策略迭代比值迭代的收敛性更强。
4.2.2 算法的展开形式¶
为了编程实现策略迭代算法，我们需要研究其逐元素展开形式。
-
第一，策略评估步骤通过\((4.4)\)中的迭代算法来求解贝尔曼公式\(v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k}v_{\pi_k}\)从而得到\(v_{\pi_k}\)，算法\((4.4)\)的逐元素展开形式为：
\[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=0,1,2,...\)
当\(j\to\infty\)，\(j\)足够大或\(\|v_{\pi_{k}}^{(j+1)}-v_{\pi_{k}}^{(j)}\|\)足够小时时停止迭代。
-
第二，策略改进步骤求解\(\pi_{k+1} = \arg \max_\pi(r_\pi + \gamma P_\pi v_{\pi_k})\)。该方程的元素展开形式为：
\[\pi_{k+1}(s)=\arg\max_{\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(s) =\arg\max_a q_{\pi_k}(s,a)\)。那么上述优化问题的解为：
\[\pi_{k+1}(a|s)=\left\{\begin{array}{ll}1,&a=a_k^*(s),\\0,&a\neq a_k^*(s).\end{array}\right.\]
上述算法的伪代码在\(4.2\)中展示。
算法\(4.2\): 策略迭代算法的伪代码
4.2.3 示例¶
一个简单的例子¶
考虑图\(4.3\)中的例子。其中有两个状态，每个状态有三种可能的动作：\(\mathcal{A} = \{a_l, a_0, a_r\}\)。这三种动作分别表示向左移动、保持不变和向右移动。奖励设置为\(r_{boundary} = −1\)和\(r_{target} = 1\)。折扣因子为\(\gamma = 0.9\)。
图4.3: 一个用于说明策略迭代算法实现的示例。
接下来，我们逐步介绍策略迭代算法的实现过程。当\(k = 0\)时，如图\(4.3(a)\)所示，该策略并不理想，因为它没有朝着目标区域移动。接下来，我们将展示如何应用策略迭代算法来获得最优策略。
-
第一，在策略评估步骤中求解贝尔曼公式，该例子对应的贝尔曼方程为：
\[\begin{aligned}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{aligned}\]由于该方程很简单，可以直接手动求解得出：
\[v_{\pi_0}(s_1) = -10, \\v_{\pi_0}(s_2)= -9.\]我们也可以通过\((4.4)\)中的迭代算法求解。例如，选择初始状态值为\(v_{\pi_0}^{(0)}(s_1) = v_{\pi_0}^{(0)}(s_2) = 0.\)。根据算法\((4.4)\)可知:
\[\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}\]最后可以得到\(v_{\pi_{0}}^{(j)}(s_{1})\to v_{\pi_{0}}(s_{1})=-10\)且\(v_{\pi_{0}}^{(j)}(s_{2})\to v_{\pi_{0}}(s_{2})=-9\)
-
第二，在策略改进步骤的关键在于计算每个状态-行动对配对的\(q_{\pi_0}(s,a)\)。以下\(q\)表可以用来演示这一过程：
表\(4.4\): 图\(4.3\)中示例的\(q_{\pi_k}(s,a)\)的表达式。
将上一步策略评估中得到的\(v_{\pi_0}(s_1) = −10\)和\(v_{\pi_0}(s_2) = −9\) 代入表\(4.4\)可得表\(4.5\)。
表\(4.5\): 当\(k=0\)时，\(q_{\pi_k}(s,a)\)的值。
在每一个状态，新的策略应该选择的最大价值动作，由此可得新策略\(\pi_1\)：
\[\pi_1(a_r|s_1)=1,\quad\pi_1(a_0|s_2)=1.\]这个策略在图\(4.3(b)\)中展示出来了，直观上可以看到这个策略是最优的。
因为上面例子很简单，因此一次迭代就足以找到最优策略。对于更复杂的示例，则需要更多的迭代。
一个复杂的例子¶
接下来，我们使用一个更复杂的例子(图\(4.4\))来演示策略迭代算法。奖励设置为：\(r_{boundary} = −1，r_{forbidden} = −10，r_{target} = 1\)。折扣因子为\(\gamma = 0.9\)。
从初始策略(图\(4.4(a)\))开始，策略迭代算法能够逐渐收敛到最优策略(图\(4.4(h)\))。如果我们观察策略的演变，就会发现两个有趣的现象。
-
第一，接近目标区域的状态会比远离目标区域的状态更早找到最优策略。实际上，要想从远离的目标的状态出发到达目标，必须要求靠近目标的状态先找到通往目标的路径。
-
第二，接近目标区域的状态的状态值更高。这是因为如果从较远状态出发到达目的地，所得到的回报会被大打折扣，从而状态值较小。
图\(4.4\): 策略迭代算法生成的策略的演化过程。