策略迭代（Policy Iteration）

策略迭代的大概思想是：首先给定一个任意策略，迭代贝尔曼方程，求得当前策略下的值函数，然后根据值函数更新策略，调整后的策略又可以计算值函数，这样循环往复，直到策略收敛。

策略迭代算法包含两个大的过程：

• 策略评估：就是计算值函数
• 策略提升：基于上一步的值函数估计一个更好的策略

基本步骤

策略迭代的具体实施步骤如下：

• 初始化：初始化所有状态的值函数和一个任意的初始策略$\pi (s)$
• 策略评估：通过贝尔曼方程，求出当前策略下的值函数，直到值函数收敛
• 策略更新：利用步骤2的值函数更新策略，更新的原则是在$s$上选择$a$，使得$V(s)$最大（贪婪思想）
• 重复步骤2和步骤3，直到策略收敛

例子：公主的营救

在这个游戏中：

• 王子每回合可以往上、下、左、右四个方向移动
• 每走一步，体力值减1，记为-1
• 找到公主，游戏结束
• 目标是最小体力损耗找到公主

这个一个标准的马尔科夫决策过程(MDP)：

• State：王子所在位置
• Action：上/下/左/右走一格
• Reward：体力损耗
• 折扣因子为1

首先初始化$V(s)$为0，$\pi (s)$为均匀随机策略。

什么是均匀随机策略？如下，在任意状态，可以上下左右走，若走出框，则返回原位置，奖励仍记为-1

接下来进行策略评估，计算$V(s)$，应用的公式是
$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)\left(R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V_{\pi }(s^{{}^{\prime }})\right)$$

因此，第一个格子的$V_{\pi }(s)$：
$$V_{\pi }(s)=0.25\ast (-1+0)+0.25\ast (-1+0)+0.25\ast (-1+0)+0.25\ast (-1+0)=-1$$
类似的，可以计算出每个格子的 $V_{\pi }(s)$，结果如下：

由于公主是最终状态，即没有状态流出，所以是0。

进行第二次计算，第一个格子：
$$V_{\pi }(s)=0.25\ast （-1+-1）+0.25\ast （-1+-1）+0.25\ast （-1+-1）+0.25\ast （-1+-1）=-2$$

中央的格子：
$$V_{\pi }(s)=0.25\ast （-1+-1）+0.25\ast （-1+-1）+0.25\ast （-1+-1）+0.25\ast （-1+0）=-1.75$$

以此类推，再进行一此计算之后，价值分布：

假设我们走到这一步，已经 收敛 了。那么我们可以进行下一步，策略提升。

如何使用贪婪思想进行策略提升呢？

首先看王子所在的位置，他可以上下左右走，往上走计算$q(s,a)$是-4，往下走是-3.875，往左走是-4，往右走是-3.9375，我们在这四个数中选一个最大的，显然，往下走是最大的。因此，我们取最大的max，把往下走的可能性提升为100%，舍弃掉其他不如这个的策略。

再看中间部分，可知往下走是最大的，可以将策略优化为向下，最终，可以得到如下的策略：

然后，在新的策略下，再计算$V(s)$至收敛，然后再得到新的策略，然后再计算$V(s)$至收敛，如此往复，直到策略收敛（更新前后的策略计算的$V(s)$接近）。整个过程如下所示：
$${\pi }_0\stackrel{E}{⟶}{V}_{\pi 0}\stackrel{I}{⟶}{\pi }_1\stackrel{E}{⟶}{V}_{\pi 1}\stackrel{I}{⟶}{\pi }_2\stackrel{E}{⟶}\cdots \stackrel{I}{⟶}{\pi }_{\ast }\stackrel{E}{⟶}{V}_{\pi \ast }$$

最终，就得到了最优策略，以及最优策略下的最优状态值。

价值迭代（Value Iteration）

价值迭代（Value Iteration）是求解马尔可夫决策过程（MDP）的一种方法，用于找到最优策略。价值迭代的基本思想是，通过迭代计算状态的价值函数，直到这些价值函数不再发生变化，从而得到最优的状态价值分布。

基本步骤

• 初始化：为所有的状态$s$赋一个初始价值$V(s)$，通常可以选择一个保守的估计，如0。
• 对于每个状态$s$，计算其预期价值。即从该状态出发，采取各种可能的行为所能获得的最大期望回报。公式如下：
  $$V^{\ast }(s)=\underset{a}{\max }\left(R(s,a)+\gamma \sum _{s^{{}^{\prime }}\in S}p(s^{{}^{\prime }}|s,a)V^{\ast }(s^{{}^{\prime }})\right)$$
• 终止条件：判断价值函数是否收敛，即对于所有状态，价值函数值不再发生变化。如果收敛，则终止迭代；否则，回到第2步继续迭代。
• 输出最优策略：一旦价值函数收敛，可以通过查看在每一步选择中哪个行动使得价值最大来确定每个状态的最优策略。

例子：公主的营救

在这个游戏中：

• 王子每回合可以往上、下、左、右四个方向移动
• 每走一步，体力值减1，记为-1
• 找到公主，游戏结束
• 目标是最小体力损耗找到公主

这个一个标准的马尔科夫决策过程(MDP)：

• State：王子所在位置
• Action：上/下/左/右走一格
• Reward：体力损耗
• 折扣因子为1

首先，对于每个状态，初始化$V(s)=0$：

然后进行第一轮迭代，对于每个state，逐一尝试上、下、左、右四个Action，记录每个Action带来的Reward，取最大的Reward作为状态的价值。因此，第一轮迭代完成后，状态价值分布如图：

因为公主所在的状态是最终状态（没有下一状态），所以公主的状态还是0，不会发生变化。

接着进行第二轮迭代，第二轮迭代完成后的价值分布如下：

第三轮迭代完成后的价值分布如下：

第四轮迭代完成后的价值分布如下：

在第四轮迭代中，所有$V(s)$更新前后都没有任何变化，我们认为价值迭代已经找到了最优策略。

策略迭代与价值迭代的区别

实现方式

策略迭代是一种基于策略的方法，它通过不断更新策略来寻找最优策略。具体来说，策略迭代包括两个步骤：策略评估和策略改进。在策略评估中，我们通过当前策略来评估每个状态的价值函数；在策略改进中，我们根据当前状态的价值函数来更新策略，使得策略更加贴近最优策略。

值迭代是一种基于值函数的方法，它通过不断更新值函数来寻找最优策略。具体来说，值迭代通过不断迭代更新每个状态的价值函数，直到价值函数收敛为止。然后，我们可以根据最终的价值函数来得到最优策略。

目标

策略迭代的目标是直接优化策略，通过不断迭代更新策略来逼近最优策略。然而，由于每次迭代都需要进行策略评估和策略改进，计算量较大。

值迭代的目标是通过优化状态值函数来得到最优策略。它通过不断更新每个状态的价值函数来逼近最优价值函数，然后根据这个最优价值函数导出最优策略。相对于策略迭代，值迭代的计算量较小。

收敛速度

通常来说，策略迭代通常更快地收敛到最优策略，但每一次迭代通常需要更多的计算。而值迭代可能需要更多的迭代次数才能收敛。

与其他技术的交互

值迭代更容易与函数近似方法（如深度学习）结合，因为它关注的是优化值函数。策略迭代则更多地用在具有明确模型的场景。