4.1-值迭代
4.1 值迭代¶
本节介绍值迭代算法。该算法正是上一章(定理\(3.3\))中所介绍的，由压缩映射定理提出的用于求解贝尔曼最优公式的算法。具体而言，该算法是
定理\(3.3\)保证了当\(k\)趋于无穷时，\(v_k\)和\(\pi_k\)分别收敛到最优状态值和最优策略。
该算法是迭代式的，每一步迭代包含两个步骤。
-
每次迭代的第一步是策略更新步骤(policy update)。从数学上讲，其目标是找到一个能够解决以下优化问题的策略：
\[\pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_k),\]其中\(v_k\)是在前一次迭代中获得的。
-
第二步称为值更新步骤(value update)。在数学上，它通过以下方式计算一个新的值\(v_{k+1}\)：
\[v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{k},\tag{4.1}\]其中\(v_{k+1}\)将在下一次迭代中使用。
Note
注: 思想就是先固定\(v_k\)，找到一个新策略，然后利用新策略更新\(v_k\)
上面介绍的值迭代算法采用的是矩阵向量形式。为了实现该算法，我们需要进一步考察其逐元素形式。虽然矩阵向量形式有助于理解算法的核心思想，但逐元素形式对于实现细节是必要的。
4.1.1 逐元素形式与实现¶
考虑时间步\(k\)和状态\(s\)。
-
首先，策略更新步骤\(\pi_{k+1}=\arg\max_\pi(r_\pi+\gamma P_\pi v_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_{k}(s^{\prime})\right)}_{q_{k}(s,a)},\quad s\in\mathcal{S}.\]我们在第\(3.3.1\)节中表明，能够解决上述优化问题的最优策略是
\[\pi_{k+1}(a|s)=\left\{\begin{array}{ll}1,&a=a_k^*(s),\\0,&a\neq a_k^*(s),\end{array}\right.\tag{4.2}\]其中\(a_k^*(s) = \arg\max_a q_k(s,a)\)。如果\(a_k^*(s) = \arg\max_a q_k(s,a)\)有多个解，我们可以任选其中一个，而不会影响算法的收敛性。由于新的策略\(π_{k+1}\)选择\(q_k(s, a)\)最大的行动，因此这种策略被称为Greedy策略(greedy)。
-
其次，值更新步骤的逐元素形式为\(v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{k}\)。
\[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}.\]将\((4.2)\)代入上式，得到
\[v_{k+1}(s)=\max_{a}q_{k}(s,a).\]
总之，上述步骤可以概括为
实现细节在算法\(4.1\)中进行了总结。
算法\(4.1\): 值迭代算法的伪代码
一个可能令人困惑的问题是，\((4.1)\)中的\(v_k\)是否为状态值。答案是否定的。尽管\(v_k\)最终会收敛到最优状态值，但并不能保证它满足任何策略的贝尔曼公式。例如，它通常不满足\(v_k = r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_k\)或\(v_k = r_{\pi_{k}}+\gamma P_{\pi_{k}}v_k\)。它仅仅是由算法生成的一个中间值。此外，由于\(v_k\)不是状态值，\(q_k\)也不是动作值。
4.1.2 示例¶
接下来，我们给出一个例子，以说明值迭代算法的逐步实现过程。这个例子是一个两行两列的网格，其中包含一个禁区(图4.2)。目标区域为\(s_4\)。奖励设置为\(r_{boundary} = r_{forbidden} = −1，r_{target} = 1\)。折现率为\(\gamma= 0.9\)。
图\(4.2\): 一个用于演示值迭代算法实现的示例。
每个状态-动作对的q值表达式如表4.1所示。
表\(4.1\): 如图\(4.2\)所示示例中\(q(s, a)\)的表达式。
-
\(k=0\):
不失一般性，选择初始值为 \(v_0(s_1) = v_0(s_2) = v_0(s_3) = v_0(s_4) = 0\)。
\(q\)值计算：将\(v_0(s_i)\)代入表\(4.1\)，可得到表\(4.2\)中所示的\(q\)值。
策略更新: \(\pi_1\)是通过为每个状态选择具有最大\(q\)值的动作得到的：
\[\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.\]该策略在图\(4.2\)(中间子图)中进行了可视化。很明显，该策略不是最优的，因为它在\(s_1\)时选择保持不动。值得注意的是，\((s_1,a_5)\)和\((s_1,a_3)\)的\(q\)值实际上是相同的，我们可以随机选择其中任一动作。
值更新：\(v_1\)是通过将每个状态的最大\(q\)值更新为\(v\)值得到的：
\[v_1(s_1) = 0, \quad v_1(s_2) = 1, \quad v_1(s_3) = 1, \quad v_1(s_4) = 1.\]
表\(4.2\): 在\(k = 0\)时\(q(s,a)\)的值。
-
\(k=1\):
\(q\)值计算：将\(v_1(s_i)\)代入表\(4.1\)，可得到表\(4.3\)中所示的\(q\)值。
策略更新: \(\pi_2\)是通过为每个状态选择具有最大\(q\)值的动作得到的：
\[\pi_1(a_3|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.\]该策略在图\(4.2\)(右子图)中进行了可视化。
值更新：\(v_2\)是通过将每个状态的\(v\)值更新为最大的\(q\)值而得到的：
\[v_2(s_1) = \gamma 1, \quad v_2(s_2) = 1 + \gamma 1, \quad v_2(s_3) = 1 + \gamma 1, \quad v_2(s_4) = 1 + \gamma 1.\]
表\(4.3\): 在\(k = 1\)时\(q(s,a)\)的值。
-
\(k=2,3,4,...\)
值得注意的是，如图\(4.2\)所示，策略\(\pi_2\)已经是最优的。因此，我们在这个简单的例子中，只需要运行两次迭代即可获得最优策略。对于更复杂的例子，我们需要运行更多的迭代，直到\(v_k\)的值收敛(例如，直到\(\|v_{k+1}-v_k\|\)小于预先设定的阈值)。