强化学习 2. 马尔可夫决策过程

前言

从零开始学习ai文章系列计划是个人在《动手学深度学习》和《磨菇书》两本书的学习中的个人笔记，文章也会以课本中的章节分开，即每个章节一片笔记。我会尽量的把主要内容以及遇到的难点进行记录与解决，如果哪里有错误的欢迎指正。或者不清晰的可以直接查看原文部分。

《蘑菇书》原文（课本）：https://datawhalechina.github.io/easy-rl/#/

（由于有时候公式太多，可能会直接贴图片）

蘑菇书的文章结构不会跟之前《动手学深度学习》按照原文章节进行，个人会适当调节。

虽然考虑过分多个章节，但是感觉全放在一起看比较流畅。

---

1. 马尔可夫性质

马尔可夫性质（Markov property）是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布 仅依赖于当前状态。

我们设状态的历史为 \(h_t={s_1,s_2,s_3,…,s_t}\)（\(h_t\) 包含了之前的所有状态），则马尔可夫过程满足条件：(这里p是概率) \[ p(s_{t+1}|s_t) = p(s_{t+1}|h_t) \] 离散时间的马尔可夫过程 也称为马尔可夫链（Markov chain）。

例如，图 2.2 里面有4个状态，这4个状态在 \(s_1,s_2,s_3,s_4\) 之间互相转移。比如从 \(s_1\) 开始，\(s_1\) 有 0.1 的概率继续存留在 \(s_1\) 状态，有 0.2 的概率转移到 \(s_2\)，有 0.7 的概率转移到 \(s_4\) 。如果 \(s_4\) 是我们的当前状态，它有 0.3 的概率转移到 \(s_2\) ，有 0.2 的概率转移到 \(s_3\) ，有 0.5 的概率留在当前状态。

我们可以用状态转移矩阵（state transition matrix）P 来描述状态转移 \(p( s_{t+1}=s' ∣ s_t=s)\)：

状态转移矩阵类似于条件概率（conditional probability），它表示当我们知道当前我们在状态st时，到达下面所有状态的概率。所以它的每一行描述的是从一个节点到达所有其他节点的概率。

2.马尔可夫奖励过程（Markov reward process, MRP）

马尔可夫奖励过程（Markov reward process, MRP）是 马尔可夫链 加上 奖励函数。

马尔可夫奖励过程中，状态转移矩阵和状态都与马尔可夫链一样，只是多了奖励函数（reward function）。奖励函数R是一个期望，表示当我们到达某一个状态的时候，可以获得多大的奖励。这里另外定义了折扣因子 γ 。如果状态数是有限的，那么 R 可以是一个向量。

奖励函数 实际上理解成 即时奖励 就行了。即执行动作后，到达某个状态获得的奖励。

2.1 回报与价值函数

回报（return）可以定义为奖励的逐步叠加，假设时刻t后的奖励序列为 \(r_{t+1},r_{t+2},r_{t+3},...\) ，则回报为

其中，T是最终时刻（t是开始时刻），γ 是折扣因子，越往后得到的奖励，折扣越多。这说明我们更希望得到现有的奖励，对未来的奖励要打折扣。

当我们有了回报之后，就可以定义状态的价值了，就是状态价值函数（state-value function）。对于马尔可夫奖励过程，状态价值函数被定义成回报的期望，即：

期望就是从这个状态开始，我们可能获得多大的价值。所以期望也可以看成未来可能获得奖励的当前价值的表现，就是当我们进入某一个状态后，我们现在有多大的价值。

我们使用折扣因子的原因如下：

1. 有些马尔可夫过程是带环的，它并不会终结，我们想避免无穷的奖励。
2. 我们并不能建立完美的模拟环境的模型，我们对未来的评估不一定是准确的，我们不一定完全信任模型，因为这种不确定性，所以我们对未来的评估增加一个折扣。我们想把这个不确定性表示出来，希望尽可能快地得到奖励，而不是在未来某一个点得到奖励。
3. 如果奖励是有实际价值的，我们可能更希望立刻就得到奖励，而不是后面再得到奖励（现在的钱比以后的钱更有价值）。
4. 我们也更想得到即时奖励。有些时候可以把折扣因子设为 0（γ=0），我们就只关注当前的奖励。我们也可以把折扣因子设为 1（γ=1），对未来的奖励并没有打折扣，未来获得的奖励与当前获得的奖励是一样的。折扣因子可以作为强化学习智能体的一个超参数（hyperparameter）来进行调整，通过调整折扣因子，我们可以得到不同动作的智能体。

2.2 举例说明

以 下图2.4 举例说明我们之前所学的概念。

奖励函数可以定义为：智能体进入第一个状态 \(s_1\) 的时候会得到 5 的奖励，进入第七个状态 \(s_7\) 的时候会得到 10 的奖励，进入其他状态都没有奖励。

我们对以下3种 4步骤的回合（γ=0.5）来计算回报 G。

1. \(s_4,s_5,s_6,s_7\) 的回报: 0 + 0.5×0 + 0.25×0 + 0.125×10 = 1.25
2. \(s_4,s_3,s_2,s_1\) 的回报: 0 + 0.5×0 + 0.25×0 + 0.125×5 = 0.625
3. \(s_4,s_5,s_6,s_6\) 的回报: 0 + 0.5×0 + 0.25×0 + 0.125×0 = 0

(第一个0当成从某个初始状态 \(s_0\) 必定到达 \(s_4\) 即可，而并不是说从 \(s_4\) 开始。因为奖励的定义是到达某一个状态后才获取的奖励)

我们对轨迹 \(s_4,s_5,s_6,s_7\) （第一个）的奖励进行计算，这里折扣因子是 0.5。

1. 在 \(s_4\) 的时候，奖励为0。
2. 下一个状态 \(s_5\) 的时候，因为我们已经到了下一步，所以要把 \(s_5\) 进行折扣， \(s_5\) 的奖励也是0。
3. 然后是 \(s_6\) ，奖励也是0，折扣因子应该是0.25。
4. 到达 \(s_7\) 后，我们获得了一个奖励，但是因为状态 \(s_7\) 的奖励是未来才获得的奖励，所以我们要对之进行3次折扣。

最终这个轨迹的回报就是 1.25。类似地，我们可以得到其他轨迹的回报。

这里就引出了一个问题，当我们有了一些轨迹的实际回报时，怎么计算它的价值函数呢？

比如我们想知道 \(s_4\) 的价值，即当我们进入 \(s_4\) 后，它的价值到底如何？一个可行的做法就是我们可以生成很多轨迹，然后把轨迹都叠加起来。比如我们可以从 \(s_4\) 开始，采样生成很多轨迹，把这些轨迹的回报都计算出来，然后将其取平均值作为我们进入 \(s_4\) 的价值。这其实是一种计算价值函数的办法，也就是通过蒙特卡洛（Monte Carlo，MC）采样的方法计算 \(s_4\) 的价值。

3. 贝尔曼方程

贝尔曼方程（Bellman equation）：

• \(s'\) 可以看成未来的某一状态（全部状态集合S中的一个），
• \(p(s'∣s)\) 是指从 当前状态s 转移到 未来状态s′ 的概率。
• \(V(s')\) 代表的是未来某一个状态 \(s'\) 的价值。
• R(s) 通常定义为“处在状态 s 时，下一步获得的期望奖励”，也可以理解为“从 s 出发一步后得到的奖励的期望”。

我们从当前状态开始，有一定的概率去到未来的所有状态，所以我们要把 p(s′∣s) 写上去。我们得到了未来状态后，乘一个 γ，这样就可以把未来的奖励打折扣。

贝尔曼方程就是 当前状态 与 未来状态的迭代关系，表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动态规划创始人理查德 ⋅ 贝尔曼（Richard Bellman）而得名 ，也叫作“动态规划方程”。

3.1 解析解

假设有一个马尔可夫链如图 2.5a 所示，贝尔曼方程描述的就是当前状态到未来状态的一个转移。

如图 2.5b 所示，假设我们当前在 \(s_1\) ， 那么它只可能去到3个未来的状态：有 0.1 的概率留在它当前位置，有 0.2 的概率去到 \(s_2\) 状态，有 0.7 的概率去到 \(s_4\) 状态。所以我们把状态转移概率乘它未来的状态的价值，再加上它的即时奖励（immediate reward），就会得到它当前状态的价值。

我们可以把贝尔曼方程写成矩阵的形式：

当我们把贝尔曼方程写成矩阵形式后，可以直接求解：

我们可以直接得到解析解（analytic solution）：

我们可以通过矩阵求逆把 V 的价值直接求出来。但是一个问题是这个矩阵求逆的过程的复杂度是 \(O(N^3)\) 。所以当状态非常多的时候，比如从10个状态到1000个状态，或者到100万个状态，当我们有100万个状态的时候，状态转移矩阵就会是一个100万乘100万的矩阵，对这样一个大矩阵求逆是非常困难的。所以这种通过解析解去求解的方法只适用于很小量状态的马尔可夫奖励过程。

3.2 贝尔曼更新

我们也可以用动态规划的方法，一直迭代贝尔曼方程，直到价值函数收敛，我们就可以得到某个状态的价值。我们通过自举（bootstrapping）的方法不停地迭代贝尔曼方程，当最后更新的状态与我们上一个状态的区别并不大的时候，更新就可以停止，我们就可以输出最新的 V′(s) 作为它当前的状态的价值。这里就是把贝尔曼方程变成一个贝尔曼更新（Bellman update），这样就可以得到状态的价值。

初始化所有 V(s) 为0，对于某个状态s，根据 \(V'(s)=R(s)+\gamma \sum^{}_{s' \in S}P(s'|s)V(s')\) 更新当前状态s的价值，对于所有状态s重复此步骤，每轮重复此过程，直到所有状态 V(s) 不再大幅度变化

本质上就是一种价值迭代的方法。我们后面会提到策略迭代和价值迭代。

4. 马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作）状态转移也多了一个条件，变成了 \(p(s_{t+1}=s'|s_t)\) 。未来的状态不仅依赖于当前的状态，也依赖于在当前状态智能体采取的动作。马尔可夫决策过程满足条件：\(p(s_{t+1}=s'|s_t) = p(s_{t+1}=s'|h_t)\) （ \(h_t\) 表示：到时间 t 为止的历史信息（history）。

对于奖励函数，它也多了一个当前的动作，变成了 \(R(s_t=s,a_t=a)\) 。当前的状态以及采取的动作会决定智能体在当前可能得到的奖励多少。

4.1 马尔可夫决策过程中的策略

策略定义了在某一个状态应该采取什么样的动作。一般用\(\pi\) 表示我们的策略。 \[ \pi(a|s)=p(a_t=a|s_t=s) \] 概率代表在所有可能的动作里面怎样采取行动，比如可能有 0.7 的概率 a=往左走，有 0.3 的概率 a=往右走，这是一个概率的表示。

在马尔可夫决策过程里面，状态转移函数 \(P(s'∣s,a)\) 基于它当前的状态以及它当前的动作。因为我们现在已知策略函数，也就是已知在每一个状态下，可能采取的动作的概率，所以我们就可以直接把动作进行加和，去掉 a，这样我们就可以得到对于马尔可夫奖励过程的转移，这里就没有动作，即

可以发现现在我们 计算 s到s′ 的概率并不需要动作a。即原本的P(s′∣s,a) 变成了P(s′∣s)。这就是所谓的马尔可夫决策过程 转换成 马尔可夫奖励过程。

4.2 马尔可夫决策过程 和 马尔可夫过程/马尔可夫奖励过程的区别

两者最主要的就是状态转移的方式。

在 马尔可夫过程/马尔可夫奖励过程 状态的转移是直接从一个状态到另一个状态，如 \(s_1 \rightarrow s_2\).

而在 马尔可夫决策过程 中，状态的转移是通过动作决定的，如 \(s_1执行动作a_1 \rightarrow s_2\) .

4.3 马尔可夫决策过程中的价值函数

让我们回忆之前的马尔可夫决策过程中的价值函数定义为

即从状态s开始，所有回报的期望。

那么在马尔可夫决策过程中，我们另外引入了一个 Q 函数（Q-function）。Q 函数也被称为动作价值函数（action-value function）。Q 函数定义的是在某一个状态采取某一个动作，它有可能得到的回报的一个期望，即

如果对 Q 函数中的动作进行加和，就可以得到价值函数：

此处我们对 Q 函数的贝尔曼方程进行推导：

推导说明，可跳过

我们从这步开始继续推导，首先根据状态s执行动作a后到达下一状态s'的概率，展开E

根据马尔可夫性质未来的回报 未来的回报 \(G_{t+1}\) 只取决于这个 s′，

将该方程带入之前一开始的展开中，得到如下公式（原来推导中最终结果）

如果我们重新合并概率P，就能得到原来推导中的下面公式（\(s_{t+1}\)就是s'）

5. 贝尔曼期望方程

我们可以把状态价值函数和 Q 函数拆解成两个部分：即时奖励和后续状态的折扣价值（discounted value of successor state）。

通过对状态价值函数进行分解，我们就可以得到一个类似于之前马尔可夫奖励过程的贝尔曼方程————贝尔曼期望方程（Bellman expectation equation）：

对于 Q 函数，我们也可以做类似的分解，得到 Q 函数的贝尔曼期望方程：（其中下一状态所执行的动作a是由当前策略\(\pi\) 决定的）

贝尔曼期望方程定义了当前状态与未来状态之间的关联。

我们之前的贝尔曼方程那节提到，V(s)的定义为：

R(s) 通常定义为“处在状态 s 时，下一步获得的期望奖励”，也可以理解为“从 s 出发一步后得到的奖励的期望”。这里可以当成 \(\sum_{s' \in S}{[p(s'|s)*r_{s'}]}\) ，这里的s'与后面的未来奖励计算同步。

所以原式应该为 \[ V(s)=\sum_{s' \in S}{\{p(s'|s)* [r_{s'}+\gamma V(s')]\}} \]

其中

也就是说我们的策略已经融入其中。这种方式只有在有模型的条件下才能计算，即知道状态转移概率p的情况下。我们能直接计算出p(s'|s)

事实上我们大多数情况下是无模型的，即不知道这个状态转移概率p。那么我们该如何得到价值V(s)呢。我们只需要按照期望的公式，重复在当前策略 \(\pi\) 下采样获取 \(r_{t+1}+\gamma V_{\pi}(s_{t+1})\) ，然后求平均即可。

我们假设参数X符合某个概率分布，我们从中采样N次，获得 \(x_1,x_2,…,x_N\)

那么根据大数定律： \[ \frac{1}{N} \sum_{i=1}^{N}{x_i}≈ \mathbb{E}[X] \]

我们进一步进行简单的分解，先给出式（2.8）：

接着，我们再给出式(2.9)：

我们把式(2.9)代入式(2.8)可得(2.10)

式(2.10)代表当前状态的价值 与 未来状态价值之间的关联。

6. 策略评估和控制

6.1 马尔可夫决策过程中的策略评估

计算价值函数的过程就是策略评估。

同步备份是指每一次的迭代都会完全更新所有的状态，这对于程序资源的需求特别大。

异步备份（asynchronous backup）的思想就是通过某种方式，使得每一次迭代不需要更新所有的状态，因为事实上，很多状态也不需要被更新。

备份类似于自举之间的迭代关系，将价值信息从一个状态（或状态-动作对）的后继状态（或状态-动作对）转移回它。

在英文原文中，“to back up” 不仅仅有“备份”这个意思。

back up your car 倒车（往后移动）🚗

back up your argument 用证据支持（从后面支撑）

back up the value 从后面的状态把价值传回来（RL语境）

但是我们实际上更常用的表达是更新

比如从V(s)依赖V(s')进行更新

我们再来看一个动态的例子，推荐斯坦福大学的一个网页，这个网页模拟了式(2.18)所示的单步更新的过程中，所有格子的状态价值的变化过程。

https://cs.stanford.edu/people/karpathy/reinforcejs/gridworld_dp.html

但是由于他的计算结果不符合他给出的公式

所以我这里仅仅只是按照原文提及，不推荐。我会在后续策略迭代和价值迭代中用自己的代码重新实现。

在b站上找到的案例，来简单解释。

根据公式

我们能看到-1.7的计算由来

6.2 马尔可夫决策过程控制

找到最优策略的过程就是控制

首先介绍最佳价值函数：

最佳价值函数是指，我们搜索一种策略 \(\pi\) ， 让每个状态的价值最大。\(V^∗\) 就是到达每一个状态，它的值的最大化情况。 在这种最大化情况中，我们得到的策略就是最佳策略，即

最佳策略使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个最佳价值函数，就可以认为某个马尔可夫决策过程的环境可解。在这种情况下，最佳价值函数是一致的，环境中可达到的上限的值是一致的，但这里可能有多个最佳策略，多个最佳策略可以取得相同的最佳价值。

当取得最佳价值函数后，我们可以通过对 Q 函数进行最大化来得到最佳策略：

当Q函数收敛后，因为 Q 函数是关于状态与动作的函数，所以如果在某个状态采取某个动作，可以使得 Q 函数最大化，那么这个动作就是最佳的动作。如果我们能优化出一个 Q 函数 \(Q^∗(s,a)\) ，就可以直接在 Q 函数中取一个让 Q 函数值最大化的动作的值，就可以提取出最佳策略。

搜索最佳策略有两种常用的方法：策略迭代和价值迭代。

6.3 策略迭代

策略迭代由两个步骤组成：策略评估和策略改进（policy improvement）。

如图 2.21a 所示，

第一个步骤是策略评估，当前我们在优化策略 \(\pi\) ，在优化过程中得到一个最新的策略。我们先固定这个策略不变，然后估计它的价值，即 给定当前的策略函数 来估计 状态价值函数。

第二个步骤是策略改进，得到 状态价值函数后，我们可以进一步推算出它的 Q 函数。得到 Q 函数后，我们直接对 Q 函数进行最大化，通过在 Q 函数做一个贪心的搜索来进一步改进策略。

这两个步骤一直在迭代进行。所以如图 2.21b 所示，在策略迭代里面，在初始化的时候，我们有一个初始化的状态价值函数 V 和 策略 \(\pi\) ，然后在这两个步骤之间迭代。

图 2.21b 上面的线就是我们当前状态价值函数的值，下面的线是策略的值。 策略迭代的过程与踢皮球一样。我们先给定当前已有的策略函数，计算它的状态价值函数。算出状态价值函数后，我们会得到一个 Q 函数。我们对Q 函数采取贪心的策略，这样就像踢皮球，“踢”回策略。然后进一步改进策略，得到一个改进的策略后，它还不是最佳的策略，我们再进行策略评估，又会得到一个新的价值函数。基于这个新的价值函数再进行 Q 函数的最大化，这样逐渐迭代，状态价值函数和策略就会收敛。

经典策略迭代中，环境具有有限状态集合 S，同时动作集合 A 也是有限的，因此可选策略数量是有限的，所以实质上就是：

单调改进 + 有限策略空间 → 必然在有限步内到达最优策略

我们这里的策略\(\pi\) 是与参数无关的，因此对每个状态能进行直接的修改。后续我们会使用网络作为我们的策略，而网络是由各种参数构成的，因此我们的策略是与参数θ相关的，我们的策略也从\(\pi\) 变成了 \(\pi_{\theta}\) 。

相比原来有许多的不同，

1. 即使对于某一状态我们通过修改参数对其进行调整，也会影响到其他状态。
2. 策略集合不再是“所有策略”，它只是一个子集。比如线性方程无法完全拟合曲线。原来的策略中所有状态都有单独的动作进行修改，即存在全部可能。而使用网络后只能表达部分的策略。

因为参数 \(\theta\) 是一个连续数，其空间是无限的，可能出现震荡、鞍点、局部最优等现象。所以无法确定在有限步内能到达最优策略。也就是说，后续网络策略 \(\pi_{\theta}\) 并不严格遵从这里说的策略迭代理论。

6.4 价值迭代

最优性原理：一个策略\(\pi\) 在状态 s 达到了最优价值，那么对于任何能够从 s 到达的 s′的所有状态，在策略中都已经达到了最优价值。

举个例子方便理解，假设从A走到C：A → B → C

如果当前 \(V(A)\) 在策略\(\pi\) 下是最优的，那么根据最优性原理，可以得出 \(V(B)\) 价值也是最优的。

为什么会得出这个结论呢，我们可以用价值更新公式来理解：

我们当前的 \(V(A)\) 的价值计算需要下一状态价值\(V(B)\)，那么如果当前策略策略 \(\pi\) 是最优的话，当前 \(V(A)=V^*(A)\) （当前的V(A)是最大的)。那么很自然得出计算V(A)所需的V(B)也是最大的，即 \(V(B)=V^*(B)\)。

依次推理，所有后续的状态价值V(s)都是最优的。这也就是所谓的后继的状态的每一步都按照最优的策略去做。

这和我们价值迭代有什么关系呢？价值迭代做的工作类似于价值的反向传播，每次迭代做一步传播。从终点状态开始逐步的传播到其他状态，就像之前的下图一样。如果某状态达到了最优，则该状态与终点之间就存在了最优线路。

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

其核心区别在于更新的目标不同。

在策略迭代中，我们的更新目标是策略。

举例：为了更新策略

在评估阶段：我们会根据当前策略，计算此时的所有状态s的Q(s,a)值。

在控制阶段：我们会根据计算出来的Q(s,a)，调整原来的策略，将动作动作概率重新分配到能获得最大的Q(s,a)的动作上，从而获得新的策略。

在价值迭代中，我们的更新目标是价值。

正如我们之前所说：价值迭代做的工作类似于价值的反向传播。

举例：

首先我们根据公式 \[ Q(s,a)=R(s,a)+\gamma \sum^{}_{s' \in S}P(s'|s,a)V(s') \] 计算出状态s下的所有Q值（这里没有策略\(\pi\) 参与，）

然后 \(当前的V(s)=最大的Q(s,a)\)

直到所有状态的V值稳定下来，我们策略就是执行能获取最大V(s)值的动作a。

以上仅仅是为了解释说明 策略迭代 和 价值迭代 区别而举的例子，实际上后续由于网络的参与，我们价值也由网络替代，而不是固定的值。

7.实战

7.1 环境

和之前连接中的格子一样，终点是绿色那个，红色的是奖励为-1的陷阱。灰色为障碍，进去会回退到原来的格子中，边界也是。其他白色的是奖励为0的无害区域。

正如之前所说，链接中执行和文章所写的对不上，因此个人自制环境进行表达。

上下左右箭头代表最优动作a的方向，初始是均等随机，因此四个箭头都有。左边的数字则是价值。也可以理解为最高的Q(s,a)的值。除此外陷阱、终点、障碍等位置均与上图一直。其表达请自行查看。

可以再看一个效果最终图

环境代码：

import numpy as np

# === GridWorld 基本参数 ===
rows, cols = 10, 10
gamma = 0.9
theta = 1e-4
actions = ['↑', '↓', '←', '→']
action_delta = {'↑': (-1, 0), '↓': (1, 0), '←': (0, -1), '→': (0, 1)}
goal = (5, 5)
obstacles = {(2, 1),(2,2),(2,3),(2,4),(2,6),(2,7),(2,8)
             ,(3,4),(4,4),(5,4),(6,4),(7,4)} # 障碍 (y↓,x→)
punishment={(3,3),(4,5),(4,6),(5,6),(5,8),(6,8),(7,3),(7,5),(7,6),}

# === 初始化状态值函数和策略 ===
V = np.zeros((rows, cols))
policy = {}
for r in range(rows):
    for c in range(cols):
        if (r, c) in obstacles or (r, c) == goal:
            continue
        policy[(r, c)] = {a: 0.25 for a in actions}
        # policy[(r, c)] = {'↑': 0.25, '↓': 0.25, '←': 0.25, '→': 0.25}

还有用来打印展示的代码

def print_policy(V, policy, iteration,ss='',show_a=True):
    cell_width = 12  # 每个格子占固定宽度
    """打印每次迭代的值函数与策略"""
    print(f"\n=== Policy Iteration {iteration} === {ss}")
    for r in range(rows):
        line = ""
        for c in range(cols):
            if (r, c) in obstacles:
                text = "■■■"
            elif (r, c) in punishment:
                actions_str = ''.join([a for a, prob in policy[(r, c)].items() if prob > 0])
                if show_a:
                    text = f"■{V[r,c]:.2f}■{actions_str}"
                else:
                    text = f"■{V[r, c]:.2f}■"
            elif (r, c) == goal:
                text = f"■T■"
            else:
                actions_str = ''.join([a for a, prob in policy[(r, c)].items() if prob > 0])
                if show_a:
                    text = f"{V[r, c]:.2f}{actions_str}"
                else:
                    text = f"{V[r, c]:.2f}"
            # 居中对齐
            line += text.center(cell_width)
        print(line)

7.2策略迭代

首先来查看主流程。通过policy_evaluation 函数进行策略评估，算出当前每个状态的价值。然后通过policy_improvement 进行策略改进。每一轮重复执行这两步骤。

iteration = 0
# 策略迭代
for i in range(20):
    iteration += 1
    V = policy_evaluation(V, policy, gamma, theta)
    print_policy(V, policy, iteration,'策略评估')

    policy, stable = policy_improvement(V, policy, gamma)
    print_policy(V, policy, iteration,'策略改进')

接下来看策略评估内容。

主要看下图红框中的两行

v += prob * (reward + gamma * V[nr, nc])

我们将s能到达的下一状态s‘的价值V[nr, nc] 按照概率进行加权求和。将此结果当作状态s的新的价值。

然后是策略改进的部分。

最后我们能看一下效果，首先是第一轮的策略评估和策略改进

然后对比第20轮

7.3 价值迭代迭代

也还是先看主流程。可以看到，循环内只有一个策略评估在不断迭代。因为与动作无关，所以我们打印的时候关闭了动作。

在价值迭代结束后，我们进行一次策略改进。（我们原来的策略迭代中就是选择最优策略，因此这里可以重复使用。）

for i in range(20):
    iteration += 1
    V = policy_evaluation2(V, policy, gamma, theta)
    print_policy(V, policy, iteration,'策略评估',show_a=False)
    
policy, stable = policy_improvement(V, policy, gamma)
print_policy(V, policy, iteration, '策略改进')

然后是价值迭代的函数内容

看上去和之前是不是很像，红框的地方就是差异点。我们之前说过，价值迭代，不需要策略参与，所以之前我们按照策略给出了动作概率prob，对各个动作进行加权求和。而这里，我们直接对各个可能的动作进行价值迭代计算，不需要使用策略给出的概率。然后我们选择最高的更新值为我们的价值。

查看下运行效果。

前几轮：

像不像一口小喷泉，从目标处开始将价值扩散到所有的状态。

最终20轮

然后我们最终进行一次策略改进