4.1-值迭代
本节介绍第一个能够求解最优策略的算法-值迭代 (value iteration)。该算法实际上正是定理\(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\)
上述算法是以矩阵向量形式呈现的。为了实现该算法，我们需要进一步分析其按元素展开形式 (elementwise form)。在此之前需要明确，\((4.1)\)中的\(v_k\)是否是状态值？答案是否定的。尽管当\(k\)趋于无穷时\(v_k\)会收敛到最优状态值，但是当\(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}.\]上述优化问题的最优解为：
\[\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)\)有多个相同的解，那么可以任选其中一个，而不会影响算法的收敛性。
-
其次，值更新步骤\(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).\]即新的值等于状态\(s\)对应的最大\(q\)值。
上述步骤可以概括为如下形式：
上述算法的伪代码参见算法\(4.1\)。
算法\(4.1\): 值迭代算法的伪代码
4.1.2 示例¶
下面通过一个简单的例子来详细说明值迭代算法的实现过程。如图\(4.2\)所示，这例子是一个\(2\times 2\)的网格世界，其中有一个禁止区域和一个目标区域。奖励设置为\(r_{boundary} = r_{forbidden} = −1，r_{target} = 1\)，\(\gamma= 0.9\)。
图\(4.2\): 一个用于演示值迭代算法实现的示例。
首先，我们可以建立每个状态-动作对的q-table，其中每一个元素展示了如何从\(v\)值计算出\(q\)值。
表\(4.1\): 如图\(4.2\)所示示例中\(q(s, a)\)的表达式。
表\(4.2\): 在\(k = 0\)时\(q(s,a)\)的值。
-
\(k=0\):
初始值为\(v_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\)，得到的\(q\)值如表\(4.2\)中所示。
策略更新: 每个状态的策略应更新为选择最大\(q\)值的行动。基于此，通过表\(4.2\)可以看出新的策略为：
\[\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.\]在状态\(s_1\)，由于行动\(a_3\)和\(a_5\)的\(q\)值是相等的，因此可以随机选择其中一个值，这里我们选择的是\(a_5\)。图\(4.2\)中间图展示了上面得到的新策略。
值更新：每个状态的\(v\)值应该更新为其最大\(q\)值，由此可得如下新值：
\[v_1(s_1) = 0, \quad v_1(s_2) = 1, \quad v_1(s_3) = 1, \quad v_1(s_4) = 1.\]不难看出，这次迭代得到的策略不是最优的，因为它在\(s_1\)时选择保持不动。下面继续迭代
表\(4.3\): 在\(k = 1\)时\(q(s,a)\)的值。
-
\(k=1\):
计算\(q\)值：将\(v_1(s_i)\)代入表\(4.1\)，得到表\(4.3\)中的\(q\)值。
策略更新: \(\pi_2\)是通过为每个状态选择具有最大\(q\)值的行动得到的。因此，通过表\(4.3\)可以看出新的策略为：
\[\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\)值更新为最大的\(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.\]如果需要，则可以继续迭代。
-
\(k=2,3,4,...\)
值得注意的是，如图\(4.2\)的右图所示，策略\(\pi_2\)已经是最优的。因此，在这个简单的例子中，只需要运行两次迭代即可获得最优策略。对于更复杂的例子，我们需要运行更多轮的迭代，直到\(v_k\)的值收敛(例如，直到\(\|v_{k+1}-v_k\|\)小于预先设定的阈值)。